Cache Eviction Policies in Storage Engines

Caching is a concept in computer science that stores frequently accessed items in fast-access volatile storage to improve performance. Retrieving data from a cache, rather than a more durable storage layer, improves response time and reduces computational needs.

Why is volatile storage faster?

Volatile storage consists of RAM, registers and CPU caches. Persistent storage consists of hard disk drives and solid state drives, which persist data even after power failures. HDDs require disk rotation and mechanical head movements; SSDs organize data into pages. Both are significantly slower than memory.

Cache eviction

Due to limited space, cached items that are no longer needed have to be removed to allow newer, more urgently needed items to be added. This process is called eviction. Eviction policies decide what items to remove based on a determined scheme.

• FIFO evicts the oldest item regardless of use.
• LRU evicts the least recently accessed item.
• CLOCK uses a circular buffer and an access bit.
• LFU evicts the item with the lowest access rate.

A cache is only as good as the policy that decides what to throw away.

Window TinyLFU

Window TinyLFU combines a small LRU window with a larger SLRU main cache and a TinyLFU admission policy. New items enter the window; when it fills, the window victim is compared with the main cache's probation victim. The better candidate stays.

w = 2 / error_rate
d = ln(1 / delta)
memory = w * d * counter_bits

The result is a policy that behaves like LFU for frequency-heavy workloads while still adapting to bursts. It is used in Caffeine and has implementations in Go and other languages.

Conclusion

Every eviction policy is a tradeoff between recency, frequency and metadata cost. The right choice depends on the access pattern you actually have, not the one you imagine.