浅谈原子操作

所谓原子操作，就是要么不做，要么全做。在很多场景中，都有对原子操作的需求。在翻aep的spec文档时，也发现了一个巧妙的方法。所以顺便发散性地总结一下各种实现原子操作的方法，水平有限，欢迎拍砖。

小粒度——指令

根据intel手册卷三第八章的描述，x86使用三种机制来实现原子操作：

1. Guaranteed atomic operations。Guaranteed atomic operations是指一些基本的读写内存操作，这些操作都是保证原子性的。一般来说，读写位于一个cache line中的数据是原子性的。
2. bus lock，使用LOCK#信号和指令的lock前缀。锁总线的方式很简单，进行原子操作的cpu会在bus上assert一个LOCK#信号，此时其他cpu的操作都会被block住。
3. cache lock，利用cache一致性协议(MESI协议)来实现。如果要访问的内存区域已经在当前cpu的cache中了，就会利用cache一致性协议来实现原子操作，否则会锁总线。

intel早期cpu(如Intel386，Intel486，奔腾处理器)实现原子操作，是通过bus lock来实现的。这种实现的问题，是完全不相关的两个cpu之间，也会相互竞争总线锁，从而导致整体性能下降。在后来的cpu中，intel对这一问题进行了优化。当要进行原子操作的内存已经被拉入cache中时，cpu会使用cache一致性协议来保证原子性，这被称为cache lock。相比于bus lock，cache lock粒度更细，能获得更好的性能。
x86中，有些指令是自带lock语义的，比如XCHG，更新段描述符等等；另外一些指令可以手动加上lock前缀来实现lock语义，比如BTS, BTR,CMPXCHG指令。在这些指令中，最核心的当属CAS(Compare And Swap)指令了，它是实现各种锁语义的核心指令。不同于自带原子语义的XCHG，CAS操作要通过”lock CMPXCHG”这样的形式来实现。一般而言，原子操作的数据长度不会超过8个字节，也不允许同时对两个内存地址进行CAS操作（如果可以的话，免锁双向链表不是梦）。
原子操作中另一个绕不开的话题是ABA问题，水平有限，就不展开讲了。简单提一个例子，在linux内核的slub实现中，用上了一个宏cmpxchg_double，这并不是同时对两个内存地址进行CAS的黑魔法，而正是利用CMPXCHG16B指令解决ABA问题的宏函数，有兴趣的可以深究一把。

大粒度

当原子操作的对象大小在16字节或者8字节以内时，一两条指令就能实现原子操作。但是，当对象的大小较大时，实现原子操作的就需要其他方法了，比如加锁和COW。深究这两种方法，可以发现在本质上，它们还是将问题转换成了16字节的原子操作。

加锁

加锁这个方式很好理解，只要一加锁，整个临界区的操作就可以被看作一个原子操作。
内核中提供了各种各样的锁，自旋锁，读写锁，seq锁，mutex，semaphore等等，这些锁对读写者的倾向各有不同，在是否允许睡眠上也有所不同。
简单来说，自旋锁和读写锁的核心都是利用原子指令来CAS操纵一个32位/64位的值，它们都不允许睡眠，但是读写锁对于读者做了优化，允许多个读者同时读取数据，而自旋锁则对于读写操作没有什么偏向性。seq基于自旋锁实现，不允许睡眠，但是对写者更为友好。mutex和semaphore也是基于自旋锁实现的，但是它们允许互斥区的操作陷入睡眠。
可以看到，加锁这种方式，最核心的还是利用指令实现原子操作。

COW

针对大对象原子操作的另一种方式是COW（copy on write）。
cow的思想其实非常简单，首先我们有一个指向这个大对象的指针，在需要原子性修改这个大对象的数据时，因为没办法做到inplace修改，所以就把这个对象的数据拷贝一份，在对象副本上修改，最后再原子性地修改指向这个对象的指针。可以看到，这里最核心的地方是利用指令来实现指针的替换。
关于COW，这里举一个AEP的例子。AEP是一种存储介质，这里只需要知道它可以 按字节寻址和 数据在掉电后不消失即可。普通的磁盘，一般有扇区原子性的保证，也就是在将新数据写入某个扇区的途中突然掉电的话，这个扇区上要么完全没有新数据，要么新数据完全被写下去了，不会出现一半新一半旧的状态。扇区原子性的保证很重要，许多数据库都依赖它，然而，AEP这种存储介质没有这种保证，所以需要用软件的方式来做这种保证，称为BTT。
BTT的思路也很简单，为了方便理解，后文我不引入AEP的术语来进行描述。
首先把整个存储空间划分成若干个block，每个block有自己的物理块号，然后再维护一个表来做逻辑块号到物理块号的转换。给上层逻辑块的数量略小于物理块数量，这样就会有一部分的物理块没有被映射，姑且称为free block。
比如下图，4个逻辑块，5个物理块，其中1号块是free block。

接下来，在往一个逻辑块上写数据时，先找一个free block，把数据写上去，接下来去映射表中，将逻辑块的映射修改该free block。整个流程中，最关键的一步——修改映射关系——是原子性的。只要有这个保证，那么就能够提供block数据原子性更新的能力。
COW的思想在很多地方都有，比如qemu的qcow镜像快照，ext4和btrfs在写入数据时的cow，linux内核的rcu机制等等。此外，cow最有名的使用场景莫过于fork的实现了，但是它只是单纯的为了减少拷贝开销，与原子性没有太大关系。

COW优化

cow的方式，有个很麻烦的事情，就是每次都得原子性得去更新指针。那么有没有办法去掉这个指针呢？有的。
这个是在intel关于AEP的文档上学到的另一种取巧的方式（ 注意，下面描述的例子和上文中的BTT没有任何关系）。起因是这样的：
AEP的驱动使用一个称为index block的结构来管理元数据，这个index block处于整个介质的 起始位置，大小至少为256字节。有些操作会去更改它的多个字段的值，所以可能出现更改字段到一半的过程中掉电的情况，因此需要一种机制来 保证更改过程是原子性的。
正常的COW方式，需要在起始位置处保留两个index block大小的空间以及一个指针，其中一个index block作为备用。在修改index block的数据时，以cow的方式将全部的数据存储在备用index block中，然后以COW的方式更改指针指向该备用index block中。
intel使用下面的机制来优化掉指针：
依然是两个index block，index block中有一个称为seq的字段。seq是一个两位的数，共有4个状态。除去00状态，还有01、10、11三个状态，将这三个状态视为一个循环，如下:

为了方便叙述，两个index block分别命名为blockA和blockB。

• 第一次写入数据，写入到blockA中，其上的seq为01；
• 第二次写入数据，写入到blockB中，其上的seq为10；
• 第三次写入数据，写入到blockA中，其上的seq为11；
• 第四次写入数据，写入到blockB中，其上的seq为01；
• …

如此往复，在恢复时，只要读取并比较两个index block上的seq中哪个处于循环的前方，就能找到最新的那个index block。这样的优势是显而易见的，一是避免了额外的指针，或者说把指针固化到两个index block中，避免了一个8字节指针对两个index block对齐带来的麻烦；二是少一次写操作，提升了效率。

多对象

前面针对的都是一个个单个的对象，如果涉及到多个对象，要保证原子性就比较复杂了。比如，如果使用加解锁的方式，就需要注意锁的顺序，防止死锁的问题；如果是cow的方式，就需要注意中途失败以后的把已替换的指针回滚回去的问题。从更大的格局来看，针对多个对象的原子操作，本质上就是进行一次事务操作。所以，这个问题的解法，参考事务的实现就好了。

写日志

事务的四大特征ACID，即原子性，一致性，隔离性和持久性，基本上是一个常识了，而原子性只是事务的一个特性。
写日志算是实现事务最通用的方式了，日志一般分为redo和undo两种日志，为了加快恢复速度，一般还会引入检查点(checkpoint)的概念。在文件系统和数据库的实现中，基本上都能看到事务的身影。
写日志除了能保证原子性和一致性以外，还对磁盘这种外存设备很友好，因为写日志基本上都是顺序的。在这一方面的典型案例，当属日志结构文件系统和leveldb的LSM-tree了。
leveldb的原理想必不用再提了，它把对于K-V对的增删改操作都变成一条条的日志，然后持久化为磁盘上的一个个SST，之后再触发合并整理。这样一来，基本上对于磁盘的所有操作都是顺序的了。
日志结构文件系统也是类似的思想，它将文件数据的增删改操作直接变成日志写到磁盘里面，文件的实际数据不需要单独再存到某个地方，而是靠日志恢复出来。这种做法对写操作是非常友好的，但是读方面的性能就有点差强人意了。

事务内存

事务通常是用于保证持久性数据一致性的。去掉持久性的要求，将事务的概念引入到对于内存对象的操控中，就有了事务内存的概念。
正如上文所说，对于多个对象的操作，加锁和cow的方式，在使用时都比较麻烦。加锁的方式要考虑加解锁顺序防止死锁，中途失败了还要按照特定的顺序解锁回滚；cow也是一样，虽然没有死锁的问题，但是在回滚上也是很麻烦的。另一个问题就是，针对不同的场景，加解锁的顺序要重新考虑，cow的回滚也要重新考虑，不具有通用性。
事务内存机制则是为了解决这些问题而提出的，它把针对多个对象的原子操作抽象为一个事务，只要按照它提供的api，以串行化的思路去编程就行了。不用考虑加解锁的顺序，也不必考虑回滚的问题，在遇到了某些fatal error时只要abort掉事务即可。这是一种通用的并发编程方式，简化编码的同时，还能保证并发的性能。
事实上，事务内存机制的内部实现，也是依赖于cow机制和加解锁来实现的，更深一步，其实也是依赖于原子操作指令的。

总结

总结一下：
16字节或8字节以内的内存数据，使用cpu的原子操作指令；
16字节以上的数据，使用加锁、COW的方式，或者优化过的使用seq的COW方式，本质上还是依赖于原子指令；
针对多个对象的原子操作，引入事务或者事务内存的概念，实际上的实现要么是写日志，要么是依赖于cow或加锁的方式，最终依赖于原子指令。
所以，万变不离其宗，原子操作指令很关键。

参考链接

• https://pmem.io/documents/NVDIMM_Namespace_Spec.pdf
• https://software.intel.com/content/dam/develop/public/us/en/documents/325462-sdm-vol-1-2abcd-3abcd.pdf
• https://zhuanlan.zhihu.com/p/151425608
• https://zh.wikipedia.org/wiki/%E8%BD%AF%E4%BB%B6%E4%BA%8B%E5%8A%A1%E5%86%85%E5%AD%98