Media data is distributed across multiple devices and is locatable using a hashing function and a hash table. The media data is partially replicated based on popularity thereof. In a described implementation, a media data block is locatable by hashing a media data indicator to produce a media data hash value that maps to a bin of the hash table. The bin is associated with at least one device that stores and/or with a sender that is capable of sending to clients the media data blocks mapping thereto. Each bin may have primary and secondary roles. Devices holding primary roles store all of the media data blocks mapping to a bin. Devices holding secondary roles replicate the media data blocks mapping to the bin that are also within a top predetermined popularity percentage. Popularity is determined based on numbers of clients currently requesting a particular media data portion.