作者介紹：包子俠

原文鏈接：混合時間戳

翻譯自論文： HybridTime - Accessible Global Consistency with High Clock Uncertainty

摘要

在物理時鐘不確定的分布式系統(tǒng)中保證全局一致性是很多分布式系統(tǒng) （如分布式數(shù)據(jù)庫） 要解決的問題。Google的Spanner數(shù)據(jù)庫通過使用高精度時鐘，降低時鐘不確定性，然后使用提交等待（commit wait）來實現(xiàn)副本組之間的一致性，這項技術可以確保因果相關的事務在時間上以超過時鐘同步誤差界限的方式區(qū)分（解讀：Spanner通過引入原子鐘來解決不同物理服務器時鐘誤差不一致的問題。spanner的TrueTime返回的不是一個時間點，而是一個時間范圍[t-ε,t+ε]，通過這個時間范圍可以保證，只要兩個事務之間的時間差大于原子鐘的誤差邊界，就可以區(qū)分兩個事務的因果關系，誤差越小，就越精確）。然而，對于其他數(shù)據(jù)庫廠商來說，在谷歌數(shù)據(jù)中心之外使用類似的技術可能很困難，甚至不可能（例如，當使用像amazonec2這樣的云服務時）。

在本文中，我們介紹了混合時間HybridTime（物理時鐘和邏輯時鐘的混合），可以用來實現(xiàn)一個全局一致性數(shù)據(jù)庫。與Spanner不同，對于大多數(shù)事務，HybridTime不需要等待時間誤差（解讀：Spanner的TrueTime是一個范圍時間，為了確保時間的準確性，事務會等待時間超過該誤差再提交），因此可以用于常見的時間同步系統(tǒng)。我們在同一個系統(tǒng)中實現(xiàn)了HybridTime和commit wait，并在一系列實際場景中對HybridTime與Spanner的commit wait進行了實驗比較，結果表明HybridTime在延遲方面的性能相較于Spanner的commit-wait可以提高1個數(shù)量級。

1. 簡介

越來越多的分布式系統(tǒng)，如Spanner這樣的分布式數(shù)據(jù)庫，以前所未有的規(guī)模部署，并跨多個數(shù)據(jù)中心進行分區(qū)/復制，以降低服務延遲并提升容錯能力。在這樣的系統(tǒng)中，事務常常跨越多個數(shù)據(jù)中心，并涉及多個服務器，每個服務器服務于一個數(shù)據(jù)集的不同分區(qū)。

為了提供良好的性能，許多可伸縮的分布式數(shù)據(jù)庫，如Amazon的Dynamo和Facebook的Cassandra，放松了一致性模型，只提供最終的一致性。其他如HBase和BigTable只為涉及單個分區(qū)的操作提供了強一致性，而無法跨數(shù)據(jù)庫作為一個整體提供強一致性。

這些松散的一致性模型給應用程序開發(fā)人員帶來了困難，他們通常習慣于針對完全線性化的單節(jié)點數(shù)據(jù)結構進行編程。

此外，如果最終用戶看到一致性方面的異常，他們可能會感到驚訝和不安：例如，一個按地理分布的服務（多數(shù)據(jù)中心），用戶可能首先被路由到本地數(shù)據(jù)中心并執(zhí)行某些操作，例如發(fā)送電子郵件。如果他們重新加載瀏覽器并被路由到另一個數(shù)據(jù)中心，他們?nèi)匀幌Ｍ陔娮余]件發(fā)件箱中看到他們發(fā)送的消息。更松散的一致性模型，如時間線一致性或最終一致性運行這種異常，在這種模型下，用戶在不同的數(shù)據(jù)中心可能會看到不同的數(shù)據(jù)，這對于銀行或在線商務等許多應用程序來說可能是不可接受的。

解決一致性問題的最簡單方法是在所有服務器上具有完全準確和同步的時鐘；但是，由于在分布式系統(tǒng)中不可能實現(xiàn)絕對精確的物理計時，因此實現(xiàn)全局一致性的傳統(tǒng)方法是使用邏輯時鐘，例如：Lamport Clocks或者Vector Clocks。這種時鐘可以提供全局的、因果一致的數(shù)據(jù)和更新視圖，但有兩個缺點：第一，它們要求所有客戶端必須傳播時鐘數(shù)據(jù)以獲得一致的視圖；第二，分配的時間戳與物理時間無關。

因此，它們無法提供在物理時間點上的快照讀請求，這是商業(yè)系統(tǒng)（如Oracle Flashback和ibm db2）以及學術項目（如Immortal DB）提供的功能。此外，用戶希望他們所知道的在現(xiàn)實世界中發(fā)生的操作看起來是有序的，與系統(tǒng)是否能在它們之間建立因果關系無關，而Lamport時鐘的向量時鐘無法提供這一點。

值得一提的是，我們所指的一致全局狀態(tài)不僅是服務于相同數(shù)據(jù)的不同副本之間的一致狀態(tài)，而且是在數(shù)據(jù)庫的不同分區(qū)之間保持一致的狀態(tài)，這種狀態(tài)本身可能分布在地理分布的數(shù)據(jù)中心中。像Spinnaker這樣的系統(tǒng)使用Paxos來實現(xiàn)前者，但是對于跨分區(qū)操作，它又回到了悲觀的鎖定方案中。許多可伸縮數(shù)據(jù)庫的應用程序都涉及到大量的分析工作負載，其中只讀事務常常在整個數(shù)據(jù)集上運行。對于這些類型的事務，可能要運行幾分鐘甚至幾個小時，基于鎖的跨分區(qū)一致性方案是不可接受的，因為它們會阻止任何其他并發(fā)操作。

Spanner引入了commit wait，這是一種確保基于物理時間的全局狀態(tài)一致性的方法，方法是強制操作等待足夠長的時間，以便所有參與者都同意操作的時間戳已經(jīng)越過了基于最壞情況下的誤差邊界。雖然具有創(chuàng)新性，但系統(tǒng)性能高度依賴于時間同步基礎設施的質(zhì)量，因此，如果沒有專用硬件（如原子鐘和GPS接收器），系統(tǒng)性能可能無法接受。通常情況下，用戶可能會將應用部署在公有云上，例如Amazon EC2，因此不具備添加此類高精度計時設備所需的基礎設施的條件。在本文中，我們提出了混合時間（HybridTime，HT），一種物理時鐘和邏輯時鐘的混合體，并且我們展示了如何使用HT來實現(xiàn)與Spanner相同的語義，但是即使在通?？捎玫臅r間同步的情況下（如：NTP等不完全精確的時間同步情況下），它也具有良好的性能。

與Spanner一樣，我們的方法依賴于帶有有界誤差的物理時間測量來為系統(tǒng)中發(fā)生的事件分配混合時間戳。然而，與Spanner不同的是，我們的方法通常不需要等待錯誤，因此允許在常見的部署場景中使用，在這些場景中，時鐘同步通過諸如NTP之類的公共協(xié)議進行同步，在這種情況下，時鐘同步誤差通常高于使用Spanner的TrueTime。權衡是，為了避免提交等待，HybridTime要求時間戳在機器之間傳播，以實現(xiàn)與Spanner相同的一致性語義。與向量時鐘相反，矢量時鐘可以隨著集群中參與者數(shù)量的增加而擴展，而混合時間時間戳具有恒定且較小的大小。

HybridTime時鐘遵循與Lamport時鐘相似的更新規(guī)則，但是時間值不是純邏輯的：每個時間值都有一個邏輯組件，它有助于保證與Lamport時鐘相同的屬性，還有一個物理組件允許事件與物理時間點相關聯(lián)。與邏輯時間戳一樣，HT時間戳也需要附加到每個來自客戶端的消息上。HT時間戳不受向量時鐘問題的影響，向量時鐘可以隨著時間的推移從不同的機器中積累狀態(tài)而增長。相反，它們更像是Lamport時鐘時間戳，因為它們具有恒定和較小的大小。此外，與Lamport時鐘和向量時鐘相比，當兩個事件之間的間隔超過最大時鐘誤差時，即使它們沒有因果關系，或者如果它們的因果關系是通過系統(tǒng)無法捕獲的隱藏通道建立的，也可以建立事件的時間順序。

本文主要貢獻如下：

• 我們介紹了HybridTime時鐘，包括更新算法和正確性證明。
• 我們介紹了在現(xiàn)實中如何使用HybridTime時鐘，與TrueTime在Spanner中的應用場景類似。
• 我們基于相同的場景與Spanner的TrueTime進行了對比。
• 我們描述了如何使用常見的硬件和軟件實現(xiàn)commit-wait。

2. 背景和相關工作

Spanner的一個主要優(yōu)點是外部一致性（externally consistent），這被定義為完全線性化，即使在存在隱藏通道的情況下。在本文中，我們使用外部一致這一術語。此外，我們使用術語全局一致性（globally consistent）來描述一個系統(tǒng)，該系統(tǒng)提供相同的線性化語義，前提是不存在隱藏通道。

盡管副本組內(nèi)的一致性在大型數(shù)據(jù)庫中得到了廣泛的實現(xiàn)，但副本組間的一致性卻不是這樣。Dynamo[9]作者指出，他們使用向量時鐘在一行中執(zhí)行2個沖突解決，但沒有為多行事務提供等效的功能。Cassandra[13]與Dynamo有相似之處，它使用普通的掛鐘時間戳，沒有考慮時鐘誤差，因此無論是在副本組內(nèi)部還是在副本組之間，都不能提供一致性。類似地，BigTable[4]和它的開源版本HBase[1]在每臺服務器上本地分配時間戳，并且不提供跨副本組（tablets）的一致性保證。水平分區(qū)的SQL系統(tǒng)，如MySQL（通常被描述為“sharded MySQL”）類似地提供分區(qū)內(nèi)的一致性，但是不能跨多個分區(qū)查詢快照。

如果所有參與者都能訪問一個完全同步的物理時鐘，那么實現(xiàn)一致的系統(tǒng)將是微不足道的。然而，眾所周知，分布式系統(tǒng)中的服務器不可能擁有完全同步的時鐘。即使使用時間同步機制，如NTP[21]，在系統(tǒng)中不同機器上運行的進程也有不精確的時鐘，與理論參考時鐘相比，這些時鐘會存在一些絕對誤差。此外，現(xiàn)實生活中的時鐘會隨著時間的推移而出現(xiàn)偏差：不同機器上的時鐘可能會隨著時間的推移而彼此之間的距離越來越遠。因此，數(shù)據(jù)庫通常求助于其他機制來為事務分配時間戳，從而可以計算出因果一致的快照。其中一種時間戳機制是使用邏輯時鐘，例如Vector Clocks[10,20]或Lamport Clocks[15]。使用這種時鐘來排序事件的系統(tǒng)可以是全局一致的；但是，它們不具有外部一致性，因為它們要求所有客戶端參與者傳播時鐘。例如，如果客戶端A通過隱藏通道與客戶端B通信而不轉發(fā)時間戳，則不能保證客戶端B能夠看到客戶端A執(zhí)行的任何修改。

其他系統(tǒng)，如Percolator[22]、HBaseSI[27]和Cloudtps[26]使用一個集中的時間戳服務來為事務分配單調(diào)遞增的時間戳，并確定序列化順序。因此，它們在全球和外部都是一致的。但是，這種方法不能很好地擴展到高事務吞吐量，并且如果是地理分布的設置，在遠程數(shù)據(jù)中心運行的事務將不得不為每個事務付出到時間戳服務的昂貴往返開銷，并且會增加不可接受的延遲。有些系統(tǒng)在廣域網(wǎng)中實現(xiàn)某種形式的因果一致性。COPS[18]或ChainReaction[2]在地理分布系統(tǒng)中實施因果關系約束，但不在時間戳中嵌入物理意義。最后，在物理時間和時鐘錯誤的推理方面有值得注意的工作[24]，其目的是允許以與邏輯時間類似的方式使用物理時間，例如全局謂詞檢測，但據(jù)我們所知，它還沒有應用于分布式數(shù)據(jù)庫。

Spanner的關鍵創(chuàng)新在于，系統(tǒng)分配的時間戳既可以用來實現(xiàn)外部一致性，又具有物理意義，而Vector Clocks和Lamport Clocks的時間戳是純邏輯的。此外，Spanner分配具有已知有界誤差的時間戳。我們將展示HybridTime也提供了具有物理意義和有界誤差的時間戳。

3. HybridTime

3.1 HybridTime假設

與如何獲得物理時間測量無關，HybridTime依賴于某些假設。在本節(jié)中，我們將介紹這些假設，并說明在大多數(shù)現(xiàn)代分布式系統(tǒng)部署的環(huán)境下，這些假設是合理的，TrueTime也做出了類似的假設。HybridTime假設機器有一個相對精確的物理時鐘，能夠提供絕對時間測量值（通常從1970年1月1日起以毫秒或微秒為單位）。幾乎所有的現(xiàn)代服務器都配備了這樣的物理時鐘。我們用PCi(e)函數(shù)表示該物理時鐘，該函數(shù)輸出物理時鐘返回的數(shù)字時間戳，表示進程i讀取事件e的時間，

此外，我們假設有一個底層的物理同步設施，它使不同服務器之間的物理時鐘相對于參考服務器“參考”時間保持同步，由PCref（e）函數(shù)表示，該函數(shù)輸出由事件e的“參考”過程返回的數(shù)字時間戳。此外，我們假設這樣的設施能夠隨每次測量提供有界誤差，由Ei（e）函數(shù)表示，該函數(shù)輸出進程i在事件e發(fā)生時的誤差值ε。同樣，這是合理的假設，因為幾乎所有大型集群都執(zhí)行時間同步守護進程，例如前面提到的NTP，它既同步服務器的時鐘，又在任何時候提供時鐘錯誤的最大限制。值得一提的是，TrueTime也做出了類似的假設。最后，我們注意到，我們對時鐘的實際精度沒有任何假設，即服務器時鐘返回的物理時間戳可能有一個任意大但有限的誤差，只要這個誤差的界限是已知的。假設1形式化了PCref（e）、PCi（e）和Ei（e）之間的預期關系。

假設1：物理時鐘誤差是有界的

?i, e : |PCre f(e)?PCi(e)| ≤ Ei(e)    --- (1)

也就是說，我們假設每個服務器的物理時鐘返回的物理時間戳的誤差都在由Ei（e）函數(shù)限定的范圍內(nèi)。這個假設是合理的，因為大多數(shù)NTP部署確實提供了相對master的最大誤差保證。Spanner的作者提到，TrueTime API做了類似的事情，盡管精度要高得多。值得注意的是，Ei（e）是一個進程相關的誤差函數(shù)，每個進程一個，該函數(shù)的輸出隨進程和時間而變化。

假設2: 物理時鐘時間戳在一個進程內(nèi)部是單調(diào)遞增的

?i, e, f : e → f ? PCi(e) ≤ PCi(f)   --- (2)

也就是說，當查詢服務器的物理時鐘的當前時間時，它從不輸出小于先前結果的值。同樣，這是合理的：可以將NTP配置為通過在相當長的時間段內(nèi)減慢或加快服務器時鐘來調(diào)整服務器時鐘，以確保依賴時間讀取的應用程序不會受到調(diào)整的很大影響。在某些情況下，NTP可能會向前或向后跳過時間，但這種情況非常極端，通過監(jiān)視NTP守護進程狀態(tài)很容易檢測到。當檢測到此類事件時，服務可以選擇自行關閉或故障停機。

在這些假設的基礎上，我們將介紹HybridTime所依賴的物理時間戳API，這些API是基于物理時鐘和NTP實現(xiàn)的。

3.2 HybridTime時鐘和協(xié)議

在本節(jié)中，我們將介紹HybridTime Clock（HTC）。HybridTime Clock時間戳是一個pair<physical,logical>，其中physical表示事件發(fā)生的物理時間，logical是邏輯序列號。算法2描述了HTC算法。

從HTC時鐘獲取時間戳的工作原理如下：每次需要為事件或消息分配時間戳時，會調(diào)用HTC.Now()函數(shù)來獲取最新的時間戳。這個“最新”時間戳的物理分量要么是從物理時鐘（PC）獲得的值，要么是存儲在最后一個物理時鐘中的值，以較大者為準。類似地，“最新”時間戳的邏輯值要么是0（如果選擇了當前PC值），要么是序列中的下一個邏輯值（如果選擇了最后一個物理值）。

更新HTC時鐘的工作原理如下：對于任何傳入的時間戳（算法2中的“in”）:

• 如果傳入值的物理分量低于HTC.Now()則不需要執(zhí)行任何操作
• 如果傳入值的物理分量等于HTC.Now()我們將next_logical設置為當前邏輯值和傳入邏輯值的最大值，再加一。
• 如果傳入值的物理分量高于HTC.Now()我們將last_physical設置為它，next_logical設置為傳入時間戳的邏輯組件加1。

我們隨后指出，如果將HTC時間戳解釋為一個簡單的字典式可比值，則算法2實現(xiàn)了Lamport時鐘，其附加優(yōu)點是生成的時間戳具有物理意義，并且在限定誤差范圍內(nèi)準確表示物理時間。

定義1: HCT（e）< HCT（f）被定義為時間戳二元組（物理、邏輯）的字典序。

算法1：The Physical Clock API

i = server id()
function NOW : int physical, int ε
    physical = PC_i(now)
    ε = E_i(physical)
    return p, ε
end function

算法2: The HybridTime Clock Algorithm

types:
    type Timestamp of {int physical, int logical}
var:
    int last_physical = 0
    int next_logical = 0
    PhysicalClock pc  ; 提供算法1的API
function NOW : Timestamp
    Timestamp now;
    int cur_physical = pc.now().physical;
    if cur_physical ≥ last_physical then
        now.physical = cur_physical;
        now.logical = 0
        last_physical = cur_physical;
        next_logical = 1;
    else
        now.physical = last_physical;
        now.logical = next_logical;
        next_logical++;
    end if
    return now;
 end function
 function UPDATE(Timestamp in) : void
    int Timestamp now = Now();
    if now.physical > in.physical then
        return;
    end if
    last_physical = in.physical;
    next_logical = in.logical + 1;
 end function

混合時鐘為事件保證了一定的順序：
定理1: HybriTime時鐘的happened-before關系構成了事件的總順序
定理1的證明是顯而易見的，因為我們使用字典序來排序事件。

雖然HybriTime時鐘并沒有直接利用時間測量誤差，但前面已經(jīng)說過這種測量誤差是有界的，因此算法不會隨著時間累積誤差。這一點很重要，因為如果沒有界限存在，那么時間戳的物理組成部分將變得毫無意義，而排序也只不過是用邏輯時鐘定義的順序。

我們首先定義HybridTime時間戳分配中的誤差。讓HTCi(f)表示一個HybridTime時鐘時間戳分配，其形式為二元組（物理、邏輯）值。讓t_real_f是f發(fā)生的“實時”時間，讓error(f)是HybridTime時鐘分配物理時間戳組件的誤差，即：error(f) = t_real_f ? HTCi(f).physical。
對于任何事件f，如果f從物理時鐘獲取其物理時間戳組件，由于假設1，我們知道在進程i（PCi()）讀取的任何物理時鐘都有函數(shù)Ei()給出的有界誤差，這意味著，在算法2中，如果事件取當前時鐘讀取的值（第11行），則其誤差等于從物理時鐘獲得的誤差。翻譯如下：

? f,i : HTCi(f).physical = PCi(f)
→ error(f) ∈ [?Ei(f),Ei(f)]

現(xiàn)在，我們將證明，即使事件采用其前面事件的物理時間戳組件，其誤差仍然是有界的：
定理2: 對于因果鏈f中的任何事件，HTC時間戳的物理分量近似于事件發(fā)生的“實時”時間，其誤差為：

?e, f,(e → f)
∧(HTCi(e).physical = PCi(e))
∧(HTCi(f).physical = HTCj(e).physical) ?
error(f) ∈ ]?Ej(e),Ei(f)[

附錄A中提供了定理2的完整證明。定理2解釋如下：如果分配給f的混合時間戳源于因果鏈中它前面的事件e，并且如果e的時間戳是從物理時鐘獲得的，那么將e的物理時間戳組件分配給f的物理時間誤差在(?Ej(e), Ei(f))之間。
這意味著，使用本地物理時鐘還是遠端節(jié)點j的物理時鐘的唯一區(qū)別是，誤差的區(qū)間左值受節(jié)點j中發(fā)生e事件時測量的誤差約束，而不是受本地誤差的約束。

4. 實現(xiàn)

我們在一個研究原型上實現(xiàn)了HybridTime和commit-wait外部一致性，并在類似于Spanner設計的實際場景中進行了一系列實驗。在這一部分中，我們介紹了研究原型數(shù)據(jù)庫的一致性模式、體系結構和事務語義。
我們的實現(xiàn)同時支持多種外部一致性模式?？蛻舳丝梢宰杂蛇x擇最適合該用例的模式，并為每個寫請求選擇一致性模式。支持以下一致性模式：

• 無一致性：在這種模式下，沒有外部一致性保證，事務從每個服務器的物理時鐘分配時間戳，并且不保證讀取是一致的或可重復的。

• HybridTime一致性：在這種模式下，我們使用HybridTime實現(xiàn)了與Spanner一樣的全局一致性(沒有隱藏通道)。在使用該一致性模型時，客戶端必須確保將從服務器接收到的時間戳傳播到其他服務器和客戶端。在同一個客戶端進程中，時間戳將代表用戶自動傳播。如果存在隱藏通道，即，如果寫入或讀取以沒有傳播時間戳，則無法保證外部一致性。

• Commit-wait一致性：在這種模式下，我們的實現(xiàn)通過使用提交等待（Commit wait）來保證與Spanner相同的外部一致性語義。然而，我們沒有使用TrueTime（它是一個專用的私有API），而是在廣泛使用的網(wǎng)絡時間協(xié)議（NTP）之上實現(xiàn)了提交等待。因此，在這種一致性模式下，我們支持隱藏通道。

這種靈活性意味著，當應用程序開發(fā)人員知道沒有隱藏的通道，或者愿意傳播時間戳時，他們不需要為commit-wait產(chǎn)生額外的開銷。但是，如果應用程序開發(fā)人員確實使用了外部通道（例如企業(yè)服務總線或外部web服務），他們可能會在這些情況下選擇性地應用commit-wait。根據(jù)作者在大型企業(yè)中使用大數(shù)據(jù)應用的經(jīng)驗，我們認為許多應用程序是完全封閉的系統(tǒng)，沒有隱藏的通道，因此絕大多數(shù)事務可以使用HybridTime一致性。

注意: 為了防止惡意客戶端操縱時鐘，生產(chǎn)環(huán)境下的實現(xiàn)應該使用諸如HMAC之類的方案來驗證時鐘值。

4.1 架構

我們省略了研究原型數(shù)據(jù)庫的完整實現(xiàn)細節(jié)，而是介紹了與不同一致性模式的實現(xiàn)相關的特性。我們的原型數(shù)據(jù)庫對key space進行了分區(qū)，并將這些分區(qū)分布在多臺機器上。這些分區(qū)類似于HBase中的regions或BigTable中的tablets。每個分區(qū)都有自己的副本組（Replica Group），通過類似Paxos的一致性算法來管理副本一致性，只有RG leader能處理寫請求。在目前的實現(xiàn)中，每個分區(qū)都支持本地事務，即對單個分區(qū)的更新符合ACID，但跨分區(qū)的更新不是原子的(a)或孤立的(i)（盡管它們是持久的(D)和一致的(C)）。因此，想要讀/寫多個分區(qū)，客戶端需要向每個分區(qū)發(fā)出獨立的請求。

我們使用MVCC來存儲每個數(shù)據(jù)的多個歷史版本，每個版本都標有寫入數(shù)據(jù)的時間戳，類似于BigTable或Vertica[14]/C-store[25]的設計。讀取操作被分配一個時間戳，并且總是讀取該時間戳之前最近寫入的版本，忽略任何將來或過去的數(shù)據(jù)。

4.2 事務類型

我們的原型支持三種類型的操作，我們使用與Spanner相同的術語：

1. Read-Write(RW) Transactions：RW事務包括所有改變現(xiàn)有數(shù)據(jù)的事務。一個RW事務之前可能有一個讀操作或一系列讀操作，并且需要在處理數(shù)據(jù)之前對每個要訪問的行加鎖。Spanner將RW事務分為兩類：需要訪問多個分區(qū)的事務和只需要訪問一個分區(qū)的事務（Single RG Transaction）。在本文中，我們只實現(xiàn)和評估了后者，但解釋了如何用HybridTime實現(xiàn)前者。
2. Snapshot Transactions：Snapshot Transactions是針對當前數(shù)據(jù)的無鎖只讀事務。也就是說，客戶端請求某組數(shù)據(jù)的最新狀態(tài)。然而，由于這些行可能跨越不同的分區(qū)，甚至數(shù)據(jù)中心，節(jié)點需要一致同意什么是當前數(shù)據(jù)，以及哪些數(shù)據(jù)是在當前之前提交的。
3. Time-travel Read：Time-travel Read是針對過去數(shù)據(jù)的無鎖只讀事務。也就是說，客戶端請求的是過去某個物理時間點的某組數(shù)據(jù)的狀態(tài)。同樣，因為這些數(shù)據(jù)行可能跨越不同的分區(qū)或數(shù)據(jù)中心，所有參與的節(jié)點都需要就在選定的過去這個時間點之前提交了哪些操作達成一致。

值得注意的是，從客戶端的角度來看，Snapshot Transactions和Time-travel Read之間的概念區(qū)別只是前者需要被分配一個與當前事務相對應的時間戳，而后者將其時間戳選為某個過去的時間點。由于這一點，在我們的實現(xiàn)中，我們只區(qū)分寫事務和讀事務，前者修改數(shù)據(jù)并為本次修改分配一個所有節(jié)點都同意的時間戳，后者在某個一致的時間點快照上執(zhí)行讀操作。Read-Write(RW) Transactions雖然從數(shù)據(jù)庫的角度來看很有趣，但是在HybridTime的實現(xiàn)上沒有什么區(qū)別，因為唯一相關的區(qū)別是它們經(jīng)歷了一個讀階段，在這個階段中讀鎖是在寫階段之前獲得的。

深入研究Spanner等數(shù)據(jù)庫中的“外部一致性”概念，我們發(fā)現(xiàn)它非常接近兩個基本概念：i）操作必須作用于并產(chǎn)生一致的全局狀態(tài)[12]（CGS）；ii）操作必須是原子的，即當在單個事務下對多個分區(qū)執(zhí)行操作時，某個觀察者能同時觀察到所有這些分區(qū)都產(chǎn)生了變更。實際上，i）意味著，如果一個客戶端執(zhí)行事務A，該事務涉及一組機器，然后執(zhí)行另一個獨立事務B，該事務涉及另一組不相交的機器，則其他客戶端只能觀察事務序列：[], [A], [A, B]。由于A和B是因果關系，所以序列[B]不是CGS，不應被觀察到。另一方面ii）意味著如果一個客戶端在一個分區(qū)上執(zhí)行操作C，在另一個分區(qū)上執(zhí)行操作D的事務，另一個客戶端只能觀察[]或[C, D]。

為了清晰起見，我們省略了這樣一個事實：在幾乎所有的消息交換中，客戶端向服務器發(fā)送和從服務器接收它們最后一個已知的HT時間戳。類似地，這發(fā)生在服務器之間，區(qū)別在于服務器可以從HT時鐘讀取和發(fā)送當前值，而客戶端不能獲取HT，只能傳播從其他服務器接收的HT時間戳。

4.3 Write Transactions

使用HybridTime執(zhí)行Write Transactions與在Spanner中執(zhí)行RW事務有相似之處。對于單個分區(qū)的Write事務，該分區(qū)的RG leader（Replica Group Leader）首先獲取所有相關鎖，然后為事務分配一個時間戳ts(ht)。當副本復制事務時，它們根據(jù)第3.2節(jié)中介紹的更新規(guī)則更新其HT時鐘。一旦leader收到大多數(shù)復制確認，它就會應用更改，認為事務已提交，并通知客戶客戶端。因為對于每個事務，參與副本的HT時鐘都會更新，所以它們同意ts(ht)x是過去的，這與執(zhí)行讀事務相關。由于所有Single RG Transaction都必須經(jīng)過leader，因此可以保證，如果事務B在事務a的時間戳之后分配了一個時間戳，那么所有副本都將同意B跟在a之后。

涉及多個分區(qū)的事務需要一個協(xié)調(diào)器RG（coordinator RG），該協(xié)調(diào)器在每個分區(qū)RG的一致協(xié)議之上執(zhí)行兩階段提交協(xié)議。在收到客戶端的請求后，協(xié)調(diào)器RG的leader向所有參與者RG發(fā)出Prepare命令。每個參與者RG（participant RG）的leader獲取相關鎖并用其當前的HT時間戳進行應答。然后協(xié)調(diào)器RG leader選擇接收到的時間戳中最高的一個，并將該時間戳分配給事務，在它向參與者RG leaders發(fā)送Apply命令時附帶這些信息。在收到所有參與者已應用該事務的確認后，協(xié)調(diào)器RG負責人回復客戶端。注意，在Spanner中，客戶端驅(qū)動兩階段提交協(xié)議。這在這里也是一個類似的選擇，但為了簡單起見我們省略了這個選項。

客戶端在每一個后續(xù)請求時都會攜帶從任何服務器獲得的最后一個已知時間戳，很容易看出，根據(jù)HT時鐘更新規(guī)則，從同一客戶端啟動到不同分區(qū)的順序事務具有順序時間戳，從而保證了所需的“全局一致性”屬性。如果交易有因果關系，但其因果關系是通過隱藏渠道（即最后已知的HT時間戳未傳播的渠道）建立的，例如，客戶端1執(zhí)行交易A，然后通過隱藏渠道使客戶端2執(zhí)行交易B，單靠時鐘不能保證外部一致性。在這種情況下，用戶可以顯式地啟用commit-wait來執(zhí)行事務A，從而以提交延遲為代價來確保外部一致性屬性。如果客戶端1在通道上通信之前執(zhí)行了許多寫事務，則它們可以只在這些事務的最后一個操作上啟用commit-wait，以便在對總體性能影響不大的情況下實現(xiàn)相同的一致性。

4.4 Read Transactions

所有讀取事務都在全局狀態(tài)的一致快照上執(zhí)行，而不需要獲取鎖。單節(jié)點讀取通過實現(xiàn)多版本并發(fā)控制[3]（MVCC）來實現(xiàn)這一點，這是一種眾所周知的數(shù)據(jù)庫技術?？蛻舳丝梢赃x擇為事務指定時間戳，也可以不指定時間戳，在這種情況下，事務將以最新的狀態(tài)執(zhí)行。對于訪問單個分區(qū)的讀事務，如果客戶端沒有指定時間戳，則事務將由該分區(qū)的RG leader執(zhí)行，因為它是唯一保證具有最新狀態(tài)的節(jié)點。當接收到來自客戶端的請求時，leader為事務分配一個HT時間戳，對應于從HT時鐘獲得的最新時間戳，獲得MVCC快照并執(zhí)行事務。對于單個分區(qū)的read事務，客戶端可以指定一個過去的時間戳。RG中的副本需要在固定的、預先配置的時間間隔內(nèi)跟上主機，否則將被逐出。這意味著，如果客戶端希望讀取某個時間點的數(shù)據(jù)，并且知道該時間點相較于目前的時間差大于副本之間同步的最大時間差，它可以將請求路由到任何副本，而不必強制將請求路由到leader，因為它可以保證，如果副本仍在活動狀態(tài)，它將包含包括請求時間點之前的所有數(shù)據(jù)。如果客戶端指定的時間點比前面提到的時間段更近，則事務將被路由到leader。跨多個分區(qū)的Read事務的執(zhí)行方式與單個分區(qū)的事務非常相似，但有一些細微差別。如果客戶端沒有提供時間戳，或者如果指定的時間戳與當前非常接近，以至于它落在至少一個副本的最大物理時間測量誤差（通常設置為1秒）之內(nèi)，則必須執(zhí)行初始協(xié)商回合，其中客戶端從所有參與者獲得當前時間戳并選擇最舊的作為快照的時間戳。然后，讀事務繼續(xù)進行，就像在單個分區(qū)情況下一樣。在這種情況下，Spanner的作者選擇讓客戶端在所有情況下選擇時間戳，這避免了最近事務的初始協(xié)商回合，但可能會迫使讀取事務等待所選時間戳是安全的（即肯定是在過去）。我們選擇不采用這種方法，因為客戶端可能經(jīng)常運行在不同步的機器上。由于在本文中沒有足夠的時間，我們沒有實現(xiàn)協(xié)商階段，在協(xié)商階段，客戶端從leader那里獲得最新的時間戳，而將我們的評估重點放在單個分區(qū)Read事務上。我們注意到，Spanner論文也沒有衡量這類事務，我們沒有進行比較的依據(jù)。

5. 實驗和評估

在本節(jié)中，我們將展示我們的實驗結果和搭建過程，并演示HyBrid Time如何跟commit-wait以前使用，以及它在延遲方面的比較。

5.1 壓力測試工具

我們使用眾所周知的YCSB[6]作為所有實驗的壓力測試工具。我們使用了最多三個并發(fā)的客戶端，每個運行8個線程，其中60%是插入，20%是更新，20%是單行讀取。這三個客戶端對應于三種不同的一致性模式：每個客戶端使用一種模式執(zhí)行所有寫操作。

5.2 實驗配置

我們在Google Compute Engine中進行了所有實驗。所有實驗均在美國中部1-a和歐洲西部1-a“區(qū)域”進行。在每個“區(qū)域”中，我們組裝了10臺n1-standard-8型機器。這種類型的機器有8個“虛擬CPU”，每個CPU對應于“2.6GHz Intel Sandy Bridge Xeon或Intel Ivy Bridge Xeon（或更高版本）處理器上的單個超線程”，因此，更準確地說，每臺機器都有4個帶超線程的內(nèi)核。每臺機器也有30GB的內(nèi)存，我們在每臺機器上附加了一個容量為350GB的“持久磁盤”，格式化為ext4格式，我們在其中存儲數(shù)據(jù)庫的持久數(shù)據(jù)和WAL日志。我們的原型數(shù)據(jù)庫運行在Linux上，因此每臺機器都被引導到debian-7-wheezy映像。操作系統(tǒng)安裝到與存儲該數(shù)據(jù)庫數(shù)據(jù)的分區(qū)不同的磁盤分區(qū)。

服務器運行NTP版本為4.2.6，并修改如下配置：

• 時間服務器配置為Google Compute Engine提供的時間服務器。我們假設這個時間服務器與我們進行測試用的服務器在一個數(shù)據(jù)中心，從而提供較低的RTT和良好的時鐘質(zhì)量。我們相信，大多數(shù)數(shù)據(jù)中心在短時間內(nèi)就已經(jīng)有了NTP源，隨著使用HybridTime等技術的數(shù)據(jù)庫變得越來越普遍，云提供商會將高質(zhì)量的NTP服務器作為標準基礎設施。
• 最大輪詢間隔設置為8秒，以確保時鐘誤差邊界經(jīng)常同步。
• Allan intercept配置修改為8秒。

這些非標準配置降低了時鐘誤差同時也降低了實際時鐘精度。也就是說，因為頻繁的時鐘同步帶來的抖動對會影響實際時鐘質(zhì)量，但是提供給內(nèi)核的最大誤差會持續(xù)保持在比較小的范圍。對于HybridTime這樣的系統(tǒng)，與較小的平均時鐘偏移相比，更嚴格的誤差限制對應用程序更有好處。下表顯示了我們從集群中提取的一個和兩個數(shù)據(jù)中心的最大錯誤差：

除非明確說明，所有實驗結果都是在啟用了完全持久性的情況下獲得的，也就是說，如果系統(tǒng)沒有為客戶端的數(shù)據(jù)調(diào)用fsync()/fdatasync()，則數(shù)據(jù)不可見，從而將機器崩潰時丟失數(shù)據(jù)的機會就降到了最低。這與一些廣泛使用的大型數(shù)據(jù)庫的設置不相上下，例如Cassandra使用一個后臺線程周期性地調(diào)用fsync()，在發(fā)生斷電時就存在一個丟失數(shù)據(jù)的時間窗口，而撰寫本文時HBase還沒有“適當?shù)膄sync支持”。

由于我們的實驗室在IaaS上進行的，所以我們無法獲得存儲系統(tǒng)的硬件/軟件布局，因此無法完整描述Google Compute Engine中的“持久磁盤”是如何實際實現(xiàn)的。但是，由于持久性通常是任何數(shù)據(jù)庫的主要關注點，而fsync()系統(tǒng)調(diào)用通常需要在硬件上完成，因此我們對存儲介質(zhì)的延遲特性進行了一些測量，在這些介質(zhì)中，我們保存了數(shù)據(jù)和WAL。我們使用“flexible I/O tester”基準測試工具，配置了有2個writer和2個reader，每個writer對每個寫操作進行fsync()/fdatasync()調(diào)用，寫入塊大小時1KB，與數(shù)據(jù)庫基準工作負載中的一行大小大致相同。對于本文來說，最相關的結果是寫延遲，因為它們可能代表了total request time的一個重要部分，測試結果是（毫秒）：min=1，max=39，avg=1.93，stdev=2.08。這意味著，平均而言，每個客戶端請求將花費至少2毫秒的時間等待I/O，這是我們在下一節(jié)描述的實驗中的一個重要因素。

5.3 實驗1：Single datacenter, no consensus

實驗1的目標是揭示每種一致性模式對請求延遲的影響，而不考慮其他數(shù)據(jù)庫問題，如持久性或容錯性，因為滿足這兩個需求對數(shù)據(jù)庫性能有很大的影響。我們在這個實驗中要回答的問題是，撇開其他數(shù)據(jù)庫問題不談，不同一致性模式的獨立影響是什么：no consistency、HybridTime consistency、Commit-Wait consistency在total request latency上的不同。因此，對于這個實驗，我們禁用了fsync()調(diào)用，依靠操作系統(tǒng)緩沖區(qū)來最好地選擇實際保存數(shù)據(jù)的時間。此外，對于這個實驗，我們禁用了一致性復制，從而將客戶端請求中的數(shù)據(jù)寫入單個節(jié)點。

<img src='2.png' width='60%'/>

<center>圖1</center>

我們在單個數(shù)據(jù)中心的10節(jié)點集群上執(zhí)行了實驗1。圖1顯示了我們獲得的主要結果。圖1中的圖表描繪了與時鐘誤差重疊的每種一致性模式在服務器上測量的任意時間段的延遲。延遲時間是移動平均值，每個數(shù)據(jù)點表示自上一個數(shù)據(jù)點以來的平均延遲（以微秒為單位）。no consistency、HybridTime consistency這兩種模式的平均延遲在100微妙（0.1毫秒）以內(nèi)，Commit-Wait consistenc則在25000微妙（25毫秒）以上。
圖3中的圖表描繪了在YCSB客戶端上測量的50%、75%、90%、99%和99.9%的延遲直方圖。no consistency、HybridTime consistency 99%的請求都能在2毫秒返回。而Commit-Wait consistenc 99%的請求在30毫秒內(nèi)返回。

一個重要的結論是HybridTime的一致性對延遲幾乎沒有影響。盡管是預期的，但這表明，正如所聲稱的那樣，通過簡單地要求客戶端傳播單個時間戳，就可以通過混合時間獲得Commit-Wait相同的一致性好處。這兩個圖表的另一個好處是，撇開持久性和復制性，時鐘錯誤對Commit-Wait一致性的總延遲有非常大的影響。Commit-Wait一致性請求比非Commit-Wait請求慢2個數(shù)量級（沒有fsync和replication），最大的時鐘誤差是我們能夠從傳統(tǒng)的NTP設置中提取出來的，盡管稍微做了一些調(diào)整。正如預期的那樣，Commit-Wait請求的延遲與時鐘誤差密切相關，并隨時鐘誤差的變化而增減。這可以作為以下實驗的基線。

另一個非常重要的結論是，雖然我們能夠從NTP獲得的最大時鐘誤差值高于TrueTime和Spanner的最大時鐘誤差值（11-15毫秒vs.5-7毫秒），但它們并不高很多，通常是2-2.5倍。雖然兩倍的時間是重要的，我們注意到，我們使用公共服務器來同步時間主機，而時間主機本身的最大錯誤是6-9毫秒。我們認為，這意味著，使用commit-wait的設置與典型的NTP協(xié)議一起使用，同時保持延遲時間接近Spanner中的延遲時間，這不僅是合理的，而且是可能的，例如，對于具有公共、良好時間源的足夠近的數(shù)據(jù)中心。

5.4 實驗2：Single datacenter with consensus

對于實驗2，我們評估了啟用了持久性和一致性復制的請求延遲。我們的目標是通過這個實驗回答兩個問題：i）在啟用復制和持久性的情況下，commit-wait一致性模式在整個request time中所占的時間百分比；ii）在某些情況下，是否HyBridTime一致性成為首選選項。

<img src='4.png' width='60%'/>

<center>圖2</center>

圖2中的圖表再次描繪了與時鐘誤差重疊的每個一致性模式在任意時間段內(nèi)的延遲。在圖2中可以看到，即使啟用了持久性和復制，HyBridTime一致性請求完成所需的時間（2.5ms)比commit-wait請求(30ms)少一個數(shù)量級。事實上，HybridTime請求完成所需的時間是Spanner論文中報告的單個副本組寫入所需時間的5倍左右，這使得HybridTime成為延遲敏感場景中的一個可能選擇，即使TrueTime之類的精確時鐘也是可能的。

圖2顯示，即使有一個完整的數(shù)據(jù)庫堆棧，commit-wait一致性請求的許多時間仍要花費在等待時鐘誤差。也就是說，即使是將數(shù)據(jù)傳輸?shù)狡渌?jié)點（在應答之前必須調(diào)用fsync()）和本地WAL，99.9%的請求花費86%的時間等待時鐘誤差。我們不直接將等待時間與Spanner上公布的數(shù)字進行比較，因為它們是單副本、無提交等待的，請求時間比我們的數(shù)據(jù)庫原型開啟了一致性副本的時間還要高。我們推測這可能是由于在Spanner中實現(xiàn)的其他功能尚未發(fā)布，或者我們的研究原型還不支持，比如多分區(qū)寫入事務。

5.5 實驗3：Two datacenters

對于實驗3，我們將我們的原型數(shù)據(jù)庫部署到兩個不同的數(shù)據(jù)中心，并讓每個數(shù)據(jù)中心的客戶端寫入所有分區(qū)。這個實驗的目的是為了證明，和Spanner的commit-wait一樣，HybridTime也可以在geo-distributed集群上工作，并且YCSB客戶端的吞吐量對于HybridTime一致性比commit-wait一致性要高得多。

<img src='4.png' width='60%'/>

<center>圖3</center>

圖3顯示了實驗3的延遲數(shù)據(jù)正態(tài)直方圖。這個實驗的一個重要結論是，HybridTime不僅顯示出較低的延遲值，而且這些值也更穩(wěn)定，例如，在YSCB中，25%的請求屬于同一個bin。這是有意義的，因為commit-wait延遲隨時鐘誤差而變化，而HybridTime延遲僅取決于服務器實現(xiàn)，這表明當延遲需要遵循嚴格的sla時，HybridTime可能是更好的選擇。

在整個實驗評估過程中，我們沒有關注吞吐量，因為吞吐量高度依賴于服務器和客戶端的數(shù)量，但是值得一提的是，使用HybridTime一致性的單個YSCB客戶端的吞吐量大約是使用commit-wait一致性的客戶端的20倍。

6. 結論

本文介紹了一種新的全局一致性算法：HybridTime，該算法基于NTP的時間同步之上進行實現(xiàn)，相較于Spanner的commit-wait，延遲低了一個數(shù)量級。HybridTime為全局分布式數(shù)據(jù)庫的事務提供了happend-before排序特性及誤差邊界，同時提供了物理上有意義的時間戳，以支持point-in-time查詢。我們還演示了如何在廣泛使用的NTP協(xié)議之上實現(xiàn)commit-wait一致性，雖然相較于Spanner延遲更差，但在同一數(shù)量級內(nèi)。此外，我們還展示了HybridTime和commit wait可以共存于同一個系統(tǒng)中，以便用戶可以根據(jù)需要自由選擇。如果可能存在隱藏通道，那么commit-wait是更好的選擇，也是唯一一個確保全局一致性的方法，代價是響應客戶端請求的速度慢1個數(shù)量級。另一方面，如果系統(tǒng)是封閉的，并且沒有隱藏的通道，那么HybridTime可以提供整個集群的一致性，即使對于地理分布的集群也是如此，且延遲要低得多。

附錄A - HybridTime時間戳分配的誤差有界性證明

證明：設e為在節(jié)點i發(fā)生事件f之前發(fā)生在節(jié)點j的事件，其時間戳隨消息一起傳輸并用于調(diào)用HTC.Update(). 假設e的物理時間戳組件高于PCi(f)，使得算法2中第24行中的測試通過，使得最后一個物理時間戳的值被更新為e的物理時間戳組件的值，并且隨后被分配為fs物理時間戳。
如果e的時間戳是從物理時鐘（PCj(e)）獲得的，那么，由于假設1，e發(fā)生的real時間必須在以下時間間隔內(nèi)：

t_real_e ∈ [PCj(e)?Ej(e),PCj(e) +Ej(e)]     ---- (5)

我們也知道，f發(fā)生的real時間是在如下區(qū)間內(nèi)：

t_real_f ∈ [PCi(f)?Ei(f),PCi(f) +Ei(f)]     ---- (6)

我們知道，e和f發(fā)生的順序如為：e → f，因此e和f的real時間之間的關系如下：

t_real_f > t_real_e                          ---- (7)

由于e → f，從（5）和（7）我們可以斷言t_real_f必須發(fā)生在e的最早可能值之后，即：

PCj(e)?Ej(e) < t_real_f                      ---- (8)

在區(qū)間的右側，我們可以斷言t_real_f一定發(fā)生在PCi(f)+Ei(f)之前，即：

t_real_f ≤ PCi(f) +Ei(f)                     ---- (9)

將(8)和(9)結合在一起，我們得到：

PCj(e)?Ej(e) < t_real_f ≤ PCi(f) +Ei(f)      ---- (10)

如果我們從(10)的不等式中減去分配給f時間戳物理分量的值PCj(e)，我們得到：

?Ej(e) < t_real_f ?PCj(e) ≤ PCi(f)?PCj(e) +Ei(f)    ---- (11)

由于我們選擇了PCi(e)作為f的物理時間戳，即（HTCi(f).physical=HTCj(e).physical)∧(HTC(e).physical=PCi(e)），我們從算法2知道：

PCi(f) < PCj(e)                              ---- (12)

從(12)我們知道PCi(f)?PCj(e)<0，HTCi(f).physical=PCj(e)，我們之前將error(f)定義為t_real_f?HTCi(f)，因此(11)變?yōu)椋?/p>

?Ej(e) < error(f) < Ei(f)                    ---- (13)

也就是說在時間戳分配時，將PCi(e)作為f的時間戳的物理部分引起的絕對誤差為：

error(f) ∈ (?Ej(e),Ei(f))                   ---- (14)

參考

[1] HBase. https://hbase.apache.org/.

[2] ALMEIDA, S., LEITAO? , J., AND RODRIGUES, L. ChainReaction: a causal+ consistent datastore based on chain replication.the 8th ACM European Conference (Apr. 2013), 85–98.

[3] BERNSTEIN, P. A., AND GOODMAN, N. Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13, 2 (June 1981), 185–221.

[4] CHANG, F., DEAN, J., GHEMAWAT, S., HSIEH, W., AND WALLACH, D. Bigtable: A distributed storage system for structured data. Proceedings of the 7th USENIX Symposium on Operating Systems Research (Jan. 2006).

[5] COOPER, B., RAMAKRISHNAN, R., SRIVASTAVA, U., SILBERSTEIN, A., JACOBSEN, H.-A., PUZ, N., WEAVER, D., AND YERNENI, R. PNUTS: Yahoo!’s hosted data serving platform. Proceedings of the VLDB Endowment 1, 2 (Aug. 2008).

[6] COOPER, B. F., SILBERSTEIN, A., TAM, E., RAMAKRISHNAN, R., AND SEARS, R. Benchmarking cloud serving systems with YCSB. the 1st ACM symposium (June 2010), 143–154.

[7] CORBETT, J. C., DEAN, J., EPSTEIN, M., FIKES, A., FROST, C., FURMAN, J. J., GHEMAWAT, S., GUBAREV, A., HEISER, C., HOCHSCHILD, P., HSIEH, W., KANTHAK, S., KOGAN, E., LI, H., LLOYD, A., MELNIK, S., MWAURA, D., NAGLE, D., QUINLAN, S., RAO, R., ROLIG, L., SAITO, Y., SZYMANIAK, M., TAYLOR, C., WANG, R., AND WOODFORD, D. Spanner: Google’s Globally Distributed Database. Transactions on Computer Systems (TOCS 31, 3 (Aug. 2013).

[8] DAVIS, J. IBM/DB2 Universal Database: Building Extensible, Scalable Business Solutions., 1999.

[9] DECANDIA, G., HASTORUN, D., JAMPANI, M., KAKULAPATI, G., LAKSHMAN, A., PILCHIN, A., SIVASUBRAMANIAN, S., VOSSHALL, P., AND VOGELS, W. Dynamo: amazon’s highly available key-value store. SOSP ’07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles (Oct. 2007).

[10] FIDGE, C. J. Timestamps in message-passing systems that preserve the partial ordering. In Proceeding of the th Australian Computer Science Communication (1988).

[11] HERLIHY, M. P., AND WING, J. M. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (July 1990), 463–492.

[12] KEITH MARZULLO, K. M. Consistent global states of distributed systems: Fundamental concepts and mechanisms. Distributed Systems (1993).

[13] LAKSHMAN, A., AND MALIK, P. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review 44, 2 (Jan. 4), 35–40.

[14] LAMB, A., FULLER, M., VARADARAJAN, R., TRAN, N., VANDIVER, B., DOSHI, L., AND BEAR, C. The vertica analytic database: C-store 7 years later. In Proceedings of the VLDB Endowment (Aug. 2012), VLDB Endowment.

[15] LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, 7 (July 1978).

[16] LAMPORT, L. Paxos made simple. ACM SIGACT News (2001).

[17] LEE, J. W., LOAIZA, J., STEWART, M. J., HU, W.-M., AND WILLIAM H BRIDGE, J. Flashback database.

[18] LLOYD, W., FREEDMAN, M. J., KAMINSKY, M., AND ANDERSEN, D. G. Don’t settle for eventual: scalable causal consistency for wide-area storage with COPS. SIGMOD ’05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data (Oct. 2011), 401–416.

[19] LOMET, D., BARGA, R., MOKBEL, M. F., SHEGALOV, G., WANG, R., AND ZHU, Y. Immortal DB: transaction time support for SQL server. In SIGMOD ’05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data (June 2005), ACM, pp. 939–941.

[20] MATTERN, F. Virtual Time and Global States of Distributed Systems. Parallel and Distributed Algorithms (1989).

[21] MILLS, D. L. Network Time Protocol (NTP). Network (1985).

[22] PENG, D., AND DABEK, F. Large-scale incremental processing using distributed transactions and notifications. In OSDI’10:Proceedings of the 9th USENIX conference on Operating systems design and implementation (Oct. 2010), USENIX Association.

[23] RAO, J., SHEKITA, E. J., AND TATA, S. Using Paxos to build a scalable, consistent, and highly available datastore. In Proceedings of the VLDB Endowment (Jan. 2011), VLDB Endowment.

[24] STOLLER, S. D. Detecting global predicates in distributed systems with clocks. Distributed Computing 13, 2 (2000), 85–98.

[25] STONEBRAKER, M., ABADI, D. J., BATKIN, A., CHEN, X., CHERNIACK, M., FERREIRA, M., LAU, E., LIN, A., MADDEN, S., O’NEIL, E., O’NEIL, P., RASIN, A., TRAN, N., AND ZDONIK, S. C-store: a column-oriented DBMS. VLDB Endowment, Aug. 2005.

[26] WEI, Z., PIERRE, G., AND CHI, C.-H. CloudTPS: Scalable Transactions for Web Applications in the Cloud. Services Computing, IEEE Transactions on 5, 4 (2012), 525–539.

[27] ZHANG, C., AND DE STERCK, H. HBaseSI: Multi-row Distributed Transactions with Global Strong Snapshot Isolation on Clouds. Scalable Computing: Practice and Experience 12, 2 (Jan. 2011).

MemFireDB，帶你體驗不一樣的云端飛翔。