Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build a Readers–Writer Lock

Build a Readers–Writer Lock

Readers–writer locking sits behind almost every read-heavy service you will ever build — a feature-flag cache, a routing table, an in-memory index, a config store — anywhere reads outnumber writes 100:1 or more. You already know the vocabulary: “let readers run concurrently, give a writer exclusive access.” This project makes you build the primitive yourself, in Go and Java, hand-rolled from a mutex and a condition variable — not by wrapping Java’s ReentrantReadWriteLock or Go’s sync.RWMutex. That is deliberate: the interview question is never “can you call the library,” it is “do you understand what the library is doing for you, and where it can still bite you.” You will ship two versions of the same lock, and the second one exists only because the first has a bug that will actually deadlock your on-call rotation.

1. The Trap

Failure mode 1 — the plain mutex collapses throughput. Start with the obvious thing: guard the shared state with one mutex, full stop. Say you are building a feature-flag cache read by every request — 50,000 reads/sec, one write every 30 seconds when someone flips a flag. A single mutex means every one of those 50,000 reads/sec serializes behind every other read, even though none of them mutate anything and none of them conflict with each other. Two reads can never run at the same time even on a 64-core box. You have turned a purely parallel workload into a queue: p99 read latency balloons under load for a resource that had no reason to contend in the first place.

Failure mode 2 — the naive fix starves the writer, permanently. So you fix it the obvious way: track a reader count, let any number of readers hold the lock at once, and only make a writer wait until the count hits zero. This is the classic “first readers–writers” solution, and it has a nasty property: if readers arrive continuously and their windows overlap — reader #2 grabs the lock before reader #1 releases — the count can stay above zero indefinitely. The writer is queued behind “wait for zero active readers,” and if that moment never arrives, the writer waits forever. Not slow — forever. A background compaction job, a config reload, a cache invalidation — anything that has to write can starve permanently behind a read-heavy service that never goes quiet. You will reproduce this exact failure in Movement 5, with real measured numbers: a continuous stream of readers for a full observation window, and the writer never gets in even once.

2. Scope it like a senior

Before writing a line of lock code, pin down the requirements — each answer changes the mechanism, not just the tuning:

For this build we scope it as: read-heavy, the writer must not starve, fairness only needs to be “bounded, not necessarily FIFO,” not reentrant, no upgrade in the core build (stretch in M4), single process (not distributed — that escalation is Movement 7).

3. Reason to the design

Step 1 — simplest thing that works. One mutex around the whole critical section. Correct, trivially. Zero read parallelism — this is Failure mode 1 from the Trap.

Step 2 — let readers overlap. Track a readers count and a writerActive flag behind a monitor (mutex + condition variable). A reader waits only while a writer is active, then increments the count and proceeds; a writer waits until readers == 0 and no other writer is active, then takes exclusive access. Multiple readers now run concurrently — the throughput problem is fixed.

Step 3 — find the flaw by tracing it. The writer’s wait condition is “readers == 0.” Nothing in the reader’s acquire path checks whether a writer is waiting — only whether one is active. So: writer arrives, sees readers > 0, starts waiting. Reader A releases, count drops toward zero, broadcasts. But before the writer's goroutine/thread gets scheduled and re-checks the condition, Reader B has already come in and incremented the count back up. The writer's loop re-checks readers > 0, it's still true, back to waiting. Repeat this with a continuous stream of readers and the writer can lose that race indefinitely — not because of bad luck once, but structurally, every single time.

Step 4 — derive the fix: a turnstile. The bug is that nothing stops new readers from joining once a writer is waiting. The fix is a second flag — call it writersWaiting — that a writer raises the instant it arrives, before it starts waiting for the readers to drain. Readers now check that flag too: once it's raised, no new reader may enter. Readers already inside keep running to completion (nobody is evicted), the count monotonically drains, and the writer is guaranteed to proceed within one “reader drain” — bounded by however long the currently in-flight readers take, never longer, no matter how many more readers show up after. This is the classic turnstile pattern (the same core idea used to solve the dining philosophers and to build writer-preferring locks in general): a gate that stops new arrivals without disturbing anyone already through it.

Note the trade-off you just made, explicitly: readers that arrive while a writer is waiting now block too, even though in principle they could still run concurrently with the readers already inside. You have traded a slice of read throughput/burst-absorption for a hard bound on writer wait. That trade-off is the spine of Movement 6.

4. Build it — milestones

Build a lock with this contract, growing it milestone by milestone. Attempt each milestone yourself before reading the reference implementation below — the reveal is positioned after the spec on purpose.

Reference implementation — M1, reader-preferring (Go)

This is the version with the bug left in on purpose — it is what most engineers ship on the first pass, and it compiles and passes every test that doesn’t specifically hammer the writer with continuous readers.

package main

import "sync"

type NaiveRWLock struct {
    mu           sync.Mutex
    cond         *sync.Cond
    readers      int
    writerActive bool
}

func NewNaiveRWLock() *NaiveRWLock {
    l := &NaiveRWLock{}
    l.cond = sync.NewCond(&l.mu)
    return l
}

// RLock is reader-preferring: it only checks whether a writer is ACTIVE,
// never whether one is WAITING. That is the whole bug.
func (l *NaiveRWLock) RLock() {
    l.mu.Lock()
    for l.writerActive { // BUG: ignores "is a writer waiting"
        l.cond.Wait()
    }
    l.readers++
    l.mu.Unlock()
}

func (l *NaiveRWLock) RUnlock() {
    l.mu.Lock()
    l.readers--
    if l.readers == 0 {
        l.cond.Broadcast()
    }
    l.mu.Unlock()
}

func (l *NaiveRWLock) Lock() {
    l.mu.Lock()
    for l.writerActive || l.readers > 0 { // waits for readers==0 -- may never happen
        l.cond.Wait()
    }
    l.writerActive = true
    l.mu.Unlock()
}

func (l *NaiveRWLock) Unlock() {
    l.mu.Lock()
    l.writerActive = false
    l.cond.Broadcast()
    l.mu.Unlock()
}

Reference implementation — M3, fair via turnstile (Go)

package main

import "sync"

// FairRWLock adds a turnstile: writersWaiting > 0 blocks NEW readers from
// entering. Readers already inside finish normally -- nobody is evicted --
// but once a writer shows up the reader stream is throttled to zero, so the
// writer is guaranteed in within one "reader drain."
type FairRWLock struct {
    mu             sync.Mutex
    cond           *sync.Cond
    readers        int
    writerActive   bool
    writersWaiting int // the turnstile
}

func NewFairRWLock() *FairRWLock {
    l := &FairRWLock{}
    l.cond = sync.NewCond(&l.mu)
    return l
}

func (l *FairRWLock) RLock() {
    l.mu.Lock()
    for l.writerActive || l.writersWaiting > 0 { // turnstile check
        l.cond.Wait()
    }
    l.readers++
    l.mu.Unlock()
}

func (l *FairRWLock) RUnlock() {
    l.mu.Lock()
    l.readers--
    if l.readers == 0 {
        l.cond.Broadcast()
    }
    l.mu.Unlock()
}

func (l *FairRWLock) Lock() {
    l.mu.Lock()
    l.writersWaiting++ // raise the turnstile the instant we arrive
    for l.writerActive || l.readers > 0 {
        l.cond.Wait()
    }
    l.writersWaiting--
    l.writerActive = true
    l.mu.Unlock()
}

func (l *FairRWLock) Unlock() {
    l.mu.Lock()
    l.writerActive = false
    l.cond.Broadcast() // wakes both waiting readers and the next writer
    l.mu.Unlock()
}

Reference implementation — M1 & M3 (Java)

Hand-rolled with ReentrantLock + Condition — the point of the exercise is to build the monitor yourself, not to reach for java.util.concurrent.locks.ReentrantReadWriteLock.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

final class NaiveRWLock {
    private final Lock mu = new ReentrantLock();
    private final Condition condition = mu.newCondition();
    private int readers = 0;
    private boolean writerActive = false;

    // readLock is reader-preferring: only checks writerActive, never
    // whether a writer is WAITING. That is the whole bug.
    void readLock() throws InterruptedException {
        mu.lock();
        try {
            while (writerActive) condition.await(); // BUG
            readers++;
        } finally { mu.unlock(); }
    }

    void readUnlock() {
        mu.lock();
        try {
            readers--;
            if (readers == 0) condition.signalAll();
        } finally { mu.unlock(); }
    }

    void writeLock() throws InterruptedException {
        mu.lock();
        try {
            while (writerActive || readers > 0) condition.await(); // may wait forever
            writerActive = true;
        } finally { mu.unlock(); }
    }

    void writeUnlock() {
        mu.lock();
        try {
            writerActive = false;
            condition.signalAll();
        } finally { mu.unlock(); }
    }
}
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

// Writer-preferring / fair via a turnstile: writersWaiting > 0 blocks
// NEW readers. Existing readers finish normally; the writer is guaranteed
// in within one reader drain once it raises the turnstile.
final class FairRWLock {
    private final Lock mu = new ReentrantLock();
    private final Condition condition = mu.newCondition();
    private int readers = 0;
    private boolean writerActive = false;
    private int writersWaiting = 0; // the turnstile

    void readLock() throws InterruptedException {
        mu.lock();
        try {
            while (writerActive || writersWaiting > 0) condition.await();
            readers++;
        } finally { mu.unlock(); }
    }

    void readUnlock() {
        mu.lock();
        try {
            readers--;
            if (readers == 0) condition.signalAll();
        } finally { mu.unlock(); }
    }

    void writeLock() throws InterruptedException {
        mu.lock();
        try {
            writersWaiting++; // raise the turnstile the instant we arrive
            while (writerActive || readers > 0) condition.await();
            writersWaiting--;
            writerActive = true;
        } finally { mu.unlock(); }
    }

    void writeUnlock() {
        mu.lock();
        try {
            writerActive = false;
            condition.signalAll(); // wakes readers and the next writer
        } finally { mu.unlock(); }
    }
}

5. Break it — the starvation test

The harness (reusing the exact NaiveRWLock/FairRWLock types from Movement 4): spin up ~24–32 reader goroutines/threads, each looping “acquire read lock, hold briefly, release, tiny random gap, repeat” with jittered timings so the readers do not stay in lock-step (an unjittered stream lets every reader drain out at the same instant and hands the naive lock an easy, unrealistic opening). While that stream runs continuously, one writer tries to acquire the exclusive lock once, and you measure how long it takes — capped at an observation window.

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

// hammerReaders keeps a continuous, JITTERED, overlapping stream of readers
// flowing so the reader count almost never touches zero. (An unjittered
// stream lets every reader drain out in lock-step and hands the naive lock
// an easy opening -- that would understate the real bug.)
func hammerReaders(stop <-chan struct{}, n int, rlock, runlock func(), wg *sync.WaitGroup) {
    for i := 0; i < n; i++ {
        wg.Add(1)
        go func(seed int64) {
            defer wg.Done()
            r := rand.New(rand.NewSource(seed))
            for {
                select {
                case <-stop:
                    return
                default:
                }
                rlock()
                time.Sleep(time.Duration(300+r.Intn(400)) * time.Microsecond)
                runlock()
                time.Sleep(time.Duration(r.Intn(150)) * time.Microsecond)
            }
        }(int64(i)*7919 + 17)
    }
}

func runTrial(name string, rlock, runlock func(), wlock, wunlock func()) {
    const readerCount = 24
    const observe = 1500 * time.Millisecond

    stop := make(chan struct{})
    var wg sync.WaitGroup
    hammerReaders(stop, readerCount, rlock, runlock, &wg)
    time.Sleep(20 * time.Millisecond) // let readers ramp up and overlap

    acquired := make(chan time.Duration, 1)
    start := time.Now()
    go func() {
        wlock()
        acquired <- time.Since(start)
        wunlock()
    }()

    select {
    case d := <-acquired:
        fmt.Printf("%-28s writer acquired after %v\n", name, d)
    case <-time.After(observe):
        fmt.Printf("%-28s writer STARVED -- did not acquire within %v\n", name, observe)
    }
    close(stop)
    wg.Wait()
}

func main() {
    naive := NewNaiveRWLock()
    runTrial("naive (reader-preferring):", naive.RLock, naive.RUnlock, naive.Lock, naive.Unlock)

    fair := NewFairRWLock()
    runTrial("fair (turnstile):", fair.RLock, fair.RUnlock, fair.Lock, fair.Unlock)
}

Measured, not hypothetical (this exact harness, compiled and run with go vet and go build -race clean, 5 consecutive trials):

naive (reader-preferring):  writer STARVED -- did not acquire within 1.5s   (every run)
fair (turnstile):           writer acquired after ~580–710μs              (every run)

The Java harness (below, using the exact NaiveRWLock/FairRWLock from Movement 4) reproduces the identical result — timings are millisecond-scale instead of microsecond-scale because the reader hold/gap times were deliberately widened to stay well above JVM sleep-granularity noise, not because the JVM behaves differently:

import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;

final class RWLockStarvationHarness {

static final int READER_COUNT = 32;
static final long OBSERVE_MS = 2000;

interface RLock  { void lock() throws InterruptedException; }
interface RUnlock { void unlock(); }
interface WLock  { void lock() throws InterruptedException; }
interface WUnlock { void unlock(); }

static Thread[] hammerReaders(AtomicBoolean stop, RLock rlock, RUnlock runlock) {
    Thread[] threads = new Thread[READER_COUNT];
    for (int i = 0; i < READER_COUNT; i++) {
        final long seed = i * 7919L + 17L;
        threads[i] = new Thread(() -> {
            Random r = new Random(seed);
            while (!stop.get()) {
                try {
                    rlock.lock();
                    Thread.sleep(2 + r.nextInt(3)); // 2-4ms hold (ms-scale: reliable across JVMs)
                    runlock.unlock();
                    Thread.sleep(r.nextInt(2)); // 0-1ms gap
                } catch (InterruptedException e) {
                    return;
                }
            }
        });
        threads[i].start();
    }
    return threads;
}

static void runTrial(String name, RLock rlock, RUnlock runlock,
                      WLock wlock, WUnlock wunlock) throws InterruptedException {
    AtomicBoolean stop = new AtomicBoolean(false);
    Thread[] readers = hammerReaders(stop, rlock, runlock);
    Thread.sleep(20); // let readers ramp up and overlap continuously

    CountDownLatch done = new CountDownLatch(1);
    long[] acquiredAtNanos = new long[1];
    long start = System.nanoTime();
    Thread writer = new Thread(() -> {
        try {
            wlock.lock();
            acquiredAtNanos[0] = System.nanoTime();
            done.countDown();
            wunlock.unlock();
        } catch (InterruptedException e) { /* starved -- treated as non-acquisition below */ }
    });
    writer.start();

    boolean acquired = done.await(OBSERVE_MS, TimeUnit.MILLISECONDS);
    if (acquired) {
        double ms = (acquiredAtNanos[0] - start) / 1_000_000.0;
        System.out.printf("%-28s writer acquired after %.3f ms%n", name, ms);
    } else {
        System.out.printf("%-28s writer STARVED - did not acquire within %d ms%n", name, OBSERVE_MS);
        writer.interrupt();
    }
    stop.set(true);
    for (Thread t : readers) t.join();
}

public static void main(String[] args) throws InterruptedException {
    NaiveRWLock naive = new NaiveRWLock();
    runTrial("naive (reader-preferring):", naive::readLock, naive::readUnlock, naive::writeLock, naive::writeUnlock);

    FairRWLock fair = new FairRWLock();
    runTrial("fair (turnstile):", fair::readLock, fair::readUnlock, fair::writeLock, fair::writeUnlock);
}
}
naive (reader-preferring):  writer STARVED - did not acquire within 2000 ms   (5/5 runs)
fair (turnstile):           writer acquired after ~5.3–8.9 ms                (5/5 runs)

The lesson, made concrete: comment out the writersWaiting > 0 check in readLock/RLock (i.e. paste the M1 body back in) and re-run — you will reproduce the STARVED line on the fair lock too. That one removed condition is the entire difference between a lock that is correct-but-unfair and one that is correct-and-bounded. Also worth running once: go build -race / a longer JVM stress loop on both versions — there is no data race in either; the bug is a liveness bug (the wrong thing eventually happens, or never happens), not a safety bug (two things happen that should never happen together). That distinction — safety vs. liveness — is worth having crisp for the drilling round.

6. Optimise — with trade-offs

You just hand-built a writer-preferring RW lock. Before you ship it, know exactly what it costs relative to the library primitives and the lock-free alternatives — and know when the honest answer is “use a plain mutex.”

MechanismRead concurrencyWriter starvation riskComplexityBest when
Plain mutexNone — all serializedNone (FIFO-ish by default)TrivialLow contention, or the critical section is a handful of instructions — RW bookkeeping overhead can exceed the benefit
Our hand-rolled turnstile RW lockFull, until a writer arrivesBounded to one reader-drainModerate (1 mutex, 1 cond, 3 ints)You need the exact bound and want to own the code (interview, or a primitive nothing in your stack provides)
Go sync.RWMutexFull, until a writer arrivesAlready writer-preferring — a pending Lock() blocks new RLock()sZero — it's in the stdlibDefault choice in Go; you rarely need to hand-roll this in production, only to understand it
Java ReentrantReadWriteLockFull, until a writer arrivesNonfair (default) mode allows barging and does not bound writer wait; fair mode uses arrival-order queuing at a throughput costZero to use, supports reentrancy and write->read downgrade (not upgrade)Default choice in Java when you need reentrancy or downgrade; pick fair mode explicitly if starvation is unacceptable
StampedLock optimistic readReaders never block at allN/A — readers don't wait, they validate-and-possibly-retryHigher — no reentrancy, manual validate() disciplineRead-dominated, cheap-to-redo read section, simple/copyable data (e.g. reading two fields of a point)
Copy-on-write (e.g. CopyOnWriteArrayList)Wait-free — readers iterate a stable snapshot arrayN/A — writers pay, not readersLow to use, O(n) copy per writeRead-extremely-heavy, write-extremely-rare, small collections (listener lists, routing tables that change rarely)
RCU (Read-Copy-Update)Wait-free, no lock at all on the read sideN/A — writers copy, mutate, atomically swap a pointer, then wait a “grace period” before reclaiming the old versionHigh — needs a reclamation/epoch schemeExtremely read-hot, latency-critical paths (kernel routing tables); you can tolerate readers briefly seeing a stale version

When a plain mutex is actually the right call: if the critical section is a few instructions and reads don’t dominate writes by at least ~10:1, the reader-count bookkeeping in a RW lock (an atomic increment/decrement on every single read, contended across all readers on one cache line) can cost more than the serialization it was meant to avoid. This is exactly why the JDK docs warn that ReentrantReadWriteLock and StampedLock are not automatically wins over synchronized for short, low-contention sections — measure before reaching for the fancier primitive.

7. Defend under drilling

“Reader-preference vs. writer-preference — what's the actual trade-off?” Reader-preference (M1) maximizes read throughput and burst absorption but has no bound on writer wait — it can starve. Writer-preference (M3, the turnstile) bounds writer wait to one reader-drain, at the cost of blocking any reader that arrives after a writer is already waiting, even though it could theoretically run concurrently with in-flight readers. A strict FIFO/ticket-based lock adds true arrival-order fairness on top of that, at the cost of more bookkeeping and lower peak read throughput. Pick based on whether writer latency is user-facing (Movement 2).

“Why can upgrading a read lock to a write lock deadlock?” Say two threads, T1 and T2, each hold the read lock and each want to upgrade to the write lock. Upgrading means “become the writer without releasing my read lock first” (releasing first defeats the purpose — another writer could sneak in between release and re-acquire). So T1 waits for every other reader — including T2 — to release before it can become exclusive; T2 is doing the exact same wait on T1. Neither will release while waiting to upgrade. That is a circular wait over a shared resource — a deadlock, structurally identical to the classic two-thread lock-ordering deadlock, just with two “kinds” of the same lock instead of two different locks. Two real fixes: (a) allow only one upgrade attempt in flight at a time via a distinct “update lock” that is not itself shared among ordinary readers (PostgreSQL uses exactly this pattern); or (b) don’t upgrade — release the read lock and re-acquire the write lock, and explicitly re-validate your invariants afterward, since state may have changed in the gap (the same check-then-act hazard as any non-atomic compound operation).

“When is StampedLock’s optimistic read actually worth it?” When reads vastly outnumber writes, the read section is small and cheap to redo, and the data is simple enough that validate() is nearly free — the textbook example is reading two fields of an immutable-ish point and computing a distance: copy both fields, then validate; on failure, fall back to a real read lock. It is not worth it when the read section does expensive or side-effecting work you cannot cheaply redo, or when you need reentrancy or Condition support, both of which StampedLock lacks.

“How does this relate to MVCC or RCU?” Same idea, different layer: stop blocking readers at all by giving them a consistent-enough view while a writer works separately, then swap. In a database, MVCC gives each reader a snapshot version of a row taken at transaction start while a writer creates a new version rather than mutating in place; old versions are reclaimed once no active transaction can still see them. In the Linux kernel, RCU readers dereference a pointer with no lock whatsoever; a writer copies, mutates, and atomically swaps the pointer, then waits for a “grace period” — long enough for every reader that started before the swap to finish — before freeing the old copy. Our turnstile lock still blocks readers once a writer shows up; the MVCC/RCU move removes that block entirely, paying instead with extra memory (multiple live versions) and a reclamation problem (when is it safe to free the old version?).

“What breaks at 100× the load, across 100 app servers instead of one process?” The in-process turnstile is a pure memory operation — it does not care how many reads/sec hit it, only how many threads are actually inside your process. The failure mode that appears at scale is a different axis: if 100 app servers all need to coordinate on the same shared resource, an in-memory lock cannot help them at all — you need a distributed lock (a lease in etcd/ZooKeeper, or a Redis-based mutual exclusion scheme), and that reintroduces network partitions, lease expiry, and clock skew as entirely new failure modes this exercise never had to deal with. The more common escape hatch in practice is to avoid the distributed mutex altogether and push toward the MVCC/replicated-snapshot model from the question above — which is precisely why that pattern dominates at the database and distributed-systems layer.

8. You can now defend

Re-authored/Deepened for this guide. Related concept: Read-Write Locks — Concurrency.

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

Stuck on Build a Readers–Writer Lock? 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 Readers–Writer Lock** (Hands-On Builds) and want to truly understand it. Explain Build a Readers–Writer Lock 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 Readers–Writer Lock** 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 Readers–Writer Lock** 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 Readers–Writer Lock** 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 Bounded Producer–ConsumerBuild a Thread Pool →