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

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

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

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

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

答案是，F(xiàn)LP 不可能是基于異步系統(tǒng)模型（參見系統(tǒng)模型和現(xiàn)實）證明的，這是一種非?？量痰哪Ｐ?，不能夠使用任何時鐘系統(tǒng)和超時檢測。如果允許使用超時宕機檢測、或者任何可以識別節(jié)點宕機的方法，就能夠?qū)崿F(xiàn)可靠的共識算法。甚而，只讓算法用隨機數(shù)來進行故障檢測，也能夠繞過這個不可能定理。

因此，盡管在理論上，F(xiàn)LP 定理非常重要，斷言異步網(wǎng)絡(luò)中共識不可能達到；但在實踐中，分布式系統(tǒng)達成共識是可行的。

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

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

原子提交和兩階段提交

在第七章我們探討過，在多個寫操作中途出現(xiàn)故障時，原子性能夠?qū)脤犹峁┮环N簡單的語義。事務結(jié)果是要么成功提交（事務的全部寫入都成功持久化），要么全部丟棄（事務的所有寫入都被回滾，即取消或者扔掉）。

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

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

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

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

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

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

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

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

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

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

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

兩階段提交簡介

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

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

一次成功執(zhí)行的兩階段提交

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

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

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

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

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

基于承諾的系統(tǒng)

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

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

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

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

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

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

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

協(xié)調(diào)者故障

我們已經(jīng)討論了在 2PC 中如果任何一個參與者（participant）或者網(wǎng)絡(luò)故障時的系統(tǒng)行為：

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

然而，我們還沒有討論，當協(xié)調(diào)者故障（coordinator failure）時，系統(tǒng)應當如何應對。

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

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

第一階段后協(xié)調(diào)者故障

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

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