The performance and capacity characteristics of flash storage make it attractive to use as a cache. Recency-based cache replacement policies rely on an in-memory full index, typically a B-tree or a hash table that maps each object to its recency information. Even though the recency information itself may take very little space, the full index for a cache holding N keys requires at least logN bits per key. This metadata overhead is undesirably high when used for very large flash-based caches, such as key - value stores with billions of objects. To solve this problem, the authors propose a new RAM-frugal cache replacement policy that approximates the Least-Recently-Used (LRU) policy.