Patent ID: 8601216

Claim:
A method for removing a cache block from a cache queue associated with a cache, the method comprising: detecting, by a processor, a first cache miss, wherein the cache comprises a plurality of memory units storing values from a plurality of storage blocks within a storage, wherein the cache queue comprises a plurality of cache blocks referencing memory units in the cache, and wherein the first cache miss comprises an access to an uncached storage block; identifying, within the cache queue, a new cache block storing a value of a storage block, wherein the storage block is located in a storage container occupying a portion of the storage; calculating an estimated access rate for the storage container based upon cache hits received by recycled new cache blocks associated with storage blocks located in the storage container; calculating, by the processor and based upon the estimated access rate and a latency of the storage container, an estimated cache miss cost for the storage container; calculating, by the processor, a removal probability for the storage container based on a mathematical formula of the estimated cache miss cost; randomly selecting a probability number from a uniform distribution, wherein the removal probability exceeds the probability number; and evicting, in response to the removal probability exceeding the probability number, the new cache block from the cache queue.