在分布式計算領域，共識問題是最重要而基礎的問題。從表面上看含義很直接：可以粗略的理解為多個節點就某件事達成共識。乍看起來，你會覺得，這有什么難的？但不幸的是，很多系統都因為低估了共識算法的實現難度而問題百出。

盡管共識問題非常之重要，但在本書中直到現在才才被提及，似乎有點晚了。這是因為這個主題實在是太艱深了，而欣賞其精妙需要非常多的前置知識。即使在學術界，對共識問題的研究也是歷經數十年坎坷才逐漸有了一些沉淀。在本書里，我們在第五章鋪墊了冗余（replication），在第七章鋪陳了事務，在第八章探討了分布式系統的系統模型，在本章又討論了線性一致性和全序廣播，到現在，我們終于做足了準備來好好談談共識問題了。

在很多場景下讓多個節點達成共識是非常重要的。比如：

• Leader 選舉在使用單主模型的數據庫中，所有節點需要對誰是主節點達成一致。當網絡問題導致有些節點不能正常通信時，領導權就會出現爭議。在這種情形下，共識對于避免錯誤的故障轉移非常重要。引入如果出現兩個領導者可以同時接受寫入（腦裂），所有副本上的數據就會產生分叉，從而變得不一致甚而數據丟失。
• 原子提交在一個橫跨多節點或具有多分區的數據庫中，可能會出現某個事務在一些節點執行成功，但在另外一些節點卻運行失敗。如果我們想保持事務的原子性（ACID 中的 A，參見原子性），我們就必須讓所有節點就事務的結果達成一致：要么全部回滾（只要有故障），要么提交（沒有任何故障）。這個共識的特例也被稱為原子提交（atomic commit）。

共識的不可能性。你也許聽過 FLP —— 以 Fischer，Lynch 和 Paterson 三位作者姓名首字母命名的一種不可能原理——在網絡可靠，但允許節點宕機（即便只有一個）的異步模型系統中，不存在總是能夠達成共識的算法。在分布式系統中，我們又必須得假設節點可能會宕機，因此穩定可靠的共識算法是不存在的。但是，我們現在卻在探討可以達成共識的算法。這又是為啥？這可能嗎？

答案是，FLP 不可能是基于異步系統模型（參見系統模型和現實）證明的，這是一種非常苛刻的模型，不能夠使用任何時鐘系統和超時檢測。如果允許使用超時宕機檢測、或者任何可以識別節點宕機的方法，就能夠實現可靠的共識算法。甚而，只讓算法用隨機數來進行故障檢測，也能夠繞過這個不可能定理。

因此，盡管在理論上，FLP 定理非常重要，斷言異步網絡中共識不可能達到；但在實踐中，分布式系統達成共識是可行的。

在本小節，我們首先會詳細探討原子提交。特別的，我們將會討論兩階段提交（2PC，two-phase commit）算法，這是一種解決原子提交的最為常見的算法，很多數據庫和服務端應用都實現了該算法。可以看出，2PC 在某種程度上是一種共識協議——雖然不是很完美。

在學習完 2PC 之后，我們將會轉向更完善的共識算法，比如 Zookeeper 中用的 Zab 算法和 etcd 中用的 Raft 算法。

原子提交和兩階段提交

在第七章我們探討過，在多個寫操作中途出現故障時，原子性能夠對應用層提供一種簡單的語義。事務結果是要么成功提交（事務的全部寫入都成功持久化），要么全部丟棄（事務的所有寫入都被回滾，即取消或者扔掉）。

原子性能夠避免失敗的事務通過半完成（half-finished）或者半更新（half-updated）的結果來破壞數據庫系統。這一點對于多對象事務（參見單對象和多對象操作）和支持二級索引的數據庫來說尤為重要。二級索引是獨立于原始數據的一種數據結構，因此如果你更新了原始數據，對應的二級索引也需要進行同步更新。原子性能夠保證二級索引和原始數據時刻保持一致。（如果索引不和原始數據保持同步更新，那該索引就失去了其作用）

從單機到分布式的原子提交

對于運行在單機數據上的事務，原子提交通常由存儲引擎層來實現。當客戶端請求數據庫節點提交事務時，數據庫會首先將事務所涉及到的寫入進行持久化（通常通過寫前日志 WAL 的方式，參見讓 B 樹更可靠），事務結束時在硬盤上追加一個特殊的提交記錄（commit record）到日志上。如果數據庫在處理事務的過程中宕機了，在重啟時會從日志上對事務進行恢復：

1. 如果在宕機前，提交記錄已經追加到磁盤上，則該事務被認為已經成功提交。
2. 否則，該事務所有的寫入將會被回滾。

因此，在單機數據庫里，事務是否提交主要取決于數據持久化到磁盤的順序：首先是數據，接著是提交記錄。提交事務還是中止事務，決定性時刻在于提交記錄成功刷盤的那一瞬間：在此之前，事務可能會被中止（由于宕機）；在此之后，該事務一定會被提交（即使宕機）。也即，是唯一的硬件設備（某個特定節點上的某個具體的磁盤驅動）保證了提交的原子性。

然而，當事務涉及到多個節點時又當如何？例如，一個跨分區的多對象事務，或者基于關鍵詞分區的二級索引（在該情況下，索引數據和基礎數據可能不在一個分區里，參見分片和次級索引）。大多數“NoSQL”分布式存儲不支持這種跨節點的分布式事務，但很多分布式關系型數據庫則支持。

在上述場景中，只是簡單地在提交事務時給每個節點發送提交請求讓其提交事務，是不能夠滿足事務基本要求的。這是因為，可能有的節點成功提交了，有的節點卻提交失敗了，從而違反了原子性保證：

• 有些節點在提交時檢測到完整性約束被破壞了，因此中止事務；但另外一些節點卻能夠成功提交。
• 有些提交請求由于網絡過慢而超時丟棄，另外一些提交請求卻成功抵達。
• 有一些節點在寫入提交記錄前宕機重啟，導致事務回滾；另外一些節點卻成功提交。

如果有些節點提交了該事務，但另外的一些節點卻中止該事務了，多個節點間就會處于不一致的狀態。而且，一旦事務在一個節點上提交了（即便之后發現了該事務在其他節點上失敗了）就難以進行撤銷。由于這個原因，我們需要僅在確信所有相關節點都能成功提交時，本節點才能提交。

事務提交后是不可撤銷的——在事務提交后，你不能再改變主意說，我要重新中止這個事務。這是因為，一旦事務提交了，就會對其他事務可見，從而可能讓其他事務依賴于該事務的結果做出一些新的決策；這個原則構成了讀已提交（read commited）隔離級別的基礎（參見讀已提交）。如果事務允許在提交后中止，其他已經讀取了該事務結果的事務也會失效，從而引起事務的級聯中止。

當然，事務所造成的結果在事實上是可以被撤銷的，比如，通過補償事務（_compensating transaction_）。但，從數據庫的視角來看，這就是另外一個事務了；而跨事務的正確性，需要應用層自己來保證。

兩階段提交簡介

兩階段提交（2PC，two-phase commit）是一種在多個節點上實現原子事務的算法——即，保證所有節點要么都提交，要么都中止。這是數據庫中一個經典的算法。2PC 算法會在某些數據庫內部使用，有時也會以 XA 事務（支持 Java 事務 API）或者 SOAP Web 服務原子事務形式，供應用層使用。

2PC 基本流程如下圖所示。相比單機事務的一次提交請求，2PC 中的提交、中止過程被拆分成了兩個階段（即名字由來）。

一次成功執行的兩階段提交

不要混淆 2PC 和 2PL。Two-phase commit (2PC) 和 two-phase locking (2PL，參見兩階段鎖) 是兩個完全不同的概念。2PC 是為了在分布式系統中進行原子提交，而 2PL 是為了進行事務并發控制的一種加鎖方式。為了避免歧義，可以忽略他們在名字簡寫上的相似性，而把它們當成完全不同的概念。

2PC 引入了一個單機事務中沒有的角色：協調者（coordinator，有時也被稱為事務管理器，transaction manager）。協調者通常以庫的形式出現，并會嵌入到請求事務的應用進程中，但當然，它也可以以單獨進程或者服務的形式出現。比如說，Narayana, JOTM, BTM, or MSDTC.

和單機事務一樣，2PC 事務通常也由應用層對多個節點上的數據讀寫開始。和協調者相對，我們將這些數據節點稱為事務的參與者（participants）。當應用層準備好提交后，協調者開始階段一：向每個參與者發送 prepare 請求，詢問他們是否能夠提交。然后，協調者會根據參與者的返回而進行下一步動作：

1. 如果所有參與者都回復“可以”（yes），表示能夠提交，則協調者就會進入第二階段發出提交（ commit ）請求，此時，提交事實上才開始執行。
2. 如果有任何參與者回復“不行”（no），或者請求超時了，協調者就會進入第二階段并發送一個 中止（abort）請求，中止事務。

這個過程在某種程度上很像西方文化中的結婚儀式：牧師會分別問新娘、新郎是否愿意與對方結婚，通常，雙方都會回答“我愿意”（I do）。當牧師收到雙方肯定的回答后，就會宣布他們結為夫婦：即事務提交，并將這個令人高興的事實傳達給所有賓客。如果新娘、新郎有任何一方回答否，則儀式中止。

基于承諾的系統

從上面的簡要描述中，我們可能很難想通為什么兩階段提交能夠保證原子性？而多個節點的單階段提交就做不到這一點。畢竟，雖然是兩階段，但是兩階段中的任何一個請求都有可能在網絡中丟失。讓 2PC 能夠保證原子性的核心原因到底是什么？

為了理解它的工作原理，我們把 2PC 各個階段拆得更細一些：

1. 當應用想開啟一個分布式事務時，它會首先向協調者要一個事務 ID。該事務 ID 是全局唯一的。
2. 應用會使用前述事務 ID 向所有的參與者發起一個單機事務，所有節點會各自完成讀寫請求，在此過程中，如果有任何出錯（比如節點宕機或者請求超時），協調者或者任意參與者都可以中止事務。
3. 當應用層準備好提交事務時，協調者會向所有參與者發送準備提交（prepare）請求，并在請求中打上事務 ID 標記。如果有請求失敗或者超時，則協調者會對所有參與者發送帶有該事務 ID 的中止請求。
4. 當參與者收到準備提交請求時，它必須確認該事務能夠在任何情況下都能被提交，才能回復“可以”。這包括，將所有寫入刷到磁盤（一旦承諾了，就不能反悔，即使之后遇到宕機、斷電或者磁盤空間不足）、檢查是否有沖突或者違反約束的情況。換句話說，如果回復“可以”，意味著參與者讓渡了中止事務的權利（給協調者），但此時并沒有真正地提交。
5. 當協調者收到所有參與者準備提交的回復后，會決定提交還是中止該事務（只有在所有參與者都回復“可以”時，才會提交）。協調者需要將該決策寫入事務日志，并下刷到磁盤，以保證即使宕機重啟，該決策也不會丟失。這被稱為提交點（commit point）。
6. 協調者將決策刷入了磁盤后，就會將決策（提交或者中止）請求發給所有參與方。如果某個請求失敗或者超時，則協調者會對其進行無限重試，直到成功。不允許走回頭路：如果協調者決定了提交，則不管要進行多少次的重試，也必須要保證該決策的執行。如果參與者在此時宕機了，則當重啟時也必須進行提交——因為它承諾過要提交，因此在重啟后不能拒絕提交。

因此，該協議有兩個重要的“不可回退點”：

1. 當某個參與者回復“可以”時，就做出了（將來無論發生什么）肯定可以提交的承諾。（當然，協調者可以中止事務）
2. 當協調者決定提交時，該決定一旦做出（寫入磁盤），就是不可撤回的。

這兩個承諾保證了 2PC 的原子性（其實單機事務是將上述兩個事件合二為一：將提交記錄寫入事務日志即代表提交）。

說回婚禮的比喻，在說“我愿意”之前，雙方都有說“沒門”（或者任何相當言論）來中止事務的自由。然而，一旦承諾“我愿意”，就不能收回該承諾。即使你在說出“我愿意”之后昏倒過去，哪怕沒有聽到牧師說“你們現在已結為夫妻”，也不影響對應事務已經提交的事實。當你之后恢復意識時，可以憑借事務 ID 向牧師詢問你們的婚姻狀態，或者簡單的等待牧師下一次重試的提交請求（重試會在你昏迷期間一直進行）。

協調者故障

我們已經討論了在 2PC 中如果任何一個參與者（participant）或者網絡故障時的系統行為：

1. 如果任意準備提交（prepare）請求失敗，則協調者中止事務。
2. 如果任意提交（commit）或者中止（abort）請求失敗，則協調者會進行無限重試。

然而，我們還沒有討論，當協調者故障（coordinator failure）時，系統應當如何應對。

如果協調者在準備提交請求發送前故障，則參與者可以放心的中止事務。然而，一旦參與者收到準備提交請求，并且回復“可以”，則根據 2PC 設定，它不能單方面的中止事務——而必須等待協調者的提交或者中止請求。如果此時協調者宕機或者網絡故障，則參與者只能死等。參與者事務的這種狀態稱為存疑（in doubt）或者未定（uncertain）。

圖 9-10 就是一個這樣的例子。在該例子中，系統處于第二階段，協調者準備提交，并且數據庫實例 2 收到了提交請求。此時，協調者宕機，還沒來得及給數據庫實例 1 發送提交請求，因此該實例不知道是要提交還是中止事務。超時機制在這里并不能解決問題：超時后，如果數據庫實例 1 單方面決定中止事務，則會和數據庫實例 2 處于不一致的狀態。類似的，單方面提交事務也不靠譜，畢竟另外的參與者也可能收到請求并中止了事務。

第一階段后協調者故障

在未收到協調者的消息前，參與者無從得知是要提交還是中止。原則上，參與者之間可以互相溝通以確定該如何進行下一步，并最終達到一致，但這已經超脫了 2PC 協議范疇。

在 2PC 中，唯一使算法能夠完成的方法就是等待協調者恢復。這也是為什么，協調者在給參與者發送提交或者中止消息時，需要先將該決策寫入事務日志中：當協調者恢復時，他就能從事務日志中讀取該決策，以讓所有處于未決狀態的參與者狀態確定下來。如果協調者恢復了，發現并沒有寫入任何決策到事務日志中，則中止該事務。因此，2PC 的提交點（commit point）最終可以歸結到協調者上的單機原子提交。