Caching hard
How does the 'TinyLFU' admission policy (used in Caffeine/Ristretto) improve upon LRU for scan-heavy workloads?
- A It prioritizes the allocation of additional system memory to handle the overhead of expensive scanning operations during periods of peak load.
- B It utilizes a probabilistic filter (Count-Min Sketch) to track frequency history, only admitting new items if they are more popular than the victim candidate.
- C It temporarily disables the caching mechanism for any incoming request identified as part of a large-scale linear scanning workload in the database.
- D It leverages a random sampling algorithm that periodically purges keys from the cache hierarchy regardless of their actual access frequency or recency.
Answer: B. It utilizes a probabilistic filter (Count-Min Sketch) to track frequency history, only admitting new items if they are more popular than the victim candidate.
**TinyLFU** uses a **Count-Min Sketch** (probabilistic frequency counter) to track the historical popularity of items. When the cache is full, it compares the victim (LRU) with the incoming item. If the incoming item is historically less popular ('one-hit wonder'), it is rejected (not admitted). This protects the cache from being polluted by scans or low-value data.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- In the Cache-Aside pattern, what happens when the application requests data that is missing from the cache (a 'Cache Miss')?
- Why use a centralized Distributed Cache (like a Redis Cluster) over local in-memory caches on each web server?
- Setting a short TTL (e.g., 60 seconds) on a cached object helps to:
- What is the primary architectural goal of introducing a cache into a system?
- Most caching systems rely on the principle of 'Temporal Locality', which states:
- Your cache uses an LRU (Least Recently Used) eviction policy. When the cache is full, which item is removed?