【Zookeeper核心原理】Paxos協議的原理和實際運行中的應用流程分析_李浩宇Alex

theme: smartblue

本文已參與「掘力星計劃」，贏取創作大禮包，挑戰創作激勵金。

Paxo算法介紹

Paxos算法是萊斯利·蘭伯特(Leslie Lamport)1990年提出的一種基於消息傳遞的一致性算法。

Paxos產生背景

Paxos算法是基於消息傳遞且具有高度容錯特性的一致性算法，是目前公認的解決分佈式一致性問題最有效的算法之一，其解決的問題就是在分佈式系統中如何就某個值（決議）達成一致。

Paxos算法主要是針對Zookeeper這樣的master-slave集羣對某個決議達成一致，也就是副本之間寫或者leader選舉達成一致。我覺得這個算法和狹義的分佈式事務不是一樣的。

在常見的分佈式系統中，總會發生諸如機器宕機或網絡異常（包括消息的延遲、丟失、重複、亂序，還有網絡分區），也就是會發生異常的分佈式系統)等情況。

Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分佈式系統中，快速且正確地在集羣內部對某個數據的值達成一致。也可以理解成分佈式系統中達成狀態的一致性。

Paxos保證一致性：

Paxos算法是分佈式一致性算法用來解決一個分佈式系統如何就某個值(決議)達成一致的問題。一個典型的場景是，在一個分佈式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。

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

分佈式系統中一般是通過多副本來保證可靠性，而多個副本之間會存在數據不一致的情況。所以必須有一個一致性算法來保證數據的一致，描述如下：

假如在分佈式系統中初始是各個節點的數據是一致的，每個節點都順序執行系列操作，然後每個節點最終的數據還是一致的。

Paxos算法就是解決這種分佈式場景中的一致性問題。對於一般的開發人員來説，只需要知道paxos是一個分佈式選舉算法即可。

多個節點之間存在兩種通訊模型：共享內存（Shared memory）、消息傳遞（Messages passing），Paxos是基於消息傳遞的通訊模型的。

發生網絡分區所導致的數據不一致問題，就是Paxo算法需要解決的問題！

拜占庭問題

拜占庭問題：是指拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。

問題是這些將軍在地理上是分隔開來的，只能依靠通訊員進行傳遞命令，但是通訊員中存在叛徒，它們可以篡改消息，叛徒可以欺騙某些將軍採取進攻行動；
促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。

Paxos算法的前提假設是不存在拜占庭將軍問題，即：信道是安全的（信道可靠），發出的信號不會被篡改，因為Paxos算法是基於消息傳遞的。它也是 Paxos算法的提出者,由於硬件和網絡原因而造成的消息不完整問題，只需要一套簡單的校驗算法即可。

Paxos算法概念

在Paxos算法中，有三種角色：

Proposer（投票發起者）：Proposer負責提出提案
Acceptor（投票接受者）：Acceptor負責對提案作出裁決（accept與否）
Learner（節點學習者）：learner負責學習提案結果

Proposal：這裏的一個很重要的概念叫提案（Proposal），可以理解為我們的一個操作或者數據信息傳遞，最終要達成一致的value就在提案裏。

Paxo算法的特點介紹

一個進程或者服務節點可能同時充當多種角色，可能既是Proposer又是Acceptor又是Learner 。

只要Proposer發的提案被Acceptor接受（半數以上的Acceptor同意才行），Proposer就認為該提案裏的value被選定了。
Acceptor告訴Learner哪個value被選定，Learner就認為那個value被選定。只要Acceptor接受了某個提案，Acceptor就任務該提案裏的value被選定了。

Paxo算法的投票和認可機制

為了避免單點故障，會有一個Acceptor集合，Proposer向Acceptor集合發送提案，Acceptor集合中的每個成員都有可能同意該提案且每個Acceptor只能批准一個提案，只有當一半以上的成員同意了一個提案，就認為該提案被選定了。

Paxos算法的解決的問題描述

有多個（propose）value（value在提案Proposal裏）的進程集合。一致性算法需要保證提出的這麼多value中，只有一個value被選定（chosen）。
如果沒有value被提出，就不應該有value被選定。如果一個value被選定，那麼所有進程都應該能學習（learn）到這個被選定的value。
只有被提出的value才能被選定，只有一個value被選定，並且如果某個進程認為某個value被選定了，那麼這個value必須是真的被選定的那個。
保證最終有一個value會被選定，當value被選定後，進程最終也能獲取到被選定的value。

Paxos算法的過程

Paxos算法類似於兩階段提提交，其算法執行過程分為兩個階段。具體如下：

階段一（prepare階段）：
- Proposer選擇一個提案編號N，然後向半數以上的Acceptor發送編號為N的Prepare請求:Proposal（N）。
- 如果一個Acceptor收到一個編號為N的Prepare請求：
- 若小於它已經響應過的請求，則拒絕，不迴應或回覆error。
- 若N大於該Acceptor已經響應過的所有Prepare請求的編號（maxN），那麼它就會將它已經接受過的編號最大的提案作為響應反饋給Proposer，同時該Acceptor承諾不再接受任何編號小於N的提案。

如果還沒有的accept提案的話返回{pok，null，null}

階段二（accept階段）：
- 如果一個Proposer收到半數以上Acceptor對其發出的編號為N的Prepare請求的響應，那麼它就會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編號最大的提案的value，如果響應中不包含任何提案，那麼V就由Proposer自己決定。
- 如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大於N的Prepare請求做出過響應，它就接受該提案。
- 如果N小於Acceptor以及響應的prepare請求，則拒絕，不迴應或回覆error（當proposer沒有收到過半的迴應，那麼他會重新進入第一階段，遞增提案號，重新提出prepare請求）。

Paxos算法的過半依據

Paxos基於的過半數學原理：我們稱大多數（過半）進程組成的集合為法定集合，兩個法定（過半）集合必然存在非空交集，即至少有一個公共進程，稱為法定集合性質。例如A,B,C,D,F進程組成的全集，法定集合Q1包括進程A,B,C，Q2包括進程B,C,D，那麼Q1和Q2的交集必然不在空，C就是Q1，Q2的公共進程。如果要説Paxos最根本的原理是什麼，那麼就是這個簡單性質。也就是説：兩個過半的集合必然存在交集，也就是肯定是相等的，也就是肯定達成了一致。