> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/wisr-group/cache/index/lhd-improving-cache-hit-rate-by-maximizing-hit-density.md). # LHD: Improving Cache Hit Rate by Maximizing Hit Density https\://www\.usenix.org/conference/nsdi18/presentation/beckmann ### Presentation * Key-value cache is 100x faster than database * Crucial in modern web-application, web-server --> cache (sit at a separate cluster, DRAM, MemCache), faster than underlying database * At 98% cache hit rate * +1% hit rate --> 35% speedup * Even small hit rate improvements cause significant speedup Choosing the right eviction policy is hard * Key-value caches have unique challenges * Variable object sizes * Variable workloads * Prior policies are heuristics that combine regency and frequency * No theoretical foundation * Require hand-tuning --> fragile to workload changes * No policy works for all workloads * Prior system simulates many cache policy configurations to find right one per workload Goal: Auto-tuning eviction policy across workloads * The "big picture" of key-value caching * Goal: maximizing cache hit rate * Constraint: limited cache space * Uncertainty: in practice, don't know what is accessed again * Difficulty: variable sizes * Where does cache space go? ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FrwjElIVJVL1rxS94PP1y%2Fimage.png?alt=media\&token=05488d60-66b3-4724-82b1-82ab6a3e50af) * Hit density (HD) * Hit density combines hit probability and expected cost * Q: Don't understand, if the cost incorporates the size, why isn't that being considered as the final objective that we want to achieve? * **object's hit probability / (object size \* object's expected lifetime)** * Least hit density (LHD) policy: Trying to evict object with smallest hit density * But how do we predict these quantities? * Estimating hit density (HD) * Age - # accesses since object was last requested * Random variables * H - hit age: P \[H = 100] = probability an object hits after 100 accesses (101 access) * L - life time: P\[L = 100] = probability an object hits or is evicted after 100 accesses * Easy to estimate HD from these quantities * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FpNRGDn9073taWCBaVZM9%2Fimage.png?alt=media\&token=7965351c-3515-4c29-858c-d38eb4b27d72) * Hit probability * Expected lifetime * Example: estimating HD from object age * Estimate HD using conditional probability * Monitor distribution of H & L online * By definition, object of age a wasn't requested at age <= a * Ignore all events before a ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FAVvYAd9m3fc4oGo3nJAq%2Fimage.png?alt=media\&token=c46759c5-6f5e-437d-a803-32b6dd75ead6) * LHD by example * Users ask repeated for common objects and some user-specific objects * Best hand-tuned policy for this app: cache common media + as much user-specific as fits * Probability of referencing object again * Common object modeled as scan, user-specific object modeled as Zipf * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FLdx9Nk0c0C9KOtjS2JpX%2Fimage.png?alt=media\&token=3ae0dd4b-5543-4264-af8c-1abf1b14002d) * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FtKcINXptr5blB0YwVigr%2Fimage.png?alt=media\&token=79511616-ecab-422f-bf46-e7a771915e22) * Guard the objects up to the peak (slightly older), and after the peak, eviction policy to perform somethings like LRU * Improving LHD using additional object features * Conditional probability lets us easily add information * Condition H & L upon additional informative object features, e.g., * Which app requested this object? * How long has this object taken to hit in the past? * Features inform decisions --> LHD learns the "right" policy * No hard-code heuristics * LHD gets more hits across many traces, and needs much less space * RANKCACHE: translate theory to practice * The problem * Prior complex policies require complex data structures * Synchronization --> poor scalability --> unacceptable request throughput * Policies like GDSF require O(log N) heaps * Even O(1) LRU sometimes too slow because of synchronization * Many key-value systems approximate LRU with CLOCK / FIFO * Can LHD achieve similar request throughput to production system? * RankCache makes LHD fast * Track information approximately * Precompute HD as table indexed by age & app id & etc * Randomly sample objects to find victim * Similar to Redis, Memshare * Tolerate rare races in eviction policy * Related work * Using conditional probabilities for eviction policies in CPU caches * EVA * Fixed object sizes * Different ranking function * Prior replacement policies * Key-value: Hyperbolic, simulations, AdaptSize, Cliffhanger * Non key-value: ARC, SLRU, LRU-K * Heuristic based * Require tuning or simulation * Future directions * Dynamic latency / bandwidth optimization * Smoothly and dynamically switch between optimized hit ratio and byte hit ratio * Optimizing end-to-end response latency * App touches multiple objects per request * One such object evicted --> others should be evicted too * Modeling cost, e.g., to maximize write endurance in FLASH / NVM * Predict which objects are worth writing to 2nd tier storage from memory