raft是一种共识算法，各节点可以就指定值达成共识，达成共识后的值，就不再改变了。raft是基于论文 https://raft.github.io/raft.pdf，raft是paxos的一种实现，它简化了paxos的模型，增加了很多约束和限定条件，使得更容易在生产中落地，简要描述如下（摘自https://github.com/hashicorp/raft）：

协议描述

raft节点有3种状态：跟随者、候选人、领导者。所有的节点初始都是跟随者。在跟随者这个状态，节点可以接受来自领导者的日志复制和选举投票。如果在随机等待时间内没有收到请求，节点就推举自己为候选人。在候选人这个状态，节点发送请求投票给其他节点。如果节点收到大多数节点的投票，那么候选人就晋升为领导者。领导者必须接收新的日志并且复制日志到其他节点。所有的读写请求都必须在领导者节点上。

一旦集群有了领导者，它就能够接收新的日志。客户端可以请求领导者添加新的日志项，对于raft来说，日志项是一个二进制对象。领导者可以把日志项写到持久化存储中并且尝试复制日志到大多数节点上。一旦日志项被复制到大多数节点上，那么就视为提交，领导者就把日志项应用到有限状态机。有限状态机是一个应用特定的，并且用接口实现的。

有一个跟日志复制相关的明显问题。raft提供一个机制来把当前状态生成快照，并且日志是压缩的。因为有限状态机的抽象化，复原有限状态机的状态必须把所有的日志重放一遍。raft会生成快照，并且把快照之前的日志都删除掉。整个过程是自动的，不需要人工干预的，并且这样也可以防止一直消耗磁盘空间，也可以减少复原日志的时间。

最后，当集群增加节点或者移除节点时，只要存在大多数节点，那么raft就可以自动更新集群信息。但是如果大多数节点无法保证，那么这就会变成一个非常棘手的问题。假如，集群中只有2个节点，A和B。仲裁节点个数也是2，这就意味着所有的节点必须达成共识才能提交新的日志项。假如，节点A或者B失败了，那么就不可能达成仲裁。这就意味着集群无法添加，或者删除，或者提交其他的日志项。这样会导致集群的不可用。这个时候，人工干预就不可避免，需要删除节点A或者节点B，并且重新启动集群。

3个节点的raft集群可以忍受1个节点宕机，5个节点的集群可以忍受2个节点宕机。推荐的配置是3个节点或者5个节点，否则更多的节点会导致性能问题。

raft比paxos的性能好一点。假如领导者比较稳定，那么提交一个新的日志项需要所有大多数节点的来回请求。性能表现也取决于磁盘I/O和网络延迟。

成员状态

raft节点有3种状态：

• 领导者（leader） - 领导者是整个集群的领导者，所有读写请求都必须在领导者节点上。只要集群中有领导者，那么就不会发生新的选举。领导者会定期发送心跳给跟随者，告诉其它节点，我还活着，不要触发选举。领导者也会同步日志给跟随者，跟随者复制日志并应用到本地状态机。
• 跟随者（follower） - 跟随者会接收来自领导者的心跳请求和复制日志请求。如果在一定的时间内没有收到领导者的心跳请求，那么跟随者会立马把自己的状态变成候选人。
• 候选人（candidate）- 跟随者变成候选人之后，会立马给自己投上一票，然后发送请求投票rpc消息给其它的节点寻求票数，只要票数足够，候选人会变成领导者。在选举期间，整个集群不可用，无法对外提供服务。

领导者选举

以3节点为例，集群启动时，所有节点的初始状态是跟随者：

1. 节点1的timeout最小，最先因为心跳超时而触发选举，首先节点1把自己变为候选人，同时给自己投上一票，然后发送请求投票rpc消息给节点2
2. 节点1同时发送请求投票rpc消息给节点3
3. 节点2收到请求投票rpc消息，发现有新的选举，给节点1投上一票
4. 节点3收到请求投票rpc消息，发现有新的选举，给节点1投上一票
5. 节点1成为领导者之后，发送心跳rpc消息给节点2
6. 节点1发送心跳rpc消息给节点3
7. 节点2收到心跳rpc消息，知道领导者还活着，不触发新的选举
8. 节点3收到心跳rpc消息，知道领导者还活着，不触发新的选举

***这里有几个关键的点：***

• 心跳超时timeout是随机的，这样就不会因为心跳超时而同时触发选举，比如配置了x ms，随机时间取x ms和 2x ms之间的数
• 每一届领导者都是有任期编号term，rpc消息中都会带上选举的任期编号，当节点2/3接收请求投票rpc消息时，发现任期编号大于自己当前的任期编号，就给节点1投上一票
• 节点成为领导者之后，会周期性的给跟随者发送心跳消息，阻止跟随者触发新的选举
• 在一届任期内，赢得大多数选票的节点成为领导者，如果在选举超时时间内，没有赢得大多数选票，就会触发新的选举。在一届任期内，每个节点至多只会投1票。比如，节点1在任期4内请求节点2投票，节点2会把当前的票投给节点1，节点3在任期4内再来请求节点2投票时，节点2就没有票可以投了
• 任期编号大的节点会拒绝投票给任期编号小的候选人。比如发生网络分区时，有一个跟随者单独在一个网络分区，因为无法跟其它节点通讯，会触发选举，增加任期编号为2，其它2个节点的任期编号已经是3了，这个时候，另外2个节点就会拒绝任期编号为2的节点的请求投票
• 日志完整性高的节点拒绝投票给日志完整性低的节点，rpc消息中都会带上最后一条日志的索引和任期编号。比如发生网络分区时，有一个跟随者单独在一个网络分区，因为无法跟其它节点通讯，日志复制就慢一拍，那么日志完整性就低，当触发新的选举时，即使选举的任期编号更大，但是，因为日志完整性低，其它节点也会拒绝投票

日志复制

日志复制是raft中非常重要的内容，客户端给raft集群提交的数据是以日志的形式存在的，一条一条的指令就是日志中一个一个日志项。raft集群处理客户端写请求的过程，就是一个复制和应用日志项到状态机的过程。

日志包含以下信息：

•  索引值：日志项对应的索引值，是连续的、递增的数字
• 任期编号：当前领导者所在的任期编号
• 指令：就是客户端提交的数据，以指令的形式存在日志项中，比如把键为foo的值设置成bar，可以写成指令set foo=bar

***那么如何复制日志呢？***

1.  客户端发送写请求提交数据
2. 领导者接收到请求，发送日志复制rpc消息给跟随者，rpc消息里面包含领导者最新的日志项
3. 领导者确认日志复制到大多数节点上，然后提交日志并应用到本地状态机
4. 领导者返回结果给客户端
5. 在下一次心跳rpc消息或者日志复制rpc消息中，包含领导者已经提交的日志项
6. 跟随者接收到，发现领导者已经提交但是自己没有提交时，就会应用到本地状态机

上面第3点中，领导者确认日志复制到大多数节点上时就会提交日志，如果这个时候有一个跟随者节点宕机或者网络原因，没有接收到最新的日志复制rpc消息，那么当它恢复时，

***raft算法时如何实现日志一致的呢？***

1.  领导者发送日志复制请求给跟随者时，消息中会有LogEntry（当前日志索引：4）、LogTerm（当前任期编号：2）、PrevLogEntry（上一条日志索引：3）、PrevLogTerm（上一条日志任期编号：1）
2. 跟随者发现自己不存在PrevLogEntry、PrevLogTerm时，返回错误给领导者
3. 领导者发现跟随者返回错误时，就发送复制前一条日志的请求给跟随者，消息中会有LogEntry（当前日志索引：3）、LogTerm（当前任期编号：1）、PrevLogEntry（上一条日志索引：2）、PrevLogTerm（上一条日志任期编号：1）
4. 跟随者发现自己存在PrevLogEntry、PrevLogTerm时，就复制日志到自己的本地，返回成功给领导者
5. 领导者接着发送复制下一条日志的请求给跟随者
6. 跟随者复制日志成功并返回

成员变更

成员变更是生产上使用raft集群时会碰到的问题，比如raft集群中某个节点宕机了，需要进行节点替换或者增加节点。在成员变更的时候，可能发生双leader的情况。比如有一个3节点集群，增加2个节点，那么可能发生下面这种情况：

1. 通过调用领导者的增加节点接口添加节点D和E，leader把最新的集群节点信息[A, B, C, D, E]作为日志项复制到其它跟随者节点
2. 当日志复制到大多数节点C、D、E后，最新的配置信息作为日志项提交leader并应用到状态机，这样C、D、E中就是最新的5节点[A, B, C, D, E]，A、B还是老的3节点[A, B, C]
3. 这个时候，发生网络分区，C、D、E在一个网络里面，A和B在另一个网络里面
4. A和B触发选举，选举出节点A作为leader，C、D、E中还是节点C作为leader，这个时候集群中就出现了2个leader

***那么如何避免出现双leader的情况呢？***

• 因为配置信息是动态添加的，同步配置信息的时候发生网络分区才出现双leader。那么一开始把所有节点信息都配置好，然后统一启动集群，可以避免这个问题。如果集群已经在运行，就需要停止集群再重新启动。这种方式不适合生产上不能停机的情况
• 另外一种方式是进行单节点变更，一次只变更一个节点，等到添加完成后，再变更下一个节点，具体如下：

1.  3节点集群增加一个节点D，新配置信息同步到B、C、D大多数节点后，B、C、D中的配置信息是4节点[A, B, C, D]，A的信息可能还是[A, B, C]
2. 继续增加节点E，新配置信息同步到C、D、E大多数节点后，C、D、E中配置信息是5节点[A, B, C, D, E]，此时，即使发生网络分区，如C、D、E在一个分区中，C成为leader，如A、B在一个分区中，A无法成为leader，因为A的日志完整性比节点B低，而B要成为leader的条件是得到大多数的选票，至少需要3票，但是同一个网络里面只有2个节点，B也无法成为leader，这样整个5节点集群也只会有1个leader

 可以发现，只要保证节点变更时，集群无法形成2个大多数，那么就不会出现双leader的情况。这里执行单节点变更时，需要等待上一次单节点变更完成。如果一次单节点变更没有完成，新的单节点变更又开始，在网络分区的情况下，是可能出现2个领导者的。一般在领导者启动时，创建一个NO_OP日志项，这样可以确保可能正在进行的单节点变更，已执行完成，这样再执行其它单节点变更不会有问题

基于raft算法实现一个简单的KV存储

本人基于开源的hashcorp raft算法实现一个简单的KV存储 https://gitee.com/liuanyou/myraft.git ，大概实现思路如下：

• 提供http接口写KV，在接收到KV数据之后，把KV数据写操作作为日志项应用到leader节点，等到日志项复制到大多数节点之后，应用日志项到状态机。在应用状态机的时候，获取日志项中的KV数据，然后保存到文件中。调用http接口读KV时，从文件中读取对应key的value数据
• 启动raft集群时，事先指定好所有节点的配置信息，这样启动后就会触发选举，选举出leader节点
• 客户端调用http接口，如果访问的不是leader节点，那么会把leader节点的信息作为response发送给客户端，这样客户端会请求leader节点的http接口