Read-Copy-Update (RCU) is a synchronization mechanism that allows multiple threads to read shared data structures concurrently without locks, while writers can update the same structures with minimal blocking. Originally developed for the Linux kernel, RCU has become fundamental to high-performance systems that need to scale read-heavy workloads across many CPU cores.

The key insight behind RCU is simple: readers never block, and writers defer destructive operations until all existing readers have finished. This trades a small amount of writer complexity for massive improvements in read scalability.

How RCU Works

Traditional locking requires readers to acquire locks, which creates contention as core counts increase. Every reader that takes a lock must coordinate with other readers and writers through shared memory operations, creating cache line bouncing and serialization points.

RCU eliminates this coordination for readers entirely. When a reader wants to access RCU-protected data, it simply marks the beginning of a read-side critical section with minimal overhead—often just a compiler barrier on architectures with cache coherence. The reader then accesses the data structure directly, with no atomic operations or cache invalidations. When done, it marks the end of the critical section.

Writers follow a three-phase process. First, they create a modified copy of the data structure. Second, they atomically update a pointer to make the new version visible to future readers. Third, they wait for all readers that might still be using the old version to finish, then reclaim the old memory. This waiting period is called a grace period.

Grace Periods and Quiescent States

The grace period is the mechanism that makes RCU safe. A grace period is guaranteed to complete only after every CPU core has passed through at least one quiescent state—a point where no RCU read-side critical sections are active on that core.

The kernel tracks quiescent states efficiently. On Linux, context switches, idle periods, and explicit quiescence markers all count. The RCU subsystem aggregates these observations across all cores to determine when it’s safe to reclaim old memory. This happens asynchronously, with no involvement from readers.

Different RCU implementations use different grace period mechanisms. Classic RCU requires every CPU to report a quiescent state. Tree RCU scales this to thousands of cores using a hierarchical tree structure. SRCU (sleepable RCU) allows readers to block, using per-CPU counters instead of relying on scheduler knowledge.

When RCU Makes Sense

RCU excels in scenarios with high read-to-write ratios. Routing tables, connection tracking structures, and configuration data are canonical examples. Reads dominate by orders of magnitude, so eliminating read-side overhead produces dramatic throughput gains.

The pattern also works well for append-mostly data structures like lists where updates primarily add new elements rather than modifying existing ones. Network packet processing, device driver lookups, and security policy enforcement all fit this profile.

RCU is less suitable when writes are frequent relative to reads, or when updates must be immediately visible to all readers. The grace period introduces latency between when a writer removes data and when that memory can be safely freed. Systems that need strict memory bounds or real-time reclamation may find this delay problematic.

Beyond the Kernel

While RCU originated in operating system kernels, the pattern has spread to user space. The userspace RCU library (liburcu) provides multiple RCU variants for different application needs. High-performance databases, message queues, and network services use RCU to eliminate lock contention on read-heavy code paths.

Modern C++ memory ordering primitives make it possible to implement RCU-like patterns using acquire-release semantics, though getting the details right requires careful attention to memory model subtleties. The fundamental idea—separate read and write paths, defer destructive operations—applies regardless of implementation.

The Tradeoff

RCU represents a clear tradeoff: extremely fast lock-free reads in exchange for more complex write paths and deferred memory reclamation. For workloads dominated by lookups and traversals, this exchange is usually worth it. The ability to scale reads across dozens or hundreds of cores without coordination overhead unlocks performance that traditional locking simply cannot achieve.

Understanding RCU means recognizing when elimination of reader overhead matters more than simplicity or immediate memory reclamation. In those cases, RCU transforms contention bottlenecks into scalable, concurrent operations.