漫谈Gossip协议与其在Redis Cluster中的实现 _Gossip协议

前言之前给小伙伴们科普ClickHouse集群的时候，我曾经提到ClickHouse集群几乎是去中心化的（decentralized），亦即集群中各个CK实例是对等的，没有主从之分。集群上的复制表、分布式表机制只是靠外部ZooKeeper做分布式协调工作。想了想，又补了一句：
“其实单纯靠P2P互相通信就能维护完整的集群状态，实现集群自治，比如redis Cluster 。”
当然限于时间没有展开说。这个周末休息够了，难得有空，来随便讲两句吧。
在官方Redis Cluster出现之前，要实现集群化Redis都是依靠Sharding+Proxy技术，如Twemproxy和Codis（笔者之前也写过 Codis集群的事儿）。而官方Redis Cluster走了去中心化的路，其通信基础就是Gossip协议，同时该协议还能保证一致性和可用性。本文先来介绍一下它。
Gossip协议简介
最近几个月一直在看《Friends》下饭。认为自己从不gossip的Rachel一语道破了gossip的本质。

文章插图

现实生活中的流言八卦传播的机制就是“I hear something and I pass that information on”，并且其传播速度非常快。而Gossip协议就是借鉴了这个特点产生的，在P2P网络和分布式系统中应用广泛，它的方法论也特别简单：
在一个处于有界网络的集群里，如果每个节点都随机与其他节点交换特定信息，经过足够长的时间后，集群各个节点对该份信息的认知终将收敛到一致。
这里的“特定信息”一般就是指集群状态、各节点的状态以及其他元数据等。可见，Gossip协议是完全符合BASE理论精神的，所以它基本可以用于任何只要求最终一致性的领域，典型的例子就是区块链，以及部分分布式存储。另外，它可以很方便地实现弹性集群（即节点可以随时上下线），如失败检测与动态负载均衡等。
以下GIF图示出Gossip协议下一种可能的消息传播过程。蓝色节点表示对消息无感知，红色节点表示有感知。

文章插图

Source: https://managementfromscratch.wordPress/ target=_blank class=infotextkey>WordPress.com/2016/04/01/introduction-to-gossip/
为了使Gossip协议更易于表达和分析，一般都会借用流行病学（epidemiology）中的SIR模型进行描述，因为大流行病（pandemic，比如这次新冠肺炎）的传播与流言八卦的传播具有相似性，并且已经由前人总结出一套成熟的数学模型了。
流行病学SIR模型
SIR模型早在1927年就由Kermack与McKendrick提出。该模型将传染病流行范围内的人群分为3类：

S（易感者/susceptible），指未患病的人，但缺乏免疫能力，与感染者接触之后容易受到感染。
I（感染者/infective），指已患病的人，并且可以将病原体传播给易感者人群；
R（隔离者/removed），指被隔离在无传染环境，或者因病愈获得免疫力而不再易感的人。

如果不考虑人口的增长和减少，即s(t)+i(t)+r(t)始终为一常量的话，那么SIR模型就可以用如下的微分方程组来表示。

文章插图

其中，系数β是感染率，γ则是治愈率。为了阻止以至消灭传染病的流行，医学界会努力降低感染率，提高治愈率。但是在Gossip协议的语境下，计算机科学家要做的恰恰相反，即尽量高效地让集群内所有节点都“感染”（对信息有感知）。由SIR模型推演出的Gossip协议传播模型主要有两种，即反熵（Anti-entropy）和谣言传播（Rumor-mongering），下面分别介绍之。
反熵（Anti-entropy）
熵是物理学中体系混乱程度的度量，而反熵就是通过看似杂乱无章的通信达到最终一致。反熵只用到SIR模型中的S和I状态，S状态表示节点尚未感知到数据，I状态表示节点已感知到数据，并且正在传播给其他节点。具体来讲，反熵Gossip协议有3种实现方式：