3410dfac69e0065e19f60253b6f4d184
RAFT 协议理解

RAFT 协议理解

RAFT 协议是什么?

Raft 是用来管理复制日志(replicated log)的一致性协议。它跟 multi-Paxos 作用相同,效率也相当,但是它的组织结构跟 Paxos 不同。这使得 Raft 比 Paxos 更容易理解并且更容易在工程实践中实现。

有一个非常好的关于 raft 协议的动画:Raft 协议动画

Raft设计目标

设计 Raft 算法过程中有几个目标:

  • 它必须提供一个完整的实际的系统实现基础,这样才能大大减少开发者的工作;
  • 它必须在任何情况下都是安全的并且在典型的应用条件下是可用的;并且在正常情况下是高效的。
  • 最重要的目标也是最大的挑战是可理解性。它必须保证能够被大多数人容易地理解。另外,它必须能够让人形成直观的认识,这样系统的构建者才能够在现实中进行扩展。

raft使用了两种通用的技术来解决这个问题:

  • 第一个技术就是问题分解:只要有可能,我们就将问题分解成几个相对独立的,可被解决的、可解释的和可理解的子问题。例如,Raft 算法被我们分成 leader 选举,日志复制,安全性和成员变更几个部分。

  • 第二个方法是通过减少状态的数量来简化状态空间,使得系统更加连贯并且尽可能消除不确定性。所有的日志是不允许有空洞的,并且 Raft 限制了使日志之间不一致的方式。尽管在大多数情况下我们都试图去消除不确定性,但是在某些情况下不确定性可以提高可理解性。随机化方法虽然引入了不确定性,但是他们往往能够通过使用相近的方法处理可能的选择来减少状态空间。使用随机化来简化 Raft 中的 leader 选举算法

Raft协议的作用

一致性算法允许多台机器作为一个集群协同工作,并且在其中的某几台机器出故障时集群仍然能正常工作。

Raft 协议基本概念

复制状态机(State Machine Replication)

状态机复制是实现容错服务的一种常规方法,主要通过复制服务器,并协调客户端和这些服务器镜像间的交互来达到目标。这个方法也同时提供了理解和设计复制管理协议的一套基本框架。

决定性是提供容错支持的理想特性。直观而言,假如系统存在多分拷贝,其中一个的故障会因为与其它系统的状态或者输出有差异,而变得明显。只要简单推理下,就可以知道实现容错性需要最少三份拷贝,在一个系统出错的情况下,其它两个系统可以供我们比较状态和输出。而两份拷贝显然不够,因为我们无从判别出错的是哪一个。再进一步推演,就可以知道具备三份拷贝的系统最多能支持单系统故障(随后必须修复或者替换掉故障拷贝)。假如有多余一个拷贝出现故障,那么三份状态或者输出都会互不相同,导致无法判断正确的拷贝。通常而言,一个支持F个故障的系统,必须至少包含2F+1份拷贝(也称为镜像)状态机复制。多余的拷贝被用作区分正确和故障拷贝的证据。特殊的情况也可以改良这些制约目前的推理都预设这些镜像仅仅是面临随机的独立故障,比如内存错误或者硬盘崩溃。但源自某些镜像尝试欺骗系统而带来的问题,也同样能被状态机复制通过隔离变化来处理。

在Raft中,问题可以分解为如下几个过程:

  • 领导选取

  • 日志复制

  • 成员变化

节点状态

每个节点有三个状态,他们会在这三个状态之间进行变换。客户端只能从主节点写数据,从节点里读数据。

  • 领导者 Leader
  • 候选人 Candidate
  • 追随者 Follower

初始化状态时,三个节点都是Follower状态,并且term为0。

每个节点会分配一个随机的选举超时时间(election timeout)。在这个时间内,节点必须等待,不能成为Candidate状态。

大多数

假设一个集群由N个节点组成,那么大多数就是至少N/2+1。例如:3个节点的集群,大多数就是至少2;5个节点的集群,大多数就是至少3。

任期(Term)

Raft 算法将时间划分成为任意不同长度的任期(term)。任期用连续的数字进行表示。每一个任期的开始都是一次选举(election),一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举,它就会在该任期的剩余时间担任领导人。在某些情况下,选票会被瓜分,有可能没有选出领导人,那么,将会开始另一个任期,并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

在raft算法中,比较谁的数据最新有2个参考指标,任期和logIndex,任期大的节点,数据一定最新,任期一样的话,就要比较该任期内谁的MaxLogIndex最大了。引入任期的概念可以简化数据比较的精度。

  • 任期在 Raft 算法中充当逻辑时钟的作用,这使得服务器节点可以发现一些过期的信息比如过时的 leader 。

  • 每一个服务器节点存储一个当前任期号,该编号随着时间单调递增。

  • 服务器之间通信的时候会交换当前任期号;

  • 如果一个服务器的当前任期号比其他的小,该服务器会将自己的任期号更新为较大的那个值

  • 如果一个 candidate 或者 leader 发现自己的任期号过期了,它会立即回到 follower 状态。(所以说老leader如果发生了网络分区,后来接收到新leader的心跳的时候,比拼完任期之后,会自动变成follower。

  • 如果一个节点接收到一个包含过期的任期号的请求,它会直接拒绝这个请求。

举个例子

例如现在节点a等待168ms , 节点b等待210ms , 节点c等待200ms 。由于a的等待时间最短,所以它会最先成为Candidate,并向另外两个节点发起投票请求,希望它们能选举自己为Leader。

另外两个节点收到请求后,假设将它们的投票返回给Candidate状态节点a,节点a由于得到了大多数节点的投票,就会从Candidate变为Leader。接下来,这个分布式系统所有的改变都要先经过节点a,即Leader节点。

如果某个时刻,Follower不再收到Leader的消息,它就会变成Candidate。然后请求其他节点给他投票(类似拉票一样)。其他节点就会回复它投票结果,如果它能得到大多数节点的投票,它就能成为新的Leader。

日志复制

日志格式

日志由有序编号的日志条目组成。每个日志条目包含它被创建时的任期号(每个方块中的数字),并且包含用于状态机执行的命令。如果一个条目能够被状态机安全执行,就被认为可以提交了。每个日志条目也包含一个整数索引来表示它在日志中的位置。

复制过程

  • 所有的写请求会首先由leader即节点接收到,并且写入一条日志。由于这条日志还没被其他任何节点接收,所以它的状态是uncommitted

  • 为了提交这条日志,Leader会将这条日志通过心跳消息复制给其他的Follower节点。

  • 一旦有大多数节点成功写入这条日志,那么Leader节点的这条日志状态就会更新为committed状态。

  • Leader节点然后通知其他Follower节点,其他节点也会将值更新。这个时候集群的状态是完全一致的,这个过程就叫做日志复制(Log Replication)

leader通过强制追随者们复制它的日志来处理日志的不一致。这就意味着,在追随者上的冲突日志会被领导者的日志覆盖。为了使得追随者的日志同自己的一致,领导人需要找到追随者同它的日志一致的地方,然后删除追随者在该位置之后的条目,然后将自己在该位置之后的条目发送给追随者。这些操作都在 AppendEntries RPC 进行一致性检查时完成。

领导者永远不会覆盖自己已经存在的日志条目;

日志永远只有一个流向:从领导者到追随者;

在Raft算法中,当一个日志被安全的复制到绝大多数的机器上面,即AppendEntries RPC在绝大多数服务器正确返回了,那么这个日志就是被提交了,然后领导者会更新commit index

日志压缩

top Created with Sketch.