Read-Write Lock

Why RWLock matters

• Database indexes. A B-tree index is read on every query and modified only on insert/update/delete. With 10:1 read:write ratio (typical OLTP), RWLock cuts contention dramatically vs a plain mutex on the index root.
• Configuration objects. Production services read a config snapshot millions of times per second; reload happens once per minute. RWLock or its read-mostly cousin RCU is the canonical pattern.
• Cache layers. An LRU cache exposes get(), put(), evict(); reads are 10-100× more frequent. RWLock allows many concurrent gets while serializing puts. Higher-throughput caches partition the lock per shard or go fully lock-free.
• Copy-on-write structures. Persistent data structures pair RWLock with structural sharing — readers see a stable snapshot while a writer builds the next version atomically.
• File-system metadata. Directory reads (readdir, stat) vastly outnumber writes (mkdir, unlink). VFS layer in Linux uses per-inode RWLocks (now mostly RCU after the dcache rewrite).
• Network routing tables. Per-packet route lookups are reads; topology updates are rare writes. Most kernels and userspace routing daemons use either RWLock or RCU.

How RWLock is implemented

The naive design is a single 64-bit atomic word with a writer flag in the top bit and reader count in the rest:

// Reader acquire
do {
    state = lock.load();
    if (state & WRITER_BIT) wait();
} while (!lock.compare_exchange(state, state + 1));

// Writer acquire
do {
    state = lock.load();
    if (state != 0) wait();
} while (!lock.compare_exchange(0, WRITER_BIT));

Real implementations (glibc, jemalloc, Java's ReentrantReadWriteLock) are far more complex because of:

• Wakeup discipline. When a writer releases, do you wake one writer (FIFO) or wake all readers (throughput)? Glibc uses a futex-based wait queue with explicit policy.
• Recursive locking. Some RWLocks allow a thread holding read to acquire read again (recursive read), or upgrade read-to-write under specific conditions. Adds per-thread state tracking.
• Cancellation. Pthread cancellation, async signals, and process-shared semantics complicate the wait/wake logic.
• Cache-friendliness. The hot reader-count word becomes a contention magnet. Per-CPU sharded RWLocks (Linux's percpu_rwsem) eliminate this for reads at the cost of slow writes.

The starvation problem

Reader-preference policy: while reader-count > 0, new readers may enter; writers wait. Sounds throughput-friendly but produces an unbounded waiting time for writers when readers continuously arrive. Documented production bug: a Cassandra-like store had a stat-update writer waiting 30+ seconds during query bursts. Symptoms: stale stats, eventual cluster-wide thread pool exhaustion as writes piled up.

Three production fixes:

• Writer-preference. Once a writer queues, the lock blocks new readers. Existing readers drain, writer proceeds, then a batch of waiting readers can enter together. Preferred for write-correctness-critical code.
• FIFO fairness. Readers and writers form a single queue in arrival order. Java new ReentrantReadWriteLock(true). Eliminates starvation in both directions but lowers reader throughput because contiguous readers can't bypass intermediate writers in the queue.
• Bounded reader window. Reader count caps at K; the K+1th reader waits even if no writer queued. Bounds the worst-case writer wait to K read durations.

RCU as a RWLock alternative

If reads need to scale across many cores, RWLock's reader-counter is itself a bottleneck — every reader pings the same cache line, costing 100+ ns on a multi-socket machine. RCU sidesteps this entirely: readers do not modify shared state.

Numbers from the Linux kernel folks (paulmck.livejournal.com): on a 64-core machine, naive pthread_rwlock_rdlock peaks around 5M reads/sec aggregated; per-CPU rwsem hits 600M/sec; classic RCU has effectively no upper bound (limited only by per-thread work).

The trade-off: RCU writers must wait a "grace period" — typically 1-10 ms — before freeing the old version. So RCU is for genuinely read-mostly data with copyable semantics; RWLock fits when writes need predictable latency and the data can't easily be copied.

Performance benchmarks

From a 2023 benchmark on 16-core x86 (numbers approximate):

• std::shared_mutex, 100% reads, 16 threads: 18M ops/sec.
• std::shared_mutex, 90/10 mix: 12M ops/sec.
• std::shared_mutex, 50/50 mix: 4M ops/sec.
• std::mutex equivalents: 6M, 6M, 5M ops/sec respectively.
• folly::SharedMutex (writer-priority, reader-fast-path): 80M ops/sec at 100% reads.

Takeaway: high-quality RWLocks beat mutexes from ~80% reads up; bog-standard pthread_rwlock can lose to mutex on shorter critical sections because of implementation overhead.

Common misconceptions

• "Always faster than mutex." Wrong on low-contention or short critical sections. The reader-counter atomic adds ~10-30 ns; an uncontended mutex acquire is ~25 ns. Profile before assuming.
• "Fair by default." Pthread_rwlock is reader-preference on Linux glibc, writer-preference on BSD/macOS, configurable. Java's default ReentrantReadWriteLock is non-fair (better throughput, possible starvation).
• "Read-to-write upgrade is safe." Generally not — two readers attempting upgrade simultaneously deadlock. Use upgrade-mode locks (boost::upgrade_mutex) or release-and-reacquire with re-validation.
• "Reader cost is free." Every reader still does an atomic increment + decrement, costing 10-30 ns on x86 and more on cache-cold cases. Hot-path code measures this.
• "Solves the cache problem." RWLock distributes reads across cores but writes still invalidate the lock's own cache line and the protected data's lines. Per-CPU shards or RCU scale further.
• "More readers always faster." The reader-count cache line bouncing across NUMA nodes can make 32-thread RWLock reads slower than 4-thread. Sharded RWLocks or RCU are needed at scale.

When to pick something other than RWLock

• Mutex when: reads are short or rare; simpler reasoning; less code complexity.
• RCU / hazard pointers when: reads must scale to dozens of cores; writes are infrequent and tolerate millisecond latency.
• Lock-free data structure when: a published algorithm exists for your operation set (queue, hash, list).
• MVCC / snapshot isolation when: readers want a consistent point-in-time view rather than a fresh value, common in databases.
• Copy-on-write when: writes can be infrequent and atomic-pointer-swap suffices.
• Per-CPU data + IPI when: counter-style data, where each CPU maintains its own value and reads aggregate.