Deep Dive into Caffeine Cache: W‑TinyLFU Design, High‑Performance Architecture, and Code Analysis

Caffeine is a high‑performance, low‑memory local cache for Java that improves upon Guava Cache by adopting a sophisticated W‑TinyLFU eviction strategy, asynchronous read/write buffers, and a hierarchical timer wheel for flexible expiration.

Comparison with Guava Cache – Caffeine retains the familiar Guava API (Cache, LoadingCache, CacheBuilder) while offering significantly better hit rates and throughput, which is why Spring 5 switched its default local cache to Caffeine.

Basic Usage – Creating a cache is straightforward:

private static LoadingCache
cache = Caffeine.newBuilder()
    .maximumSize(256L)
    .initialCapacity(1)
    .expireAfterAccess(2, TimeUnit.DAYS)
    .expireAfterWrite(2, TimeUnit.HOURS)
    .refreshAfterWrite(1, TimeUnit.HOURS)
    .recordStats()
    .writer(new CacheWriter
() {
        @Override public void write(@NonNull Object key, @NonNull Object value) {
            log.info("key={}, CacheWriter write", key);
        }
        @Override public void delete(@NonNull Object key, @Nullable Object value, @NonNull RemovalCause cause) {
            log.info("key={}, cause={}, CacheWriter delete", key, cause);
        }
    })
    .build(new CacheLoader
() {
        @Override public String load(@NonNull String key) throws Exception {
            return "value_" + key;
        }
        @Override public String reload(@NonNull String key, @NonNull String oldValue) throws Exception {
            return "value_" + key;
        }
    });

W‑TinyLFU Core Design – The algorithm combines a small Window cache (admission space) with a main cache split into protected and probation segments using a Segmented LRU (SLRU). Frequency is tracked by a compact FrequencySketch based on a Count‑Min Sketch stored in a single 64‑bit word, limiting each counter to 15 and halving all counters periodically to age old entries.

public void increment(@NonNull E e) {
    if (isNotInitialized()) return;
    int hash = spread(e.hashCode());
    int start = (hash & 3) << 2;
    int index0 = indexOf(hash, 0);
    int index1 = indexOf(hash, 1);
    int index2 = indexOf(hash, 2);
    int index3 = indexOf(hash, 3);
    boolean added = incrementAt(index0, start);
    added |= incrementAt(index1, start + 1);
    added |= incrementAt(index2, start + 2);
    added |= incrementAt(index3, start + 3);
    if (added && (++size == sampleSize)) {
        reset();
    }
}

The evictEntries method decides whether to keep a candidate from the window or evict the victim from the main space based on their frequencies, with a small random tie‑breaker to mitigate hash‑collision attacks.

boolean admit(K candidateKey, K victimKey) {
    int victimFreq = frequencySketch().frequency(victimKey);
    int candidateFreq = frequencySketch().frequency(candidateKey);
    if (candidateFreq > victimFreq) return true;
    if (candidateFreq <= 5) return false;
    int random = ThreadLocalRandom.current().nextInt();
    return ((random & 127) == 0);
}

Adaptive Window Size – The climb routine monitors hit‑rate changes and dynamically adjusts the window proportion (default 1 % of total capacity) to optimise for workloads with bursty or steady access patterns.

Asynchronous Read/Write Buffers – Caffeine uses a striped, non‑blocking BoundedBuffer (read buffer) and an MPSC MpscGrowableArrayQueue (write buffer) to batch maintenance work such as statistics updates, expiration, and eviction, reducing lock contention on hot keys.

Timer Wheel Expiration – When custom per‑key expiration is required via .expireAfter(Expiry) , Caffeine employs a hierarchical timer wheel to place entries into buckets based on their absolute expiration time, avoiding costly sorted structures.

Additional optimisations include soft/weak references, false‑sharing elimination, and optional CompletableFuture ‑based asynchronous loading.

Overall, Caffeine combines modern caching theory (W‑TinyLFU, Count‑Min Sketch, adaptive window sizing) with practical engineering (striped buffers, timer wheel) to deliver near‑optimal hit rates with minimal memory overhead.