最近看到了CockroachDB的這篇博客?Living without atomic clocks: Where CockroachDB and Spanner diverge（不依賴原子鐘：CockroachDB和Spanner的分野。原文地址?https://www.cockroachlabs.com/blog/living-without-atomic-clocks/）。

這篇博客算是把分布式系統(tǒng)中的時(shí)間問(wèn)題，講的比較透徹了，所以就抽時(shí)間翻譯了一下。因?yàn)樵谋容^長(zhǎng)，所以就拆成上下兩篇發(fā)了，這是上篇。

話不多說(shuō)，下面就是正文了。

CockroachDB的設(shè)計(jì)是基于谷歌的Spanner數(shù)據(jù)存儲(chǔ)系統(tǒng)。Spanner最令人驚訝和最受啟發(fā)的方面之一是它使用原子鐘和GPS時(shí)鐘為參與者節(jié)點(diǎn)提供真正準(zhǔn)確的強(qiáng)時(shí)間同步。Spanner的設(shè)計(jì)者稱之為“TrueTime”，它提供了系統(tǒng)中任意兩個(gè)節(jié)點(diǎn)之間嚴(yán)格的時(shí)鐘偏移量。這讓他們可以做一些突破性的事情！我們將在下面詳細(xì)介紹其中的一些，但其中最主要的是它們能夠利用緊密同步的時(shí)鐘來(lái)提供高水平的外部一致性（下文將解釋這個(gè)概念的含義）。

如果有人對(duì)Spanner略知一二，那么他們首先要問(wèn)的問(wèn)題之一是：“如果你要寫(xiě)一個(gè)開(kāi)源數(shù)據(jù)庫(kù)，你就不能使用原子鐘；那么CockroachDB到底是怎么工作的呢？”（譯者注：這里給不了解Spanner的讀者預(yù)先解釋一下，原子鐘是非常昂貴的設(shè)備，并且Spanner的TureTime對(duì)原子鐘的使用方法也是沒(méi)有開(kāi)源的。所以一個(gè)開(kāi)源的數(shù)據(jù)庫(kù)，必定不能依賴原子鐘來(lái)工作，因?yàn)槟菢幽呐履汩_(kāi)源了，大家也完全沒(méi)有辦法去使用）

這是一個(gè)非常好的問(wèn)題，也是我們（試圖）在這里詳細(xì)闡述的問(wèn)題。作為一個(gè)受Spanner啟發(fā)的系統(tǒng)，我們面臨的挑戰(zhàn)在于在沒(méi)有神奇全局時(shí)鐘（譯者注：原文為“magical clock”）的情況下提供類似的外部一致性保證。CockroachDB旨在在現(xiàn)成的商品硬件上運(yùn)行，在任何任意的節(jié)點(diǎn)集合上運(yùn)行。它是“云中立的”，因?yàn)樗梢院芎玫乜缍鄠€(gè)公共和/或私有云，使用您喜歡的任何虛擬化層。如果需要外部依賴于專門(mén)的硬件來(lái)進(jìn)行時(shí)鐘同步，那是一件不現(xiàn)實(shí)的事情。

那么CockroachDB是怎么做的呢？好吧，在回答這個(gè)問(wèn)題之前，讓我們更深入地了解為什么TrueTime是為Spanner設(shè)計(jì)的。

時(shí)間在分布式系統(tǒng)中的重要性

時(shí)間是一件變化無(wú)常的事情。對(duì)于不熟悉分布式系統(tǒng)研究中時(shí)間復(fù)雜性的讀者來(lái)說(shuō)，需要了解的是：系統(tǒng)中的每個(gè)節(jié)點(diǎn)都有自己的時(shí)間，由自己的本地時(shí)鐘提供。這個(gè)時(shí)鐘設(shè)備很少能與系統(tǒng)中的其他節(jié)點(diǎn)完全同步，因此，沒(méi)有“絕對(duì)”時(shí)間可以參考。

拋開(kāi)是否存在不談，完全同步的時(shí)鐘是分布式系統(tǒng)研究的圣杯（譯者注：這句話的意思是，雖然完全同步的時(shí)鐘不可能實(shí)現(xiàn)（不過(guò)也不完全絕對(duì)，萬(wàn)一未來(lái)可以做到量子通信呢），但我們還是可以幻想一下完全同步的時(shí)鐘如果存在，會(huì)對(duì)分布式系統(tǒng)帶來(lái)多大的變革）。從本質(zhì)上講，無(wú)論事件起源于哪個(gè)節(jié)點(diǎn)，（完全同步的時(shí)鐘）都能提供一種絕對(duì)排序事件的方法。當(dāng)性能受到威脅時(shí)，這一點(diǎn)尤其有用，允許節(jié)點(diǎn)子集在不考慮集群其他部分的情況下向前推進(jìn)（就像其他節(jié)點(diǎn)都看到了相同的“絕對(duì)”時(shí)間一樣），同時(shí)仍然保持全局排序保證。我們最喜歡的圖靈獎(jiǎng)得主（譯者注：指Barbara Liskov老太太，2008 年因“對(duì)編程語(yǔ)言和系統(tǒng)設(shè)計(jì)的實(shí)踐與理論基礎(chǔ)，尤其是數(shù)據(jù)抽象化、容錯(cuò)和分布式計(jì)算的貢獻(xiàn)”獲得圖靈獎(jiǎng)，她發(fā)明了CLU編程語(yǔ)言，目前常用的C++、Java、Python都受到CLU的影響）在這篇論文中（譯者注：指Practical uses of synchronized clocks in distributed systems，Barbara Liskov于1978年發(fā)表的一篇討論分布式系統(tǒng)中同步時(shí)鐘應(yīng)用的論文，Spanner也引用了這篇論文）寫(xiě)了一些關(guān)于這個(gè)主題的內(nèi)容。

Linearizability（譯者注：直譯是線性化，也可以翻譯成“線性一致性”）

相比之下，沒(méi)有完全同步時(shí)鐘的系統(tǒng)（實(shí)際上是所有的系統(tǒng)）想要建立一個(gè)完整的全局排序，必須在每次操作中與單個(gè)時(shí)間源通信。這就是Percolator使用的“timestamp oracle”背后的動(dòng)機(jī)。假設(shè)從外部來(lái)看，一個(gè)指定了事務(wù)T1、T2的順序?yàn)閇T1,T2]的系統(tǒng)在任何情況下都能給出事務(wù)T2在事務(wù)T1結(jié)束之后開(kāi)始的強(qiáng)一致性保證的話，我們稱這系統(tǒng)具備了“外部一致性（external consistency）”。（譯者注：這句話比較難理解，實(shí)際上是呼應(yīng)開(kāi)頭，給出了external consistency的釋義：一個(gè)系統(tǒng)如果具備了external consistency，那么它在任何情況下都會(huì)給外部呈現(xiàn)一個(gè)符合Linearizability的結(jié)果。這句話看起來(lái)有點(diǎn)像重復(fù)了1+1=2，但實(shí)際上，確實(shí)就是1+1=2（哈哈）。后文里external consistency就等同于Linearizability）。為了進(jìn)一步混淆（譯者注：這里作者有點(diǎn)開(kāi)玩笑擺爛的意思，分布式領(lǐng)域這些一致性概念確實(shí)非?；靵y，很多時(shí)候?yàn)榱私忉屵@些模棱兩可的名詞就要費(fèi)很大的勁，比如各種各樣的consistency（笑）。各位讀者在這里沒(méi)太有必要糾結(jié)于弄懂這幾個(gè)詞的含義，看本段最后的注解就OK了），這就是人們可互換地稱之為“Linearizability（線性一致性）”或“Strict Serializability（嚴(yán)格可串行化）”的東西。Andrei（譯者注：指作者同事Andrei Matei）對(duì)這種一致性模型有更多的描述。

（譯者注：其實(shí)這段只說(shuō)了一件事：本文中，External Consistency =?Linearizability = Strict Serializability。（大家記住這一句就行，不要在這過(guò)于糾結(jié)了）

關(guān)于Linearizability，這里給大家再解釋一下。線性一致性其實(shí)是并發(fā)系統(tǒng)中的一個(gè)概念，指的是對(duì)單個(gè)順序的一組操作提供了一個(gè)符合客觀時(shí)間順序的排序操作。在這篇文章中，實(shí)際上是把線性一致性擴(kuò)大到和Strict Serializability等同的地步了，也就是說(shuō)比下文要討論的Serializability更進(jìn)一步，是隔離級(jí)別更上層的一個(gè)概念。哪怕在事務(wù)邏輯中不相干的事務(wù)，也要符合這個(gè)特性。就比如說(shuō)事務(wù)T2在事務(wù)T1提交之后開(kāi)始，T1在1ms開(kāi)始，3ms提交，那么T2開(kāi)始的點(diǎn)就必須晚于3ms，哪怕他們倆完全沒(méi)有交集，比如T1修改了a，T2修改了B。所以說(shuō)在事務(wù)中，我們是不需要External Consistency/Linearizability/Strict Serializability?這么嚴(yán)格的保證的（雖然Spanner和單機(jī)數(shù)據(jù)庫(kù)做到了這點(diǎn)），這也是后文要論證的。）

Serializability（譯者注：可串行化，也稱“可序列化”）

讓我們?cè)偾腥胍粋€(gè)線索，引入“Serializability”的概念。大多數(shù)數(shù)據(jù)庫(kù)開(kāi)發(fā)人員都熟悉Serializability，因?yàn)樗茿NSI SQL標(biāo)準(zhǔn)提供的最高隔離級(jí)別。它保證一個(gè)事務(wù)在讀取和寫(xiě)入時(shí)，就好像在這期間只有這一個(gè)事務(wù)在訪問(wèn)數(shù)據(jù)庫(kù)一樣，從而完全避免了事務(wù)間的互相干擾。換句話說(shuō)，并發(fā)執(zhí)行的事務(wù)T1和T2，T2讀取不到T1的任何中間狀態(tài)，從而讓兩者在執(zhí)行過(guò)程中對(duì)同一key可以讀取不同的值。

在非分布式數(shù)據(jù)庫(kù)中，Serializability意味著事務(wù)的Linearizability，因?yàn)閱蝹€(gè)節(jié)點(diǎn)的時(shí)鐘單調(diào)遞增（這就是關(guān)鍵所在！）。如果事務(wù)T1 在啟動(dòng)事務(wù)T2之前提交, 那么事務(wù)T2 只能在以后提交。

在分布式數(shù)據(jù)庫(kù)中，這套邏輯就不成立了。很容易就可以想到，如果系統(tǒng)中的節(jié)點(diǎn)具有不同步的時(shí)鐘，那么兩個(gè)有先后關(guān)系事務(wù)（譯者注：原文為“causally-related transaction”。舉個(gè)例子，假設(shè)A的賬戶扣款后，就會(huì)觸發(fā)給B發(fā)一個(gè)短信，這是兩個(gè)事務(wù)，但事務(wù)B又一定要在事務(wù)A之后執(zhí)行，因?yàn)樗鼈冊(cè)谕獠窟壿嬌洗嬖谙群箜樞蜿P(guān)系，這就可以理解為“causally-related transacgtion”）的順序很有可能就被顛倒過(guò)來(lái)了。

（譯者注：??！重點(diǎn)??！這里是最重要的邏輯，大家一定要把這里弄懂，再看后面的內(nèi)容才有意義。這里最核心的點(diǎn)是，Serializability是對(duì)于事務(wù)隔離級(jí)別的一致性保證，而Linearizability是對(duì)任何有順序關(guān)系事務(wù)的一致性保證。所以時(shí)鐘的差異就造成了影響，在單機(jī)庫(kù)中，Serializability?=?Linearizability；分布式庫(kù)中，Serializability?<?Linearizability。）

假設(shè)有兩個(gè)節(jié)點(diǎn)，N1 和N2, 以及兩個(gè)事務(wù)，T1 和T2，在N1和N2節(jié)點(diǎn)分別提交。因?yàn)槲覀儧](méi)有全局唯一的時(shí)間來(lái)源，所以事務(wù)使用節(jié)點(diǎn)本地時(shí)鐘來(lái)生成提交時(shí)間戳。為了說(shuō)明這方面的棘手之處，我們假設(shè)N1節(jié)點(diǎn)有一個(gè)準(zhǔn)確的本地時(shí)鐘，但N2的本地時(shí)鐘滯后100毫秒。事務(wù)T1先在N1上執(zhí)行, 其在ts＝150ms時(shí)提交。50ms后（t=200ms時(shí)），外部觀察者看到T1提交并由此啟動(dòng)T2（在N2節(jié)點(diǎn)上執(zhí)行)。但因?yàn)镹2的本地時(shí)鐘滯后100ms，所以T2提交的時(shí)間為一個(gè)過(guò)去的時(shí)間，即ts=100ms。現(xiàn)在，我們?cè)贜1上讀取和N2上讀取將看到相反的順序，T2的寫(xiě)入（ts=100ms）似乎發(fā)生在T1的寫(xiě)入之前（ts=150ms），盡管情況正好相反。這就麻煩了呀！（請(qǐng)注意，只有當(dāng)兩個(gè)事務(wù)訪問(wèn)一組不相交的key時(shí)，才會(huì)發(fā)生這種情況。）

（譯者注：結(jié)合上面銀行扣款的例子，就很好理解了。雖然在邏輯中是A的賬戶扣款后觸發(fā)給B發(fā)短信，但因?yàn)榉植际较到y(tǒng)內(nèi)不同步的時(shí)鐘，表現(xiàn)為先給B發(fā)了短信，50ms后才對(duì)A進(jìn)行扣款。這就是這里的問(wèn)題所在。要強(qiáng)調(diào)的是，這里必須是兩個(gè)沒(méi)有重疊key的事務(wù)才會(huì)有這種問(wèn)題，如果有重疊key，會(huì)有事務(wù)的鎖機(jī)制或其他機(jī)制來(lái)干擾）

（譯者注：再?gòu)?qiáng)調(diào)一遍，其實(shí)這段這么多內(nèi)容就只是為了說(shuō)明一件事：時(shí)鐘的差異造成了影響，在單機(jī)庫(kù)中，Serializability?= Linearizability；分布式庫(kù)中，Serializability?<?Linearizability。）

上面描述的“異?！?，如圖1所示，是我們稱之為“順序顛倒”的東西。雖然Spanner提供了Linearizability保證，但CockratchDB只聲稱可以Serializability，盡管在實(shí)踐中有一些功能可以幫助彌補(bǔ)這一差距。我會(huì)（懶洋洋地）再次聽(tīng)從Andrei的話，他確實(shí)在這里占據(jù)了很多位置（譯者注：指作者同事Andrei Matei寫(xiě)的有關(guān)CockroachDB一致性模型的另一篇文章，CockroachDB's consistency model。鏈接：https://www.cockroachlabs.com/blog/consistency-model/）。

未完待續(xù)...