Deep Dive into Caffeine Cache: High‑Performance Design, W‑TinyLFU Algorithm, and Implementation Details

Overview

Caffeine is a high‑performance, low‑memory local cache for Java that is often described as the "next‑generation" or "modern" cache, improving on Guava Cache with better hit rates and throughput.

Comparison with Guava Cache

The article references a previous Guava Cache tutorial and notes that Spring 5 has replaced Guava Cache with Caffeine due to superior benchmark results.

Using Caffeine

Typical usage mirrors Guava Cache: import the Caffeine package, create a LoadingCache with builder options such as maximumSize , expireAfterAccess , expireAfterWrite , refreshAfterWrite , and provide a CacheLoader . An example code snippet demonstrates setting size limits, expiration policies, a writer, and a loader.

High‑Performance Design (W‑TinyLFU)

The core of Caffeine’s performance is the W‑TinyLFU eviction policy, which combines a small window cache, a probation segment, and a protected segment (SLRU). New entries first enter the window; when the window overflows, entries are promoted to probation, and a frequency‑based filter decides whether to evict the victim from the main cache.

W‑TinyLFU Details

W‑TinyLFU uses a FrequencySketch based on a Count‑Min Sketch to approximate access frequencies with only 4 bits per entry (max 15). The sketch increments on each read/write via onAccess . When the total count reaches a threshold, all frequencies are halved (freshness mechanism).

Eviction Policy

When the cache exceeds its maximum size, evictEntries moves excess items from the window to probation, then compares candidates from probation with the LRU victim using admit . The candidate wins if its frequency is higher; ties are broken with a small random chance to protect against hash‑collision attacks.

Adaptive Window Size (Climb)

The climb method dynamically adjusts the window size based on recent hit‑rate changes. It computes an adjustment amount, expands or shrinks the window, and rebalances the protected and probation segments to suit workload characteristics (e.g., OLTP vs. OLAP).

Asynchronous High‑Performance Read/Write

Caffeine separates cache operations from maintenance work using buffers. Reads enqueue a Node into a readBuffer ; writes use a writeBuffer . Buffers are drained asynchronously, reducing lock contention on hot keys.

Read Buffer (Striped Ring Buffer)

The read buffer is a striped, non‑blocking bounded buffer built on StripedBuffer and RingBuffer . Each thread hashes to its own sub‑buffer, avoiding hotspot contention. The buffer may drop entries if full, which is acceptable for read‑side statistics.

Write Buffer (MPSC Queue)

Writes use a Multiple‑Producer/Single‑Consumer queue ( MpscGrowableArrayQueue ) that allows many threads to enqueue without locks while a single consumer processes the operations promptly.

Timer Wheel Expiration

For variable expiration times (via .expireAfter ), Caffeine employs a hierarchical timer wheel. Each entry is placed into a bucket based on its absolute expiration time; the wheel advances in ticks, efficiently expiring entries without scanning the entire cache.

Other Optimizations

Additional techniques include soft/weak references, false‑sharing mitigation, and CompletableFuture‑based asynchronous loading.

Conclusion

Caffeine combines the W‑TinyLFU algorithm, lock‑free read/write buffers, and a timer‑wheel to deliver near‑optimal hit rates, low latency, and modest memory usage, making it a superior choice for Java backend caching.