分布式协议一口气学完

一、Raft 协议

1.1 基础概念

Raft 算法是通过一切以领导者为准的方式，实现一系列数据的共识和各节点日志的一致。Raft是强领导模型，集群中只能有一个领导者。

成员身份：领导者（Leader）、跟随者（Follower）和候选者（Candidate）。

图1 成员身份

• 
  
• 领导者：集群中霸道总裁，一切以我为准，处理写请求、管理日志复制和不断地发送心跳信息。
  
• 跟随者：普通成员，处理领导者发来的消息，发现领导者心跳超时，推荐自己成为候选人。
  
• 候选人：先给自己投一票，然后请求其他集群节点投票给自己，得票多者成为新的领导者。
  
• 任期编号：每任领导者都有任期编号。当领导者心跳超时，跟随者会变成候选人，任期编号 +1，然后发起投票。任期编号小的服从编号大的。
  
• 心跳超时：每个跟随者节点都设置了随机心跳超时时间，目的是避免跟随者们同时成为候选人，同时发起投票。
  
• 选举超时：每轮选举的结束时间，随机选举超时时间可以避免多个候选人同时结束选举未果，然后同时发起下一轮选举
  

1.2 领导选举

1.2.1 选举规则

• 
  
• 领导者周期性地向跟随者发送心跳消息，告诉跟随者我是领导者，阻止跟随者发变成候选人发起新选举；
  
• 如果跟随者的随机心跳超时了，那么认为没有领导者了，推荐自己为候选人，发起新的选举；
  
• 在一轮选举中，赢得一半以上选票的候选人，即成为新的领导者；
  
• 在一轮选举中，每个节点对每个任期编号的选举只能投出一票，先来先服务原则；
  
• 日志完整性高（也就是最后一条日志项对应的任期编号值更大，索引号更大）的跟随者A拒绝给完整性低的候选人B投票，即使B的任期编号大；
  

1.2.2 选举动画

图2 初始选举

图3 领导者宕机/断网

图4 第一轮选举未果，发起第二轮选举

1.3 日志复制

日志项（Log Entry）：是一种数据格式，它主要包含索引值（Log index）、任期编号（Term）和 指令（Command）。

• 
  
• 索引值：它是用来标识日志项的，是一个连续的、单调递增的整数值。
  
• 任期编号：创建这条日志项的领导者的任期编号。
  
• 指令：一条由客户端请求指定的、服务需要执行的指令。
  

图5 日志信息

1.3.1 日志复制动画

图6 简单日志复制

图7 复杂日志复制

1.3.2 日志恢复

每次选举出来的Leader一定包含在多数节点上最新的已经提交的日志，新的Leader将会覆盖其他节点上不一致的数据。

虽然新Leader一定包括上一个Term的Leader已提交(Committed)日志，但是可能也包含上一个Term的Leader的未提交(Uncommitted)日志。

这部分未提交日志需要转变为Committed，相对比较麻烦，需要考虑Leader多次切换且未完成日志恢复，需要保证最终提案是一致的、确定的，不然就会产生所谓的幽灵复现问题。

为了将上一个Term未提交的日志转为已提交，Raft算法要求Leader当选后立即追加一条Noop的特殊内部日志，并立即同步到其它节点，实现前面未提交日志全部隐式提交。

这样保证客户端不会读到未提交数据，因为只有Noop被大多数节点同意并提交了之后（这样可以连带往期日志一起同步），服务才会对外正常工作；

Noop日志本身是一个分界线，Noop之前的日志被提交，之后的日志将会被丢弃。Noop日志仅包含任期编号和日志索引值，没有指令。

日志“幽灵复现”的场景

图8

第一步，A是领导者，在本地记录4和5日志，并没有提交，然后挂了。

图9

第二步，由于B的日志索引值比C的大，B成为了领导者，仅把日志3同步给了C，然后挂了。

图10

第三步，A恢复了，并且成为了领导者，然后把未提交的日志4和5同步给了B和C（C在A成为了领导者之后、同步日志之前恢复了），然后ABC都提交了日志4和5，就这样原本客户端写失败的日志4和5复活了，进而客户端会读到其认为未提交的日志（实际上集群日志已提交）。

Noop解决日志复现

第一步，同上面一样。

第二步，由于B的日志索引值比C的大，B成为了领导者，这次不仅把日志3同步给了C，还记录了一个Noop日志，并且同步给了C。

图11

第三步，当A恢复了，想成为领导者，发现自己的日志任期编号和日志索引值都不是最大的，即使B挂了也还有C，A也就成为不了领导者，乖乖使用B的日志覆盖自己的日志。

1.4 成员变更

集群成员变更最大的风险是可能同时出现 2 个领导者。比如在成员变更时，节点 A、B 和 C 之间发生了分区错误，节点 A、B 组成旧集群（ABC）中的“大多数”。

而节点 C 和新节点 D、E 组成了新集群（ABCDE）的“大多数”，它们可能会选举出新的领导者（比如节点 C）。结果出现了同时存在 2 个领导者的情况。违反了Raft协议中领导者唯一性原则。

图12 集群（ABC）同时增加节点D和E

最初解决办法是联合共识（Joint Consensus），但实现起来难，后来 Raft 的作者就提出了一种改进后的方法，单节点变更（single-server changes）。

在正常情况下，旧集群的“大多数”和新集群的“大多数”都会有一个重叠的节点。

图13 集群（ABCD）增加新节点E

图14 集群（ABCDE）删除节点A

图15 集群（ABC）增加新节点D

图16 集群（ABCD）删除节点A

需要注意的是，在分区错误、节点故障等情况下，如果并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者的情况。

二、Gossip 协议

Gossip协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。Gossip其实是一种去中心化思路的分布式协议，解决信息在集群中的传播和最终一致性。

2.1 原理

Gossip协议的消息传播主要有两种：反熵（Anti-Entropy）和谣言传播（Rumor-Mongering）。

2.1.1 反熵：节点相对固定，节点数量不多，以固定概率传播所有的数据

每个节点周期性地随机选择其他节点，通过互相交换各自的所有数据来消除两者之间的差异，实现数据的最终一致性。反熵非常可靠，但每次节点两两交换各自的所有数据会带来非常大的通信负担，因此不会频繁使用。通过引入校验和等机制，可以降低需要对比的数据量和传播消息量。

反熵 使用“simple epidemics”方式，其包含两种状态：susceptible和infective，这种模型也称为SI model。处于infective状态的节点代表其有数据更新，并且会将这个数据分享给其他节点；处于susceptible状态的节点代表其并没有收到来自其他节点的更新。

图17 反熵

2.2.2 谣言传播：节点动态变化，节点数量较多，仅传播新到达的数据

当一个节点有了新信息后，这个节点变成活跃状态，并周期性地向其他节点传播新信息。直到所有的节点都知道该新信息。由于节点之间只传播新信息，所以大大减少了通信负担。

谣言传播 使用“complex epidemics”方法，比反熵 多了一种状态：removed，这种模型也称为SIR model。处于removed状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。因为谣言消息会在某个时间标记为removed，然后不会再被传播给其他节点，所以谣言传播有极小概率使得所有节点数据不一致。

图18 谣言传播

一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。

2.2 通信方式

节点间的交互主要有三种方式：推、拉和推/拉

图19 节点状态

2.2.1 推送模式（push）

节点A随机选择联系节点B，并向其发送自己的信息，节点B在收到信息后比较/更新自己的数据。

图20 推方式

2.2.2 拉取模式（pull）

节点A随机选择联系节点B，从对方获取信息，节点A在收到信息后比较/更新自己的数据。

图21 拉方式

2.2.3 推/拉模式（push/pull）

节点A向选择的节点B发送信息，同时从对方获取信息，节点A和节点B在收到信息后各自比较/更新自己的数据。

图22 推/拉方式

2.3 优缺点

• 
  
• 优点
  
  • 
    
  • 可扩展性（Scalable）: Gossip协议是可扩展的，一般需要 O(logN) 轮就可以将信息传播到所有的节点，其中N代表节点的个数。每个节点仅发送固定数量的消息，并且与网络中节点数目无关。在数据传送时，节点并不会等待消息的Ack，所以消息传送失败也没有关系，因为可以通过其他节点将消息传递给之前传送失败的节点。允许节点的任意增加和减少，新增节点的数据最终会与其他节点一致。
    
  • 容错（Fault-tolerance）: 网络中任何节点的重启或者宕机都不会影响 Gossip 消息的传播，具有天然的分布式系统容错特性。
    
  • 健壮性（Robust）: Gossip协议是去中心化的协议，集群中的所有节点都是对等的，没有特殊的节点，所以任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量。
    
  • 最终一致性（Convergent consistency）: Gossip协议实现信息指数级的快速传播，因此在有新信息需要传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。
    
  
  
  
• 缺点
  
  • 
    
  • 消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网，不可避免的造成消息延迟。
    
  • 消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，不可避免地引起同一节点消息多次接收，增加消息处理压力。
    
  
  
  

三、参考

• 
  
• raft.github.io
  
• thesecretlivesofdata.com/raft/
  
• Raft算法（一）：如何选举领导者？
  
• Raft算法（二）：如何复制日志？
  
• Raft算法（三）：如何解决成员变更的问题？
  
• 如何解决分布式系统中的“幽灵复现”？
  
• Gossip协议：流言蜚语，原来也可以实现一致性
  
• 浅谈集群版Redis和Gossip协议，它们之间的联系及用法
  
• 分布式一致协议Gossip协议
  
• 分布式原理：一文了解 Gossip 协议
  
• 从Ping-Pong消息学习Gossip协议的实现