Read-write locks

01The intuition

The problem it solves

A school notice board is read by a thousand students a minute and updated by one teacher a few times a day. The first thread-safe version puts one lock around everything, so a student reading a notice blocks every other student, even though none of them changes anything.

import threading

class NoticeBoard:
    def __init__(self) -> None:
        self.notices: dict[str, str] = {}
        self.lock = threading.Lock()

    def read(self, key: str) -> str:
        with self.lock:                 # readers wait for other readers
            return self.notices.get(key, "")

    def post(self, key: str, text: str) -> None:
        with self.lock:
            self.notices[key] = text

Reads are harmless to each other; only a write needs to be alone. With 1,000 reads a minute of 1 ms each, serialising them wastes nothing yet; with 100,000 reads a second of 50 μs each, a single lock caps the board at 20,000 reads a second on any number of cores. The lock is stricter than the data needs.

Build it one piece at a time

Step one: state the rule you actually need. Any number of readers may be inside at once; a writer must be inside alone. That is a read-write lock. Python's standard library does not ship one, so build it from a lock and a condition variable, which is itself a good interview exercise.

class RWLock:
    def __init__(self) -> None:
        self._cond = threading.Condition()
        self._readers = 0
        self._writer = False

    def acquire_read(self) -> None:
        with self._cond:
            while self._writer:
                self._cond.wait()
            self._readers += 1

    def release_read(self) -> None:
        with self._cond:
            self._readers -= 1
            if self._readers == 0:
                self._cond.notify_all()

Step two: the writer side waits until there is no writer and no reader, then marks itself in. Releasing wakes everyone so that waiting readers and writers can re-check.

class RWLock(RWLock):   # continued
    def acquire_write(self) -> None:
        with self._cond:
            while self._writer or self._readers > 0:
                self._cond.wait()
            self._writer = True

    def release_write(self) -> None:
        with self._cond:
            self._writer = False
            self._cond.notify_all()

Step three: a steady stream of readers can keep _readers above zero forever, and the writer starves. Fix it by counting waiting writers and making new readers wait while any writer is waiting. The board then uses the lock with the natural methods.

class FairRWLock(RWLock):
    def __init__(self) -> None:
        super().__init__()
        self._waiting_writers = 0

    def acquire_read(self) -> None:
        with self._cond:
            while self._writer or self._waiting_writers > 0:
                self._cond.wait()
            self._readers += 1

    def acquire_write(self) -> None:
        with self._cond:
            self._waiting_writers += 1
            while self._writer or self._readers > 0:
                self._cond.wait()
            self._waiting_writers -= 1
            self._writer = True

class NoticeBoard:
    def __init__(self) -> None:
        self.notices: dict[str, str] = {}
        self.rw = FairRWLock()

    def read(self, key: str) -> str:
        self.rw.acquire_read()
        try:
            return self.notices.get(key, "")
        finally:
            self.rw.release_read()

Lock state as three readers and one writer arrive:

Why it works

The invariant is: either the writer flag is set and the reader count is zero, or the writer flag is clear. Every acquire waits inside a loop until entering keeps that invariant, and every release notifies so the waiters re-check it. The loop, not an if, is essential: a notified thread can be beaten to the lock by a newcomer and must test again.

Where it breaks: a reader that acquires the read lock and then calls a method that takes the write lock deadlocks on itself, because upgrading is not supported; design the API so the decision to write is made before any lock is taken. The second trap is cost: this lock takes the condition's internal lock on every operation, so for very short reads a plain lock can actually be faster. Measure before choosing.

plain lock: throughput ≤ 1 / read time. RW lock with r cores and rare writes: ≈ r / read time

The trade-off you must say out loud

Read-write locks pay off when reads greatly outnumber writes and each read is long enough that parallelism matters; otherwise they add complexity and a starvation question for nothing. The alternative worth naming is copy-on-write: writers build a new structure and swap one reference, so readers never lock at all. The follow-up that usually comes next is exactly "why not copy-on-write", and the answer depends on how big the structure is and how often it changes.

Where it shows up in the 100 Google problems

• Phone book with concurrent access: lookups and prefix searches read, adds write; this lock is the second step after a plain lock.
• HTTP router with path parameters: resolving routes happens on every request, registering them rarely; copy-on-write of the trie is the alternative.
• Thread-safe LFU cache: the interviewer rejects one big lock; the honest reply is that even a get mutates frequency, so a read-write lock does not fit cleanly.
• Level-order iterators over a shared tree: many iterators read while a mutator wants to write.

02Used in these problems

• Design a thread-safe LFU cache
• Design a phone book with concurrent access
• Design independent level-order iterators over a shared tree
• Design an HTTP router with path parameters