簡述paxos演算法的實現過程

『壹』 如何淺顯易懂地解說 Paxos 的演算法

Paxos演算法解決的問題是在一個可能發生消息可能會延遲、丟失、重復的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。

一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。

一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。 節點通信存在兩種模型：共享內存和消息傳遞。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。

分析Paxos演算法的目的

Paxos演算法的目的是為了解決分布式環境下一致性的問題。多個節點並發操縱數據，如何保證在讀寫過程中數據的一致性，並且解決方案要能適應分布式環境下的不可靠性（系統如何就一個值達到統一）。

Paxos演算法中，可分為4種角色：

• Proposer：提議發起者，處理客戶端請求，將客戶端的請求發送到集群中，以便決定這個值是否可以被批准。

• Acceptor：提議批准者，負責處理接收到的提議，他們的回復就是一次投票。會存儲一些狀態來決定是否接收一個值。

• Client：產生議題者，Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。

• Learner：最終決策學習者，最終學習的目標是Acceptor們最終接受了什麼議題？

Paxos演算法的原理

例如：公司商定年會舉辦的地點，每個人都可以提出建議。在現實環境中我們可以在一個會議室共同討論或在微信群中討論（基於內存共享方式）；但在基於消息傳遞的分布式環境中每個人只能通過手機簡訊與其它人通過。如何在這種會延遲、丟失的環境中確定一個年會舉辦地點。

Paxos演算法是這樣解決這個問題：

每個人都可以提出建議、同意建議、接受建議

少數服從多數。只要建議被多數人同意即可確定該建議。

於是確定以下討論方式：

• 只有被提出來的建議才能被大家同意。

• 最終只能確定一個建議。

• 如果某個人認為大家同意了某 個建議，那麼這個建議必須真的是被大家同意的。

Paxos演算法圖解



在實現環境中會通過一次提議，選擇一個Leader。後續所有的提議都只能由Leader提出。

原來paxos演算法里的角色都是這樣的不靠譜，不過沒關系，結果靠譜就可以了。該演算法就是為了追求結果的一致性。

原文鏈接：什麼是Paxos演算法？Paxos演算法是區塊鏈核心演算法之一

『貳』 paxos演算法是什麼

Paxos演算法是萊斯利·蘭伯特（Leslie Lamport，就是LaTeX中的＂La"，此人現在在微軟研究院）於1990年提出的一種基於消息傳遞的一致性演算法。這個演算法被認為是類似演算法中最有效的。

蘭伯特提出的Paxos演算法包含2個部分：

一個是Basic Paxos演算法，描述的是多節點之間如何就某個值（提案Value）達成共識；

另一個是Multi-Paxos思想，描述的是執行多個Basic Paxos實例，就一系列值達成共識

可因為蘭伯特提到的Multi-Paxos思想，缺少代碼實現的必要細節（比如怎麼選舉領導者），所以在理解上比較難。Basic Paxos是Multi-Paxos思想的核心。

(2)簡述paxos演算法的實現過程擴展閱讀

背景

Paxos演算法解決的問題是一個分布式系統如何就某個值（決議）達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點執行相同的操作序列，那麼他們最後能得到一個一致的狀態。

為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。

一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。因此從20世紀80年代起對於一致性演算法的研究就沒有停止過。節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。

『叄』 如何淺顯易懂地解說 Paxos 的演算法

Paxos真的並不是很容易理解，而且最初版本的Paxos也不能實現，相對而言一些變種演算法更加容易理解，而且在工程實現上也比較簡單。

其實看論文確實是最有效的，但卻不是最高效的。理解運作過程也好，推導過程也好，大家的回答都是為了幫助大家更高效的掌握這門演算法。大家的回答已經很好， 我這里作為補充，也是算另一個角度，幫助大家去理解paxos的數學推導過程，寫了這么一篇文章：Paxos理論介紹(1): 樸素Paxos演算法理論推導與證明 - 分布式一致性與高可用實踐 - 知乎專欄。希望能幫到大家。

『肆』 一致性演算法（Paxos、Raft、ZAB)

一致性演算法（Paxos、Raft、ZAB)

什麼是一致性

1、弱一致性
a、最終一致性
i、DNS（Domain Name System）
j、Gossip（Cassandra的通信協議）

以DNS為例：

2、強一致性
a、同步
b、Paxos
c、(multi-paxos)
d、ZAB(multi-paxos)

DNS 就是一種最終一致性，比如 上圖中 增加一條記錄： www.hyb.small.com , 我們從其他DNS伺服器一時會讀取不到，但是過一會就會讀取得到了。

數據不能存在單點上。
分布式系統對fault tolerence的一般解決方案是state machine replication 。

准確的來說應該是 state machine replication 的共識（consensus）演算法。

paxos其實是一個共識演算法，系統的最終一致性，不僅需要達成共識，還會取決於client的行為

主從同步復制

1、Master 接受寫請求
2、Master 復制日誌到slave
3、Master 等待，直到所有從庫返回

問題：

任何一個節點失敗，哪怕是從節點（Slave）同步失敗，都會導致整個集群不可用，雖然保證了一致性，但是可用性卻大大降低

基本想法：
a、多數派：
每次寫都保證寫入大於N/2個節點，每次讀保證從大於N/2個節點中讀。
比如5個節點，每次寫大於3個節點才算成功；讀也是大於3個節點才算成功。

b、多數派還不夠！
在並發環境下，無法保證系統正確性，順序非常重要。比如下圖的 Inc 5; Set 0; 執行順序亂了，結果就會引發錯亂。

Lesile Lamport,Latex的發明者。

為描述Paxos演算法早昌，Lamport虛擬了一個叫做Paxos的希臘城邦，這個島按照議會民主制的政治模式制定法律，但是沒有人願意將自己的全部時間和精力放在這種事上，所以無論是議員、議長或者傳遞消息的時間。

Paxos

1、Basic Paxos
2、Multi Paxos
3、Fast Paxos

強一致性演算法---Basic Paxos

角色叢睜晌介紹：

Client:系統外部角色，請求發起者。像民眾

Propser: 接滲鋒受Client 請求，向集群提出提議(propose)。並在沖突發生時，起到沖突調節的作用。像議員替民眾提出議案

Accpetor(Voter): 提議投票和接收者，只有在形成法定人數(Quorum,一般即為majority 多數派)時，提議才會最終接受，像國會。

Learner:提議接受者，backup，備份，對集群一致性沒什麼影響，像記錄員；

步驟、階段(phases):
1、Phase 1a:Prepare
proposer 提出一個提案，編號為N，此N 大於這個proposer之前提出提案編號，向acceptors請求同意，要求有quorum接受的才行。

2、Phase 1b:Promise
N 必須大於此acceptor之前接受的任何提案編號，才會接受，否則會拒絕。

3、Phase 2a: Accept
如果達到了多數派，proposer會發出accept請求，此請求包含提案編號N ,以及提案內容。

4、Phase 2b:Accepted
如果此acceptor在此期間沒有收到任何編號大於N的提案，則接受此提案內容，否則忽略。

流程圖如下：

操作步驟如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;

1、Acceptor部分節點失敗，但達到了Quoroms，此時仍然會成功。

如果有一個Acceptor因為各種原因掛掉了，3個Acceptors變成了2個Acceptors，還是滿足>n/2 的要求，所以還是會成功。

2、Proposer失敗，上一次記錄不會被寫入Proposer表，然後重新開啟一個新的Proposer，來替代上次的Proposer來處理未完成請求，此時編號已經增加為2，也就是Prepare(2)

Basic Paxos when an Proposer fails
如果Proposer 在發送了一條Accept消息之後，但是還沒收到Accepted消息之前就掛掉了，只有一個Acceptor接收到了Accept消息。那麼整個Paxos協議就沒法進行下去了，這時一個新的Leader（Proposer）會被選舉出來，重新開始一輪新的共識。

Basic Paxos潛在的問題是：活鎖（liveness）或eling

Basic Paxos很有可能出現這種情況：
1、議員A(proposer A)說我們來討論提案1，大部分議員說：「好，我們來討論提案1」；
2、但是此時議員A還沒有說內容是什麼，這時候又來了一個議員B，又來說：「我們來討論提案2」；這時候大部分還沒有接受提案1，提案2的編號是大於提案1的，這時候大部分還沒有接受議案2；
3、這時候議員A以為網路斷了，然後把編號改下，內容不變然後提出議案3；然後議案4、議案5....
這樣就形成了活鎖。
解決活鎖的方法是用Random的timeout，當兩個沖突的時候用一個隨機的等待時間；當自己提議未生效時，再發起提議等待幾秒。

Basic-Paxos是一個無限循環的2PC，1條日誌的確認至少需要2個RTT + 2次落盤（1次是prepare的廣播與回復，1次是accept的廣播與回復）。

Basic Paxos when multiple Proposers conflict
最後再描述一個最復雜的情況，即有多個Proposers認為他們是Leaders，並不斷的發送Prepare請求。為什麼會有多個Leaders呢？ 有可能一個Proposer當了一段時間Leader之後掛掉了，新的Proposer被選為Leader繼續新的一輪共識。後面掛掉的Proposer又恢復了，它認為自己還是Leader，所以繼續發送Prepare請求。

Basic Paxos的問題
難實現（角色太多）、效率低（2輪RPC）、活鎖問題

Multi Paxos:
新概念，Leader;唯一的propser，所有請求都需經過此Leader;

只有一個Proposer，沒有第二個Proposer； 這個Proposer就是Leader,沒人跟他搶;

再者分布式系統必須串列執行所有提議，否則就會出現前面說的順序問題。

--------First Request(第一次執行)----------
Request
Prepare(N) //選Leader
Promise(N,I,{Va,Vb,Vc})
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

--------Following Request(第二次或者以後)----------
Request
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

第二次或者以後，就不用再選Leader了 直接執行Request 請求，由Leader 發出議案。
如果Leader 掛了 就選下一個總統Leader(N+1)

減少角色，進一步簡化，在Basic-Paxos中我們區分了很多角色，有Clients、Proposers、Acceptors、 Learners，實際上Proposers、Acceptors 、Leanrners可以合並成一個，統稱為Server，下面是合並之後的序列圖。

Multi-Paxos when roles are collapsed and the leader is steady
同樣的，當Leader很穩定的時候，我們可以在接下來的執行中忽略Phase 1. 如下圖所示：

Raft
1、劃分三個子問題
a、Leader Election
b、Log Replication
c、Safely
2、重定義角色
a、Leader
b、Follower
c、Candidate

原理動畫解釋： http://thesecretlivesofdata.com/raft
場景測試： https://raft.github.io

Raft 是比 Multi Paxos 還要簡單的一個版本
一致性並不代表完全正確性！三個可能結果：成功，失敗，unknown

詳細內容參考：
https://www.jianshu.com/p/6cd41fe0b8f6

強一致性演算法--ZAB
基本與raft相同。在一些名詞的叫法上有些區別：如ZAB將某一個leader的周期稱為epoch，而raft則稱為term。實現上也有些許不同：如raft保證日誌連續性，心跳方向為leader至follower，ZAB則相反。