LHD: Improving Cache Hit Rate by Maximizing Hit Density
summary
Introduces least hit density (LHD), a ranking that models each object's conditional probability of future hits divided by its size and expected remaining lifetime to maximize hits-per-space; implements it in RankCache built on memcached using coarse ages, precomputed tables, random victim sampling and lock-avoidance. LHD consistently outperforms LRU and recent policies, matching hit rate with on average 8× less space than LRU and 2–3× less than recent proposals, and RankCache boosts 16-thread throughput ~8× vs LRU and ~2× vs CLOCK.
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:28Key-value cache is 100X faster than database
- 1:05Key-value cache hit rate determines web application performance
- 1:41Choosing the right eviction policy is hard
- 2:56The big picture of key-value caching
- 3:29Where does cache space go?
- 6:13Our metric: Hit density (HD)
- 7:01Estimating hit density (HD)
- 8:08Example: Estimating HD from object age
- 10:19Probability of referencing object again
- 10:53LHD by example: what's the hit density?
- 12:03LHD by example: policy summary
- 12:41Improving LHD using additional object features
- 14:58The problem
- 15:39RankCache makes LHD fast
- 16:21Making evictions fast
- 17:02Serial bottlenecks dominate → LHD best throughput
- 18:33Related Work
- 19:11Future directions
- 20:20THE ADVANCED COMPUTING SYSTEMS ASSOCIATION
related talks
15mTake Out the TraChe: Maximizing (Tra)nsactional Ca(che) Hit Rate
24mWrite-Optimized Dynamic Hashing for Persistent Memory
25mDistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed...
16mJohnny Cache: the End of DRAM Cache Conflicts (in Tiered Main Memory Systems)
50mLet's talk about the cache!
11meMRC: Efficient Miss Ratio Approximation for Multi-Tier Caching
44mHow to speed up your application using JCache
25mMemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing