1. 強一致性

1.1. 最終一致資料庫通過跨多台機器分區和複製數據集來獲得可擴展性，其代價是要跨副本維持強數據一致性以及允許衝突寫入

• 1.1.1. 在更新數據對象後，不同的客戶端可能會看到該對象的舊值或新值，直到所有副本都收斂到最新值

1.2. 另一類分散式資料庫提供一種可替代的模型，即強一致性數據系統，也稱為NewSQL或分散式SQL

• 1.2.1. 強一致性系統試圖確保所有客戶端在數據對象更新後看到相同、一致的值

• 1.2.2. 提供眾所周知的ACID（原子性、一致性、隔離性、持久性）資料庫事務來處理衝突更新的優勢

1.3. 事務和數據一致性，是現有單節點關係資料庫中每個人都熟悉的特征，消除了最終一致系統中固有的許多複雜性

1.4. 對於互聯網規模的系統，最佳結果當然是提供強一致資料庫的好處，同時具備最終一致系統的性能和可用性

1.5. 強一致資料庫則旨在提供與單節點系統相同的一致性保證

• 1.5.1. 有了強一致性，你在編寫應用程式時便可以確保一旦資料庫確認更新，所有客戶端的後續讀取就會看到新值

1.6. 事務和副本一致性的解決方案由不同的技術社區在不同的時間開發

• 1.6.1. 事務一致性

  • 1.6.1.1. 對於事務一致性，二階段提交演算法起源於Jim Gray（資料庫系統先驅之一）1978年的工作

  • 1.6.1.2. 在支持ACID事務的分散式資料庫中，你需要一種演算法，使得在單個事務中更新來自不同物理數據分區和節點的數據對象時能夠保持一致性

• 1.6.2. 副本一致性

  • 1.6.2.1. 強副本一致性意味著在數據對象更新後，無論客戶端訪問哪個副本，都會看到相同的值

  • 1.6.2.2. 用於實現事務和副本一致性的演算法稱為共識演算法(consensus algorithm)，它們使分散式系統中的節點能夠就某些共用狀態的值達成共識或協議

1.7. ACID事務

• 1.7.1. 原子性(Atomicity)

  • 1.7.1.1. 對資料庫的所有更改都必須像單個操作一樣執行，所有更新必須都成功（提交）​，或者必須都失敗（回滾）​

• 1.7.2. 一致性(Consistency)

  • 1.7.2.1. 事務將使資料庫處於一致狀態

• 1.7.3. 隔離性(Isolation)

  • 1.7.3.1. 當事務正在進行時，事務修改的任何數據對其他併發事務是不可見的

• 1.7.4. 持久性(Durability)

  • 1.7.4.1. 如果事務提交，則所做的更改是永久性的，並且在系統出現故障時可以恢復

1.8. 具有一致性保證和支持簡易單機編程的可擴展和高可用的分散式資料庫是數據管理系統的“必殺技”​

2. 一致性模型

2.1. 最強的一致性模型，也稱為嚴格一致性、嚴格可串列化或外部一致性的模型，是資料庫和分散式系統社區定義的兩個最具限制性的一致性模型的組合

2.2. 可串列化

• 2.2.1. 可串列化通常稱為事務一致性，即ACID中的“C

• 2.2.2. 事務對多個數據對象執行一次或多次讀取和寫入

• 2.2.3. 可串列化保證在多個項目上執行一組併發事務時等同於事務按某種順序執行

2.3. 可線性化

• 2.3.1. 可線性化可線性化與讀取和寫入單個數據對象有關

• 2.3.2. 可線性化定義了使用掛鐘時間(wall clock time)的操作順序，掛鐘時間較近的操作會發生在掛鐘時間較遠的操作之後

3. 分散式事務

3.1. 從應用程式開發人員的角度來看，將事務視為一種簡化分散式系統故障場景的工具是最容易理解的

• 3.1.1. 應用程式只需簡單地定義使用ACID屬性執行哪些操作，剩下的由資料庫完成

• 3.1.2. 事務語義確保兩個操作要麼都成功要麼都失敗

• 3.1.3. 鎖是確保事務隔離性所必需的

3.2. 二階段提交

• 3.2.1. 經典的副本一致性演算法Paxos於1998年由Leslie Lamport首次提出

• 3.2.2. 二階段提交(two-Phase Commit，2PC)是經典的分散式事務共識演算法

  • 3.2.2.1. 在SQL Server和Oracle等關係資料庫以及VoltDB和Cloud Spanner等現代分散式SQL平臺中廣泛應用

• 3.2.3. 二階段提交也得到外部中間件平臺的支持

  • 3.2.3.1. Java Enterprise Edition中的Java Transaction API(JTA)和Java Transaction Service(JTS)

  • 3.2.3.2. 外部協調器可以使用XA協議驅動跨異構資料庫的分散式事務

• 3.2.4. 當資料庫客戶端啟動事務時，選擇一個協調器

  • 3.2.4.1. 協調器分配一個全局唯一的tid（事務標識符）並將其返回給客戶端

  • 3.2.4.2. tid標識的是由協調器維護的數據結構，稱為事務上下文

  • 3.2.4.3. 事務上下文記錄了參與事務的資料庫分區或參與者，以及它們的通信狀態

  • 3.2.4.4. 上下文由協調器保存，持久地維護事務的狀態

• 3.2.5. 準備階段（投票階段）

  • 3.2.5.1. 協調器向所有參與者發送一條消息，告訴它們準備提交事務

• 3.2.6. 執行階段

  • 3.2.6.1. 當所有參與者都對準備階段做出答覆時，協調器將檢查結果

  • 3.2.6.2. 如果所有參與者都可以提交，則整個事務可以提交，協調器向每個參與者發送提交消息

  • 3.2.6.3. 如果任意參與者決定中止事務，或者在指定的時間段內沒有回覆協調器，協調器則發送一個中止消息給每個參與者

• 3.2.7. 故障分析

  • 3.2.7.1. 故障可能是由系統崩潰或與應用程式的其他部分分區引起的

  • 3.2.7.2. 參與者故障

    3.2.7.2.1. 若參與者在準備階段完成之前崩潰，事務將被協調器中止，這是一個簡單的故障場景

    3.2.7.2.2. 也可能參與者先回覆準備消息，然後出現故障

    3.2.7.2.3. 從本質上講，參與者故障不會威脅一致性，因為它會達到正確的事務結果

  • 3.2.7.3. 協調器故障

    3.2.7.3.1. 如果協調器在發送準備消息後發生故障，參與者就會進退兩難

    3.2.7.3.1.1. 決定投票提交的參與者必須阻塞，直到協調器通知他們事務結果

    3.2.7.3.1.2. 如果協調器在發送提交消息之前或期間崩潰，參與者將無法繼續，因為協調器已經失敗並且在恢復之前不會發送事務結果

    3.2.7.3.2. 協調器故障沒有簡單的解決方法

    3.2.7.3.3. 唯一可行的解決方案是讓參與者等到協調器恢復後，檢查事務日誌

    3.2.7.3.4. 事務協調器恢復和事務日誌可以完成未完成的事務並確保系統一致性

    3.2.7.3.4.1. 缺點是參與者必須在協調器恢復前阻塞

• 3.2.8. 二階段提交的弱點就是不能容忍協調器故障

  • 3.2.8.1. 與所有單點故障問題一樣，解決此問題的一種可能方法是在參與者之間複製協調器和事務狀態

  • 3.2.8.2. 如果協調器失敗，參與者可以被提升為協調器並完成事務

4. 分散式共識演算法

4.1. 實現副本一致性，使所有客戶端都能讀取不同數據對象副本的一致數據值，需要副本之間就數據值達成共識或協議

• 4.1.1. 容錯共識演算法的基礎是原子廣播、全序廣播或複製狀態機等一類演算法

  • 4.1.1.1. 它們保證一組值或狀態以相同的順序嚴格一次(exactly once)傳遞到多個節點

• 4.1.2. 二階段提交也是一種共識演算法

4.2. Leslie Lamport的Paxos（可能是最著名的共識演算法）是無領導的

• 4.2.1. 無領導和其他複雜性使其實施起來非常棘手

• 4.2.2. 變體Multi-Paxos

  • 4.2.2.1. Multi-Paxos與Raft等基於領導者的方法有很多共同之處，它們是分散式關係資料庫（如Google Cloud Spanner）實現的基礎

4.3. 為了容錯，共識演算法必須在領導者和追隨者都出現故障的情況下使應用程式仍能取得進展

• 4.3.1. 當一個領導者失敗時，必須選出一個新的領導者，並且所有追隨者必須就同一領導者達成一致

4.4. 新的領導者選舉方法因演算法而異，但它們的核心要求

• 4.4.1. 檢測有故障的領導者

• 4.4.2. 一名或多名追隨者提名自己為領導者

• 4.4.3. 投票選舉新的領導者，可能要進行多輪投票

• 4.4.4. 一個恢復協議，用於確保在選舉出新領導者後所有副本都達到一致的狀態

4.5. 容錯共識演算法旨在僅與法定數或大多數參與者一起運行

• 4.5.1. 法定數用於確認原子廣播和領導人選舉

4.6. Raft

• 4.6.1. Raft是一種基於領導者的原子廣播演算法

  • 4.6.1.1. 單個領導者接收客戶請求，建立訂單，並向追隨者執行原子廣播以確保一致的更新順序

• 4.6.2. Raft的設計是為了直接應對Paxos演算法的複雜性

• 4.6.3. 被稱為“一種可理解的共識演算法”​，於2013年首次發佈

• 4.6.4. 任期編號是一個邏輯時鐘，每個有效的任期編號都與一個領導者相關聯。

• 4.6.5. 只有大多數追隨者需要在日誌中提交條目

  • 4.6.5.1. 意味著在不同時間提交的日誌條目可能在不同追隨者上並不相同

• 4.6.6. 在多個需要共識的生產系統中實現，包括Neo4j和YugabyteDB資料庫、etcd鍵值存儲和分散式記憶體對象存儲Hazelcast等

5. 強一致性實踐

5.1. VoltDB

• 5.1.1. VoltDB是最初的NewSQL資料庫之一

• 5.1.2. 建立在無共用架構之上，關係表使用分區鍵進行分片並跨節點複製

• 5.1.3. 每個VoltDB表分區都與一個CPU內核關聯

• 5.1.4. 存儲過程被視為事務單元

• 5.1.5. VoltDB是一個記憶體資料庫，它必須採取額外的措施來提供數據安全性和持久性

  • 5.1.5.1. 每個SPI都將命令日誌中的條目寫入持久存儲

  • 5.1.5.2. 每個分區還定義了一個快照間隔

• 5.1.6. 從版本6.4開始，VoltDB支持可線性化，因此在同一個資料庫集群中具有最強的一致性級別

  • 5.1.6.1. VoltDB實現可線性化的原因是，它對所有分區的寫入順序達成了共識，而且事務是按順序執行的，不會交錯

5.2. Google Cloud Spanner

• 5.2.1. 2013年，Google公司發表了Spanner資料庫論文

  • 5.2.1.1. Spanner被設計為一個強一致的全球分散式SQL資料庫

    5.2.1.1.1. Google將這種強一致性稱為外部一致性

  • 5.2.1.2. Cloud Spanner是一個基於雲的資料庫即服務(DBaaS)平臺

• 5.2.2. Cloud Spanner使用Paxos共識演算法使副本保持一致

  • 5.2.2.1. 與Raft一樣，Paxos使一組副本就一系列更新的順序達成一致

  • 5.2.2.2. 二階段提交的實現表現為一個Paxos組

• 5.2.3. Cloud Spanner對開發者隱藏了表分區的細節

  • 5.2.3.1. 隨著數據量的增長或收縮，它將跨機器動態地重新分區數據，將數據遷移到新位置來平衡負載

• 5.2.4. Cloud Spanner支持ACID事務

  • 5.2.4.1. 如果事務僅更新單個分片中的數據，則分片的Paxos領導者處理請求

  • 5.2.4.2. 領導者首先獲取被修改行上的鎖，並將變更傳遞給每個副本

• 5.2.5. TrueTime服務

  • 5.2.5.1. TrueTime為Google數據中心配備衛星連接的GPS和原子鐘，並提供具有已知上限時鐘偏差的緊密同步時鐘，據報道約為7 ms

• 5.2.6. Cloud Spanner是GCP（谷歌雲平臺）不可或缺的組件

  • 5.2.6.1. GCP客戶群涵蓋金融服務、零售和游戲等行業，這些行業都被它強大的一致性保證以及高可用性和全球分散式部署能力所吸引

• 5.2.7. Cloud Spanner啟發了基於Spanner架構的開源實現

  • 5.2.7.1. 這些實現不需要定製TrueTime式硬體，當然，代價是較低的一致性保證

  • 5.2.7.2. CockroachDB

  • 5.2.7.3. YugabyteDB