本文转载自微信公众号「云巅论剑」,作者子札。转载本文请联系云巅论剑公众号。
前言
所谓原子操作,就是要么不做,要么全做。在很多场景中,都有对原子操作的需求。在翻aep的spec文档时,也发现了一个巧妙的方法。所以顺便发散性地总结一下各种实现原子操作的方法,欢迎大家交流探讨。
小粒度——指令
根据intel手册卷三第八章的描述,x86使用三种机制来实现原子操作:
Guaranteed atomic operations。Guaranteed atomic operations是指一些基本的读写内存操作,这些操作都是保证原子性的。一般来说,读写位于一个cache line中的数据是原子性的。
bus lock,使用LOCK#信号和指令的lock前缀。锁总线的方式很简单,进行原子操作的cpu会在bus上assert一个LOCK#信号,此时其他cpu的操作都会被block住。
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