概述
NewSQL日漸火熱，無論還是開源的TiDB，CockroachDB還是網際網路大廠的Spanner，Oceanbase都号稱NewSQL，也就是分布式資料庫。NewSQL的典型特征就是，支援SQL，支援事務，高性能，低成本，高可靠，強一緻，易擴充，運維友好等。從NewSQL的演進來看，所謂NewSQL，可以簡單了解為NoSQL+傳統的關系型資料庫的結合，NoSQL強調分布式(高可用，可擴充)，關系型資料庫則強調事務，SQL。正因為二者的疊加，是以需要把兩個領域的概念整合在一起，本文主要想把分布式資料庫中幾個基本概念講清楚。
一緻性
資料庫和分布式系統中都有一緻性概念，由于很多英文單詞對應的中文都是“一緻性”，導緻容易産生誤區。資料庫中的ACID，C是Consistency，這個C主要強調應用邏輯的一緻性，比如應用定義的限制，包括外鍵等。分布式系統的CAP以及一緻性協定，也稱為一緻性。前者主要強調，讀是否能讀到最新，以及并發場景下操作執行的時序關系，主要包括線性一緻性(linearizability)，順序一緻性(sequential consistency)，因果一緻性(causal consistency)等；後者主要強調“共識”，分布式中的多個節點對某個事情(選主，事務送出)達成一緻，常見的共識算法包括paxos協定，raft協定等。
線性一緻性(linearizability)
簡單來說，線性一緻性要求，第一，“寫後讀”，這裡寫和讀是兩個操作，如果寫操作在完成之後，讀才開始，讀要能讀到最新的資料，而且保證以後也能讀操作也都能讀到這個最新的資料。第二，所有操作的時序與真實實體時間一緻。相對于“寫後讀”，第二點要求即使不相關的兩個操作，如果執行有先後順序，線性一緻性要求最終執行的結果也需要滿足這個先後順序。比如，操作序列(寫A，讀A，寫B，讀B)，那麼不僅，讀A，讀B能讀到最新A值和B值；而且要保證，如果讀B讀到最新值時，讀A一定也能讀到最新值，也就是需要保證執行時序與真實時序相同。第三點，如果兩個操作是并發的(比如讀A沒有結束時，寫B開始了)，那麼這個并發時序不确定，但從最終執行的結果來看，要確定所有線程(程序，節點)看到的執行序列是一緻的。
下圖對線性一緻性有詳細的論述，來源于[6]
順序一緻性(sequential consistency)
相比線性一緻性，主要差別在于，對于實體上有先後順序的操作，是否要保證這個時序。具體而言，對于單個線程，操作的順序仍然要保留，對于多個線程(程序，節點)，執行的事件的先後順序與實體時鐘順序不保證。但是要求，從執行結果來看，所有線程(程序，節點)看到的執行序列是一樣的。詳細定義來源于[6]
下圖的例子很好的區分了線性一緻性和順序一緻性。
對于(a),執行序列write(y,2),read(x,0),write(x,4),read(y,2)，結果符合要求，但是從用戶端的角度來看，write(x,4)先于read(x,0)執行，但是read卻沒有讀到最新值。
對于(b),write(y,2)和read(y,2)有先後順序，也是符合“寫後讀”，是以是線性一緻性。
對于(c), 有幾種可能：
1).write(x,4),read(y,0),write(y,2),read(x,0)，x的寫後讀，不符合要求；
2).write(y,2),read(x,0),write(x,4),read(y,0)，y的寫後讀，不符合要求。
是以既不符合線性一緻性，也不符合順序一緻性。
因果一緻性(causal consistency)
相對于順序一緻性，弱化了不相關操作是否需要保序。
對于b),p1和p2 w(x)是沒有先後關系的，是以誰先發生都是可以的。
從p3的視角來看，操作執行的序列是w(x,7),r(x,7),w(x,2),r(x,2),w(x,4);保證了“寫後讀”
從p4的視角來看，操作執行序列是w(x,2),w(x,4),r(x,4),w(x,7),r(x,7);保證了“寫後讀”
但是不同程序看到的執行序列不一樣，是以不符合順序一緻性。
可串行化
上一篇文章講了資料庫中異常和隔離級别，實際上隔離級别是純粹資料庫領域的概念與分布式系統并沒有交集，比如讀未送出，讀送出，可重複讀以及可串行化。對于資料庫而言，我們說Serializable，是說并發場景下，多個并發事務最終執行的序列與某個串行執行的序列相同(無事務并發，事務的執行沒有重疊)。那麼如何實作并發控制來達到可串行化排程。資料庫中對于同一對象的操作可能存在幾類沖突，包括讀寫沖突，寫寫沖突，寫讀沖突等，如果解決了這些沖突，也就實作了可串行化排程。實際上沖突可串行化排程是可串行排程的充分條件，并非必要條件，詳細展開可以看這篇blog，而我們實際的資料庫系統中實作可串行化排程也是解決沖突串行化問題。主要有兩種，一種是基于S2PL(Strict 2 Phrase Locking)，事務操作過程中，對讀加讀鎖，對寫加寫鎖，事務送出時，才将鎖釋放，為了避免幻讀，還需要實作間歇鎖等；另外一種，是基于Snapshot的SSI隔離級别，這種實作與S2PL的主要差別在于，讀仍然采用快照讀，不加鎖，讀寫不互斥，為了實作可串行化排程，需要收集事務的讀寫操作資訊，并判斷是否事務有互相依賴的情況(沖突成環)，如有，則将沖突的事務復原，實際上是first-commit-win原則，最後導緻成環的事務會被復原。具體可以參考論文:Serializable Isolation for Snapshot Databases，目前商業資料庫PG和CockroachDB都是實作了SSI隔離級别。而MySQL的InnoDB存儲引擎則是采用了S2PL實作了可串行化隔離級别。
線性一緻性VS可串行化
前面分别介紹了分布式系統中的一緻性以及資料庫中的可串行化隔離級别，分布式資料庫顯然是分布式系統，也是資料庫系統，那麼是否能做到線性一緻性+可串行化，就是所謂的“Strong Consistency”。這個定義來源于Jepsen的一篇blog，具體可以看下圖。
我們要注意到，讨論線性一緻性時，我們讨論的粒度是一個操作，操作是否滿足先後關系；而讨論隔離級别時，粒度是一個事務，事務是否與某個串行執行的結果相同。是以，這裡就比較特殊了，事務中包含了若幹讀寫操作，我們要保證讀到最新，是說後開啟的事務的讀能讀到之前的送出；還是事務中的每個讀都能讀到讀開始之前的送出(讀送出)。至少從DDIA(Designing Data-Intensive Application)[2]這本書介紹來看，應該是後者，是以它認為基于S2PL協定實作的可串行化，可以做到線性一緻性兼得；而SSI由于是快照讀，導緻讀不能讀到最新，是以不滿足線性一緻性的。
資料庫要實作“線性一緻性”，需要保證事務操作按全局時鐘的先後順序。對于寫而言，通過一個統一的地方配置設定時間戳，顯然先後執行的事務配置設定的時間戳也滿足先後關系。這裡實際上需要一個統一“全局時間源”，也就是業内常用的TSO(TimeStampOracle)方案，TSO能保證所有事務全局有序。對于讀而言，讀采用加鎖目前讀，也能保證讀到最新，是以結合S2PL可以兼得可串行化+線性一緻性，也就是實作Strict Serializable。
External Consistency(外部一緻性)
google Spanner論文還提到一個外部一緻性的概念，
Spanner通過GPS+原子鐘保證了所有事務的寫有序，實作了類似TSO的功能，但是避免了TSO的單點可用性和性能問題。它提到External Consistency相比linearizability，主要是限制了非相關并發事務的送出順序與實體時鐘要保持一緻，因為linearizability并不限制并發執行的操作。論文中沒有提到Spanner如何實作Serializable隔離級别，我猜測是類似SSI的實作，那麼仍然做不到Strict Serializable。
總結
分布式資料庫中的一緻性概念有很多，但含義都不太一樣，ACID中的一緻性主要強調應用邏輯的一緻性，需要應用參與保證一緻性，CAP中的一緻性則主要強調多個副本的一緻性，寫後讀是否能讀到最新，這裡面就衍生了幾種一緻性，包括線性一緻性，順序一緻性，因果一緻性等。資料庫有隔離級别的概念，對于可串行化隔離級别也要求順序，實際上與分布式系統的一緻性沒有什麼關系，它更強調隔離，不強調事務執行的順序是否與真實執行先後順序保持一緻。是以，資料庫可能實作了可串行化隔離級别，但是并不一定實作了線性一緻性，比如基于SSI實作的可串行化就是這類系統。
參考文檔
[1].spanner論文
[2].https://jepsen.io/consistency
[3].http://www.bailis.org/blog/linearizability-versus-serializability/
[4].Spanner存儲層實作
[5].Serializable Isolation for Snapshot Databases
[6].《Distributed Computing，Principles, Algorithms, and Systems》
[7].《Designing Data-Intensive Applications》