RCU，读多写少的锁实现

发表于 分类于

之前有很多场景都是读多写少，而且不怎么需要实时。一直比较好奇应该用什么锁，读写锁总是不满意，最近看6.S081看到rcu，咦，是我想要找的东西。

水平超低预警

一年前就开始看DDIA和做6.824 Raft 那些东西，不过当时水平太菜了。一直不太敢写并发和分布式相关的东西。并发有很多反直觉的地方，我写出来总是踩坑。好在golang的channel什么的写起来都很舒服。
一年过去了，自认水平总没有当初那么菜了，鼓起勇气开始写一点关于并发和Go的东西，所以新开了一个分类。（结果发现一年前看的好多东西都忘了。。。记住的好多也是错的。。。）
这个系列肯定有很多丢人现眼的地方，路过的朋友看到我说的不对的地方请在评论告诉我

用途和概念

用途

我们可以用读写锁来保证读取和写入的一致性。在大量读取、少量写入的场景，读写锁的效率会比较低，用RCU可以提高读的性能。使用RCU，读的时候可以不加锁，也不用去管什么内存屏障和原子性了，直接读就完事了。
而且如果写入很少，几乎没有同时写入的情况，RCU的写入速度是很快的，写并不一定比读写锁慢（Grace Period其实很短）

典型场景包括：路由表、DNS查询、内核

The basic form of such “Pure RCU” designs is as follows:

  1. Make a change, for example, to the way that the OS reacts to an NMI.
  2. Wait for all pre-existing read-side critical sections to completely finish (for example,by using the synchronize_sched() primitive). The key observation here is that subsequent RCU read-side critical sections are guaranteed to see whatever change was made.
  3. Clean up, for example, return status indicating that the change was successfully made

在内核里面主要是处理中断、代替读写锁、订阅发布、代替引用计数等。在内核中应用的介绍可以看文章：RCU Usage In the Linux Kernel: One Decade Later
下面是一个NMI的例子（不可打断中断应该也不会被抢占，正适合RCU）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
rcu_list_t nmi_list;
spinlock_t nmi_list_lock;
void handle_nmi()
{
  rcu_read_lock();
  rcu_list_for_each(&nmi_list, handler_t cb)
    cb();
  rcu_read_unlock();
}
void register_nmi_handler(handler_t cb)
{
  spin_lock(&nmi_list_lock);
  rcu_list_add(&nmi_list, cb);
  spin_unlock(&nmi_list_lock);
}
void unregister_nmi_handler(handler_t cb)
{
  spin_lock(&nmi_list_lock);
  rcu_list_remove(cb);
  spin_unlock(&nmi_list_lock);
  synchronize_rcu();
}

RCU在用户态用的比较少，远不如mutex和spinlock普遍。
当然，用户态一般不怎么用这个东西，像数据库那种（用redis上内存用cache硬抗.jpg）

概念

reader很简单，就是rcu_read_lock和rcu_read_unlock。rcu_read_lock和rcu_read_unlock中间的这一段通常叫读侧临界区 (read-side critical sections)

writer的要复杂一点

实现

rcu的实现有很多，比如实时性比较好的srcu（sleepable rcu）、嵌入式用的比较多的tinyrcu、用于CPU核数非常多的tree-rcu；这里只说一下简单经典的rcu实现，其他具体的实现可以去看Paul的文章。
这里大部分都是从lwn那里抄来的，建议英文好的直接看原文：
What is RCU? Part 2: Usage

如果想看详细实现可以去看linux rcu主要作者Paul的文章和书：Is Parallel Programming Hard, And, If So, What Can You Do About It?

Linux对于指针的load和store都是原子的，所以在链表读取的时候，指针要么指向新插入完成的，要么指向旧的还没被删的链表，不会出现正在修改链表的时候刚删除指针还没来得及插入产生segmentation fault。

以链表为例，写入（Write）的时候先复制（copy）一个副本，然后在读取（read）较少的合适时间执行插入操作。当然，我们可以等到完全没有写入的间隙。但是读取（reader）很多一直没用空闲，写入会非常慢；一直都有reader的极端情况会导致一直无法写入。rcu用宽限期（grace period）巧妙的解决了这个问题。

怎么知道copy之前的读取全部完成可以reclaim了

我看rcu之前的第一反应是引用计数，当引用计数降到0就说明copy的副本可以reclaim了。但是引用计数效率太低了，而且多核的时候引用计数更麻烦了。

经典的rcu模型是不允许抢占的。当读取完成进入临界区，我们认为这个CPU进入一次静止状态（quiescent state），以下简称QS。linux里面用cpumask来记录这个状态，我们就简单的当成是用一个bitmap来保存每个cpu的状态好了。显然，从bitmap得知copy之后每个CPU都经历过一次QS后，那在copy之前的读操作都已经完成了，这个时候就可以reclaim了。

多个writer怎么处理

如果有多个writer，那通常会给不同的writer加spin_lock来处理

无锁

无锁是对于读来说的，写入的时候锁比较多。在修改bitmap的时候是需要加锁的（一般是spin_lock）。太多的写入同时对bitmap加锁效率很低，于是就有了tree-rcu。tree-rcu是将不同的CPU状态分组加锁，然后树状结构向上汇总状态。

如果你的逻辑CPU数量（就是你在htop里看到的，比如6核12线程的5600x是12）小于16，那它会退化成单个rcu_node。
tree-rcu详见[A Tour Through TREE-RCU’s DataStructures]

多个writer的情况下也要加锁，一般是spin_lock锁。

用户态

rcu的实现依赖了很多内核态的东西，移植到用户态比较困难。比较出名的一个用户态rcu是liburcu

模仿rcu的思想可以实现一点读多写少的优化，比如sonic的map
如何实现一个超快读的map

链接

What is RCU? – “Read, Copy, Update” Linux Kernel文档的介绍
RCU Usage In the Linux Kernel: One Decade Later MIT 6.828课 RCU的阅读材料，我就是在这个课上看到rcu的，看起来还挺有意思
Introduction to RCU
Is Parallel Programming Hard, And, If So, What Can You Do About It? 我对于rcu的不少疑惑是看了这个才懂，推荐（本书主要作者Paul也是linux rcu的主要实现者）
深入理解并行编程 上面那本书的中文翻译
谢宝友 深入理解RCU系列文章
Linux锁机制：可抢占RCU原理
[CPU masks - linux-insiders] linux-insiders的CPU masks介绍（这本书也挺不错的，我好几次查资料翻到，讲的比较易懂）
CPU masks 介绍 中文翻译