TBF: A Memory-Efficient Replacement Policy for Flash-based Caches

Abstract: We present a new RAM-frugal cache replacement policy that approximates the least-recently-used (LRU) policy. It uses Two Bloom Filters (TBF) in RAM for maintaining the recency information and leverages an on-flash key–value store to cache objects. TBF could be used to enhance any existing key-value stores to provide caching functionalities. TBF requires only one byte of RAM per cached object, which makes it suitable for implementing a very large flash-based key-value cache.

Bio: Biplob Debnath is a research staff member at NEC Laboratories America. He received a B.S. in Computer Science and Engineering from the Bangladesh University of Engineering and Technology, and M.Sc. and Ph.D. degrees from the University of Minnesota. His most recent works have been focusing on nonvolatile memory, data deduplication, and key-value store design. Web: www.nec-labs.com/~biplob/.