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

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

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

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

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

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

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

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

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

原子提交和兩階段提交

在第七章我們探討過，在多個(gè)寫操作中途出現(xiàn)故障時(shí)，原子性能夠?qū)?yīng)用層提供一種簡單的語義。事務(wù)結(jié)果是要么成功提交（事務(wù)的全部寫入都成功持久化），要么全部丟棄（事務(wù)的所有寫入都被回滾，即取消或者扔掉）。

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

從單機(jī)到分布式的原子提交

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

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

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

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

在上述場景中，只是簡單地在提交事務(wù)時(shí)給每個(gè)節(jié)點(diǎn)發(fā)送提交請求讓其提交事務(wù)，是不能夠滿足事務(wù)基本要求的。這是因?yàn)椋赡苡械墓?jié)點(diǎn)成功提交了，有的節(jié)點(diǎn)卻提交失敗了，從而違反了原子性保證：

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

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

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

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

兩階段提交簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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