Raft in Tarantool：它的工作原理和使用方法

去年，我们在Tarantool中引入了同步复制。我们在这个过程中遵循了Raft算法。该任务由两个主要阶段组成：所谓的仲裁写入（即同步复制）和自动领导者选举。

同步复制首先在2.5.1版中引入，而2.6.1版支持基于Raft的自动队长选举。

我叫谢尔盖·佩特连科，我参与了这些大功能的开发。今天，我将告诉你它们是如何工作的。我将介绍如何配置队长选举，以及基于Raft的算法允许Tarantool用户做的一些新事情。

1.简而言之，复制

在深入研究我们的队长选举算法之前，让我们回答这个问题：为什么需要这些算法？

在多个节点组成的集群中，需要选择一个领导者，节点之间需要进行复制-数据同步。如果您已经熟悉复制，可以转到下一节。

复制有两种类型：异步复制和同步复制。

异步复制

这种类型的复制是一种事务，在登录到主机时立即确认，然后发送到副本。它非常快。

此外，具有异步复制的集群不会失去可访问性，无论有多少副本失败。只要主机正常工作，提交事务的能力就会保持不变。

但速度和可访问性的代价是可靠性。如果主服务器出现故障，其上提交的某些事务可能无法发送到任何副本，因此将丢失。

异步复制如下所示：

主人在左边。它在记录事务后立即用“ok”响应客户机。

或者像这样：

主人在左边。它对客户端的响应是一切正常，但随后它崩溃了，并且该事务不存在于任何其他节点上。

同步复制

在同步复制的情况下，事务首先发送到副本，然后从多个副本中收集确认，只有在主副本提交事务时。这种复制相当可靠。如果主服务器出现故障，则保证其确认的所有事务至少存在于一个副本上。

不幸的是，它也有一些缺点。首先，集群的写可用性受到影响：如果足够多的副本失败，主机将失去应用事务的能力，因为它无法再收集仲裁。此外，记录事务和确认事务之间的延迟远远超过异步复制。在登录之后，主服务器还必须将事务发送到副本并等待它们的响应。

同步复制如下所示：

主人在左边。在向客户端发送响应之前，它将数据发送到复制副本并等待其响应。

无论发生什么情况，通过同步复制，您都不会丢失已确认的数据：

即使主服务器出现故障，副本仍拥有事务

同步复制的关键概念是仲裁。在确认事务之前，主节点确保已将其发送到仲裁节点并可应用于这些节点。可以配置仲裁的大小。例如，如果仲裁等于2，则在提交事务之前，事务必须至少在主服务器旁边的一个副本上。

2.队长和队长选举

在本文中，领导者和大师的意思相同。它是一个可以应用事务并将它们复制到集群中其他节点的节点。

如果现任队长失败了，我们该怎么办？我们需要指派一位新的队长。几个队长不能当选；我们只希望一个节点成为信息源。否则，将需要额外的努力来避免不同节点上应用的事务之间的冲突。

那么，我们如何选举一位队长？有两种方法可以做到这一点。第一种方法是，所有复制副本都可以等待，直到某个外部设备在引导失败后为其分配一个引导。它可以是将一个节点从只读模式切换到读写模式的管理员，也可以是管理复制的外部工具。在这种情况下，可以指定一个领导者，但需要一些额外的步骤，集群停机时间将非常长。

让我解释一下我的意思：如果领导失败，新当选的领导必须包含适用于旧领导的所有事务。由于领导者是真相的来源，没有交易将意味着数据被确认，然后就消失了。这对于同步复制尤其重要。没有任何节点可以成为领导者。它一定是最不落后于老主人的。下一步必须应用旧领导没有确认的所有同步事务。我们必须等到它们被复制到节点仲裁中，然后发送这些事务的确认。

换句话说，有很多工作，我们不想手动完成。

另一种选择是教导集群节点就其中哪一个成为新的领导者达成一致。这就是我们想到选举算法的地方。节点必须通过相互通信来选择新的领导者。然后，新当选的领导必须确认旧领导剩余的所有同步事务。也就是说，自动完成上述所有工作。这种解决方案的优点是最大限度地减少领导节点故障后的停机时间。缺点是需要选择和实现队长选举算法。尽管后者可能只对我们的团队有意义。

幸运的是，我们不必重新发明轮子。我们决定实现Raft——一种著名而可靠的算法。

3.Raft算法

Raft包括同步日志复制和领导者选举，保证在集群生命周期的任何阶段都可以选择单个领导者。

通常，集群看起来是这样的：一个节点处于领先状态，可以写入日志、应用事务等。所有其他节点都处于跟随状态，并应用从领先节点接收的所有内容。如果跟随者通过通信信道接收到来自非领导者的事务，则忽略该事务。

协议中负责日志复制的部分相当清楚。当前领导者向所有集群节点发送带有新条目的AppendEntries请求。当超过一半的集群成员成功应用了领导者发送的条目时，这些条目被视为已确认。

我们将在本文中看到的协议的另一部分涉及队长选举。

以下是Raft算法的简要说明，需要进一步叙述。您可以阅读原始文章了解更多详细信息。

集群的整个生命周期被划分为称为术语的逻辑块。他们用从一开始的整数编号，每个任期从选举新队长开始。一旦选择了领导者，它将接受请求并记录新条目，并进一步发送给集群的其余成员。

对于要选出的节点，群集中超过一半的节点必须投票支持它。它保证在每个任期内，要么选出一位队长，要么根本不选。从某种意义上讲，选举可能永远不会产生一位队长。如果所有节点都已投票，但没有候选人获得多数票，则可能会发生这种情况。在这种情况下，新的任期将开始，新的选举将举行。所有节点将再次投票。因此，其中一个节点迟早会成为领导者。

在Raft中，每个节点可以处于三种状态之一：跟随者、候选者或领导者。

跟随者是一种状态，其中节点只能响应来自领导者的附加条目和来自候选人的请求投票请求。如果追随者很长一段时间（在所谓的选举超时期间）没有收到队长的任何消息，那么他将进入候选人状态，开始新的任期和新的选举。

候选节点是发起新选举的节点的状态。在这种情况下，节点为自己投票，然后向集群的所有成员发送RequestVote请求。对该请求的响应是VoteGranted字段，如果节点投票给候选人，则该字段设置为true。候选人本身从不响应其他候选人的投票请求。它已经投了自己的票，不投别人的票。候选人为其计票。一旦在群集中的所有节点中有超过一半的投票支持它，候选人就成为领导者。它通过发送一个空请求AppendEntries（一种只有领导者才能发送的心跳信号）向其他节点报告。

如果从选举开始以来，选举超时时间已经过去，并且没有收集到所需的票数，这可能意味着没有人获得足够的选票。在这种情况下，候选人通过增加其任期并将RequestVote请求重新发送给其他节点来发起新的选举。为了避免无休止的重选循环，每个节点上的选举超时都会稍微随机化。这样，迟早会有一名候选人率先发起新的选举并获得所需票数。

引线是节点可以写入日志的唯一状态。领导使用AppendEntries请求复制此日志。此外，当没有新的请求到达时，领导者会定期发送心跳-空的请求-以避免超时和新的提名。

如果领导者或候选人突然从其中一个节点得知一个新术语已经开始（大于他们所在的术语），它将立即成为追随者。之后，选举超时从一开始就开始计数。

日志仅包含当前术语的编号和该术语中的语音广播。这对于防止节点在重新启动后重新投票是必要的。

未记录节点状态。重新启动后，节点始终处于跟随器状态。

4.我们的同步复制实现

Raft协议中负责日志复制的部分在队长选举工作开始前三个月作为一项单独任务实施。

对于有价值数据的空间，可以单独启用同步性。则只有与此空间相关的事务将是同步的。

同步事务在应用之前等待副本仲裁的确认。也就是说，首先必须对其进行记录，然后将其发送到副本仲裁，副本仲裁必须确认接收到事务。只有这样，交易才能完成并应用。

如果事务在指定的时间间隔内（可配置，请参见下文）未达到法定人数，则将通过超时回滚。

Tarantool日志的特殊之处在于它只存储重做条目，而不存储撤消条目。这意味着重新启动后，日志只能从头到尾重放，重复所有应用的事务。但是，日志不能不可见-也就是说，写入日志的应用事务无法撤消。日志根本不具备执行此操作所需的功能。它使原木更紧凑。回滚事务所需的结构存储在内存中，如果是异步复制，则在成功写入日志后立即释放。在同步复制的情况下，在事务由节点仲裁确认后，或者在事务通过超时回滚后，释放它们。

我们的日志是仅附加的。回滚事务时，您不能仅从中删除额外的条目。此外，由于事务已发送到副本，我们现在需要告诉他们它已回滚。由于日志的特殊性，所有事务都会记录到日志中，包括同步和异步事务。这意味着，在一段时间内，日志包含同步事务，我们不知道它们是否得到确认。

因此，需要一种新的日志条目类型—回滚。主服务器在等待副本的确认时一超时，它就用回滚事务的LSN（日志序列号）记录一个回滚条目。与日志中的所有其他条目一样，此条目将转发到副本。收到此类条目后，复制副本回滚失败的同步事务以及具有较大LSN的所有事务。由于存储在其内存中的撤消日志，复制副本可以执行此操作。大师也是这样做的。
如果收集了收到事务的副本的仲裁，则需要告知副本事务已被确认。首先，它将让他们清除撤消日志。其次，当从日志中恢复时，他们需要关于哪些事务被应用，哪些事务未被应用的信息。为此，在日志中添加了另一个服务条目-确认。

Tarantool中的复制是通过逐行将条目从主日志传输到副本来实现的。因此，确认和回滚条目对我们帮助很大：有关同步事务确认或回滚的消息通过常规复制通道传递给复制副本。不需要弄清楚主机将如何向它们发送系统消息。它只是从日志中读取它们，并将它们作为正常数据发送。此外，复制副本可以将接收到的服务消息原封不动地写入其自己的日志中，从而允许它们正确恢复，而忽略已取消的同步事务。

在开发过程中，我们可以采用另一种方法：首先，将事务发送到副本，然后仅当事务应用于副本仲裁时，才将其写入主日志。但我们仍然会遇到一些困难。如果事务已被取消，则仍需要告知副本。此外，在某些情况下，事务可能应用于副本，然后主机可能会失败，并在重新启动后忘记它。在提前登录的情况下，主机可能无法自动应用未确认的事务，但至少不会丢失它。

因此，所有事务（同步和异步）都记录在预写日志（WAL）中。成功写入后，异步事务会立即提交，而同步事务会进入一个特殊的队列-limbo，等待复制到节点仲裁中。当达到确认的法定人数时，提交事务，并将确认条目写入日志。如果等待确认超时，将向日志写入回滚条目，并回滚该事务以及队列中紧随其后的所有事务。

应该注意，如果同步事务队列不是空的，那么异步事务在提交之前也会进入队列。它们不等待确认，但必须在队列中等待，以便在同步事务未收集仲裁的情况下回滚。这是必要的，因为同步事务可以更改同步空间和常规空间中的数据。因此，访问相同空间的异步事务将依赖于此同步事务。

默认情况下，当事务在队列中时，其他事务将看到它们的更改。这个问题称为脏读，为了避免它，您需要启用事务管理器。在乙烯基（Tarantool磁盘引擎）中，事务管理器始终处于启用状态，而在memtx（在内存中存储数据的引擎）中则是通过Alexander Lyapunov的努力实现的，他将在文章中介绍这一点。

5.使Raft适应我们的复制协议

在Tarantool中，副本集节点之间的所有通信都通过两个实体进行：发送数据的relay和负责接收数据的applier。在Raft之前，中继的唯一工作就是发送日志条目。实现同步复制后，只需将系统消息写入日志，就可以将其发送到所有副本。我们甚至不需要为relay添加任何附加功能。它继续将日志条目转发到副本，就像以前一样。同时，必须教会应用程序使用者如何处理从主机继电器接收到的系统消息。

在Raft算法实现的情况下，这个小小的特技效果不太好。问题在于，首先，并非所有筏系统信息都应写入日志，因此继电器将无处读取这些遗漏的信息。其次，即使是进入日志的消息，即当前项的数目和节点的投票数，也不应该由副本自动应用。它必须接收有关术语变化和投票的信息，但不必像其他节点那样投票。因此，有必要教导relay根据请求向副本发送任意消息。它在日志的发送部分之间执行此操作。

在Raft的队长选举阶段，会发送大量附加信息：候选人的投票请求和追随者的投票。该信息不应存储在日志中；根据协议，只有当前项和该节点在当前项中投票的候选项存储在那里。Raft模块本身在tx线程中运行，tx线程是处理事务的线程。根据Raft，状态的每次变化（即状态的持续部分、术语和节点的投票）都应记入日志。记录新状态后，可以将其传递给其他副本。为此，tx向所有线程发送一个中继消息，其中包括非持久性信息-Raft集群中节点的角色，以及该节点的vclock（可选）。然后，每个继电器将此信息发送到与其连接的副本，副本将其发送到其Raft模块。

在Raft中，节点日志的状态（即节点上存在的数据）可以由单个数字表示-日志条目的数量，称为日志索引。在Tarantool中，它的模拟值是日志序列号（LSN），这是分配给每个事务的序列号。

不同之处在于，在Tarantool中，日志的状态不是单个数字，而是一个称为vclock的LSN数组。这是一种从异步主机到主机的传统复制，所有节点都可以同时写入。来自每个节点的事务不仅由LSN签名，还由节点的ID签名。

集群的所有节点在vclock中都有自己的组件。记录来自另一个节点的事务后，复制副本将事务的序列号分配给其vclock组件。在一个由三个节点组成的集群中，其中一个副本的vclock可以如下所示：｛1:11、2:13、3:5｝。这意味着该节点包含来自节点1的序列号最多为11的所有事务，来自节点2的序列号最高为13的所有事务。并且（假设我们正在查看节点3的vclock），该节点本身只记录了5个事务。

由于vclock，我们不得不对Raft实现进行一些调整。首先，默认情况下，该算法始终可以通过比较日志索引来确定哪个节点拥有最新的数据。然而，在我们的实现中，我们需要比较vclock，这可能是不可比较的，例如，｛1:3，2:5｝和｛1:4，2:1｝。这不是一个严重的问题，但因此，节点只会投票给vclock严格大于或等于其自身的候选节点。

如前所述，在Tarantool中，日志不是撤销日志，而是重做日志，仅附加日志。这本身增加了复杂性。即使大多数节点投票给候选人，少数节点可能拥有来自前一位队长的最新数据。由于集群的状态现在由一位新队长控制，这一少数群体无法继续工作。您需要删除这些节点的数据并将它们重新连接到集群。这称为重新加入。这个问题在Raft算法中没有出现，因为少数人只是简单地切断他们的日志的末端以匹配领导者的日志。

6.配置Raft

6.1.节点运行模式

对于要参与领导者选举的节点，必须在其配置中设置election_mode选项。

 box.cfg{
        election_mode = "off", -- default value
    }

election_ mode可以设置为以下值之一：

• “关闭”-救生筏不工作。在这种情况下，节点将接收并记住当前术语的编号。这对于节点在筏板开启时立即加入集群的正常操作是必要的。

• “选民”-节点将投票给其他候选人，但永远不会开始选举并提名自己。此类节点可用于限制可从中选出领导者的节点数量。假设您将一个由三个节点组成的集群：两个候选节点和一个投票节点。然后，如果队长失败，第二位候选人将通过获得多数票（三分之二——自己的票和选民节点的票）立即赢得选举。

  • 如果您需要在不关闭领导的情况下强制领导辞职，此设置也很有用。如果当前队长被重新配置为“选民”，那么它将立即变成只读，并停止向追随者发送心跳。选举超时后，追随者将开始新的选举，并选择另一个节点作为领导者。

• “候选人”-节点可以在检测到没有队长时立即开始选举。此外，该节点可以投票给其他候选人，但前提是它在当前任期内尚未投票给自己。

如上所述，集群的生存期被划分为称为项的时间间隔。术语用从1开始的整数编号。新的任期从新的选举开始。因此，在每一届选举中，要么选出一位队长，要么没有人能够赢得选票。条款还防止同一节点在同一次选举中投票两次。在当前选举中投票后，节点不仅会记住投票已被投票，还会将该投票写入日志。随着新选举的开始（以及新任期的开始），投票将重置为零，这允许节点再次投票。

Raft有一项队长选举要求：法定人数为N/2+1票，同时禁止每次选举投票超过一次。这确保了只有一个节点可以赢得选举。

三个集群节点在两项中的状态。在t1任期内，s1成为领先者，因为它是第一个发出投票请求的人。当s1失败时，s2是第一个注意到的。它也是第一个发出投票请求的人，并成为t2任期的领导者。当s1返回时，它成为了一个简单的追随者

如果节点的日志更新或等于节点的日志，则节点将投票给第一个发送投票请求的候选人。为了找出哪一个节点更新，将比较它们的vClock。只有当候选人的每个vclock分量大于或等于投票人的相应vclock成分时，才会进行投票。也就是说，选民日志中的所有事务也必须在候选人日志中。

vclock-矢量时钟；显示节点上有哪些数据以及哪些数据不在节点上的结构。它是记录在此节点上的事务的序列号数组。集群的所有节点在vclock中都有自己的组件。记录来自另一个节点的事务后，复制副本将事务的序列号分配给其vclock组件。在由三个节点组成的集群中，其中一个节点的vclock可能如下：｛1:11、2:13、3:5｝。这意味着该节点包含来自节点1的序列号最多为11的所有事务，来自节点2的序列号最高为13的所有事务。并且（假设我们正在查看节点3的vclock），该节点本身只记录了5个事务。

在同步复制的情况下，如果同步事务的提交仲裁设置为至少N/2+1，投票人将选择一个日志中肯定包含所有提交的同步事务的领导者。事实上，由于交易必须到达至少N/2+1个待确认节点，并且要选出新的领导者，它需要至少收到N/2+1个节点的投票，因此该交易将记录在至少一个投票节点的日志中。因此，它将被记录在新队长的日志中。

三个集群节点在两项中的状态。在t1任期内，s1成为领先者，因为它是第一个发出投票请求的人。当s1失败时，s2是第一个注意到的。它也是第一个发出投票请求的人，并成为t2任期的领导者。当s1返回时，它成为了一个简单的追随者

6.2.重新选举超时

连任是选举的一个重要因素。它允许您处理没有候选人赢得法定票数的情况。它的工作原理是这样的：候选人在选举暂停期间为自己收集选票。如果尚未获得足够数量的选票，并且尚未宣布队长，候选人将开始新的选举，增加任期数。选择超时取决于配置，并在其值的10%内随机化。

选择超时可以这样配置：

box.cfg{
        election_timeout = 5, -- default value, seconds
    }

6.3.候选人的法定投票人数

节点在成为领先者之前必须获得的投票数只能与同步复制仲裁一起配置。

 box.cfg{
        replication_synchro_quorum = 1, -- default value
    }

在同步复制的情况下，1以外的任何值都有意义。应用事务的节点的仲裁计算如下：1用于在主机上成功记录事务+1用于应用事务的每个副本。

值为1表示禁用同步复制，因为事务登录到主机后将立即达到仲裁。

对于领导者选举，仲裁值不能设置为小于N/2+1，其中N是群集中投票节点的数量-不是所有节点，而是投票节点，配置为election_mode='candidate’或election_ mode=‘选民’。否则，在第一次选举中，可能会选出几位队长。

为了正确地向集群添加新的投票节点，您需要执行以下操作：

• 使用副本的election_mode='off’将副本连接到集群。

• 等待复制副本初始化并开始正常工作。

• 如有必要，增加replication_synchro_quorum，使其不小于N/2+1（N是投票节点数+新副本数）。

• 通过设置election_mode='voter’或’candidate’在副本上启用Raft。

• 如果添加了无表决权副本，则无需更新仲裁。

• 如果需要从集群中删除投票副本，则需要先禁用它，然后才减少仲裁，但不能低于N/2+1的值。

6.4.即将更新

我们理解，上述过程非常不方便，并且容易出现人为错误。很快，在版本2.6.2和2.7.1中，可以指定一个公式来计算配置中的仲裁。在这种情况下，仲裁将在每次将节点添加到集群或从集群中移除时自动更新。它看起来像这样：

 box.cfg{
        replication_synchro_quorum = "N / 2 + 1", -- default value
    }

每当从_ cluster空间插入或移除节点时，仲裁将根据公式进行更新，该空间存储有关集群中注册的所有节点的信息。该公式将被N参数取代，该参数等于_ cluster空间中的记录数。同步复制仲裁和投票仲裁都将使用此公式。

请注意，其中一个节点的故障不会导致仲裁的更改。要降低仲裁，需要从_cluster空间中删除节点。Tarantool从不单独从_ cluster中删除节点，只有管理员才能这样做。

7.Raft群监测

要监视Raft的状态，可以使用表box.info.election。它看起来像这样：

 box.info.election
    ---
    - state: leader
      vote: 1
      leader: 1
      term: 2
    ...

哪里：

• 状态=当前节点的状态；可能的选项有跟随者、领导者、候选人或无。

• 术语=当前术语的编号。

• leader＝在该术语中为leader的节点的副本_ id。

• 投票=该节点投票的节点的副本id。

投票和队长不必匹配。结果可能是，这个节点也是一个候选人，并为自己投票。但后来又有另一位候选人抢先一步，成为了领导者。

该表显示了节点的当前角色、任期编号、任期队长的ID以及上次选举中投票的节点ID。

此外，筏板详细记录其所有动作：

2020-11-27 14:41:35.711 [7658] main I> Raft: begin new election round
2020-11-27 14:41:35.711 [7658] main I> Raft: bump term to 2, follow
2020-11-27 14:41:35.711 [7658] main I> Raft: vote for 1, follow
2020-11-27 14:41:35.712 [7658] main/116/Raft_worker I> Raft: persisted state {term: 2, vote: 1}
2020-11-27 14:41:35.712 [7658] main/116/Raft_worker I> Raft: enter leader state with quorum 1

日志可以显示节点投票给谁，谁是其队长，以及在什么时候它自己领先。

它还记录节点所在的术语，以及在收到投票请求时为何不投票给其他节点的原因。在这些原因中，可能是选民和候选人的不可比性，也可能是现任队长已经被选中。

8.结论

Tarantool 2.6具有基于Raft算法的自动队长选举内置功能。现在您可以在不使用外部工具的情况下更改主控形状。这允许您将所有设置保存在一个位置-Tarantool配置文件。仲裁更新将很快实现自动化，进一步提高可用性。此外，内置实现的优点是更高的可靠性和对即将到来的事件的最快响应。现在，Tarantool的内置功能允许您以最小的工作量编写自动故障切换。

Lua中的详细示例项目可以在我们的示例库中找到。看一看。除了队长选举之外，它还包含许多有用的代码示例。

原文标题：Raft in Tarantool: How It Works and How to Use It
原文作者：Sergey Petrenko
原文链接：https://dzone.com/articles/raft-in-tarantool-how-it-works-and-how-to-use-it