Raft

复制集包括可追加的日志和状态机，每个节点维护各自的复制集，复制集的内容完全相同，日志条目的内容和顺序最终一致

通过选举一个leader节点，来实现对复制集的管理，leader接收客户端请求，并将数据同步给集群其他节点，并且决定何时提交数据到状态机，当leader宕机，集群检测到后会选举一个新的leader

raft动态图

raft是一个基于leader的管理复制集的共识算法

由集群选举出来的唯一节点，接收客户端请求，同步给集群其他节点，并且提交数据到状态机

当发现有大于自己任期的请求，成为follower

leader

所有节点启动时的状态，不会发送任何请求，只会响应请求

当选举超时仍未收到请求时，转变为候选者

follower

选举时，leader的候选者

会向其他节点发送选票，当收到集群大多数选票时成为leader，当收到leader的心跳或者有大于自己任期的选票，成为follower，当选举超时的时候，任期加1，开始新一轮选举

candidate

raft集群角色

投票请求，投票阶段由候选者发送

主从同步请求，是由leader发送的日志数据，日志数据为空表示心跳

快照请求

请求

相当于一个逻辑时钟，每个节点维护自己的任期，是单调递增的，当一个节点收到的请求的任期大于自身，则更新自己的任期，如果小于自身，则拒绝这个请求

一个任期包括选举和正常处理客户端请求2个阶段，每个任期最多产生一个leader（大多数选票，节点在一个任期按照先到先得只给一个候选者投票）

如果收到的请求的任期大于自己，更新自己的任期；当候选者或leader收到的任期大于自己，则转变为follower

任期

概念

每个节点启动时的状态都是follower，每个节点维护一个定时器，超时时间是一定范围内的随机值，选举超时后，follower任期加1，转换成候选者，投票给自己，并且向其他节点发送投票请求，投票请求包含候选者id、任期、最新日志索引和最新日志任期

请求的任期大于等于自己，如果大于，更新自己的任期

在自己的任期内没有投过选票，或者投过相同的选票

最新日志的任期和索引大于等于自己，以确保选出来的leader具有所有已提交的日志

同意投票的条件

同一任期，每个节点按照先到先得只给一个候选者投票；候选者在选举超时时间内如果收到过半选票则成为leader，如果收到其他leader的同步请求则转为follower，如果选举超时，没收到过半选票和leader同步请求，则任期加1，重置选举超时时间，发起新一轮选举请求

候选者成为leader后，开始向其他节点发送心跳，使其他节点都保持follower的状态

必须要大于等于集群节点间发起请求到响应的平均时间

小于等于节点宕机的平均时间间隔

选举超时时间

leader选举

leader产生后，就可以接收客户端请求，leader将收到的数据变更信息追加到日志末尾，并且同步给其他节点，其他节点一致性检查通过后，再进行追加或覆盖自身日志，返回同步成功响应，当收到过半同步成功响应，提交日志到状态机，返回写入成功响应给客户端

对于尚未同步成功的少数节点，Leader会一直重试，即使已经响应了客户端，这样使得集群不会因为少数处理慢的节点而影响整体性能

对于leader，日志是只追加的，不会删除，日志由条目组成，每个条目包含数据变更指令、索引、以及提交该条目的节点的任期

用于日志一致性检查，索引和任期都相同表示这2条日志以及它们之前的日志都相同

用于网络分区恢复时的数据一致性检查，分区的不同集群的日志任期不同，分区故障恢复后，相同日志索引，取任期大的作为最终日志

日志任期的作用

写入状态机，持久化，最终写入所有节点的状态机（所有节点最终都需要提交日志）

提交索引由leader通过同步请求发送给follower，follower收到后写入自己的状态机

为了解决已提交的旧的日志被覆盖，raft规定不能直接提交当前任期之前的日志，只能提交当前任期的日志，而之前的日志被间接提交

日志的提交

同步的请求中包含了同步数据前一条的索引(nextIndex)和任期，follower收到后，检查索引和任期在自身日志中存在，才能接收该请求，从nextIndex+1开始追加或覆盖

一致性检查不通过时，leader减少同步数据的索引(nextIndex)，重发请求，直到匹配为止。这时follower冲突部分的日志会被覆盖

leader维护了每个节点的nextIndex，初始值为leader最大日志索引+1，然后通过一致性检查来逐步更新为匹配的最大日志索引

数据一致检查

日志复制

如果集群直接由旧的配置切换成新的，由于节点配置切换的时间点不同，那么就存在出现同一任期2个leader的情况

leader收到客户端扩缩容请求后，先向自身加入一条新旧集群并存的配置日志，当同步给集群大多数节点时，提交该并存配置，再写入、同步新集群的配置日志，节点同步到新配置，不属于集群的节点转为follower并下线

配置日志一旦追加，立即生效，不需要提交才生效

leader并存配置生效时，数据会同步给新旧所有节点，选举和提交需要得到新旧2个集群过半同意，如果发生选举，新旧节点都可能选为leader

并存配置的节点需要新旧2个集群过半同意，所以并存配置的节点和旧的配置的节点只会产生唯一一个leader

当并存配置提交时，说明过半节点已拥有并存配置，这时旧节点不可能选为leader，因为并存配置节点日志更新，得不到过半投票。这时可以安全地切换到新配置

选举安全

扩容时，如果新加入的节点比较多，使得过半机制需要包含这些节点，那么由于它们需要同步旧数据，将导致客户端发送的新数据迟迟得不到响应。解决方法：新加入的节点只同步数据，不参与过半机制，直到日志数据跟上leader进度后，leader才开始写入并存配置，进行配置变更。

缩容时，如果leader不在新集群中，那么日志复制时的过半统计不统计自己，当写入新配置时，转为follower并下线

由于移除的节点不能收到leader的心跳，选举超时成为候选者，会先旧集群所有节点发送投票请求，可能使得新集群leader转为follower，集群最终会选出新的leader，移除的节点还是收不到心跳，继续选举超时，导致集群不断重复选举

解决方法：节点在响应投票请求时，必须要判断当前是否已存在leader（该投票请求距离上一次leader心跳的时间间隔是否小于选举最小超时时间），如果存在，忽略这次投票请求

缩容时，移除的节点会干扰新集群

额外问题

动态扩缩容

每个节点会独立地为已提交的日志生成快照，作用是减少日志的存储空间，减少日志复制的时间

快照中包含了对应日志指令执行的最终状态、最新的集群配置、对应日志的最大索引和任期，索引和任期的作用是一致性检查，比如当Follower的快照之后没有日志条目时，需要得到快照的日志索引和任期。

快照生成完成后，对应的日志会被删除。

大多数情况下，节点独立生成各自快照，只有当leader没有follower需要的日志（已生成快照并且删除了），才会将快照发送给follower，一般发生在慢follower和新加入的节点

快照文件是按序分块传输的，当前块在快照文件的起始偏移量，0表示创建一个新的快照文件

快照传输

写快照的时机：日志达到指定门限大小时触发写快照，门限值应该显著大于生成的快照大小，这样可以显著减少磁盘带宽

使用写时复制的方法生成快照，不影响其他对日志数据的操作

日志压缩

客户端随机选择一个节点发送请求，如果不是leader，则拒绝请求并将leaderId返回客户端，客户端重新发起请求，如果超时，可以轮询选择下一节点重复上诉步骤

如何确保客户端请求只被执行一次：客户端每个不同的请求带一个唯一ID（重试的请求带相同id），集群状态机维护了每个客户端最近一次请求的ID和响应，如果客户端的一个请求已经发过响应，则不再重复执行该请求，直接返回该响应

客户端读如果直接从Leader读，可能因为网络分区（2个leader）的原因从过期leader读到过期数据，所以读也需要额外的操作：1、任期开始时leader是不知道提交索引的位置的，因此通过提交一个空的日志来确定提交索引，其实就是在任期开始时，leader会提交所有的日志2、在响应读请求之前，leader需要先发送一次心跳来确认是否分区故障而被废弃

读请求

客户端交互

Raft