【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最根本的原理是什麼，那麼就是這個簡單性質。也就是說：兩個過半的集合必然存在交集，也就是肯定是相等的，也就是肯定達成了一致。