Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build a Concurrent LRU Cache

Build a Concurrent LRU Cache (+ a CAS Counter)

You already know how to build an LRU cache: hash map for O(1) lookup, doubly-linked list for O(1) move-to-front and evict-tail. That's the easy 80%. The interview — and the production incident — lives in the other 20%: an LRU cache is almost always shared by many threads, and its signature move, "touching an entry makes it most-recently-used," is a write to the recency list even when the caller only asked to read a value. Get that one fact wrong and your "thread-safe" cache serializes every reader in your fleet behind a single lock, and your throughput graph goes flat no matter how many cores you throw at it. This lab builds a coarse-lock LRU, breaks it under read-heavy load, then fixes it two different ways — sharding and a lock-free CLOCK/second-chance design — in both Java and Go, plus a hand-rolled CAS counter as the atomic-primitives companion piece. See also: Caching — LRU Lock Contention & Redis Ops for the production/Redis-scale version of exactly this problem, and Build an LRU + TTL Cache if you haven't built the single-threaded version yet — do that one first if the O(1) mechanics themselves are new.

1. The trap

Say you ship an in-process LRU cache for a hot, read-heavy lookup — feature flags, a routing table, a small config blob — read by 8+ threads per instance, written rarely. You do the responsible thing: wrap the whole cache in one lock so it's provably thread-safe. Code review approves it. Then someone benchmarks it under load:

threads=1   ~32,000,000 gets/sec
threads=2   ~12,000,000 gets/sec   <- adding a thread made it WORSE
threads=4   ~ 9,000,000 gets/sec
threads=8   ~ 9,800,000 gets/sec   <- flat. 8x the threads, ~0.3x the per-thread throughput.

(Real numbers from Movement 5's benchmark, not illustrative — you'll reproduce them yourself.) This is not a GC pause, not a bad benchmark, not "Java is slow." It's structural: a coarse lock around an LRU cache makes every get() take the exact same exclusive lock as every put(), because get() silently mutates the recency list (move-to-front). You didn't write a read-write lock by mistake — you wrote a cache where there is no such thing as a pure read. Adding reader threads doesn't add parallelism, it adds a longer line at the same door. This lab is about seeing that door, and then removing it.

2. Scope it like a senior

Before touching a lock, pin down what you're actually building. A candidate who reaches for synchronized immediately is the one who solves the wrong problem correctly. Ask:

Answering these first is what separates "I locked it" from "I understood what needed protecting, and chose the cheapest correct mechanism for this workload."

3. Reason to the design

Attempt 0 — exact LRU, single-threaded. HashMap for O(1) key→node lookup, doubly-linked list for O(1) move-to-front and evict-tail. get(k) looks up the node and splices it to the front; put(k,v) inserts at the front and evicts the tail if over capacity. Correct, fast, and shares zero state safely with anyone — because there's only one thread. This is M1 below.

Attempt 1 — wrap it in one lock (the coarse lock). The obvious next step: put a ReentrantLock/Mutex around the whole cache, take it in both get() and put(). This is correct — no data race, no corrupted list. But look at what you actually locked: get() calls unlink() + pushFront() just like put() does. There is no read-only code path through this cache. So the lock isn't "protecting writes from reads" — every caller, reader or writer, takes the SAME exclusive lock, and they all queue behind each other. This is Movement 1's trap, named precisely: the eviction policy's own bookkeeping turns every read into a write.

Attempt 2 — shard the lock, not the data structure's ordering. If one lock over N keys is the bottleneck, cut it into K locks over N/K keys each: hash the key to a shard, take only that shard's lock. A get() on shard 3 no longer waits behind a put() on shard 7. You give something up: there is no longer one global recency order, only K independent local ones — "least recently used within this shard" instead of "least recently used, period." For a cache (not a strict FIFO/ordering primitive), that's usually a trade worth making, because the thing you actually care about — hit rate — barely moves when you go from one global LRU list to K local ones, as long as key traffic isn't wildly skewed to one shard. This is M3, and it's exactly what ConcurrentHashMap did internally in Java 7 (segment locking) before Java 8 moved to finer-grained bucket locking.

Attempt 3 — stop mutating on read, period. Sharding reduces contention but doesn't remove the root cause: reads still take a lock. The more radical fix asks: what's the minimum information a read needs to leave behind to make eviction reasonable, without touching a shared list? Answer: one bit per entry, "was this used recently?" — set with a single atomic store, no lock, no list surgery, no serialization between readers. Eviction is done lazily by a "clock hand" that sweeps entries: bit set → clear it and give the entry a second chance (it was used since the hand last passed, so don't evict yet); bit clear → evict it (it's been a full sweep since anyone touched it, that's the closest you can get to "least recently used" without an actual list). This is CLOCK / second-chance — the same mechanism behind Linux page replacement (`CLOCK-Pro`), and the eviction core of production caches like Caffeine. It is approximately LRU (a full sweep, not perfect recency order), and that inaccuracy is the price of removing every reader-side lock. This is M4, and it is the answer to "how do I make reads truly not block."

The CAS-counter tie-in. Both the sharded lock (implicitly) and the CLOCK cache (explicitly, for the reference bit) lean on one primitive: compare-and-swap — "update this memory location to next only if it still equals expected; otherwise tell me, so I can retry." That's the same mechanism that makes a lock-free counter possible, which is why this lab includes one: a CasCounter built from a hand-rolled CAS retry loop, next to a deliberately BrokenCounter that uses a plain count++ and reliably loses updates. See also Atomics & Compare-And-Swap (CAS) and CAS & the ABA Problem for the underlying theory this lab exercises.

4. Build it — milestones

Attempt each milestone yourself before reading the reference implementation — the reveal is positioned after the tests on purpose.

Reference implementation — Java

M1 — exact LRU (not yet thread-safe):

import java.util.HashMap;
import java.util.Map;

/** M1: exact single-threaded LRU. HashMap for O(1) lookup + a doubly linked
 *  list for O(1) move-to-front / evict-tail. NOT thread-safe on its own --
 *  every get() mutates the list (move-to-front), which is the whole trap. */
public final class LRUCache<K, V> {
    private static final class Node<K, V> {
        K key; V value; Node<K, V> prev, next;
        Node(K k, V v) { key = k; value = v; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<K, Node<K, V>>();
    private final Node<K, V> head = new Node<K, V>(null, null); // MRU sentinel side
    private final Node<K, V> tail = new Node<K, V>(null, null); // LRU sentinel side

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    /** Returns the value, or null on miss. MUTATES the list: moves the node
     *  to the front. This single fact is Movement 1's trap. */
    public V get(K key) {
        Node<K, V> n = map.get(key);
        if (n == null) return null;
        unlink(n);
        pushFront(n);
        return n.value;
    }

    public void put(K key, V value) {
        Node<K, V> n = map.get(key);
        if (n != null) {
            n.value = value;
            unlink(n);
            pushFront(n);
            return;
        }
        if (map.size() == capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
        }
        Node<K, V> fresh = new Node<K, V>(key, value);
        map.put(key, fresh);
        pushFront(fresh);
    }

    public int size() { return map.size(); }

    private void unlink(Node<K, V> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void pushFront(Node<K, V> n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
}

M2 — coarse lock:

import java.util.concurrent.locks.ReentrantLock;

/** M2: baseline thread-safety. ONE lock guards the whole cache -- correct,
 *  but every get() takes the SAME exclusive lock as put(), because get()
 *  mutates the recency list. Reads serialize behind writes AND behind each
 *  other. This is the "coarse lock" row in the trade-off table. */
public final class CoarseLockLRUCache<K, V> {
    private final LRUCache<K, V> inner;
    private final ReentrantLock lock = new ReentrantLock();

    public CoarseLockLRUCache(int capacity) {
        inner = new LRUCache<K, V>(capacity);
    }

    public V get(K key) {
        lock.lock();
        try {
            return inner.get(key);
        } finally {
            lock.unlock();
        }
    }

    public void put(K key, V value) {
        lock.lock();
        try {
            inner.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        lock.lock();
        try { return inner.size(); } finally { lock.unlock(); }
    }
}

M3 — sharded / striped locks:

import java.util.concurrent.locks.ReentrantLock;

/** M3: sharded / striped locks. Partition the keyspace into N independent
 *  shards, each its own small LRUCache + its own lock. A get() on shard 3
 *  no longer blocks a get() on shard 7 -- contention drops ~N x. The price:
 *  there is no longer ONE global recency order, only N local ones, so
 *  eviction is "least recently used within this shard," not globally. For
 *  a cache (not a strict ordering structure) that trade is usually free. */
public final class StripedLRUCache<K, V> {
    private final LRUCache<K, V>[] shards;
    private final ReentrantLock[] locks;
    private final int shardCount;

    @SuppressWarnings("unchecked")
    public StripedLRUCache(int totalCapacity, int shardCount) {
        this.shardCount = shardCount;
        shards = new LRUCache[shardCount];
        locks = new ReentrantLock[shardCount];
        int perShard = Math.max(1, totalCapacity / shardCount);
        for (int i = 0; i < shardCount; i++) {
            shards[i] = new LRUCache<K, V>(perShard);
            locks[i] = new ReentrantLock();
        }
    }

    private int shardFor(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);
        return Math.abs(h) % shardCount;
    }

    public V get(K key) {
        int s = shardFor(key);
        locks[s].lock();
        try {
            return shards[s].get(key);
        } finally {
            locks[s].unlock();
        }
    }

    public void put(K key, V value) {
        int s = shardFor(key);
        locks[s].lock();
        try {
            shards[s].put(key, value);
        } finally {
            locks[s].unlock();
        }
    }
}

M4 — CLOCK / second-chance, lock-free reads (fixed, after an adversarial verify pass caught a real visibility bug — see the code comment):

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicIntegerArray;
import java.util.concurrent.atomic.AtomicReferenceArray;
import java.util.concurrent.locks.ReentrantLock;

/** M4: approximate LRU via CLOCK / second-chance. Avoids the M1-M3 trap
 *  entirely by never mutating a list on a read. Every slot has one
 *  "referenced" bit; get() sets it (no lock, no list surgery -- readers
 *  never block each other or a writer). Eviction is done by a "clock hand"
 *  that sweeps slots: bit set -> CAS it back to 0 and give the slot a
 *  second chance; bit clear -> evict this slot. This is the mechanism
 *  behind Linux page replacement and many production caches (e.g.
 *  Caffeine's Window-TinyLFU admission + a clock-like eviction). */
public final class ClockCache<K, V> {
    private final int capacity;
    private final Object[] keys;
    // NOT a plain Object[] -- see the note on get()/put() below: a plain
    // array here has no happens-before edge to an unsynchronized reader,
    // which is a real, verified bug this design hit (Go's -race caught the
    // equivalent; Java's memory model makes the same access a silent
    // visibility bug instead of a detector hit -- arguably worse, since
    // nothing tells you). AtomicReferenceArray gives volatile-style
    // get/set per slot with no lock.
    private final AtomicReferenceArray<Object> values;
    private final AtomicBoolean[] referenced;
    private final ConcurrentHashMap<K, Integer> slotOf = new ConcurrentHashMap<K, Integer>();
    private final AtomicInteger clockHand = new AtomicInteger(0);
    // Only the (rare) eviction/insert path takes this lock; get() never does.
    private final ReentrantLock writeLock = new ReentrantLock();
    private final AtomicIntegerArray occupied; // 0 = empty, 1 = occupied

    public ClockCache(int capacity) {
        this.capacity = capacity;
        keys = new Object[capacity];
        values = new AtomicReferenceArray<Object>(capacity);
        referenced = new AtomicBoolean[capacity];
        for (int i = 0; i < capacity; i++) referenced[i] = new AtomicBoolean(false);
        occupied = new AtomicIntegerArray(capacity);
    }

    /** Lock-free read path: map lookup + a single "referenced" set + a
     *  volatile-semantics array get. No list mutation, so concurrent
     *  readers never contend with each other. */
    @SuppressWarnings("unchecked")
    public V get(K key) {
        Integer slot = slotOf.get(key);
        if (slot == null) return null;
        referenced[slot].set(true); // "I was used" -- give it a second chance later
        return (V) values.get(slot);
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            Integer existing = slotOf.get(key);
            if (existing != null) {
                values.set(existing, value);
                referenced[existing].set(true);
                return;
            }
            int slot = findSlotToUse();
            if (occupied.get(slot) == 1) {
                slotOf.remove(keys[slot]);
            }
            keys[slot] = key;
            values.set(slot, value);
            occupied.set(slot, 1);
            referenced[slot].set(true);
            slotOf.put(key, slot);
        } finally {
            writeLock.unlock();
        }
    }

    /** The clock sweep: advance the hand; a set bit gets one CAS'd-off
     *  second chance, a clear bit is the victim. compareAndSet is what
     *  makes "clear the bit" safe even though a concurrent get() might be
     *  racing to set it back to true at the same instant. */
    private int findSlotToUse() {
        for (int i = 0; i < capacity; i++) {
            if (occupied.get(i) == 0) return i;
        }
        while (true) {
            int hand = clockHand.getAndUpdate(new java.util.function.IntUnaryOperator() {
                public int applyAsInt(int operand) { return (operand + 1) % capacity; }
            });
            if (referenced[hand].compareAndSet(true, false)) {
                continue; // gave it a second chance, move on
            }
            return hand; // bit was already false -> evict this one
        }
    }

    public int size() { return slotOf.size(); }
}

The CAS counter (the mechanism behind M4's reference bit, isolated). Save as CasCounter.java:

import java.util.concurrent.atomic.AtomicLong;

/** The CAS-counter mini-lesson. increment() below is written out by hand as
 *  a compare-and-swap RETRY LOOP -- the same pattern AtomicLong.incrementAndGet
 *  uses internally -- so you can see the mechanism, not just call a library
 *  method. Contrast with BrokenCounter, which loses updates. */
public final class CasCounter {
    private final AtomicLong value = new AtomicLong(0);

    /** Hand-rolled CAS increment: read, compute, compareAndSet; on failure
     *  (another thread won the race), retry with a fresh read. No lock. */
    public long increment() {
        while (true) {
            long current = value.get();
            long next = current + 1;
            if (value.compareAndSet(current, next)) {
                return next;
            }
            // else: someone else updated `value` between get() and
            // compareAndSet() -- loop and try again with the new current.
        }
    }

    public long get() { return value.get(); }

    /** ABA note (not exercised by the counter, which is monotonic and thus
     *  ABA-immune): compareAndSet(expected, next) only checks that the VALUE
     *  is still `expected` -- if another thread changed it away and back to
     *  the same value in between (A -> B -> A), your CAS still "succeeds"
     *  even though the world moved. Harmless for a monotonically increasing
     *  counter, but a real bug for CAS-based stacks/free-lists, where a
     *  reused node pointer can look identical after a pop-push-pop cycle.
     *  Fix: pair the value with a version/stamp (AtomicStampedReference) so
     *  A-v1 -> B -> A-v2 is distinguishable from the original A-v1. */
}

The bug CasCounter fixes, for contrast. Save as BrokenCounter.java:

/** The bug CasCounter fixes: a plain long, incremented with `count++`.
 *  `++` is read-modify-write, NOT atomic -- two threads can both read the
 *  same value, both add 1, both write the same result back. One increment
 *  is lost, silently, no exception. */
public final class BrokenCounter {
    private long count = 0;
    public void increment() {
        count++; // BUG: read-modify-write, not atomic -- lost updates under contention
    }
    public long get() { return count; }
}

All four classes plus the two demo/benchmark mains compile clean under javac (JDK 8) with zero warnings.

Reference implementation — Go

M1 — exact LRU (container/list + a map, generic):

// Package lrucache builds a concurrent LRU cache from scratch, in stages:
// M1 exact single-goroutine LRU -> M2 coarse-lock thread-safety -> M3
// sharded/striped locks -> M4 approximate CLOCK cache that never mutates
// on a read.
package lrucache

import "container/list"

type entry[K comparable, V any] struct {
	key   K
	value V
}

// LRUCache is M1: exact LRU, map + doubly linked list, O(1) get/put.
// NOT goroutine-safe on its own -- every Get mutates the list (move to
// front), which is the whole trap this kata is about.
type LRUCache[K comparable, V any] struct {
	capacity int
	ll       *list.List
	items    map[K]*list.Element
}

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
	if capacity <= 0 {
		panic("capacity must be > 0")
	}
	return &LRUCache[K, V]{
		capacity: capacity,
		ll:       list.New(),
		items:    make(map[K]*list.Element, capacity),
	}
}

// Get mutates the list on every call (move-to-front) -- that mutation is
// exactly why a naive concurrent Get needs a WRITE lock.
func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	var zero V
	el, ok := c.items[key]
	if !ok {
		return zero, false
	}
	c.ll.MoveToFront(el)
	return el.Value.(*entry[K, V]).value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if el, ok := c.items[key]; ok {
		el.Value.(*entry[K, V]).value = value
		c.ll.MoveToFront(el)
		return
	}
	if len(c.items) >= c.capacity {
		back := c.ll.Back()
		if back != nil {
			c.ll.Remove(back)
			delete(c.items, back.Value.(*entry[K, V]).key)
		}
	}
	el := c.ll.PushFront(&entry[K, V]{key: key, value: value})
	c.items[key] = el
}

func (c *LRUCache[K, V]) Len() int { return len(c.items) }

M2 — coarse lock:

package lrucache

import "sync"

// CoarseLockLRUCache is M2: one Mutex around the whole cache. Correct, but
// Get takes the SAME exclusive lock as Put, because Get mutates the
// recency list. Reads serialize behind writes and behind each other.
type CoarseLockLRUCache[K comparable, V any] struct {
	mu    sync.Mutex
	inner *LRUCache[K, V]
}

func NewCoarseLockLRUCache[K comparable, V any](capacity int) *CoarseLockLRUCache[K, V] {
	return &CoarseLockLRUCache[K, V]{inner: NewLRUCache[K, V](capacity)}
}

func (c *CoarseLockLRUCache[K, V]) Get(key K) (V, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.inner.Get(key)
}

func (c *CoarseLockLRUCache[K, V]) Put(key K, value V) {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.inner.Put(key, value)
}

M3 — sharded / striped locks:

package lrucache

import (
	"hash/maphash"
	"sync"
)

// StripedLRUCache is M3: partition the keyspace into N shards, each its
// own small LRUCache + its own Mutex. A Get on shard 3 no longer blocks a
// Get on shard 7. Cost: no single global recency order, only N local ones.
type StripedLRUCache[K comparable, V any] struct {
	shards    []*stripeShard[K, V]
	shardMask uint64
	seed      maphash.Seed
	keyString func(K) string
}

type stripeShard[K comparable, V any] struct {
	mu    sync.Mutex
	cache *LRUCache[K, V]
}

// NewStripedLRUCache takes shardCount as a power of two and a keyString
// function to hash arbitrary comparable keys (Go generics can't hash an
// arbitrary K directly without reflection, so the caller supplies it --
// same trade every generic sharded cache in Go makes).
func NewStripedLRUCache[K comparable, V any](totalCapacity, shardCount int, keyString func(K) string) *StripedLRUCache[K, V] {
	perShard := totalCapacity / shardCount
	if perShard < 1 {
		perShard = 1
	}
	shards := make([]*stripeShard[K, V], shardCount)
	for i := range shards {
		shards[i] = &stripeShard[K, V]{cache: NewLRUCache[K, V](perShard)}
	}
	return &StripedLRUCache[K, V]{
		shards:    shards,
		shardMask: uint64(shardCount - 1),
		seed:      maphash.MakeSeed(),
		keyString: keyString,
	}
}

func (c *StripedLRUCache[K, V]) shardFor(key K) *stripeShard[K, V] {
	var h maphash.Hash
	h.SetSeed(c.seed)
	h.WriteString(c.keyString(key))
	return c.shards[h.Sum64()&c.shardMask]
}

func (c *StripedLRUCache[K, V]) Get(key K) (V, bool) {
	s := c.shardFor(key)
	s.mu.Lock()
	defer s.mu.Unlock()
	return s.cache.Get(key)
}

func (c *StripedLRUCache[K, V]) Put(key K, value V) {
	s := c.shardFor(key)
	s.mu.Lock()
	defer s.mu.Unlock()
	s.cache.Put(key, value)
}

M4 — CLOCK / second-chance, lock-free reads (fixed after go test -race caught a genuine data race — see Movement 5):

package lrucache

import (
	"sync"
	"sync/atomic"
)

// ClockCache is M4: approximate LRU via CLOCK / second-chance. Get never
// mutates a list -- it only flips a per-slot "referenced" bit with an
// atomic Store. The CAS is used by the clock hand during eviction to
// safely give a slot a second chance without a lock. This is the
// mechanism behind Linux page replacement and the eviction core of
// production caches like Caffeine.
type ClockCache[K comparable, V any] struct {
	capacity int

	// writeMu guards only Put/eviction -- Get never takes it.
	writeMu sync.Mutex
	slotOf  sync.Map // K -> int (slot index); safe for concurrent Get/Put

	keys       []K
	values     []atomic.Pointer[V] // NOT a plain []V -- see the note below
	referenced []atomic.Bool
	occupied   []atomic.Bool
	clockHand  atomic.Int32
}

func NewClockCache[K comparable, V any](capacity int) *ClockCache[K, V] {
	return &ClockCache[K, V]{
		capacity:   capacity,
		keys:       make([]K, capacity),
		values:     make([]atomic.Pointer[V], capacity),
		referenced: make([]atomic.Bool, capacity),
		occupied:   make([]atomic.Bool, capacity),
	}
}

// Get is the lock-free read path: sync.Map lookup + one atomic Store on
// the reference bit, then an atomic Load of the value pointer. No list
// surgery, so concurrent Gets never block each other or the (rare)
// writer.
//
// IMPORTANT (a real bug this design hit while being verified): the
// reference BIT isn't the only shared state -- the payload is too. A
// naive `values []V` plain slice races: Put on slot S can be replacing the
// value while a concurrent Get on the SAME slot S (a stale hit racing an
// eviction reusing that slot) reads it, and `go test -race` catches this
// exact race deterministically. Fix: store *V behind atomic.Pointer[V],
// so the swap itself is atomic and properly synchronized -- still no
// mutex on the read path, but no torn/racy read either.
func (c *ClockCache[K, V]) Get(key K) (V, bool) {
	var zero V
	v, ok := c.slotOf.Load(key)
	if !ok {
		return zero, false
	}
	slot := v.(int)
	c.referenced[slot].Store(true) // "I was used" -- second chance later
	p := c.values[slot].Load()
	if p == nil {
		return zero, false
	}
	return *p, true
}

func (c *ClockCache[K, V]) Put(key K, value V) {
	c.writeMu.Lock()
	defer c.writeMu.Unlock()

	if v, ok := c.slotOf.Load(key); ok {
		slot := v.(int)
		c.values[slot].Store(&value)
		c.referenced[slot].Store(true)
		return
	}

	slot := c.findSlotToUse()
	if c.occupied[slot].Load() {
		c.slotOf.Delete(c.keys[slot])
	}
	c.keys[slot] = key
	c.values[slot].Store(&value)
	c.occupied[slot].Store(true)
	c.referenced[slot].Store(true)
	c.slotOf.Store(key, slot)
}

// findSlotToUse is the clock sweep: advance the hand; a set reference bit
// gets one CAS'd-off second chance, a clear bit is the victim. The CAS is
// what makes "clear this bit" safe even while a concurrent Get on the same
// slot might be racing to set it back to true.
func (c *ClockCache[K, V]) findSlotToUse() int {
	for i := 0; i < c.capacity; i++ {
		if !c.occupied[i].Load() {
			return i
		}
	}
	for {
		hand := int(c.clockHand.Add(1)-1) % c.capacity
		if c.referenced[hand].CompareAndSwap(true, false) {
			continue // gave it a second chance, keep sweeping
		}
		return hand // bit was already false -> evict this slot
	}
}

The CAS counter:

package lrucache

import "sync/atomic"

// CasCounter: the CAS-counter mini-lesson. Increment is written out by
// hand as a compare-and-swap retry loop -- the same pattern
// atomic.Int64.Add uses internally under the hood on most platforms -- so
// the mechanism is visible, not hidden behind a library call.
type CasCounter struct {
	value atomic.Int64
}

func (c *CasCounter) Increment() int64 {
	for {
		current := c.value.Load()
		next := current + 1
		if c.value.CompareAndSwap(current, next) {
			return next
		}
		// else: value changed under us -- loop and retry.
	}
}

func (c *CasCounter) Get() int64 { return c.value.Load() }

// ABA note (not exercised by this monotonic counter, which is immune to
// ABA): CompareAndSwap(old, new) only checks the VALUE still equals old --
// if another goroutine moved it A -> B -> A in between, the CAS still
// "succeeds" even though the world changed underneath you. Harmless here;
// a real bug for CAS-based stacks/free-lists where a reused pointer can
// look identical after a pop-push-pop cycle. Fix: pair the value with a
// version/generation counter so A-gen1 -> B -> A-gen2 is distinguishable.

// BrokenCounter is the bug CasCounter fixes: a plain int64 incremented
// with count++. That is a non-atomic read-modify-write -- two goroutines
// can both read the same value, both add 1, both write the same result
// back, and one increment is silently lost. go build -race / go test
// -race will also flag this as a genuine data race.
type BrokenCounter struct {
	count int64
}

func (c *BrokenCounter) Increment() {
	c.count++ // BUG: read-modify-write, not atomic -- data race, lost updates
}

func (c *BrokenCounter) Get() int64 { return c.count }

The full module (lrucache package + two cmd/ demo binaries + a race-detecting test file) passes go build ./... and go vet ./... clean.

5. Break it — the tests that fail

Break-it test #1: reads serialize on the coarse lock. Pre-warm each cache design, then measure pure get() throughput at 1, 2, 4, and 8 concurrent threads/goroutines, no writes in the timed window — so the only variable is how many readers can proceed at once. Best-of-5 timed trials after a warmup pass, on an 11-core Apple Silicon laptop (JDK 8 / Go 1.25.5); run 3× independently to confirm the pattern, not just the absolute numbers, holds:

Java (LockContentionDemo, 65,536-entry cache, 64 shards):

COARSE  threads=1  ops/sec=32,322,274
COARSE  threads=2  ops/sec=12,002,208   <- more than 60% of throughput GONE the instant a 2nd reader shows up
COARSE  threads=4  ops/sec=9,077,172
COARSE  threads=8  ops/sec=9,803,953    <- flat: 8x the threads bought ~0x more throughput

STRIPED threads=1  ops/sec=9,955,424    <- slower solo (hashing + indirection overhead)
STRIPED threads=2  ops/sec=16,929,974   <- but it SCALES: beats coarse from 2 threads on
STRIPED threads=4  ops/sec=18,015,201
STRIPED threads=8  ops/sec=14,563,348

CLOCK   threads=1  ops/sec=38,872,755
CLOCK   threads=2  ops/sec=79,075,346   <- ~2x per added thread: this is what "readers never block" looks like
CLOCK   threads=4  ops/sec=146,777,771
CLOCK   threads=8  ops/sec=146,641,004  <- plateaus near the physical core count, not near "1 lock"

Go (cmd/lockcontention, same shape):

COARSE  goroutines=1  ops/sec=27,203,667
COARSE  goroutines=2  ops/sec=11,147,717
COARSE  goroutines=4  ops/sec=4,992,205   <- keeps getting WORSE with more goroutines, not just flat
COARSE  goroutines=8  ops/sec=3,820,397

STRIPED goroutines=1  ops/sec=10,270,850
STRIPED goroutines=2  ops/sec=15,356,437
STRIPED goroutines=4  ops/sec=19,261,799
STRIPED goroutines=8  ops/sec=19,719,929  <- scales roughly 2x from 1->8

CLOCK   goroutines=1  ops/sec=23,399,019
CLOCK   goroutines=2  ops/sec=51,601,251
CLOCK   goroutines=4  ops/sec=96,544,025
CLOCK   goroutines=8  ops/sec=101,213,348 <- ~4.3x from 1->8, the largest scaling of the three designs

The signature to internalize: COARSE doesn't scale, it degrades — every additional concurrent reader in Go actively made things worse (Mutex acquisition under contention costs more than the useless work it protects), and in Java it collapses once and then flatlines. That is what "reads serialize behind a write lock" looks like on a chart: throughput stops responding to added parallelism entirely, because there is fundamentally one door and everyone (reader or writer) queues at it. STRIPED and CLOCK both scale because they removed that single door — CLOCK the most, because it removed the reader-side lock entirely rather than just narrowing it.

Break-it test #2: lost updates without CAS. 8 threads/goroutines each increment a shared counter 200,000 times. Expected total = 1,600,000, exactly, every run. BrokenCounter (plain count++) vs CasCounter (compare-and-swap retry loop):

-- Java (CasCounterDemo) --
BROKEN  (count++)         expected=1,600,000  actual=842,640    lostUpdates=757,360
CAS     (compareAndSet)   expected=1,600,000  actual=1,600,000  lostUpdates=0

-- Go (cmd/cascounter) --
BROKEN  (count++)         expected=1,600,000  actual=475,919    lostUpdates=1,124,081
CAS     (CompareAndSwap)  expected=1,600,000  actual=1,600,000  lostUpdates=0

Nearly half to nearly three-quarters of the increments simply vanish — no exception, no corrupted memory, just a wrong number that looks plausible. That's the entire danger of a non-atomic read-modify-write under contention: it fails silently, not loudly. Go's race detector makes this concrete and undeniable rather than just "the number looks off":

$ go test -race -run TestBrokenCounter_LosesUpdates -v ./lrucache/...
==================
WARNING: DATA RACE
Write at 0x00c0000102c8 by goroutine 38:
  lrukata/lrucache.(*BrokenCounter).Increment()
      .../cascounter.go:48 +0xa0
Previous write at 0x00c0000102c8 by goroutine ...
==================
    lrucache_test.go:106: BUG REPRODUCED: want 320000, got 178021, lost 141979 updates
--- FAIL: TestBrokenCounter_LosesUpdates (0.01s)

And the correct designs are verified genuinely race-free under the same detector, not just "seems fine in testing":

$ go test -race -run 'RaceFree|ExactUnderContention' -v ./lrucache/...
--- PASS: TestCoarseLockLRUCache_RaceFree (0.12s)
--- PASS: TestStripedLRUCache_RaceFree (0.06s)
--- PASS: TestClockCache_RaceFree (0.15s)
--- PASS: TestCasCounter_ExactUnderContention (0.54s)
PASS

A finding worth naming honestly: the first version of ClockCache written for this lab did NOT pass TestClockCache_RaceFree — go test -race caught a genuine data race on the plain []V values slice (a concurrent Get and Put touching the same slot with no synchronization on the payload, only on the reference bit). The fix (shown above) was switching to atomic.Pointer[V] in Go and AtomicReferenceArray in Java. The lesson generalizes beyond this lab: removing the lock from a read path means EVERY piece of shared state that read touches needs its own synchronization story, not just the "obvious" one (here, the reference bit) — the payload counts too. This is exactly the kind of bug the adversarial-verify step (recompile, re-run, don't just eyeball it) exists to catch.

6. Optimise — with trade-offs

ApproachRead throughput under contentionEviction accuracyComplexityUse when
Exact LRU, coarse lock (this lab's M2)Worst — degrades or flatlines as readers increase; one lock for reads AND writesPerfect: true global LRU orderLowest — trivial to reason about, trivial to get wrong under loadLow-concurrency callers, or a cache that's genuinely write-heavy so contention is unavoidable anyway; correctness-critical exact ordering (rare)
Sharded / striped locks (M3)Good — scales roughly with shard count for uniform key traffic; degrades under key skew (hot shard)Approximate: LRU per-shard, not globallyModerate — more state, a hash function to get right, a shard-count tuning knobRead-heavy AND write-heavy mixed traffic, moderate concurrency (tens of threads), uniform-ish key distribution; the default upgrade from a coarse lock
Sampled / CLOCK (second-chance) (M4)Best for reads — genuinely lock-free reads, scales with coresApproximate: "not touched in a full sweep," not exact recencyHighest of the three — atomics per slot, a sweeping hand, and (as Movement 5 showed) the payload itself needs its own synchronization planRead-dominated hot paths (routing tables, feature flags, hot rows) where p99 latency matters more than perfectly exact LRU ordering
Go sync.Map (no manual eviction)Very good for read-mostly, append-mostly key sets (it's optimized for exactly that access pattern)None built in — no capacity bound or eviction policy at all; you'd have to add one yourselfLow to use, but it is NOT an LRU cache — it's an unbounded concurrent map that happens to be fast for skewed read/write patternsAn unbounded or externally-bounded map with disjoint keys per goroutine (e.g. a per-connection cache) — not a substitute for capacity-bounded LRU
Caffeine (Java) / Ristretto (Go) — production librariesExcellent — lock-free reads via a ring-buffer-batched approximate LFU/LRU hybrid (Window-TinyLFU)Very good in practice — admission + eviction tuned against real traces, usually beats naive LRU on hit rateYou don't write it, you configure it — but you lose the "I built and can defend this" depth this lab is forProduction code, basically always — hand-roll a cache for an interview or because you have a genuinely unusual access pattern the library doesn't fit, not because "how hard can it be"

The real judgment call: a coarse lock is the right DEFAULT to start with — it's the easiest to prove correct, and premature striping/CLOCK-ification is wasted complexity if your actual read concurrency is low. Reach for sharding when you've measured contention on a shared lock and the workload has decent key spread. Reach for CLOCK/second-chance (or just adopt Caffeine/Ristretto) only once you've established that reads genuinely dominate and even sharded lock overhead shows up in a profile — the accuracy you give up (approximate vs. exact recency) is real, and you should be able to say, out loud, why your hit rate doesn't actually suffer for it.

7. Defend under drilling

8. You can now defend

Re-authored/Deepened for this guide. Reference code compiled and executed before publishing: Java (javac/java, JDK 8) and Go (go build ./..., go vet ./..., go test -race ./...) both clean; the lock-contention benchmark and the lost-update/CAS-counter demo reproduce the stated numbers on repeated runs; an initial data race in the Go ClockCache was caught by go test -race during verification and fixed (documented in Movement 5) before publishing. See also: Caching — LRU Lock Contention & Redis Ops, Atomics & Compare-And-Swap (CAS), CAS & the ABA Problem, and Build an LRU + TTL Cache.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build a Concurrent LRU Cache? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build a Concurrent LRU Cache** (Hands-On Builds) and want to truly understand it. Explain Build a Concurrent LRU Cache from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build a Concurrent LRU Cache** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build a Concurrent LRU Cache** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build a Concurrent LRU Cache** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Build a Blocking QueueBuild a Semaphore from Scratch →