A method of inserting cache blocks into a cache queue includes detecting a first cache miss for the cache queue, identifying a storage block receiving an access in response to the cache miss, calculating a first estimated cache miss cost for a first storage container that includes the storage block, calculating an insertion probability for the first storage container based on a mathematical formula of the first estimated cache miss cost, randomly selecting an insertion probability number from a uniform distribution, and inserting, in response to the insertion probability exceeding the insertion probability number, a new cache block corresponding to the storage block into the cache queue.