分佈式算法最全詳解 -4 大主流算法圖解-

大家好，我是 mikechen。

分佈式算法對於保證分佈式一致性非常的重要，也是構建分佈式的基石，下面我就重點詳解 4 大主流分佈式算法 @mikechen

Paxos 算法

Paxos 算法是一種用於分佈式一致性的協議，主要解決：分佈式系統中的一致性問題，確保多個節點對共享狀態達成一致。

在 Paxos 算法中，有三種角色，分別是：提議者（proposer）、接收者（acceptor）和學習者（learner）。

如下圖所示：

Paxos 算法：是基於議員們如何就提案達成一致的一個隱喻而命名，提議者負責提出提案，接收者負責接受、或拒絕提案。

Paxos 算法主要分爲三個階段：

  1. 準備階段（Prepare Phase）：提議者向大多數接收者發送一個編號爲 n 的準備請求，要求接收者回復已經接受過的最大編號的提案；

  2. 提案階段（Proposal Phase）：如果提議者收到了大多數接收者的回覆，表示接收者已經接受了編號小於 n 的提案，那麼提議者就可以向接收者發送一個編號爲 n 的提案；

  3. 學習階段（Learn Phase）：如果一個提案被大多數接收者接受，那麼學習者就可以學習到這個提案。

應用場景：

Paxos 算法通常用於：實現分佈式數據庫、分佈式鎖、一致性哈希等需要強一致性的分佈式系統中。

Raft 算法

Raft 算法是一種用於分佈式一致性的算法，Raft 算法可以簡要理解爲 Paxos 算法的精簡版。

因爲 Paxos 算法過於難以理解，而 Raft 算法做了精簡，主要涉及到 3 大角色：

分別是：領導者（Leader）、跟隨者（Follower）、和候選人（Candidate）。

1、領導者（Leader）

領導者是 Raft 算法中的核心角色，負責：處理客戶端的請求，並通過日誌複製機制，確保所有的跟隨者都複製了領導者的日誌條目。

領導者定期發送心跳消息給其他節點，以保持自己的領導地位。

2、跟隨者（Follower）

跟隨者是 Raft 算法中的普通節點，它們接受：來自領導者的指令，並複製領導者的日誌。

在正常情況下，大多數節點都是跟隨者，它們不處理客戶端請求，只負責接收、和複製領導者的日誌。

3、候選人（Candidate）

候選人是在選舉過程中的節點狀態，當一個節點處於候選人狀態時，它向其他節點發送選舉請求，試圖成爲新的領導者。

在 Raft 算法中，選舉過程是通過投票機制實現的，候選人需要獲得大多數節點的支持才能成爲新的領導者。

如果候選人在一定時間內沒有獲得足夠的選票，那麼它將重新進入跟隨者狀態。

Raft 算法的基本思想是：

通過定期的選舉過程來選出一個領導者，領導者負責處理客戶端請求，並確保日誌的一致性；

在領導者的領導下，所有的跟隨者，都複製領導者的日誌，並且只有領導者有權向日志中添加新的條目。

應用場景

Raft 算法，適用於各種需要一致性複製的分佈式系統，包括：分佈式數據庫、分佈式文件系統...... 等。

ZAB 算法

ZAB 算法，全程是 ZooKeeper Atomic Broadcast，該算法是 Apache ZooKeeper 用於實現一致性的協議。

ZAB 算法：是一種基於原子廣播的算法，用於確保分佈式系統中的多個節點之間的一致性。

大致流程如下：

應用場景

ZAB 算法通常用於構建分佈式協調服務，例如：Apache ZooKeeper。

Gossip 算法

Gossip 算法是一種分佈式通信算法，用於實現分佈式系統中的信息傳播、和狀態同步。

原理：

Gossip 算法的核心是：隨機通信、和信息傳遞，每個節點都定期與其他節點進行通信，並將自己的信息傳播給其他節點。

當一個節點收到其他節點的信息時，它會更新自己的狀態並將信息，傳播給其他節點，從而實現狀態的同步和信息的傳播。

這就類似在病毒傳播中，病毒通過感染一個人然後傳播給另一個人，逐步擴散。

類似地，Gossip 算法中的節點通過、與鄰居節點進行通信，將自己的信息傳播給其他節點，逐步擴散。

應用場景：

Gossip 算法適用於構建分佈式存儲系統、分佈式計算系統..... 等，需要信息傳播和狀態同步的場景。

這些算法在分佈式系統中都發揮着重要作用，可以根據具體的需求、和場景選擇合適的算法，來實現分佈式一致性。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/986dumOR90RRJ4kkCLx0kg

猜你喜歡