简单解释Spanner的TrueTime在分布式事务中的作用

问题：

1. 分布式环境里，我们无法保证不同机器的时钟总是具有相同的值（由于温度湿度等因素，有些机器的时间走的快或慢）。比如两台机器A和B，他们的时钟差500毫秒。
2. 当使用时间戳来记录事务(transaction)的commit时间的话，我们需要保证同一个partition的前后两个transaction：Tx1和Tx2，Tx2的commit时间戳比Tx1大。

看一个例子：

假设我们有3个partition，自上而下我们称其为A,B,C，为了简化问题A，B，C各自有一个值可以更改，分别在3台机器上（出于简化问题我们不考虑一个partition其实是一个paxos机群，出于简化问题，我们考虑通信瞬间完成，即使这样，我们可以看到分布式事务的时钟偏移都会造成问题）

我们假设C有准确的真实时间。

先看Tx1的蓝色图：

在真实时间50的时候，Tx1发生，Tx1是跨A和C的事务，把A的值update为a，把C的值update为x， 分布式事务里，需要一个coordinator收集参加事务的partition的时间戳，假设它得到A的时间戳为104， C的时间戳为50，由于我们只能选一个时间戳来做整个事务的commit时间戳，假设我们总是选大的为commit时间戳(Spanner就是选大的，为了篇幅这里不解释为什么了)。则Tx1的commit时间戳为104；那么C记录下x这个值具有104的时间戳。

再看Tx2的红色图：

10个单位时间之后，Tx2发生在真实时间60，Tx2是跨B和C的事务，把B的值update为b，把C的值update成y，C的时间戳已经进步到60， 而如果B此刻的时间戳为100，根据选大时间戳原则，Tx2的commit时间戳为100. 那么C记录下y这个值具有100的时间戳。

可以看出Tx1发生在Tx2 之前，它的时间戳反而比Tx2要大。当有人读C的值时，会读到x而不是y，因为x看起来比y要新。而实际上y比x新，决定正确的新/老值是分布式数据库必须解决的问题。

Spanner的TrueTime和Commit Wait

Spanner的TrueTime利用原子钟(和标配的石英钟相比非常昂贵)，保证了机群里的任意机器的时间戳差距不会超过一个上限值：ε，且当coordinator选择好时间戳之后，会等待一个ε的时间才告诉参与transaction的partition这个时间戳来commit。

我们假设ε=60个单位时间再来看上图：

• Tx1照常不变，但是coordinator在选择了104作为Tx1 的时间戳之后，要等待60个单位时间。
• 在这60个单位时间里，由于写锁，C不能接受任何新的transaction。
• 60个单位时间过去，Coordinator广播Tx1 commit结束，Tx1的时间戳为104。C接到Tx1 commit的信息，解除写锁，C此时的本地时间变成110。记录x的时间戳为104.
• 由于C的写锁，在Tx1之后发生的Tx2快也只能在真实时间110发生，此时Coordinator收集B和C关于Tx2的时间戳，C的时间戳为110。由于我们总是选大参与事务的时间戳，可以看到不管B的时间戳是什么，我们都保证Tx2的时间戳不会小于110，这样y的时间戳必定大于110，也必定大于在Tx1里C写入的x的时间戳104.

这样：我们就保证了有交集的两个transaction，先发生的Transaction，无论有多少个参与Transaction的partition，无论他们的本地时钟如何偏移，只要他们之间的差不超过ε，且coordinator总是等待ε的时间才通知所有参与事务的partition: "事务commit结束"。那么后发生的Transaction的时间戳必定比先发生的Transaction的时间戳大。 而数据库就可以利用时间戳来判断那个值是新值了。

同时可以看到，Spanner由于commit等待，ε越大，写的latency越高，throughput越低。

总结和拓展思考

Spanner的TrueTime的本质是(给我自己看的用来迅速回忆的简述)

1. 原子钟保证机器间的时间差不超过ε

2. Coordinator选完commit时间戳之后等待ε的时间才广播commit，这样保证所有参加此事务的partition的本地时钟已经超过commit时间戳的值(由于1. 所有机器的本地时间不小于commit时间戳减去ε),所以任何有这些partition参与的，任何之后发生的新transaction的commit时间戳，必大于之前发生commit的时间戳。

3. 用Beam Model或者说DataFlow Model来理解的话(注意：理解这段内容，"可能"需要看过这本书：评:Streaming System(简直炸裂,强势安利)，或者读过Google DataFlow那篇论文)，每台机器的本地时钟的流动就好像watermark的流动(假设通过超光速往下游流动，方便理解，后边拿掉)，任何参与事务的机器的prepare就好像他们的prepare event和watermark一起流动到了coordinator，coordinator使用一个session window和atWarterMark Trigger等待所有参加事务的event到达，选择commit时间戳且所有上游的watermark超过这个commit时间戳，作为session window的结束，可以看到coordinator决定commit时间戳之后需要等待的时间必定不超过ε，所以就算不通讯(拿掉超光速watermark时间戳流)去持续等待上游的watermark，coordinator也可以通过等待ε来保证commit时间戳的单向增长性。

来源 https://zhuanlan.zhihu.com/p/44254954