https://mp.weixin.qq.com/s/5GJIGx7aeHpDdPCs4jyE2Q
本篇文章为Raft系列文章中的第一篇，Raft的介绍。整个系列文章描述了Raft分布式共识算法及其在Go中的完整实现。

Raft是一种相对较新的算法（2014），但是它在业界已经被大量使用。最为大家所熟知的当属K8s，它依赖于Raft通过etcd分布式键值存储。

本系列文章的目的是描述Raft的功能齐全且经过严格测试的实现，并捎带介绍Raft的工作方式。我们假设读者至少了解过Raft相关文章。

不要指望在一天内完全掌握Raft。尽管它的设计比Paxos更易于理解，但Raft仍然相当复杂。它要解决的问题-分布式共识-是一个难题，因此解决方案的复杂性自然有一个下限。

1

复制状态机

分布式共识算法可以看作是解决跨多个服务器复制确定性状态机的问题。状态机一词用来表示任意服务；毕竟，状态机是计算机科学的基础之一，并且一切都可以用它们来表示。数据库，文件服务器，锁服务器等都可以被认为是复杂的状态机。

考虑一些由状态机表示服务。多个客户端可以连接到它并发出请求，并期望得到响应：

只要执行状态机的服务器是可靠的，系统就可以正常工作。如果服务器崩溃，我们的服务将不可用，这可能是不可接受的。通常，我们系统的可靠性取决于运行它的单个服务器。

提高服务可靠性的一种常见方法是通过复制。我们可以在不同的服务器上运行服务的多个实例。这样就创建了一个集群，这些服务器可以协同工作以提供服务，并且任何一台服务器崩溃都不应导致该服务中断。通过消除会同时影响多台服务器的常见故障模式，将服务器彼此隔离进一步提高了可靠性。

客户端将跟整个集群请求服务，而不是单个服务器来执行服务。此外，组成集群的服务副本必须在它们之间进行通信以正确复制状态：

图中的每个状态机都是服务的副本。其思想是所有状态机都以锁步的方式执行，从客户端请求中获取相同的输入并执行相同的状态转换。这样可以确保即使某些服务器出现故障，它们也可以将相同的结果返回给客户端。Raft就是实现此目的的算法。

介绍一些相关名词：

服务：是我们正在实现的分布式系统的逻辑任务。例如，键值数据库。

服务器或副本：一个启用raft的服务实例，它运行在一台与其他副本和客户端有网络连接的隔离机器上。

集群：一组Raft服务器进行协作以实现分布式服务。典型的群集大小为3或5。

2

共识模块和Raft日志

作为一种通用算法，Raft并没有规定如何使用状态机实现服务。它旨在实现的功能是可靠，确定性地记录和再现状态机的输入序列（在Raft中也称为命令）。给定初始状态和所有输入，就可以完全精确地重放状态机。另一种思考方法：如果我们从同一状态机获取两个单独的副本，并从相同的初始状态开始为它们提供相同的输入序列，则状态机将以相同的状态结束并产生相同的输出。

这是使用Raft的通用服务的结构：

关于该组件的更多细节：

状态机与我们上面看到的相同。它表示任意服务；在介绍Raft时，键值存储是一个常见例子。

日志是存储客户端发出的所有命令（输入）的地方。命令不直接应用于状态机；相反，当它们已成功复制到大多数服务器时，Raft将应用它们。而且，该日志是持久性的——它保存在稳定的存储中，可以在崩溃后幸免，并且可以用于在崩溃后回放状态机。

共识模块是Raft算法的核心。它接受来自客户端的命令，确保将它们保存在日志中，与集群中的其他Raft副本一起复制它们（与上图中的绿色箭头相同），并在确信安全时将它们提交给状态机。提交到状态机后会将实际更改通知客户。

3

领导者和追随者

Raft使用了一个强大的领导模型，其中集群中的一个副本充当领导者，其他副本充当追随者。领导者负责根据客户的请求采取行动，将命令复制到追随者，并将响应返回给客户。

在正常操作期间，追随者的目标是简单地复制领导者的日志。如果领导者发生故障或网络分区，则一个追随者可以接管领导权，因此该服务仍然可用。

该模型有其优缺点。一个重要的优点是简单。数据总是从领导者流向跟随者，只有领导者才能响应客户请求。这使得Raft集群更容易分析、测试和调试。一个缺点是性能——因为集群中只有一台服务器与客户机通信，这可能成为客户机活动激增时的瓶颈。答案通常是：Raft不应该用于高流量的服务。它更适合于一致性非常重要的低流量场景，但可能会牺牲可用性——我们将在容错一节中介绍。

4

客户端交互

前面说过：客户端将和整个集群通信，而不是和单个服务器通信来执行服务。什么意思呢？集群只是通过网络连接的一组服务器，那么将如何和整个集群通信？

答案很简单：

在使用Raft集群时，客户端知道集群副本的网络地址。

客户端最初向任意副本发送请求。如果该副本是领导者，它将立即接受请求，并且客户端将等待完整的响应。此后，客户端会记住该副本是领导者，而不必再次搜索它（直到出现某些故障，例如领导者崩溃）。

如果副本表示不是领导者，则客户端将尝试另一个副本。此处可能的优化是，跟随者副本可以告诉客户端哪个其他副本是领导者。由于副本之间不断进行通信，因此通常知道正确的答案。这样可以为客户端节省一些猜测的时间。在另一种情况下，客户端可能意识到与其通信的副本不是领导者，如果在一定的超时时间内未提交其请求。这可能意味着它通信的副本实际上不是领导者（即使它仍然认为是副本）——可能已经从其他Raft服务器中被分隔出来了。超时结束后，客户端将继续寻找其他领导者。

在多数情况下，第三点中提到的优化是不必要的。通常，在Raft中区分“正常运行”和“故障情况”很有用。很典型的服务将花费其99.9％的时间用于“正常运行”，该情况下，客户知道领导者是谁，因为首次跟该服务通信时就缓存了此信息。故障场景——我们将在下一节中进行详细讨论——肯定会造成混乱，但只是一小段时间。正如我们将在下一篇文章中详细了解的那样，一个Raft集群将很快地从服务器的临时故障或网络分区中恢复——在大多数情况下，恢复间隔只有一秒钟。当新的领导者声明其领导权并且客户找到它是哪台服务器时，将会出现短暂的不可用状态，但是之后它将返回到“正常操作模式”。

5

Raft中的容错和CAP原则

让我们回顾一下这次没有连接客户端的三个Raft副本的示意图：

在集群中，我们可以预料到哪些故障?

现代计算机中的每个组件都可能发生故障，但是为了使讨论更加容易，我们将运行Raft实例的服务器视为原子单元。这给我们带来了两种主要的失败类型：

服务器崩溃，其中一台服务器在一段时间内停止响应所有网络流量。崩溃的服务器通常会重新启动，并可能在短暂中断后恢复联机。

一种网络分区，其中一个或多个服务器由于网络设备或传输介质的问题而与其他服务器和/或客户端断开连接。

从服务器A与服务器B进行通信的角度来看，B崩溃与A和B之间的网络分区是无法区分的。它们都以相同的方式表现出来——A停止接收来自B的任何消息或响应。在系统级看来，网络分区要隐蔽得多，因为它们会同时影响多台服务器。在本系列的下一部分中，我们将介绍一些由于分区而引起的棘手的情况。

为了能够优雅地处理任意网络分区和服务器崩溃，Raft要求群集中的大多数服务器都可以启动，并且领导者可以在任何给定的时刻使用它来取得进展。对于3台服务器，Raft可以容忍单个服务器故障。如果有5台服务器，它将容忍2台；对于2N + 1台服务器，它将容忍N个故障。

这就引出了CAP定理，它的实际结果是，在存在网络分区的情况下，我们必须权衡可用性和一致性。

在权衡中，Raft处于一致性阵营中。其不变量旨在防止群集可能达到不一致状态的情况，在这种情况下，不同的客户端将获得不同的答案。为此，Raft牺牲了可用性。

正如前面所说，Raft并不是为高吞吐量，细粒度的服务而设计的。每个客户端请求都会触发大量工作——Raft副本之间的通信，以将其复制到大多数副本并持久化；在客户得到回应之前。

因此，例如，我们不会设计一个所有客户端请求都通过Raft进行复制的数据库。那就太慢了。Raft更适合粗粒度的分布式原语——例如实现锁服务器，选举高层协议的领导者，在分布式系统中复制关键配置数据等等。

6

为什么选择Go

本系列中介绍的Raft实现是用Go编写的。从作者角度来看，Go具有三个强大的优势，这使其成为本系列以及一般网络服务的有希望的实现语言：

并发性：像Raft这样的算法，本质上是深度并发的。每个副本执行正在进行的操作，运行定时事件的计时器，并且必须响应来自其他副本和客户端的异步请求。

标准库：Go具有功能强大的标准库，可以轻松编写复杂的网络服务器，而无需导入和学习任何第三方库。特别是在Raft的情况下，第一个必须回答的问题是“如何在副本之间发送消息？”，许多人陷入设计协议和某些序列化或使用繁重的第三方库的细节中。Go仅具有net/rpc，它是用于此类任务的足够好的解决方案，它的建立速度非常快，并且不需要导入。

简便性：即使在我们开始考虑实现语言之前，实现分布式共识也已经足够复杂。可以用任何一种语言编写清晰，简单的代码，但是在Go语言中，这是默认的习惯用法，并且该语言在每个可能的级别上都反对复杂性。

7

下一步

如果文章中有什么问题，可以在下方留言。从概念上讲，Raft在表面上看似简单，但是一旦我们进入代码，就会遇到很多陷阱。该系列的后续部分将提供有关该算法各个方面的更多详细信息。