开发者小助手 2020-12-03 202浏览量
作者 | 子札
来源 | 云巅论剑
所谓原子操作,就是要么不做,要么全做。在很多场景中,都有对原子操作的需求。在翻 aep 的 spec 文档时,也发现了一个巧妙的方法。所以顺便发散性地总结一下各种实现原子操作的方法,欢迎大家交流探讨。
根据 intel 手册卷三第八章的描述,x86 使用三种机制来实现原子操作:
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(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 的方式,有个很麻烦的事情,就是每次都得原子性的去更新指针。那么有没有办法去掉这个指针呢?有的。
这个是在 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://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
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
凌云时刻签约作者是为阿里经济体内云布道师在技术文章、图书出版、视频作品等培养优秀人才的通道,通过报名和审核的方式,加入凌云时刻成为签约作者,持续为布道的道路上答疑解惑、技术传承而提供好内容。