The Anti-Entropy Gossip Paper

Gossip 协议分 anti-entropy 和 rumor-mongering 两类。前者持续不断地传播信息，直至信息被更新版本的内容替代；后者在指定的时间内传播某条消息，确保该消息以最大的可能性被同步到整个集群。这篇 post 讨论的论文是针对 Anti-Entropy Gossip 展开的。

Gossip 状态 ​

Gossip 中的状态包括 K 到（V，N）的映射，KV 分别代表键值，N 是版本号。这个状态可以更新，会被复制到所有的集群成员上。集群中每个成员都会周期性地执行如下操作：随机选择另一个成员，传递状态，两个成员进行状态合并操作。

状态传递方式 ​

传递状态的方式一般有三种：

1. 推：A 将状态发送给 B，由 B 来执行状态合并；
2. 拉：A 将自身状态摘要发送给 B（只包含 V、N 不包含 K），B 只返回有必要更新的状态；
3. 推 - 拉：在拉的基础上，B 还会检查自身落后的状态，将摘要发送给 A，然后 A 再发送相应状态。

可见，推拉结合的方式能够同时更新双方的状态，效率更高，论文后续关注这一种方式。

状态合并 ​

精确合并（Precise Reconciliation） ​

该模式下，只有需要更新的状态（由版本号等判定）会被发送，这意味着双方需要事先交换摘要。

在状态数据量太大（超过了 MTU）时，一次状态发送时只能发送一个子集，此时优先发送哪些状态就成了一个问题。 例如，如果优先传输版本号最新的状态，那么必然有落后的状态（相比于频繁更新的那部分而言）出现饥饿状况。

整体合并（Scuttlebutt Reconciliation） ​

scuttlebutt 一词本身也具有 gossip 的意思，翻译成整体其实不算很准确：

early 19th century (denoting a water butt on the deck of a ship, providing drinking water): from scuttled butt. Sailors would traditionally exchange gossip when they gathered at the scuttlebutt for a drink of water.

论文使用整体合并的方式实现对网络带宽和 CPU 的高效利用。 整体合并要求状态的版本号是状态全局的，也就是说，KVN 三元组中的 N 表示的不再是特定 KV 对的版本，而是当前全局状态的版本。因此，一旦出现状态更新，更新的状态记录的版本号就会是所有记录最大版本号 + 1，而非简单在其之前版本号基础上 + 1。

在检查是否需要更新时，需要比较当前记录与状态最大版本号，只有收到的记录版本号大于当前状态最大版本号时才会更新。 这种模式在并发状态更新的情况下可以避免下图所示的无意义状态更新：

图中存在 p, q, r 三台主机，在两个时间阶段直接，p 和 q 都同 r 交换了状态，由于 MTU 限制，只同步了数据 a。 如果下一阶段 pq 之间发生 gossip，由于两者的最大版本号均为 21（来自 r），因此不会发生 b 和 c 数据的更新， 这部分数据的更新只能来自于 r。这样一来就避免了 p 更新来自 q 的数据，这部分数据尽管更新，但是并非最新的数据版本，迟早会被来自 r 的数据所取代。

流控制 ​

流控制的目的是控制更新提交的速率，使之在接收方可容忍的范围内尽可能大，类似于 TCP 中利用滑动窗口控制流量。

集群中两个成员 gossip 时，将交换它们目前的最大更新速率。两者将根据双方的最大速率、期望速率来调整彼此的最大速率。

另外，发送方还会根据本地是否出现连续的满溢 gossip 消息，来调整自身的最大速率：