Raft
Intro
共识算法让一组共同协作的计算机在其中一部分失效后也能继续工作下去，因此共识算法被应用于大规模的可靠软件系统中。在之前该领域使用的大都是Paxos，或者是在Paxos的影响之下设计出来的，但是Paxos较为难理解，因而更难实现，因而有人提出了Raft。正如其论文标题
接下来先简要介绍一下这个共识算法，该算法的主要流程可以分为两个部分，第一个部分就是领导人的选举，第二部分就是让leader负责接受用户请求并将自己的日志发送给所有的follower，让follower的日志与自己保持一致，同时当某个日志已经被复制到大多数机器上时，leader会负责通知所有follower。
Leader Election
Raft中共有三种角色，分别是leader、candidate和follower。其中leader负责处理用户请求，与所有follower进行通信从而完成共识；candidate状态用于选举出新的leader；follower仅处理来自leader和candidate的请求，并不会主动与其他节点通信。
说完Raft种的三种角色，我们可以看一看Raft的Leader的选举的过程了。Raft在每个follower和candidate节点都会维护一个计时器，当一段时间没有收到来自leader的消息后就会认为这个leader挂了，需要重新选举出leader。但是由于网络分裂的存在，可能之前的leader并没挂，只是网络出现问题，而网络问题修复后就会出现同一时间出现多个leader的问题。为了解决这个问题，Raft将时间分割为多个term，每个任期会有一个递增的任期号，每个任期的开始时都会有一次新的leader的选举。一个节点如果希望成为该term的Leader，会需要大多数节点的投票，因此这也就保证了在同一Term中最多只会有一个Leader。每个被选举出的Leader负责在该任期中所有的客户请求。每个节点还会保留一个本地的任期号，任何节点在交换信息时也都会带上该任期号，一个节点如果收到的消息带有一个较大的任期号时会更新本地任期号，如果收到的消息带有一个较小的任期号时则会直接拒绝该消息。
Raft的每个节点的初始角色都是follower，如果该节点能够收到当前term的leader的心跳信息则已知维持在follower状态，如果间隔一段时间没有收到Leader的消息则开始选举，该节点会首先从follower状态转换成candidate状态，然后广播投票请求。那么该次尝试选举可能有三种结果，第一种是发现了一个更新的Leader，这种情况下该节点会直接转换为follower，然后接受leader的请求；第二种是收到了大多数节点的投票，此时该节点成为新的Leader，并周期性的广播心跳消息来同时其他节点；第三种是计时器超时，该candidate仍然没有收到足够的投票，此时该节点会重新增加term号开始新的选举，这一机制是为了防止多个节点同时开始选举，导致没有任何一个节点能够得到足够多的投票的情况。为了保证一个term最多仅有一个节点被选举出来，因此每个节点针对一个term最多仅能投一票。需要注意的是一个节点在收到任何一种消息时，如果term号比本地保留的term小则拒绝消息，如果比本地的大则会先更新节点的状态，因此每个节点最终处理的消息中所带有的任期号都与本地的任期号相同。为了防止在leader失效的情况下多个节点可能同时开始新的选举，然后导致没有任何一个节点获得大多数投票的情况频繁发生，每个节点会在一定范围内随机设置超时长度。
Log Replication
当一个节点被选举成为leader后，该节点会负责该term里所有的客户端的请求的处理，这个leader会首先将客户端的请求添加到自己的日志中，之后利用AppendEntries来想其他节点复制该日志，当某条日志已经被安全的复制后，leader会将该日志对应的命令应用到状态机中，并将执行结果返回给客户端。leader会尽可能的让所有节点都拥有与自己相同的日志。Raft将可以应用到状态机的日志条目称为committed，并保证所有committed的日志条目最终会被所有的状态机执行。当创建一个日志的leader将该日志条目复制到大多数的follower上后，该日志条目就认为是committed的，同时还会commit该日志条目之前的所有日志条目。leader会将已知的commit的最高的日志序号包含在所有AppendEntries消息中，来让follower能够知道哪些条目已经提交，然后应用到本地的状态机中。
Raft维护了一系列性质，其中一条就是日志匹配性质，该性质维护了不同节点之间日志的关系，剩余性质会在下一节进行介绍。raft中的日志匹配性质包括两条，第一条是如果两个节点的日志中的两个条目有相同的序号和任期号则这两个条目有着相同的内容；第二条是如果两个节点的日志中某两个条目有着相同的序号和任期号则这两个条目之前的所有日志条目都有着相同的内容。第一个性质来源于每个term仅有最多一个leader，而一个leader仅会在一个位置设置一个条目，因此两个日志如果任期号与序号都相同则内容一定相同。而第二个性质与AppendEntries的实际流程有关，Leader的AppendEntries请求中会包含一系列的日志以及在这些日志之前的一个条目的序号与任期号，当一个follower收到leader的AppendEntries请求时会对之前一个条目的任期号与序号进行匹配，仅当这个日志条目的序号和任期号与AppendEntries参数中的相同时才会将这些条目添加到自己的日志中，否则会删除该点及之后的所有日志条目。因此利用性质1与follower在AppendEntries时进行的一致性检验可以保证性质2。
那么我们来看一看为什么每个leader仅能commit自己创建的日志，而不能直接commit之前term的日志。下图来自于论文中的Figure8，该图中首先S1成为了term2的leader，然后在复制了自己的日志到一小部分节点后崩溃，之后S5成为了term3的leader，并在2号位置创建了新的条目，随后S5崩溃，S1成为term4的leader，并开始将复制日志，其中term2的日志被复制到大多数节点，但假设此时直接commit该日志，随后S1崩溃、S5重启，其当选为新的Leader，由于该leader仅有已commit的所有条目，因此此时S5并没有S1在term2创建的条目，因此S5可能覆盖掉已commit的日志，这直接违反了raft需要维护的性质。而如果之间term的日志条目仅能由间接提交，此时如(e)，新选举出的leader必需包含term4的日志，因而必须包含term2的日志，因此不会被之后选举出的leader覆写。简而言之，之所以不能直接commit之前term的日志，是因为由于新选举出的leader可能并不包含之前term的日志，因此可能覆写这些日志，而利用间接commit可以保证新选举出的leader一定包含之前的所有日志，因而不会覆盖这些日志。
Safety
除了日志匹配属性，raft维护了一系列的性质，本节会逐一介绍这些性质并介绍这些性质是如何被满足的。
选举安全性
每个任期最多仅有一个节点被选举为leader。通过限制每个节点在每个任期仅能为一个节点投票，同时一个节点如果需要成为这个任期的leader需要大多数节点的投票，因此每个任期最多仅有一个leader。
Leader仅添加日志
Leader仅会向其日志中添加条目，而不会删除或修改已有条目。
Leader完整性
如果一个日志条目在term i被提交，那么这个日志条目会出现在所有term高于i的leader中。这一性质来自于一个candidate如果希望成为leader需要得到大多数节点的投票，因此该candidate的日志比大多数节点都新，同时由于该日志条目已经commit，因此会出现在大多数节点中，因此leader一定会包含该日志条目。
状态机安全性
如果一个服务器在一个序号处应用了一条指令，那么所有状态机在该序号处都会应用同样的指令。该性质可由Leader完整性得来。
日志压缩
raft可以使用快照来消减日志所占的存储空间，通过记录状态机的状态，从而可以安全的删除在进行快照时已经被应用的日志。每个节点会独立的进行快照，但leader可能将自己的快照发送给落后较多的节点来更新其状态。
成员变更
Raft支持成员的动态变更，最简单的成员变更方法是将整个集群下线，然后更新其配置文件，在重新启动该集群，但这需要手动操作，因此带来了很多的不可控因素。Raft利用Joint Consensus来支持成员的动态变更，其保证在任何时间，对同一个Term最多仅有一个Leader。
Raft为进行配置变更，会首先进入Joint Consensus状态，在该状态中：
- 日志条目会复制到旧配置所指定的成员以及新配置所指定的成员中
- 日志条目需要复制到新配置指定的成员中：需要将已有的日志条目复制到新的成员中
- 日志条目需要复制到旧配置指定的成员中：
- 任何一个配置的成员都能称为Leader
- 任何共识需要得到旧配置的大多数成员以及新配置的大多数成员的同意
当Leader收到配置变更请求后会生成一个新的配置C<old,new>并利用Raft将该日志条目复制到集群中。当一个Follower发现C<old,new>后，其也会利用该配置进行进一步的共识(用于Leader Election)，此时由于Leader 处于Joint Consensus状态，因此其也会将该日志条目复制给新配置所指定的集群成员，因而保证如果该日志条目被Commit，则新配置所指定的大多数成员拥有所有已有的日志。当C<old,new>被Commit后，标识新配置所指定的大多数成员都已经拥有了所有的日志，旧配置所指定的大多数成员也拥有该配置变更信息。此时由于Leader election选举出的节点必定有该日志条目，因此此时旧配置所指定的成员以及新配置的成员都不能单独进行共识，必须另一个配置所指定的成员的允许，此时Leader开始共识C
我对需要进行第二阶段共识的理解是，由于第一阶段进行C<old,new>的共识过程中可能有其他的用户请求，这些请求可能并没有被完全复制到新的配置所指定的成员中，而C<old,new>的Commit仅能保证该日志之前的所有条目被复制到新的集群中，而之间所有的请求可能仅复制到了一小部分新配置所指定的成员，而此时如果直接在C<old,new>Commit时直接让旧配置所指定的成员停止消息响应则可能丢失很多用户的请求，因此需要开始一个新条目的共识来保证之前的所有的日志条目被复制到新配置所指定的成员中。
但目前我有一个问题，能否在C<old,new>Commit后让旧配置存在的节点停止响应消息，而新配置的成员将仅使用新配置指定的成员进行共识，从而避免为C
总结
该篇博客仅对raft的一些基础性质和原理进行介绍，具体执行流程可以参见论文，raft的配置变更也没有进行介绍，希望能够给正在了解raft的人提供一些帮助。