國科大學(xué)習(xí)生活（期末復(fù)習(xí)資料、課程大作業(yè)解析、學(xué)習(xí)文檔等）: 文章專欄（點(diǎn)擊跳轉(zhuǎn)）
大數(shù)據(jù)開發(fā)學(xué)習(xí)文檔（分布式文件系統(tǒng)的實(shí)現(xiàn)，大數(shù)據(jù)生態(tài)圈學(xué)習(xí)文檔等）: 文章專欄（點(diǎn)擊跳轉(zhuǎn)）

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB

1. 什么是分布式一致性算法？

分布式一致性算法是用于在分布式系統(tǒng)中確保數(shù)據(jù)一致性的一類算法。在分布式計(jì)算環(huán)境中，數(shù)據(jù)通常會(huì)分布在多個(gè)節(jié)點(diǎn)或副本中，并且這些節(jié)點(diǎn)可能由于網(wǎng)絡(luò)延遲、故障或其他原因而導(dǎo)致數(shù)據(jù)的不一致。因此，分布式一致性算法的目標(biāo)是確保分布式系統(tǒng)中的所有節(jié)點(diǎn)最終都能達(dá)到一致的狀態(tài)。
分布式一致性算法可以分為兩種主要類型：強(qiáng)一致性和弱一致性。

1. 強(qiáng)一致性算法（Strong Consistency）：強(qiáng)一致性算法保證在任何時(shí)刻，系統(tǒng)中的任意節(jié)點(diǎn)都可以看到相同的數(shù)據(jù)副本，并且對(duì)數(shù)據(jù)的任何操作都會(huì)立即反映在系統(tǒng)的其他部分。常見的強(qiáng)一致性算法包括Paxos和Raft。
2. 弱一致性算法（Weak Consistency）：弱一致性算法允許在分布式系統(tǒng)中的不同節(jié)點(diǎn)之間存在一定時(shí)間上的數(shù)據(jù)不一致，以提高系統(tǒng)的可用性和性能。弱一致性算法通常以最終一致性為目標(biāo)，即系統(tǒng)最終會(huì)達(dá)到一致的狀態(tài)。常見的弱一致性算法包括Gossip協(xié)議和CRDTs（Conflict-free Replicated Data Types）。

分布式一致性算法的選擇取決于系統(tǒng)的需求和特定的應(yīng)用場景。強(qiáng)一致性算法提供了嚴(yán)格的一致性保證，但可能會(huì)對(duì)性能產(chǎn)生較大的影響。而弱一致性算法可以在某些場景下提供更高的性能，但對(duì)數(shù)據(jù)的一致性要求較低。
因此，在設(shè)計(jì)分布式系統(tǒng)時(shí)，需要根據(jù)實(shí)際需求綜合考慮一致性和性能之間的權(quán)衡。

1.1 Paxos一致性協(xié)議

Paxos是一種分布式系統(tǒng)中的一致性算法，用于解決分布式系統(tǒng)中節(jié)點(diǎn)之間的數(shù)據(jù)一致性問題。它是由Leslie Lamport于1990年提出的。在 Paxos 算法中，把數(shù)據(jù)修改用提案標(biāo)識(shí)：Proposal:提案，即分布式系統(tǒng)的修改請(qǐng)求，可以表示為[提案編號(hào)N，提案內(nèi)容value]

在 Paxos 算法中有三種角色：Proposer，Acceptor，Learners（注意，每個(gè)節(jié)點(diǎn)都可以身兼數(shù)職）

• Proposer ：發(fā)起提案，只要 Proposer 發(fā)的提案被半數(shù)以上 Acceptor 接受，Proposer 就認(rèn)為該提案里的 value 被選定了。
• Acceptor : 只要 Acceptor 接受了某個(gè)提案，Acceptor 就認(rèn)為該提案里的 value 被選定了。不同意比自己以前接收過的提案編號(hào)要小的提案，例如A以前給N號(hào)提案表決過，那么再收到小于等于N號(hào)的提案時(shí)就直接拒絕了
• Learners : Acceptor 告訴 Learner 哪個(gè) value 被選定，Learner 就認(rèn)為那個(gè) value 被選定。類似記錄被通過提案的記錄員，負(fù)責(zé)記錄提案

Paxos算法的核心思想是通過多個(gè)輪次的消息傳遞和投票來達(dá)成共識(shí)。算法的主要流程可以概括如下：

1. 準(zhǔn)備階段（Prepare）：提議者（Proposer）向接受者（Acceptor）發(fā)送Prepare請(qǐng)求，在接受者中選擇一個(gè)提案編號(hào)（Proposal Number）作為準(zhǔn)備的回應(yīng)。
2. 承諾階段（Promise）：如果一個(gè) Acceptor 收到一個(gè)編號(hào)為 N 的 Prepare 請(qǐng)求，且 N 大于該 Acceptor 已經(jīng)響應(yīng)過的所有 Prepare 請(qǐng)求的編號(hào)，那么它就會(huì)將它已經(jīng)接受過的編號(hào)最大的提案（如果有的話）作為響應(yīng)Propose反饋給 Proposer，同時(shí)該 Acceptor 承諾不再接受任何編號(hào)小于 N 的提案。
3. 學(xué)習(xí)階段（Learner）：如果提議者（Proposer）收到了大多數(shù)接受者（Acceptor）的承諾（Promise），那么它會(huì)向所有節(jié)點(diǎn)發(fā)送確定的請(qǐng)求（Accept請(qǐng)求），要求它們接受提案。接受者在接收到大多數(shù)的接受請(qǐng)求后，就可以接受該提案。
   

通過多個(gè)輪次的消息傳遞，Paxos算法最終可以使得所有節(jié)點(diǎn)達(dá)成一致，并選擇一個(gè)確定的提案作為共識(shí)結(jié)果。

Paxos示例1：

Paxos示例2：

Paxos算法是一種高度復(fù)雜的算法，尤其是在實(shí)現(xiàn)細(xì)節(jié)和各種優(yōu)化策略方面。它是分布式系統(tǒng)中的重要工具，用于確保數(shù)據(jù)的一致性和可靠性。

1.2 Paxos算法缺陷

在網(wǎng)絡(luò)復(fù)雜的情況下，一個(gè)應(yīng)用Paxos算法的分布式系統(tǒng)，可能很久無法收斂，甚至陷入活鎖的情況：

為解決這種問題的出現(xiàn)，下面我們來介紹另一種一致性算法：Raft。

1.3 Raft一致性協(xié)議

Raft 是一種分布式一致性算法，用于在分布式系統(tǒng)中實(shí)現(xiàn)數(shù)據(jù)的一致性和高可用性。它由 Diego Ongaro 和 John Ousterhout 在 2013 年提出，并于 2014 年發(fā)表的論文中詳細(xì)描述了算法的設(shè)計(jì)原則和機(jī)制。

根據(jù)Paxos的改進(jìn)：整個(gè)系統(tǒng)只有一個(gè)Proposer，稱之為Leader。
若集群中沒有Leader，則在集群中選出一個(gè)節(jié)點(diǎn)并聲明它為第M任Leader。集群的Acceptor只表決最新的Leader發(fā)出的最新的提案，其他步驟和Paxos相同。Raft 和 Paxos 一樣只要保證 n/2+1 節(jié)點(diǎn)正常就能夠提供服務(wù)；Raft 把算法流程分為三個(gè)子問題：

• 選舉（Leader election）
• 日志復(fù)制（Log replication）
• 安全性（Safety）
  

Raft 算法的領(lǐng)導(dǎo)者選舉機(jī)制具有以下過程：

1. 初始狀態(tài)：當(dāng)一個(gè) Raft 集群啟動(dòng)時(shí)，所有節(jié)點(diǎn)都處于 Follower 狀態(tài)。每個(gè)節(jié)點(diǎn)都等待接收來自 Leader 的心跳消息。
2. Follower 成為 Candidate：如果一個(gè) Follower 在一段時(shí)間內(nèi)未收到來自 Leader 的心跳消息，它將成為 Candidate，并開始發(fā)起選舉。
3. 發(fā)起選舉：一旦成為 Candidate，節(jié)點(diǎn)將增加自己的當(dāng)前任期號(hào)（term），然后發(fā)送包含該任期號(hào)和候選人 ID 的請(qǐng)求給其他節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)只能投一次票，因此在一次選舉中只會(huì)有一個(gè) Candidate 獲勝。
4. 投票過程：每個(gè)節(jié)點(diǎn)在收到來自 Candidate 的選舉請(qǐng)求后，會(huì)根據(jù)以下條件進(jìn)行投票決策：
   • 如果該節(jié)點(diǎn)已經(jīng)投過票給了其他 Candidate，并且該 Candidate 的任期號(hào)更大，則拒絕投票。
   • 如果該節(jié)點(diǎn)的日志更新較新，沒有落后于 Candidate 的日志，則支持該 Candidate 并重置自己的選舉超時(shí)計(jì)時(shí)器。
5. 選舉勝出條件：一個(gè) Candidate 可以成為新的 Leader，需要滿足以下條件之一：
   • 收到了大多數(shù)節(jié)點(diǎn)的選票，并且得票數(shù)超過了一半。
   • 在選舉過程中，其他節(jié)點(diǎn)成為了 Leader（新的 Leader 后來者居上）。
6. 成為 Leader：當(dāng)一個(gè) Candidate 贏得選舉后，它將成為新的 Leader。它會(huì)發(fā)送心跳消息給所有節(jié)點(diǎn)來維持自己的領(lǐng)導(dǎo)地位，并準(zhǔn)備接收客戶端的操作請(qǐng)求。

通過這樣的領(lǐng)導(dǎo)者選舉機(jī)制，Raft 算法保證了集群中只存在一個(gè) Leader，使得整個(gè)系統(tǒng)能夠穩(wěn)定運(yùn)行。而選舉過程中使用的隨機(jī)化和選舉超時(shí)機(jī)制，確保了快速選出新的 Leader，從而減少系統(tǒng)的不可用時(shí)間。

相對(duì)于其他一致性算法，如 Paxos，Raft 更加易于理解和實(shí)現(xiàn)。它的設(shè)計(jì)模塊化，便于擴(kuò)展和維護(hù)。它的目標(biāo)是提供一個(gè)可靠的分布式一致性算法，以簡化構(gòu)建分布式系統(tǒng)的難度。
Raft動(dòng)態(tài)圖片演示鏈接
一定要看！
一定要看！
一定要看！重要的事情說三遍，演示超級(jí)詳細(xì)?。?！

2. 什么是Zookeeper？

Zookeeper是一個(gè)用于構(gòu)建分布式應(yīng)用的開源協(xié)調(diào)服務(wù)。它提供高度可靠的分布式協(xié)調(diào)功能，使得分布式應(yīng)用可以在大規(guī)模集群中進(jìn)行協(xié)作和同步。

Zookeeper可以被廣泛應(yīng)用于分布式系統(tǒng)中的各種場景，如分布式鎖、領(lǐng)導(dǎo)選舉、配置管理、命名服務(wù)等。它被許多分布式系統(tǒng)和框架使用，比如Hadoop、Kafka等。Zookeeper的簡單和可靠性使得它成為構(gòu)建可擴(kuò)展和彈性的分布式系統(tǒng)的重要工具之一。

2.1 ZAB一致性協(xié)議

ZAB（ZooKeeper Atomic Broadcast）是 Apache ZooKeeper 分布式協(xié)調(diào)服務(wù)中使用的一種原子廣播協(xié)議。它旨在實(shí)現(xiàn)分布式系統(tǒng)中的一致性和可靠性。
ZAB 協(xié)議將 ZooKeeper 服務(wù)集群中的節(jié)點(diǎn)分為兩個(gè)角色：Leader 和 Follower。Leader 負(fù)責(zé)接收并處理客戶端請(qǐng)求，然后將請(qǐng)求廣播給集群中的所有節(jié)點(diǎn)（包括自己）。Follower 則對(duì) Leader 發(fā)送的消息進(jìn)行復(fù)制和追隨，以保持整個(gè)集群的數(shù)據(jù)一致性。

選舉參數(shù)
在介紹選舉流程之前，需要介紹幾個(gè)參數(shù)，

• myid: 服務(wù)器ID，這個(gè)是在安裝Zookeeper時(shí)配置的，myid越大，該服務(wù)器在選舉中被選為Leader的優(yōu)先級(jí)會(huì)越大。ZAB算法中通過myid來規(guī)避了多個(gè)節(jié)點(diǎn)可能有相同zxid問題，（注意可以對(duì)比之前的Raft算法，Raft算法中通過隨機(jī)的timeout來規(guī)避多個(gè)節(jié)點(diǎn)可能同時(shí)成為Leader的問題）。
• zxid: 事務(wù)ID，這個(gè)是由Zookeeper集群中的Leader節(jié)點(diǎn)進(jìn)行Proposal時(shí)生成的全局唯一的事務(wù)ID，由于只有Leader才能進(jìn)行Proposal，所以這個(gè)zxid很容易做到全局唯一且自增。因?yàn)镕ollower沒有生成zxid的權(quán)限。zxid越大，表示當(dāng)前節(jié)點(diǎn)上提交成功了最新的事務(wù)，這也是為什么在崩潰恢復(fù)的時(shí)候，需要優(yōu)先考慮zxid的原因。
• epoch: 投票輪次，每完成一次Leader選舉的投票，當(dāng)前Leader節(jié)點(diǎn)的epoch會(huì)增加一次。在沒有Leader時(shí)，本輪此的epoch會(huì)保持不變。

另外在選舉的過程中，每個(gè)節(jié)點(diǎn)的當(dāng)前狀態(tài)會(huì)在以下幾種狀態(tài)之中進(jìn)行轉(zhuǎn)變。

LOOKING: 競選狀態(tài)。
FOLLOWING: 隨從狀態(tài)，同步Leader 狀態(tài)，參與Leader選舉的投票過程。
OBSERVING: 觀察狀態(tài)，同步Leader 狀態(tài)，不參與Leader選舉的投票過程。
LEADING: 領(lǐng)導(dǎo)者狀態(tài)。

ZAB 協(xié)議的核心機(jī)制包括兩個(gè)階段：崩潰恢復(fù)階段（Leader 選舉）和消息廣播階段。

1. 崩潰恢復(fù)階段（Leader 選舉）：

   • 選舉算法：在初始啟動(dòng)或 Leader 崩潰的情況下，ZAB 協(xié)議會(huì)啟動(dòng)選舉算法來選舉新的 Leader。節(jié)點(diǎn)將發(fā)送選舉請(qǐng)求（包含自己的 ID 和選舉輪次）給所有節(jié)點(diǎn)，并等待其他節(jié)點(diǎn)的投票。某個(gè)節(jié)點(diǎn)收到投票請(qǐng)求后，會(huì)比較選舉輪次和節(jié)點(diǎn) ID 來決定是否投票。最終，根據(jù)投票數(shù)量和選舉規(guī)則，選舉出新的 Leader 節(jié)點(diǎn)。

   • 同步數(shù)據(jù)：新選出的 Leader 需要將自己的數(shù)據(jù)狀態(tài)同步給其他節(jié)點(diǎn)，以確保整個(gè)集群達(dá)到一致性。Leader 會(huì)將自己的數(shù)據(jù)變更記錄（事務(wù)日志）發(fā)送給所有的 Follower 節(jié)點(diǎn)，然后等待大多數(shù)節(jié)點(diǎn)確認(rèn)接收。

2. 消息廣播階段：

   • Leader 的操作：一旦選舉成功，Leader 負(fù)責(zé)接收客戶端的操作請(qǐng)求，并將這些請(qǐng)求轉(zhuǎn)換為事務(wù)日志，然后將日志廣播給所有的 Follower 節(jié)點(diǎn)。
   • Follower 的復(fù)制：Follower 節(jié)點(diǎn)接收到 Leader 發(fā)送的事務(wù)日志后，會(huì)將其復(fù)制到本地的存儲(chǔ)中，并發(fā)送確認(rèn)消息給 Leader。當(dāng) Leader 收到大多數(shù)節(jié)點(diǎn)的確認(rèn)消息后，可以確認(rèn)該日志已經(jīng)被復(fù)制成功。
   • 提交和應(yīng)用：在大多數(shù)節(jié)點(diǎn)確認(rèn)接收到某個(gè)事務(wù)日志后，Leader 可以將該事務(wù)日志提交，并將結(jié)果應(yīng)用到自己的狀態(tài)中。然后 Leader 會(huì)通知所有的節(jié)點(diǎn)該事務(wù)的提交結(jié)果，以保持整個(gè)集群狀態(tài)的一致性。

Zookeeper選舉機(jī)制示例：
注：示例中的服務(wù)器ID即為上文中的myid、事務(wù)ID即為上文zxid中的count、邏輯時(shí)鐘即為上文中的epoch

ZAB一致性協(xié)議講解視頻B站鏈接

強(qiáng)烈建議觀看，畢竟純文字的形式對(duì)于知識(shí)的理解不如演示動(dòng)畫的形式來的快

ZAB 協(xié)議通過 Leader 選舉和日志復(fù)制的方式實(shí)現(xiàn)了數(shù)據(jù)的一致性和可靠性。它確保了在集群中只有一個(gè) Leader，避免了數(shù)據(jù)沖突。同時(shí)，ZAB 協(xié)議提供了恢復(fù)機(jī)制，以應(yīng)對(duì) Leader 崩潰或網(wǎng)絡(luò)分區(qū)等異常情況。這使得 ZooKeeper 可以作為高性能、高可用性的分布式協(xié)調(diào)服務(wù)在實(shí)際應(yīng)用中被廣泛使用。

參考文獻(xiàn)：
文章名：一文徹底搞懂ZAB算法，看這篇就夠了！??！
文章名：Zookeeper核心知識(shí)及分布式一致性算法

21點(diǎn)19分 2023年12月15日
近期課程壓力變小，于是重新開始學(xué)習(xí)大數(shù)據(jù)開發(fā)框架知識(shí)
書寫學(xué)習(xí)文檔一方面是為了督促自己更好的學(xué)習(xí)，另一方面也是給自己的學(xué)習(xí)之路留下個(gè)痕跡。

身為初學(xué)者，難免有表述不準(zhǔn)確的地方，歡迎大家積極討論交流。
不積跬步 無以至千里！文章來源地址http://www.zghlxwxcb.cn/news/detail-763355.html

到了這里，關(guān)于分布式一致性算法Paxos、Raft 及 Zookeeper ZAB的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！