1. Paxos和Raft算法簡介

1.1 Paxos算法簡介

Paxos算法（Lamport 2001）是Lesile Lamport提出的一種基于消息傳遞、高容錯的共識算法。 分布式系統中的節點通信有兩種模型：共享內存和消息傳遞。 基于消息傳遞通信模型的分布式系統不可避免地會遇到進程減慢和殺掉、消息延遲、丟失、重復等問題。 Paxos算法是一種在存在上述異常的情況下仍能保持一致性的協議。Paxos算法用一個希臘故事來描述。 在Paxos中，共有三種角色，分別是Proposer（用于發布提案提案）、Acceptor（可以接受或拒絕提案）、Learner（研究選中的提案，當提案被超過一半的Acceptor接受時）。 下面是Paxos想要解決的問題的更精確的定義：1. 決議（值）只有在提案者提出后才能被批準 2. 在 Paxos 算法的一個執行實例中，只有一個值被批準（選擇） 3. 學習者只能得到選擇的值

所有食物請求必須由全局唯一的服務器協調和處理。 這樣的服務器稱為領導者服務器，其余的其他服務器成為跟隨者服務器。 Leader 服務器負責將客戶端事務請求轉換為事務提案并將提案分發給集群中的所有 follower 服務器。 之后，Leader服務器需要等待所有Follower服務器的反饋。 一旦超過一半的follower服務器給出了正確的反饋，leader就會再次向所有follower服務器分發commit消息，要求其提交之前的提案。

1.2 Raft算法簡介

Raft（Ongaro and Ousterhout，2014）實現了與 Paxos 相同的功能，將分布式一致性分解為多個子問題： 領導者選舉、日志復制、安全、日志、成員資格變更 成員資格變更。Raft 將系統中的角色分為領導者leader、追隨者和候選人：

Leader：接受客戶端請求，并將日志請求同步給Follower。 當日志同步到大部分節點后，它會告訴Follower提交日志。
Follower：接受并持久化Leader同步的日志，并在Leader通知可以提交日志后提交日志。
Candidate：領導者選舉過程中的臨時角色。
Raft要求系統任何時候最多有一個Leader，一個普通的選舉過程中只有Leader和Followers。

2. Raft的優勢總結

2.1 raft更容易理解

對于學習者來說，Raft 更容易理解，因為 Raft 將算法中使用的各種元素和過程描述為民主社會中的選舉。領導人(leader)由民眾投票選舉產生。 在Raft算法的開始，沒有leader，集群中的所有參與者都是群眾。 接著就先開始了一場普通的選舉。 在集群leader的選舉期間，全體群眾均可參加選舉。 這時，全體群眾的角色就變成了候選人(candidate)，通過民主投票選出leader。 之后，領導人的任期開始，然后選舉結束。 除leader外，所有candidate都變回了群眾的角色，服從leader的領導。
Paxos令人難以理解的地方在于安全性的保障。 Lamport在論文中指出“我們要求不同的提案(proposal)有不同的編號”。 然而，這個對于理解安全性來說重要的概念在接下來的論文中并沒有得到清晰的解釋。 Raft算法提出了Term的概念來解決這個問題。 Raft算法的核心概念與現實民主制度非常吻合，因此很容易理解。

2.2 raft更容易實現

對paxos的描述側重于理論。 根據 Google 的chubby論文，“Paxos 算法的描述與現實世界系統的需求之間存在顯著差距……最終的系統將基于未經驗證的協議。” paxos中的原論文并沒有給出提案編號和日志復制的具體實現方法。 如果不考慮小細節，整個協議的一致性就會崩潰。 而且，對于發現和糾正錯誤的實現細節，也沒有詳細的現成參考資料。 綜上所述，需要對paxos協議有深刻的理解才能在實現出相應的一致性應用。 在博士論文《BRIDGING THEORY AND PRACTICE of the Raft protocol》中，作者則通過案例具體展示出了如何使用 raft 協議構建一致的狀態機應用。