特点

• 互斥性：在同一时刻，只有一个客户端能持有锁

• 安全性：避免死锁，如果某个客户端获得锁之后处理时间超过最大约定时间，或者持锁期间发生了故障导致无法主动释放锁，其持有的锁也能够被其他机制正确释放，并保证后续其它客户端也能加锁，整个处理流程继续正常执行

Raft是一种为简化分布式系统共识而设计的算法，其核心思想是将复杂问题分解为领导选举、日志复制和安全性三个关键部分。以下是对Raft的详细介绍：

1. 核心概念

• 节点角色：
  • 领导者（Leader）：处理客户端请求，管理日志复制。
  • 跟随者（Follower）：被动响应领导者和候选者的请求。
  • 候选者（Candidate）：在选举期间临时角色，发起投票请求。
• 任期（Term）：
  • 全局递增的编号，唯一标识领导者的任期。
  • 用于检测过时的请求（如旧领导者的消息）。

2. 领导选举

• 触发条件：跟随者超时未收到心跳（选举超时，通常随机化为150-300ms），转为候选者。
• 选举过程：
  1. 候选者自增任期，向所有节点发送RequestVote请求。
  2. 节点仅对首个符合条件的请求投票（同一任期内一票一投，且候选者日志足够新）。
  3. 候选者获多数票即成为新领导者，立即发送心跳确立权威。
• 安全性：通过日志完整性检查（选举限制）避免选出过时的领导者。

3. 日志复制

• 流程：
  1. 客户端请求由领导者转化为日志条目。
  2. 并行复制到所有跟随者。
  3. 当多数节点确认后，领导者提交条目并应用到状态机。
  4. 通知跟随者提交日志。
• 一致性保证：
  • 每个日志条目包含任期号和索引。
  • 日志匹配特性：若两节点日志中某索引的条目任期相同，则之前的所有条目均一致。
  • 领导者处理不一致时，通过强制覆盖跟随者的日志确保最终一致。

4. 安全性机制

• 提交规则：领导者只能提交当前任期的日志（间接提交旧任期的条目）。
• 崩溃恢复：
  • 节点重启后根据持久化的日志恢复状态。
  • 新领导者通过日志比对修复不一致的跟随者日志。
• 网络分区处理：高任期的新领导者优先，旧领导者因低任期自动降级。

5. 优化与扩展

• 日志压缩与快照：
  • 定期生成快照以压缩日志，减少存储和传输开销。
  • 跟随者落后时，领导者直接发送快照加速同步。
• 线性一致性：通过领导者序列化所有写请求，确保操作顺序一致性。

6. Raft vs. Paxos

• 易用性：Raft通过强领导者和连续日志简化实现；Paxos灵活但复杂。
• 日志结构：Raft日志无空洞，Paxos允许空洞但最终填补。
• 领导权：Raft仅一个活跃领导者，Paxos允许多提议者共存。

7. 实现要点

• 持久化状态：保存当前任期、投票记录和日志，防止重启后状态丢失。
• 定时器管理：合理设置心跳间隔与随机化选举超时，避免活锁。
• 测试验证：模拟网络分区、节点宕机等故障，确保算法正确性。

8. 应用场景

适用于需强一致性的分布式系统，如分布式数据库（etcd、CockroachDB）、协调服务（Consul）等。

可理解的共识算法研究

(In Search of an Understandable Consensus Algorithm–Extended Version)

作者:Diego Ongaro and John Ousterhout–Stanford University

摘要

Raft是管理复制日志的共识算法, 比Paxos牛.

1. 介绍

复制状态机,如图1

共识算法管理

2. Raft把共识算法分解为3个独立的子问题：

2.1 Leader选举

当前Leader挂掉后必须进入一个新Leader的选举