PgSQL · 源码分析 · PG中的无锁算法和原子操作应用一则

无锁算法是利用cpu的原子操作实现的数据结构和算法来解决原来只能用锁才能解决的并发控制问题。 众所周知，在一个并发系统中特别是高并发的场景下，锁的使用会影响系统性能。 这里的cpu的原子操作是不可中断的一个或者一系列操作, 也就是不会被线程调度机制打断的操作， 运行期间不会有任何的上下文切换。

常用的原子操作包括：

cas，compare & set，或是 compare & swap: 看某内存位置的值是不是等于一个值oldval， 如果是就写入新值newval，返回一个bool值标识是否做了更新

fetch-and-add: 把某个内存位置加上一个值

test-and-set: 写值到某个内存位置并传回其旧值

本文并不打算对这些原子操作概念和原理本身进行展开讨论，有兴趣的读者可以参考wikipedia或其它的网上文章。

由于postgresql是一个跨平台的开源软件，支持十几种cpu架构和众多的操作系统， 而原子操作又与cpu架构和编译器紧密相关，所以原子操作在postgresql中的实现稍显复杂。

在postgresql中原子操作的实现涉及到的文件包括（由于postgresql的头文件都位于源码的include目录里， 所以本文后面的说明头文件路径时都是只引用到include子目录这一层）:

include/port/atomics.h

include/port/atomics目录里的所有头文件

源文件 src/backend/port/atomics.c

原子操作的所有对外部模块可用符号都声明在头文件port/atomics.h中， 而其他文件都可看作是原子操作模块的内部实现文件不允许外部模块直接引用。 也就是说，如果要在postgresql代码中使用原子操作只需包含port/atomics.h即可。 而port/atomics.h也是原子操作模块的最主要的源文件，所有其他的源文件都是通过该文件组织起来的。 下面从port/atomics.h源文件开始分析。

port/atomics.h 整个文件分成4个部分。

通常支持一个新的平台只需要在port/atomics.h的第1部分或第2部分中实现如下函数即可：

pg_compiler_barrier()

pg_write_barrier()

pg_read_barrier()

pg_atomic_compare_exchange_u32()

pg_atomic_fetch_add_u32()

pg_atomic_test_set_flag()

pg_atomic_init_flag()

pg_atomic_clear_flag()

前三个函数是实现内存屏障（memory barrier）的，剩下的是基本的原子操作函数， port/atomics.h的第3部分包含了头文件port/atomics/generic.h, 它利用这几个基本的原子操作实现更多的原子操作函数。

port/atomics.h第4部分是定义本模块所有的导出函数，通常都是定义一个简单的inline函数去调用该函数的具体实现（实现函数名一般为xxx_impl）。 下面是第4部分具体定义的原子操作函数：

内存屏障相关函数，包括 compiler barrier 和 read/write barrier

语义上的布尔值（pg代码里叫flag，具体实现上可能映射到一个字节，或一个整数）的原子操作，包括：

pg_atomic_init_flag，初始化一个flag

pg_atomic_test_set_flag, test-and-set，这也是flag的唯一支持的原子 操作函数

pg_atomic_unlocked_test_flag，检查flag是否没有被设置

pg_atomic_clear_flag，清除已设置的flag

32位无符号整数的原子操作，包括：

pg_atomic_init_u32, pg_atomic_read_u32, pg_atomic_write_u32，初始化、读、写操作

pg_atomic_exchange_u32，给原子变量赋值并返回原值

pg_atomic_compare_exchange_u32, 32位无符号整数的cas操作，比较原子变量和另一个变量的值， 如果相等就赋一个新值到原子变量里，返回一个布尔值标识是否进行了赋值操作

pg_atomic_fetch_add_u32, pg_atomic_fetch_sub_u32, pg_atomic_fetch_and_u32, pg_atomic_fetch_or_u32 对某个原子变量进行加、减、与、或操作，并返回变量改变之前的值

pg_atomic_add_fetch_u32, pg_atomic_sub_fetch_u32 对某个原子变量进行加、减操作，并返回变量改变之后的值

64位无符号整数的原子操作，与32位的实现的操作函数相似，只是实现的是64位版本，这里需要注意的是， 64位版本并不保证所有平台的都支持，目前在postgresql的源代码中还没有被使用。

在port/atomics.h的文件开头的注释里，代码的作者也提到了：除非必要否则尽量不要使用原子操作， 可以使用更上层的数据结构或算法如lwlock，spinlock或者普通锁，因为使用原子操作需要更多的技巧， 写出完全正确的代码是比较难的。

目前在postgresql的代码中有3个地方使用了原子操作来提高并发性能，分别是事务提交时的并发处理， lwlock的实现和buffer的管理，下一节我们将对其中的一个进行分析，其他对原子操作的使用将会在后续的文章中进行分析。

当一个写事务提交时，进程要修改自己的pgproc结构来标识自己已经结束了，其中的一个主要动作是重置自己事务id(xid)， 为了简化我们后面就管这个过程叫重置xid，这时需要以排它的方式获取procarraylock锁，以防拿事务snapshot的进程看到不一致的结果。 当有很多事务提交时，每一个要提交的进程依次唤醒、拿锁、放锁，导致该锁的过度争用。为了提高效率这个patch只让一个进程获取procarraylock锁， 由该进程为所有同时提交的其他进程（patch里叫一个procarray组）集中批量修改。

下面来详细分析一下该patch的代码。patch修改了pgproc结构和pgproc数组头结构proc_hdr，在pgproc中加入了3个成员变量：

在proc_hdr中加入一个成员变量：

首先在事务提交时尝试去获取procarraylock，如果获取到了就直接调用重置xid函数， 否则调用一个新加的函数procarraygroupclearxid通过使用原子操作进行批量重置xid。

整个patch主要逻辑都在procarraygroupclearxid函数中，该函数首先将自己加到procarray组的头部：

这段代码通过对位于proc_hdr结构中的procarray组头部进行cas原子操作，不断的尝试将自己加入到procarray组中， 这里是通过存储其pgprocno（相当于pgproc数组下标），形成一个用pgprocno串起来的链表。 注意在以上3条语句之间随时有可能由其他进程插进来把它们自己加到procarray组中导致cas操作失败， 失败之后程序会进行下一次循环直到成功。 执行完这段代码变量nexidx存储的是原procarray组的头部， 代码通过比较nextidx来判断是否是procarray组的第一个成员即leader，leader的nextidx应该是初值invalid_pgprocno， 由leader负责整个组的重置xid工作，非leader成员只需等待leader完成工作后通知自己即可。

procarray组的leader先获取procarray锁，然后从组头部拿到第一个元素，并把组头置成初值invalid_pgprocno， 这时其他进程可以开始一个新的procarray组：

注意在执行这段代码过程中，还会不断有新到组成员加进来，所以使用了while循环。

这个函数的最后就比较简单了，procarray组的leader循环组列表对每个成员调用重置xid函数， 最后在释放了procarraylock锁之后通知每个组成员继续执行。

通过对以上patch代码的分析我们可以看到pg巧妙的利用了原子操作有效的减少了在高并发的条件下在事务提交时对procarraylock锁的争用。 但随着硬件服务器上cpu核数的不断增加，并发的不断加大，procarraylock锁的争用仍然是一个需要不断优化的热点， 其中一个最有希望的解决方案是使用csn（commit sequence number）替代原来的事务快照（snapshot）机制来做可见性判断， 这在postgresql社区里已经有了patch，我们将在后续文章进行分析。