Raft分布式一致性算法(论文解读和源码实现)
前言
建议先对raft论文有一些基本的浏览，然后再看下面的内容。可以结合后面引用的链接去进行更深入的学习。下文提到的章节，指论文的章节
正文
通过领导人的方式，Raft 将一致性问题分解成了三个相对独立的子问题：
- 领导选举：一个新的领导人需要被选举出来，当现存的领导人宕机的时候会重新选出一个新的领导（章节 5.2）
- 日志复制：领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同。
- 安全性：在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。章节 5.4 阐述了 Raft 算法是如何保证这个特性的；这个解决方案涉及到一个额外的选举机制（5.2 节）上的限制。
除此以外，还有：
-
日志压缩
-
成员关系变化
-
与客户端交互
图3
领导选举
重点阅读论文的 5.1 以及 5.2，结合 Figure 2 食用。
image.png
只需要两个rpc和两个周期性检查的timer（heartbeat timer和election timer）即可描述领导选举：
-
requestVote
-
appendEntity（作为心跳包）
-
election timer作为选举超时（随机超时时间150ms~300ms），使得follwer转变为candidate以及candidate处于分票状态时的重新选举。
-
heartbeat timer作为心跳超时（定时，50ms），使用appendEntity重置各follower的election timer。（日志复制那里还要维护nextIndex，matchIndex和commitIndex）
对于每一个不同状态的 Raft 节点，他们可能有如下并发的事件：（即复制状态机的行为）
-
Follower
- 处理
AppendEntries（重置electionTimer，维护3个index，同步日志） - 处理
RequestVote（是否给发送请求的candidate投票，需要candidate数据是up to date且获得绝大多数节点的投票才能称为leader） -
electionTimer超时（follower转变为candidate）
- 处理
-
Candidate
- 处理
AppendEntries（判断term是否转变为follower） - 处理
RequestVote（根据term是否需要转变为follower，判断是否成为leader） -
electionTimer超时（分票后的重新选举） - 发起投票
sendRequestVote（给集群其他节点发送requestVote，请求投票）
- 处理
-
Leader
- 处理
AppendEntries（判断term是否转变为follower，维护各follower的nextIndex和matchIndex，维护leader的commitIndex） - 处理
RequestVote（判断term是否转变为follower） -
heartbeatTimer超时(给各节点发送appendEntity) - 停掉
electionTimer计时器 - 发送心跳包
sendAppendEntries（根据leader的nextIndex数组打包请求参数，发送appendEntries）
- 处理
日志复制
image.png
image.png
图示：
-
黑点：表示matchIndex
-
箭头：表示nextIndex
-
虚线（虚线围起来的，紫色底的2。表示日志项）：表示该日志还没提交。
-
实线（实线围起来的）：日志已提交
步骤：
当前leader通过心跳（appendEntities）维护不同节点的nextIndex和matchIndex。
follower节点接收到appendEntity请求时，对比自己的和leader发过来的term和nextIndex。如果自己的小，就返回false，让leader降低nextIndex。直到leader发过来的日志就是自己缺失的那部分，直接删掉follower节点的matchIndex之后的数据，添加leader发过来的自己缺失的数据。
leader节点接受到appendEntity的返回后：
如果是成功的返回：维护该follower的matchIndex和nextIndex，查看当前是否绝大多数follower节点已复制（通过查看leader维护的matchIndex数组来判断），如果大多数已复制，即表示该日志项已提交，下一次心跳的AppendEntity会使得各follower的commitIndex也得到更新，即各follower节点的该日志项也处于已提交状态。；
如果是失败的返回，降低对应follower的nextIndex，然后直接对该follower重新发送appendEntity
image.png
image.png
image.png
image.png
此时该复制状态机的状态就保持了一致（获得共识）。
安全性
详见论文第五节
描述了 Raft 算法是如何选举和复制日志的。然而，到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。
-
选举限制
Raft 使用投票的方式来阻止一个候选人赢得选举除非这个候选人包含了所有已经提交的日志条目。候选人为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果候选人的日志至少和大多数的服务器节点一样新（up to date，Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新），那么他一定持有了所有已经提交的日志条目。
-
提交之前任期内的日志条目
Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有领导人当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。
成员关系变化
详见论文第6小节。
image.png
两阶段变更的方式：
第一阶段：共同一致（过渡阶段）
-
领导者收到从旧配置到新配置的变更请求时，创建共同一致的日志并复制给其他节点
-
follower以最新的配置做决定，领导者需要以已经提交的配置来做决定
-
新旧配置中所有机器都可能成为领导者
-
达成一致要在新旧配置上均获得大多数支持
第二阶段：切换到新配置
- 提交新配置的日志到所有节点，一旦新配置的日志被提交，即完成变更
日志压缩
详见论文第7小节
在实际的系统中，Raft 产生的日志在持续的正常操作中不断增长，但不可以无限的增长下去。
快照（snapshot）是最简单的压缩方式。在快照中，全部的当前系统状态都被写入到快照中，存储到持久化的存储中，然后在那个时刻之前的全部日志都可以被丢弃。
Raft快照基本思想：
-
每个服务器独立创建快照，只包括已经被提交的日志
-
快照值存储了当前的状态、最后的索引位置和任期号
-
快照完成后，删除最后索引位置之前的所有日志和快照
-
领导人必须偶尔的发送快照给一些落后的follower
异常情况分析
image.png
上图的任意一步，任意一个节点都可以宕机。也可以保证数据一致性。。
follower或者candidate节点崩溃
-
如果不是一半节点崩溃，服务还是可用，leader还是可以通过appendEntity给正常follower节点复制数据，确认接收后，leader保证该日志项是提交状态，向客户端返回操作成功，等到心跳（appendEntity）使得follower对于该日志项也提交成功；
-
如果超过一半节点崩溃，服务不可用，等待节点重启，通过appendEntity扫描节点需要同步的数据（维护nextIndex，matchIndex），使用leader的数据覆盖当前follower数据，即该节点已同步完成数据，等待多数节点恢复，服务即可用。
客户端请求的数据到达leader前，leader崩溃
等待集群重新选举。且客户端重新请求。
客户端数据已到达leader，但未复制到绝大多数follower（即处于uncommited），leader崩溃
uncommited数据无意义。等待集群重新选举。且客户端重新请求。
客户端数据已到达leader，已复制到绝大多数follower（处于commited），leader崩溃
等待集群重新选举。且客户端重新请求。但是该不应该继续保存在复制状态机上。（不然就造成重复提交）。因此需要raft服务能内部去重（具备幂等性，实现线性化语义），论文上是第八节（client interaction）中提到一个解决方案就是：
客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。
网络分区，导致双leader
客户端向那个不具备绝大多数节点的leader请求，肯定是超时的。
客户端只有向具备绝大多数节点的leader请求才能正常返回。
多说一下，分区后的数据恢复：
不正常的leader网络恢复，接收到正常leader的appendEntity后降级为follower，进行日志复制过程。
代码实现raft
自己实现过一个简单的raft，包含领导选举，日志复制和安全性，未实现日志压缩，成员关系变化。
思路：
一个节点使用了一个go routine模拟一个状态机，两个timer，两个rpc（使用go的net/rpc内置包）。
但是发现测试特别困难。仅仅根据论文描述写了代码，也简单的打印测试，基本是可用的，可以选举出来leader，同步数据，但是异常边界情况很难模拟出来然后测试。
代码如下，实现不完整：
https://github.com/theoneLee/go-raft-demo
todo
后面发现raft.github.io上有一个mit分布式系统的课程，里面包含了raft的一个实现，且附带完善的测试用例，准备好好看课程,然后实现这块内容。
参考
- 论文
https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
- 可视化raft
http://thesecretlivesofdata.com/raft/
- mit 6.824
http://nil.csail.mit.edu/6.824/2020/index.html
- 《云原生分布式存储基石 etcd深入解析》第一章
