当前位置：首页 > news >正文

分布式系统中的Paxos协议

news 2025/5/15 6:24:14

设计一个分布式系统必定会遇到一个问题—— 因为分区容忍性（partition tolerance）的存在，就必定要求我们需要在系统可用性（availability）和数据一致性（consistency）中做出权衡 。这就是著名的 CAP 定理。它告诉我们，分布式系统中有三项关键属性，但你不可能同时满足所有三个：

一致性（Consistency）：所有节点上的数据都是一致的，比如每个人看到的文档都是最新的。
可用性（Availability）：系统能响应所有请求，即使有些节点出问题也能继续运行。
分区容忍性（Partition Tolerance）：即使节点之间的网络通信出现了问题，系统还能继续工作。

CAP 定理的意思是，你必须在这三者之间做取舍。例如，分区容忍性对于分布式系统非常重要，因为网络问题在分布式环境中经常发生。如果你想要保证系统的分区容忍性和可用性，那一致性就可能受到影响，反之亦然。

举个例子，如果你在不同城市的朋友们一起玩在线游戏，游戏可能因为网络分区导致有的人操作延迟。但游戏公司通常会优先保证可用性（即游戏继续运行），而不总是优先考虑一致性（比如大家瞬间同步）。这就是 CAP 定理的应用。

1. 数据一致性问题与Paxos的背景

在分布式系统中，多个节点需要协作完成一致的操作（例如更新数据库、选举主节点）。但由于网络延迟、节点故障等问题，如何让所有节点对某个值（例如一条操作指令）达成一致，是一个复杂的挑战，称为共识问题。
Paxos协议由Leslie Lamport于1990年提出，是首个被严格证明正确性的分布式共识算法，成为解决此类问题的经典方案。

2. Paxos的核心目标

安全性（Safety） ：所有节点最终达成相同的值，且该值必须由某个节点提出。
活性（Liveness） ：只要多数节点存活且通信正常，算法最终能达成一致。
容错性：允许系统中最多半数节点故障（包括崩溃、网络分区等）。

3. 核心概念与角色

Paxos协议中有三类角色：

Proposer（提议者） ：提出提案（Proposal），包含唯一编号和提议的值。
Acceptor（接受者） ：投票决定是否接受某个提案。
Learner（学习者） ：学习已达成一致的提案值。

关键概念：

提案编号（Proposal Number） ：全局唯一且递增的编号，用于区分提案优先级。
多数派（Quorum） ：超过半数的Acceptor集合，用于确保决策的唯一性。

4. Basic Paxos算法流程

Paxos通过两阶段协议（Prepare & Accept）确保一致性：

阶段一：Prepare（准备阶段）

Proposer发送Prepare请求：
- 生成一个全局唯一的提案编号 n，向所有Acceptor发送 Prepare(n)。
Acceptor响应Promise：
- 若收到的 n 大于已回复过的所有Prepare请求的编号，则回复 Promise(n, accepted_n, accepted_v)，其中 accepted_n 和 accepted_v 是该Acceptor已接受的最高编号提案的值。
- 否则拒绝请求。

阶段二：Accept（接受阶段）

Proposer发送Accept请求：
- 若收到多数派Acceptor的Promise回复：
  - 选择所有回复中最高编号对应的值 v（若存在），否则使用自己的提案值。
  - 向所有Acceptor发送 Accept(n, v)。
Acceptor接受提案：
- 若收到的 n 大于等于已承诺的Prepare编号，则接受该提案，回复 Accepted(n, v)。
- 否则拒绝。
Learner学习结果：
- 一旦某提案被多数派Acceptor接受，Learner将值 v 作为最终结果。