一、 Raft简介
1.1 Raft简介
Raft 是一种为了管理日志复制的分布式一致性算法。Raft 出现之前，Paxos 一直是分布式一致性算法的标准。Paxos 难以理解，更难以实现。Raft 的设计目标是简化 Paxos，使得算法既容易理解，也容易实现。
Paxos 和 Raft 都是分布式一致性算法，这个过程如同投票选举领袖（Leader），参选者（Candidate）需要说服大多数投票者（Follower）投票给他，一旦选举出领袖，就由领袖发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。
Raft 可以解决分布式 CAP 理论中的 CP，即 一致性（C：Consistency） 和 分区容忍性（P：Partition Tolerance），并不能解决 可用性（A：Availability） 的问题。
1.2 分布一致性
分布式一致性 (distributed consensus) 是分布式系统中最基本的问题，用来保证一个分布式系统的可靠性以及容错能力。简单来说，分布式一致性是指多个服务器的保持状态一致。
在分布式系统中，可能出现各种意外（断电、网络拥塞、CPU/内存耗尽等等），使得服务器宕机或无法访问，最终导致无法和其他服务器保持状态一致。为了应对这种情况，就需要有一种一致性协议来进行容错，使得分布式系统中即使有部分服务器宕机或无法访问，整体依然可以对外提供服务。
以容错方式达成一致，自然不能要求所有服务器都达成一致状态，只要超过半数以上的服务器达成一致就可以了。假设有 N 台服务器， 大于等于 N / 2 + 1 台服务器就算是半数以上了 。
1.3 复制状态机
复制状态机（Replicated State Machines） 是指一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的。
复制状态机通常都是基于复制日志实现的，如上图。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。
保证复制日志相同就是一致性算法的工作了。在一台服务器上，一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，尽管有些服务器会宕机。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成一个高可靠的状态机。
实际系统中使用的一致性算法通常含有以下特性：
安全性保证 （绝对不会返回一个错误的结果）：在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。 可用性：集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用。因此，一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。 不依赖时序来保证一致性：物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。 通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。
1.4 RAFT应用
通过 RAFT 提供的复制状态机，可以解决分布式系统的复制、修复、节点管理等问题。Raft 极大的简化当前分布式系统的设计与实现，让开发者只关注于业务逻辑，将其抽象实现成对应的状态机即可。基于这套框架，可以构建很多分布式应用：
分布式锁服务，比如 Zookeeper 分布式存储系统，比如分布式消息队列、分布式块系统、分布式文件系统、分布式表格系统等，比如大名鼎鼎的 Redis 就是基于 Raft 实现分布式一致性 高可靠元信息管理，比如各类 Master 模块的 HA
二、 Raft基础
Raft 将一致性问题分解成了三个子问题：选举 Leader、日志复制、安全性。
在后续章节，会详细讲解这个子问题。现在，先了解一下 Raft 的一些核心概念。
2.1 服务器角色
在 Raft 中，任何时刻，每个服务器都处于这三个角色之一 ：
Leader - 领导者，通常一个系统中是一 主（Leader）多从（Follower） 。 Leader 负责处理所有的客户端请求。 Follower - 跟随者，不会发送任何请求，只是简单的 响应来自 Leader 或者 Candidate 的请求。 Candidate - 参选者，选举新 Leader 时的临时角色。
图示说明：
- Follower 只响应来自其他服务器的请求。在一定时限内，如果 Follower 接收不到消息，就会转变成 Candidate，并发起选举。
- Candidate 向 Follower 发起投票请求，如果获得集群中半数以上的选票，就会转变为 Leader。
- 在一个 Term 内，Leader 始终保持不变，直到下线了。Leader 需要周期性向所有 Follower 发送心跳消息，以阻止 Follower 转变为 Candidate。
2.2 任期
Raft 把时间分割成任意长度的 任期（Term），任期用连续的整数标记。每一段任期从一次选举开始。Raft 保证了在一个给定的任期内，最多只有一个领导者。
如果选举成功，Leader 会管理整个集群直到任期结束。 如果选举失败，那么这个任期就会因为没有 Leader 而结束。
不同服务器节点观察到的任期转换状态可能不一样：
服务器节点可能观察到多次的任期转换。 服务器节点也可能观察不到任何一次任期转换。
任期在 Raft 算法中充当逻辑时钟的作用，使得服务器节点可以查明一些过期的信息（比如过期的 Leader）。每个服务器节点都会存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号。
如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。 如果一个 Candidate 或者 Leader 发现自己的任期号过期了，那么他会立即恢复成跟随者状态。 如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。
数据可视化的应用场景越来越广泛，数据可以呈现为更多丰富的可视化形式，使用户能够更加轻易、便捷的获取并理解数据传达的信息。
2.3 RPC
Raft 算法中服务器节点之间的通信使用 远程过程调用（RPC）。基本的一致性算法只需要两种 RPC：
RequestVote RPC - 请求投票 RPC，由 Candidate 在选举期间发起。 AppendEntries RPC - 附加条目 RPC，由 Leader 发起，用来复制日志和提供一种心跳机制。
三、选举Leader
3.1 选举规则
Raft 使用一种心跳机制来触发 Leader 选举。Leader 需要周期性的向所有 Follower 发送心跳消息，以此维持自己的权威并阻止新 Leader 的产生。
每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms ~ 300ms，如果在竞选超时时间内没有收到 Leader 的心跳消息，就会认为当前 Term 没有可用的 Leader，并发起选举来选出新的 Leader。开始一次选举过程，Follower 先要增加自己的当前 Term 号，并转换为 Candidate。
Candidate 会并行的向集群中的所有服务器节点发送投票请求（RequestVote RPC），它会保持当前状态直到以下三件事情之一发生：
自己成为 Leader其他的服务器成为 Leader
没有任何服务器成为 Leader
3.1.1自己成为 Leader
当一个 Candidate 从整个集群半数以上的服务器节点获得了针对同一个 Term 的选票，那么它就赢得了这次选举并成为 Leader。每个服务器最多会对一个 Term 投出一张选票，按照先来先服务（FIFO）的原则。要求半数以上选票的规则确保了最多只会有一个 Candidate 赢得此次选举。 一旦 Candidate 赢得选举，就立即成为 Leader。然后它会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。
3.1.2 其他的服务器成为 Leader
等待投票期间，Candidate 可能会从其他的服务器接收到声明它是 Leader 的 AppendEntries RPC。
如果这个 Leader 的 Term 号（包含在此次的 RPC 中）不小于 Candidate 当前的 Term，那么 Candidate 会承认 Leader 合法并回到 Follower 状态。 如果此次 RPC 中的 Term 号比自己小，那么 Candidate 就会拒绝这个消息并继续保持 Candidate 状态。
3.1.3 没有任何服务器成为 Leader
如果有多个 Follower 同时成为 Candidate，那么选票可能会被瓜分以至于没有 Candidate 可以赢得半数以上的投票。当这种情况发生的时候，每一个 Candidate 都会竞选超时，然后通过增加当前 Term 号来开始一轮新的选举。然而，没有其他机制的话，选票可能会被无限的重复瓜分。
Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。为了阻止选票起初就被瓜分，竞选超时时间是一个随机的时间，在一个固定的区间（例如 150-300 毫秒）随机选择，这样可以把选举都分散开。
以至于在大多数情况下，只有一个服务器会超时，然后它赢得选举，成为 Leader，并在其他服务器超时之前发送心跳包。
同样的机制也被用在选票瓜分的情况下：每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。
理解了上面的选举规则后，我们通过动图来加深认识。
3.2 单Candidate选举
1) 下图表示一个分布式系统的最初阶段，此时只有 Follower，没有 Leader。Follower A 等待一个随机的选举超时时间之后，没收到 Leader 发来的心跳消息。因此，将 Term 由 0 增加为 1，转换为 Candidate，进入选举状态。
2)此时，A 向所有其他节点发送投票请求。
3) 其它节点会对投票请求进行回复，如果超过半数以上的节点投票了，那么该 Candidate 就会立即变成 Term 为 1 的 Leader。
4) Leader 会周期性地发送心跳消息给所有 Follower，Follower 接收到心跳包，会重新开始计时。
3.3 多 Candidate 选举
1) 1如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票。例如下图中 Candidate B 和 Candidate D 都发起 Term 为 4 的选举，且都获得两票，因此需要重新开始投票。
2) 当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低。
