RAFT从入门到放弃 Part-1
在分布式共识算法这个领域，paxos 横行了快20年。根本原因还是paxos基本上已经是唯一的解法了，但是他不容易理解，和实现上比较困难。个人觉得难以理解是因为阅读的时候总会去想如何实现，如果不去想如何实现，仅仅针对basic paxos而言，还是比较简单的。但是工业实现和算法本身有冲突。因为proposer的proposal最终提交的可能不是最开始的值，而且如何保证顺序等等实现细节lamport大神不屑于解释。所以后面出现了raft，raft 可以认为是一个mutil paxo的子集。更加侧重于how to build。而不是why this can work。
复制状态机
paxos也提到复制状态机，复制状态机是提供输入输出的一般程序。客户端的请求会被定义为log，log会按照一定的顺序通过共识算法在集群中达成一致。在确定集群达到一致后，会按照顺序执行log中的command，执行完毕后程序对外的运行时状态就是状态机，理想状态下该状态在整个集群中的每一个服务上都应该是一样的。
复制
主从复制
如果在项目中使用主从复制，而且是同步主从复制，那么主从在任意时刻都对外提供一摸一样的数据。如果主从中任意节点写入失败，则判定当前的写入失败，这种情况下，保证了CAP中的CP
主从异步复制，只要当master写入成功就可以判定为写入成功，从可以通过异步写入。该情况下，会出现从的数据和主的数据不保持一致的情况，但是写入性能会较大提升。主要保证CAP中的AP
半同步半异步 部分节点保证和主一模一样，部分可以允许丢失。如果同步数量较多，就是保证CP，如果异步复制较多，则主要是保证高吞吐。主要也是保证AP
无主复制
所有的节点都是平等的，客户端将请求发送给所有的节点，节点内部需要保证数据的一致性
该方式可以通过客户端一次性读取多个节点来实现，比如写入至少半数的节点，每次读取也是，然后读取发现部分节点没有其他节点已经有的数据，可以进行一个补偿性的写入
上诉两种方式，无主复制用的比较少，大部分都是主从复制。一般leader 对外提供读写服务。或者在某些场景下运行leader进行写，然后follower执行读。但是需要保证读取的数据在同步之后。也就是不会存在读取follower过期或者还没来得及同步的数据。
分布式共识 解决的其实就是这个复制和尽量保证高可用的问题。basic paxos 采用的有点类似于无主复制。mutil paxos 和raft 都是采用主从同步中的半同步半异步复制，假设当前集群中服务个数为n，同步复制的节点需要至少为major（n/2+1）才能保证当前对外提供的服务可用。
为什么是major个数的节点可用？主要是这么保证的话，那么节点中的数据在任何时候写入或者读取，都需要通过major个数来判定，在异常情况下，比如脑裂的情况下，有两个leader，他们的操作肯定会在一个服务上造成冲突，导致无法进行，从而可以让某个leader知道自己的可能不再是集群的leader。
分布式共识
上文简单的介绍了复制，复制主要是为了保证高可用，解决单点问题。在很多的时候，系统采用一主多从的方式将数据进行冗余，保证任意时刻leader 无法提供服务的时候，可以将follower提升为leader继续对外提供服务。所以将操作分为两部分，即：
leader 选举
leader 执行常规操作（复制日志）
后文将介绍raft是如何保证这两个操作是正确和安全的执行。
raft 组件
paxos 中agent 一共有三种状态
proposer
acceptor
learner
raft 的任意时刻，一台服务只能有一下三种状态中的一种
leader
follower
candidate
paxos 中上面的三个状态可以在任意一个agent中，一个agent可以有多个状态。即每个agent都对外进行复制操作，也接受其他agent传过来的复制操作，也会对达成一致的复制日志进行最终的处理（写入state machine）。mutil paxos 进行了简化，系统只有一个proposer，其他都是acceptor。在raft中，proposer就是leader,accepter就是follower，为了选举还引入了一个candidate。而且在raft中，每一个服务只会处于上三种状态中的一种。三种状态的转换方式为：
上图中，follower 只会接受来自leader 或者candidate的rpc请求，leader 复制接受客户端请求，一旦一个server（agent）成为了leader，他将对系统中其他的server发送心跳，当收到集群major个返回（确认当前的leader 没有发生变化）则说明server 仍然处于leader 状态。candidate 是当前的follower无法感知到leader后发起选举leader的时候一个中间状态，leader 可以退化成follower，follower可以进化成candidate，candidate 可以退化成follower，candidate可以进化成ledaer，但是leader一旦无法确认自己仍然是leader的时候，只能退化成follower。
paoxs中，将一个proposal 使用proposalNum 进行区分，而raft中，因为当前的follower知道自己的leader，所以，proposalNum 退化为term，即每次leader 会将term 包含在复制rpc中，follower根据term 确定当前的leader是否合法。term在集群中都是单调递增的数字，它是集群服务中的一个logic clock，可以让server 发现已经过时的leader，也能够通过term确定写入的合法性和进行选举。只有在集群发生选举的时候，集群中的term才会发生变化。
如果server 当前的term小于接收到到的term，server会将自己的term 设置为接收到的term
如果一个candidate 接收到的term 小于收到的term，他会将自己的状态切换为follower，执行1
如果server 接收到小于当前term的请求，则拒绝请求。
server的状态
每个server中的状态
currentTerm 当前服务接收到的最新的leader的term，初始为0，后续单调递增
VoteFor 接收到选举请求的时候的candidateID,没有选举的时候为null
log[] 准备写入状态机中的日志数组
commitIndex 已经被commit 的Index，此处的commit 表示为已经被复制到major的server上，但是可能还没有被状态机执行。
lastApplied 被执行到状态机中的index
leader 中的状态
nextIndex[] 准备复制给给对应follower的index，初始化为当前leader的最新的logIndex
matchIndex[] 已经被复制到follower的index，初始化为0
RPC 请求
appendEntriesRpc
arguments
term leader的term
leaderID leader的serverid
preLogIndex 上一个append的log数组index
preLogTerm 上一个append的log数组的term
entries[] 本次传送的log的entries
leaderCommit leader 已经确定被复制到大多数的index
result 和receiver implementation
term currentTerm 当前server的term
success
true 如果说preLogIndex 和preLogTerm 和传过来的值相等，则返回true
false 如果收到的term< currentTerm
false 如果preLogIndex 和preLogTerm 和当前的值不匹配
在2,3 都为true 的情况下，已经存在preLogIndex +1 的位置（此时需要写入数据的位置），已经存在数据，则删除已经存在的数据以及后面的数据
写入entries
如果ledaerCommit > commitIndex ，设置commitIndex 为leader的commitIndex 和当前log中index 中的最小值。
RequestVoteRPC
arguments
term 候选人的term，在没有收到来自leader的心跳的时候，follower 将自己进化为candidate，并且将currentTerm+1
candidateId candidate的serverid
lastLogIndex log数组中的最新日志
lastLogTerm log数组中的最新的term
result
term 返回server当前的term
VoteGranted 如果candidate在当前server中获得了选票，则返回true，表示给当前的candidate 投票
如果currentTerm>term 返回false，否则执行2
如果candidate的log 比当前server的log 要更加 up-to-date，而且当前voteFor为null或者为当前的candidate，则返回true
每个服务需要遵守的规则
所有的服务器 allServers
如果commitIndex > lastApplied ,增加lastApplied，并且将log[lastApplied] 写入到状态机器中，
如果上面的rpc请求中，返回的值包含的term> currentTerm,则将currentTerm设置为term，并且将状态修改为follower
收到来自leader的appendRPC 或者心跳（entries为空的appendRpc），重置election timeout。
followers
接受和返回来自leader和candidate的请求
如果election timeout内没有收到append日志请求或者心跳请求（心跳为特殊的append请求）也没有收到candidate的选举请求，则进化为candidate
candidate
在follower 进化为candidate之后，开始选举操作
将currentTerm 增加
给自己投票，设置voteFor=serverId
重置election timeout，发送选举请求给其他的服务。
4* 如果收到major服务的选票（返回的GrantVote为true），进化为leader
5* 如果收到来自leader的appendRpc，退化为follower
6* 如果在election timeout 时间内没有获得选票，重新执行上面的1，2，3.
leader
发送appendRpc 给集群中的其他服务，如果没有append请求，则需要在指定的时间（小于server的election timeout）发送心跳请求给其他的服务。
接收到来自客户端的请求，写入本地的log中，当该log已经被apply 到statemachine之后，返回给客户端
如果lastLogIndex 大于follower的nextIndex，发送从follower的nextindex开始的entries。
如果返回true，成功写入到follower，增加follower对应的nextIndex 和matchIndex。
如果返回false，则将当前的nextIndex 往后递减，然后发送。一直到对应上。
如果存在一个index为N，N> CommitIndex, 而且major matchIndex>= N,log[N].term=currentTerm，将commitIndex 设置为N。
可以看到，commitIndex就是已经复制给大多数的日志index，也就是可以准备apply到状态机中的index。
raft 遵循的强制性要求
在每个时间点，raft都遵循以下几个要求，或者说下面的属性，在raft服务执行过程中任意时间都为true。
Election Safety
任意一次选举，都只会选举出一个leader
Leader Append-Only
leader只会不断的append日志，不会删除或者更改日志。
Log Matching
如果两个服务中的log[i] 拥有相同的index 和term，在此之前的所有的log 中的entry 完全相同。
Leader Completeness
如果一个log已经在某个term中被提交，那么在后续的所有term中，该log都可见。
State Machine Safety
如果一个log的index 里的entry已经被apply 到state machine，那么不会有任何一个server中在该index 对应的位置apply一个另外的entry到state machine中。
从appendRpc成功的要求，必须保障preIndex 和preTerm相等，而且有logMatching，和leaderAppendOnly，即可以看出，raft在mutli paxos上面新增了一些强制要求，不在有日志空洞。而通过获得选票的条件可以看出，raft的每次选出来的leader 都是尽量包含当前上一任term中最全日志的。所以减少了后续针对日志空洞的补全，但是不支持乱序append，只能按部就班一个个append 到日志中。
leader election
raft的选举比较简单，就是通过随机触发的方式开始进行选举，服务启动的时候都是folllower。server中一共有两个时间，一个是选举超时（election timeout）的时间，个人理解是当前leader获得的lease，即在该时间段，follower 不会认为leader已经丢失了leader的身份（除非收到了voteRpc请求）。还有一个就是发送心跳（heartbeat time）的时间，改时间是定时发送心跳给follower，重置follower的 election timeout，相当于找follower继续活的lease。当然，如果leader 在心跳超时的时间里持续发送append，则会重置本地的heartbeat time 和follower的election timeout，来节约网络开销。为了避免减少选举出现的冲突，raft 将election timeout 设置为一个随机数，论文建议范围为（150-300ms）。那么对于的心跳时间应该小于该时间。
$$
选举的操作其实可以看作为一次basic paxos，即集群在谁是leader上达成共识。
$$
但是raft 在一次paxos中做了很多的工作，确保两件事情：
尽量减少冲突
通过随机睡眠时间，在一定的时间范围内，尽量避免多个candidate 发起选举
选举出来的leader 中包含了更加完整的日志
按照先来先服务（first come，first service）的原则。
收到投票请求的server（V）发现自己的日志比candidate（C）更加完整会拒绝对方的请求，(lastTermV > lastTermC) ||�(lastTermV == lastTermC) && (lastIndexV > lastIndexC)。
判断当前来的term 是否小于currentTerm,如果是，直接返回false
如果当前来的term 大于本身的term，将currentTerm设置为term，将自己设置为follower。进行下一步检查。
如果当前的已经给其他人投票了，返回false
如果当前没有给其他人投票，或者已经给本次发起投票的candidate投过票
判断candidate的lastTerm 是否大于自身的lastTerm，是就返回投票
如果candidate的lastTerm小于自身的lastTerm，返回false
如果candidate的lastTerm 等于自身的lastTerm，则比较日志的lastIndex
如果candidate的lastIndex 大于等于自身的lastIndex，则返回投票
如果candidate 小于自身的lastIndex，则返回false
返回投票之前，需要将voteFor 设置为candidate的id
candidate 收到投票的结果，如果有一个term大于自己的term，则将currentTerm设置为较大值，并且放弃本轮投票，退化为follower。
如果没有出现6 的情况，而且major的server 都给candidate 投票，则切换成leader。
如果在7收到选票后挂掉，还没有来得及心跳。则新的选举开始，注意的是voteFor里面是当前term 下的candidate，如果说term 发生变化，则candidateId 需要重置
由于各种原因，某台机器自己脱离了集群，但是没有挂掉，于是会不断的进行选举重试也就是会不断增加现在term，如果最后该集群回到了集群，此时他的term 会比现在leader的term大很多，导致集群发送重新选举，而且term 会跨越很大。为了防止该问题出现，会在askVote之前进行一个preVote，只有在能和major个server正常通信的情况下。才会进入到candidate的角色。
candidate 切换为leader 后，开始向集群发起心跳。
heartBeatTime < electionTimeout < MTBF ((average) time between failures for a single server.)
领导选举主要是通过上面的两种限制，做到了选举leader的时候减少同一时间多个candidate参与选举，从而瓜分选票，导致无法第一时间选出leader。通过控制给对方投票的条件，做到了选出的leader 应该拥有绝大部分的log，至少，commit的log即已经被复制到大多数的日志肯定可以被leader 感知到，因为获得选票也需要是major的follower参与。但是整个选举肯定是安全的，即不可能选举出两个相同的leader。
Log replication
上图为一个可能的集群状态，每个log的entry都包含了term和command，日志是从leader 流向follower的，而且leader永远不会修改自己的log，只会不断的追加日志。这么做的意义和好处是啥呢？
便于处理不一致的日志
如上图，在某时刻发生election，其中最上面的成为了leader
这里首先来看下在leader 被选出来的时候内部的状态
首先原来的leader 应该是c，因为c中term6下的日志比其他多
在index 10 的时候，c可能发生了网络分区，但是在选举超时的过程中，他仍然在对外提供服务index11=6，term=6 ，然后d在term7 的时候获得了大部分的选票,然后写入了两个log。
在index11 复制过程中，d又发生了网络分区，此时top中的term为7，lastLogterm为6，lastLogIndex为11，最终，top变成了leader，此时集群term为8.
在top成为leader以后，集群中有的server 日志过多（c，d），有点太少（a,b），还有不一致的（c,d,e,f）。但是已经commit到大多数的日志{term=6,index=9}的日志肯定是在leader中的，所以，此时使用leader 的日志为准。那么复制到major的日志肯定是不会丢失的，我们的状态机肯定处于安全的位置
但是还有一个问题，就是如果是C成为了leader，那么前面没有复制到major的{term=6,index=11}，后续也会被提交到大部分的日志中，这里可能会给客户端带来困扰，因为前文提到，C 可能成为leader后收到index=11 的entry，但是没有复制给major就发生了网络分区，甚至挂了，但是该日志已经被写入了index11，后续立马重启的时候回到集群，并且当选，但是我们已经给客户端发送了写入失败情况，在过两轮，index11 被写入到了集群中，那么后续客户端发现该日志中的command已经处理过了。
然后就是{b,e,f}这种term 和index 都不一样，而且term远小于当前leader的log，直接使用leader的日志进行覆盖，这样在前面已经commit的日志肯定在leader中的保证下状态机也是安全的。因为raft原本是从前往后挨着找，比较费时，可以在
减少中间状态
在mutli paxos中，leader 需要对空洞日志进行补充，但是使用连续的日志，就不会存在空洞的日志，而raft中，一旦一个leader 当选，他只需要开始接受请求，执行日志复制就ok了。这样减少了复杂度，而且数据都是可靠的。
leader不能提交非自己任期的log
日志的状态有：
appended 已经被写入到当前的节点，lastLogIndex
commit 已经被写入到major。CommitIndex
LastApplied 已经被写入到状态机中 LastApplied
LastLogIndex \geqcommitIndex\geqLastApplied
可以看到，只有leader 知道那些日志已经被commit了，所以append的请求里需要包含leader的lastCommit，然后客户端收到该数据，更新自己的数据。如果复制到了major，但是没有收到更新lastCommit的数据，此时follower其实是不知道当前的已经commit的位置的，所以发生选主以后，确定commit的位置是个比较重要的工作，也是可能出问题的操作。
figure3.7
figure3.7 可以展示为什么当前的 leader 不能直接复制和提交前面任期的日志。考虑现有场景，s1-s5 组成的集群中，
a场景，s1-s5中的currentTerm=2，此时s1为 leader ，写入了{term2,index2}，只复制到了s2上。
b场景， s1失去 leader ，此时s5通过{s3,s4,s5}获得 leader 的权限，s2-s4中的currentTerm=3，然后s5写入了一个{term3,index2}，然后s5挂掉，此时s1醒过来，此时s1获得选票(考虑的场景s4先醒过来，然后发送term=4给s1,但是s4没有获得major，然后s1timeout，成为 leader ）。
c场景，如果 leader 可以直接复制和提交前任的log，s1 将{term2,index2}写入了major的server中(s1,s2,s3)。如果还没有来得及commit的时候s1挂掉，此时{term2,index2}已经被commit了，只是s1没有将commit消息发送给s2,s3。
d1场景，s5 回到集群，然后成为 leader （由于他的index2的term为3，此时s2,s3，s4的currentTerm为4，所以s5 获得的term为5），然后相同的，他将term3的日志进行复制,可能会出现d1的情况，就是index2 原本已经被复制的term2的数据被覆盖了。也就是已经commit的日志被覆盖掉了，这是不被允许的。
d2场景，如果不允许直接复制活着提交前任的log，而是只能提交和复制当前term的日志，s1只负责复制term4的日志，这样通过上面的append 规则，会将前任的log自动提交。有一种情况是term为4的时候一直没有收到任何的日志请求，导致term2 一只无法被复制或者commit的情况，所以每次选举后， leader 会发送一条noOp的append 日志，然后隐形提交前任term的log。
## 综述
raft 通过限制leader的选举，确保leader 包含了当前commit的所有日志，保证不会出现已经commit的日志丢失。采用随机时间内发生选举，减少选举过程中的冲突。通过限制append，必须和前面的日志匹配才能append，让日志没有空洞日志，减少了选举之后leader的行为。通过确保leader 只会append 和commit 自己term的日志，减少可能存在的已经被commit 的日志丢失的情况。
