原子操作概述
近年来随着服务器上CPU核数的不断增加，无锁算法（Lock Free）越来越广泛的被应用于高并发的系统中。PostgreSQL 做为世界上最高级开源数据库也在9.5时引入了无锁算法。本文先介绍了无锁算法和原子操作在PostgreSQL中的具体实现， 再通过一个Patch来看一下在PostgreSQL中是如何利用它来解决实际的高并发问题的。
无锁算法是利用CPU的原子操作实现的数据结构和算法来解决原来只能用锁才能解决的并发控制问题。 众所周知，在一个并发系统中特别是高并发的场景下，锁的使用会影响系统性能。 这里的CPU的原子操作是不可中断的一个或者一系列操作, 也就是不会被线程调度机制打断的操作， 运行期间不会有任何的上下文切换。
常用的原子操作包括：
- CAS，Compare & Set，或是 Compare & Swap: 看某内存位置的值是不是等于一个值oldval， 如果是就写入新值newval，返回一个bool值标识是否做了更新
- Fetch-and-add: 把某个内存位置加上一个值
- Test-and-set: 写值到某个内存位置并传回其旧值
本文并不打算对这些原子操作概念和原理本身进行展开讨论，有兴趣的读者可以参考Wikipedia或其它的网上文章。
PostgreSQL中原子操作的实现
由于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个部分。
第1部分和第2部分分别用来包含具体CPU架构相关的头文件和各种编译器相关的头文件。 这些头文件都在port/atomics目录下。第1部分所包含的头文件里一般都是用汇编语言实现的CPU相关的内存屏障1和原子操作的实现函数， 目前只在X86架构下用GCC编译的情况下实现了汇编版本原子操作，而其他的CPU架构则采用第2部分里的编译器实现的通用版本， 一般的编译器如GCC2都内置了原子操作的支持。之所以X86版本提供了基于汇编的实现主要是为了更好的性能和支持更老版本的GCC。 第2部分的最后还包含了port/atomics/fallback.h头文件，该文件声明了PostgreSQL自己使用自旋锁或操作系统的信号量模拟实现的原子操作的版本， 具体实现位于src/backend/port/atomics.c中，这在第1部分和第2部分都没有找到实现的情况下会使用该版本，注意使用该版本性能会比较差。
通常支持一个新的平台只需要在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的管理，下一节我们将对其中的一个进行分析，其他对原子操作的使用将会在后续的文章中进行分析。
使用原子操作减少事务提交时锁的争用
在PostgreSQL中每个Session的执行时的一些关键的状态信息都保存在PGPROC这个结构当中， 如当前所执行事务的事务ID(xid)，PostgreSQL维护了一个PGPROC的数组叫ProcArray， 由一个叫ProcArrayLock的锁保护着。ProcArray在PostgreSQL当中属于核心数据结构， 在事务的开启和结束，在执行任何查询时获取事务快照（Snapshot）3做可见性判断时都会获取ProcArrayLock锁去访问ProcArray。 现在在高并发的情况下ProcArrayLock锁争用已经非常严重了，在PostgreSQL 9.6时提交了一个Patch使用原子操作来减少对该锁的争用。
当一个写事务提交时，进程要修改自己的PGPROC结构来标识自己已经结束了，其中的一个主要动作是重置自己事务ID(xid)， 为了简化我们后面就管这个过程叫重置xid，这时需要以排它的方式获取ProcArrayLock锁，以防拿事务Snapshot的进程看到不一致的结果。 当有很多事务提交时，每一个要提交的进程依次唤醒、拿锁、放锁，导致该锁的过度争用。为了提高效率这个Patch只让一个进程获取ProcArrayLock锁， 由该进程为所有同时提交的其他进程（Patch里叫一个ProcArray组）集中批量修改。
下面来详细分析一下该Patch的代码。Patch修改了PGPROC结构和PGPROC数组头结构PROC_HDR，在PGPROC中加入了3个成员变量：
/* Support for group XID clearing. */
/* 如果是一个ProcArray组的成员为true */
bool procArrayGroupMember;
/* 指向下一个ProcArray组的成员 */
pg_atomic_uint32 procArrayGroupNext;
/*
* 这是在调用重置xid的函数所需要传递的参数
*/
TransactionId procArrayGroupMemberXid;
在PROC_HDR中加入一个成员变量：
/* ProcArray组的第一个成员 */
pg_atomic_uint32 procArrayGroupFirst;
首先在事务提交时尝试去获取ProcArrayLock，如果获取到了就直接调用重置xid函数， 否则调用一个新加的函数ProcArrayGroupClearXid通过使用原子操作进行批量重置xid。
整个Patch主要逻辑都在ProcArrayGroupClearXid函数中，该函数首先将自己加到ProcArray组的头部：
while (true)
{
nextidx = pg_atomic_read_u32(&procglobal->procArrayGroupFirst);
pg_atomic_write_u32(&proc->procArrayGroupNext, nextidx);
if (pg_atomic_compare_exchange_u32(&procglobal->procArrayGroupFirst,
&nextidx,
(uint32) proc->pgprocno))
break;
}
这段代码通过对位于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 (true)
{
nextidx = pg_atomic_read_u32(&procglobal->procArrayGroupFirst);
if (pg_atomic_compare_exchange_u32(&procglobal->procArrayGroupFirst,
&nextidx,
INVALID_PGPROCNO))
break;
}
注意在执行这段代码过程中，还会不断有新到组成员加进来，所以使用了while循环。
这个函数的最后就比较简单了，ProcArray组的Leader循环组列表对每个成员调用重置xid函数， 最后在释放了ProcArrayLock锁之后通知每个组成员继续执行。
通过对以上Patch代码的分析我们可以看到PG巧妙的利用了原子操作有效的减少了在高并发的条件下在事务提交时对ProcArrayLock锁的争用。 但随着硬件服务器上CPU核数的不断增加，并发的不断加大，ProcArrayLock锁的争用仍然是一个需要不断优化的热点， 其中一个最有希望的解决方案是使用CSN（commit sequence number）替代原来的事务快照（Snapshot）机制来做可见性判断， 这在PostgreSQL社区里已经有了Patch，我们将在后续文章进行分析。
1 内存屏障是一个和原子操作相关的概念，限于篇幅本文没有介绍， 有兴趣的读者可参考PostgreSQL源代码目录下的src/backend/storage/lmgr/README.barrier，或其他网上资料
2 参见 GCC 6.2.0 原子操作内置函数
3 在获取事务快照（Snapshot）时需要以共享方式获取ProcArrayLock锁， 并且循环整个ProcArray数组来拿到当前所有执行事务的列表，持锁时间会更长，而且获取事务快照是一个更频繁的操作， 根据事务隔离级别的不同，执行每个事务可能要进行多次获取事务快照操作
