首先是 Paxos 系列論文：
《The Part Time Parliament》，Paxos算法的基礎(chǔ)論文，作者通過Paxos神會(huì)選舉例子描述了分布式系統(tǒng)面臨的一致性問題，并且給出了Paxos正式算法，以及算法的嚴(yán)格數(shù)學(xué)證明。后續(xù)所有的文獻(xiàn)，工程實(shí)踐都是圍繞這篇文章展開的。
Paxos維基百科上有算法的簡(jiǎn)潔描述，文章最后的幾個(gè)流程圖描述的實(shí)例對(duì)于學(xué)習(xí)Paxos算法很有幫助。
《Paxos Made Simple》，循循漸進(jìn)地講解 paxos 解決的問題、逐步增強(qiáng)的約束條件（P1、P2、P2a – P2c）等，P1 保證至少有一個(gè)值被接受， P2 保證只有一個(gè)被選中的值被所有 process 接受。然后介紹兩階段的步驟：proposer 的選擇。達(dá)成一致的值之后，接下來論文討論了其他 process 學(xué)習(xí)機(jī)制和 liveness 問題，paxos 無法解決活鎖問題，但是實(shí)際應(yīng)用中這個(gè)問題可以通過選舉一個(gè)唯一的 proposer 來避免。接下來談到實(shí)現(xiàn)，說明一個(gè) Replication State Machine 的實(shí)現(xiàn)問題，著重討論了 leader failure 情況下的『空洞』問題，通過引入 no-op commands 來減少服務(wù)中斷時(shí)間。但是這篇論文沒有明確提到 multi paxos 的介紹，這就需要繼續(xù)閱讀其他論文和博客來理解。
《Paxos Made live》。這篇論文是 Google 發(fā)表的，討論了 paxos 的工程實(shí)踐，也就是 chubby 這個(gè)眾所周知的分布式服務(wù)的實(shí)現(xiàn)，可以結(jié)合《The Chubby lock service for loosely-coupled distributed systems》 一起看。實(shí)際應(yīng)用中的難點(diǎn)，比如 master 租約實(shí)現(xiàn)、group membership 變化、Snapshot 加快復(fù)制和恢復(fù)以及實(shí)際應(yīng)用中遇到的故障、測(cè)試等問題，特別是最后的測(cè)試部分。非常值得一讀。《The Chubby lock service for loosely-coupled distributed systems》 更多介紹了 Chubby 服務(wù)本身的設(shè)計(jì)決策，為什么是分布式鎖服務(wù)，為什么是粗粒度的鎖，為什么是目錄文件模式，事件通知、多機(jī)房部署以及應(yīng)用碰到的使用問題等等。
Paxos Made Practical。這篇論文更詳細(xì)地討論了 State Machine 的實(shí)現(xiàn)，甚至還帶上了 C語(yǔ)言的偽代碼，定義了 prosper 、 acceptor 以及 SM 本身需要實(shí)現(xiàn)的接口和通訊協(xié)議，更重要的是討論了 membership change 的問題，通過引入 view 視圖的概念，介紹了 view-change 協(xié)議來解決成員變動(dòng)問題（可能是故障或者上下線新成員），按我的理解，這個(gè)過程也是 paxos 的應(yīng)用。最后介紹了可能的優(yōu)化手段。
（view change 協(xié)議）
其次，一致性方面另一塊就是 Raft 算法，按照 Google Chubby 論文里的說法，
Indeed, all working protocols for asynchronous consensus we have so far
encountered have Paxos at their core.
但是 Raft 真的好理解多了，我讀的是《In Search of an Understandable Consensus Algorithm》，論文寫到這么詳細(xì)的步驟，你不想理解都難。畢竟 Raft 號(hào)稱就是一個(gè) Understandable Consensus Algorithm。無論從任何角度，都推薦閱讀這一篇論文。
首先能理解 paxos 的一些難點(diǎn)，其次是了解 Raft 的實(shí)現(xiàn)，加深對(duì) Etcd 等系統(tǒng)的理解。這篇論文還有一個(gè) 250 多頁(yè)的加強(qiáng)版《CONSENSUS: BRIDGING THEORY AND PRACTICE》，教你一行一行寫出一個(gè) Raft 實(shí)現(xiàn)，我還沒有學(xué)習(xí)，有興趣可以自行了解。Raft 通過明確引入 leader（其實(shí) multi paxos 引申出來也有，但是沒有這么明確的表述）來負(fù)責(zé) client 交互和日志復(fù)制，將整個(gè)算法過程非常清晰地表達(dá)出來。Raft 的算法正確性的核心在于保證 Leader Completeness ，選舉算法選出來的 leader 一定是包含了所有 committed entries 的，這是因?yàn)樗?committed entries 一定會(huì)在多數(shù)派至少一個(gè)成員里存在，所以設(shè)計(jì)的選舉算法一定能選出來這么一個(gè)成員作為 leader。多數(shù)派 accept 應(yīng)該說是一致性算法正確性的最重要的保證。
最后，我還讀了《Building Consistent Transactions with Inconsistent Replication》，包括作者的演講，作者也開放了源碼。Google Spanner 基本是將 paxos 算法應(yīng)用到了極致，但是畢竟不是所有公司都是這么財(cái)大氣粗搞得起 TrueTime API，架得起全球機(jī)房，控制或者承受得了事務(wù)延時(shí)。這篇論文提出了另一個(gè)思路，論文介紹的算法分為兩個(gè)層次： IR 和基于其他上的 TAPIR。前者就是 Inconsistent Replication，它將操作分為兩類：
- inconsistent： 可以任意順序執(zhí)行，成功執(zhí)行的操作將持久化，支持 failover。
- consensus：同樣可以任意順序執(zhí)行并持久化 failover，但是會(huì)返回一個(gè)唯一的一致(consensus)結(jié)果。
IR 的調(diào)用圖：
可見他需要服務(wù)端和客戶端共同參與，對(duì)于 consensus 操作，如果 replicas 之間有沖突，會(huì)在客戶端引入一個(gè) decide 過程來決定使用哪一個(gè)值，相應(yīng)地，在服務(wù)端為了解決 master 和 replicas 的不一致問題，引入了 sync/merge 過程來解決沖突，master 運(yùn)行 merge 過程來解決 consensus 操作的副本沖突，而所有節(jié)點(diǎn)運(yùn)行 sync 過程來同步 master 記錄。關(guān)于 sync/master 的描述看原文：
"Some replicas may miss operations or need to reconcile their state if the
consensus result chosen by the application (i.e., transaction) protocol does
not match their result. To ensure that IR replicas eventually converge, they
periodically synchronize. Similar to eventual consistency, IR relies on the
application (i.e., transaction) protocol to reconcile inconsistent replicas.
On synchronization, a single IR node first upcalls into the application
protocol with Merge, which takes records from inconsistent replicas and
merges them into a master record of successful operations and consensus
results. Then, IR upcalls into the application (i.e., transaction) protocol
with Sync at each replica. Sync takes the master record and reconciles
application (i.e., transaction) protocol state to make the replica consistent
with the chosen consensus results."
為了保證正確性，IR 對(duì)上層應(yīng)用層協(xié)議有特殊的要求：
- Invariant checks must be performed pairwise.也就是要求任意兩個(gè) consensus 操作，其中一個(gè)至少對(duì)另一個(gè)是可見的。不然無法檢測(cè)是否沖突。
- Application protocols must be able to change consensus operation results.對(duì)于已經(jīng)達(dá)成一致的結(jié)果，還要允許是可以被修改的，merge 過程會(huì)修改原來認(rèn)為的一致的結(jié)果，這是不一致復(fù)制必然帶來的問題。
- 性能原則 1：Application protocols should not expect operations to execute in the same order. 對(duì)于順序不要有任何假設(shè)。
- 性能原則 2：Application protocols should use cheaper inconsistent operations whenever possible rather than consensus operations. 盡量用 inconsistent 操作。比如在 TAPIR 里只有 prepare 是 consensus 類型操作。
正因?yàn)閷?duì)于應(yīng)用層協(xié)議有這么多的限制，因此論文提出了 TAPIR 這個(gè)算法來解決事務(wù)的 linearizable ordering 問題。TAPIR 的具體算法請(qǐng)閱讀論文吧，這里不再?gòu)?fù)述。大體的思路就是客戶端參與事務(wù)的沖突檢測(cè)（OCC validation checks），Leader 執(zhí)行IR 的 merge 過程，對(duì)于還沒有committed 的事務(wù)（可能 abort ，也可能來不及提交)，重新跑一遍 OCC 檢測(cè)沖突，根據(jù)結(jié)果來決定最終是提交還是回滾。
對(duì)于復(fù)制和恢復(fù)的描述：
TAPIR’s sync function runs at the other replicas to reconcile TAPIR state with
the master records, correcting missed operations or consensus results where
the replica did not agree with the group. It simply applies operations and
consensus results to the replica’s state: it logs aborts and commits, and
prepares uncommitted transactions where the group responded PREPARE-OK.
傳統(tǒng)兩階段提交， Google spanner 之類的思路：
TAPIR 的流程：
關(guān)于 TAPIR 的解讀推薦兩篇博客:Building Consistent Transactions with Inconsistent Replication和Paper review: Building Consistent Transactions with Inconsistent Replication (SOSP’15)。 TAPIR 的源碼只包含了 normal case 的處理，恢復(fù)之類的過程都是沒有的，對(duì)于 recovery 的一些疑問，可以參考 A FEW WORDS ABOUT INCONSISTENT REPLICATION (IR)，同樣也是我的疑問，這在實(shí)際工程中是非常重要的部分，但是論文卻是匆匆?guī)н^。
