Gossip 分布式一致性协议与 Redis Cluster
Gossip Protocol
Gossip 协议和名字一样，是利用类似流言传播的方式来实现一致性的一种算法。它还有些别名，epidemic protocol 等，都是描述它的一致性传播过程。它的来源是一篇1987年的ACM论文，在现在已经应用的比较广了，包括一些分布式基础设施、区块链和 p2p 项目等等。
一个比较有趣的背景是 gossip 协议的原理和六度分隔理论，也就是那个通过六个人认识全世界的理论是相同的。基于这个理论，可以看出任何信息的传播其实非常迅速，而且网络交互次数也不会很多。gossip 的相关思想在路由算法、泛洪等都有用到，但是 gossip 论文给出了定义、具体方法和证明。
简单来说，gossip 使用非中心化的设计，每个节点都随机地选择其他某些节点来共享消息。这个定义比较宽泛，所以实现有很多变种。不过基本原理围绕那篇论文，还是比较类似的。
原理
gossip 算法又叫反熵（anti-entropy），也就是在混乱中寻求一致，通过杂乱的通信最终使所有节点的状态都达成一致。可以得出两点，gossip 的本质是一个最终一致性算法，它保证的一致性是最终一致性；其次，gossip 不考虑对各种混乱情况做分类讨论，它通过设计实现天然的分布式容错，而不是去专门维护各种加入离开情况。
gossip 协议分为两种类型，一种叫反熵，一种叫谣言传播。反熵字面意思就是降低混乱度、增加相似性，其实就是每次传播自己的所有数据；对应的谣言传播就是只传递新到达的数据。
反熵的主要工作方式是每个节点在每个周期随机地选择其他节点，然后通过互相交换自己的所有数据来消除两者的差异，就是所谓反熵。这种方法可以在来回间保证两者信息一致，但是显而易见会造成巨大的通信负担，所以不应该频繁使用。这种模式包含 Suspective（易感者）和 Infective（感染者）两种状态区分是否其有数据更新，所以也叫 SI 模型，是一种 simple epidemics。为什么 simple 呢，因为 SI 模型的传播是永远不会停止的，即使每个节点都接收到了全部更新，也会继续发送无用的同步消息。这是因为我们没法知道所有更新是否都拉完，为了确保一致性，只能不断推送。
Anyone can start a rumor, but none can stop one. (American proverb)
谣言传播的主要工作方式是当一个节点有新信息，就会周期性地联系其他节点发送这个新信息，并保持一定的活跃时间。这种方式只会交换新信息，所以可以减小通信负担。谣言传播主要使用 SIR 模型，它相比前面的 SI 模型多了一种状态 Removed，因为信息需要一个标记来使其在传播一段时间后不再被传播，否则又慢慢退化回 SI 模型了。为了维护这个信息的 age，我们可以引入一个反馈机制，在这个信息被接收者多次接收，达到一个阈值后发送者就转为 removed 状态不再发送。因为有 removed 状态的加入，这种类型的信息就有小概率出现更新无法到达所有节点的情况。相比 SI 模型，SIR 模型可以实现传播的终止，但牺牲了完全同步的一致性。
上述的两种类型分别代表通信的可靠性和代价的取舍，一般需要将两种方法结合起来使用。
对于通信方式来说，gossip 定义了三种方式来进行节点间交互：push、pull 和 push&pull。其实从字面上也比较好理解，push 就是A向在随机选择时联系的节点发送自己的消息且只管发送，B收到后更新比自己新的数据；pull 就是A随机联系B并从对方获取信息；push&pull 就是A和B同时向对方获取数据来更新自己的信息。
比较容易看出，每次进行传播操作，push 需要通信一次，pull 需要两次，而 push&pull 需要三次。虽然消息数增加了，但 push&pull 的效果最好，一次传播操作即可使节点完全一致。
总而言之，gossip 通过种子节点在 gossip 周期内散播消息，被感染节点又随机找几个邻接节点散播消息，通过将消息分类实现全量同步和增量同步的区分，并分别使用 SI 和 SIR 模型来完成，这两种模型又基于不同的通信方式来实现。
实现
剩下的就是如何用三种通信方式来实现两种模型了。具体实现可以直接看这本书的伪代码，两种模型这里面也讲的非常细致，还有数学证明：
特点
总结下 gossip 协议的优点：
- 可扩展性：gossip 是天然可扩展的，没有中心化瓶颈，收敛的时间开销是 O(logN)
- 容错性：gossip 完全不依靠投票，节点对等，所以天然容错
- 快：在节点数量比较多的时候，扩散速度 O(logN) 比一个主节点 O(n) 的传播要快得多
- 简单：非常简单，易于理解
缺点：
- 保证的是最终一致性，而非 raft 等提供的强一致性，中途会有不一致情况
- 可能出现很多冗余信息，同一个节点可能收到很多重复消息，同时对网络和cpu造成浪费
- 不能解决拜占庭问题
应用
因为其是彻底的非中心化协议（相对于 raft），它很适合用于数据库的 replication、集群成员维护、服务注册、故障检测等方面。
现在，redis 采用 gossip 作为集群中各节点信息的维护方案，apache cassandra、服务发现 Consul 也都采用 gossip 实现快速消息传播。此外，比特币也使用 gossip 协议来传播交易和区块信息。
Redis Cluster 如何使用 Gossip
众所周知 redis cluster 是 redis 官方实现的一种集群方式，采用 gossip + 局部 raft 实现，保证最终一致性。下面就看看它是如何使用 gossip 的。
消息种类
redis 使用 gossip 主要有下面几种消息：
- meet：通知新节点加入。新节点加入后，会参与后续的 ping pong 消息交换。
- ping：用于集群内相互在线检测，以及交换自己和其他一些节点的状态信息。
- pong：对 ping 和 meet 的回复，封装了自身状态，用于让集群其他节点更新自己的信息。
- fail：一个节点判定另一个节点下线，就广播一个fail消息使其他节点更新这个下线情况。
工作流程
redis cluster 通过 gossip 进行故障转移、槽位（slot）信息更新、新节点发现。对应的，这些信息提供的一致性就是最终一致性。
redis cluster 的每个节点都会维护一个 100ms 的周期，每个节点会在每个周期随机选择一些节点，并偏好性地添加一些节点，发送 ping 消息。如果接收 ping 消息的节点没有按时返回 pong，该节点就会标记其为疑似下线状态。集群中的节点会通过 gossip 传播自己掌握的各节点的状态信息，如果有半数的持有 slot 的主节点（ redis cluster 的架构中，每个节点会配备多个从节点，所以叫主节点，但这不是 gossip 涉及的范围。对于 gossip 来说，各个节点对等）都将某个主节点报告为疑似下线，其将被标记为下线并在整个集群广播。被标记为下线后，对应的从节点会根据 raft 的 leader election 机制来选举新的主节点，然后进行故障转移，新主向集群发一条 pong 消息广而告之，更新自己的信息。
总结
一段话总结 gossip 与 redis cluster 的应用：
gossip 协议是一种简单但可扩展、容错且快速的信息交换协议，用于在分布式系统中进行信息传播，提供最终一致性的一致性保证。gossip 通过反熵和谣言传播两种方法，分别维护全量和增量信息，通过 SI 和 SIR 模型权衡通信代价与可靠性的取舍。在 redis cluster 中，采用 gossip 来去中心化地维护节点的成员变更和故障转移，传递加入和退出节点的信息，并完成对故障节点的过半剔除。