分布式一致性算法01 Paxos算法
一、基本概念
Paxos是分布式一致性的经典算法，由Leslie Lamport在1990年提出。
二、Paxos算法通常涉及三种角色：
Proposer（提议者） ：负责提出提议（Proposal），即向系统中提出一个值。Proposer通常是客户端，负责发起提议并分配一个不重复的自增ID给每个提议。
Acceptor（接受者） ：参与决策过程，负责接收并回应Proposer的提议。每个Acceptor只能接受一个值，并且为了保证最多只有一个值被选定（Chosen），Proposal必须被超过一半的Acceptors所接受。
Learner（学习者） ：负责学习最终被选定的值。Learner不参与协商过程，只是接收并记录最终被选定的值。
在实际过程中，一个节点可以同时承担1~3个角色。
三、Paxos算法的基本过程
1、准备阶段（Prepare Phase）：
提议者（Proposer）选择一个提议编号（ballot number），并将其发送给所有接受者（Acceptor）。
接受者在接收到提议者的准备请求后，如果当前编号大于其已承诺的最高编号，则更新其承诺编号，并返回一个承诺（promise）给提议者，承诺中包含当前已接受的最高编号和值。
2、提议阶段（Proposal Phase）：
提议者收集到多数接受者的承诺后，选择一个值（value），并结合最新的提议编号，生成提议（propose）消息发送给接受者。
接受者在接收到提议消息后，如果提议编号大于其已有的承诺编号，则接受该提议，并返回确认消息给提议者。
3、决定阶段（Decide Phase）：
提议者收集到多数接受者的确认消息后，可以决定该值为最终值，并将其写入日志或状态机中。
学习者（Learner）从提议者处获取并学习最终决定的值，确保所有节点都有一致的状态。
四、举例说明：
假设我们有一个分布式系统，包含10个节点：P1、P2是提议者，A1、A2、A3、A4、A5是接受者，L1、L2、L3是学习者。
1、准备阶段：
P1提出一个提议编号，编号为1。
P1向所有接受者A1~A5发送询问，询问P1将发起编号为1提议是否可以。
A1收到提议时，并没有反馈过任何一次提议，于是反馈可以接受，并承诺，后续不会接受编号比1小的提议。A2~A4类似。
几乎同时，P2提出一个提议，编号为5。
P2向所有接受者A1~A5发送询问，询问P2将发起编号为5提议是否可以。
A1收到提议时，承诺的最小编号为1，于是反馈可以接受，并承诺，后续不会接受编号比5小的提议。A2~A4类似。
到这里，P1和P2的提议，前后都被允许提交了。当然，也有情况可能是，部分节点先收到了P2，这种情况下，P1的提议编号就无效了，需要重新拟定编号，这个编号必须单调增加。
2、提议阶段
P1收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为1的提议值为V1。
接受者收到提交消息时，已经无法接收比5小的提议，于是就拒绝P1，提议不通过。
P2收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为5的提议值为V5。
接受者收到提交消息时，反馈P2同意了5号提议。
3、决定阶段
当提议5收到过半同意反馈时（5个节点中3个以上同意），认为提议通过，各节点并将V5写入日志。
此时，学习者L1、L2、L3也会学习到V5的结果，并写入日志。
五、Paxos算法的特点
多数同意：在Paxos算法中，只有当提议者收到超过半数接受者的同意时，提议才可能被提交。
唯一性：Paxos算法保证了在任何给定的一轮中，只有一个提议可以被接受。
容错性：即使在一些节点失败的情况下，Paxos算法也能够工作。
Paxos算法的实现和理解都相当复杂，但它是许多现代分布式系统一致性协议的基础，如Raft算法等。