Raft实现(1)：介绍

本文是介绍Raft分布式共识算法及其Go完整实现系列文章中的第一篇。以下是完整的列表:

• 第1部分：介绍(本文)
• 第2部分:选举
• 第3部分:命令和日志复制
• 第4部分:持久性和优化

Raft是一个相对较新的算法（2014年被实现），但它已经在工业中得到了广泛的应用。最知名的例子可能是Kubernetes，它通过etcd分布式键值存储依赖Raft。

本系列文章的目标是介绍一个功能完整且经过严格测试的Raft实现，并提供一些关于Raft如何工作的例子。这些并不是学习Raft的唯一资源。我猜你至少读过一次《Raft》的论文；此外，我强烈建议你花点时间仔细阅读Raft网站上的资源——观看一两个原作者的演讲，以及raft的可视化演示，以及浏览Ongaro的博士论文了解更多细节。

不要期望在一天内完全掌握Raft。尽管它的设计比Paxos更容易理解，但《Raft》仍然相当复杂。它要解决分布式共识问题——是一个困难的问题，所以解决方案的复杂性有一个自然的下限。

状态机副本

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

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

只要执行状态机的服务器是可靠的，这个系统就能正常工作。如果服务器崩溃，我们的服务变得不可用，这可能是不可接受的。一般来说，我们的系统和运行它的单个服务器一样的可靠程度时一样的。

提高服务可靠性的常用方法是通过复制(副本)。我们可以在不同的服务器上运行服务的多个实例。创建一个协同工作的服务器集群来提供服务，任何一个服务器崩溃都不会导致整个服务不可用。通过服务器之间的隔离，是消除同时影响多个服务器的常见故障的方法，进一步提高了可靠性。

客户端不再和单个服务器通信来执行服务，而是和整个集群通信。此外，组成集群的服务器必须彼此通信，以正确地复制状态:

图中的每个状态机都是服务的副本。其思想是，所有状态机都是同步执行的，从客户端请求中获取相同的输入并执行相同的状态转换。这确保了即使某些服务器出现故障，它们也会向客户端返回相同的结果。Raft是一个实现这一功能的算法。

这里需要对本系列文章将反复使用的一些术语进行介绍:

• service：是正在实现的分布式系统的提供的服务。例如，键值数据库。
• Server和Replica：通过网络连接运行raft算法的服务器，能为客户度提供相应的服务。
• cluster：一组协同实现分布式服务的Raft服务器。典型的集群大小是3或5。

共识模块和Raft日志

下面介绍上图中显示的状态机内部情况。Raft是一种通用算法，它并不规定服务如何在状态机中实现。它的目标是能够可靠地、确定地记录并将输入序列(在Raft中也称为命令)复制到状态机。给定一个初始状态和所有输入，可以完全准确地重放状态机。换句话说：如果我们取相同状态机的两个独立副本，并从相同的初始状态开始为它们提供相同的输入序列，那么状态机将以相同的状态结束，并在此过程中产生相同的输出。
以下是使用Raft的通用服务的结构:

关于这些组件的更多细节:

• 状态机与我们上面看到的状态机相同。它代表了任意服务；键值存储是说明Raft时的一个常见示例。
• 日志是存储客户端发出的所有命令(输入)的地方。这些命令不会直接应用到状态机；相反，Raft会在它们被成功复制到大多数服务器时执行它们。此外，该日志是持久性的——它保存在未发生故障服务器存储上，并可用于在崩溃后恢复状态机。
• 共识模块是Raft算法的核心；它接受来自客户端的命令，确保将它们保存在日志中，将它们复制到集群中的其他Raft服务器上(与上一个图中的绿色箭头相同)，并在确认状态机安全时将它们提交到状态机。提交到状态机并通知客户端请求结果。
  如果你还不是很清楚，不要担心。本系列剩下的文章将详细解释其中的内容!

领导者和跟随者（leaders和followers）

Raft使用了一个强领导者模型，其中集群中的一个副本作为领导者，其他副本作为跟随者。领导者负责响应客户的请求，将命令复制给跟随者，并将响应返回给客户。

在正常操作期间，跟随者(follower)的目标只是简单地复制领导者的日志。在领导者故障或网络分区的情况下，一个跟随者可以接管领导者，服务仍然可用。

这个模型有其优点和缺点，一个显著的优点是简单。数据总是从领导者流向跟随者，只有领导者才会回应客户端的请求。这使得Raft集群更容易分析、测试和调试。缺点是性能——由于集群中只有一个服务器与客户端通信，这可能成为客户端请求激增时的瓶颈。对此问题的答案通常是，Raft不应该用于大流量的服务。它更适合一致性至关重要、低流量的场景，但可能会牺牲可用性——我们将在容错一节说明这一点。

客户端交互

之前，说过“客户端不再联系单个服务器来请求服务，而是联系整个集群”;但这意味着什么呢？集群只是通过网络连接的一组服务器，那么如何联系“整个集群”呢？
答案很简答：

• 当使用Raft集群时，客户端知道集群副本的网络地址。它是如何知道这一点(例如，通过使用某种服务发现机制)这些超出了本文的讨论范围。
• 客户端首先向任意副本服务端发送请求。如果这个副本是leader，它立即确认请求，客户端将等待完整的响应。在此之后，客户端记住这个副本是leader，就不必再搜索它了(直到出现失败，比如leader崩溃)。
• 如果副本服务端返回它不是leader，客户端将尝试另一个副本。这里一个可能的优化是，一个follower副本可以告诉客户端哪个副本是leader。由于副本之间不断地通信，通常知道leader是哪个。这可以节省客户端几次通信。
• 另一种情况是，如果请求在某个超时时间内没有提交，客户端会意识到它所请求的副本不是leader。(如果它仍然认为它是)——它可能已经从其他Raft服务器中被分区了。当超时结束时，客户端将继续搜索另一个leader。

第三个要点中提到的优化在大多数情况下是不必要的。一般来说，在Raft中区分“正常操作”和“故障场景”是很有用的。一个典型的服务将花费99.9%的时间在“正常操作”中，在“正常操作”中，客户端知道谁是领导者，因为在第一次联系服务时缓存了这些信息。故障场景——我们将在下一节中更详细地讨论——肯定会麻烦点，但只会持续很短的时间。我们将在下一篇文章中详细了解到，Raft集群可以非常迅速地从临时服务器故障或网络分区中恢复——在大多数情况下，恢复时间不到一秒钟。当在新的领导者选举成功之前，服务将会有短暂的不可用，但之后它将回到“正常运行模式”。

Raft中的容错和CAP定理

让我们回顾一下三个Raft副本的状态图，没有连接客户端:

在这个集群中，我们可能会遇到哪些类型的故障?
现代计算机中的每个组件都可能发生故障，但为了让讨论更容易一些，我们将运行Raft实例的服务器视为一个原子单元。只留下两种主要的失败类型:
1、服务器故障：其中一个服务器停止响应所有网络流量一段时间。故障的服务器通常会重新启动，并可能在短暂中断后恢复联机。
2、网络分区：由于网络设备或传输介质出现问题，一个或多个服务器与其他服务器和/或客户端断开连接。

从服务器A和服务器B通信的角度看，B服务器故障的话，在A和B之间是无法区分的。表现形式都一样-A停止接收来自B的消息。从系统级别的角度看，网络分区很难处理，因为同时影响多个服务器。在本系列的下一部分中，我们将讨论由于分区而产生的一些棘手的场景。

为了能够优雅地处理任意的网络分区和服务器故障，Raft要求集群中的大多数服务器在任何给定的时刻都处于可用状态，这是为了能够实现选举。对于3个服务器，Raft可以容忍单个服务器故障。如果有5个服务器，它可以容忍2个；对于2N+1个服务器，它可以容忍N个服务器故障。

这就引出了CAP定理，其实际结果是，存在网络分区(这是现实中不可避免的一部分)的情况下，我们必须小心地平衡可用性和一致性。在这种平衡中，Raft坚定地站在一致性阵营。它的宗旨是防止集群可能出现不一致的状态，即不同的客户端接收到不同的结果。为了实现这一目标，Raft牺牲了可用性。

正如我前面提到的，Raft不是为高吞吐量、细粒度服务而设计的。每个客户端请求都会触发相当多的工作——Raft服务器之间的通信，以便将其复制到大多数跟随者，并将其持久化；这一切都发生在客户端得到响应之前。

因此，你不会设计一个多副本数据库，让所有客户端请求都通过Raft，那就太慢了。Raft更适合于粗粒度的分布式原语——比如实现锁服务器、为更高级别的协议选择领导者、在分布式系统中复制关键配置数据等等。