raft 算法学习笔记&个人理解
概述
Raft 论文对 raft 的描述：“raft是一种为了管理复制日志的一致性算法”；在我的理解中，分布式系统通常都会对数据进行复制备份来达到容错的目的（因为数据会复制到集群中的不同机器中，当某一台服务器宕机后，可以通过请求别的服务器来获取相同的数据），因此保持复制数据的一致性非常重要，而raft就是一种可以用来保持复制数据的一致性算法。
一致性模块 Consensus Module 执行的就是raft算法，它保证拷贝到所有 server 上的每一条日志是一致的。State Machine 状态机对应我们的业务逻辑，日志作为状态机的输入，输入一致就能保证输出是一致的。
raft基础
raft 集群中的节点有三种状态：Leader、Follower、Candidate；任何时刻，每个节点都处于三个状态之一，正常情况下，只有一个 Leader 和若干个 Follower 。
Leader
负责接收客户端的请求和发送追加日志（AppendEntries）请求给 follower，而且会周期性的发送心跳给 follower。
Follower
大部分时间接收 leader 发送的 AppendEntries 请求（心跳也属于 AppendEntries 请求），返回追加日志结果给 leader；或者是接收 candidate 的投票请求(RequestVote)，返回投票结果给 candidate。follower不会主动发送请求，只会被动接收leader或者candidate的请求并回复。
Candidate
follower 在一段选举超时时间内收不到任何信息则会变成 candidate，发起选举，向其他节点发送投票请求，若收到过半数节点的选票，则变成leader。
任期（term）
Raft 把时间分割成任意长度的任期（term），任意一个任期内，最多只有一个 leader （选票瓜分的情况会导致没有 leader ）。任期在 Raft 算法中充当逻辑时钟的作用，这使得服务器节点可以发现一些过期的信息比如过时的 leader 。
两种RPC
Raft 算法中服务器节点之间使用 RPC 进行通信，并且基本的一致性算法只需要两种类型的 RPC。请求投票（RequestVote） RPC 由 candidate 在选举期间发起，追加日志（AppendEntries）RPC 由 leader 发起，用来复制日志和提供一种心跳机制。
Leader选举
Raft使用一种心跳机制来触发Leader选举：leader周期性地向所有follower发送心跳（不包含日志条目的 AppendEntries 请求）来维持自己的地位。如果一个follower在一段选举超时时间内收不到任何消息，它就会假设系统没有可用的leader，然后开始进行选举以选出新的leader。
要开始一次选举过程，follower 先增加自己的当前任期号并且转换到 candidate 状态。然后投票给自己并且并行地向集群中的其他服务器节点发送投票请求（让其他服务器节点投票给它）。之后可能会发生三种情况：1）candidate获得过半数的选票，成为 leader；2）其他服务器节点成为了 leader；3）没有任何获胜者。
对于同一个任期，每个节点只会投票给一个 candidate，按照先来先服务的原则投票。获得过半选票（保证只有一个leader）的 candidate 赢得选举成为leader，立即向其他节点发送心跳消息来确定自己的地位并阻止新的选举。
在等待选票期间，candidate 可能会收到宣称是 leader 发来的添加日志请求（可能是心跳），如果该 leader 的任期号不小于 candidate 当前的任期号，candidate 会结束选举回到 follower 状态，否则保持 candidate 状态。
如果多个 follower 同时成为 candidate ,那么选票可能会瓜分导致没有一个 candidate 获得过半选票赢得选举，这样每个 candidate 都会超时，然后通过增加当前任期号来开始新一轮的选举。raft通过使用随机选举时间的方法来确保很少发生瓜分选票的情况发生。
日志复制
leader 被选举出来后，就开始接收处理客户端的请求。收到客户端的处理请求后，leader 将客户端请求的指令作为一条新的条目追加到日志中，并通过 AppendEntries 请求向其所有的 follower 发送该条目，让 follower 复制该条目。当超过一半的 follower 返回成功复制条目的回复时，leader 就把该条目提交，条目提交以后 leader 会应用该条目到它的状态机中（状态机执行该指令），然后把执行结果返回给客户端，leader 在随后也会通过周期性的 AppendEntries 请求通知 follower 该条目已提交，让 follower 将该条目应用各自的状态机中。
匹配特性
raft中的日志条目使用任期号和索引值来进行标识，每条日志条目存储一条状态机指令和leader收到指令时的任期号，索引值就是日志条目在日志的位置。
raft中的日志具有以下匹配特性：
- 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的的指令。
- 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也都相同。
一致性检查
在发送 AppendEntries 请求的时候，leader会将前一个日志条目的索引位置和任期号包含在里面，如果 follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么它就会拒绝该新的日志条目。这个一致性检查保证了第二条特性。
一致性的维护
正常情况的话，leader 和 follower 的日志保持一致，一致性检查从来不会失败。若 leader 出现崩溃可能会导致日志处于不一致的状态，follower 可能缺少在新 leader 中有的日志条目，也可能拥有一些新 leader 没有的条目。
raft通过让 leader 强制 follower 复制它的日志来解决不一致的问题，follower 中跟 leader 冲突的日志条目会被 leader 的日志条目覆盖。
要使得 follower 的日志跟自己一致，leader 必须找到两者达成一致的最大的日志条目（索引最大），删除 follower 日志中从那个点之后的所有日志条目，并且将自己从那个点之后的所有日志条目发送给 follower 。
安全性
选举的限制
在任何基于 leader 的一致性算法中，leader 最终都必须存储所有已经提交的日志条目。
raft 通过在选举投票机制中加入一个日志条目新旧的检查，来保证新 leader 在当选时就包含了之前所有任期中已经提交的日志条目。这样一致性维护的时候，日志条目的传送是单向的，只从 leader 到 follower。
candidate 在 RequestVote 请求中会带有它的最后一条日志条目的索引值和任期号，follower 收到 candidate 的 RequestVote 请求后，会检查自己的最后一条日志条目是否比 candidate 的最后一条日志条目要新，如果是则绝对不会给该 candidate 投票。这样保证了 candidate 收到过半的选票时 ，表明 candidate 的日志至少和过半的节点的日志一样新，那么它一定包含了所有已经提交的条目。
日志最后条目的任期号不一样的话，任期号大的日志更新；任期号相同，则日志较长的那个更新。
提交之前任期内的日志条目
该问题暂时还没有理解，简书：raft理解 by asmer中的问题5讲述的就是这个问题，但是结合这个和论文暂时还是没有理解。
参考：
分布式一致性算法：Raft 算法（Raft 论文翻译） 翻译版本1
寻找一种易于理解的一致性算法（扩展版）翻译版本2
简书：raft理解 by asmer