Contents

Read Copy UpdateEdit

Read Copy Update (RCU) is a synchronization technique designed to make read-heavy data structures in concurrent systems fast and scalable. By allowing readers to access data without acquiring locks and by updating data through create-and-swap of versions, RCU reduces contention and latency on multicore hardware. It is a foundational approach in the Linux kernel and has influenced many high-performance data structures in both kernel and user space, including Userspace RCU implementations and various lock-free patterns. At its core, RCU trades a modest amount of writer-side complexity for dramatically faster and more scalable reads, which matters in systems that must handle millions of concurrent readers without stalling.

RCU is most at home in read-mostly environments where the cost of locking on every read would be prohibitive. In such scenarios, many threads can read shared state simultaneously without blocking each other, while writers proceed by constructing a new version of the data and swapping pointers. The old version remains visible to readers that started before the swap, and is reclaimed only after a grace period has elapsed, ensuring no reader still references it. This grace period is typically determined by quiescent states in the system (conditions under which a thread or CPU is considered to have passed through a stable state), and is orchestrated by specialized primitives such as synchronize_rcu and memory-reclamation callbacks like call_rcu.

Overview

  • Read-side operations proceed without taking locks. Readers enter a critical section via rcu_read_lock and exit with rcu_read_unlock, performing their reads while the data structure remains accessible and unmodified to them.
  • Writers allocate a new version of the data, modify it as needed, and atomically update the pointer to the new version.
  • The old version remains available to any readers that started before the swap, but is not reclaimed until a grace period has passed, at which point the old memory can be freed.
  • The approach hinges on careful memory ordering and grace-period management to avoid use-after-free errors and ensure safe reclamation of old versions.
  • RCU is implemented in the Linux kernel and is also available in user-space libraries, enabling similar patterns outside the kernel, for example in high-performance servers and databases. See Linux kernel and Userspace RCU for broader context.

How it works

  • Read path
    • A reader enters an rcu_read_lock region and accesses a shared data pointer.
    • The reader completes its read, then exits the rcu_read_lock region.
  • Update path
    • A writer allocates a new copy of the data and makes the necessary changes to the new version.
    • The writer updates the shared pointer to point to the new version, thereby making the new data visible to subsequent readers.
    • The old version remains accessible to any readers that started before the swap.
    • After a grace period, the system guarantees that all pre-existing readers have finished, and the old version can be reclaimed safely.
  • Grace period and reclamation
    • The grace period is defined by the point at which all CPUs or threads have passed through a quiescent state, indicating that no reader is still referencing the old version.
    • Reclamation is typically deferred via callbacks (e.g., call_rcu) so the memory is freed only when it is safe.

Variants and flavors

  • Classic RCU (non-preemptible read-side): optimized for environments where readers do not preemptively interrupt critical sections, keeping the read path extremely lightweight.
  • Preemptible RCU (rcu_sched in the Linux kernel): supports kernels with preemption, ensuring correctness even when readers can be interrupted mid-read.
  • Sleepable RCU (SRCU): allows readers to sleep, broadening the contexts in which RCU can be used, at the cost of some additional complexity and overhead.
  • Userspace RCU (URCU): a broad family of libraries that bring RCU-like semantics to user-space applications, enabling scalable reads in servers and services outside the kernel.
  • In practice, each flavor targets different scheduling and preemption guarantees, memory reclamation needs, and performance trade-offs, allowing developers to pick the approach that best fits their workload.

Implementations and patterns

  • In the Linux kernel, RCU is a core primitive with documented interfaces such as rcu_read_lock / rcu_read_unlock and synchronize_rcu, together with callbacks like call_rcu for deferred reclamation.
  • In user space, the URCU family provides similar primitives for applications that require scalable read access without expensive locking.
  • Common data-structure patterns under RCU include read-mostly maps, lists, and caches where readers frequently traverse data structures without interfering with writer threads.

Use cases and examples

  • The Linux kernel uses RCU to manage large, read-dominated data structures such as the dentry cache and various filesystem metadata, allowing fast path lookups without lock contention.
  • Many high-performance servers and databases adopt RCU-like patterns to optimize read latency in hot paths, especially where data can be versioned and old versions can be reclaimed later.
  • The combination of RCU with memory reclamation primitives provides a practical approach to avoiding long-lived locking while maintaining correctness under concurrent updates.

Performance and trade-offs

  • Reads are typically fast and scalable, as they proceed without acquiring global locks.
  • Writes incur overhead: duplicating data, updating pointers, and scheduling reclamation. The cost of a write is offset by the gains in read throughput in read-heavy workloads.
  • Memory usage can increase due to maintaining multiple versions of data during the grace period.
  • Correct use requires discipline: readers must not access freed memory and writers must ensure that grace periods are properly observed.
  • The decision to use RCU depends on workload characteristics (read-to-write ratio, mutation patterns, and latency requirements) and the ability to manage the added complexity in code paths.

Controversies and debates

  • Proponents emphasize empirical performance gains: for systems with many concurrent readers, RCU can dramatically reduce lock contention and improve latency, making it a practical choice for scalable, high-throughput software.
  • Critics caution that the technique introduces complexity and potential memory-management hazards. The correctness guarantees rely on precise use of read-side primitives, grace periods, and deferred reclamation, which can lead to subtle bugs if misapplied.
  • A common debate centers on when to adopt RCU instead of simpler locking or reference-counting schemes. From a results-oriented stance, defenders argue that, in the right contexts, RCU delivers superior performance and scalability with manageable risk when implemented with discipline and robust testing.
  • In practice, the right approach depends on the system’s goals: maximum read-side performance and low latency for large-scale, read-heavy workloads; or simpler, more maintainable locking strategies for write-heavy or smaller-scale components.
  • Where critics see risk, advocates point to mature toolchains, well-documented patterns, and mature implementations in the Linux kernel and URCU that provide proven reliability when used appropriately.

See also