Raft
简介
CAP模型指出分布式系统不能同时满足分区容忍性，可用性，一致性这三个特性，而最多只能满足其中的两个特性。
一致性是指分布式系统在跨节点场景下数据达成一致性的过程，一致性可以分为线性一致性，顺序一致性等
Raft是一种一致性算法，也称为共识算法。但相比于Paxos而言，Raft的工程实现更加简单，容易理解。
Paxos是无主的共识算法，无主算法对容灾的处理更加复杂，而且因为每个节点都可以发起请求，所以需要复杂的机制从并发的请求中选择一个作为选中的值写入集群。
Raft的角色除了Paxos中的Candidate和Follow之外，还有Leader角色。
| 名称 | 职责 |
|---|---|
| Leader | 处理客户端请求，并将请求同步给Follow，当超过一半的节点回复Leader同步成功，Leader则提交日志。 |
| Follow | 接受并持久化来自Leader的日志，并接受Leader的指令进行数据提交。 |
| Candidate | 竞选Leader过程中的临时角色。 |
在运行过程中，Raft只允许Leader节点提交数据，所以Raft第一个步骤是Leader的选举。在Leader宕机的时候会重新进行Leader选举。
有了Leader之后，Leader会提交数据，进行日志同步。
除了Leader之外，集群中其他成员的变更也需要处理。
原理
Raft将共识算法分为几个环节，Leader的选举，日志同步，日志压缩，成员变更等。
Leader选举
raft算法把时间轴分为不同的任期（term），每个Term拥有唯一的ID，termId，该ID全局唯一单调递增。如果选举成功，则进入维持任务term阶段，此时leader负责接收客户端请求并负责复制日志，同时Leader和所有的follower都保持通信，如果follower发现通信超时，TermId递增并发起新的选举。如果选举成功，则进入新的任期。如果选举失败，termId递增，然后重新发起选举直到成功。
Leader在任期内会向其他follower节点发送心跳来维持地位，follower如果发现心跳超时，就认为leader节点宕机或者不存在。随机等待一段时间之后，follower会发起选举，变成candidate，然后竞选leader。选举结果有两种情况：
- 获取超过半数投票，赢得选举
- 投票未超过半数，选举失败
当candidate收到其他Leader的结果通知，candidate通过任期termId判断是否处理，如果请求的任期termId不小于candidate当前任期的termId，那么candidate会承认该Leader的合法地位，并转化为follower。
日志复制
选举 leader 成功后，整个集群就可以正常对外提供服务了。Leader 接收所有客户端请求，然后转化为 log 复制命令，发送通知其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令，任期号表示 leader 的当前任期。
follower 收到日志复制请求的处理流程：
- follower 会使用前一个日志的任期号和日志索引来对比自己的数据：
- 如果相同，接收复制请求，回复 ok；
- 否则回拒绝复制当前日志，回复 error；
- leader 收到拒绝复制的回复后，继续发送节点日志复制请求，不过这次会带上更前面的一个日志任期号和索引；
- 如此循环往复，直到找到一个共同的任期号&日志索引。此时 follower 从这个索引值开始复制，最终和 leader 节点日志保持一致；
- 日志复制过程中，Leader 会无限重试直到成功。如果超过半数的节点复制日志成功，就可以任务当前数据请求达成了共识，即日志可以 commite 提交了；
综上， Log Replication 日志复制有两个特点：
- 如果在不同日志中的两个条目有着相同索引和任期号，则所存储的命令是相同的，这点是由 leader 来保证的；
- 如果在不同日志中的两个条目有着相同索引和任期号，则它们之间所有条目完全一样，这点是由日志复制的规则来保证的；