共享变量的并发读写

我blog上的老文，已经沉了，在专栏发一下。

在高性能并发服务器中，对于共享对象的读写是最常见的操作之一，比如全局配置类对象的并发读取和更新，以及更复杂的如copy on write btree、堆栈等的并发读写，最基本的操作都可以简化理解为通过全局共享的指针，并发读取和更新指针所指向对象的操作。最简单的模型如下所示，一个包含了多个字段的结构体：

可以通过一个全局指针struct gConf *g_conf进行访问。有多个线程会同时读取或更新这个对象，要求任何时刻读取到的内容一定是“一致的”，即读取到的a/b/c的值一定是相同一次更新的值，而不能出现读到的a是某一次更新的值，而b或c是另外一次更新的值。我们假设研发平台为x86_64，指令级的原子操作最多是64位（实际intel提供了128bit的原子操作，但是本文后续的讨论的方法只用到64bit的原子操作），因为gConf包含三个8字节整数，无法使用原子操作指令对a/b/c一次性赋值，因此必须通过程序算法来保证并发情况下读取到的内容满足“一致性”。下面开始从易到难讨论5种处理“共享对象并发读写”的方法。

1. 读写锁最简单朴素的想法是为这个结构配备一个读写锁，读取操作在读锁保护下执行，更新操作在写锁保护下执行。这个方法在对象读取和更新操作都比较简单，且并发程度不高的情况下是一个不错的选择。但是由于读锁与写锁互相阻塞，在读取或更新操作比较费时的情况下，会出现更新或读取线程被阻塞的风险，在高并发的场景下，这种阻塞不可接受。一个实例是数据库系统的全局schema管理器，每次事务都需要读取schema的内容，而DDL会引起schema更新，它的内容比较复杂，更新操作比较费时，会阻塞住处理事务的线程。

2. 引用计数的问题为了解决读写操作相互阻塞的问题，使用类似Copy on write的方式，每次更新时都构造新的对象，在更新过程中，读取操作还是读取旧的对象，更新操作完成后，原子的替换掉指针使其指向新的对象。而被替换掉的对象不能立即释放，而是要确保这个对象不再被继续使用的情况下，才能将其释放掉。因此这里使用引用计数机制，在读取前将引用计数加1，读取完毕后将引用计数减1，当引用计数减到0的时候，表示没人在使用这个对象，可以将其释放掉。引用计数在没有并发保护情况下面临的问题是，取得全局指针g_conf和通过这个指针操作对象的引用计数这两个操作并非原子的。可能存在的情况是，一个线程T1取得g_conf的值保存到寄存器后，就被切换出去，另外一个线程T2将g_conf替换后，判断旧的对象引用计数为0，则将其释放。当T1被切换回来继续执行时，它在寄存器中保存的g_conf指向的对象已经被释放，访问对象引用计数的这一次操作就已经存在非法内存访问的风险。下面两节讨论两种解决并发引用计数的方案。

3. 带锁的引用计数解决第2点提出的原子性问题，一个最直接的方式是使用锁，将读写g_conf和修改引用计数两个操作放在一个独立全局锁（g_lock）的临界区执行，代码示例如下：

读取并将引用计数加1：

将引用计数减1：

使用新的对象替换旧对象：

在实际场景中，通常读取g_conf的操作更多且并发量大，而替换g_conf的操作不会经常发生，因此读取g_conf时加共享锁，替换g_conf时加互斥锁。

使用锁保护引用计数的方式在高并发的情况下存在一些局限：一方面可能存在读者或写者被饿死的情况；另一方面多个写者无法并发，应用在copy on write btree等数据结构中时，多个写者相互阻塞的问题会影响到整个数据结构的并发性能。

4. 无锁的引用计数因此，一个更进一步的设计是使用无锁的引用计数，即无论读取g_conf还是替换g_conf都不在锁中进行，如下图所示：

RefNode的结构包含了指向GConf对象的指针data_ptr，以及引用计数ref_cnt，自增序列号seq_id，ref_cnt和seq_id长度都为4字节且地址连续，可以经由一次8字节的原子操作进行原子性的修改和读取。每次构造新的GConf对象的要同时分配新的RefNode来保存GConf对象的地址。RefNode对象的分配和释放由专用的分配器进行分配和重用，一旦分配就不会释放回系统。引用计数的加1和减1，操作的是RefNode对象的ref_cnt字段，当引用计数减为0时，将data_ptr指向的对象释放，并将seq_id加1，然后将RefNode对象释放给内存分配器。已释放回分配器的RefNode对象仍然可以被安全的访问到。替代全局GConf指针，我们增加了一个被称为GNode结构体的全局对象称为g_node，它包含了指向RefNode对象的指针称为node_idx，和这个RefNode中seq_id字段的值node_seq。node_idx和seq_id长度都为4字节且地址连续，可以经由一次8字节的原子操作进行原子性的读取和替换。读取和替换操作的代码示例如下：将引用计数加1并返回：

将引用计数减1：

使用新的对象替换旧对象：

其中几个原子操作的作用：1. RefNode::atomic_check_seq_and_inc_ref原子性的判断如果seq_id等于传入参数就将ref_cnt加1，并返回true，否则返回false。2. atomic_store_and_fetch_old原子性的将第二个参数赋值给第一个参数，并返回第一个参数的旧值。3. RefNode::atomic_dec_ref_and_inc_seq原子性的将ref_cnt减1，并判断ref_cnt如果已减为0，则将seq_id加1并返回true，否则返回false。工程实现上，为了达到node_idx长度只能有4字节的要求，RefNode分配器设计为定长数组，node_idx为数组下标，使用定长无锁队列作为分配器来维护空闲的node指针。一般来说一个线程只会增加一次引用计数，因此对于维护GConf这样全局只有一个的对象，定长RefNode数组的长度初始化为与线程个数相等就够用了。

5. HazardPointer引用计数基本可以解决共享对象并发读写的问题，但它仍然存在一些不足：第一，每次读取都需要使用原子操作修改全局引用计数，高并发情况下的对同一个变量的原子操作可能成为性能瓶颈；第二，管理RefNode对象的无锁分配器有额外的管理和维护成本，增加的实现复杂度；第三，针对每个共享对象都需要维护N个（N为线程个数）RefNode，如果共享对象数量较多（比如Btree节点），为节省空间，还需要额外的机制来避免大量使用RefNode。因此再介绍一种被称为HazardPointer的思路，它由Maged M. Michael在论文“Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”中提出，基本思路是将可能要被访问到的共享对象指针（成为hazard pointer）先保存到线程局部，然后再访问，访问完成后从线程局部移除。而要释放一个共享对象时，则要先遍历查询所有线程的局部信息，如果尚有线程局部保存有这个共享对象的指针，说明这个线程有可能将要访问这个对象，因此不能释放，只有所有线程的局部信息中都没有保存这个共享对象的指针情况下，才能将其释放。读取和替换操作的代码示例如下：

读取操作：

使用新的对象替换旧对象：

可以看到，读取操作先保存了GlobalVersion到线程局部，然后去读取g_conf指针，虽然可能同时发生的回收操作遍历g_hv_array并不保证原子性，但是即使一个更小的hazard version被放入g_hv_array而错过了遍历，也不会有风险。

因为回收操作是先更新g_conf指针后遍历g_hv_array，而读取操作是先更新g_hv_array后读取g_conf指针，所以最坏情况下读取操作与回收操作同时发生，且读取操作放入g_hv_array的hazard version被回收操作遍历时错过，那么读取操作读到的g_conf一定是被回收操作更新之后的，本次不会被回收，可以安全的访问。

HazardVersion相对HazardPointer，在用法上更加简单，无需针对具体的数据结构进行分析，局限是需要在被管理的对象中保存version。其次，与HazardPointer一样，由于遍历g_hv_array比较费时，因此也需要引入类似的延迟回收机制。需要注意的是，它的缺点也比较明显，一旦出现一个线程长时间不释放HazardVersin时，会阻塞住后面更大Version对象的释放。

7. 总结本文讨论了“读写锁”、“带锁的引用计数”、“无锁的引用计数”、“HazardPointer”、“HazardVersion” 五种方法来处理共享对象的并发读写问题，在实际工程领域，“带锁的引用计数”比较常见，在特定场景下优化读写锁可以得到不错的性能，并且很易于理解和实现；“无锁的引用计数”实现复杂但并发读写性能卓越，在已开源的OceanBase版本中也有实践；“HazardPointer”实现简单，但是理解和使用都较复杂；“HazardVersion”是一种基于“HazardPointer”的创新思路，有一定的局限性，凭借简单易用的接口，可以在很多场景替代“HazardPointer”。