Paxos与Raft

Paxos

解决了一致性问题。

在一个分布式系统中，每个 proposer都可以提出一个 value，consensus 算法就是用来从这些 values 里选定一个最终 value。如果没有 value 被提出来，那么就没有 value 被选中；如果有1个 value 被选中，那么所有的 process 都应该被通知到。

Paxos 例子说明

• 无人竞争，超过半数即可通过提案
• 先后竞争，先到先得，回复当前选择；同时竞争，先到先得，视后到者身份不同，可能有回复，可能无回复

Raft

Raft 是一种为了管理复制日志的一致性算法。

一致性
一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。

管理日志
一致性算法是从复制状态机的背景下提出的，复制状态机通常都是基于复制日志实现的，这个日志可以理解为一个指令。

领导人选举

Raft 通过选举一个领导人，然后给予他全部的管理复制日志的责任来实现一致性。

每个 server 都可能会在 3 个身份之间切换：领导者、候选者、跟随者

所有服务器初始化的时候，都是 跟随者，这个时候需要一个 领导者，所有人都变成 候选者，直到有人成功当选 领导者。

领导者也有宕机的时候，宕机后引发新的 选举，所以，整个集群在选举和正常运行之间切换

每一个 server 最多在一个任期内投出一张选票（有任期号约束），先到先得。

一旦成功，立即成为领导人，然后广播所有服务器停止投票阻止新得领导产生。

日志复制

客户端发送日志给领导者，随后领导者将日志复制到其他的服务器。如果跟随者故障，领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。

步骤

1. 客户端提交
2. 复制数据到所有跟随者
3. 跟随者回复 确认收到
4. 领导者回复客户端和所有跟随者 确认提交。