侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

Raft

林贤钦
2022-04-25 / 0 评论 / 1 点赞 / 211 阅读 / 3,490 字
温馨提示:
本文最后更新于 2022-04-25,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Raft

由于 Paxos 算法在国际上被公认的非常难以理解和实现,因此不断有人尝试简化这一算法。到了2013 年才诞生了一个比 Paxos 算法更易理解和实现的分布式一致性算法—Raft 算法。

拜占庭失败

简单来说,在从前,拜占庭将军问题被认为是一个逻辑上的困境,它说明了一群拜占庭将军在试图就下一步行动达成统一意见时,可能存在的沟通问题。

该困境假设每个将军都有自己的军队,每支军队都位于他们打算攻击的城市周围的不同位置,这些将军需要就攻击或撤退达成一致。只要所有将军达成共识,即协调后决定共同执行,无论是攻击还是撤退都无关紧要。

基于著名的 FLP 不可能问题的研究,拜占庭将军们面临三种困境:

  1. 将军们没有统一的时间(没法对表);
  2. 无法知道别的将军是否被击败;
  3. 将军们之间的通讯是完全异步的。

拜占庭失败又称为任意失败,所谓任意失败是,参与的节点对请求产生不一致的响应,一个说当前数据是 A,而另一个却说它是 B。

这个故障往往是程序 Bug 导致的,可以通过严格软件开发流程管理来尽可能规避。但我们都清楚,Bug 在生产系统中是很难避免的,特别是系统版本差异带来的问题是极其常见的。故在运行态,一部分系统并不信任直接从远程节点获得的数据,而是采用交叉检测的方式来尽可能得到正确的结果。

另一种任意失败是一些节点故意发送错误消息,目的是想破坏系统的正常运行,从而牟利。采用区块链技术的数字货币系统则是使用正面奖励的模式(BFT),来保证系统内大部分节点不“作恶”(做正确事的收益明显高于作恶)。

共识算法是为了解决拜占庭将军问题而产生的。共识算法使用逻辑时钟来提供统一时间,并引入错误侦测技术来确定参与节点的情况,从而在完全异步的通讯情况下可以实现分布式系统的共识。

共识算法

共识是可容错系统中的一个基本问题:即使面对故障,服务器也可以在共享状态上达成一致。

共识算法允许一组节点像一个整体一样一起工作,即使其中的一些节点出现故障也能够继续工作下去,其正确性主要是源于复制状态机的性质:一组Server的状态机计算相同状态的副本,即使有一部分的Server宕机了它们仍然能够继续运行。

image-20220425191746651

一般通过使用复制日志来实现复制状态机。每个Server存储着一份包括命令序列的日志文件,状态机会按顺序执行这些命令。因为每个日志包含相同的命令,并且顺序也相同,所以每个状态机处理相同的命令序列。由于状态机是确定性的,所以处理相同的状态,得到相同的输出。

因此共识算法的工作就是保持复制日志的一致性。

服务器上的共识模块从客户端接收命令并将它们添加到日志中。它与其他服务器上的共识模块通信,以确保即使某些服务器发生故障。每个日志最终包含相同顺序的请求。一旦命令被正确地复制,它们就被称为已提交。每个服务器的状态机按照日志顺序处理已提交的命令,并将输出返回给客户端,因此,这些服务器形成了一个单一的、高度可靠的状态机。

适用于实际系统的共识算法通常具有以下特性:

  • 安全。它们确保在所有非拜占庭条件下(包括网络延迟,分区和数据包丢失,重复和乱序)的安全性(不会返回不正确的结果)。
  • 高可用。只要任何大多数(过半)服务器都可以运行,并且可以相互通信和与客户通信,一致性算法就可用。 因此,五台服务器的典型集群可以容忍任何两台服务器的故障。 假设服务器突然宕机,它们可以稍后从状态恢复并重新加入群集。
  • 一致性不依赖时序。它们不依赖于时序来确保日志的一致性:错误的时钟和极端消息延迟在最坏的情况下会导致可用性问题(译者注:言外之意是可以保证一致性)。
  • 及时响应。在通常情况下,只要集群的大部分(过半服务器)已经响应了单轮远程过程调用,命令就可以完成; 少数(一半以下)慢服务器不会影响整个系统性能。

Raft算法概述

Raft 算法可以说是目前最成功的分布式共识算法,包括 TiDB、FaunaDB、Redis 等都使用了这种技术。原因是 Multi-Paxos 没有具体的实现细节,虽然它给了开发者想象空间,但共识算法一般居于核心位置,一旦存在潜在问题必然带给系统灾难性的后果。而 Raft 算法给出了大量的实现细节,且处理方式相比于 Multi-Paxos 有两点优势。

  1. 发送的请求的是连续的,也就是说 Raft 的写日志操作必须是连续的;而 Multi-Paxos 可以并发修改日志,这也体现了“Multi”的特点。
  2. 选主必须是最新、最全的日志节点才可以当选,这一点与 ZAB 算法有相同的原则;而 Multi-Paxo 是随机的。因此 Raft 可以看成是简化版本的 Multi-Paxos,正是这个简化,造就了 Raft 的流行。

Raft节点类型

一个 Raft 集群包括若干服务器,以典型的 5 服务器集群举例。在任意的时间,每个服务器一定会处于以下三个状态中的一个:

  • Leader:负责发起心跳,响应客户端,创建日志,同步日志。
  • Candidate:Leader 选举过程中的临时角色,由 Follower 转化而来,发起投票参与竞选。
  • Follower:接受 Leader 的心跳和日志同步数据,投票给 Candidate。

在正常的情况下,只有一个服务器是 Leader,剩下的服务器是 Follower。Follower 是被动的,它们不会发送任何请求,只是响应来自 Leader 和 Candidate 的请求。

image-20220425192451535

raft任期

image-20220425192513475

aft 算法将时间划分为任意长度的任期(term),任期用连续的数字表示,看作当前 term 号。

  • 每一个任期的开始都是一次选举,在选举开始时,一个或多个 Candidate 会尝试成为 Leader。
  • 如果一个 Candidate 赢得了选举,它就会在该任期内担任 Leader。
  • 如果没有选出 Leader,将会开启另一个任期,并立刻开始下一次选举。raft 算法保证在给定的一个任期最少要有一个 Leader。

每个节点都会存储当前的 term 号,当服务器之间进行通信时会交换当前的 term 号;如果有服务器发现自己的 term 号比其他人小,那么他会更新到较大的 term 值。如果一个 Candidate 或者 Leader 发现自己的 term 过期了,他会立即退回成 Follower。如果一台服务器收到的请求的 term 号是过期的,那么它会拒绝此次请求。

raft日志

  • entry:每一个事件成为 entry,只有 Leader 可以创建 entry。entry 的内容为<term,index,cmd>其中 cmd 是可以应用到状态机的操作。
  • log:由 entry 构成的数组,每一个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。

entry 总是先被 Leader 添加到自己的 log 数组中,然后再发起共识请求,获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex,然后把对应的 entry 应用到自己的状态机中。

raft领导人选举

raft 使用心跳机制来触发 Leader 的选举。如果一台服务器能够收到来自 Leader 或者 Candidate 的有效信息,那么它会一直保持为 Follower 状态,并且刷新自己的 electionElapsed(选举占用时间),重新计时。

  • Leader 会向所有的 Follower 周期性发送心跳来保证自己的 Leader 地位。

  • 如果一个 Follower 在一个周期内没有收到心跳信息,就叫做选举超时,然后它就会认为此时没有可用的 Leader,并且开始进行一次选举以选出一个新的 Leader。

为了开始新的选举,Follower 会自增自己的 term 号并且转换状态为 Candidate。然后他会向所有节点发起 RequestVoteRPC 请求, Candidate 的状态会持续到以下情况发生:

  • 赢得选举
  • 其他节点赢得选举
  • 一轮选举结束,无人胜出

赢得选举的条件是:一个 Candidate 在一个任期内收到了来自集群内的多数选票(N/2+1) ,就可以成为 Leader。

在 Candidate 等待选票的时候,它可能收到其他节点声明自己是 Leader 的心跳,此时有两种情况:

  • 该 Leader 的 term 号大于等于自己的 term 号,说明对方已经成为 Leader,则自己回退为 Follower。
  • 该 Leader 的 term 号小于自己的 term 号,那么会拒绝该请求并让该节点更新 term。

aft使用了随机选举超时时间来避免因同时出现多个Candidate导致没有一个Candidate获得大多数选票,从而导致无线重复选举。每一个 Candidate 在发起选举后,都会随机化一个新的枚举超时时间,这种机制使得各个服务器能够分散开来,在大多数情况下只有一个服务器会率先超市;它会在其他服务器超时之前赢得选举。

1

评论区