本系列文章主要介紹計(jì)算機(jī)系統(tǒng)中時(shí)鐘的處理。主要內(nèi)容包含NTP，Lamport邏輯時(shí)鐘，向量時(shí)鐘，TrueTime等。本文是第四篇，介紹TrueTime。
計(jì)算機(jī)的時(shí)鐘（一）：NTP協(xié)議
計(jì)算機(jī)的時(shí)鐘（二）：Lamport邏輯時(shí)鐘
計(jì)算機(jī)的時(shí)鐘（三）：向量時(shí)鐘
在本系列上面的文章中我們介紹過(guò)NTP協(xié)議，使用網(wǎng)絡(luò)來(lái)同步真實(shí)世界的物理時(shí)間(Wall Clock)。由于廣域網(wǎng)的復(fù)雜網(wǎng)絡(luò)狀況，誤差可能在100毫秒級(jí)別。這么大的誤差顯然是不適合一些精確度要求高的應(yīng)用，一種辦法是拋棄物理時(shí)鐘，使用邏輯時(shí)鐘解決物理時(shí)鐘不可靠的問(wèn)題。另外一種辦法是努力提高物理時(shí)鐘的精度，將誤差降到可以接受的范圍。Google設(shè)計(jì)的TrueTime就是這種方案的代表。
TrueTime硬件
TrueTime由Google于2012年提出，用于Google的全球范圍部署的數(shù)據(jù)庫(kù)Spanner。TrueTime由時(shí)鐘硬件和算法組成。其中時(shí)鐘硬件由GPS時(shí)鐘和原子鐘組成。之所以使用這兩種硬件的原因是因?yàn)檫@兩種硬件的故障原因不一樣，這樣可以提高時(shí)鐘的可靠性。GPS時(shí)鐘故障的原因有天線和接收器故障，無(wú)線信號(hào)干擾等。原子鐘可能由于頻率問(wèn)題造成時(shí)鐘漂移。這兩種原因是不相交的，所以能提高整個(gè)硬件的可靠性。整個(gè)硬件的成本并不貴，淘寶上原子鐘的價(jià)格從幾千到幾萬(wàn)都有。下圖是美國(guó)Symmetricom公司的超小型芯片級(jí)原子鐘，價(jià)格1500美元。
TrueTime架構(gòu)
TrueTime架構(gòu)如下：
每個(gè)數(shù)據(jù)中心有若干個(gè)time master機(jī)器。大部分time master機(jī)器安裝了GPS天線和接收器。剩下的time master機(jī)器安裝了原子鐘。time master之間會(huì)相互校驗(yàn)時(shí)間，如果某個(gè)time master發(fā)現(xiàn)自己的本地時(shí)間和其他time master相比差異很大，會(huì)把自己設(shè)置為離線，停止工作?？蛻舳讼蚨鄠€(gè)time master查詢，防止某個(gè)time master出現(xiàn)故障影響結(jié)果。
即使使用了GPS時(shí)鐘和原子鐘，也不能保證時(shí)鐘0誤差。2012年Spanner論文發(fā)表時(shí)，時(shí)鐘的誤差范圍 ε 是1ms到7ms，平均4ms。前面我們介紹過(guò)NTP的誤差在100ms級(jí)別，TrueTime的誤差相比NTP大大減少了。
TrueTime API
TrueTime提供了三個(gè)API來(lái)操作時(shí)間：
| Method | Returns |
|---|---|
| TT.now() | TTinterval: [earliest, latest] |
| TT.after(t) | true if t has definitely passed |
| TT.before(t) | true if t has definitely not arrived |
- TT.now() 返回的是當(dāng)前時(shí)間，由于時(shí)鐘硬件誤差的存在，這個(gè)當(dāng)前時(shí)間存在一個(gè)不確定的范圍(uncertainty time)，也即一個(gè)范圍 [earliest, latest]，可以保證當(dāng)前絕對(duì)時(shí)間一定在這個(gè)范圍內(nèi)，上面介紹過(guò)，這個(gè)間隔范圍最大是7ms。
- TT.after(t) 判斷傳入的時(shí)間戳是否已經(jīng)是過(guò)去的時(shí)間，也即 t < TT.now().earliest。
- TT.before(t) 判斷傳入的時(shí)間戳是否是未來(lái)的時(shí)間，也即 TT.now().latest < t。
使用TrueTime API時(shí)，需要搭配下面兩個(gè)規(guī)則。
- Start： 提交事務(wù)Ti時(shí)，leader必須選擇一個(gè)大于等于TT.now().latest的時(shí)間作為提交時(shí)間戳si。
- Commit Wait： leader必須等待TT.after(si)為true后才能提交數(shù)據(jù)，也即必須等待si的絕對(duì)時(shí)間過(guò)去了才能提交數(shù)據(jù)。
使用這兩個(gè)規(guī)則可以保證：如果事務(wù) T1 提交后 T2 才開(kāi)始，那么 T2 的提交時(shí)間一定晚于 T1 的提交時(shí)間。也就是說(shuō)事務(wù)的提交順序一定和事務(wù)發(fā)生的絕對(duì)時(shí)間上的順序一致。
TrueTime應(yīng)用
有了TrueTime API和Start，Commit Wait規(guī)則，能解決什么問(wèn)題呢，如何應(yīng)用呢？
舉個(gè)例子：分布式事務(wù)中有三臺(tái)服務(wù)器S1，S2，S3。執(zhí)行分布式事務(wù)時(shí)，某一臺(tái)參與者作為協(xié)調(diào)者提交事務(wù)，提交時(shí)使用這次事務(wù)所有參與者中最大的時(shí)間戳作為事務(wù)的提交時(shí)間。每臺(tái)服務(wù)器和絕對(duì)時(shí)間Tabs都有誤差，S1的時(shí)間比絕對(duì)時(shí)間快5ms，即Tabs + 5，S2的時(shí)間比絕對(duì)時(shí)間慢4ms，即Tabs - 4，S3的時(shí)間比絕對(duì)時(shí)間慢4ms，即Tabs - 2。
現(xiàn)在有一個(gè)事務(wù)T1，參與者包括S1和S2，S1執(zhí)行分支事務(wù)的本地時(shí)間是15ms，S2執(zhí)行分支事務(wù)的本地時(shí)間是7ms。S2作為協(xié)調(diào)者，提交事務(wù)時(shí)選擇了15ms作為整個(gè)事務(wù)的執(zhí)行時(shí)間。
另外一個(gè)事務(wù)T2，參與者包括S2和S3，S3執(zhí)行分支事務(wù)的本地時(shí)間是13ms，S2執(zhí)行分支事務(wù)的本地時(shí)間是12ms。S2還是作為協(xié)調(diào)者，提交事務(wù)時(shí)選擇了13ms作為整個(gè)事務(wù)的執(zhí)行時(shí)間。
什么？絕對(duì)時(shí)間上事務(wù)T2比T1要晚執(zhí)行，但是提交時(shí)間T2卻比T1要早，這顯然是錯(cuò)誤的。
我們看看使用TrueTime如何解決這個(gè)問(wèn)題。
假設(shè)TrueTime誤差 ε 為7ms。
T1事務(wù)協(xié)調(diào)者選擇提交時(shí)間s1時(shí)，根據(jù) Start 規(guī)則，必須大于所有事務(wù)參與者中最大的本地時(shí)間，還要大于協(xié)調(diào)者本地TT.now().lastest。計(jì)算得出 s1 = max(15, 7 + 7) = 15ms。
選擇提交時(shí)間s1后，根據(jù) Commit Wait 規(guī)則，還要等待TT.after(15)為true后才能提交數(shù)據(jù)。實(shí)際可能在絕對(duì)時(shí)間17ms提交的數(shù)據(jù)。
T2事務(wù)協(xié)調(diào)者選擇提交時(shí)間s2時(shí)，根據(jù) Start 規(guī)則，計(jì)算得出 s2 = max(13, 12 + 7) = 19ms。
選擇提交時(shí)間s2后，根據(jù) Commit Wait 規(guī)則，還要等待TT.after(19)為true后才能提交數(shù)據(jù)。實(shí)際可能在絕對(duì)時(shí)間21ms提交的數(shù)據(jù)。
可以看出T2的提交時(shí)間要晚于T1，解決了這個(gè)例子中的問(wèn)題。當(dāng)然，實(shí)際處理時(shí)，還會(huì)對(duì)數(shù)據(jù)進(jìn)行加鎖等操作，Google Spanner中詳細(xì)的事務(wù)處理流程可以查看論文。
TrueTime性能
Google Spanner中，對(duì)同一個(gè)數(shù)據(jù)進(jìn)行修改時(shí)，需要加鎖，TrueTime相當(dāng)于是把所有并發(fā)操作串行化，進(jìn)行排隊(duì)。由于TrueTime的誤差在1到7ms之間，平均誤差4ms。一次事務(wù)需要等待兩個(gè) ε，一個(gè)是選擇提交時(shí)間時(shí)需要等待TT.now().latest，另外一個(gè)是提交數(shù)據(jù)時(shí)需要等待TT.after(s)，平均需要等待8ms。也就是說(shuō)對(duì)于同一個(gè)數(shù)據(jù)的寫(xiě)事務(wù)，Spanner并發(fā)量是每秒125個(gè)。這是論文發(fā)表時(shí)的數(shù)據(jù)，論文中也寫(xiě)到未來(lái)希望把誤差 ε 降低到1ms。
上圖是論文中給出的誤差 ε 數(shù)據(jù)，從中可以看到，90%的誤差 ε 都在1ms以內(nèi)，99%的誤差 ε 都在2ms以內(nèi)。
關(guān)于性能，論文中有句話我深以為然：
We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.
