從CockroachDB看分布式資料庫系統的一緻性

最近仔細研究了下CockroachDB的相關文檔和paper，感覺在市場上衆多的NewSQL分布式資料庫系統中，它對于資料的一緻性追求應該是最為極緻的，由此也回顧了下分布式系統下，所謂的一緻性相關概念，由于每次思考起這個東西總感覺有些燒腦，經常會反複走入同一個思維誤區，這裡感覺記錄下自己目前的了解，個人感覺應該是準确的，如果大家看到不對的地方歡迎指正。

背景

曆史上，資料庫和分布式系統是兩個不同的研究群體，他們各自形成了對于資料一緻性(Consistency)的不同了解，這也是為什麼大家會經常感到迷惑的原因。這裡先大概說一下

1. 資料庫研究群體主要關注的是在單個主機的情況下，多個并發事務同時操作的情況下，如果保證資料庫系統中資料項的一緻性，包括：實體上資料不被破壞，資料的限制（唯一性限制，引用限制），或者業務限制（x + y == 10) 不被破壞。
2. 分布式系統主要關注在跨網絡互相連接配接，且資料有多副本複制的叢集中，對于邏輯上單個資料項（可能有多個實體副本）的操作，能否和單機系統中對于單個資料項操作的效果一樣，始終看到正确的符合操作順序的資料結果。

随着網際網路和大資料的興起，這兩個研究群體在不斷融合，而關于資料一緻性的問題又進一步變複雜了，現在問題變成了，在一個分布式叢集中，并發執行若幹事務（多個資料項的操作集合），系統最好能同時滿足以上兩類一緻性的要求。

這篇文章會先從分布式系統的一緻性說起，我們先簡化問題，考慮單個資料項（比如單個Key)的操作，再擴充到事務系統，最後看下業界不同系統實作的情況。

分布式系統的一緻性問題

在單機環境下，如果有兩個線程并發操作同一個記憶體位址的資料（對齊讀寫保證操作原子性），底層的作業系統核心和硬體協同可以保證，對于該資料的并發寫入不會沖突，且兩個寫操作的執行順序和他們在實體時間上的順序一緻。這一點非常重要，正是有了這種操作原子性和順序性的保證，程式員在編寫代碼時可以做出一些很明确的假設：

假設線程1先執行 x = 2，線程2後執行x = 3，最後線程3讀取x一定得到3。

可以看到先 -> 後 -> 最後這個幾個關鍵字，這隐含表示了操作間的順序和實體時間順序是一緻的！！

到了分布式系統中，前面這種看起來想當然的事情就不那麼容易了，因為節點之間産生了通信，而通信是要有時間消耗的：

如果光具有無限大的速度，我們可以認為任何通信都在瞬間完成，那麼可以達成和前面單機中一樣的效果：

t1下發的 x = v1的操作瞬間完成并傳回了，t2、t3時刻也依次完成了操作，很明顯操作執行的順序和實體時間順序是一緻的。

不幸的是，現實情況可能是這樣：

從start -> end之間的錐形（參見DDIA）描述了操作的發起和響應過程。可以看到操作1的[start1 -> end1] 和 操作2的[start2 -> end2]之間是有重疊的，由于網絡延遲等因素，根本無法确定兩個操作的先後順序，但是[start1 -> end1] 和操作3的[start3 -> end3]之間則沒有overlap，很明确的是，實體時間上操作3一定是在操作1完成後才發生的，那麼作為最接近單機一緻性的要求，我們可以要求操作3産生的效果也一定在操作1之後，這個要求就是所謂的線性一緻性(linearizability)，即：如果一個操作op2的開始是在另一個操作op1的結束之後，則系統應該觀察到的效果是op1先生效，op2後生效。

上面的例子是針對單個key值的，但線性一緻的定義并不限于隻對同一個key的操作，比如操作1是針對key1，操作3針對key3，以上的要求仍然需要成立。

線性一緻性是分布式系統所能達到的最接近單機系統的最強一緻性模型(單機或者理想分布式（瞬間通信）下，操作是[t1 -> t1] [t2 -> t2]，不會重疊)。

注意這裡有個思維陷阱：

從系統自身的角度，它看到了v2的寫入是先于v1的，但由于實際的操作間隔有重疊，這兩個操作的順序并沒有要求，也就是說，對于系統來說，并不是要求所有操作的順序都和達到系統的實體時間順序一緻，隻是操作1和操作3這兩個事件之間由于有因果關系，順序是要有保證的！

那麼怎麼能知道操作之間是否存在因果關系呢？答案是，系統無法知道，但它又被要求不能破壞這種因果順序，是以系統能做的是，反向保守處理，通過避免操作的潛在重疊可能來建立所有操作間的全序，這麼說可能有些抽象，看了下面的spanner和cockroachDB的例子就應該清楚了。

分布式系統的時間概念

很明顯線性一緻性和實體時間有着緊密的關聯，而麻煩的是，一旦涉及到分布式系統，時間的概念就不再準确了，因為所有的節點并不共享一個全局的實體時鐘，假設每個node都能看到一個假想的，挂在某個位置的時鐘，那跨越節點界定不同僚件的實際順序也非常容易，但這東西并不存在，不過思路确實是朝着這個方向的，人們希望能有方法盡量接近“全局統一時鐘”。

Timestamp Oracle

這是最顯而易見的思路，也是最簡單的，任何操作都要先到一個統一的節點上擷取時間戳，隻要這個節點可以保證自身配置設定的時間戳單調遞增，那它就是那個“全局共享時鐘”，但缺點也很明顯，首先是單點瓶頸，其次任何操作都要先和它互動，這會增加round trip的延遲，如果這個全局唯一節點是部署在不同region，這個延遲在實際應用中很難接受。

TrueTime

這個google spanner采用的方案，倚仗google強大的軟硬體基礎設施能力，利用原子鐘和gps交叉同步，google建立了人類最接近“全局共享時鐘”的分布式時鐘機制，不同節點上的時間戳的偏差最大隻有7ms。

軟體同步時鐘

TrueTime是硬體保障的時鐘同步機制，而如NTP或者Amazon Time Sync Service這樣的軟體同步機制，雖然遠遠達不到相同的誤差精度，但其思路也還是一緻的：盡可能使各節點上的時鐘偏差在一個有界的範圍内。

一旦有了某種形式的時鐘，我們就可以結合MVCC為資料的操作打上一個時間戳(timestamp），不同操作産生不同版本的資料，用這個時間戳描述資料的産生時間，進而界定操作之間的順序和資料的可見性。

擴充到資料庫系統

前面已經描述了分布式系統下，單個資料庫對象的操作語義，而且資料庫領域，事務是針對多個資料項的操作的集合，事務的ACID特性要求每個事務的操作要麼全部發生，要麼全部不發生。

對于事務來說，可串行化(serializability)是最為嚴格的一緻性語義，即事務的執行雖然實際是并發的，但其執行效果等價于事務以某種串行的順序依次發生。可串行化可以阻止所有并發事務造成的異常情況(anomalies)，進而保證資料的正确性（一緻性）。

那麼在分布式資料庫系統中，涉及到分布式環境下的最強的一緻性定義又是什麼呢？首先我們仍然需要串行化的隔離級别，這樣可以保證每個事務就可以視作是原子性的操作。然後就是事務（原子性操作）之間的順序又該怎麼規定呢？和單對象操作一樣，如果事務1結束後，事務2才開始，那麼可以系統要求看到的操作順序也是： 先看到事務1生效，再看到事務2生效。但如果兩個事務的執行間隔是有重疊的（從發起者的角度，類似上圖的[start1, end1]和[start2, end2]），則對兩者的執行順序不做要求。

這裡我覺得CockroachDB的strict serializability是一個非常不錯的術語，感覺linearizability更适合描述傳統分布式系統中單對象的操作行為，而strict serializability更接近事務serializability的含義，在可串行化排程的基礎上，進一步限制的事務的具體順序與實體時間之間的關系，但本質上兩個術語可以認為是等價的。

業界各類實作方案

TiDB

TiDB采用了最為簡單的Timestamp Oracle的方案，是以在擴充性和跨地域部署上受到了很大限制，目前TiDB5.0的全球資料庫并不具有真正意義上的跨地域寫入能力。

Spanner

Spanner自然采用了TrueTime的基礎設施，由于不同節點間，在時間戳上的最大誤差就是7ms，是以其采用了commit wait的方式，來保證完全的strict serializability。（google稱為外部一緻性，表示系統能夠遵從系統外部的因果事件的先後順序，也是很貼切的術語）

commit wait的原理其實很簡單，如下圖：

假設事務1在t1這個時間戳時可以送出了，由于節點上的時間戳是有不确定區間的，實際的實體時鐘可能在第1個區間内的任意點上，那麼如果在t1時間戳上立即向用戶端傳回commit成功，用戶端收到後立即下發第二個事務，那麼從線性一緻的角度，這個事務2的時間戳一定要大于t2，這樣系統才能判斷出事務2是在事務1之後。

為了避免出現圖中虛線的情況，事務1在t1确定送出後，要等待一段時間，也就是到t2這個時間戳，這時再向用戶端傳回committed消息，這樣後續新到達的事務，其時間戳一定在t2之後，避免了不确定區間的交集，保證系統可以正确判定事務1/2的先後順序。

CockroachDB

CRDB沒有google那麼強大的财力和基礎設施，采用了NTP這種“窮人版”的TrueTime + HLC的混合時鐘方案，關于HLC這裡不具體展開，有興趣的同學可以去參考其paper和相關資料，HLC可以提供幾個重要的特性：

1. 本質上仍是lamport時鐘，通過互動消息，保證節點上的時間戳可以捕獲系統内事件的因果關系
2. 保證每個節點上的時間戳是單調遞增的
3. 保證不同節點間的時間誤差是有界的，隻不過這個誤差很大，預設是500ms

由于誤差區間（不确定區間）太大了，如果也采用commit wait，明顯是無法接受的，是以CRDB做了些妥協，不再追求全局範圍内strict serializability，但可以保證針對單個key（對象）操作的linearizability，具體如下：

對某個資料項K的設定，先後由兩個gateway node(使用者請求的接收節點）來執行，這裡假設node2是在使用者受到操作1的結果後才發起的，也就是兩個操作間具有因果關系，順序必須是操作1 -> 操作2，但由于前後兩次操作來源于不同節點node1,node2，其上的時間戳t1,t2可能存在不确定性，具體來說：

t1對應的真實時間區間是[t1 , t1 + max_offset]， t2的真實區間是[t2, t2 + max_offset]

1. t2 > t1 + max_offset，則可以确定t2對應的實體時間一定在t1之後，其順序滿足操作1,2之間的因果關系
2. t2 <=  t1 + max_offset，則無法确定t2和t1在實體時間上的先後，此時CRDB的處理方式是，把操作2的時間戳向後推遲到不确定區間之後，進而保證操作2一定被系統視為在操作1之後，保證了操作的因果順序。當然如果操作2是在一個更大的事務内部，則這種推遲還可能有其他副作用，但單就這個寫操作來說，這樣并沒有問題，本質上等價于以新的時間戳重新執行了這個操作。
3. t2 < t1，顯然隻要node1/2之間的時鐘誤差在0 -> max_offset這個範圍之内，這種情況不會發生

通過以上的分析，我們可以看到CRDB可以保證單個key操作的線性一緻性，即使系統中各節點間存在一定的時鐘誤差。這其實已經做到了在CAP理論中所描述的Consistency的要求，也就是對于資料的讀取是no stale read的。

推廣到多key操作的事務，由于CRDB隻采用了serializability這種最強的隔離級别，每個事務都具有唯一的讀寫時間戳，這個時間戳也決定了事務串行化執行的順序，那麼如果兩個事務操作的read/write set在key上有交集，由于以上的機制在該key上成立，就保證了這兩個事務的時間戳也滿足線性一緻的要求。

雖然已經非常接近了，但這還不是全局的strict serializability，一旦兩個事務在讀寫集合上沒有交集，就無法對他們的時間戳建立限制，是以無法保證其因果順序不被破壞，例如如下例子：

1. client3 發起事務 select * from t1，未得到結果
2. client1 執行事務 insert into t1 values(1)，然後commit成功傳回
3. client2 執行事務 insert into t1 values(2)，然後commit成功傳回
4. client3 的執行結果傳回

由于client1 / 2的操作沒有交集，他們的事務順序在系統内無法保證和實體時間順序（因果順序）一緻，而client3的讀操作又和事務1/2之間沒什麼因果關系，是以client3讀到什麼結果都是有可能的（隻有1 隻有2 都沒有 1,2都有）

但如果是如下執行序列：

3. client3 發起事務 select * from t1 并得到執行結果

雖然1,2之間沒有順序保證，但讀事務3與1,2各自有資料交集且有因果順序，是以可以保證：3一定讀到1且3一定讀到2。

考慮到CockroachDB作為一款跨地域部署的分布式OLTP資料庫系統，其對資料的正确性和一緻性的追求還是非常值得敬佩的，而且也采用了大量的技術優化來提升事務的吞吐，降低延遲，這樣就在保證了盡可能強的一緻性語義的前提下，盡可能的給出最佳擴充性和性能。

總結

基本描述了我對分布式系統的線性一緻性的了解還有如何擴充到具有事務語義的資料庫系統中，也大概介紹了下現在主流的幾種OLTP系統的具體實作方案，包括時鐘方案和提供的一緻性語義級别，如果有了解不正确的地方，希望大家幫忙指正。

綜合來看，小強DB在沒有任何強大的硬體時鐘方案的情況下實作了非常接近線性一緻性的語義，可以說是非常牛逼了。