算法描述

State

所有节点的持久化状态，需要在响应RPC前更新到稳定存储：

  • currentTerm 记录的当前任期，初始为0
  • votedFor 当前任期投票支持的candidateId，没有投出票时为null
  • log[] 日志条目，每个条目包含状态机命令及leader接收命令时的任期

所有节点的内存状态：

  • commitIndex 可以提交的日志条目最高索引，初始为0，单调增加
  • lastApplies 应用到状态机的最后一条日志条目索引，初始为0，单调增加
    • 认为状态机也是易失的，重启后需要重新应用所有日志

Leader节点的内存状态，每次选举后初始化：

  • nextIndex[] 为每个节点维护的下次发送的日志条目的起始索引，初始为 1+$last_log_index
    • 根据AppendEntry RPC的响应更新
  • matchIndex[] 为每个节点维护的已经和Leader同步的日志条目的最高索引，初始为0，单调增加
    • 用于更新commitIndex

AppendEntries RPC

由Leader发起，用于复制日志条目或着发送心跳

请求参数：

  • term leader的任期
  • leaderId follower根据LeaderId转发客户端请求
  • preLogIndex 本次发送的日志条目之前的那一条的索引
  • preLogTerm 本次发送的日志条目之前的那一条的任期
  • entries[] 发送的日志条目，可能发送多条，发送心跳时为空
  • leaderCommit Leader的commitIndex，用于follower更新自己的

响应参数：

  • term 当前任期，用于Leader更新自己的任期
    • Leader收到响应中的任期比自己高怎么处理？
    • 记录响应中的任期，然后比较当前任期与原始RPC请求中的任期，如果两者不同，直接放弃处理
      • RPC请求中的任期和当前任期不同，说明发出RPC后，自己收到了别的RPC更新了自己的任期
    • 如果RPC请求中的任期和自己当前任期相同，继续处理
      • 使用响应中的任期更新自己
      • 清空voteFor
      • 转为Follower
  • success 如果follower包含匹配prevLogIndex/prevLogTerm的日志，则返回true

接收者实现：

  • 如果term < currentTerm，返回false
  • 如果prevLogIndex/preLogTerm不匹配自己的日志状态，返回false
  • 如果存在的日志和prevLogIndex/preLogTerm冲突，删除在这之后的所有日志
  • 追加日志中不存在的所有条目
  • 如果leaderCommit > commitIndex，设置 commitIndex=min(leaderCommitIndex, index of last entry)
    • min操作是必要的，否则，如果leaderCommitIndex超出了Leader发给Follower的日志条目，Follower有可能应用到后面错误的条目

注意：

  • 心跳消息也会包含prevLog消息，用于日志同步。因此即使是心跳消息，接受者也需要进行参数校验，才能确认心跳合法
  • 只有通过参数校验的心跳消息，才能重置选举超时定时器
  • Leader收到RPC响应后，由于网络延迟，它自己的状态（任期、角色、日志等）可能已经发生了变化

RequestVote RPC

由Candidate发出，用于收集选票

请求参数：

  • term candiate的任期
  • candidateId
  • lastLogIndex candidate最后一条日志的索引
  • lastLogTerm candidate最后一条日志的任期

响应参数：

  • term currentTerm，用于candidate更新自己的任期
  • voteGranted 支持成为Leader，为true

接受者实现：

  • 如果term < currentTerm，返回false
  • 如果voteFor为null或candiateId，并且根据lastLogXX判断candidate的日志至少和接受者的日志一样新，则投票返回true

注意：

  • RPC的请求超时时间就是选举超时时间，如果候选人正在收集选票，但是选举计时器触发了，应该开始下一轮选举，防止停滞

Rules for Servers

所有节点实现：

  • 如果 commitIndex > lastApplied，则增加lastApplies，应用 log[lastApplied]到状态机
  • 如果RPC请求或响应中的term > currentTerm，则更新currentTerm，再转为Follower
    • 如果自己之前是Leader，需要停止发送AppendEntry RPC
    • 如果之前是Follower，需要停止RequestVote RPC

Follower实现：

  • 响应来自Candidate和Leader的RPC
  • 如果选举定时器超时时没有收到Leader心跳或Candidate请求选票，则转为Candidate
    • 重置选举定时器的前提：收到Leader心跳或给Candidate投票

Candidate实现：

  • 转换为Candidate时，开始选举
    • 增加currentTerm
    • 给自己投票
    • 重置选举超时定时器
    • 向其它所有节点发送RequestVote RPC
  • 如果收到多数节点的选票，成为Leader
  • 如果收到新Leader的AppendEntry RPC，变为Follower
  • 如果选举超时，开始新的选举

Leader实现

  • 成为Leader后，向每个节点发送心跳；定期发送心跳，来阻止节点许那句超时
  • 如果收到客户端命令，将日志条目保存到本地日志，直到应用到状态机之后响应客户端
  • 如果最后一条日志的索引大于等于某个Follower节点的nextIndex，则发送AppendEntry RPC请求，包含从nextIndex开始的所有日志
    • 如果返回成功，更新该Follower对应的nextIndex和matchIndex
    • 如果因为日志冲突失败，减小nextIndex后重试
  • 如果存在N > commitIndex，并且对于多数接地那满足 matchInex[i] >= N，并且 log[N].term==currentTerm，则设置 commitIndex=N
    • 在AppendEntry RPC的响应中执行这个操作
    • 可以看出，Leader只能提交自己任期的日志。对于之前任期的日志，不能主动提交，只能出现本任期的日志后，连带提交之前任期的日志

关于matchIndex[i]和nextIndex[i]：

  • nextIndex只是一个临时值，用于向真实的匹配位置逼近，初始时是在日志末尾
  • matchIndex保存每个Follower的真实匹配位置，初始时是在日志开头

matchIndex不能被设置为一个太⾼的值，因为这可能导致commitIndex被向前移动得太远。这就是为什么matchIndex被初始化为0，并且只在跟随者肯定地确认AppendEntries RPC时才更新。准确的更新方法：

  • matchIndex 更新为在 RPC 中发送的参数中 prevLogIndex + len(entries[])
  • 而不是使用matchIndex=nextIndex-1或者matchIndex=len(log)
  • 因为nextIndex和log有可能在发出RPC后发生变化。

Raft给出的保证

  • 选举安全性：一个任期内，最多只有一个Leader产生
  • Leader仅追加：Leader不会覆盖或者删除自己的日志条目，仅追加新的条目
  • 日志匹配：如果两个日志包含一个索引和任期都相等的条目，那么这两个日志在这个索引及之前的所有条目都相同
  • Leader完整性：如果一个条目在某个任期被提交，那么在Leader的更高的任期中，这个条目仍然存在
  • 状态机安全：如果节点向状态机应用了某个索引的日志条目，其它的节点也会在这个索引位置应用同样的条目

重置选举定时器的时机

并不是每次收到AppendEntry RPC或者RequestVote RPC的时候都要重置定时器，而是有条件的：

  • 从当前的真实Leader那⾥得到⼀个AppendEntry RPC
    • 如果RPC参数中的任期已经过时，就不应该重置计时器
  • 正在开始⼀个选举
  • RequestVote RPC处理中授予另⼀个候选者投票
    • 前提是候选者参数满足条件

客户端和Raft状态机的交互

  1. 客户端向当前leader所在的应用层（状态机）发送请求
  2. 应用层把客户端的请求下发给raft层：这里有一个请求，请将它提交到replicated log里，当你完成的时候，告诉我已经做完了。
  3. raft的leader和每个副本通信，直到所有的副本有半数以上的副本把这个新的操作添加到各自的日志中。
  4. raft的leader发送给应用层的服务一个通知：你发我的操作，我已经做好日志记录，已经被安全的复制
  5. 应用层执行这个操作，更新状态机，回复结果给客户端
  6. leader在下一个AppendEntry RPC中通知follower已提交的进度，follower顺序执行已提交的日志，应用到自己的状态机中。
  7. 在这些replicas中，大家执行日志的顺序是一样的，即state是一样的。

Leader 选举

节点启动后，最初是Follower角色，在选举定时器超时前，如果收到来自Leader的心跳或者为Candidate投出选票，会继续保持Follower状态。

Leader会周期性的向其它节点发送心跳来维护地位。

如果Follower的选举定时器超时前什么都没收到，就认为当前Leader异常，然后发起新的选举。

开始选举后，Follower增加当前的任期，转换到Candidate角色，为自己投票，然后并行的向其它节点发出征集选票的请求，直到：

  • 赢得选举
    • Candiate收到来自多数节点的选票
    • Candiate赢得选举后就变成Leader，然后向其它节点发送心跳来宣告自己，阻止新的选举发起。
  • 其它节点成为Leader
    • 等待选举响应过程中，Candiate可能收到来自其它节点的心跳请求
      • 如果对方（可能是Leader）的任期至少和自己一样，则Candidate转为Follower
      • 如果对方的任期比自己小，Candidate会拒绝RPC然后继续留在Candidate状态。
  • 选举超时
    • 如果多个Follower同时成为Candidate，出现瓜分选票会导致没有Candidate获胜
    • 每个Candidate都会超时，然后自增任期再次开始下一轮选举
    • Raft使用随机的选举超时时间来保证尽量不出现瓜分选票的情况

每个节点在每个任期内，最多投出一票，且按照先来先服务的原则。

日志复制

Leader将来自客户端的命令封装在日志条目中，追加到日志结尾，然后并行的向其它节点发起AppendEntry RPC。

当条目被安全的复制，Leader会应用这个条目到状态机，最后向客户端回复成功。

如果网络故障或Follower节点宕机，Leader会一直重试AppendEntry RPC，直到所有Follower获得和Leader一致的日志。

每个日志条目包含一个状态机命令及Leader收到命令时的任期号。任期号用于检测日志一致性。每个条目都对应一个索引，用来定位在日志中的位置。

日志条目

Leader决定什么时候向状态机应用一条日志是安全的。当日志可以被应用时，及成为已提交状态。

Raft保证已提交的日志被持久化，且最终会被所有的状态机执行。

一旦创建条目的Leader将条目复制到多数节点，那么这个条目就是提交状态。同时会顺带提交这个条目之前的日志，即使他们是由之前的Leader创建。

注意，Leader只能提交自己任期产生的条目，不能提交之前任期Leader产生的条目。对于之前任期的条目，只能在本任期提交时被顺带提交。以此来保证以提交的日志在更高的任期中仍然存在。

Leader会跟踪已提交的最高索引，在AppendEntry RPC中通知其它节点。一旦Follower得知最新的commitIndex，就会将前面未应用的日志应用到自己的状态机。

Raft维持了下面的日志匹配属性：

  • 如果不同日志里的两个条目有相同的index和term，那么它们存储的命令相同
    • 因为Leader在某个任期在某个index只会生成一个条目
    • 并且条目在日志中不会修改位置
  • 如果两个日志中的两个条目有相同的index和term，那么它们前面的日志都相同
    • 由AppendEntry RPC执行的一致性检查保证，Follower会检查自己lastLogIndex位置的条目任期是否是lastLogTerm，不是则拒绝请求
    • 一致性检查以归纳的方式进行
      • 最开始日志是空的，满足日志匹配属性
      • 日志追加时的一致性检查也会维护日志匹配属性
      • RPC返回后，Leader就知道在这个条目之前的条目都是一致的

Leader崩溃切换会导致日志不一致，如下图

leader crash

Raft中由Leader负责处理Follower日志出现不一致的情况：通过强制Follower使用Leader的日志来解决。

在安全性部分会介绍，在什么条件下这种操作时安全的。

为了将Follower的日志变为和自己一致，Leader必须找到Follower是从什么位置开始不一致，删除Follower那之后的日志，然后把自己的那部分日志发给Follower

  • 所有这些操作都是在AppendEntry RPC中做的
  • Leader维护了每个节点接下来需要发送条目的索引：nextIndex
  • 发送RPC时，lastLogIndex/lastLogTerm对应nextIndex-1位置的条目
  • 如果Follower发现lastLog位置的条目不一致，AppendEntry RPC将会失败
  • Leader会减小nextIndex然后重试，最终找到一致的位置甚至是日志最开始
    • 朴素的方式是每次将nextIndex减1然后重试
    • 快速的方法是，Follower在响应中告知自己该位置的实际任期t，以及自己该任期的开始索引idx，Leader往前跳过这个任期t，从idx位置重试

这种机制下，Leader上任后不要执行特殊的操作来使Follower日志一致，在AppendEntry RPC中就可以顺带完成日志一致性检查。

Leader永远不会覆盖或者删除自己的条目。

正常情况下，新的条目在一批RPC中就可以复制到集群的多数节点，单个慢响应的Follower并不会影响性能。

安全性

Raft算法实现在Leader选举和日志复制实现上给出了一些限制条件，使Raft算法能够正确地工作。

选举限制

Raft在选举阶段通过一个限制条件，保证之前任期已提交的日志一定存在于高任期的Leader中，且从Leader上任就存在。这样就不需要将之前的日志发送给新Leader，因为它已经有了。

如果Candidate的日志至少和集群中多数节点的日志一样新，那么Candidate就拥有所有已提交的日志。

选举限制：收到RequestVote RPC的节点，如果发现自己的日志比Candidate的日志更新，则拒绝投票。

如何比较两个日志哪个更新：

  • 如果日志最后的条目任期不同，那么拥有高任期的日志更新
  • 如果日志最后的条目任期相同，那么长度更长的日志更新

只有在Candidate的日志至少比集群多数节点的日志一样新时，才能赢得选举。

日志提交限制

提交限制：Leader只能提交自己任期产生的日志。

  • 对于之前任期产生的日志，即使已经复制到多数节点，也不能直接提交，只能在提交本任期日志时顺带提交。

log commit

当前已经到了term4了。此时，虽然term2的日志已经复制到多数节点，但还是不能提交它，因为当前是在term4，只能等待在当前任期提交term4的日志，从而间接提交term2。

这样就能避免，c中提交了term2的日志，在d中被覆盖的情况。

任期号涨上去了，那老的日志什么时候提交呢，后面没有新的日志来了咋办？

  • 当选为Leader后发送特殊的NO-OP日志，不包含命令，仅用来推进条目提交。

有些场景下，Leader可以安全地推断出老的条目可以被提交了（如条目被复制到了每个节点上），但是Raft为了实现简单还是选择了保守的方式。

如何基于Raft实现线性一致性

所谓的强一致性并不是指集群中所有节点在任一时刻的状态必须完全一致，而是指一个目标，即让一个分布式系统看起来只有一个数据副本，并且读写操作都是原子的，这样应用层就可以忽略系统底层多个数据副本间的同步问题。 也就是说，我们可以将一个强一致性（线性一致性）分布式系统当成一个整体，一旦某个客户端成功的执行了写操作，那么所有客户端都一定能读出刚刚写入的值。即使发生网络分区故障，或者少部分节点发生异常，整个集群依然能够像单机一样提供服务。

使用了 Raft 的系统都是线性一致的吗？

  • 不是的，Raft 只是提供了一个基础，要实现整个系统的线性一致还需要做一些额外的工作。

假设期望基于 Raft 实现一个线性一致的分布式 kv 系统，从最朴素的方案开始，指出每种方案存在的问题，最终使整个系统满足线性一致性。

  1. 写主读从

在该方案中我们假设读操作直接简单地向 follower 发起，那么由于 Raft 的 Quorum 机制（大部分节点成功即可），针对某个提案在某一时间段内，集群可能会有以下两种状态：

  • 某次写操作的日志尚未被复制到一少部分 follower，但 leader 已经将其 commit。
  • 某次写操作的日志已经被同步到所有 follower，但 leader 将其 commit 后，心跳包尚未通知到一部分 follower。

以上每个场景客户端都可能从状态机读到过时的数据，整个系统显然是不满足线性一致的。

  1. 写主读主

在该方案中我们限定，所有的读操作也必须经由 leader 节点处理。读写都经过 leader 难道还不能满足线性一致？是的，并且该方案存在不止一个问题。

  • 问题一：状态机落后于 committed log，导致从状态机读到旧数据
    • 解决：写请求处理时，等状态机应用到对应的条目后，再响应写请求。这样之后的读请求就能从状态机中读到最新数据。
  • 问题二：网络分区导致读到旧数据
    • 旧的Leader由于网络分区而下台，但它自己不知道，仍响应读请求
  1. Raft log read

为了确保 leader 处理读操作时仍拥有领导权，可以将读请求同样作为一个提案走一遍 Raft 流程，当这次读请求对应的日志可以被应用到状态机时，leader 就可以读状态机并返回给用户了。 这种读方案称为 Raft Log Read。

为什么这种方案满足线性一致？因为该方案根据 commit index 对所有读写请求都一起做了线性化，这样每个读请求都能感知到状态机在执行完前一写请求后的最新状态，将读写日志一条一条的应用到状态机，整个系统当然满足线性一致。

但该方案的缺点也非常明显，那就是性能差，读操作的开销与写操作几乎完全一致。而且由于所有操作都线性化了，我们无法并发读状态机。

Raft线性一致读优化

Read Index

与 Raft Log Read 相比，Read Index 省掉了同步 log 的开销，能够大幅提升读的吞吐，一定程度上降低读的时延。其大致流程为：

  • Leader 在收到客户端读请求时，记录下当前的 commit index，称之为 read index。
  • Leader 向 followers 发起一次心跳包，这一步是为了确保领导权，避免网络分区时少数派 leader 仍处理请求。
  • 等待状态机至少应用到 read index（即 apply index 大于等于 read index）。
  • 执行读请求，将状态机中的结果返回给客户端。

Lease Read

与 Read Index 相比，Lease Read 进一步省去了网络交互开销，因此更能显著降低读的时延。

基本思路是 leader 设置一个比选举超时（Election Timeout）更短的时间作为租期，在租期内我们可以相信其它节点一定没有发起选举，集群也就一定不会存在脑裂，所以在这个时间段内我们直接读主即可，而非该时间段内可以继续走 Read Index 流程，Read Index 的心跳包也可以为租期带来更新。

Lease Read 可以认为是 Read Index 的时间戳版本，额外依赖时间戳会为算法带来一些不确定性，如果时钟发生漂移会引发一系列问题，因此需要谨慎的进行配置。

Follower Read

在前边两种优化方案中，无论我们怎么折腾，核心思想其实只有两点：

  • 保证在读取时的最新 commit index 已经被 apply。
  • 保证在读取时 leader 仍拥有领导权。

这两个保证分别对应前面“写主读主”中所描述的两个问题。

其实无论是 Read Index 还是 Lease Read，最终目的都是为了解决第二个问题（Leader还是Leader）。换句话说，读请求最终还是由 leader 来承载的。

那么读 follower 真的就不能满足线性一致吗？其实不然，这里给出一个可行的读 follower 方案：

Follower 在收到客户端的读请求时，向 leader 询问当前最新的 commit index，反正所有日志条目最终一定会被同步到自己身上，follower 只需等待该日志被自己 commit 并 apply 到状态机后，返回给客户端本地状态机的结果即可。

这个方案叫做 Follower Read。

注意，Follower Read 并不意味着我们在读过程中完全不依赖 leader 了，在保证线性一致性的前提下完全不依赖 leader 理论上是不可能做到的。

未涉及的话题

  • 日志快照
  • 日志压缩
  • 配置更新