luohaha
True Time算法的实现与思考
背景
在分布式系统中，由于每台机器产生的时间戳无法达成共识，导致每台机器从自身读取的时间戳变得毫无意义。在不想引入中心时间戳产生器的场景下，我们可以通过ntp服务，不断地校准每台机器的时间，但是这种方式得到的时间戳依然无法从理论上证明其正确性。在Google Spanner论文中，提出来了一个很有趣的关于时间的想法，就是假设每台机器产生的时间戳是有误差的，但是误差的增长速率是有上界的。在这个已知前提下，我们可以在分布式系统中达成关于时间戳误差范围的共识，这就是我们后面要讨论的true time。 根据spanner论文中关于true time描述部分提到的两篇论文，《Time synchronization in DCNET hosts》[1] 和《Maintaining the time in a distributed system》[2]，这里重新梳理了下truetime的实现，并证明truetime的正确性。
算法
以下总结了《Maintaining the time in a distributed system》[2] 中提到的算法。
-
假设: 𝑠𝑖为第 i 台 server。 t 是当前的物理时间。 𝐶𝑖 (t)为第 i 台 server 的时间戳。 𝐸𝑖 (𝑡)为第 i 台 server 的误差。 𝑟𝑖 为𝑠𝑖上一次校正的时间。 𝜀𝑖 为𝑠𝑖 上一次校正的误差。 δ𝑖为𝑠𝑖的时钟漂移速率,需要满足|1 − 𝑑𝐶𝑖(𝑡) / dt| ≤ δ𝑖 。 𝜉𝑗𝑖 为从i到j的rtt。在server i上测量。
-
目标：这个算法的目的是在 n 个 server 的分布式系统中，每台机器的时间能够保持一致。一致指的是所有的server的时间范围[𝐶𝑖(𝑡) − 𝐸𝑖(𝑡), 𝐶𝑖(𝑡) + 𝐸𝑖(𝑡)]都存在一个共同交集。也就是说,在绝对时间点𝑡0, 两台机器之间的时间戳误差,要小于他们的误差的和。也就是:
|𝐶𝑖(𝑡0) − 𝐶𝑗(𝑡0)| <= 𝐸𝑖(𝑡0) + 𝐸𝑗(𝑡0) (1)
而且，保证:
𝐶𝑖(𝑡0) − 𝐸𝑖(𝑡0) ≤ 𝑡0 ≤ 𝐶𝑖(𝑡0) + 𝐸𝑖(𝑡0) (2)
- 具体实现： N台Server之间会相互通信，会互相发送询问数据包，当server i接受到询问请求时，会返回 C 和 E:
// server i计算得到返回的C和E
C(𝑡) = 𝐶𝑖(𝑡)
E(𝑡) = 𝜀𝑖 + (𝐶𝑖(𝑡) − 𝑟𝑖) * δ𝑖
当server i收到其他机器的回复𝐶𝑗和𝐸𝑗时，首先，需要判断是否和当前的时间范围一致(也就是是否有交集)，如果一致: // 在其它机器的返回时间与自己保持一致的前提下，如果误差小于当前机器，则采用其它机器的时间和误差
If
𝐸𝑗 + (1 + δ𝑖) * 𝜉𝑗𝑖 ≤ 𝐸𝑖(𝑡)
Then
𝑟𝑖 = 𝐶𝑗,
𝐶𝑖 = 𝐶𝑗,
𝜀𝑖 = 𝐸𝑗 + (1 + δ𝑖) * 𝜉𝑗𝑖
以上算法的证明在论文[2]有论述。证明成立的前提是，|1 − 𝑑𝐶𝑖(𝑡) / dt| ≤ δ𝑖 。 Spanner中true time的证明
假设存在两个事务tran1和tran2，事务1的结束时间早于事务2的开始时间，spanner中如果存在事务tran1结束后，事务tran2才开始，保证事务1的时间戳，小于事务2的时间戳。在执行事务的时候，会等待对应的时间误差过去，因此存在:
t2 – t1 >= 𝐸1(𝑡) + 𝐸2(𝑡) (3)
需要证明:
𝐶2 − 𝐶1 ≥ 0
即可知，tran1的时间戳绝对小于tran2的时间戳。 证明: 因为根据(2)可知:
𝐶𝑖(𝑡) − 𝐸𝑖(𝑡) ≤ 𝑡 ≤ 𝐶𝑖(𝑡) + 𝐸𝑖(𝑡)
所以
Min(𝐶2) = t2 - 𝐸2
Max(𝐶1) = t1 + 𝐸1
可知
𝐶2 − 𝐶1 ≥ t2 – t1 – (𝐸2 + 𝐸1)
因为已知(3)，所以证明成功。 Spanner中truetime的正确性
因为上述算法的正确性的前提是漂移速率δ𝑖，需要满足
|1 − 𝑑𝐶𝑖(𝑡) / 𝑑𝑡| ≤ δ𝑖
如果不满足，就会出现不一致(时间范围不存在交集)的情况，spanner的truetime正确性就得不到保障。 关于工程实现的思考
true time的实现从原理上来说，是不需要依赖于使用原子钟的。但是，如果引入原子钟，对这个系统会有好处。 因为在上述提到的算法中，通过机器之间的相互通信，能够保证大家都处于一致的时间状态，并且时间的误差能够向周围的最小误差机器靠拢。但是，整个集群的误差会随着时间的流逝，逐渐变大，从而导致事务的执行时间会逐渐变长。因此，需要在集群中引入一台或多台时间偏移速率很小的原子钟，其它的机器通过不断地与他们通信，从而不断地消除自己的时间偏移。原子钟的引入，另外的好处就是，其它与其保持一致的机器，它们之间相互保持一致的概率也会很高。 而且我认为，true time的使用不应该只限制在分布式事务领域，在分布式系统的其他领域，也能发挥很大的作用。 Reference
[1] Mills D L. Time synchronization in DCNET hosts[J]. DARPA Internet Project Report IEN-173, COMSAT Laboratories, 1981. [2] Marzullo K, Owicki S. Maintaining the time in a distributed system[J]. ACM SIGOPS Operating Systems Review, 1985, 19(3): 44-54.
