背景

在分散式系統中，由於每台機器產生的時間戳無法達成共識，導致每台機器從自身讀取的時間戳變得毫無意義。在不想引入中心時間戳產生器的場景下，我們可以通過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] 中提到的演算法。

  1. 假設: ????為第 i 台 server。 t 是當前的物理時間。 ???? (t)為第 i 台 server 的時間戳。 ???? (??)為第 i 台 server 的誤差。

    ???? 為????上一次校正的時間。

    ???? 為???? 上一次校正的誤差。 δ??為????的時鐘漂移速率,需要滿足|1 ? ??????(??) / dt| ≤ δ?? 。 ?????? 為從i到j的rtt。在server i上測量。

2. 目標：這個演算法的目的是在 n 個 server 的分散式系統中，每台機器的時間能夠保持一致。一致指的是所有的server的時間範圍[????(??) ? ????(??), ????(??) + ????(??)]都存在一個共同交集。也就是說,在絕對時間點??0, 兩台機器之間的時間戳誤差,要小於他們的誤差的和。也就是:

|????(??0) ? ????(??0)| <= ????(??0) + ????(??0) (1)

而且，保證:

????(??0) ? ????(??0) ≤ ??0 ≤ ????(??0) + ????(??0) (2)

3. 具體實現： 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.
推薦閱讀：
查看原文 >>
相关文章