ᕕ( ᐛ )ᕗ Jimyag's Blog

Raft 论文总结

简介

如何多快好省的对大规模数据集进行存储和计算?

解决

  1. 更好的机器
  2. 更多的机器

问题

  1. 不断垂直扩展机器,升到一定配置之后就不能升级了。升级机器的配置带来的提升与付出的价格不匹配。瓶颈是在与硬件和对成本的控制
  2. MapReduce 中使用一些廉价的机器组成一个集群处理大规模的数据,这也会引出一个问题。如何保证多个机器之间的同步,如何解决机器间的网络问题。对于网络通信有三种:写入成功,写入失败,消息丢掉(无法判断消息丢失还是延迟)

如何让跨网络的机器之间协调工作?

  1. 状态立即一致
  2. 状态的最终一致

如何应对网络不可靠以及节点的实效?

  1. 可读写
  2. 可读
  3. 不可用

复制状态机

图 1

  1. Client 将操作发送到 Leader 结点,
  2. Leader 将同步请求发送到其余的结点,将操作记录到日志中
  3. 专门的状态机会将日志应用到 server

一致性要解决的问题

  1. 输入:写入命令
  2. 输出:所有节点最终处于相同的状态
  3. 约束
  4. 网络不确定性:在非拜占庭情况下 (非受信网络),出现网络 分区、冗余、丢失、乱序 等问题下要保证正确。
  5. 基本可用性:集群大部分节点能够保持相互通信,那么集群就应该能够正确响应客户端
  6. 不依赖时序:不依赖物理时钟或者极端的消息延迟来保证一致性。不能依靠给消息时间戳来保证消息的顺序。零点飘逸
  7. 快速响应:对客户端请求的响应不能依赖集群中最慢的节点

一个可行解

Raft 的详细实现

状态机

图 2

raft 中有三个角色 (状态),三个角色可以进行一些切换,每一个状态都有不同的数据结构 所有的节点在启动的时候都是 Follower,会启动一个心跳计时器,如果心跳计时器超时了,那么就会变为 Candiate 状态,变成之后会立即向其他结点发送投票请求进行投票,同时也会启动一个选举超时计时器。 如果收到半数以上人数的票就会变为 leader,成为 leader 之后发送心跳和同步日志,启动一个定时器,每隔一段时间给 follower 发送心跳。 如果始终没有收到足够的选票,这时候选举定时器超时,就会更新自己的状态为候选人重新发起一轮新的投票过程 如果在等待选票的过程中,收到了 leader 的心跳请求,就会退回到 follower 状态。 由于网络分区,集群中又出现了一个 leader,这时候网络中就有两个 leader,这是分布式系统中一个常见的问题 - 脑裂。如何避免这个问题呢?给每一个 leader 都有一个任期 term(在心跳中就会同步任期数),如果有两个 leader 之后就后根据 term 较大的一个作为新的 leader,较小的 term 的 leader 就会退回为 follower 选举的过程中,超时计时器的时间是固定的,所有的 follower 变为 candidate 同时请求选举,可能会有瓜分选票的问题,三个人手上都只有一张选票,没有超过半数,一直选举,一直都没有 leader 出现,一直都不可写。raft 为了避免这个问题,给每个结点选举超时时间设定了一个随机范围,尽量在一次选举中就可以选出 leader

数据结构

通用持久性数据(三个状态都有)

参数 解释
currentTerm 服务器已知的最新的任期,首次启动的时候为 0。通过心跳更新
votedFor 当期任期内收到选票的候选者的 ID,如果没有投给任何人,则为空,就是把票投给了谁
log[] 日志的条目,每个条目包含了用于应用状态机的命令,以及 leader 接受到该条目时的 term,索引从 1 开始

通用易失性数据

参数 解释
commitIndex 已知已提交的最高的日志条目的索引,初始值为 0
lastApplied 已经被应用到状态机的最高的日志条目的索引,初始值为 0

leader 的易失性数据

参数 解释
nextIndex[] 每一个 follower,发送到改 follower 的下一个日志条目的索引,初始值为 leader 的最后日志条目的索引 +1
matchIndex[] 每一个 follower,已知的已经复制到该 follower 的最高日志条目的索引,初始值为 0

对于每一个角色,都有不同的定时器,leader 是发送心跳的计时器,follower 是心跳超时的计时器,candidate 是选举超时的计时器

RPC

RPC 的发起者是谁,由谁接受处理它?

请求投票

什么时候触发?
  1. follower 变为 candidate(follower 的心跳计时器超时了)
  2. 选举超时
请求 (核心) 参数
参数 说明
term 候选人的任期号
candidateID 候选人的 ID
lastLogIndex 候选人的最后 (新) 日志条目的 index
lastLogTerm 候选人最后日志条目的任期号
返回值
参数 说明
term 当期任期号
voteGranted 候选人获得这张选票时为 true,否则为 false
返回 term 是集群中已经有新的 leader 出现了,把当前 term 给候选人,让它切换状态
投票逻辑(候选人)
  1. 在转变成候选人后就立即开始选举过程
  2. 自增当前的任期号 (currentTerm)
  3. 给自己投票 (votedFor = 自己的 ID)
  4. 重置选举超时计时器
  5. 发送请求投票的 RPC 给其他所有服务器(到选举规则了)
  6. 如果接收到大多数服务器的选票,那么就变成领导人
  7. 如果接收到来自新的领导人的附加日志 RPC,转变成跟随者
  8. 如果选举过程超时,再次发起一轮选举
选举的规则(接受到 RPC 方)
  1. 如果 term< currentTerm 返回 false,currentTerm
  2. (判断候选人已经提交的的日志是否是足够新的,候选人应该拥有所有的已提交,从建立之初到现在的所有的日志)如果 votedFor 为空 或者 等于 candidateld(可能是新一轮投票),并且比较 lastLogTerm 和 currentTerm
  3. lastLogTerm>currentTerm 则直接投票
  4. 小于则拒绝
  5. 等于则比较 lastLogIndex 和 log[len(log)-1].idx

日志追加&心跳

触发
  1. 客户端发起写请求时
  2. 发送心跳时
  3. 日志匹配失败时
请求参数
参数 说明
term 当前 leader 的任期号
lederID 领导者的 ID
preLogIndex leader 紧邻新日志之前的那个日志的 index
preLogTerm leader 紧邻新日志之前的那个日志的 term
entries 需要被提交的日志的条目
leaderCommit 领导者的已知已提交的最高的日志条目的索引
响应值
参数 说明
term 当前任期,对于 leader 而言,它会更新自己的 Term
success 如果 follower 所含有的条目和 preLogIndex 以及 preLogTerm 匹配上了,返回 true
第一个分区得不到半数确认,会处于为提交的状态
日志追加(leader)
  1. 一旦成为 leader:发送空的附加日志 RPC(心跳) 给所有的 follower,在一定空余时间之后不停的重复发送,阻止 follower 超时
  2. 如果接受到来自 client 的写请求:附加本条目到本地日志中,在条目被应用到状态机后响应 client(可选,如果是强一致的,就这样做,如果不是强一致附加到本地日志就可以返回了)
  3. 对于 follwer,如果 leader 的最后日志条目的索引值>=nextIndex,那么发送从 nextIndex 开始的所有日志条目:
  4. 如果成功,更新相应追随者的 nextIndex 和 matchIndex
  5. 如果因为日志不一致而失败,减少 nextIndex 重试 (每次减 1 进行尝试,直到找到和 preLogIndex,term 匹配的就停止,就可以发送日志了。为什么只匹配到这个就可以认为之前的也一样呢?只要不匹配就往后退,就删除,最后肯定会当 index=0 的时候一定匹配,那么这时候 1 也匹配,2 也配)
  6. 如果存在一个满足 N>commitIndex 的 N,并且大多数的 matchIndex[i]>=N 成立,并且 log[N].term == currentTerm 成立,那么 commitIndex = N (matchIndex 是当前集群同步的进度,N 就是超过一半的节点都提交到这个点了,中位数,那么就满足了法定人数,此时更新这个 commit 就是安全的)
接受日志 (follower)
  1. 如果 leader 的 term < follower 当前的 term,返回 false,currentTerm
  2. 在接受者的日志中,如果能找到一个和 preLogIndex 以及 preLogTerm 一样的索引和任期的日志条目,则执行下面操作,否则返回 false,
  3. 如果一个已经存在的条目和新的条目发生冲突 (索引相同,任期不同),那么就删除这个已经存在的条目以及它之后的所有条目。(五个结点旧的 leader 和其中一个结点与其他三个结点分区了,网络恢复后,结点 A 有可能存在没有提交的 logEntry),leader 会让删除不是自己任期内的为提交的日志。当前日志未提交,可以强制使 follower 复制日志和 leader 一样。
  4. 追加日志中尚未存在的任何新条目 5. 如果领导者的 (commitIndex)leaderCommit 大于 接收者的 commitlndex 则把接收者的 commitlndex 重置为 ( leaderCommit 或者是 发来的最新日志条目的索引值取两者 的最小值) ???

算法证明

五条公理

特性 说明
选举安全特性 给定一个 term,最多只有一个 leader
leader 只附加原则 leader 绝对不会删除或者覆盖自己的日志,只会增加
日志匹配原则 如果两个日志在相同 index 的 term 也相同,那么我们认为日志从头到 index 之间都完全相同
leader 完全特性 某条日志条目在某个任期号中已经被提交,那么这个条目必然出现在更大的 term 的所有 leader 人中
状态机安全特性 如果一个 leader 已经将给定 index 的日志条目应用到状态机中,那么其他任何 follower 在这个 index 不会应用一个不同的日志

选举安全特性

1

在一个任期内半数以上选票才可以当选,保证每个任期要么 0 个领导要么 1 个领导。 normal operation 是有 leader 的时候 一个 term 可能也没有 leader 被选举出来,那么这时候 term++,继续选举

日志复制过程的完全匹配

  1. 因为 集群在任意时刻最多只能有一个 leader 存在,leader 在一个任期内只会在同一个索引处写入一次日志
  2. 又因为 领导者从来不会删除或者覆盖自己的日志,并且日志一旦写入就不允许修改
  3. 所以 只要任期和索引相同,那么在任何节点上的日志也都相同
  4. 因为 跟随者每次只会从与 leader 的 PreLog 匹配处追加日志,如果不匹配 则 nextindex -1 重试
  5. 所以 由递归的性质可知一旦跟随者和 leader 在 PreLog 处匹配,那么之前的所有日志就都是匹配的 (0 就是空 log,是起点,所有的结点都相同)
  6. 所以只要把 preLog 之后的日志全部按此次 Leader 同步 RPC 的日志顺序覆盖即可保证 二者的一致性

安全性

每一任的领导者一定会有所有任期内领导者的全部已提交日志吗?

选举限制

选民只会投票给任期比自己大,最后一条日志比自己新 (任期大于或者等于时索引更大) 的候选人。 但这真的正确吗? 图 4

  1. 时刻 a,S1 是任期 2 的领导人并且向部分节点(S1 和 S2)复制了 2 号位置的日志条目,然后宕机​
  2. 时刻 b,S5 获得了 S3、S4( S5 的日志与 S3 和 S4 的一样新,最新的日志的任期号都是 1)和自己的选票赢得了选举,成了 3 号任期的领导人,并且在 2 号位置上写人了一条任期号为 3 的日志条目。在新日志条目复制到其他节点之前,S5 若机了​
  3. 时刻 c,S1 重启,并且通过 S2、S3、S4 和自己的选票赢得了选举,成了 4 号任期的领导人,并且继续向 S3 复制 2 号位置的日志。此时,任期 2 的日志条目已经在大多数节点上完成了复制​ (s3 的 4 可能还没有提交)
  4. 时刻 d,S1 发生故障,S5 通过 S2、S3 的选票再次成为领导人(因为 S5 最后一条日志条目的任期号是 3,比 S2、S3、S4 中任意一个节点上的日志都更加新),任期号为 5。然后 S5 用自己的本地日志夜写了其他节点上的日志​
  5. 上面这个例子生动地说明了,即使日志条目被半数以上的节点写盘(复制)了,也并不代表它已经被提交(commited)到 Raft 集群了——因为一旦某条日志被提交,那么它将永远没法被删除或修改。这个例子同时也说明了,领导人无法单纯地依靠之前任期的日志条目信息判断它的提交状态​
  6. 因此,针对以上场景,Raft 算法对日志提交条件增加了一个额外的限制:要求 Leader 在当前任期至少有一条日志被提交,即被超过半数的节点写盘
  7. 正如上图中 e 描述的那样,S1 作为 Leader,在崩溃之前,将 3 号位置的日志(任期号为 4)在大多数节点上复制了一条日志条目(指的是条目 3,term 4),那么即使这时 S1 若机了,S5 也不可能赢得选举一一因为 S2 和 S3 最新日志条目的任期号为 4,比 S5 的 3 要大,S3 无法获得超过半数的选票。无法赢得选举,这就意味着 2 号位置的日志条目不会被覆写

所以新上任的领导者在接受客户端写入命令之前 需要提交一个 no-op(空命令),携带自己任期号的日志复制到大多数集群节点上才能真正的保证选举限制的成立。(相当于不会单独同步 Term 2,而是把同步 Term2 与 Term4 原子化,不然 Term2 会被覆盖)

状态机安全性证明(三段论)

  1. 定义 A 为上个任期最后一条已提交日志,B 为当前任期的 leader​
  2. 因为 A 必然同步到了集群中的半数以上节点​
  3. 又因为 B 只有获得集群中半数以上节点的选票后才能成为 leader​
  4. 所以 B 的选民中必然存在拥有 A 日志的节点​
  5. 又因为 选举限制,B 成为 leader 的前提是比给它投票的所有选民都要新​
  6. 所以 B 的日志中必然要包含 A​
  7. 又因为 日志完全匹配规则 如果 A 被 B 包含,那么比 A 小的所有日志都被 B 包含​
  8. 因为 lastApplied <= commitIndex​
  9. 又因为 raft 保证已提交日志在所有集群节点上的顺序一致​
  10. 所以 应用日志必然在在所有节点上顺序一致​
  11. 因为 状态机只能按序执行应用日志部分​
  12. 得证 状态机在整个集群所有节点上必然 最终一致

状态机安全性证明(反证法)

  1. 当日志条目 L 被同步给半数以上节点时,leaderA 会移动 commitIndex 指针提交日志,此时的日志被提交​
  2. 当 leader 崩溃后,由一个新节点成为 leaderB,假设 leaderB 是第一个未包含 leaderA 最后已提交日志的领导者​
  3. 选举过程中,只有获得半数以上节点认可才能成为 leader,因此至少有一个投票给当前 leaderB 的节点中含有已经提交的那条日志 L。​
  4. 那么根据选举限制,节点只会将选票投给至少与自己一样新的节点​
  5. 节点 C 作为包含 leaderA 最后提交日志条目的投票者,如果 leaderB 与节点 C 的最后一条日志的任期号一样大时,节点 C 的条目数一定大于 leaderB,因为 leaderB 是第一个未包含最后一条 LeaderA 日志的领导者。这与选举限制相矛盾,节点 C 不会投票给 leaderB
  6. 如果 leaderB 最后一条日志的任期号大于节点 C 最后一条日志的任期号,那么 leaderB 的前任领导中必然包含了 leaderA 已经提交的日志 (leaderB 是第一个不包含 leaderA 已提交日志的领导者 这一假设) 根据 日志匹配特性 leaderB 也必须包含 leaderA 最后的已提交日志,这与假设矛盾。​
  7. 所以证明 未来所有的领导者必然包含过去领导者已提交的日志,并且日志匹配原则,所有已提交日志的顺序一定是一致的。
  8. 又因为 任意节点仅会将已提交日志按顺序应用于自身的状态机,更新 lastApplied 指针,因此所有节点的状态机都会最终顺序一致。
  9. 得证 raft 算法能够保证节点之间的协同工作。

一些额外的资料

一致性介绍

脑裂 (split-brain)

原本一个集群,被分成了两个集群,同时出现了两个“大脑”,这就是所谓的“脑裂”现象。这里的大脑都是被选举出来的,可能由于网络分区的原因,选举的时候。由于原本的一个集群变成了两个,都对外提供服务。一段时间之后,两个集群之间的数据可能会变得不一致了。当网络恢复时,就面临着谁当 Leader,数据怎么合并,数据冲突怎么解决等问题。

网络分区

在分布式环境下,有时由于网络通讯故障,而不是服务器上的应用故障,导致一些节点认为应用不可用,另外一些节点认为应用仍可用。导致,整个系统在提供服务时,造成了不一致性。由于故障将网络划分为多个区域了。