揭开共识算法的神秘面纱及其实现

什么是共识算法？什么是分布式数据库？Kubernetes和ZooKeeper如何以容错方式存储数据？

这些是我们将在本文中尝试回答的一些问题。本文的A部分将尝试解释您将在当前的分布式计算世界中听到的一些常见术语。在B部分中，我们将探讨共识算法的基本概念。C部分将介绍两个著名的共识算法，RAFT和ZAB，最后，我们将探索这些算法如何支持ZooKeeper和Kubernetes的分布式本质。

这些概念可能看起来很新，但了解它们肯定会对你的工作或下一次面试有所帮助。马丁·克莱普曼(Martin Kleppmann)写的一本名为“设计数据密集型应用程序”(Designing Data-密集型Applications)的优秀著作中借用了大量文字内容。祝您学习愉快！

在单引导者复制中，引导者(主)将数据复制到其所有跟随者(读取副本、辅助节点)。这是最常用的复制模式。每当新写入到达主节点时，它都会将该写入保留到其本地存储，并将相同的数据作为更改流或复制日志发送到其所有复制副本。然后，每个辅助节点按照在领导节点上处理数据的相同顺序更新其自己的本地数据副本。

在领导者-跟随者的情况下，可能会发生两个节点都认为自己是领导者的情况。这种情况叫做裂脑。如果两位领导人都接受写入是危险的，而且没有解决冲突的过程。数据可能会丢失或损坏。

让我们考虑一下我们有五个节点的情况。节点A是当前的领导者，其余的是跟随者。现在假设我们的节点A出现故障。其余节点在它们之间做出决定，并将节点B提升为新的领导者。现在节点A重新联机。这个节点直到现在还不知道发生了什么，并且仍然相信自己是领导者，这导致系统有两个领导者节点。

线性化背后的基本思想是使系统看起来好像只有一个数据副本，并且其中的所有操作都是原子的。有了这个保证，即使可能有多个副本，实际上应用程序也不需要担心它们。

可线性化很重要，因为它解决了一些非常重要的用例，例如锁定和领导者选举、数据库唯一性保证(唯一性约束)和跨通道定时依赖。

您可能认为实现这一点的最简单方法是真正只使用数据的单个副本。但是，这种方法是不可容错的。如果保存该副本的节点出现故障，数据将丢失，或者至少在重新启动该节点之前无法访问。现在问题出现了，如何在复制的数据库中实现线性化。

单个引导者复制：在这里，引导者拥有用于写入的数据的主拷贝，而跟随者在其他节点上维护数据的备份拷贝。如果你从领导者或同步更新的追随者那里阅读，那么他们就有可能成为线性化的。

单引导器复制通过选择一个节点作为引导器，并对引导器上单个CPU核心上的所有操作进行排序，从而确定操作的总顺序。因此，挑战是如何在吞吐量大于单个领导者可以处理的情况下扩展系统，以及在领导者出现故障时如何处理故障转移。在分布式系统中，这个问题称为全序广播或原子广播。

全顺序广播通常被描述为用于在节点之间交换消息的协议。非正式地，它要求始终满足两个安全属性：

交付可靠。不会丢失任何消息。如果将消息传递到一个节点，则会将其传递到所有节点。

查看总订单广播的另一种方式是，它是创建日志(如复制日志中的日志)的一种方式，其中传递消息类似于将消息追加到日志。由于所有节点必须以相同的顺序传递相同的消息，因此所有节点都可以读取日志并看到相同的消息序列。

总订单广播是异步的。保证以固定顺序可靠地传递消息，但不能保证何时传递消息(因此，一个收件人可能会落后于其他收件人)。相比之下，线性化是近期的保证。保证读取时会看到写入的最新值。

几乎所有的共识算法在内部都使用领导者。这些协议利用纪元编号，并保证在每个纪元内，领导者是唯一的。

1.每次认为现任领导人已经去世，节点之间就会开始投票选举新的领导人。

2.该选举被赋予递增的纪元编号，因此纪元编号是完全有序的并且单调递增。

3.如果两个不同时代的不同领导人之间存在冲突(可能是因为前一位领导人实际上并没有去世)，那么以纪元数较高的领导人为准。

4.领导者在被允许作出任何决定之前，必须从一定的节点法定人数中收集选票。只有当节点不知道有任何其他具有更高纪元的领导者时，它才会投票支持一项提议。这可以防止大脑分裂的问题。

共识意味着多个服务器就相同的信息达成一致。通常，我们可以通过三个步骤定义一致性算法：

当选人。流程会选出一位领导人来做决策。领导者提出下一个有效的输出值。

投票吧。无故障流程监听领导提出的值，对其进行验证，并将其作为下一个有效值提出。

决定吧。非故障流程必须就单个正确的输出值达成共识。

共识算法是分布式系统的一大突破。它们为系统带来了具体的安全属性(一致性、完整性和有效性)，但它们仍然具有容错性。它们提供全顺序广播，因此它们还可以以容错的方式实现可线性化的原子操作。

算法可以容忍的失败次数是有限制的。任何共识算法都需要至少大多数节点正常工作才能确保终止。

共识算法有一些与之相关的局限性，这限制了它们在某些情况下的可用性。

节点在决定提案之前对其进行投票的过程是一种同步复制，这会导致性能问题。

协商一致制度总是需要绝对多数才能运作。这意味着，在四个节点的仲裁中，您至少需要三个节点才能运行。

共识系统通常依靠超时来检测故障节点。在具有高度可变的网络延迟的环境中，经常会发生节点错误地认为领导者由于暂时性网络问题而发生故障的情况。在这种情况下频繁的领导人选举会导致糟糕的表现，因为系统最终可能会花费更多的时间来选择领导人，而不是做任何有用的工作。

最后，我们都在等待的部分：理解到目前为止我们读到的一切是如何构成各种共识算法的支柱的。然后，我们来看一下各种常用的协调服务的工作原理：ZooKeeper和etcd。

RAFT算法是一种单引导者算法。RAFT算法中的节点可以处于以下三种状态之一：

领导者保持以心跳超时指定的规则间隔向所有跟随者发送心跳。所有消息都通过此心跳进行通信。RAFT算法遵循以下步骤。

如果追随者没有收到领导人的来信，那么他们可以成为候选人。选举超时是指追随者在成为候选人之前等待的时间。它是随机的，介于150ms和300ms之间。

然后，候选人开始新的选举任期。它为自己投票，并向其他节点发送请求投票消息。节点用它们的投票进行回复。

如果候选人从多数节点获得选票，它就会成为领导者。这个过程叫做领导人选举。所有更改都要经过引线，如上图所示。

在领导人选举期间，请求投票还包含有关候选人日志的信息，以确定哪个日志是最新的。如果请求投票的候选人的更新数据少于它请求投票的追随者，则追随者根本不会投票给所述候选人。

每个更改都会作为一个条目添加到领导者的日志中。日志条目最初是未提交的。

领导者等待，直到大多数节点已经写入该条目。收到响应后，现在提交条目。

然后，领导者更新跟随者该值已提交的信息。追随者节点然后分别提交该值。

群集现在已就系统状态达成共识。此过程称为日志复制。

解决了分裂大脑问题，因为在集群中，任何时候都只有一个节点可以达到多数。如果两个节点的票数相等，则投票将再次进行。

正如您一定已经意识到的那样，该算法使用了我们之前研究过的两阶段提交的概念。首先，由一位领导人发起一轮投票。在超过半数的选票被接受后，就会发起承诺。

它正在各种系统中使用，例如etcd和Consul(Hashicorp)。MongoDB的复制也受到RAFT算法的广泛影响。

ZAB(动物园饲养员原子广播)是动物园饲养员使用的一种共识协议。ZAB是针对ZooKeeper的专用协议，因此它的使用仅限于ZooKeeper。扎布和动物园管理员一起出生于2007年。

如果领导者在提交阶段失败，并且此写入操作已在至少一个跟随者上提交，则该跟随者肯定会被选为领导者，因为它的zxid是最大的。被选为领袖后，此跟随者让所有跟随者提交此消息。

从上面的图表中我们可以看到，到目前为止，我们已经探索过的共识算法有广泛的实现，比如ZooKeeper、etcd和Chubby。它们间接用于解决分布式系统中的各种问题，如服务发现、协调、锁定、故障检测和主机选举。

“一种高度一致的分布式键值存储，它提供了一种可靠的方式来存储需要由分布式系统或计算机群集访问的数据。它可以在网络分区期间优雅地处理领导者选举，并可以容忍机器故障，即使在领导者节点中也是如此。ETCD机器之间的通信通过RAFT共识算法进行处理。

现在让我们来看看使用它的一些流行工具/软件。

Etcd用作服务发现的后端，并存储所有集群状态和配置，本质上是作为其数据库。

它使用etcd的手表功能来监视对这两项内容的更改。如果它们有分歧，库伯内斯就会做出改变，使实际状态和期望状态相协调。

通过kubectl create进行的任何更改都将导致etcd中的条目更新。

用于维护配置信息、命名、提供分布式同步和提供组服务的集中式服务。

动物园看守人本身就是一个技术奇迹，所以我们不会深入讨论它的全部细节。

ZooKeeper维护集群配置信息，该信息在集群中的所有节点之间共享。

它可以通过使用锁、队列等来解决集群中的分布式同步问题。

ZooKeeper还在群组服务中帮助选择集群中的主要动物(领导者选举过程)。

提供更改通知功能。客户端可以发现另一个客户端何时加入集群(基于它写入ZooKeeper的值)，或者另一个客户端是否失败。

作为应用程序开发人员，您很少需要直接使用ZooKeeper，因为它实际上并不适合作为通用数据库。更有可能的是，您最终会通过其他项目间接依赖它。例如，HBase、Hadoop纱线、OpenStack Nova、Akka和Kafka都依赖于在后台运行的ZooKeeper。

“Apache Kafka是一个开源的分布式事件流平台，被数千家公司用于高性能数据管道、流分析、数据集成和任务关键型应用程序。”-Apache Kafka网站。

控制者选举：控制者是Kafka生态系统中最重要的经纪实体之一，它也有责任维护所有分区的领导者-追随者关系。

主题配置：包括所有主题的配置，包括已有主题的列表，如每个主题的分区数、所有副本的位置等。

访问控制列表：所有主题的访问控制列表或ACL也在ZooKeeper中维护。

集群的成员身份：ZooKeeper还维护在任何给定时刻运行并且是集群一部分的所有代理的列表。

然而，Kafka很快就计划取消对ZooKeeper的依赖，以简化其架构。在他们的博客https://www.confluent.io/blog/category/apache-kafka上可以找到一些与卡夫卡工作有关的令人惊叹的文章。

这些都是我这边的，伙计们。我希望这篇文章对你有意义。请随时给出您的反馈意见。