A method for removing a cache block (156 - 164) from a cache queue, the cache block in the cache queue referencing a storage block in a cache, comprising: detecting, by a processor, a first cache miss for the cache queue, wherein a cache miss is a cache operation requesting a read or write of a storage block which does not exist in the cache and/or the cache queue; identifying, within the cache queue, a new cache block storing a value of a storage block, wherein the new cache block is a cache block that has zero accumulated cache hits since insertion into the cache queue; calculating, by the processor, an estimated cache miss cost for a storage container comprising: calculating, for the storage container, a fraction of a plurality of recycled new cache blocks that receive at least one cache hit during a second passage through the probationary segment, wherein the plurality of recycled new cache blocks receive zero cache hits during a first passage through the probationary segment; calculating, based upon the fraction, an estimated access rate; and calculating the estimated cache miss cost based upon a product of the estimated access rate and a latency of the storage container, wherein a storage container is a grouping of one or more storage blocks within a storage device; calculating (325, 408), 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; and in response to the removal probability exceeding the probability number, evicting the new cache block from the cache queue, otherwise not evicting the new cache block from the cache queue. detecting, by a processor, a first cache miss for the cache queue, wherein a cache miss is a cache operation requesting a read or write of a storage block which does not exist in the cache and/or the cache queue; identifying, within the cache queue, a new cache block storing a value of a storage block, wherein the new cache block is a cache block that has zero accumulated cache hits since insertion into the cache queue; calculating, by the processor, an estimated cache miss cost for a storage container comprising: calculating, for the storage container, a fraction of a plurality of recycled new cache blocks that receive at least one cache hit during a second passage through the probationary segment, wherein the plurality of recycled new cache blocks receive zero cache hits during a first passage through the probationary segment; calculating, based upon the fraction, an estimated access rate; and calculating the estimated cache miss cost based upon a product of the estimated access rate and a latency of the storage container, wherein a storage container is a grouping of one or more storage blocks within a storage device; calculating, for the storage container, a fraction of a plurality of recycled new cache blocks that receive at least one cache hit during a second passage through the probationary segment, wherein the plurality of recycled new cache blocks receive zero cache hits during a first passage through the probationary segment; calculating, based upon the fraction, an estimated access rate; and calculating the estimated cache miss cost based upon a product of the estimated access rate and a latency of the storage container, wherein a storage container is a grouping of one or more storage blocks within a storage device; calculating (325, 408), 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; and in response to the removal probability exceeding the probability number, evicting the new cache block from the cache queue, otherwise not evicting the new cache block from the cache queue.