The cache that computed everything twice

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

/**
 * Solution: the cache that computed everything twice.
 *
 * Two defects needing two different kinds of fix — which is the whole lesson.
 * ConcurrentHashMap gives you atomicity PER KEY. It cannot give you an
 * invariant over the map as a whole, and no combination of its methods will.
 *
 *   Defect 1 — containsKey then put. Each call is atomic, the pair is not, so
 *   every thread that passed the check called load(). Four thousand keys, more
 *   than thirteen thousand lookups. This defect is per-key, so a per-key
 *   atomic operation fixes it: computeIfAbsent performs the check and the
 *   insert inside the bin's lock.
 *
 *   Defect 2 — the capacity bound. "No more than N entries exist" is an
 *   invariant over the whole map. size() is only an estimate, and even an
 *   exact one would not help, because check-then-act lets any number of
 *   threads pass the check together. No per-key operation can express a
 *   whole-map invariant, so this needs one lock covering the check, the
 *   eviction and the insert together.
 *
 * That is why get() has two shapes below. Unbounded, computeIfAbsent is
 * enough and nothing blocks. Bounded, the write path is serialised — load()
 * runs one at a time — while reads stay lock-free on the fast path, which is
 * where the traffic is.
 *
 * A cache that needs both a bound and concurrent loads wants per-key locking
 * or a real cache library. See the stretch.
 */
public class Solution {

    static final int THREADS = 8;
    static final int KEYS = 4_000;
    static final int MAX_ENTRIES = 1_000;

    static class Cache {
        private final ConcurrentHashMap<Integer, String> entries = new ConcurrentHashMap<>();
        private final AtomicInteger lookups = new AtomicInteger();
        private final Object writeLock = new Object();
        private final int capacity;
        private final boolean bounded;

        Cache(int capacity, boolean bounded) {
            this.capacity = capacity;
            this.bounded = bounded;
        }

        private String load(int key) {
            lookups.incrementAndGet();
            return "row-" + key;
        }

        String get(int key) {
            if (!bounded) {
                // FIX 1: check and insert inside the bin's lock. Exactly one
                // load per key, and no lock on any other bin.
                return entries.computeIfAbsent(key, this::load);
            }

            // Fast path: no lock. null is unambiguous here, because a
            // ConcurrentHashMap cannot hold a null value.
            String hit = entries.get(key);
            if (hit != null) return hit;

            synchronized (writeLock) {
                // Re-check: another thread may have loaded it while we waited.
                String again = entries.get(key);
                if (again != null) return again;

                // FIX 2: evict BEFORE inserting, both inside the lock, so the
                // bound holds at every instant rather than on average.
                if (entries.size() >= capacity) {
                    Iterator<Integer> it = entries.keySet().iterator();
                    if (it.hasNext()) entries.remove(it.next());
                }

                String value = load(key);
                entries.put(key, value);
                return value;
            }
        }

        int size() {
            return entries.size();
        }

        int lookups() {
            return lookups.get();
        }
    }

    public static void main(String[] args) throws Exception {
        boolean ok = true;

        System.out.println("── phase 1: " + THREADS + " threads, " + KEYS
            + " keys, nothing evicted ──");
        Cache unbounded = new Cache(KEYS * 2, false);
        hammer(id -> {
            for (int k = 0; k < KEYS; k++) unbounded.get(k);
        });
        System.out.println("  distinct keys : " + KEYS);
        System.out.println("  lookups made  : " + unbounded.lookups());
        ok &= check("each key was loaded exactly once", unbounded.lookups() == KEYS);

        System.out.println();
        System.out.println("── phase 2: the same keys against a capacity of "
            + MAX_ENTRIES + " ──");
        Cache bounded = new Cache(MAX_ENTRIES, true);
        AtomicInteger peak = new AtomicInteger();
        hammer(id -> {
            for (int k = 0; k < KEYS; k++) {
                bounded.get(k);
                peak.accumulateAndGet(bounded.size(), Math::max);
            }
        });
        System.out.println("  capacity      : " + MAX_ENTRIES);
        System.out.println("  peak entries  : " + peak.get());
        ok &= check("the cache never exceeded its capacity", peak.get() <= MAX_ENTRIES);

        System.out.println();
        System.out.println(ok ? "PASS" : "FAIL");
    }

    static void hammer(java.util.function.IntConsumer body) throws Exception {
        Thread[] threads = new Thread[THREADS];
        CountDownLatch start = new CountDownLatch(1);
        for (int i = 0; i < THREADS; i++) {
            final int id = i;
            threads[i] = new Thread(() -> {
                try {
                    start.await();
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    return;
                }
                body.accept(id);
            });
            threads[i].start();
        }
        start.countDown();
        for (Thread t : threads) t.join();
    }

    static boolean check(String what, boolean passed) {
        System.out.println((passed ? "  ok    " : "  FAIL  ") + what);
        return passed;
    }
}