1. A cache server operative as one of a plurality of cache servers of a distributed cache, comprising: a processor; and a memory connected to the processor, the memory storing instructions executed by the processor to: receive a cache storage request, establish a cache eviction requirement in response to the cache storage request, identify an evict entry within a cache of the cache server in response to the cache eviction requirement, wherein the evict entry is selected from a random sampling of entries within the cache, wherein the random sampling of entries is a random sampling of less than 1% of entries within the cache and wherein the evict entry is subject to an eviction policy that identifies a probabilistically favorable eviction candidate within the random sampling of entries without deterministically identifying a favorable eviction candidate of all entries within the cache, remove the evict entry from the cache, and load content associated with the storage request into the cache.