Skip to content

分布式算法

分布式算法，全称应该是 分布式一致性算法，是为了保障分布式环境下数据的一致性的算法。主流的分布式算法有：

  1. Paxos
  2. Raft
  3. ZAB(ZooKeeper Atomic Broadcast)

Paxos 算法

Paxos 算法由 Leslie Lamport 在 1998 年提出，是一个基于消息传递的一致性算法。 该算法的目的是为了 协调某个数据值并达成一致性，典型的少数服从多数的思想。

Paxos 概念

提案 Proposal

Paxos 算法中的提案是一个由提议者提出的数据值，提案由 「提案号 (Proposal ID)」 和 「提案内容 (Value)」 组成，Proposal ID 主要用于实现 Paxos 算法，Value 可以是任意的数据，比如一个请求、一个命令等。

角色

  1. Proposer：提议者，负责提出提案。
  2. Acceptor：接受者，负责接受提案。
  3. Learner：学习者，负责学习已经被接受的提案。

Proposer 提议者

提议者 Proposer 负责提出提案(Proposal)。提案内容 Value 可以是任何行为或者操作，反正在 Paxos 中都抽象为 Value。

提议者可以有多个，不同提议者可以提出不同甚至互斥的提案内容(Value)，但对于同一轮 Paxose 而言，只能有一个提案内容被批准。

Acceptor 接受者

接受者负责接受提案，可以有多个，但对于同一轮 Paxose 而言，只能批准一个提案。 接受者 Acceptor 从含义上来说是除了当前提议者 Proposer 之外的其他节点。接受者之间完全平等和独立。 提议者 Proposer 需要争取超过半数 (N/2 + 1) 的接受者 Acceptor 的支持，才能使得提案被批准，它提倡的 Value 才能被所有机器(Proposer, Acceptor, Learner)接受。

接受者有两个状态：

  1. Promise：接受者接受提案者的提案，但不批准，只是保证不再接受小于提案号的提案。
  2. Accepted：接受者接受提案者的提案，并批准。

Learner 学习者

学习者不参与选举，只负责学习已经被批准的提案。学习者可以有多个，但对于同一轮 Paxose 而言，只能有一个提案内容被学习。 在 Paxos 中，学习者主要参与相关的状态机同步流程。 Learner 的流程参考了 Quorum 议会机制，某个提案内容 Value 需要获得超过半数接受者 Acceptors 的批准，才能真正被 Learner 学习到。

阶段

Paxos 算法分为两个阶段：

  1. 准备阶段 (Prepare Phase): Proposal 向所有 Acceptor 节点发起 Prepare 请求，并携带全局唯一且递增的 Proposal ID， 要求 Acceptor 返回自己已经接受的最高提案号。如果 Acceptor 接受了更小的提案号，那么 Acceptor 将拒绝当前轮次的提案，并更新自己的状态。

  2. 承诺阶段 (Promise Phase): Acceotpr 接受到 Prepare 请求后，会检查该请求的提案号 Proposal ID 是否大于自己已经接受的最高提案号， 如果是，那么 Acceptor 更新自己的状态，承诺不在接受小于该提案号的提案，并返回自己已经接受的最高提案号和提案内容给 Proposer。