RCU 2001 — 让"读"的代价归零的并发数据结构

待复核

是什么

RCU（Read-Copy Update，读-复制-更新）是一套让”读取”几乎零开销，把代价全推给”修改”和”回收” 的并发同步方法。日常类比：图书馆里换书。

普通做法（读写锁）：每个读者读书前要先签到、读完签退；改书的人要等所有人都不在才能换。读多的时候，签到本本身成了瓶颈。
RCU 做法：旧版本书继续放在书架，读者直接取走读，不签到；要换新版本时，把新书放上去、改一下”现在指最新这本”的指针；旧书等”所有当时正在读的人都看完了”再扔掉。

读者完全不需要原子操作、不需要内存屏障、不需要写共享缓存行——这是 RCU 的杀手锏。

为什么重要

不理解 RCU，下面这些事说不清楚：

为什么 Linux 内核的目录缓存（dcache）、路由表、网络协议栈在多核机器上能线性扩展
为什么有的并发数据结构号称”读侧零开销”，是真的零，还是话术
为什么内核里到处是 rcu_read_lock() / rcu_dereference()，但它们在常见配置下展开成空语句
为什么 io_uring、folio、cgroup v2 这些近 10 年的内核新特性几乎都用 RCU

核心要点

RCU 的核心拆成 三件事：

读侧不加锁：读者读取一个被 RCU 保护的指针时，只做一次普通的内存读，不写任何共享变量。所以多核 CPU 不需要互相通信，读侧延迟就是一次缓存命中。
更新走”复制 + 替换”：要修改一个节点，就分配一个新节点、把要改的字段填好、然后原子地替换指针。老节点暂时还在内存里，因为可能有读者正在用它。
延迟回收等”宽限期”：什么时候能安全释放老节点？答：等所有”在你替换指针之前已经开始的读”都结束。这段时间叫宽限期（grace period）。Linux 用一个聪明的判定——只要每个 CPU 都至少经过一次”上下文切换 / 进入空闲 / 进入用户态”，就证明它身上没有任何 RCU 读临界区在跑了。

四个常用 API：

rcu_read_lock() / rcu_read_unlock() —— 标记读临界区。在禁抢占的内核里它们就是空操作。
rcu_dereference(p) —— 读一个 RCU 保护的指针（编译屏障 + DEC Alpha 上的依赖屏障）。
rcu_assign_pointer(p, v) —— 发布新版本（写之前加 release 屏障）。
synchronize_rcu() / call_rcu() —— 写者等宽限期 / 注册回调延迟释放。

实践案例

案例 1：Linux 路由表查找

每次发包都要查路由表，频率极高。表本身偶尔被更新（路由协议、管理员命令）。

读侧（每秒数百万次）：

rcu_read_lock();
fib = rcu_dereference(net->ipv4.fib_main);
result = fib_lookup(fib, &flow);
rcu_read_unlock();

写侧（极低频）：

new_fib = build_new_fib(...);
old_fib = net->ipv4.fib_main;
rcu_assign_pointer(net->ipv4.fib_main, new_fib);
synchronize_rcu();    // 等所有正在用 old_fib 的读者结束
free_fib(old_fib);

读侧零原子操作。多核机器上转发性能几乎线性扩展。（真实内核函数名会随版本变，但「读锁 → 解引用 → 替换指针 → 等宽限期 → 释放」模式不变。）

案例 2：dcache 路径查找

/usr/local/bin/python 这条路径，每次进程访问文件都要解析。Linux 用 RCU 做”乐观无锁”查找（RCU-walk），可拆成四步：

rcu_read_lock() 进入读临界区——不写引用计数，只保证这段时间节点不会被回收。
沿路径一层一层往下查 dentry（目录项缓存）。
走到最后一级前做一次 seqcount 校验：路径中途若被 rename / unlink 改过，校验失败。
失败则退回经典的”带锁 + 引用计数” ref-walk；成功则整次 open() 的几十次查找都是无锁的。

这是 RCU 与 seqcount 配合的经典案例。

案例 3：用户态 RCU（liburcu）

不是只能在内核用。Userspace RCU 库（McKenney 等人后续做的）让用户态程序也能享受同样模式——典型用法是 LTTng 跟踪器、QEMU 的内存映射表、以及一些高频读的内存数据库。用户态版本的难点在于”宽限期判定”——内核可以借调度上下文切换，用户态得自己设计一套（注册线程 + 周期性 quiescent state 上报）。

踩过的坑

读侧”零开销”是有前提的：读者必须保证临界区内不睡眠、不被迁移到别的 CPU（在经典 RCU 下）。如果你需要在读临界区内睡眠，得用 SRCU（Sleepable RCU），它换了一种宽限期判定方式。
写侧不便宜：synchronize_rcu() 在重负载机器上可能等几十毫秒。所以高频更新场景要么用 call_rcu() 异步回收，要么干脆别用 RCU。
读到的可能是旧版本：RCU 不是事务。你可能正在读 v1，写者已经发布了 v2，你的读完成时拿到的还是 v1 的数据——这是设计如此，不是 bug。“最终一致”，不是”立刻一致”。
DEC Alpha 的依赖排序例外：99.9% 的 CPU 上，“先读指针，再读指针指向的内容”自带顺序。Alpha 不保证。这就是 rcu_dereference() 在 Alpha 上要插入显式屏障、其他平台是空操作的原因。
写者之间还得自己加锁：RCU 只解决”读 vs 写”的同步。多个写者并发改同一个数据结构，必须自己上互斥锁/自旋锁。
不是所有数据结构都能 RCU 化：要求节点一旦发布就不再原地修改（不可变），所有更新都走”复制新节点 + 替换指针”。如果你的节点字段经常被原地写入（计数器、统计量），RCU 派不上用场。

适用 vs 不适用场景

适用：

读远多于写（10:1 以上常见，100:1 更典型）
读侧延迟敏感（路由表、dcache、SELinux 策略查找）
数据结构是”指针 + 不可变节点”形态（链表、树、哈希表桶）
能容忍”短暂读到旧版本”

不适用：

读写比例接近 1:1 → 用读写锁或精细锁
强一致性要求（金融、计数器精确值）→ 用原子计数 / seqlock
数据结构频繁原地修改（数组、位图）→ RCU 的”复制”开销吃掉收益
写侧延迟敏感 → 宽限期等待是硬伤

历史小故事（可跳过）

1980 年代：IBM 的 VM/XA 系统里就有类似机制，叫”passive serialization”。
1995 年：McKenney 在 Sequent 公司基于这个思路申请了美国专利（5,442,758），名字叫 Read-Copy Update。
2001 年：McKenney 在 OLS（Ottawa Linux Symposium）把 RCU 介绍给 Linux 社区——就是这篇论文。
2002 年：Linux 2.5.43 合入第一版 RCU 实现。
2003-2010：经历多个变体——Classic RCU、Tree RCU、Preemptible RCU、SRCU 陆续合入，覆盖不同场景。
此后 20 年：RCU 成为 Linux 内核扩展性的支柱之一。McKenney 2019 年离开 IBM、加入 Meta，至今仍在维护 RCU 子系统。今天内核里有上万处 RCU 用法。

学到什么

不对称同步：当一边的频率远高于另一边时，把代价全压给低频那一边能换巨大收益。RCU 是这个思想最成功的工程化。
延迟回收 = 用空间换时间：旧版本暂时不删，换来读者完全不需要协调。这跟 GC、MVCC、shadow paging 是同一个家族的思路。
宽限期的精妙：不维护”现在有谁在读”的列表（那会引入写共享），而是用”每个 CPU 都过一次静止点”做隐式证明。这把分布式问题变成了本地观察。
API 设计的克制：四个原语，覆盖 99% 用法。复杂度藏在实现里，不暴露给调用者。

关联

mvcc —— 数据库版本的”读不阻塞写”，思想同源
seqlock —— 读优先的另一条路，但读者要重试
lock-free-queues —— 同属无锁数据结构家族，但要 CAS
memory-barriers —— RCU 的正确性建立在内存模型之上
linux-kernel —— RCU 的主要落地

反向链接

lamport-bakery —— Lamport Bakery — 用取号排队解决并发互斥
mvcc —— MVCC — 让读写互不挡路的版本账本