事务，时间戳与混合逻辑时钟

前言

这篇文章接上文mongodb4.0事务实现浅析。 mongo从3.6之后，开始进行WT-TIMESTAMP-PROJ，后续server层引入了带签名的逻辑时钟logic_clock.h。基于逻辑时钟与客户端协同，又实现了因果一致性会话。到4.0，server层的事务框架做了大的改进，Oplog空洞的维护从server层下移到引擎层，并且支持了wt层事务[as-if]提交时间可指定，从而统一了底层快照时间戳与server层OplogTime，使得以OplogTime作为参数直接访问引擎层快照成为可能。而OplogTime本身又由逻辑时钟指定，俨然一套基于逻辑时钟的严密体系。

在这个时间点，虽然Mongo的分布式事务方案还没有公布，但是代码里已经伏线千里。每个mongos节点的逻辑时钟会被客户端传入的afterClusterTime推进(LogicalClock :: advanceClusterTime)，每个mongod节点的逻辑时钟会被mongos传入的clusterTime推进(waitForReadConcern),每个mongod自身也会因为CRUD操作推进逻辑时钟。目前的时钟维护方式使得因果一致性读写成为可能。

目前，mongo进行的这些深层次的改造让人感觉大材小用，基于时间戳的事务不是必须的。但也正因为这种改造如此刻意，我们可以相信，mongo的分布式事务方案是基于混合逻辑时钟的二阶段提交方式, mongo未来可以支持基于逻辑时间戳实现分布式快照读。 在下文中我对mongo的两阶段方案作出了猜想。

4.0引入的若干时间戳及其必要性分析

4.0基于逻辑时钟做事务，其引入了如下几种重要时间戳：

• stableTimestamp
• oldestTimestamp
• allcommittedTimestamp
• oplogReadTimestamp
• commitTimestamp
• clusterTimestamp

stableTimestamp

在上一篇文章中，我们分析过，它是为raft准备的，可以让数据库快速恢复到一个历史快照，“回滚“掉这个时间点之后的已提交事务。wt的实现方式很简单，这个点之后的数据不做checkpoint，仅记录wal。在决定回滚时，恢复到最后一个硬盘快照，丢弃掉wal就可以了。由于wt的架构中没有undolog，所以上述做法几乎是唯一出路了，然而必然的，如果一直不推进stableTimestamp，会对wt的cache造成负担。 然而，由于rocksdb的快照成本比wt低得多(这是为什么呢O(∩_∩)O~)，rocks要实现stableTimestamp的功能会非常简单。 再然而，其实这个时间戳不是必须的。引擎层的参数设置为supportsRecoverToStableTimestamp = false，可以走3.x系列的回滚方式。

commitTimestamp

我们知道，oplogTime是在事务提交前分配好的，不同事务的oplogTime必然和提交顺序无法对应。mongo为了屏蔽掉引擎层的提交时间的顺序差异，在事务提交前，可以配置任意一个事务的commitTimestamp，让它 仿佛[as-if]是在oplogTime被提交的。 这个仿佛是什么意思呢，对于一个封闭系统，观测是了解它的唯一方式，对于数据库来说，对它的读写就是观测，读到的值就是观测的结果。在mongo4.0-wt3.0之后，时间戳即快照，我们可以设定某个事务的commitTimestamp为未来的某个时间点，当该事务在现实中提交了之后，我们以当前wallclock时间戳去读它时，是读不到的。

allcommittedTimestamp

与oplogReadTimestamp

由于多个事务之间是并发的，事务的开始时间与事务的结束时间不满足相同的顺序关系。

以事务的开始时间为基准，活跃事务链表中，就存在着commitTimestamp空洞。这些空洞反映了事务的wallclock提交时间与事务的commitTimestamp的差异。

我们定义allcommittedTimestamp为最大的使得之前没有（比自己的commitTimestamp更小的未提交事务）的commitTimestamp。

• After(C1)， AC1，AC2，AC3是空洞，allcommittedTimestamp=uninited
• After(C2) , AC2, AC3是空洞，allcommittedTimestamp=AC1
• After(C3)， AC2是空洞 , allcommittedTimestamp=AC1
• After(C4)，无空洞，allcommittedTimestamp=AC1

oplogReadTimestamp由后台_oplogJournalThreadLoop定期从wt层的allcommittedTimestamp同步，可以理解为它们是同一个东西，只是oplogReadTimestamp的实时性更弱。oplogReadTimestamp是server层oplog-cursor的一个read barrier。任何对oplog的访问不允许越过这道屏障，因为屏障后面是oplog空洞，是尚未准备好的数据，跳过空洞同步oplog会使得主从数据不一致。

oldestTimestamp

小于它的时间戳才可被清理，某个时间戳的数据被清理后，就读不到了。由mongo层传给wt层，当某个时间戳之前再无pinning之上的事务时，就应该被清理。oldestTimestamp一直不推进同样会对wt的lookasidetable(这是啥O(∩_∩)O)以及缓存带来压力。

clusterTime与因果一致性

因果一致性

mongodb3.6及之后的版本，引入了因果一致性的保证。因果一致性中，有一个最重要的要素如下：

ReadOwnWrites

考虑同一个(单线程的)客户端对同一个key x的读写序列 [W(x), R(x)]。 R(x) 一定能读到W(x)的结果。 在Mongodb复制集的语境下，解释一下上面这段话。

读写序列 W(x), R(x)表示 W(x) happens before R(x) happens before指的是在在同一个客户端下的两个操作，前一个操作返回结果了，后一个操作才开始。

W(x) 一定是在主节点上执行，但是mongo是基于raft的复制集。R(x) 不一定在主上执行，可以在任意一个从节点上执行。

Mongo的官方手册显示：

即官方保证，当客户端同时设置双majority时，就可以保证图中因果一致性四要素。 如果我们仔细想想，会发现，仅靠客户端设置双majority，是无法保证readOwnWrites的。举例如下：

在双majority下，client成功设置了x=3，接着在S1上读x的值，依然是2。其原因在于，readMajority并不是广播式读大多数节点，而是基于本地的一个RaftCommitPoint的旧快照进行本地读。

难道是官方错了

官方文档是没错的，只是我们遗漏了参数。（自3.6之后），mongo的每次操作，都会带上clusterTime返回，而开启了因果一致性session功能的driver在每次请求服务端时，会带上afterClusterTime参数，该参数就是服务端上一次操作返回的clusterTime。这种情况下，读操作的readConcern，既包含majority，又包含afterClusterTime。服务端需要等到oplog向前推进到同时满足这两个条件后，才会给客户端返回值。这部分逻辑，参考

read_concern.cpp::waitForReadConcern。

时间戳-以Reader的视角来看

上面我们分析了mongo的server层和引擎层维护的若干时间戳。时间戳的维护目的，是让事务来读的。因此我们再来从reader的视角来看时间戳 mongo提供了如下几种readSource：

• kUnset/kNoTimestamp
• kMajorityCommitted
• kLastApplied
• kLastAppliedSnapshot
• kAllCommittedSnapshot
• kProvided

kMajorityCommitted

这个是最经典的了，本地维护的被raft提交后的时间戳，readConcern=Majority会读这个时间戳。

kLastApplied/kLastAppliedSnapshot

kLastApplied是基于本地写入的带有最大的oplog(或者说是commitTimestamp，一个意思)的记录对应的时间戳，每次新写入都会更新该值。这是读主/从的默认readConcern=local的实现方式。根据上文的分析，kLastApplied之前有可能有空洞。而kLastAppliedSnapshot与kLastApplied的区别仅仅在于，当操作被yield出去再回来后，是从yield之前记录的时间戳读，还是从最新的lastApplied oplog对应的时间戳读。 mongodb的yield机制请参考这一篇文章。由于空洞的存在，以这两种读方式会产生幻读。

kAllCommittedSnapshot

上文我们描述过allcommittedTimestamp的概念。mongodb4.0多文档事务提供SI（快照隔离），其保证幻读的机制就是以allcommittedTimestamp作为readSource，不会像kLastApplied产生幻读。

kUnset/kNoTimestamp

oplog的tailCursor默认以这种方式读，mongo会以oplogReadTimestamp作为readSource，保证不读到空洞。

kProvided

以上层(mongos层)指定的时间戳进行读，使用场景有待探究。

逻辑时钟

下面的内容，假设大家都已经充分具备hlc(混合逻辑时钟)的相关知识。 上面我们说过，clusterTime会返回给driver，客户端服务端通过协同clusterTime的方式实现因果一致性。那么clusterTime不被客户端篡改就变得尤为必要。

hlc在mongo中是一个64bit的整数。前32位是秒级时间戳，后32位是counter。

逻辑时钟篡改带来的问题

根据hlc的定义，当节点接收到请求时，要更新本地lc。

• local.hlc = max(local.hlc, (local.wallclock,0), request.clusterTime)

本地节点在分配lc时

• local.hlc = local.wallclock > local.hlc.clock ? hlc(local.wallclock, 0) : hlc(local.hlc.clock, local.hlc.count+1)

如果request.clusterTime并不是服务端签发的，被篡改了为一个很大的值，会导致本节点逻辑时钟的clock时钟得不到更新，最终32位的count被用尽。

mongo对签发给客户端的clusterTime做了签名验证避免这个问题，签名的轮转秘钥在admin.system.keys表中。

对mongo分布式事务方案的大胆预测

混合逻辑时钟的更新规则，上面已经清楚了。这么做的目的，是在没有全局授时的情况下，维护不同节点之上逻辑时钟的happens before关系。在4.0版本的mongos和mongod上，均会接受请求中的clusterTime，来更新本地的逻辑时钟，本文中上面分析的因果一致性读写，也是依赖混合逻辑时钟来做的。 然而，mongo4.0基于逻辑时钟做事务的最终目的，可不仅仅如此，所有这一些，都是为了分布式事务铺路的，值此mongodb分布式事务的实现尚未公布之际，我们完全可以通过mongo层已有的代码来推断mongo后续分布式事务的框架，即基于混合逻辑时钟的二阶段提交。 首先我们可以提出一个假设，mongo后续的分布式事务方案中，同一个事务在不同节点的写入的oplogTime是相同的。 这个假设合情合理，这是基于逻辑时间戳的分布式快照读的必要条件。 基于这个假设，我们很容易推断出hlc是如何与二阶段提交结合的：

• prepare.1，商量出所有参与节点中最大的逻辑时钟作为TheTs
• prepare.2，以TheTs更新协调者(mongos)的逻辑时钟
• commit.1，以TheTs更新mongod的逻辑时钟
• commit.2，以TheTs作为本次事务每个节点的OplogTime进行提交操作

数据库系统，仅仅考虑写，意义不大，只有考虑读写的关系，才会产生若干变化。同样的，上述的两阶段提交，在prepare阶段协商出hlc做提交时间戳的目的，不在于写，而在于让任意一个逻辑时钟都具备全局的比较基准，从而使得基于时间戳的分布式快照读成为可能！

孔德雨