1
通过算法分解（leader选举，日志复制和安全）和减少状态机的状态来提升Raft的可理解性
Raft独特的特性
- 强leader： 日志只从leader发送给其他的服务器
- leader选举： 使用随机计时器来选举领导人，在解决冲突的时候更加简单
- 成员关系调整： 使用共同一致(Joint Consensus)的方法来处理集群成员变化的问题，处于调整过程中的两种不同配置的集群中大多数会有重叠，让我们可以在集群变化的时候保证可用性
2 Replicated state machine
在一组服务器上的状态机具有相同状态的副本，并且在一些机器宕掉的情况下也可以继续使用。比如一些大规模的系统通常有一个集群leader，在一个独立的复制状态机中去管理leader选举和存储配置信息，比如chubby和zookeeper
replicated state machine通常是基于复制日志实现的，每一个服务器存储一个包含一系列指令的日志，并根据日志的顺序进行执行
一致性算法的任务就是保证复制日志的一致性，服务器上的一致性模块接收客户端发送的指令，然后添加到自己的日志中。它和其他的服务器上的一致性模块进行通信来保证每个服务器上的日志最终都以相同的顺序包含相同的请求。一旦指令被正确的复制，每个服务器的状态机按照日志顺序处理他们，然后将输出结果返回给客户端。这样服务器集群就（看起来）形成了一个可靠的状态机
实际系统中使用的一致性算法通常有以下特性：
- 安全性保证（绝对不会返回一个错误的结果）
- 可用性： 集群中只要有大多数的机器可运行并且能够相互通信，和客户端通信，就可以保证可用
- 不依赖时序来保证一致性： 物理时钟错误或者极端的消息延迟在最坏情况下才会导致可用性问题
- 一条指令可以在集群的大多数节点响应一轮RPC时完成，小部分比较慢的节点不会影响系统的整体性能
5
Raft通过选举一个leader，然后给予他全部的管理复制日志的责任来实现一致性。leader从客户端接受日志并复制到其他的服务器上，并且告诉其他的服务器什么时候可以安全的将日志应用到他们的状态机中。拥有一个leader可以大大简化对复制日志的管理。当leader发生故障，或者出现网络分区时，一个新的leader会被选举出来
5.1 基础
服务器状态以及他们的转化关系
提一下从Leader变成Follower这种情况，比如现在我们有一个leader，然后发生了network partition，这个leader与其他的服务器失去了联系，其他的服务器就会选举出一个新的leader。然后当network partition恢复的时候，老的leader会发现这个新的leader拥有更高的任期，他就会自己变成follower
每个任期开始都是一次选举，然后就是正常的操作。有的时候选举会失败，那么这个任期就会因为没有leader而结束
Raft可以保证在一个任期中最多只有一个领导人
任期在Raft中充当逻辑时钟的作用，使得服务器可以检测一些过时的信息：比如过时的leader。每次服务器通信的时候都会交换当前的任期号，如果一个服务器的任期号比其他人小，那么他就会更新自己的编号到较大的编号值。如果一个节点接收到一个包含过期任期号的请求，那么他就会直接拒绝这个请求
5.2 leader选举
leader周期性的向所有的跟随者发送心跳包（不包含日志项的AppendEntries RPC）来维护自己的权威。如果一个follower在一段时间内没有收到任何消息（election timeout），他会认为没有leader，并开始一次选举来选择新的leader
follower首先增加他的currentTerm，然后变成候选人状态。接着他为自己投票并向其他的服务器发送RequestVote RPC。直到（a）他赢得了选举，（b）其他的server赢得了选举，（c）一段时间后没有winner）
在一个任期中，一个server最多投一次票（存储在persistent storage中）。一旦一个服务器赢得了选举，他就会变成leader并向其他的服务器发送心跳包
在等待投票的时候，如果一个候选人收到了AppendEntries RPC，如果这个leader的任期号不小于当前候选人的任期号，那么这个候选人就会认为这个leader是合法的，并退回到follower状态。如果leader的任期号小于当前候选人的任期号，那么候选人就会拒绝这次RPC
还有一种情况就是split votes，有可能有多个候选人，导致我们找不到一个候选人有大多数的票。这时每个候选人都会超时并开启新的一轮的选举。Raft通过随机化超时的时间来避免split votes的情况。大多数时间只会有一个server超时，所以他会赢得选举并在其他人超时之前发送心跳包。
5.3 日志复制
在leader将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交
leader跟踪的最大的将会被提交的日志的索引，并且索引值会被包含在RPC中，这样其他的server可以知道leader的提交位置。一旦follower知道一条日志条目已经被提交，那么他就会将这个日志应用到本地的状态机中
figure3中的log matching property，Raft保证：
- 如果不同的日志中的两个条目拥有相同的索引和任期号，他们这两个条目包含的指令相同
- 如果不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前所有的日志条目也都完全相同
第一个特性来自于这样一个事实，leader最多在一个任期内在指定的一个日志索引位置创建一条日志条目。所以如果同位置的情况下任期相同，说明他们的日志也相同
第二个特性由AppendEntries RPC的一致性检查所保证，在发送AppendEntries RPC的时候，leader会把新的日志条目前一个条目的索引位置和任期号包含在日志内。如果follower在他的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。每一次我们Append都保证前一个条目相同，所以我们也就保证了前面所有的日志条目都完全相同
当leader崩溃的时候，就可能导致日志处于不一致的状态
当一个leader当选时，follower可能是下面的任何情况。a，b是缺少一些日志，c，d是有一些未提交的日志条目，e，f则是都存在。
比如f中，某个服务器是任期2的leader，他附加了一些日志条目到自己的日志中，但是在提交前崩溃了，他恢复以后又赢得了选举，成为任期3的leader，附加了一些日志以后又崩溃了
Raft中leader通过强制follower直接复制自己的日志来处理不一致的问题，这意味着follower中冲突的日志会被leader的日志覆盖
要让follower的日志和自己一致，leader必须找到最后两者达成一致的地方，然后删除follower在那个点之后的所有日志条目，并发送自己在那个点之后的日志给follower
leader为每个follower维护了一个nextIndex，表示下一个需要发送给follower的日志的索引。当一个leader刚上任的时候，他会初始化所有的nextIndex为自己的最后一条日志的index + 1，如果一个follower的日志和leader不一致，那么下次RPC时的一致性检查就会失败。leader就会减小nextIndex并进行重试，最终他们会在某个位置上达成一致。一旦AppendEntries RPC成功，那么follower的日志就会和leader保持一致，并在接下来的任期内一直保持
一个优化是的当follower检测到冲突的任期的时候，他可以返回冲突任期对应的最小的日志索引号，这样可以一次跳过一个冲突任期中所有的日志条目
leader从不会覆盖或者删除自己的日志
5.4 安全性
当Leader提交了一些日志的时候，可能follower会进入不可用状态。之后这个follower可能被选举为leader并覆盖了这些日志条目，就出现了不同的机器执行不同的指令序列的情况。
通过在选举leader的时候添加一些限制来完善Raft。从而保证任何leader对于给定的任期号，都拥有了之前任期所有被提交的日志条目。
Raft保证选举的时候的新的leader拥有所有之前任期中已经提交的日志条目，而不需要传送这些日志条目给leader。这意味着日志条目的传送是单向的，只从leader传送到follower
候选人为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中的其中一个之上。如果候选人的日志至少和大多数服务器节点一样新，那么他一定拥有了所有已经提交的日志条目。RequestVote RPC中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求
Raft通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁的比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更新。如果任期号相同，那么日志比较长的那个就更新。
如果一个leader在提交日志之前崩溃了，未来后续的leader会继续尝试复制这条日志。然后一个leader不能断定之前任期里的日志被保存在大多数的服务器上的时候就一定已经提交了。
上面的图就展示了一种情况，黄色的日志虽然已经被复制到的大多数的server上，但是还是有可能被蓝色日志覆盖的
为了防止这样的问题发生，Raft不会去尝试在当前任期通过计算副本的数量来commit日志。在c情况中，任期4的时候，尽管2号日志已经有了大多数的副本，但是他不会被commit。对于当前任期的日志，如果他被提交了，那么之前的那些日志也都会被间接的提交（通过Log Matching Property）。所以Leader就可以安全的声称之前的log也都被commit了
5.5 follower崩溃
由于Raft的RPC都是幂等的，所以当follower崩溃后leader就会进行无限的重试，并且重试不会造成任何问题
5.6 时间
我们要保证broadcastTime ≪ electionTimeout ≪ MTBF（平均故障时间）
这个比较容易理解，广播时间要小于选举超时时间，不然很容易出现服务器开始新的选举
当leader崩溃后，系统会在选举时间内不可用，所以选举时间不能很长
6 集群成员变化
在集群添加新机器的时候，我们就有可能出现两个leader
Raft中，在切换的时候我们需要先切换到一个过度状态，叫做共同一致
共同一致是新老配置的结合：
- 日志条目被复制给集群中新，老配置所有的服务器
- 新，老配置的服务器都可以成为leader
- 达成一致（选举和提交）需要分别在两种配置上获得大多数的支持
当一个leader接收到从C-old改变配置到C-new的时候，他会将C-old-new作为log发给其他的副本。一旦一个服务器将新的配置放到他的log中，他就会用这个配置（无论这个配置有没有提交）。leader会使用C-old-new中的规则来决定什么时候去提交这个配置。
如果leader崩溃了，一个新的leader可能会有C-old或者C-old-new来作为配置
当C-old-new提交了之后，我们可以保证新的leader已经有C-old-new的log了。然后我们可以创建C-new的log并提交他。
在图中可以看到，没有C-old和C-new可以同时进行决策的时候，所以可以保证安全性
新的服务器可能没有存储任何的日志，当新的服务器加入集群时，他们需要一定的时间去追赶，这时候还不能提交新的日志条目。所以Raft使用一种额外的阶段，在这个阶段，新的服务器会接收日志，但没有投票权。直到他们追上了其他机器
集群的leader可能不是新配置的一员，在这种情况下，leader会在提交了C-new以后回到follower状态。因为在C-new提交的时候，是最早的新的配置可以独立工作的时间
移除不在C-new中的服务器可能会扰乱集群，这些服务器不再收到心跳，所以当超时时他们会开始新的选举。新的leader会被选举出来，但是这些服务器会再次超时。为了避免这个问题，当服务器确认当前leader存在时，服务器将会忽略RequestVote RPC。当服务器在当前的最小选举时间内收到一个RequestVote RPC，他会忽略这个请求。
7 日志压缩
Raft的快照主要包括将状态机的状态写入到快照中。最后被包含的索引以及最后被包含的任期用来做一致性检查。为了支持集群成员更新，也将最后一次配置存储下来。一旦服务器完成一个快照，他就可以删除最后索引位置之前的所有日志和快照了
当leader已经删除了下一条需要发送给follower的日志时，他就需要将快照发生给他们
follower可以在不知道leader的情况下创建快照。因为创建快照的时候一致性已经达成，这时候不存在冲突了。
通过COW来解决创建快照时可能导致的阻塞问题
8 客户端交互
Raft的目标是实现线性化语义（每一个操作立即执行并且只执行一次，在他调用和回复之间）。但是我们有可能执行同一个命令多次。比如Raft提交一个日志以后，但是在响应客户端之前崩溃了。那么客户端和新的leader会重试这条指令，导致这条指令被再次执行了。解决方法是客户端对每一条指令都赋予一个唯一的序列号，如果接收到相同的指令，我们就可以立即返回结果
只读的操作可以直接处理而不需要记录日志。但是在没有限制的情况下，我们可能读到过期的数据（一个old leader恢复以后接受到了新的客户端的读请求，他就会返回过期的数据）
为了解决这个问题，Raft使用额外的措施：leader必须有关于被提交的日志的最新信息，在leader任期开始的时候，他可能不知道那些是被提交的。他在他的任期里提交一条空白的日志条目来实现这一点。leader在处理只读的请求之前必须检查自己是否已经被废除了。Raft通过让leader在响应只读请求之前，先和集群中的大多数节点交换一次心跳信息来处理这个问题
文章评论