上文中我们介绍了GSI的基本概念，WiredTiger在不使用timestampAPI时，实现了CSI。它的冲突检测算法如下：

Transaction's localView
Transaction -> {
    // Global monotonicly increasing id, allocated when transaction starts.
    txnId: int
    // The local view of the global transaction list.
    snapshots: []int
}

Global Transaction List
GTL -> {
    // used for allocating one txn's txnId
	txnIdAllocator: atomic<int>
// uncommitted transactions
	activeTxns: List<Transaction*>
// protect GTL from concurrent visit
	rwlock: RwLock
}

Transaction's mvcc prodecure
 Begin -> {
     With(GTL.rwlock.wlock()) {
         txn = Transaction {
             txnId: GTL.txnIdAllocator++
              snapshots: GTL.activeTxns.copy()
         }
         GTL.activeTxns.add(txn)
     }
     // txns are naturalled sorted in this way.
}

 Update(key, value)-> {
// get the updatelist of a key from the btree
// pick its header
    upd = GetUpdateList(key).header
    if (upd.txnId > self.snapshots.back()) {
        throw Conflict
    }
    if (txn.snapshots.find(upd.txnId) {
        throw Conflict
    }
    GetUpdateList(key).insertAtFront({self.txnId, value})
}

 Commit -> {
     With(GTL.rwlock.wlock()) {
        GTL.activeTxns.remove(self)
     }
}

• 在事务开始时，对将全局未提交的事务id copy 到事务的localView中的snapshots链表中。

• 采用firstUpdateWin的冲突检测策略，在更新记录时如果违背SI，当且仅当：

• 如果key的mvcc链头的txnId 大于localView的snapshots中的最大值，

• 如果key的mvcc链头的txnId在本事务的localView的snapshots

• 上述规则是经典的CSI的实现，在PG中也是类似的做法，正确性证明请见这篇文章

  
  

WiredTiger中引入readTimestamp和commitTimestamp，readTimestamp即GSI中的snapshotTimestamp。

Transaction -> {
    // Global monotonicly increasing id, allocated when transaction starts.
    txnId: int
    // The local view of the global transaction list.
    snapshots: []int
    read_timestamp: int
    commit_timestamp: int
}

相应的冲突检测判断部分，也引入了GSI的规则

• 即本事务的read_timestamp 小于已提交key的commit_timestamp 即认为违背GSI

• 这里默认本事务的commit_timestamp 一定大于key的mvcc链中的最大的commit_timestamp，即对于某个特定的key，该key的commit_timestamp的顺序一定要和物理提交顺序一致，这是由application-level（mongoServer层）保证的，那么Mongo层是如何保证这一点的呢，请继续往下看。

 Update(key, value)-> {
 	// get the updatelist of a key from the btree
 	// pick its header
    upd = GetUpdateList(key).header
    if (upd.txnId > self.snapshots.back()) {
        throw Conflict
    }
    if (txn.snapshots.find(upd.txnId) {
        throw Conflict
    }
    if (txn.read_timestamp < upd.commit_timetamp) {
        throw Conflict
    }
    GetUpdateList(key).insertAtFront({self.txnId, value})
 }

MongoDB从节点拉取主节点的Oplog来实现复制，主节点上的Oplog是并行提交的，因此在Oplog的末尾存在(时间上的)乱序。如果不屏蔽乱序的话，从节点读到的Oplog就会产生空洞。举个例子：

T0: txn1.start(); txn1.setCommitTimestamp(1)
T1: txn2.start(); txn2.setCommitTimestamp(2)
T2: txn3.start(); txn3.setCommitTimestamp(3)
T3: txn3.commit()  // local.oplog.rs: [3]
T4: txn1.commit()  // local.oplog.rs: [1,3]
T5: txn2.commit()  // local.oplog.rs: [1,2,3]

从空间上来讲，oplog的顺序就是事务的commitTimestamp顺序，即[1,2,3]的顺序。但是从时间上来讲，物理提交顺序不可控，尽管三条oplog最终会生成，但是不同时间点看到的oplog，是有空洞的。比如T4时刻的oplog是[1,3]，如果从节点此刻去遍历Oplog，就会丢失commitTimetamp=2的记录。

从本质上讲，所谓前缀一致的复制，指的是，如果我读到了某条commitTimestamp = X的数据，就不允许在我读这条数据后，对数据库做出commitTimestamp < X的更改。因此，不难想到我们可以维护一个最大的没有空洞的commitTimestamp，叫做AllCommitTimestamp, 形式化的定义如下， 也就是GSI读规则的第4点，描述了不会出现空洞：

上面我们分析过，事务有commitTimestamp属性。

在wiredTiger中，事务被按照commitTimestamp排序，即

TAILQ_HEAD(__wt_txn_cts_qh, __wt_txn) commit_timestamph;

我们知道，事务开始和设置commitTimestamp不在一个临界区中，因此事务的txnId的顺序和事务的commitTimestamp顺序并不完全一样，这也是为什么wiredTiger除了维护全局的active_transaction_list这个活跃事务链之外，还维护了一个commit_timestamph的队列。active_transaction_list可以看作按照txnId有序的队列，commit_timestamph可以看作按照commitTimestamp有序的队列。commit_timestamph 队列可以用来辅助AllCommitTimestamp的计算。相关伪代码如下：

for (auto v : commit_timestamph) {
  if (v.committed || v.rollbacked) {
    continue;
  }
  return v.commit_timestamp - 1;
}

根据上述伪代码，wiredTiger中，从左往右遍历commit_timestamph队列，找到第一个没有提交的事务T，allCommitTimestamp = T.commitTimestamp - 1; 这也很容易理解，T为commitTimestamp最小的未提交事务，那么比它更小的commitTimestamp所属的事务必然都已经提交了。这里有个假设，对commit_timestamph的插入操作必然都是插入到末尾，换句话说，commitTimestamp的分配必然是递增的，这一点是由application-level(mongodb-server层)保证的，那么Mongo层是如何保证这一点的呢，请继续往下看。

MongoDB用来做复制的，读oplog的读事务，它的readTimestamp由AllCommitTimestamp得到，因此能够做到前缀一致的复制。

上面我们留了两个遗留问题

1. Mongo如何做到对于某个特定的key，该key的commit_timestamp的顺序和物理提交顺序一致

2. Mongo如何做到对commit_timestamph的插入操作必然都是插入到末尾，换句话说，commitTimestamp的分配必然是递增的

这两个问题，是wiredTiger不做任何保证的，如果违背了，数据就错乱了。MongoDB的同一段代码保证了上述两点，或者说，上述问题其实是一个问题。就是所谓的PBMA策略

 1. // the global timestamp allocator
 2. GTA -> {
 3.     lock     Lock
 4.     globalTs int
 5. }
  
 6. // the timestamp allocation prodecure
 7. Transaction txn
 8. txn.Begin()
 9. with(GTA.lock) {
10.      txn.setCommitTimestamp(globalTs++)
11. }
12. ......
13. txn.Commit()

PBMA策略的关键要素是

• 事务先开始，再分配提交时间戳

• 分配提交时间戳要保证全局递增（加锁）

PBMA为何能一箭双雕的保证上面两个遗留问题呢，正确性的证明在这里

• 简单的说，对于某个特定的key，如果有两个事务都在修改， 那么根据事务冲突的规则可知， 这两个事务，一定是一个提交后，一个才开始的，满足 commit(Ti) < snapshot(Tj)的关系，对于本事务，也满足 snapshot(Tj) < commit(Tj) 的关系， 那么可知， commit(Ti) 是小于 commit(Tj)的， 即commit 顺序跟物理顺序相一致。

上面介绍了MongoDB副本集系统跟4.0的时间戳的一些实现， 底下我们需要了解一下在MongoDB 4.2 的分布式事务又是如何使用时间戳来实现的。

分布式系统，各个节点时钟的是不一致：

1，分布式各节点，时钟不一致，会导致分布式事务，无法定序。

2，对于分布式系统，一般都有时钟同步服务来保证各个节点的时间一致性。

3，但是即使存在时钟同步服务，任一时间点的绝对一致是很难达到的。这对于分布式系统来说，是不可依赖的。

4，分布式事务处理，如果不想为节点时间差专门去做逻辑处理，则需要基于一个稳定一致的时钟系统。— 即：逻辑时钟。

从3.6之后，MongoDB就引入了HLC的概念，在实现上的体现是，Mongos/Mongod的每次操作都会带ClusterTime，ClusterTime也作为Mongos和Client交互传递的Token。HLC在MongoDB中的体现在以下几点：

• ClusterTime在Client/Mongos/Mongod的所有操作(读/写/命令)之间传递，每个进程收到更大的ClusterTime后就更新本地的ClusterTime。

• Mongod侧，Oplog的分配与物理时间的递增会作为ClusterTime推进的驱动力。

• Mongos/Mongod侧，物理时间的偏斜会作为ClusterTime推进的驱动力。

• ClusterTime传递给Client时是被签名的，以防止被篡改使得Server端的ClusterTime无限制变大。Client本身只传递不推进ClusterTime。

相关代码在 logical_clock.h::advanceClusterTime，mongos和mongod在rpc的处理函数处均有调用。

void processCommandMetadata {
    return logicalClock->advanceClusterTime(signedTime.getTime());
}

通过上述HLC的机制，mongos/mongod各个进程之间的物理时钟不需要协调，集群的ClusterTime会随着mongos/mongod/configsvr的每次交互相互接近。如果没有HLC机制，各个shard之间的写操作的OplogTime相互独立，各个shard上的oplogTime没有totalOrder，全局的ChangeStream就无法实现。

MongoDB的2PC和CLOCK-SI paper中的算法非常接近（由于官方并未明确说明，因此并不可以说，MongoDB的2PC是对CLOCK-SI paper的实现）。MongoDB的分布式事务流程介绍可以参考这篇文章

CLOCK-SI

• 分布式系统中，考虑到多事务并发，对每个单个事务的开始时间是严格要求的，只有在不同节点上的单个事务都在同一个时间戳开始执行，那么多个事务在每个节点上的顺序才是一致的。考虑到分布式系统会有 clock skew (时钟偏斜) 的场景， 我们就需要在其他节点等待时间流逝到这个时间，才可以开始执行， 如下图所示:

  

  
  

• 上图中事务 T1，因为在P1节点是在 t时刻开始的， 所以在事务在 P2节点运行时，也需要等到t时刻才能运行， 如上图所示 P2 节点时间早于P1节点， 那么事务在P2节点，就需要等这个延迟时间。这样会造成事务执行过程中的延迟的增大。

• CLOCK-SI就是为了提出了一个方法，用来解决上面事务执行过程中的延迟问题的,

  读规则如下

  

  
  

• CLOCK-SI 的读规则提供了一个多分区情况下的一致的snapshot， 主要有两点

  
  

• 1> 如何设置事务T的SnapshotTime

• 2> 如何延迟读操作知道每个节点都有一个一致的snapshot

  
  

• 第2行，表示我们可以将snapshotTime适当的向前调整，这样，可以减少这个事务在远端节点的等待时间， 远端节点等待操作，见 第 21 和 22 行。

• 第7-9行， 如果查看的oid，发现是事务T’修改的，且T’事务正在提交，并且T’事务的提交时间小于事务T(对事物T可见的话)， 那么应该等到T’提交成功后，再读取。

  
  

• 因为 commiting 也可能会提交失败， 所以事务T不能直接读取；

• 因为 已经判断了，T’ 对事务T可见，所以事务T不能忽略。

• 综上所述，事务T的读操作只能等待。

  
  

• 第 11- 15行， 与上面类似，如果 T’ 已经 prepared，且 T’ 对事务T可见，那么 读操作需要等待到T’成功提交后，再读取。原因与上面描述类似

• 21-22 行， 规定了读请求在每个节点上，都需要等到远端物理时钟到了后，才可执行。

  
  

写规则如下






• 写规则针对事务是单点的，还是跨节点的，又分为 local commit, 和 distributed commit

• 采取两阶段的提交方式

• 先发送 prepare T 请求到所有事务参与节点

• 等待所有事务参与节点返回 T 事务已经被 prepared的结果

• 设置T 状态为 commiting状态

• 选取最大的 prepare timestamps 作为 commit timestamp, 并分配给事务T

• 记录事务T的提交时间和提交决策

• 设置事务T为commited状态

• 将 commit T 发送给所有事务参与节点

• 事务参与节点，一旦收到 prepare T的请求，

• 检查 事务 T 在本节点是否可以被修改

• 记录事务的写操作结果和协调者的id

• 将事务T状态设置为 prepared

• 设置T.prepared 时间为本地时间

• 发送 T 事务已经prepared成功的信息给事务T的协调者

• 事务参与节点, 收到 commit T的消息后

• 记录事务T 的commitTime

• 将事务T 设置为 commited 状态

  
  

• 可以看出，CLOCK-SI中明确定义了， 当分布式事务处于Prepare 状态时， 如果其他读事务可以看见这个 Prepare， 那么需要等到分布式事务状态变为提交后，才可以继续执行。这对应到 mongodb 4.2 代码中，在wt的 当读事务 碰到了 正在 Prepare的事务，会返回一个 WT_PREPARE_CONFLICT 来表示当前并不是一个合适时机， 我们需要等到这个写事务完成。

• 而上层的MongoDB如果碰到 WT_PREPARE_CONFLICT， 则会等待事务提交后，继续尝试读取，

  int ret = wiredTigerPrepareConflictRetry(opCtx, [&] { return c->search(c); });
  

• 所有对底层 cursor的遍历和查询操作，都会被封装到 wiredTigerPrepareConflictRetry 函数中， wiredTigerPrepareConflictRetry 会根据传入的函数对象的执行结果进行retry，

  
  

• 如果返回结果不是 WT_PREPARE_CONFLICT， 那么 wiredTigerPrepareConflictRetry 直接返回，

• 如果返回对象是 wiredTigerPrepareConflictRetry， 那么会下一次有事务提交或者abort时，再次调用函数对象检查一次。

  
  

• 更多关于 WT 层修改，参考这篇文章

为什么 commitTs=max{prepareTs}

首先我们需要明确的是，分布式事务哪怕在多个节点运行，最终的 commit timestamp 只能有一个。

因为 commit timestamp 必须大于 prepare timestamp， 所以 commitTs=max{prepareTs} 是一个合理的规定。

如果不认同上面规则， 认为 commit timestamp 可以小于某个节点的 prepare timestamp， 那会违反事务的原子性要求的，

举例如下:

• prepareTs(P1, T1) = commitTs(T1) < snapshotTs(T2) < prepareTs(P2, T1)

那么T2事务在节点1，可以看见T1的修改，但是在节点2， 是看不到 T1修改的， 这就违背了 事务的原子性的要求。