Raft算法概述
Raft算法是从多副本状态机的角度提出，用于管理多副本状态机的日志复制，它一致性分解为多个子问题：领导选举(Leader election)，日志复制(Log replication),安全性(Safety),日志压缩(Log compaction),成员变更(Menbership change)等。同时，Raft算法使用了更强的假设来减少需要考虑的状态，使之变得更加容易理解。
Raft讲系统中的角色分为领导者(Leader),跟从者(Follower)和候选人(Candidate)：
Leader: 接收客户端请求，并向Follower同步请求日志。当日志同步到大都数节点上后告告诉Follower提交日志。
Follower:接收并持久化Leader同步的日志，在Leader告诉它的日志提交之后，提交日志。
Candidate:Leader选举过程中的临时角色。
Raft要求系统在任意时刻最多只有一个Leader,正常工作期间Leader和Followers。
Raft算法角色状态转换如下:
Raft算法中服务器之间节点通信使用远程调用(RPCs).而在etcd的实现当中v2版本用的http，而v3版本采用的是grpc(本身是跨平台)。并且基本的一致性算法只是用了两种类型的Rpcs。请求投票(RequestVote)RPCs由候选人发起。然后附加条目数(AppendEntries)由Leader发起。用来复制日志和提供一种心跳机制。为了服务器之间传输快照增加了第三种RPCs。当服务器没有及时收到RPC的响应时，会进行重试，并且它们能够并行发起RPCs来获取最佳性能。
复制状态机
一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如，大规模的系统中通常都有一个集群领导者，像 GFS、HDFS 和 RAMCloud，典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。
复制状态机通常都是基于复制日志实现的，如图 1。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。
保证复制日志相同就是一致性算法的工作了。在一台服务器上，一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，尽管有些服务器会宕机。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成一个高可靠的状态机。
实际系统中使用的一致性算法通常含有以下特性：
安全性保证（绝对不会返回一个错误的结果）：在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
可用性：集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用。因此，一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
不依赖时序来保证一致性：物理时钟错误或者极端的消息延迟在可能只有在最坏情况下才会导致可用性问题。
通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。
Leader选举
Raft使用心跳(heartbeat)触发Leader选举。当服务器启动时，初始化Follower。Leader向所有的Followers周期性的发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机时间(150ms-300ms)发起一次选举。
Follower先要增加自己的当前任期号，也就把当前的任期号加一并且转换到候选人状态。然后它们会并行的向集群中的其他服务器节点发起请求投票的RPCs来给自己投票。结果会有以下三种情况:
- 它自己赢得了这次选举
- 其他的服务器成为了领导者
- 一段世家之后没有人获取胜利的人。
日志复制
Leader被选举出来后.它就开始为客户端提供服务，客户端每个请求都包含一条被复制状态机执行的命令。领导人将这条指令作为新的日志条目附加到日志中去。然后并行的发起附加条目RPCs给其他的服务器，让它们复制这个日志条目，当这条日志条目被安全的复制。领导人会应用这条日志条目到它的状态中然后把执行的结果返回客户端。如果Follower崩溃或者运行缓慢，再或者网络丢包，领导人会不断的尝试附加日志条目RPCs(尽管已经回复了客户端)直到所有Follower都最终存储了所有条目数。
日志由有序编号(log index)的日志组成条目。每个日志条目包含它被创建的任期号(term),和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上,就被认为可以提交了(commit)了。
Raft维护着一下特征:
1.如果在不同的日志中的两个条目拥有相同的索引和任期号,那么它们存储了相同的指令。
2.如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们的之前的所有日志条目也全部相同。
第一个特新来这样的一个事实,领导人最多在一个任期里在指定的日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。第二个特性由附加日志RPC的一个简单一致性检查保证。在发送附加日志RPC的时候，领导人会把新的日志条目紧接着之前的条目索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同的日志索引位置和任期号的条目,那么他就会拒绝接收新的条目日志。一致性检查就像一个归纳步骤:一开始空日志状态肯定是满足日志匹配特性的，然后一致性检查保护了日志匹配特性当日志扩展的时候。因此,每当附加日志RPC返回成功时，领导人就知道跟随着的日志时一样的了。
要使得跟随着的日志进入和自己一致的状态，领导人必须找到最后两者达成一致的地方，然后删除那个点之后的所有日志条目，发送自己的日志给跟随者。所有的这些日志操作都在进行附加日志RPCs的一致性检查时完成。领导人针对没一个维护者维护了一个nextIndex,这表示下一个发送给追随者的日志条目的索引地址。当一个领导人刚获得领导者的权利的时候，他初始化所有的nextIndex值作为自己的最后一条日志的index加1。如果一个跟随者的日志和领导人不一致，那么下一次日志附RPC时的一致性检查就会失败。在被跟随者拒绝之后，领导人就会减少nextIndex值并进行重试。最终nextIndex会在某个位置使得领导人和跟随者的日志达成一致。当这种情况发生，附加日志RPC就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志RPC成功，那么跟随者的日志就会和领导人保持一直，并且在接下来的任期里一直继续保持。
安全性
Raft增加了如下两条限制以保证安全性:
1>拥有最新的已提交的log entry的Follower才有资格成为Leader。
这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时。要带上自己的最后一条日志的term和log Index。其他节点收到消息时，如果发现自己的日志请求中携带的更新，则拒绝投票。日志比较的原则是:如果本地的最后一条log entry的term更大，则term大更新，如果term一样大，则log Index更大的更新。
2.Leader只能推进commit Index来提交当前term已经复制最到最大服务器上的日志，旧term日志的日志要等到提交当前的term的日志来间接提交(log Index 小于commit Index的日志被间接提交)
之所以要这样，是因为可能会出现已提交的日志被覆盖的情况:
时间和可用性
Raft的要求之一就是安全性不能依赖时间:整个系统不能因为某些事件运行的比预期快一点或者慢一点产生了错误的结果。但是，可用性(系统可以及时的响应客户端)不可避免的要依赖时间。例如，如果消息交换比服务器故障间隔时间长，候选人没有足够长的时间来赢得选举，没有一个稳定的领导人，Raft将无法工作。
领导人选举时Raft中对时间要求最为关键的方面。Raft可以选举并维持一个稳定的领导人，只需要满足下面的时间要求:
在这个不等式中，广播时间指的时从一个服务器并行的发送RPCs给集群中的其他服务器并接收平均时间，选举超时时间（150ms-300ms）选举超时时间限制，然后平均故障时间就是对于一台服务器而言，两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级，这样领导人才能发送稳定的心跳消息来阻止跟随者开始进入选举状态，通过随机化选举超时时间的方法，整个不等式也使得选票瓜分的情况变成不肯能。选举选举超时时间要比平局故障时间间隔小上几个数量级,这样系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于超时时的时间里不可用。我们希望这种情况在系统中国运行很少出现。
广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。
成员变更
成员变更是在集群运行过程中副本发生变化，如增加/减少副本数，节点替换等。
成员变更也是一个分布式一致性的问题，既所有服务器对成员新成员达成一致。但是成员变更又有其特殊性，因为成员变更的一致性达成的过程中，参与投票的过程会发生变化。
如果将成员变更当成一般的一致性问题，直接向Leader发送成员变更请求，Leader复制成员变更日志，达成多数之后提交，各个服务器提交成员变更日志后从日志成员(Cold)切换到最新成员配置(Cnew的时刻不同.
成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。
由于成员变更的这一特殊性，成员变更不能当成一般的一致性问题去解决。
为了解决这一问题.Raft提出了两段的成员变更方法。集群先成旧成员配置Cold切换到一个过度的配置，称为共同一致(joint consensus),共同一致时旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统在切换到新成员配置Cnew。
在关于重新配置还有三个问题需要提出,第一个问题是，新的服务器额能初始化没有存储任何的日志条目。当这些服务器以这种状态加入到集群中，那么它们需要一段时间来更新追赶。这时还不能提交新的日志条目。为了避免这种可用性的间隔时间Raft在配置更新的时候用了一种额外的阶段，在这种阶段，新的服务器以没有投票权的身份加入集群中来(领导人复制日志给它们。但是不考虑它们是大多数)。一旦新的服务器追赶上了集群中的集群，重新配置可以向上面描述一样处理。
第二个问题，集群的领导人可能不是新配置的一员。在这种情况下，领导人就会在提交了C-new日志后退位(回到追随者状态)。这意味着有这样一段时间，领导人管理着集群，但是不包括他自己，他复制日志但是不把他自己算作大多数之一。当C-new被提交时，会发生领导人过度。因为这时时最新的配置可以独立工作时间点(将总是能够在C-new配置下选出新的Leader)。再此之前，可能只从C-old中选出领导人。
第三个问题是:移除不再C-new中的服务器可能会扰乱集群。这些服务器将不会再接收心跳。当选举超时时，它们就会进行新的选举过程。它们会发送拥有新的任期号的请求投票RPCs，这样会导致当前的领导人退回成跟随者状态。新的领导人最终被选出来，但是被移除的服务器将会再次超时，然后这种过程再次重复，导致整体可用性大幅度下降。
为了避免这个问题，当服务器确认当前领导人存在时，服务器会忽略投票RPCs。特别的，当服务器再当前最小选举超时时间内收到一个请求投票的RPC。他不会更新当前的任期号和投票号。这不会影响正常的选举，每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。然后这有利于避免被移除的服务器的扰乱。如果领导人能够发送心跳给集群，那么他就不会更大的任期号废黜。
日志压缩
在实际系统中，不能让日志无限增长，否则系统重启时需要花很长的时间回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以抛弃。
每个副本独立的对自己系统状态进行snapshot，并且只能对已经提交的日志进行snapshot。
Snapshot中包含以下内容:
1>日志元数据:最后提交的log entry的log index和term。这两个值在snapshot之后的第一条log entry的AppendEntriesRPC的完整性检查的时候会被用上。
2> 系统当前状态。
当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者新加入一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。
做snapshot不要做的太频繁，否则消耗磁盘带宽，也不要做的太平凡，否则一点节点重启要回放大量日志，影响可用性。推荐当日组织达到某个固定的大小做一次snapshot。
做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常的日志同步过程。
参考：
http://thesecretlivesofdata.com/raft/(Raft动画)
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md(Raft论文翻译)