软件事务内存STM

我们的统计信息，以及表结构相关的元信息，都用了 copy-on-write 的技巧。 也就是说，相关的修改操作都是基于原子替换。比如说要更新一个 db 下面的一个表，它就是把这个表的信息全部 copy 到一个新对象中，修改新的表，然后原子性地将 db 引用的旧的信息，修改成新的信息。

copy-on-write 对于修改和更新是挺不友好的，之间我就记录过相应的 issue。 随着数据量越来越大，每次做 copy 的时候需要 copy 和新建的数据越来越多，执行过程会越来越慢。

还有另外一个问题就是内存占用，统计信息和表结构信息这类的，如果一直存储在内存中，对于一个非常大的集群比如 PB 级别，然后几十万张表的时候，内存就是一个大问题了。这个问题只有通过 LRU 的方式来解，只缓存最近使用的信息而不是加载全部信息。

统计信息那块使用 LRU 代码我之前大略瞄了几眼的，在并发安全方面是完全不靠谱的。这块实现如果用加锁的方式，是一个粒度很不好控制的事情，全局大锁代码简化了，但是容易数据结构修改过程中，锁阻塞造成请求卡顿，而如果想把粒度做细，代码实在太难了。copy-on-write 实现下，原子修改的好处是，即使拿到一个旧版本的信息，也不会出现卡顿。在数据量不大并且修改不频率的时候，其实是个不错的选择。

我在想还有没有什么办法能处理这里的 copy-on-write 的问题，调研了一下，发现了软件事务内存这个东西 – STM(software transactional memory)。

STM 可以看作是锁，消息传递之外，另一种内存并发安全访问的模式。锁不用说，大家都知道。而消息传递就是像 Erlang / Go 这一类的，"Do not communicate by sharing memory; instead, share memory by communicating" 的模式。在这种模式下比如说，要读写一个对象，应该是给对象所属于的 actor 去发消息，由那个 actor 去操作了返回消息。STM 则是另一个视角，它把 memory 当作像数据库的存储一样的资源，通过事务的方式来访问这种资源。

一旦用这种思维来处理内存，并发就是安全的了。因为事务要么成功，要么失败，不会留下中间状态。事务也不用考虑其它事务的交互，有隔离性的保证，ACID 里面的 I。除了没有 D，STM 对于 ACID 的其它属性都是跟事务一样的。

具体到实现有多种多样的，clojure 语言中是内置了这种支持的，haskell 也有相应的库。我去找了一下 Go 语言的，读到了这篇博客。它是基于 Transactional Locking II (TL2) 这篇论文的，论文我也一并去读了。本来这篇博客是写得挺清楚的，但是作者对原论文的理解有一些错误的地方。我翻了一下作者的那个实现，结果发现问题有点多，我还给他提了好几个 issue 了。看上去这个库对于我理解 STM 有帮助，但是拿来用是别指望了。

最后我自己写了一个，其实代码也就 100 多行的。讲一讲这个算法，以及实现过程中的一些感受和坑。

这个算法中使用一个全局时钟 global version clock，每个读事务在执行前，会取当前的全局时钟，作为事务的 read version。每个写事务，提交时会将全局时钟递增。

每个内存对象，都会绑定一个 versionedWriteLock: 两个信息用一个 uint64 来表示的，1位用于存储当前对象是否被锁住，64位用于表示该对象的版本。

接下来，我分 "读"，"写"，"提交" 三块来讲。

先说"写"操作，写其实最简单。每个事务，会把全部的修改缓存起来，而不是直接修改真实的内存对象。跟我们数据库里面记 log 一样的道理。写会记录修改的内存对象是谁，以及改成什么。直到提交的时候，检查事务无冲突之后，将写操作更新到内存对象上。

然后再看"读"操作。在只读事务里面，读操作就三步:

• 先读取内存对象的 versionedWriteLock 信息
• 读取内存对象的当前的值
• 再次读取内存对象的 versionedWriteLock 信息

我们读 versionedWriteLock 的过程都是原子的。事务启动的时刻，获取过 read version。事务在修改值之前，都会先修改 versionedWriteLock。

• 如果两次的读，读到的 lock 信息都是没有锁标记的，说明整个过程中，并没有事务正在修改这块内存
• 如果，两次读之间，版本信息没有发生变化，说明中间那次读得到的数据是有效的
• 如果 read version 大于等于读到的内存对象的 version，说明获取到的是该内存对象的最新的信息，而不是过时的

以上三点都满足的条件下，这次"读"操作成功。否则，说明可能存在冲突。冲突的情况，我们将整个事务重试，重新取 read version，将操作过程再重放一遍。

读操作有可能由于读到旧的版本(读到这个版本但是这个版本后来被修改过了)，由于正在发生修改(读到锁字段)，以及读到很旧的版本(取了一个 read version，而读到的对象在这个 read version 之后被修改过许多次了)，而重试。

算法的关键主要都集成在 "提交" 上面。事务的执行分为六步：

• 第一步，取 read version
• 第二步，执行 "读" 或 "写" 的业务逻辑，前面已经描述过读和写分别做什么
• 第三步，加锁。从这一步开始，算是进入到事务的提交过程了。对于 write set 中的每个内存对象，将它的 versionedWriteLock 的 lock 标记上。
• 第四步，获取 write version，就是将 global 的 version clock 原子递增，获取最新的值。
• 第五步，重新校验 read set。校验过程是检查 read set 的数据是否被更新过。如果检查失败则重试。
• 第六步，提交和清锁

第三步有可能出现死锁的情况。比如说第一个事务要修改 a b c d，第二个事务要修改 d c b a，然后事务1锁住了 a b，去加锁 c d 的时候卡住了。事务2锁住了 d c，要去加锁 a b 的时候卡住了。处理起来也比较简单，论文中提到，可以通过排序然后按顺序去获取锁的方式避免，不过它说更简单的处理办法是，遇锁冲突之后直接 retry，retry 很多次总能过去的，真过不去我们可以加一个重试的次数上限。

为什么第五步需要重新检验 read set? 因为第三步的加锁过程，整体上它不是一个原子操作。它是对一个个的 write set 中的对象依次加锁的。这样就可能导致写操作所基于的读，不是在由一个时间线上面。我们重新校验一遍 read set 就很好理解，类似于读操作对于单个原子变量的时候：

• 先有一个 read version 下的多个变量的读 (snapshot)
• 基于这个 read version 下的读到的结果，去做写操作，修改
• 再对所有读的对象 validate 一遍

如果能保证 read set 在后面 validate 的那一遍跟前面取 read version 的时候的那一遍，没有发生过变化，但保证了中间那次我们的修改操作是完全基于 read version 时刻对应的 snapshot 的。于是我们最终的提交，就相当两个 snapshot 之间的 CAS 操作，在 read version 时刻的 snapshot，做了涉及多个对象单元的 modification 之后，得到的新的 write version 时刻 snapshot，然后对两个 snapshot 之间 CAS。

如果我把只读事务套进这个提交流程里面，会发现只读事务会在"读"操作时，以及最后的 read set validate 的时候，被处理两次。这里可以优化，不过我们也可以想一想，为什么读事务需要两次 validation? 我觉得可以给出一个解释是这是在两个不同的阶段，需要注意 ABA 问题。也就是说，需要注意前一次检查，跟后一次检查，结果一样的情况下，有可能是没变化过，但是也有可能是变化过多次，又变回来了。

第三步加锁的时候，只锁住了 write set，却没有锁 read set。可以想一想，读到的数据是否需要加锁? 对于这个算法，是不需要加的，是因为后面还有一个 read set 校验那一步。但是对于通用的基于 snapshot 的算法，读是否加锁要考虑到 write skew 的问题。如果不带后面的 read set 重校验，两个事务，一个执行读A写B，另一个执行读B写A，就会出现A和B都写成功了，但是最终结果确不等价于任一种情况的两个事务先后执行，这就是发生了 write skew。

init:   a=1  b=2
txn1:   if (a==1) b=666
txn2:   if (b==2) a=42

write skew result: a=42 b=666

清锁，如果第三步失败的时候，注意不能直接重试，因为已经获取到一部分锁的情况下，必须先释放掉这些锁之后才能重试。更要注意的是，第三步之后已经是持有锁的，所以如果在第五步的重校验 read set 的时候出错，也必须清锁！ 之前看的那个博主实现的库在这里漏掉了，所以它那玩意铁定是不能跑的。

怎么验证我自己写的这个是可以跑的呢? 我加了一些测试 case。比如说转账测试，模拟10个账户，每个账户初始 100 块钱，然后在许多并发下，随机挑两个账户之间执行转账，这样跑许多轮之后，验证最终的所有账户上面的钱的总数是 1000。当然也有更简单的，并发地跑 +1 +1 +1 的操作，跑个 100000 次，最后看结果是不是 100000。还有一个有意思的测试，我模拟了一下并发的往一个堆数据结构里面，写入数据，最后校验一下，在并发写入的情况下，我们最终的结果依然能维持"堆"的属性。反正就 100 来行的代码，代码的测试覆盖率已经是 100% 了的。

即使这样，我还是不放心，于是跑了一个 data race，还真发现了一个好玩的事情。我发现即使算法实现是正确的，它也可以不是 data-race-free 的。或者换一种说法，它有 data race，但是仍然符合正确性预期。让我们分析一下是怎么回事。在读操作里面

	locked, version1 := v.lock.load() // 先读取内存对象的 versionedWriteLock 信息
	val := v.val    // 读取内存对象的当前的值    <-- 读操作
	locked, version2 := v.lock.load() // 再次读取内存对象的 versionedWriteLock 信息

跟事务的提交里面：

	for writeVar, val := range txn.writeSet {
		writeVar.val = val       <-- 写操作
		writeVar.lock.commit(txn.wv)
	}

对于数据字段出现读写冲突了。

这个冲突会被 versionedWriteLock 第二次读取比对时检测到，最终的读操作会重试。也就是说，这一次的 data race 的读写冲突，读到的那值其实不会真正的被使用，所以它其实是安全的。Go 的编译器理解不了这样的场景，当然，我自己也是分析过后才发现，哇，还能这样。

真的想编译器不报这个 data race 也简单，把 val 从 interface{} 改成 atomic.Value 就可以了。