Raft算法赏析

前言

最近抽空看了大名鼎鼎的Raft算法论文，看完后就一个感觉：如此复杂的算法居然可以设计得如此简洁、巧妙。

反复看了几遍，非常过瘾，原文不仅通俗易懂，而且非常严谨，所有异常情况都做了充分的考虑以及给出解决方案。

原文请参考这里

如何保证一致性

保证一致性，即需要保证我写入成功的数据，能够被正确读取的数据。

如果一个应用只有单个节点，我们能够比较容易实现这个特性。

但一个节点无法满足我们高可用的场景，我们需要多个节点互为备份，当单个节点故障时不影响整体服务。

一旦多于一个节点，我们就处在分布式的环境下，事情就变得复杂起来，我们需要考虑更多的因素：

• 节点之间应该如何进行数据进行同步，如何保证数据一致性？
• 如何处理不同节点并发收到同一份数据的修改请求？
• 若存在同一个数据在不同节点存在不同的值应该如何解决冲突？
• 如果新增或者删除节点要会不会影响整个集群？
• ……

如果你的应用是一个无状态应用，你无需考虑如此复杂的因素。

但我们大多数应用都是会产生数据的，保存这些数据的地方同样面临上面的问题，你只是把这个问题转移到了另一个地方，它很可能是你的数据库，比如MySQL。

在研究MySQL主从算法或则其他一致性算法时，我们先针对上面的问题想一个粗略的方案：

• 要解决并发数据修改问题，单节点我们会采取加锁方案，确保同一时刻只有一个线程操作数据。同样的，多节点之间，我们也要采取某种机制确保同一时刻只有一个节点进行所有修改操作，这个节点我们叫做领导者，而确定领导者的过程，通常叫做领导者选举

• 要解决不同节点数据同步问题，我们首先要解决领导者对写请求的数据持久化问题：

  • 要能够快速存储，保证落盘性能

  • 数据要绝对有序，才能保证领导者本地存储数据的正确性，也才能保证后续同步数据时能够做到有序增量

    咦，听着是不是有点队列的味道？我们当然不需要引入一个重量级的队列系统，我们需要的是它的核心——日志系统。

    节点数据同步，其本质就是做是日志复制，即将领导者本地的日志复制到其他节点。

• 要解决异常情况下节点之间的数据不一致的问题，我们必须要有一种解决数据冲突的策略：

  • 你肯定联想到了Git，使用新数据解决冲突。
  • 还要考虑大部分节点的数据状态。

• 要保证新增或者删除节点时整个集群的仍然可用，我们需要考虑：

  • 新增的节点同步数据时，不应该耗尽领导者所有资源

  • 删除的节点为领导者时，不应该让整个集群瘫痪

    所以成员关系调整也是我们需要重点考虑的一点。

MySQL

在深入Raft算法前，让我们先看看老牌数据库MySQL怎么解决上面的问题。

领导者选举

MySQL的领导者是由人工指定的——我们可以手工配置某一节点为主节点。

这个方案足够简单。

当然如果主节点挂了，我们也只能通过一系列人工操作进行领导者切换。

日志复制

MySQL提供了三种日志复制策略：

• 异步复制
  主库在执行完客户端提交的事务后会立即将结果返给客户端，并不关心从库是否已经接收并处理。
• 全同步复制
  当主库执行完一个事务，所有的从库都执行了该事务才返回给客户端。
• 半同步复制
  介于异步复制和全同步复制之间，主库在执行完客户端提交的事务后不是立刻返回给客户端,而是等待至少一个从库接收到并写到 relay log 中才返回给客户端

我们发现：

• 异步复制，从库无法保证数据一致性
• 全同步复制，能够保证数据一致性，但性能必然会受到严重的影响
• 半同步复制，只能保证部分从库的数据一致性

看起来好像还有不少优化的空间？

有请本文的主角Raft登场^_

领导者选举

Raft会自动选举领导者。

选举时有三个角色参与：领导者（Leader）、跟从者（Follower）和候选人（Candidate）

候选人参与选举有三种结果：成功、失败、平局

主要流程

• 当节点启动时，初始状态为跟随者身份。
• 如果一个跟随者在一段时间里没有接收到任何消息，就是选举超时，将发起选举以选出新的领导者。
• 跟随者增加自己的当前任期号并且转换到候选人状态。
• 每一个节点最多会对一个任期号投出一张选票，按照先来先服务的原则。
• 当一个候选人获得大多数选票时，将成为领导者，然后向其他节点发送心跳消息，阻止新的领导者产生。
• 如果领导者心跳消息中的任期号不小于候选人当前的任期号，那么候选人会承认领导者合法并回到跟随者状态，同时更新当前任期号为领导者的任期号。

任期号的设计，一定程度上防止旧数据的节点成为领导者。

异常情况

当出现候选人出现平局情况，如节点数量为偶数个，平局的情况可能会一直无限发生下去。

Raft 算法巧妙地使用随机选举超时时间的方法来避免这种情况，就算发生也能很快的解决。每个节点的选举超时时间都是随机决定的，一般在150~300毫秒之间，这样两个节点同时超时的情况就很罕见了。

写请求处理

主要流程

• 只有领导者拥有写请求处理权限

• 客户端发送所有请求给领导者，随机挑选一个服务器进行通信。如果挑选的服务器不是领导者，跟随者会拒绝客户端的请求并且返回领导者的信息（包含了网络地址）。若客户端的请求超时会再次重试上述过程。

  可选方案：随机挑选一个服务器进行通信。如果挑选的服务器不是领导者，跟随者将请求重定向给领导者。

• 领导者在收到写请求之后，在本地日志追加一条新的日志条目，然后并行的发起请求，让其他节点复制这条日志条目。

• 当领导者将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交当这条日志条目被安全的复制，领导者会应用这条日志条目到它的状态机中然后把执行的结果返回给客户端。

本地日志

日志由有序序号标记的条目组成。

每个条目都包含创建时的任期号和一个状态机需要执行的指令。

领导者的一个条目被大部分节点复制成功后，应用到状态机，就认为是已提交。

索引	1	2	3
任期号	1	1	2
指令	x=3	y=1	z=1

追随者同步

追随者的同步本质就是日志复制。

在正常的操作中，追随者收到领导者的新日志复制请求后，将写入本地日志；收到领导者提交日志请求后，将应用到状态机，确保两者的日志、状态机数据保持一致性。

为了减少请求次数，已提交日志位置的通知可以合并到未来的所有请求 （包括心跳请求）。

异常情况

当跟随者崩溃时，领导者可以通过无限重试，使追随者完成日志恢复。因为请求都是幂等的，所以重试不会造成任何问题。

当领导者崩溃时，各个节点日志可能处于不一致的状态，情况会变得复杂。如何得确定哪些日志已经被已提交了？你可能会想到收集各个副本（其他节点）已提交日志的信息去做决策，但这种做法在多轮领导者、追随者崩溃后，变得难以实现。

Raft使用了一种非常简洁的方法来解决这个难题——强领导者：

• 日志条目只从领导者发送给其他的服务器。
• 强制跟随者直接复制领导者的日志，冲突的日志条目会被领导者的日志覆盖。
• 领导者针对每一个跟随者维护了一个下一个需要发送给跟随者的日志条目的索引值（nextIndex ）
• 如果一个跟随者的日志和领导者不一致
  • 若跟随者日志少，领导者就会减小 nextIndex 并进行重试实现增量复制
  • 若跟随者日志多，则以领导者的日志全量覆盖

最终领导者和跟随者的日志达成一致。

那有没有可能领导者本身的数据存在问题？

Raft用两个巧妙的限制，确保被选举出来的领导者数据是新的而且是正确的：

• 选举请求包含了候选人的日志信息，投票人会拒绝掉那些日志没有比自己新的投票请求。
• 候选人为了赢得选举必须联系集群中的大部分节点，这意味着候选人的日志至少和大多数的服务器节点一样新。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义：

• 任期号不同，任期号大的日志更加新。
• 任期号相同，索引值大的日志更加新。

时间和可用性

Raft 的特性之一就是不依赖时间，选举领导者只要系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

广播时间指的是从一个服务器并行的发送请求给集群中的其他服务器并接收响应的平均时间；

平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。

广播时间必须比选举超时时间小一个量级，这样领导者才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态。

选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。

当领导者崩溃后，整个系统会大约相当于选举超时的时间里不可用。

成员关系调整

到目前为止，我们都假设集群的配置是固定不变的。但是在实践中，偶尔是会改变集群的配置的，例如替换那些宕机的机器或者改变配置。

我们的目的是为了变更时集群仍然能够保持可用。

可能存在问题

我们先将成员变更请求当成普通的写请求，由领导者得到多数节点响应后，每个节点提交成员变更日志，将从旧成员配置（Cold）切换到新成员配置（Cnew）。

但每个节点提交成员变更日志的时刻可能不同，这将造成各个服务器切换配置的时刻也不同，这就有可能选出两个领导者，破坏安全性。

考虑以下这种情况：

集群配额从 3 台机器变成了 5 台，可能存在这样的一个时间点，两个不同的领导者在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。

image

如何解决这个问题呢？

Raft提供了两种解决方案。

一阶段成员变更

如果增强成员变更的限制，假设Cold与Cnew任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。

那么如何限制Cold与Cnew，使之任意的多数派交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

一阶段成员变更：

成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。

成员变更由领导者发起，Cnew得到多数派确认后，返回客户端成员变更成功。

一次成员变更成功前不允许开始下一次成员变更，因此新任领导者在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。

领导者只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

二阶段成员变更

集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。

领导者收到从Cold切成Cnew的成员变更请求，做了两步操作：

第一阶段

• 领导者在本地生成一个新的日志条目，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该日志条目复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认
• 跟随者收到Cold∪Cnew的日志条目后更新本地日志，并且此时就以该配置作为自己的成员配置
• 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，领导者就提交这条日志条目。

第二阶段

• 领导者生成一条新的日志条目，其内容是新成员配置Cnew，同样将该日志条目写入本地日志，同时复制到跟随者上
• 跟随者收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置；如果发现自己不在Cnew这个成员配置中会自动退出
• 领导者收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。
• 领导者给客户端回复成员变更执行成功。

异常情况

如果领导者的Cold U Cnew尚未推送到跟随者，领导者就挂了，此后选出的新领导者并不包含这条日志，此时新领导者依然使用Cold作为自己的成员配置。

如果领导者的Cold U Cnew推送到大部分的跟随者后就挂了，此后选出的新领导者可能是Cold也可能是Cnew中的某个跟随者。

如果领导者在推送Cnew配置的过程中挂了，那么同样，新选出来的领导者可能是Cold也可能是Cnew中的某一个，此后客户端继续执行一次改变配置的命令即可。

如果大多数的跟随者确认了Cnew这个消息后，那么接下来即使领导者挂了，新选出来的领导者肯定位于Cnew中。

两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。

两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个领导者，才引入了两阶段方案。

添加新节点

添加一个新的节点到集群时，需要考虑一种情况，即新节点可能落后当前集群日志很多的情况，Raft针对这种情况做了以下处理：

• 添加进来的新节点首先将不加入到集群中，而是等待数据追上集群的进度。
• 领导者同步数据给新节点将划分为多个轮次，每一轮同步一部分数据，而在同步的时候，领导者仍然可以写入新的数据，只要等新的轮次到来继续同步就好。
• 同步的轮次不能一直持续，需要限制轮次数量，如最多同步10轮。

下线领导者

领导者将发出一个变更节点配置的指令，只有在该指令被提交之后，领导者才下线，最后按照标准流程进行新的一轮选举。

异常情况

如果某个节点在一次配置更新之后，被移出了新的集群，但是这个节点又不知道这个情况，那么按照前面描述的Raft算法流程来说，它应该在选举超时之后，将任期号递增1，发起一次新的选举。虽然最终这个节点不会赢得选举，但是毕竟对集群运行的状态造成了干扰。而且如果这个节点一直不下线，那么上面这个发起新选举的流程就会一直持续下去。

解决方案：如果领导者存活，则不允许发起新一轮的选举。

如何判断领导者是否存活？

如果领导者一直保持着与其它节点的心跳消息，那么就认为领导者节点是存活的。

读请求处理

读请求比写请求简单很多，可以直接处理而不需要记录日志。

但这里可需要考虑脏读问题，因为领导者可能不知道自己已经被作废了。

保证不脏读

Raft 中通过让领导者在响应读请求之前，先和集群中的大多数节点交换一次心跳信息，确保自己仍然是领导者。

如何优化性能

因为只读操作也要经过一次请求，所以它并没有我们想想的那么快，它可能和写操作性能差不多，并且不能通过扩展节点数量来得到整体集群读性能的提升，甚至不升反降。

折中方案

允许领导者不检查是否存活。

该方案适用于一致性要求不高的场景，以通过扩展节点来提升读性能。

优化方案

标准的强一致读操作是完全是在领导者进行的，优化方案可将读请求在任意节点处理：

• 跟随者接收到只读指令后，向领导者索要当前的已提交索引。
• 跟随者等待自身的状态机的提交完成后，即可以返回结果。

领导者向跟随者返回已提交索引值依然要先和集群中的大多数节点交换一次心跳信息。

这个方案可以让跟随者分担领导者的压力，让领导者有更多的资源来处理自身的读写操作。

进一步优化方案

领导者可以依赖心跳请求来实现租约机制，确保一段时间内都为某个领导者处理，但是这种方法强依赖时间来保证安全性。

日志压缩

随着数据的增长，日志会越来越大，Raft通过快照实现了日志压缩。

在快照系统中，整个系统的状态以及少量元数据以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。

image

结尾

分布式一致性的算法非常重要，在众多算法中，Raft以简单易懂脱颖而出，且在很多细节都提供了具体的实现方式，获得了越来越多开发者的关注与使用。

我们不禁遐想，如果MySQL能够使用Raft算法进行重构，岂不是可以变成一个强一致、高可用的分布式数据库？

事实上已经有人在做了，它就是TiDB。