事务性内存
“免费午餐”的消失和事务性内存的出现
事务性内存(Transactional Memory, 以下简称TM)试图以不(让编程者)加锁的方式解决并发问题。TM 的基本思路就是将程序视作读取和修改内存的事物,直接并发运行,利用冲突检测机制对可能发生的错误进行检测和修复。
随着多核架构的出现和普及,“免费午餐”不再有了,如果程序员想要利用好硬件性能的提升,就必须编写并行程序。然而编写并行程序并不像将程序复制一个新的备份一样简单,如何保证程序能够并行访问共享内存并且不出现错误是一个难题。
传统的解决办法就是锁机制。对临界区进行加锁,保证不会出现同时访问共享内存的情况,就破除了并发问题的“同时”因素。锁机制固然直白,带来的挑战也是巨大的。不恰当的加锁可能导致程序陷入死锁,乃至一系列问题。如果简单的加粗粒度锁,就无法从核心数量的进一步增加中获益(称作不可伸缩性)。如果希望程序正确而且可伸缩,就必须精细的添加细粒度锁,这对于程序员来说无疑是一个非常大的挑战,也是非常复杂的工作。
于是事务性内存便应运而生。事务一词从数据库的概念中借得,事务具有四点性质,被称作 ACID。
Atomic: 原子性,一个事务要么完全发生作用,要么完全没有作用。
Consistency: 一致性,事务执行前后系统能够保持正确的状态。
Isolation: 隔离性,事务之间相互隔离,在事务提交之前,事务内部的内存在外面是看不见的。
Durability: 持续性,保证事务提交后对于系统的持续影响。
ACID 大大简化了程序分析,在保证 ACID 的情况下,并行程序可能导致的一切并发问题都不复存在。原子性保证了类似普京打铁的问题不会出现,一致性保证了程序的正确性,隔离性延续了计算机中进程之间的隔离,持续性保证了程序对于内存的修改可以保存。而获得这些梦寐以求的性质只需要在原本的代码外加上一层诸如 atomic{} 之类的代码就可以完成。
可以看到,相比于锁机制,事务性内存更加易于使用,错误的处理更加简单。不仅如此,TM 保持了程序的可伸缩性和组合型,既保证了程序对于核心数的充分利用,也保证了程序进行组合后仍然保持这种性质。
实现事务性内存的两个关键
然而问题没有被解决,只是被转移给了语言层面和硬件。实现 TM 的两个关键就是数据版本化控制和冲突检测。数据版本化是为了破坏并发问题的“共享”条件,每个事务对于内存的修改都会创建一个新的数据版本。
数据版本维护
对于数据版本的维护有 eager 和 lazy 两种方法。顾名思义,eager versioning 会将写操作马上写入新版本,并将旧版本的数据缓存下来,如果事务退回,就将旧版本回复。与之相反的,lazy versioning 会将所有新版本的数据缓存知道事务结束,如果事务成功提交,就将缓存中的数据写入内存。内存的版本维护可以和 git 的版本维护类比,每个事务都可能开出一个新的分支,从而形成一个树状的结构,然后再收束成一个分支,完成开发。而对于 eager 和 lazy 两种方法的描述可以看出各个方法对于事务回退量的预估是不同的,这也引发我思考是不是可以像 CPU 的设计一样,进行类似分支预测的操作,选择当前事务的版本维护方法。
冲突检测
正如上面所述,可以把数据版本的维护看成是 git 的版本维护,那么想要完成开发,就需要合并所有的分支,而对分支的合并,冲突是在所难免的。显然程序运行中手动选择“采用当前修改”,“采用传入修改”,所以就需要对一些事务进行打回,也就是冲突检测。
冲突检测的关键在于追踪事务的读取和修改的内存集合。冲突检测可以分成两种:乐观(延迟)或悲观(及时)的冲突检测。乐观的冲突检测认为回退很少发生,所以仅仅再事务结束准备提交的时候进行冲突检测。虽然检测次数较少,但是可能导致大量事务的回退,并且和 eager versioning 不兼容。悲观的冲突检测认为回退经常发生,所以需要再每次事务进行读或写操作的时候进行检测,优点是亡羊补牢,为时不晚,缺点是可能会出现循环冲突导致所有的事务都不能提交(在乐观的冲突检测中是能够确保有一个版本可以提交成功的)。
由于乐观的冲突检测和 eager versioning 不兼容,所以如果还想搞分支预测那一套就只能选择 lazy versioning了。
TM 可能的组合一共有 3 种,如何进行选择也许不仅仅从语言设计者的层面(分支预测类似的机制),也可以交给程序的编写者来选择,这又是一个机制与策略分离的方向,语言设计者提供了三种机制,由程序编写者自行选择组合。当然这只是我的想法,可能这三种机制根本不能被混用
与锁相似的,冲突检测也存在粒度的选择,分别有对象级,单元级,cache 级。只有对象级是语言层的处理方法,虽然更加靠近编程者的逻辑,但会导致错误检测到冲突。单元级能够有效减少错误检测,但是需要更多的空间和时间。cache 级在两种方法中做了折中。
可以看到,虽然 TM 的构想非常美好,实际上执行起来没有那么简单,不存在一个完美的方法保证性能,完美性和简便,实际使用中还需要对这些方面进行考量做出抉择,正所谓“没有银弹”。
事务性内存的实现
TM 可以分成 STM 和 HTM 两大类。
STM(s 指 Software)通过软件来实现 TM,采用读/写屏障来实现 TM 中共享内存的读和写。具体做法是在代码中加入 stmStart() 和 stmCommit() 表示事务的开始和提交,stmRead() 和 stmWrite() 函数代替对内存的直接访问。这两个函数的内部实现也是通过加锁完成的,相比直接用锁优势仅仅在于采取了数据版本化所以事务回退时回复更加方便。为此付出的代价也是巨大的,比传统方法会有40%~50%的额外成本,如果需要保持隔离性会更高。
HTM(h 指 Hardware)利用了 cache 的层次结构,每个 cache line 都维护了两个 bit 用来表示是否被当前事务读/写。对于 eager versioning,在第一次写时会将地址写入 undo log 以备回退时回复数据。对于 lazy versioning,写入时修改缓存中对应地址的 W bit,如果事务回退,通过将所有 W bit 为 1 的 cache line 舍弃来缓存清空。
总结
事务性内存作为锁机制的一个替代品,能够有效简化并行程序的编写。但是付出的代价就是硬件方面的改变和性能的下降,在实际中仍然需要对这些方面进行折中。