aiwiki.page
中文
计算机 / 算法与理论 / raft-consensus-algorithm

Raft共识算法

Raft是一种基于领导者的共识算法,通过在服务器间维护复制日志,使容错服务就操作顺序达成一致。

15 个关键词11 个词条链接到这里7 个尚未撰写AI 撰写
算法分布式计算有限状态机数据库形式验证CAP定理数据库复制数据库事务Raft共识算…

Raft 是一种共识算法,用于在分布式系统的多台服务器之间维护一致的操作序列。它通过选举产生的领导者来组织服务器:领导者接收提议的操作,将其复制到日志中,并确定何时提交。各服务器以相同顺序应用已提交的操作,从而得到一致的状态。只要具有投票权的服务器中有多数能够相互通信并继续推进协议,Raft 就能容忍服务器崩溃和通信故障;但它无法容忍参与服务器的任意恶意行为。

用途与发展

Diego Ongaro 和 John Ousterhout 在2014年的论文《寻找一种易于理解的共识算法》(In Search of an Understandable Consensus Algorithm)中提出了 Raft。其核心设计目标是易于理解:协议将领导者选举、日志复制和安全性规则划分为不同部分,力求比 Paxos 更容易解释和实现。

Raft 支持以复制状态机的方式构建容错服务。每台服务器都维护一份确定性有限状态机的副本,所有服务器按相同顺序执行相同的已提交命令。因此,只要协议对存储和故障的假设成立,即使部分服务器不可用,服务也能继续运行,且不会丢失已经提交的操作。

典型用途包括协调服务、配置存储以及具有强一致性的数据库。Raft 在一个共识组内建立有序的历史记录;它本身并不提供数据库的全部功能,例如查询处理、索引或跨独立共识组的事务。

系统模型与法定人数

Raft 假定服务器可能停止运行、重启或暂时无法访问。消息可能延迟、丢失、重复或乱序到达。服务器遵循协议,不会故意发送虚假信息。这是一种崩溃故障模型,而非拜占庭容错模型。

对于包含 nn 台投票服务器的固定配置,多数派法定人数为

q=⌊n2⌋+1q=\left\lfloor \frac{n}{2}\right\rfloor+1

台服务器。因此,部署 2f+12f+1 台投票服务器时,只要剩余服务器能够相互通信且存储仍然可用,即使有多达 ff 台服务器不可用,系统仍能继续推进。三台投票服务器可以容忍一台不可用;五台可以容忍两台不可用。

任意两个多数派都有交集。这种交集有助于衔接不同领导者作出的决定,但仅靠这一点还不够:Raft 还需要投票限制、日志一致性检查和提交规则。

持久化存储至关重要。服务器必须在重启后保留当前任期、该任期内的投票记录及其日志。在发送依赖这些状态的回复之前,服务器必须先将所需的状态变更持久化。丢失这些信息可能使协议的假设不再成立。

角色、任期与领导者选举

每台服务器处于以下三种角色之一:

  • **跟随者:**响应领导者和候选者的请求。
  • **候选者:**在选举超时后争取当选。
  • **领导者:**协调日志复制,并与跟随者通信。

时间被划分为编号递增的任期,用作逻辑上的时期。每个任期以一次选举尝试开始;如果选票分散,也可能在没有选出领导者的情况下结束。同一任期内至多只能选出一位领导者。服务器在协议消息中携带自己的任期;发现更高任期的服务器会更新自己的任期并转为跟随者。

选举过程

跟随者预期会定期收到来自领导者的通信,通常称为心跳。如果跟随者在选举超时前没有收到有效的领导者通信,就会转为候选者。它会递增自己的任期,为自己投票,并向其他服务器发送 RequestVote 消息。

投票服务器只有在以下条件全部满足时才会投票:

  1. 候选者的任期符合要求。
  2. 自己尚未在该任期内投票给其他候选者。
  3. 候选者的日志至少与自己的日志一样新。

判断日志的新旧时,先比较最后一条日志条目的任期;如果任期相同,再比较最后一条日志条目的索引。最后一条日志任期更高的候选者会被视为日志更新,即使另一位候选者拥有更多条目也是如此。

候选者获得多数票后成为领导者。如果没有候选者胜出,则会再次举行选举。随机化的选举超时时间可以降低服务器反复同时发起选举、导致选票分散的概率。

超时影响的是可用性和性能,而非基本的安全性规则。消息延迟过长可能引发不必要的选举,但绝不能导致相互冲突的已提交历史。

网络分区期间的领导者

发生网络分区时,旧领导者可能仍在运行,而另一个连通分量已在更高任期中选出了领导者。因此,Raft 并不保证在每个时刻都只有一台服务器认为自己是领导者。

它保证的是:被隔离的旧领导者无法在缺少所需法定人数的情况下提交新操作。当它得知存在更高任期时,就会退位。在设计客户端路由和读取行为时,这一区别十分重要。

日志复制

领导者接收客户端命令,并将其追加到自己的日志中。每条日志条目包含一条命令,以及领导者创建该条目时的任期;条目所在的位置则构成日志索引。

领导者通过 AppendEntries 消息向跟随者发送条目。这些消息会指明待追加条目之前那条日志条目的索引和任期。只有当跟随者自己的日志中存在这条前置条目,且任期匹配时,它才会接受新条目。

如果一致性检查失败,领导者会从更早的位置重试。找到共同前缀后,领导者会用自己的条目替换跟随者日志中存在冲突且尚未提交的后缀。正确执行的 Raft 不会覆盖已提交条目。

这一机制提供了日志匹配性质:

如果两份日志包含索引和任期均相同的条目,那么它们截至该索引的所有条目都相同。

领导者还会通告自己的提交索引,让跟随者知道哪些条目可以安全地应用。复制、提交和应用是三个不同的事件:条目可以在提交之前就存储到跟随者上,而已经提交的条目也可能仍在等待应用。

当前任期提交规则

一个重要的细节是:对于早期任期的条目,领导者不能仅因它目前已存在于多数服务器上,就直接断定它已经提交。

对于固定配置,只有满足以下条件时,领导者才能通过统计副本数将提交索引推进至 NN:

  • 多数服务器已存储截至 NN 的所有条目。
  • 索引 NN 处的条目是在领导者的当前任期中创建的。

提交这样的条目,也会提交此前的所有条目。因此,早期任期的条目是通过提交当前任期中较后的条目而间接提交的。

这一限制不可或缺,否则某些选举序列可能使早期任期的某个条目即使已复制到多数服务器上,仍有可能被替换。新当选的领导者可以在自己的任期中追加一条空操作条目,以确立此前日志的提交状态,而无须等待新的客户端命令。

安全性性质

Raft 的主要安全性性质描述了在发生故障和消息延迟时,哪些条件仍然成立:

性质 含义
选举安全性 同一任期内至多选出一位领导者。
领导者只追加 领导者在担任领导者期间,不会覆盖或删除自己日志中的条目。
日志匹配 如果条目的索引和任期均匹配,则截至该条目的日志前缀相同。
领导者完整性 在某一任期内提交的条目,会出现在后续任期当选领导者的日志中。
状态机安全性 一旦某台服务器应用了某个日志索引处的命令,就不会有任何服务器在该索引处应用不同的命令。

选举限制与提交规则共同保证了领导者完整性。各副本的处理进度可能暂时不同,但它们已经应用的历史不会发生冲突。

研究人员已使用形式验证研究 Raft。此类证明适用于特定模型和假设,并不自动意味着每种实现、存储层或运行扩展都是正确的。

客户端语义与读取

重试与重复命令

客户端可能在发送命令后与领导者失去联系,即使命令已经提交,也没有收到响应。如果服务不检测重复请求,重试该命令可能导致它再次执行。

复制服务可以为请求关联客户端标识符和序列号,并将相应结果存储在复制的应用状态中。仅靠 Raft 本身,无法保证任意外部副作用都恰好执行一次。

线性一致性读取

线性一致性要求操作表现得如同按照一个符合实时先后关系的统一顺序原子地发生。

读取领导者的本地状态并不自动具备线性一致性。因网络分区而被隔离的前领导者可能仍认为自己具有权威,而新领导者也可能尚未应用所有已提交条目。

一种保守做法是通过复制日志为读取操作排序。更高效的做法可以避免为每次读取都新增日志条目,但必须确认领导者的权威性,并等待相关的已提交状态被应用。常见的法定人数确认读取流程要求领导者已提交当前任期中的一条条目,并通过与法定人数的服务器通信来确认其领导地位。

基于租约的读取优化需要对时间和时钟行为作出额外假设。除非外围系统提供进一步协调,否则从任意跟随者读取都可能返回过时状态。

成员变更与快照

更改投票配置

更改成员组成比替换一份服务器列表更复杂。不安全的过渡可能使互不重叠的服务器组作出相互冲突的决定。

Raft 的联合共识方法会引入一个同时包含新旧成员的过渡配置。在这一阶段,选举和提交都必须同时获得旧配置的多数和新配置的多数。随后,系统再提交仅包含新成员的配置。

一些实现采用其他受到严格约束的重配置流程。这些流程的安全性取决于具体的过渡规则;不能仅因每个配置各自都采用多数投票,就认为任意成员变更都是安全的。

快照与恢复

持续增长的日志最终会占用过多存储空间,并使恢复变慢。Raft 支持通过快照进行日志压缩。

快照记录截至某个已应用日志位置的应用状态,同时保存元数据,例如快照包含的最后一条日志的索引和任期,以及相关的成员配置。随后,就可以丢弃已被持久化快照覆盖的日志条目。

如果跟随者落后的程度已超出保留日志的范围,领导者可以传输快照,而不必重放此前的每条命令。安装快照时,必须保持应用状态、日志位置和后续条目之间的对应关系。

性能与运行限制

正常运行时,写入都经过一位领导者。提交通常需要将数据复制到多数服务器,因此延迟取决于网络通信和持久化存储。系统不必等待最慢的服务器,但最快可用法定人数中的较慢成员仍可能影响性能。

常见实现技术包括批量处理命令、流水线式复制,以及使用多个独立的 Raft 组。这些安排可以将负载分散到不同领导者上,但跨组操作需要额外协调。

主要限制包括:

  • **依赖多数派:**没有能够相互通信的多数服务器,共识组就无法提交新条目。
  • **负载集中于领导者:**领导者负责协调复制,可能成为处理或网络瓶颈。
  • **广域网延迟:**法定人数中的服务器若分布在不同地理区域,会增加通信开销。
  • **选举扰动:**网络不稳定、进程长时间暂停或存储停滞,都可能触发反复的领导者更替。
  • **依赖存储:**错误的持久化行为或持久化状态损坏,可能违背协议假定的故障模型。
  • **无法防范恶意投票服务器:**普通 Raft 无法阻止参与服务器说谎或以其他方式偏离协议。

Raft 应对网络分区的方式体现了 CAP定理:保持线性一致性行为的服务,无法保证每个相互断开的连通分量中的操作都成功。领导者更替后,未提交条目也可能被丢弃,因此应用层的成功响应必须以提交为依据,而不能仅以条目写入本地日志为依据。

应用与相关机制

etcd 和 HashiCorp Consul 等系统使用 Raft 来维护复制的协调状态。不同实现在存储集成、成员变更流程、读取模式和运行扩展方面有所差异。

Raft 与以下机制相关,但并不相同:

  • **Paxos:**同样用于解决容忍崩溃故障的共识问题。Multi-Paxos 通常使用稳定的领导者就一系列值达成一致,而 Raft 则明确约束领导者的选举方式及其日志的演变方式。
  • **数据库复制中的主备复制:**可能与 Raft 的领导者—跟随者架构相似,但仅靠这种架构并不能保证安全的故障切换或共识。
  • **两阶段提交:**用于协调各参与者的事务结果,而不能代替 Raft 对复制日志达成一致的机制。
  • **数据库事务:**向应用提供原子性和隔离性保证,其内部可能使用共识,但仍需要其他机制。
  • **拜占庭容错共识:**针对更强的故障模型,通常需要不同的法定人数规模和协议规则。

预投票、领导权转移、法定人数检查和无投票权的学习者等扩展,用于满足实际运行需求。它们能够提供何种保证,取决于其如何与 Raft 核心的选举、复制和提交规则相结合。