副本一致性算法

Paxos

角色

协议将系统中的节点分为三种角色：Proposer（提案者）、Acceptor（决议者）、Leaner（学习者），他们的具体职责为：

• 提案者：对key的值提出自己的值；
• 决议者：对提案者的提议进行投票，选定一个提案，形成最终决策；
• 学习者：学习决议者达成共识的决策。

决策

在 Paxos 中，一个决策过程（Round、Phase）分为两个阶段：

(1) phase1（准备阶段）：

Proposer向超过半数（n/2+1）Acceptor发起prepare消息(发送编号)； 如果Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该Acceptor 承诺不再接受任何编号小于 N 的提案。否则拒绝返回。

(2) phase2（决议阶段或投票阶段）：

如果超过半数 Acceptor 回复 promise，Proposer向Acceptor发送accept消息。注意此时的V：V 就是收到的响应中编号最大的提案的，如果响应中不包含任何提案，那么V 就由 Proposer 自己决定； Acceptor检查accept消息是否符合规则，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。

在实际发展中，Paxos算法也演变出一系列变种：

PBFT（实用拜占庭容错）算法：是一种共识算法，较高效地解决了拜占庭将军问题； Multi-Paxos算法：优化了prepare阶段的效率，同时允许多个Leader并发提议；以及FastPaxos、EPaxos等，这些演变是针对某些问题进行的优化，内核思想还是依托于Paxos。

Raft

Raft 之所以会出现，主要是因为 Paxos 晦涩难懂，大家表示很难看懂。

• Paxos 可以多点写入，无需选举 Leader，每个节点都可以接受写请求。虽然为了避免活锁问题，Multi Paxos 可以选举一个 Leader，但是也不是强制执行的，允许同一时间有多个 Leader 同时存在。多点写入，这增加了复杂度。
• Raft 只能单点写入
• 任意时刻只能有一个有效的 Leader，只能 Leader 接受写请求，Leader 同步给超过半数的 Follower

角色

在 Raft 中，节点被分为 Leader、Follower、Candidate 三种角色：

• Leader：处理与客户端的交互和与follower的日志复制等，一般只有一个Leader；
• Follower：被动学习Leader的日志同步，同时也会在leader超时后转变为Candidate参与竞选；
• Candidate：在竞选期间参与竞选；

日志结构

• index: 日志的顺序编号，如 1、2、3、4 …
• term: 写入日志的 Leader 所在的任期、轮数，其他地方称之为 epoch
• commitIndex: 这条日志被复制到了多数的机器上
• lastApplied: 哪些日志已经回放到了状态机

term 只会单调递增，日志的顺序满足: 后一条日志的 term >= 前一条日志的 term

term 作用

(1) 防止脑裂

网络分区恢复，存在两个 Leader，旧 Leader 向 Follower 发送数据，Follower 知道它的 term = 4，就知道它是过期的 Leader，于是拒绝执行写入，同时反馈给老的 Leader，你已经过期了。

(2) term 如何一直递增?

每个节点都保存了一个 term 的值，那么 term 比较小的节点是否会被选为 Leader ? 答案是不会。因为选举的时候，是要多数同意，意味着一定有一个节点保存了最新的 term 的值，而选举的时候，是选日志最新的节点作为 Leader。

ZAB

Replicated State Machine Vs. Primary-Backup System

• Replicated State Machine: 记录的是持久化的请求序列
• Primary-Backup System: 记录的是持久化的数据的状态变化

Paxos 和 Raft 用的是前者，ZAB 用的是后者。

三种算法对比

参考

• 从Paxos到Raft，分布式一致性算法解析