# LHD: Improving Cache Hit Rate by Maximizing Hit Density ### 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? ![](/files/8SffZ6NArl8HlfdBChis) * 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 * ![](/files/wgeU7h7aezpVyLAb3msM) * 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 ![](/files/emr2M8kq4mZIewvyX1XK) * 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 * ![](/files/cseLbeLXI30hVVdKDjGG) * ![](/files/31roDp3hdnCynKTbhyRK) * 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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://sliu583.gitbook.io/blog/specific-work/wisr-group/cache/index/lhd-improving-cache-hit-rate-by-maximizing-hit-density.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.