记录一些Raft的学习笔记

1.前言

1.1 一致性算法

一致性算法能够允许多台机器作为一个集群协同工作，并且在其中某几台机器故障时整个集群仍能正常工作。

一致性算法的工作就是保证每台服务器最终复制状态机的一致性，日志记录了状态机的命令，即也就是保证复制日志的一致性。只需要确保每台服务器中的日志最终包含相同顺序的命令，那么每台服务器上的状态机可以按日志顺序处理命令，达到了复制状态机的目的。形成了高可用的复制状态机。

一致性算法通常需要以下属性：

• 确保在非拜占庭条件下(包括网络延迟、数据包丢失、重复、乱序等)的安全性(不会返回不正确的结果)。
• 只要任何大多数(超过半数)服务器可以正常运行，一致性算法就可用。
• 不依赖于时序来确保日志的一致性：时钟错误或延迟会导致可用性。意思是不需要现实中的时间，如Raft是通过递增的任期数来作为逻辑时间。
• 通常情况下，只要集群的大部分(过半)已经响应的RPC，命令就能完成；少数较慢的服务器不会影响整个系统性能。

1.2 Paxos

Paxos存在以下两个问题：

• 非常难以理解。《The Part-time Parliament》⽐较晦涩难懂，但是《Paxos Made Simple》就⽐较容易理解。
• 难以构建实际的系统。因为缺乏很多细节，实际会有很多难题，导致最终实现等系统和Paxos有很大的差异，相当于是另一个协议了。

1.3 Raft设计目标

• 可理解性
• 提供一个完整的实际系统实现基础
• 在任何情况下都是安全的并且在典型的应⽤条件下是可⽤的
• 在正常情况下是⾼效的

2.Raft

raft将一致性问题分为了三个相对独立的问题：

• leader选举: 当前leader宕机时，会有新的leader选举产生
• 日志复制: leader必须从客户端接收日志条目然后复制到其他服务器节点，并且强制要求其他节点的日志与leader保持一致
• 安全性: 如果有任何的服务器节点已经应⽤了⼀个特定的⽇志条⽬到它的状态机中，那么其他服务器节点不能在同⼀个⽇志索引位置应⽤⼀条不同的指令

2.1 Leader选举

选举时机：followers在一定时间内没有收到AppendEntries的RPC或者发起投票的RPC，即超时就会转为candidate进行选举

选举时做什么
candidate：

• 增加当前轮次 term
• 给自己投票
• 重置选举定时器
• 给所有服务器发送 RequestVote RPC

follower: 按照先来后到只给一个candidate投票(安全性里还会有限制补充)

candidate会出现三种情况

• 获得了过半的投票，赢得选举成为leader，之后发送心跳信息防止新的选举。
• 收到另一个自称是leader的消息，若它的任期号不小于本candidate任期号，则承认该leader变成follower；反之拒绝这个RPC，继续保持candidate。
• 选票被分流，选举既没有赢也没有输，超时后增加任期号开始新一轮的选举，超时时间在一个区域内随机选择，避免无限重复。

2.2 日志复制

日志匹配特性

• 如果不同⽇志中的两个条⽬拥有相同的索引和任期号，那么他们存储了相同的指令。
• 如果不同⽇志中的两个条⽬拥有相同的索引和任期号，那么他们之前的所有⽇志条⽬也都相同。

复制规则

leader会强制follower的日志跟自己的保持一致，follower中跟leader冲突的日志会被leader的日志覆盖。

leader会找到与follower达成一致的最大日志条目索引，删除follower中那个点之后的所有日志，并将leader中那个点之后的所有日志条目发送给follower。

leader针对每个follower维护一个nextIndex，表示要发送的下一个日志条目索引，leader发送nextIndex失败时会减小nextIndex继续发送，直到日志达成一致的位置。

2.3 安全性

选举限制
candidate发送RequestVote RPC中包含了自己的日志信息，如果投票者的日志比这个candidate的日志还新，就会拒绝该投票请求。
Raft 通过⽐较两份⽇志中最后⼀条⽇志条⽬的索引值和任期号来定义谁的⽇志⽐较新。如果两份⽇志最后条⽬的任期号不同，那么任期号⼤的⽇志更新。如果两份⽇志最后条⽬的任期号相同，那么⽇志较⻓的那个更新。

2.4 定时

⼴播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

3 集群成员变更

4 日志压缩

当日志达到一定大小时，使用快照技术压缩日志

参考文献

[1]Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 USENIX Annual Technical Conference (Usenix ATC 14). 2014: 305-319.