作者：EVANCE SOUMAORO

即使在10年的编程生涯中，我仍然对新的软件算法有着不懈的好奇心，阅读论文和博客文章，并向其他工程师学习。然而，当你有机会实现一种算法，甚至为你的特定用例定制它时，最好的部分才真正到来。在这篇文章中，我将向你介绍我从理解集群成员制的基本原理到实现Chitchat的过程，Chitchat是我们对Scuttlebutt算法的Rust实现，带有一个phi累积故障检测器。

我将首先介绍集群成员制的主题，并给出目前Quickwit中使用的成员制算法（SWIM）的一些细节。为什么我们决定放弃它，尽管在概念上比后继者略快。然后，我将深入探讨scuttlebutt和故障检测器算法如何工作，我们是如何实现它们的。最后，我将描述我们遇到的几个真实世界的问题，以及我们如何解决这些问题。

什么是集群成员？

给定一个节点集群，集群成员是允许每个节点知道其同伴名单的子系统。它可以检测到节点故障，并最终让所有其他节点知道，一个故障节点不再是集群的成员。

解决这个问题的一个常见方法是，让一个监控节点负责通过运行heart-beating scheme来检查所有其他节点的健康状况。这种方法对少数节点来说效果很好，但随着集群的扩大，会出现热点。另一种方法是让所有的节点负责监控。虽然这避免了热点，但所有现有的heart-beating scheme提供了不同程度的可扩展性和准确性。有些产生了大量的网络流量，而有些可能需要一点时间来收敛。所有这些问题加在一起，使集群成员成为一个棘手的工程问题。

什么是SWIM，为什么我们要放弃SWIM？

从我们的第一个版本开始，Quickwit就有了集群成员功能，以便提供分布式搜索。SWIM是目前用于该功能的算法。它是基于一种被称为传播又称 "造谣 "的八卦风格。Scuttlebutt则不同，它是基于另一种被称为 "反熵 "的八卦风格。Robbert等人在他们的论文中对这两种八卦方式的区别解释如下：

反熵协议在信息被更新的信息所淘汰之前都会进行八卦，对于在一群参与者之间可靠地分享信息是很有用的。谣言传播让参与者在一定的时间内八卦信息，选择足够高的时间，以便所有参与者都很有可能收到信息。

接下来是一个我们喜欢用来解释造谣和反熵之间区别的现实世界的例子：

造谣：考虑到你刚从当地报纸上读到的一则爆炸性新闻，并决定通知你所有的联系人。你通知的人也决定通知他们的联系人。这种流言蜚语的方式使新闻传播得非常快。然而，有一段时间，人们会对新闻失去兴趣，停止传播它，而且不是每个人都有机会被告知。

反熵：假设镇上的每个人都定期与他的几个联系人（3到5个）交谈，以了解镇上的任何新闻。这种类型的信息交流是比较慢的，因为需要选定联系人的数量。然而，由于每个人都会一直这样做，所以无论花多少时间，他们都能保证了解到最新的消息。

这里的关键区别是，在SWIM中，一个节点可能会错过一些在集群中传播的消息，这可能会导致假阳性的故障检测。例如，Hashicorp不得不用Lifeguard扩展他们的生产级SWIM实现Serf。Lifeguard是一组三个扩展，旨在减少假阳性故障检测。

我们也在努力寻找一个合适的面向库的Rust中的SWIM实现。虽然我们发现Artillery一开始就非常有用，并且我在这里要感谢所有的贡献者，但我们希望有一个像围棋中的Serf那样的更经得起考验的实现方式。

此外，我们发现，scuttlebutt作为一种算法：

更容易理解和正确实施。

允许节点分享/宣传自己的信息（服务端口、可用的内存/磁盘），无需任何特殊的逻辑。

在生产级系统（如Apache Cassandra）中经过了实战检验。

scuttlebutt如何工作？

Scuttlebutt是一种带有调和技术的八卦算法，本文对此进行了充分描述。在scuttlebutt中，每个节点都保留一份集群状态的本地副本，这是一个节点ID到节点状态的映射。可以把它看作是一个由节点ID命名的键值存储，其中一个节点只允许修改（创建/更新/删除）自己的命名空间。一个节点可以应用它从其他节点感知到的变化，同时进行八卦。然而，它不能直接更新其他节点的状态。因为scuttlebutt采用了反熵流言技术，集群中的所有节点最终都会在某个时刻得到最新的集群状态。另外，注意到这个概念是基于键值存储的，使得节点很容易分享信息。

下面是节点node-1/1647537681查看集群状态的JSON表示。node-1后面的数字是一个时间戳，你很快就会明白为什么我们要添加这个数字。注意每个节点是如何宣传自己的grpc_address和heart-beating计数器的。

八卦协议的工作方式如下：

每一秒钟，一个节点随机选择几个（在我们的例子中是3个）节点进行八卦。

为了使这个节点的选择更智能一些，我们随机地包括：

一个种子节点，如果还没有被选中的话

一个死亡节点（以确定它是否重新上线）

八卦频率和所选节点的数量是可配置的，因为它们直接影响任何集群状态变化的传播速度。

现在让我们来描述一下两个节点之间的单一gossip回合的流程。

从上图可以看出，一个八卦轮是由节点A发起的。

1、节点A与节点B发起了一轮八卦：

计算其摘要（DigestA）。

向节点B发送一个带有DigestA的Syn消息。

2、节点B在收到Syn消息后：

使用DigestA计算一个delta(AB)：这个delta(AB)包含节点A从节点B的集群状态副本中丢失的内容。

计算其摘要（DigestB）。

发送一个带有delta和DigestB的SynAck回复。

3、节点A在收到SyncAck回复后：

将delta AB（变化）应用于其集群状态的副本。

使用DigestB计算delta(BA)：delta(BA)是节点B从节点A的集群状态副本中丢失的内容。

发送一个带有delta的Ack消息。

4、最后，节点B在收到Ack消息后：

将delta BA（变化）应用于其集群状态的副本。

— Digest是一个node_id到max_version的映射，有助于计算哪些密钥空间是缺失的或过时的，同时减少需要在节点之间交换的数据量。再加上Scuttlebutt依赖于UDP而不是TCP，这— 使得它成为一种非常节省资源的算法。

消息类型（Syn、SynAck和Ack）遵循与TCP 3路握手消息类型相同的模式。

关于heart-beating的附带说明

在大多数分布式系统中，节点通过heart-beating来注意它们的存在，scuttlebutt算法也不例外。然而，scuttlebutt通过状态调和以两种方式隐含地提供heart-beating：

节点A和B之间的直接heart-beating：节点A直接与节点B进行闲谈。

节点B和C之间的间接heart-beating：节点A在与B说闲话的同时分享节点C的最新状态。

在scuttlebutt算法中，不是有一个专门的heart-beating消息，而是每个节点在自己的密钥空间中维护一个heart-beating计数器的密钥，并持续更新。这就像一个需要自然传播的状态变化，就像一个节点想要宣传或与他人分享的任何其他值一样。

我们如何区分死节点和慢节点？

在scuttlebutt中，当一个节点停止分享更新（停止heart-beating）时，它的状态就被搁置了。那么，我们怎样才能有把握地将一个节点标记为死的或有问题的？我们可以使用超时，但我们可以做得更好：使用phi累积错误检测算法与scuttlebutt很好地结合起来。这个算法根据最近收到的heart-beating间隔的窗口来计算phi值，这是一个很好的近似值，考虑到了网络延迟、数据包丢失和应用程序性能波动。默认情况下，我们使用1000个心跳间隔的窗口大小，就像Apache Cassandra一样。默认的phi阈值为8.0，因为论文中建议的数值在8.0和12.0之间。在现实世界的场景中，这实际上是在快速故障检测和准确性之间进行权衡。

填补Chitchat和Quickwit之间的空白

到目前为止，我们已经解释了scuttlebutt和phi应计失败检测器，它们是我们的集群管理库实现（Chitchat）的核心组件。然而，我们在Quickwit中的一些要求仍然是与Chitchat完全集成的挑战。

我们在Quickwit中的实际用例的一些要求包括：

我们希望一个节点的每次运行都有一个新的本地状态。

我们不希望过时的状态一直覆盖新的状态。

我们希望其他运行中的节点能够检测到新启动的节点的状态优先于其之前的所有状态。

我们希望一个节点能够公布自己的公共流言地址。这对Kubernetes这样的动态环境很有用，因为有些配置只有在运行时才知道。

我们希望一个节点的ID在以后的运行中是相同的，以便尽可能长时间地保持缓存数据。

你可能已经注意到，在Quickwit解决技术难题时，简单易懂和正确实施是我们的核心准则之一。通过观察我们的需求，我们没有给Chitchat增加更多的功能，而是选择了更简单的解决方案，同时也做了一些取舍。我们的解决方案包括让Chitchat保持原样，定义什么是Node Id，并要求我们的客户（即Quickwit）在Node Id的基础上提供他们自己的定制功能。

Quickwit Node ID的实现

下面介绍我们的节点标识解决方案：

让id属性（节点在集群中的唯一标识符）在每次运行中都是动态的。也就是说，我们对一个节点的每一次运行都使用不同的唯一ID。

使gossip_public_address在设置节点时成为必需的。它的值可以从配置项、环境变量中提取，或者在运行时计算出来。

使节点id属性的一部分成为静态，并与物理节点相关，以解决缓存的要求。

在Quickwit中，这意味着从node_unique_id和node_generation的组合中提取id。/。

node_unique_id：节点的一个静态唯一ID或名称。有助于解决缓存的要求。

node_generation：一个单调增长的值。我们决定使用节点启动时的时间戳。

这个解决方案有几个优点，即：

不需要额外的措施来避免旧状态覆盖新状态。

Chitchat中的算法（scuttlebutt, phi accrual failure detector）的实现与各自的论文保持一致。

在Quickwit中使用时间戳进行生成有助于保持节点的无状态。

注意：

我希望你现在已经理解了我们之前看到的那个看起来很奇怪的nodeId node-1/1647537681。

还有一些需要注意的问题和权衡。

保持节点列表的控制。在Chitchat中，每个节点的重启都会引入一个全新的节点。节点列表会在集群中增长。虽然不是很关键，但在一个高度动态的环境中，这可能是不可取的。我们通过定期的垃圾收集过时的节点来缓解这一问题。

时间戳。由于时钟问题，使用时间戳来生成节点仍然有可能重复使用以前使用过的节点ID。Cassandra通过确保只有特定时钟范围内的节点才能加入集群来解决这个问题。在我们的案例中，由于我们使用了node_unique_id和node_generation的组合，重复使用相同组合的概率非常低。另外，当未来有时钟发生倾斜需要修复时，人们可以完全或部分地改变节点ID。

避免死节点虚假复活。当一个节点刚加入集群时，它的状态会被填充到所有现有的节点状态中，包括死亡的节点。由于接收节点状态被认为是一种间接的heart-beating，新加入的节点可能需要几秒钟的时间才能把死节点和活节点区分开。我们对这个问题的解决方案是避免对死节点进行八卦。一个新加入的节点只关心向前推进的活节点。如果一个节点重新上线，新节点还是会注意到它。这就是它的简单之处，最重要的是为在死节点上轻松实现垃圾收集铺平了道路。

总结

在这篇文章中，我们探讨了Chitchat，我们新的集群成员管理实现，使用了scuttlebutt gossip reconciliation技术和phi accrual failure detector的增强。我们首先强调了使我们放弃以前基于SWIM的实现的原因。然后探讨了新的实现方式，并描述了我们是如何解决一些论文中不一定涉及的挑战。我们相信这奠定了一个很好的基础，可以在此基础上进行扩展，以满足Quickwit集群管理功能即将到来的特性要求。最后但并非最不重要的是，Chitchat是自成一体的，足以在其他项目中使用。

参考资料

Chitchat：https://github.com/quickwit-oss/chitchat

Scuttlebutt paper：https://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf

Phi accrual error detection paper：https://www.researchgate.net/publication/29682135_The_ph_accrual_failure_detector

SWIM paper：https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf

Cassandra details：https://www.youtube.com/watch?v=FuP1Fvrv6ZQ&ab_channel=PlanetCassandra