Name
Abstract | ||
|---|---|---|
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 log N 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, we propose a new RAM-frugal cache replacement policy that approximates the least-recently-used (LRU) policy. It uses two in-memory Bloom sub-filters (TBF) for maintaining the recency information and leverages an on-flash key-value store to cache objects. TBF requires only one byte of RAM per cached object, making it suitable for implementing very large flash-based caches. We evaluate TBF through simulation on traces from several block stores and key-value stores, as well as evaluate it using the Yahoo! Cloud Serving Benchmark in a real system implementation. Evaluation results show that TBF achieves cache hit rate and operations per second comparable to those of LRU in spite of its much smaller memory requirements. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ICDE.2013.6544902 | ICDE |
Keywords | DocType | Citations |
new RAM-frugal cache replacement,full index,large flash-based cache,Recency-based cache replacement policy,N key,key-value store,memory-efficient replacement policy,cache hit rate,recency information,cached object,on-flash key-value store | Conference | 3 |
PageRank | References | Authors |
0.40 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Biplob Debnath | 1 | 357 | 19.47 |
| Cristian Ungureanu | 2 | 436 | 25.80 |
| Akshat Aranya | 3 | 135 | 10.11 |
| Stephen Rago | 4 | 58 | 3.63 |