前言
Consul 中使用 Raft 算法解决一致性问题，使用 Gossip 协议来管理集群成员和广播消息，其中 Raft 属于强一致性模型，Gossip 属于弱一致性模型。不仅是 Consul，Redis Cluster 中也使用了 Gossip 协议。
Raft 算法
Raft 算法中的 Server 有以下三种状态：Leader（领导者）、Follower（跟随者）和 Candidate（候选者）。
Leader 负责处理所有的查询和事务，并向 follower 同步事务。Follower 会将所有的 RPC 查询和事务转发给 leader 处理，所有 follower 仅从 leader 接受数据同步，数据的一致性以 leader 中的数据为准实现。
Raft 算法将一致性问题分解成为三个相对独立的子问题：
领导选取（Leader election）：在一个 leader 宕机之后必须要选取一个新的leader。
日志复制（Log replication）：Leader 必须从 client 接收 log 然后复制到集群中的其他 follower，并且强制要求其他 follower 的 log 保持和自己相同。
安全性（Safety）：Raft 的 Safety 指的是 State Machine Safety（状态机安全），其含义是如果一个 server 已经将给定索引位置的 log 应用到状态机中，则所有其他 server 不会在该索引位置应用不同的log（log 一致）。
Leader Election
情形1：选举成功
Raft 算法采用 timeout 来控制选举过程，初始化的选举过程如下：
在集群初始化启动时，节点的 Raft 状态机将处于follower 状态等待来自 leader 的心跳。
如果 follower 在 timeout 内没有接收到来自 leader 的心跳，则会将自己的状态切换为 candidate，然后向其他的 follower 发起选举请求，询问其是否将自己选为 leader。每次开启的一轮新的选举被称为一个”任期”，每个任期都有一个严格递增整数值 term 与其对应。
当某个 candidate 收到来自集群中超过 quorum （通常为半数）的投票后，即成为 leader，它将发送心跳消息给其他节点来宣告它的权威性以阻止其它节点再发起新的选举，并开始接收 client 的请求。此时一轮选举结束，集群内的每个节点的 term 都会加 1。每个 follower 在一个任期中只能投出一票，而且遵守”先到先服务”的原则。
新的 leader会继续向 follower发送心跳，心跳包里包含 client 的事务处理和查询请求，每次 follower接收到来自 leader 的心跳后，就会刷新自己的 timeout。
情形2：选举中收到其他的 Leader RPC
当一个 candidate 等待选票时，可能会收到来自其他 candidate 发来的声明其为 leader 的 AppendEntries RPC。如果这个 leader 的任期比这个 candidate 的当前任期要大，则 candidate 认为该 leader 合法，并且转换自己的状态为 follower。如果在这个 RPC 中的任期小于 candidate 的当前任期，则 candidate 会拒绝此次 RPC， 继续保持 candidate 状态。
情形3： 选举平票
如果同时有多个 follwer 想要竞选 leader，且它们都收到了同样的票数，那么这些 follower 会在等待随机的 timeout 后再次发起选举，以保证总会有一个 follower 是最先达到法定人数票数的。
即每个节点的 timeout 都是随机决定的，一般在 150 到 300 毫秒之间，这种机制使得在大多数情况下只有一个节点会率先到达 timeout，它会在其它节点 timeout 之前赢得选举并且向其它节点发送声明其选举成功的心跳。
网络分区问题
当出现网络分区故障时，会出现多个 leader，如果网络通信恢复后，集群内的 leader 会按照较大的 term 来决定。
在 Leader Election 阶段，由于旧的 leader 可能也还存活，可能会存在不只一个 leader 的情况，Raft 保证的是不存在 term 一样的两个 leader。
Log Replication
Log Replication 的步骤如下：
- 每个客户端的请求都会被重定向给 leader，每一条请求都包含一条需要被复制状态机（replicated state machine）执行的命令。
- leader 把这条命令加入到新的 log 条目中，同时向其他服务器发起 AppendEntries RPC ，要求其他 follower 同步这条 log。
- follower 同步成功后返回给 leader 一条消息，如果 leader 收到超过 quorum 的 follower 的同步成功消息，leader 将会将这条 log 输入到状态机中，然后响应 client 成功。
- 如果 follower 宕机或是网络中断，leader 会无限重发 AppendEntries RPC（甚至在它向 client响应之后），直到所有的 follower 最终同步了 log。leader 通过强制 followers 复制它的 log 来处理不一致问题，follower 上的不一致的 log 会被 leader 的 log 所覆盖。
其中，每个 log 条目包含：
- log index：log 的索引，即图片最上方的数字，是严格递增的，用来表示在 log 中的位置。
- term：log 任期号，即方块中的数字
- command：log 对应的数据修改操作。
以上同步操作中的最重要一点就是只有在 leader 接收到超过半数法定人数的 follower 都同步成功消息后，leader 才会真正执行 commit，此时一条 log 才算真正被写入到集群中（committed）。
Raft 保证以下 Log Matching Property（日志匹配原则）：
- 如果在不同 log 中的两个条目有着相同的 index 和 term，则它们所存储的 command是相同的。
- 如果在不同 log 中的两个条目有着相同的 index 和 term，则它们之间的所有条目都是完全一样的。
Safety
然而，Leader Election 和 Log Replication 还不能保证每一个状态机能按照相同的顺序执行同样的指令。例如，当 leader 提交了若干 log 条目的同时一个 follower 可能宕机了，之后它又被选为了 leader 然后用新的 log 条目覆盖掉了旧的条目，最后，不同的状态机可能执行不同的命令序列。
Leader 限制
Raft 引入了 Leader Completeness（领导人完全原则）：任何 leader 都必须拥有之前已提交的全部 log 条目，来解决这个问题。
Raft 使用投票的方式来阻止没有包含全部 log 条目的节点赢得选举。只有 candidate 的 log 比被请求投票的节点 log 要新，这个节点才会同意投票。之所以要求这个条件，是为了保证每个当选的 leader 都有当前最新的数据。为了达到这个检查 log 的目的，RequestVote RPC 请求中需要带上 candidate 的 log，如果节点发现 candidate 的 log 并不比自己更新，就会拒绝给这个节点投票。
Raft 通过比较两份 log 中最后一条 log 条目的 index 和 iterm 来判断谁的 log 比较新。如果两份 log 最后的条目的 iterm 不同，那么 iterm 大的 log 更加新。如果两份 log 的 iterm 相同，那么 log 比较长的那个就更加新。
提交之前任期的 log
如果 leader 在提交 log 之前崩溃，那么后续的 leader 该如何提交这条没有提交的 log ？有以下几种情况需要考虑。
在 (a) 中，S1 是 leader，index = 2 的位置写入了数据 2，但只写入了 S1 与 S2 中，由于未达到法定人数，这条 log 并未被 commit。
在 (b) 中，假设 S1 崩溃，S5 成为了新的 leader，此时 S5 在任期 3 中写入了数据 3 放入 index = 2 的位置，这条 log 也未被提交。
在 (c) 中，假设 S5 也崩溃，S1 恢复并成为 leader，开始同步 log，此时数据 2 已被同步到多数节点中，可以 commit。此时 S1 又接受了一条在 index = 3 的位置上写入数据 4 的 log。
这时，可能会导致以下两种情况：
- 情况 (d)：S1 再次崩溃，S5 成为 leader，开始同步 log ，此时 index =2 的位置上的数据 2 会被覆盖成 S5 上的数据 3。
- 情况 (e)：S1 不崩溃，成功将自己的当前任期前的数据 4 都同步到其他节点上，这些 log 就会被 commit。
从情况 (d) 与情况 (e) 可以看出，index = 2 的数据 2 即使处于写入超过半数节点的情况下，仍有可能会被覆盖。
此时的解决办法是：对于当前任期之前任期提交的 log，并不通过判断是否已经在半数以上节点写入成功来作为能否提交的依据，而是通过比较当前 leader 任期内的 log 写入数量是否超过半数来决定。
其他 Raft 参考资料：
Raft 可视化
Raft 论文中文翻译
Raft 官网
Gossip 协议
Gossip 协议适用于去中心化、容忍时延、读多写少的分布式集群场景。Gossip 过程由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。
Gossip 协议是为了解决分布式环境下监控和事件通知的瓶颈。Gossip 协议中的每个 Agent 会利用 Gossip 协议互相检查在线状态，分担了服务器节点的心跳压力，通过 Gossip 广播的方式发送消息。
Gossip 协议的最大的好处在于即使集群节点的数量增加，每个节点的负载也不会增加很多，几乎是恒定的。这就允许 Consul 管理的集群规模能横向扩展到数千个节点。
基于 Raft 算法，Consul 提供强一致性的注册中心服务，但是由于 Leader 节点承担了所有的处理工作，势必加大了注册和发现的代价，降低了服务的可用性。通过 Gossip 协议，Consul 可以很好地监控 Consul 集群的运行，同时可以方便通知各类事件，如 leader 选择发生、server 地址变更等。
Gossip 的特点
扩展性：网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。
容错：网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。
去中心化：Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。
一致性收敛：Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
简单：Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。
Gossip 中的通信模式
Gossip 协议中的两个节点（A、B）之间存在三种通信方式：
Push（A 最新）: A 将数据 (key,value,version) 及对应的版本号 Push 给 B，B 更新本地数据。
Pull（B 最新）：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（key, value, version）Push back 给 A，A 更新本地。
Push/Pull（A/B 一样新）：比 Pull 多一步，A 更新本地后，再将数据 Push back B，B更新本地。
如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push/Pull 则需 3 次。虽然消息数增加了，但从效果上来讲，Push/Pull 最好，理论上一个周期内可以使两个节点完全一致。
Gossip 的缺点
消息延迟：由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。
消息冗余：Gossip 协议规定，节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。