1 简介

Raft 协议架构 是一种基于领导者的共识算法，旨在实现可理解性。它将共识分为领导者选举、日志复制和安全保证。

他试图回答一个问题：两台不同的服务器如何运行同一个程序，并且在某个时间点，它们在被查询时都会返回相同的数据，即使它们收到了不同的指令。

例如，假设服务器 A 在某个时间点收到值为 1 的写入操作和值为 2 的后续写入指令。在这种情况下，我们应该查询服务器 B 以检索值 2，而服务器 B 上没有发生写入操作。

这是分布式系统中的一个经典问题，并且已在 etcd、Kubernetes、Kafka、CockroachDB 等使用的 KV 存储等系统中使用了 Consul（Vault 使用的 KV 存储）。

2 Raft基础知识

• 基于领导者：

选择一个服务器作为领导者
它接受客户端请求，管理复制
如果当前领导者失败，请选择新的领导者

• 服务器状态：

领导 Leader
追随者：完全被动 Follow
候选人：用于选举新领导人

• 时间分为术语：

项具有单调递增的数字
每个任期都以选举开始
一名或多名试图成为领导者的候选人
获胜的候选人（如果有）将担任其余部分的领导者 术语
条款允许检测过时的信息
每个服务器存储当前术语
检查每个请求
术语数单调增加
不同的服务器以不同的方式观察术语转换
服务器之间的请求-响应协议（远程过程调用、 或 RPC）。

• 2 种请求类型：

请求投票
AppendEntries （也用作检测信号）
领导人选举
追随者期望周期性心跳。如果在随机选举超时内没有心跳到达，则关注者将成为候选人，增加其任期，为自己投票，并请求其他人投票。当候选人获得多数选票时，候选人获胜。

逐步检查

1) Followers start and wait for heartbeat
2) Follower times out → candidate, starts election
3) Candidate sends RequestVote(term, lastLogIndex, lastLogTerm)
4) If majority votes → becomes leader and sends heartbeats

1 所有服务器都以关注者身份开始

没有检测信号 （AppendEntries）？

2 开始选举：

递增当前期限
为自己投票
向所有其他服务器发送 RequestVote 请求

3 选举结果：

获得大多数集群的选票：成为领导者， 开始发送检测信号以防止其他选举
在新术语中从其他服务器接收 Append

Enttries： 恢复为跟随者
超时：开始新的选举
每个服务器在给定的任期内最多投票给一名候选人

选举安全：在给定的任期内，只能有一个服务器被选为领导者
可用性：随机选举超时减少了分裂投票

3 日志复制

领导者处理客户端命令，将它们附加到其日志中，并将 AppendEntries RPC 发送给关注者。当多数人保留该条目时，领导者将其标记为已提交并将其应用于其状态机。

    AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit):
      if term < currentTerm: reply false
      if log doesn't contain an entry at prevLogIndex whose term matches prevLogTerm: reply false
      else: delete conflicting entries; append new entries; if leaderCommit > commitIndex: commitIndex = min(leaderCommit, index of last new entry)
      reply true

由领导者处理

当客户端请求到达时：
追加到本地日志
使用 AppendEntries 请求复制到其他服务器
已提交：领导者将条目复制到大多数服务器
提交后，应用于本地状态机

将结果返回给客户端

• 日志条目处理：索引、术语、命令

领导者崩溃后，日志可能会变得不一致
Raft 在日志之间保持高度的一致性（日志匹配属性）：

如果不同日志中的条目具有相同的术语和索引，则他们也有相同的命令

两个日志在该条目之前是相同的
AppendEntries 一致性检查保留上述属性。
Leader 强制其他日志匹配自己的日志：

如果跟随者收到冲突的条目，传递一致性检查 ，删除所有冲突的条目

4 安全与保证

Raft 确保：

选举限制 — 只有具有最新日志的候选人才能当选。
日志匹配 — 如果两个日志具有具有相同索引和术语的条目，则它们在该索引之前是相同的。
领导者完整性 — 承诺的条目会保留在未来的领导者中。
高级：联合共识和成员变更

安全

必须确保新任期的领导者始终拥有所有 在先前术语中提交的日志条目（领导者完整性属性）。

第 1 步：限制选举：除非 候选人的日志至少与您的日志一样最新。
比较上次日志条目的索引和术语。

第 2 步：非常小心何时将条目视为已提交
一旦在多数上复制？不安全的！

5 小结

• 当领导者Leader服务失败时会发生什么？

追随者在听不到心跳时开始选举;新领导人由多数票选出。

• Raft 如何防止脑裂？

随机选举暂停和多数投票确保每个任期只能选出一名领导人。

• 什么时候应该使用 InstallSnapshot？

当日志被压缩并且一个跟随者落后太远时，领导者会发送一个 InstallSnapshot RPC。

参考

	https://web.stanford.edu/~ouster/cgi-bin/cs190-winter20/lecture.php?topic=raft