理解 RAFT 分布式共识算法——第 1 部分

为什么我们需要共识

我们大多数人在我们的编程生涯中至少使用过一次关系数据库，如 MySQL、Oracle。当您INSERT或UPDATE一个值然后对其执行 SELECT时，您会得到最新的值——这通常是因为我们使用一台机器来管理我们的数据。

现在想象一下，您有大量数据分布在 10 台机器上。为了更好地提供数据，您已启用数据复制。假设一条数据在 3 台机器上复制，应用程序是全球性的，然后想从世界任何地方查询准确的数据，为了解决这个问题，我们需要一种机制，通过该机制，多个服务器可以就一个值达成一致，并且无论哪台机器为您的SELECT请求提供服务，每次都会得到相同的结果。

简而言之，您需要对分布式系统有一个连贯的视图，这样它的行为就好像只有一台机器在为所有请求提供服务，这就是我们需要达成共识的地方。

如果你想构建一个强一致的分布式系统（CAP定理中的CP系统），需要有共识。

Raft

Raft（复制和容错）是解决这个问题的算法/协议。它来自于 2014 年斯坦福大学 Diego Ongaro 和 John Ousterhout 的博士论文。 Raft 的设计易于理解，前身算法如 Paxos 和 Multi-Paxos 是众所周知的共识算法，已知很难理解理解，只有少数人能正确理解它们。

Raft 没有标准的实现，它只是定义了几个步骤以容错的方式达成共识。目前已经有数百种 Raft 实现，大多数工程师在他们的一生中不需要实现任何共识算法，但是理解分布式系统的核心并没有什么坏处。

Q. Raft 是如何实现的？
A. Raft 通常被实现为服务内部的一个模块，如分布式数据库或分布式键值存储如 etcd等。Raft 本身不是作为服务或微服务实现的。它就像系统中的后台进程一样工作。

前提条件概念

在我们深入了解 Raft 之前，请先了解以下概念。

法定人数

如果你的分布式系统有N节点，你至少需要(N/2) + 1节点来就一个值达成一致——基本上你需要多数票（超过 50%）来达成共识，就像任何国家的宪法选举一样。多数投票确保当(N/2) + 1节点运行和响应时，即使存在网络分区或系统中的其他故障，至少一个节点包含读取和写入请求中给定数据的最新值。

问：当我们有一个基于仲裁的节点系统时，我们可以容忍多少个节点故障N？
A.如果N是奇数，我们可以忍受N/2节点故障。如果N是偶数，我们可以忍受(N/2)-1节点故障。

下面是一个简单的表格来说明这个事实：

Q. 生产时应该选择偶数还是奇数N？
A.考虑一下N = 4，根据上表，所需的多数是3& 你只能容忍1节点故障。对于N = 5，大多数仍然是3但可以容忍2节点故障。

问：生产中 N 的最差值是多少？
A.如果N = 1or N = 2，如果丢失了一个节点，将丢失整个系统，因为您实际上根本无法容忍任何节点故障。事实上N = 2，您实际上已经使系统中的单点故障翻了一番——如果任何一个节点出现故障，您的整个系统就会出现故障。所以在生产中选择一个奇数值N 3。

问：在生产中什么是好的合理N？
A.这个数字显然取决于您对数据、带宽、吞吐量和成本要求的估计。但是，5是一个不错的数字，因为2节点总数停机，而3节点仍在运行。

问：如果大多数节点不可用会怎样？

理想情况下，系统可能会完全停止响应，具体取决如何配置读写用例。通常写入完全停止，但如果您将读取请求设计为最终一致，则可用节点仍可能为读取请求提供服务。

节点状态

Raft 节点可以处于三种状态：Leader, Follower& Candidate。我们将在后面的部分看到节点转换是如何发生的。现在只需要记住Raft 是一个基于领导者的共识协议，日志总是从领导者流向追随者。

日志

这不是常规日志文件，是基于磁盘的文件，通常称为日志条目的对象以二进制数据的形式顺序添加。

已提交和未提交的日志

• 只有当集群中的多数节点复制日志条目时，才会提交日志条目。提交的日志永远不会被覆盖。提交的日志是持久的，最终会被 Raft 集群中的所有节点执行。
• 如果客户端命令/日志条目尚未复制到大多数集群节点，则称为未提交日志。未提交的日志可以在追随者节点中被覆盖。

状态机

状态机本质上可能非常复杂。通常这意味着——根据输入到系统的输入，数据（键）的状态会发生变化。在 Raft 上下文中，认为这就像一个存储密钥最终商定值的模块。每个节点都有自己的状态机。Raft 必须确保无论提交什么日志条目，它们最终都会应用于状态机，该状态机作为内存中数据的真实来源。对于容错，状态机也可以持久化。

学期

表示节点充当领导者的时间段，该概念基于逻辑时间（不是全局时间） -它只是由每个节点单独管理的计数器。一旦一个任期结束，另一个任期就会从一个新的领导者开始。即使在给定的时间点，节点之间的学期可能会有所不同，但 Raft 有一种机制可以将它们同步并收敛到相同的值。

也称为租约或领导租约，只是它的另一个名称。

RPC

像 Facebook 移动应用程序通过 HTTP 之上的 REST API 与 Facebook 服务器通信一样，参与 Raft 的节点之间使用 TCP 之上的远程过程调用 (RPC) 进行通信。该协议适用于跨数据中心、内部系统和服务（不是面向用户的产品或服务）的通信。

Raft 使用两个不同的 RPC 请求。在高水平：

• RequestVote (RV)：当一个节点想成为领导者时，它通过发送这个请求来请求其他节点为它投票。
• AppendEntries (AE)：通过此消息，领导者要求追随者将条目添加到他们的日志文件中。领导者可以发送空消息以及向追随者指示它还活着的心跳。

Q. 基于领导者的系统的主要优势是什么？
A.当抽象基于领导者时，系统变得易于理解和操作。客户通常通过领导者进行交互，领导者负责重要的决策制定、系统的元数据状态。

问：基于领导的系统的主要缺点是什么？
一个。领导者成为单点故障。因此，系统应该能够在当前领导者失败时快速做出反应以选择另一个领导者。此外，由于所有客户端交互都通过领导者进行，因此系统可能会在规模上变得更慢。

随机超时

Raft 使用随机选举超时的概念——跟随者等待成为候选者的时间量（有关状态转换的更多详细信息，请参见图 3）。当集群启动时，每个节点都会为自己选择一个介于150-300毫秒之间的随机超时，并开始倒计时。现在有2种可能：

• 在节点超时之前，它会收到来自另一个节点的消息——它可能是来自领导者的心跳或日志复制消息或来自另一个对等方的投票请求。在这种情况下，超时被重置并且倒计时再次开始。
• 超时期间节点根本没有收到任何消息。

Q. 为什么选择随机超时？A.假设所有节点都有固定的超时时间。因此，在没有领导者的情况下，它们同时超时并且无法保证领导者选举，因为该过程可以重复多次或无限期地并且所有节点再次开始倒计时相同的超时值。所以随机化在这里有帮助。如果领导者仍未确定，则该过程会以跨节点的一组新的随机超时重新开始，最终我们将拥有一个领导者。经过一两次试验，我们不太可能没有选择领导者。

终生期限

当集群中没有领导者并且节点X超时时，它会启动一个新的选举期限，T通过添加1上一个任期的值来增加其任期。提醒您一下——术语是由所有节点管理的本地计数器。这里又有2个案例：

• 如果X被选为新的领导者，任期T继续，即；添加到领导者X和此后的所有新日志条目都使用 term 传播给追随者T。
• X输掉选举，新的选举开始于新的任期Uwhere U > T。

因此，从图形上看，术语图如下所示：