本文转载自微信公众号《云点论剑》，作者紫扎。转载本文请联系云顶论剑公众号。前言所谓原子操作，就是要么不做，要么全部做。在很多场景下，都需要原子操作。在翻看aep的spec文档的时候，我也发现了一个巧妙的方法。所以顺便总结一下实现原子操作的各种不同的方法。欢迎交流讨论。Smallgranularity-instructions根据Intel手册第3卷第8章的描述，x86使用三种机制来实现原子操作：1.Guaranteedatomicoperations。Guaranteedatomicoperations是指一些基本的内存读写操作，这些操作是保证原子性的。通常，读取和写入位于高速缓存行中的数据是原子的。2.总线锁定，使用LOCK#信号和命令的锁定前缀。锁定总线的方法很简单。执行原子操作的CPU会在总线上断言LOCK#信号，此时其他CPU的操作将被阻塞。3、缓存锁使用缓存一致性协议（MESI协议）实现。如果要访问的内存区域已经在当前CPU的缓存中，则使用缓存一致性协议实现原子操作，否则总线会被锁死。Intel早期的CPU（如Intel386、Intel486、Pentium处理器）都是通过总线锁实现原子操作的。这种实现的问题在于，两个完全不相关的CPU也会相互竞争总线锁，从而导致整体性能下降。在后来的CPU中，Intel优化了这个问题。当要原子操作的内存已经拉入缓存后，CPU使用缓存一致性协议来保证原子性，称为缓存锁。与总线锁相比，缓存锁的粒度更细，可以获得更好的性能。在x86中，有些指令有锁语义，比如XCHG、更新段描述符等；其他指令可以手动加上lock前缀来实现锁语义，比如BTS、BTR、CMPXCHG指令。在这些指令中，最核心的是CAS（CompareAndSwap）指令，它是实现各种锁语义的核心指令。不同于XCHG自带原子语义，CAS操作是以“锁CMPXCHG”的形式实现的。一般来说，原子操作的数据长度不会超过8字节，不允许同时对两个内存地址进行CAS操作（如果可以的话，无锁双向链表不是梦）。原子操作中另一个绕不开的话题就是ABA问题。水平有限，就不多说了。举个例子，Linux内核的slub实现中，使用了一个宏cmpxchg_double。这不是同时对两个内存地址进行CAS的黑魔法，而是使用CMPXCHG16B指令解决ABA问题的宏函数。有兴趣可以深入研究。大粒度当原子操作的对象大小在16字节或8字节以内时，一条或两条指令即可实现原子操作。但是，当对象的尺寸很大时，就需要其他方法来实现原子操作，比如加锁和COW。仔细观察这两个方法，我们可以发现，本质上，它们还是把问题转化成了一个16字节的原子操作。加锁加锁的方法很好理解。只要加了一把锁，整个临界区的操作就可以看成是一个原子操作。内核中提供了各种锁，如自旋锁、读写锁、seq锁、互斥锁、信号量等，这些锁对于读写者的偏好不同，在是否允许休眠方面也有所区别。简单来说，自旋锁和读写锁的核心就是用原子指令CAS操作一个32位/64位的值。它们不允许休眠，但是读写锁针对读者进行了优化，允许多个读者同时读取数据，而自旋锁对读写操作没有偏向性。seq是基于自旋锁实现的，不允许sleep，但是对写手比较友好。互斥量和信号量也是基于自旋锁实现的，但是它们允许互斥量的操作休眠。可见加锁的核心是使用指令实现原子操作。对大对象进行原子操作的另一种COW方式是COW（copyonwrite）。cow的思路其实很简单。首先，我们有一个指向这个大对象的指针。当我们需要原子修改这个大对象的数据的时候，因为没有办法做就地修改，我们就复制这个对象的数据，复制到对象副本中修改，最后原子修改指向对象的指针.可见这里的核心点是用指令代替指针。关于COW，这里举一个AEP的例子。AEP是一种存储介质，这里只需要知道它可以按字节寻址，掉电后数据不会消失。普通磁盘一般都有扇区原子性保证，即如果在向某个扇区写入新数据的过程中突然断电，该扇区要么根本没有新数据，要么新数据已经全部写完，就不会出现一半新一半旧的状态。扇区原子性的保证非常重要，很多数据库都依赖它。但是AEP等存储介质没有这个保证，所以需要用软件来做这个保证，称为BTT。BTT的思路也很简单。为了方便理解，后面就不引入AEP这个名词来描述了。先把整个存储空间分成几个块，每个块都有自己的物理块号，然后维护一个表，把逻辑块号转换成物理块号。给上层的逻辑块的数量比物理块的数量略少，所以有些物理块不会被映射，称为freeblock。例如下图中，有4个逻辑块和5个物理块，其中块1为空闲块。接下来，在向逻辑块写入数据时，首先找到一个空闲块，写入数据，然后到映射表中修改逻辑块到空闲块的映射。在整个过程中，最关键的一步——修改映射关系——是原子的。只要有这个保证，就可以提供原子更新块数据的能力。很多地方都有COW的思想，比如qemu的qcowimagesnapshot，ext4和btrfs写入数据时的cow，linux内核的rcu机制等等。另外，cow最著名的使用场景是fork的实现，但纯粹是为了减少复制开销，与原子性无关。COW优化牛。还有一个比较麻烦的事情，就是每次Atomic都要更新指针。那么有没有办法去掉这个指针呢？是的。这是从intel关于AEP的文档中学到的另一种tricky方法（注意下面描述的例子与上面的BTT无关）。原因是这样的：AEP驱动使用了一个叫做索引块的结构来管理元数据。该索引块位于整个介质的开头，大小至少为256字节。有些操作会改变多个字段的值，所以可能会在字段改变到一半的时候掉电，所以需要一种机制来保证改变过程是原子的。在普通COW模式下，需要在起始位置预留两个索引块和一个指针的空间，一个索引块作为备用。当修改索引块的数据时，将所有的数据以cow的方式存储在备索引块中，然后通过COW的方式改变指针指向备索引块。Intel使用如下机制来优化指针：仍然有两个索引块，索引块中有一个名为seq的字段。seq是一个两位数，一共有4个状态。除了00状态之外，还有01、10、11三种状态，这三种状态被视为一个循环，如下：为了描述方便，将两个索引块分别命名为blockA和blockB。第一次写入数据，写入blockA，上面的seq为01；第二次写入数据，写入blockB，上面的seq为10；第三次写数据，写到InblockA，上面的seq为11；第四次写入blockB，seq为01；...以此类推，在恢复的时候，只要读取并比较两个索引块中seq中的哪一个在循环前面就可以找到最新的索引块。这样做的好处是显而易见的。一是避免多余的指针，或者将指针固化为两个索引块，避免了用一个8字节指针对齐两个索引块的麻烦；另一种是少写一次。操作，提高效率。多对象针对单个对象。如果涉及到多个对象，保证原子性就比较复杂。比如使用加解锁的方式，需要注意加锁的顺序，防止死锁；如果使用cow的方法，需要注意中途失败后回滚替换指针的问题。从更大的角度看，对多个对象的原子操作本质上是事务操作。所以，这个问题的解决方案就是参考事务的实现。写日志事务的四个ACID特性，即原子性、一致性、隔离性、持久性，基本都是常识，原子性只是事务的一个特性。写日志是最常见的事务实现方式。日志一般分为重做日志和撤销日志。为了加快恢复速度，一般会引入检查点的概念。在文件系统和数据库的实现中，基本上都可以看到事务。写入日志除了保证原子性和一致性外，对于磁盘等外部存储设备也非常友好，因为写入日志基本上是顺序的。这方面的典型案例是日志结构的文件系统和leveldb的LSM-tree。leveldb的原理就不用多说了。它将K-V对的增删改查操作变成单独的日志，然后以SST的形式持久化在磁盘上，再进行合并排序。这样基本上所有对磁盘的操作都是顺序的。日志结构的文件系统也有类似的想法。它直接将文件数据的增删改查操作转化为日志写入磁盘。文件的实际数据不需要单独存放，而是由日志恢复。这种方式对写操作很友好，但是读性能有点差强人意。事务性内存事务通常用于保证持久化数据的一致性。去掉持久化的要求，在内存对象的操作中引入事务的概念，就有了事务内存的概念。上面说了，对于多个对象的操作，locking和cow的方法使用起来比较麻烦。加锁的方式要考虑解锁的顺序，防止死锁。如果中途失败，则必须按特定顺序解锁并回滚；牛也是如此。虽然没有死锁的问题，但是回滚就很麻烦了。还有一个问题就是对于不同的场景，添加和解锁的顺序需要重新考虑，cow的回滚也需要重新考虑，不具有通用性。事务内存机制就是为了解决这些问题而提出的。它将对多个对象的原子操作抽象为一个事务，只需要按照序列化的思想提供的API进行编程即可。不需要考虑添加和解锁的顺序，也不需要考虑回滚的问题，遇到一些致命错误就中止事务即可。这是一种通用的并发编程方式，在保证并发性能的同时简化了编码。事实上，事务内存机制的内部实现也依赖于奶牛机制和加解锁，更进一步，它还依赖于原子操作指令。总结一下：16字节或8字节以内的内存数据，使用CPU原子操作指令；对于16字节以上的数据，使用lock，COW，或者使用seq优化COW，本质上还是依赖原子指令；对于多个对象的原子操作，引入了事务或事务内存的概念。实际实现要么是写日志，要么是靠cow或者加锁的方式，最后还是靠原子指令。因此，所有的变化都保持不变，原子操作指令是关键。参考链接https://pmem.io/documents/NVDIMM_Namespace_Spec.pdfhttps://software.intel.com/content/dam/develop/public/us/en/documents/325462-sdm-vol-1-2abcd-3abcd。pdfhttps://zhuanlan.zhihu.com/p/151425608https://zh.wikipedia.org/wiki/%86%85%E5%AD%9
