当了解的区块链的时候，经常会听到这样一种说法，比特币中并没有什么突破性的技术，只是把现有技术巧妙的组合，事实也确实是这样，而其中如何保持大量节点达成一致就大量的采用了分布式系统设计的思想。
针对区块链的应用场景不同，又将区块链分为公链和联盟链，因为公链对加入者没有任何要求，所以有各种各样的计算设备加入，同时也为了足够的去中心化，公链一般都有大量的节点，比如比特币和以太坊都有近万个全节点参与共识，这些节点中有好有坏，但影响不大，只要好的节点算力占多数就没有关系， 而联盟链则在去中心化和效率之间做了权衡，通过提高节点加入网络的门槛来限制坏节点的加入，同时也限制了节点数量，比如一些采用pbft共识算法的联盟链节点一般都只有10个左右，容忍的坏节点数量也降到了大约三分之一。
不同场景的取舍不同，为了节点间达成一致采用了不同的共识算法，比如比特币通过挖矿来达成一致，NEO采用PBFT算法达成一致，甚至像超级账本采用raft来保证一致性。
比特币采用的挖矿算法需要消耗大量的计算能力来保证区块链的安全性，消耗的算力越强也就越安全，同时比特币也对加入的节点没有任何要求，甚至可以是作恶的人，但是在联盟链场景，如果采用这种算法，不但要消耗大量的电力来保证安全，还要忍受算法性能差的后果，但是联盟链又不需要那么多的节点，所以可以采用PBFT算法，既可以容忍少量的作恶又可以保证系统的性能。fabric在这个基础上更近一步，直接对加入网络的节点进行准入，获得准入的节点才能加入网络，这样一来准入的节点都是值得信赖的，所以连容错都不需要了，直接采用了raft算法，性能更近一步。
通过不同的算法保证了在不同场景下区块链节点的共识，共识的内容又是什么呢？答案就是交易，数字信息非常容易复制，在区块链系统中，需要保证大部分节点看到的交易都是一致的，这就好比一个银行账户需要在银行的不同网点看到的余额必须一致。
Raft算法解决的核心问题是在分布式环境下如何保持集群状态的一致性，简而言之就是一组服务，给定一组操作，最后得到一致的结果。
Raft算法的基本流程为：首先在集群中选择一个领导者负责日志的管理。领导者从客户端收到请求后会以日志的形式复制到其他跟随者，并且在保证安全的时候通知其它跟随者执行日志中包含的请求将状态应用到各自的状态机中。Raft算法强化了领导者的地位，数据只会从领导者流向其它跟随者从而极大的简化了算法的复杂性。当领导者因为故障宕机之后其它节点会从集群中重新选举新的领导者，重复之前的过程。在这个过程中，算法被拆分成了三个独立的子问题，即领导人选举、日志复制和异常处理。
Raft算法中一个节点在任意时刻只能处在领导人（leader），候选人（candidate），跟随者（follower）其中一个状态，初始化的时候所有的节点都处于跟随者的状态，跟随者之间通过心跳信息来感知其它节点。
通常情况下，系统中只有一个领导人并且其他节点全部都是跟随者，跟随者都是被动的，他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。
下面是三个状态的状态转换图；
节点启动的时候，都是跟随者状态，在一段时间没有收到来自领导者的心跳，就从跟随者转变为候选人，发起选举；如果收到含自己的多数选票则转换到领导者；如果发现其他节点比自己更新，则切换到跟随者状态。为了确定其他节点比自己更新，Raft又引入了任期（term）的概念。
算法起始，任期是0，当有节点当选领导者时，任期号为1，新领导人选出后，任期在之前的任期号加1。当节点从跟随者转化为候选人的时候，任期号也要增加1。在节点间通信的时候会交换当前任期号，如果该节点的任期号比其它几点小，该节点会把自己的任期号更新为较大的那个值。如果一个候选人或者领导者发现自己的任期号过期了，也就是比其它节点小，它会立刻退回到跟随者状态。如果一个节点收到的过期的任期号则会直接拒绝不做处理。
任期起到逻辑时钟的作用
Raft使用心跳机制来触发领导选举流程，领导者周期性的向所有所有跟随者发送心跳信息，每个节点只要能收到领导者或者候选人发来的心跳信息就一直保持跟随者状态。每个节点本身都会有自己的选举超时时间，如果超过这个超时时间没有收到任何消息那么它就会假设网络中没有领导者。这个时候它就会改变自己的状态为候选人，同时增加自己的任期号竞选领导人。在竞选时会首先给自己投一票，然后并行的向集群中的其它节点发送请求投票的消息。如果其它节点在这轮选举中没有投过票就会给他投一票。最终得到三种结果，成功，失败或者是无法确定领导者。具体转换过程如状态转换图所示。
如果将整个过程简单归纳成如下几步：
- 增加自己当前的
任期，转换状态到``候选人`； - 投自己一票，并且给其他节点发送请求给自己投票的请求；
- 等待其他节点回复，在等待过程中又可能发生下面的情况
- 赢得选举，成为领导者；
- 被告知其他节点当选领导者，自己退回跟随者状态；
- 超时时间没有收到足够多的选票，则重复整个选举过程；
下面的这个gif就展示了这个过程；
最后如果没有任何领导人获得超过半数选票，那么这次选举过程就会失败，但是如果一次失败可能是偶然的，但是连续多次失败如果除去系统本身的原因那么就是算法本身到达了某种不可恢复的状态。为了跳出每次都会到达这样一种不可用的状态，Raft算法使用随机选举超时时间的方法来解决：候选人会随机从固定时间区块选择一个时间作为选举超时时间，这样每个节点每次等待选举的超时时间都不一致，超时时间短的节点会有更大的机会获得更多的选票从而成为领导者。这样会极大避免因为选票被瓜分而导致选举失败的可能性。
当选出了领导人系统就可以对外提供服务，客户端把请求发送给集群，如果是跟随者收到则转发给领导者，由领导者统一处理，领导人会调度这些请求，顺序告知所有跟随者，保证所有节点的状态一致。Raft是基于复制状态机实现的，其核心思想就是相同的初始状态 + 相同的输入 = 一致的最终状态，领导者将客户端请求打包到一个个log entry，将这些log entries发送到所有跟随者节点，然后大家按相同顺序应用log entry中的命令，则状态肯定是一致的。
- 领导者接收请求打包到
log entry； - 领导者并行发送
log entry到集群所有节点； - 领导者收到大多数跟随者收到
log entry的回复； - 领导者应用
log entry里面的命令到自己的状态机中，也就是执行命令； - 领导者回复跟随者，并且让他们也执行
log entry中命令，达到和自己一致的状态机；
每个log entry中，除了需要执行的命令之外还有领导者节点的任期号，用于处理异常情况；同时我们也可以看到，当日志被复制到大多数节点，即可向客户端返回成功的消息，一旦返回了结果，就必须保证系统在任何异常情况都不会发送回滚。
Raft通过第一个阶段的commited和第二个阶段的apply，保证了状态机的一致性。
前文描述了Raft在正常情况下的算法流程，但当节点崩溃的情况下会有一些异常，影响状态机顺序的执行相同的指令。
领导人选举安全性（Election safety），即在一个任期内最多一个领导人被选出，如果有多余的领导人被选出，则被称为脑裂（brain split），如果出现脑裂会导致数据的丢失或者覆盖。Raft通过下面两点保证了不会出现脑裂的情况；
- 一个节点某一任期内最多只能投一票；
- 只有获得大多数选票才能成为领导人；
通过增加约束避免了脑裂的情况出现，保证了同一时间集群中只有一个领导者。但是当一个节点崩溃了一段时间，他的状态机已经落后其他节点很多，突然他重启恢复被选举为领导者，这个时候，客户端发来的请求再经由他复制给其他节点的状态机执行，就会出现集群状态机状态不一致的问题。
其他算法可能会同步落后的日志给领导者，然后在由领导者复制日志给其他节点，但是Raft认为这样会增加算法的复杂性，直接放弃了这种方法，而是采用拒绝投票给那些日志没有自己新的节点。
通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更新。如果两份日志最后的条目任期号相同，那么日志比索引大的日志新。
拒绝日志比自己旧节点投票是基于这样一种思考，要当选领导者，就必须获得大多数节点的选票，意味着他必须至少比大多数节点的日志新或者一致，这样拒绝比自己旧日志节点的投票请求，就保证了状态比大多数节点落后的节点是不会当选领导者。
如果一个领导者把日志复制到大多数其他节点，在应用到状态机之前崩溃了，新选出的领导者是不知道被复制到大多数节点的日志是否应用到了状态机的。
(a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目；
(b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处；
(c)中，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交；
(d) 中，S1又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。注意：虽然s2复制日志过半，但是S5节点的任期号大，日志新，是可以接收S2选票；反之S1在崩溃前把新接收到的日志复制到大多数机器中，如(e)所示的情况。
(e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。
候选者，跟随者奔溃以后，领导者就是简单的周期性的发送RPC请求，如果重启发生在节点处理完日志复制，响RPC请求之前，收到一样的RPC请求正常返回即可，没有任何问题。如果崩溃时间太长，重启以后落后其他节点日志太多，将会采取快照的方式进行恢复。
Raft的RPC请求是幂等的。
Raft的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。这个时候就又会有一些限制；
- 服务器故障的时间必须比消息交换的时间长，否则每当一个节点要收集到足够多选票的时候就宕机了，新一轮的投票又重复这个过程，导致没有足够的时间选出领导人。
- 广播的时间必须小于选举超时时间一个数量级，这样领导者才能发送稳定的心跳阻止跟随者进入候选人状态。
- 当领导者崩溃后，整个系统在大约等于选举超时时间中不可用，所以平均故障间隔时间要大于选举超时时间几个数量级，系统可用性才比较高。
一般来说，广播时间在10毫秒左右，选举超时时间在300毫秒左右，服务器平均故障时间都大于一个月。
前文已经介绍了Raft算法的正常流程和对异常的处理，但是还有一些问题没有解决，由于硬件故障、集群负载发生了变化等，需要集群中的节点动态的增加或者删除。最容易想到的方法就是暂停整个集群，更新配置，然后重启集群。但是问题显而易见，在更新配置期间集群是不可用的，而手工操作配置文件，而且是操作多个节点的配置文件，也会造成很大的风险。为了避免发生这些风险，Raft算法添加了自动化配置变更的内容。
从旧的配置直接变更到新的配置的各种方法都是不安全的，其中最大的问题就是容易出现脑裂集群分裂，举个例子；
旧配置有 1， 2， 3号节点，候选人只需要两张选票就可以变为领导者，除了自己的一张选票，还需要等待一个节点投票给自己即可，但是当集群增加2个节点的时候，旧节点之间是无法感知有几个节点加入网络的，所以还会按照旧配置投票，即收集到两张选票就可以成为候选人。而新节点是可以感知到集群中是有5个节点的，所以新节点要成为领导者需要3张选票，必然有一个时间点，既可满足旧节点的候选人选举要求，又可满足新节点的选举要求，脑裂就这样发生了。
显而易见，出现脑裂的问题是由于同一时间新旧配置节点各自单方面的作出了选领导者的决定。
停集群，更新配置，重启集群其实目的就是保证了同一时间只有一种状态，为了解决集群的可用性，Raft采取了两段提交来保证安全的变更日志。
首先当一个领导者收到一个改变配置从C-old到C-new的请求时，它会merge(C-old, C-new)并且保存到自己的日志中，然后复制到集群中的其他节点，在C-new提交之前，所有节点的决定都会基于C-old,new的配置做决定。
在C-old, new被提交以后，领导者创建一条C-new的配置复制到集群，当C-new被提交以后，就旧配置指定的节点就无关紧要了，在集群中不可见了，可以从集群移除。
节点宕机
但是在这个过程中还是会有节点宕机的异常情况发生，Raft又是如何保证整个增删节点过程的安全性呢？
如果领导者在复制包含配置文件的日志时候崩溃了，跟随者节点只有两种配置状态，C-old,new或者C-old，但是无论哪种状态，C-new都不会单方面做出决定。
空白节点加入
当一个新的服务器加入集群，新服务器本身是没有存储任何日志，是无法提交集群中的任何一条日志的，需要一段时间来追赶，Raft为了避免这种可用性的时间间隔太长，采取了节点静默加入集群，但是没有投票权，只是同步日志，当新节点已经可以跟上集群日志的时候再投票加入集群。
旧节点干扰
当C-new被提交以后，就需要移除不在C-new中的节点。在C-new被提交后，需要移除的节点就接收不到领导者的心跳消息，这个时候这些节点认为领导者可能出现了故障，会发起选举，正常执行的领导者收到投票请求后会退回到跟随者状态等待新领导者被选出，虽然最终正确的领导者会被选出，但是频繁的选举流程会扰乱集群的可用性。
为了避免这个问题，Raft采用了最小选举超时时间的机制，当服务器在当前最小选举超时时间内收到一个请求投票 RPC，他不会更新当前的任期号或者投出选票，这样就避免了频繁的状态切换。
领导者不在新集群中
还有一种可能是领导者不在新集群中，当配置文件从C-old,new变更到C-new时，领导者不在C-new中，这个时候就会在一段时间内发生旧节点管理新集群的情况。
Raft中解决方法很简单，当提交C-new成功的时候，自己的状态变为跟随者，这样领导者节点就只能在新集群中选出。
Raft算法在运行的过程中，日志是不断累积的，但是在实际的系统中，无论是从日志占用的磁盘空间，还是新节点加入集群，同步日志的网络消耗来看，日志都不能无限的增长。
Raft采用快照的方法来压缩日志，快照时间点前的日志全部丢弃。
每个服务器根据已经提交的日志，独立创建快照，快照中包含；
- 状态机最后应用的日志；
- 状态机最后应用日志的任期号；
- 状态机最后应用的配置文件内容；
领导者周期性的发送一些快照给跟随者，与领导者保持同步的节点已经提交了快照的内容，会直接丢弃，而运行缓慢或者新加入集群的服务器则不会有这个条目，就会接受并且应用的自己的状态机中。