Paxos算法
#分布式 2023-09-12

简介

Paxos 算法是 Leslie Lamport 在 1990 年提出的一种分布式系统共识算法，也是第一个被证明完备的分布式系统共识算法（前提是不存在拜占庭将军问题，也即无恶意节点）。Paxos 算法主要包括 2 个部分：

  • Basic Paxos 算法：多节点之间如何就某个值（提案 value）达成共识；
  • Multi-Paxos 思想：执行多个 Basic Paxos 实例，就一系列值达成共识。

Basic Paxos Algorithm

Basic Paxos 中存在 3 个重要的角色：

  1. Proposer（提议者）：也可称作 Coordinator（协调者）。负责接收 client 端的请求并发起提案。提案信息通常包括提案编号（Proposal ID）和提议的值（Value）。
  2. Acceptor（接受者）：也可称作 Voter（投票员）。负责对 Proposer 的提案进行投票，同时需要记住自己的投票历史。
  3. Learner（学习者）：如果有超过半数的 Acceptor 对某个提议达成了共识，那么 Learner 就需要接受这个提议，并就该提议做运算，然后将运算结果返回 client。

为了减少实现该算法所需的节点数，一个节点可以身兼多个角色。并且，一个提案被选定需要被半数以上的 Acceptor 接受。这样的话，Basic Paxos 算法还具备容错性，在少于一半的节点出现故障时，集群仍能正常工作。

Multi-Paxos thought

Basic Paxos 算法的仅能就单个值达成共识，为了能够对一系列的值达成共识，我们需要用到 Multi-Paxos 思想。

Multi-Paxos 只是一种思想，这种思想的核心就是通过多个 Basic Paxos 实例就一系列值达成共识。也就是说，Basic Paxos 是 Multi-Paxos 思想的核心，Multi-Paxos 就是多执行几次 Basic Paxos。

参考资料