论文阅读:raft协议简介

raft协议简介

最近这段时间真的是忙到飞起,网络协议的博客进行的进度也是龟速,操作系统内核更是一点进展都没有。不过毕竟还是要以工作为主呢,学习过程漫长也是急不得。最近需要实现一个分布式的Storage用于传输通道存储的高可用。因此看了一些分布式共识协议相关的论文和其他文章。其中最核心的一篇文章就是介绍raft的论文《In Search of an Understandable Consensus Algorithm》。通过这篇文章也让自己对raft的理解不仅仅停留在表面了,可以理解各个角色之间的交互以及对于数据一致性的理论保证论证。虽然网上有很多raft的介绍,也有这篇论文的全文翻译。但如果自己不从头到尾的把论文分析一遍,把里面的精华总结出来变成自己的,永远也无法理解这个协议的一些本质东西。我将从几个方面对这篇论文进行分析。首先是什么是分布式共识,在这个领域有什么经典的挑战,又是怎么解决的。第二个是分布式共识算法核心的理论基础。然后则是raft的基本概念,包括节点状态以及算法的几个核心性质。第四个是三个核心步骤(leader选举,日志复制,集群成员变更)。最后是对于该算法的一些注意的点,这些点影响了算法的正确性。ok,let’s start

什么是分布式共识算法

在单机时代,所有的程序都位于一台机器上的某一个进程中,因此什么事情都是由这一个进程来决定,比如我需要往磁盘写一条数据k=v,那么我只有两种情况,一种是我能写进去,另一种是我写不进去。然而,在分布式系统中,这个事情就变得复杂了很多,因为所有的事情都需要一个由多节点共同形成的分布式系统来对外提供服务,所以对于我是否写入了k=v这件事,需要整个系统统一知情后共同给出写入还是没写入的反馈。所谓分布式一致性的定义,也就是对于多个服务节点,给定一系列操作,在共识协议的保障下,对外给出一个确定的一致的结果(包括成功或失败)。理想情况下,分布式一致性应满足以下条件

  • 可终止性:一致性的结果需要在有限的时间内完成
  • 共识性:不同节点最终完成决策的结果相同
  • 合法性:决策的结果必然是合法的

这里所谓的共识协议就是保证分布式系统中的各个节点就某一项决策达成一致的算法

分布式共识算法面临的挑战

如果节点间的通信是可靠的,那么上面的分布性一致性也就比较容易达到,然而事实是残酷的,分布式系统中,节点之间是通过网络进行通信。在网络协议中我们知道,网络本身就是不可靠的,否则也就不会涉及TCP这种超级复杂的协议来应对网络中可能发生的各种问题了。不过就算有TCP的可靠保障,也避免不了不可靠的网络通信,著名的CAP原理中的P就是指网络分区,这种现象是天然存在的。所谓的网络分区就是在一段时间内,某台机器无法通过管理网络与其他节点进行通信。因此对于某台节点发出的某条决策/询问可能会收不到确定的回复,这里面接受和不接受都是所谓的“确定性回复”。这就可能会使得整个决策陷入停滞状态,导致可终止性无法达成,更差的,系统可能陷入到不可用的状态。同时在分布式系统中,节点故障时经常发生的。毕竟一个大型的分布式系统是有成百上千台机器统一对外提供服务,这里如果节点出现故障,上面的决策也不会收到确定性的回复。这是一种常见的问题,另一种问题就是,系统的代码健壮性出现问题,在某些特殊情况下会出现莫名其妙的bug,会做出不符合预期的举动,这些举动可能会伤害系统的正常运行。还有可能是系统间通信的网络包被恶意分子劫持,将消息进行篡改,以达到一些自己的目的。我们分别给这两种错误一个定义,把系统不响应成为非拜占庭错误,把而已响应成为拜占庭错误。这里所谓的拜占庭则源自Leslie Lamport有关拜占庭将军问题的论文,他是分布式领域最严格的容错模型,这个问题主要描述了这样一个事情:

有一组将军分别领导一队人马需要进攻一座成,每个将军并不能确定其他的将军是否是可靠的,也不知道他们发来的消息是否是可靠的,但是他们需要通过投票的方式决定是否攻打这个城市。在正常情况下,每一队人马都能够有一个统一的答复,要么选择进攻,要么选择撤退。这时候不管将军是否可靠,只要他们达成了统一的方案,选择进攻与撤退就没啥问题。但是怕的就是队伍中可能存在叛徒,他把一部分信息进行了恶意的篡改,欺上瞒下,使得一部分将军认为进攻的占了大多数,另一部分认为撤退占了大多数,所以这个恶意篡改的消息使得将军们没有采取统一的行动!

一般情况下,我们遇到的都是网络超时,机器故障等常规问题,这些撑死了就是决策呼声得不到响应,所以在大多数分布式共识协议中,他们都假设整个系统处于“非拜占庭”的情况下。raft也是做了这个假设。后面我们在raft协议中会详细说明。

刚才说到了错误的类型,那现在我们的目的就是找到一个共识算法,能够在上述所有错误出现时(包括拜占庭错误与非拜占庭错误),都能够保证整个系统的决策都是一致的。很可惜FLP impossibility否定了这个想法的正确性,它首先认为,不存在一个完美无缺的错误发现(Failure Detector)机制,例如有台机器你发出去的任何请求他都不回应你,这是你也不知道他是网络故障还是宕机了。在这种大前提下,不存在一个完美的共识算法是的系统中任何节点出现任何问题时都满足分布性一致性。

现实中是如何解决的

既然上文提到没有算法能够解决所有错误情况下分布式系统的一致性问题,那么类似paxos和raft这种协议又是怎么做的呢?这岂不是自相矛盾?实际上,这类算法是对问题的边界进行了界定。他们的一个做法是,在问题上做一个边界,就是计算和通信只需要在“安全时间”内完成即可。他们认为大多数情况下,计算和通信都可以在安全时间内结束。如果系统出现抖动,比如failure detect错误等,系统会进入某种循环状态,不让系统轻易地做出决定。当系统满足某些条件时,跳出循环做出决策。同时利用系统实现上的一些trick让系统不至于陷入永远等待从而丧失可用性的状态(raft中通过对系统平均故障时间的估计来设置通信时间,选举超时时间)。

分布式共识算法核心理论基础

在正式谈raft之前,还需要简单介绍下分布式共识算法所基于的理论工具。分布式共识协议在复制状态机的背景下产生的。在该方法中,一组服务器上的状态机计算相同的副本,即便某台机器宕机依然会继续运行。复制状态机是基于日志实现的。在这里有必要唠叨两句日志的特性。日志可以看做一个简单的存储抽象,append only,按照时间完全有序,注意这里面的日志并不是log4j或是syslog打出来的业务日志,那个我们称之为应用日志,这里的日志是用于程序访问的存储结构。有了上面的限制,使用日志就能够保证这样一件事。如图所示

我有一个日志,里面存储的是一系列的对数据的操作,此时系统外部有一系列输入数据,输入到这个日志中,经过日志中一系列command操作,由于日志的确定性和有序性,保证最后得到的输出序列也应该是确定的。扩展到分布式的场景,此时每台机器上所有了这么一个日志,此时我需要做的事情就是保证这几份日志是完全一致的。详细步骤就引出了论文中的那张经典的复制状态机的示意图

如图所示,server中的共识模块负责接收由client发送过来的请求,将请求中对应的操作记录到自己的日志中,同时通知给其他机器,让他们也进行同样的操作最终保证所有的机器都在日志中写入了这条操作。然后返回给客户端写入成功。复制状态机用于解决分布式中系统中的各种容错问题,例如master的高可用,例如Chubby以及ZK都是复制状态机,对于分布式一致性算法,通常满足以下性质:

  • 在非拜占庭错误下,保证安全性(不会返回不正确的结果)
  • 大多数机器运行,系统就可以正常运行,发生故障的机器在恢复正常后可以重新正常的加入到集群中
  • 不依赖时序来保证日志的一致性
  • 通常情况下,大多数机器就可以做出响应了,少数慢节点并不会拉低整个系统的性能

Raft基本概念与核心特性

说完了分布式共识的一些共性的特征后,下面我们这篇文章的主角终于要登场了,估计憋坏了吧哈哈。说道分布式共识算法,我们不得不提他的鼻祖,“臭名昭著”的paxos,当时Laslie Lamport的paxos协议几乎成为了一致性的代名词。包括现在,我们一提到分布式一致性,相信还是会脱口而出paxos。本文主要介绍的是raft,因此这里面不详细阐述paxos的原理了。这里只是为了引出raft的核心设计初衷,主要就是两点,首先就是paxos过于难以理解。第二就是他难以在实际场景下落地实现。有很多的系统涉及的期初都是想要完全实现一个paxos,但是最后实现的都是paxos-like的系统,例如Chubby以及ZK中的ZAB。所以作者从易于理解性以及可实现出发,重新对paxos进行诠释,最终形成了被工业界和学术界都广泛应用的raft算法。从可理解的角度,raft将整个算法归纳为三个基本步骤,分别为

  • leader选举
  • 日志复制
  • 集群成员变更

在论文的行文中也是分别介绍了这三块的具体实现,下面进行详细介绍。

Raft基本概念

首先我将整体串一遍raft,然后抽提出里面的相关概念进行说明。

一个raft协议通常包含若干个节点,通常5个(2n+1),它最多允许其中的n个节点挂掉。在任何时刻,任何节点都会处在下列三种状态之一,Leader,Follower以及Candidate。在系统正常运行的过程中,系统中会有一个Leader,其他节点都处于Follower状态,Leader负责处理所有来自客户端的请求,Follower如果收到请求会将请求路由到Leader,Follower只是被动的接收leader和candidate的请求,它自己不会对外发出请求。而candidate是用于做leader选举的状态。正常情况下leader会向follower汇报心跳,证明自己是当前系统的leader,这样所有follower就会老老实实负责同步leader的日志内容变更。当一段时间(随机时间)follower收不到leader的心跳信息时,会认为此时系统处于无leader状态,那么自己会转换到candidate状态并发起leader选举。

raft将整个时间分为若干个长度不一的片段,每一个段叫做一个任期(term),一次新的选主操作会触发一次term的更新,这里term就可以理解为逻辑时钟的概念。raft规定,一个term最多只有一个leader,可能没有,这是因为可能多个follower同时发现没有leader同时发起选主,瓜分选票。节点间在通信过程中会交换term,这样做的目的是为了唯一确认当前应该是谁在当政。如果某个candidate或leader发现自己的term小于当前的就会自觉地退到follower状态。同样的如果某个节点收到包含过期term的请求,则会直接拒绝该请求。

raft节点间使用RPC进行通信,基本的有关一致性算法的有两种基本RPC类型,分别为请求投票(RequestVotes)以及追加日志(AppendEntries),在日志压缩方面还有另外一种RPC类型(InstallSnapshot),后面会详细说明。其中日志中由若干个条目组成,每个条目都有一个Index标识。至此raft的所有概念都出来了,我简单列举一下:

Leader:节点状态一种,用于处理所有来自client请求,并将自己的日志追加行为广播到所有的follower上
Follower:节点状态一种,用于接收leader心跳,将leader的日志变更同步到自己的状态机日志中,在选举时给candidate投票
Candidate:节点状态一种,当follower发现没有leader时发起选主请求,极有可能成为下一任leader
term:用于标记当前leader/请求的有效性,一种逻辑时钟
Index:用于表示复制状态机中日志的条目
RequestVotes:candidate要求选主发送给Follower的RPC请求
AppendEntries:leader给follower发送的添加日志条目(心跳)的请求
InstallSnapshot:生成日志快照的RPC请求

Raft协议核心特性

文章中列举了五条raft的核心特性,也可以说这是raft设计的原则

  • 选举安全(Election Safety):在一个term中最多只能存在一个leader
  • leader日志追加(Leader Append-Only):leader不能覆盖或删除日志中的内容,只能新增日志
  • 日志匹配(Log Matching):如果两个日志有相同的index和任期,那么在这个任期前的所有日志条目全部相同
  • Leader强制完成(Leader Completeness):如果再某个任期内提交了某条日志条目,那么这个任期前面的日志也是确认被提交的
  • 状态机确定性(State Machine Safety):如果一台服务器将某一个index的日志条目应用到自己的状态机上,那么其他服务器不可能在同一个index上应用不同的日志条目

介绍完了raft的基本概念以及核心特性,接下来按照论文中给到的几个基本问题分别介绍raft中几个核心阶段。

Raft leader选举

raft协议通过心跳机制来触发leader选举,在节点启动阶段,会先以follower的角色启动。会试图接收leader发过来的心跳(心跳使用的是AppendeEntry的RPC请求,不过不携带任何的日志条目),当follower一段时间没有收到心跳,这里称为选举超时,超过了这个时间,follower会认定此时没有存活的leader。这时候就会触发一次新的leader选举。这时候,那个follower会把自己的身份变为candidate。这个节点会把当前的term+1,然后将票投给自己,然后发起RequestVote的请求给所有的follower。接下来可能会有三种不同的可能性。

  • 他自己获得了超过半数的投票,赢得选举,自己成为leader
  • 接收到了其他leader的RPC请求
  • 可能没有任何的获胜者(选票被多个candidate瓜分)

下面分别介绍这三种可能的情况

自己赢得选举

所有的follower在leader选举期间以first-come-first-serve的方式把票投给一个指定的candidte。同时协议规定每个任期内最多有一个candidate能够获得多数的选票。协议约定,一旦有一个candidate获取超过一半的选票。这个candidate立刻成为leader,同时发送心跳RPC请求维护自己的leader地位。

第二种情况就是,candidate在等待投票的过程中,可能收到另外一个leader发过来的AppendEntries的rpc请求,这个candidate会对leader的合法性进行判断,如果leader带来的term不小于当前的term,那么candidate认定当前发请求的leader是合法的,自己会退回到follower角色。但如果RPC中的term低于目前的term,那么candidate会选择拒绝这个RPC请求。

最后一种情况就是,没有任何一个candidate获得大多数follower的投票,那么他们又会选举超时,将当前term增加1,启动新一轮的leader选举。会有机制保证不会一直在这个过程中循环下去。

raft协议采用了随机的选举超时时间,防止选票被瓜分导致当前term内的选举失败。raft一般设置选举超时时间为150ms–300ms之间的随机数。这样做的好处是,能把各个follower认定leader失效的时间分散化。更加容易是的某些follower成为candidate后获得多数选票的概率。同时,每次candidate发起一次选举之初都会重置一个随机的选举超时时间。减少选票被瓜分的可能性。之所以将超时时间设置为随机,主要是为了使整个协议更好理解一些。之前例如设置等级的方式会存在一些可用性的问题,因此选择了随机选举超时时间的机制。

日志复制

上文介绍了leader选举,某个follower在选举超时后,会变为candidate发起新的一轮leader选举,当这个candidate获取了多数follower的投票之后。自动赢得选举,其他follower或candidate收到合法leader发送的心跳后会自动回退成为follower。在自己当选leader之后,就会自动开始承担整个系统的服务。所有client的每一个请求都包含一条将被复制状态机执行的命令。leader会将这条指令当成一个日志条目追加到日志中。然后会发起一条AppendEntries RPC给其他follower,进行日志条目的复制。当该条目安全的被复制之后,leader会正式在自己的状态机中执行这条指令,然后将执行结果返回给客户端。如果follower出现问题时,leader会不断的重试这个AppendEntries请求,知道所有的follower储存了这条日志条目。

如下图所示,日志如以下的形式进行组织,主要包含三部分,首先是日志需要被状态机执行的指令,第二个则是日志条目对应的任期。第三个则是标识日志位置的信息index。

这里面有一个概念叫做日志被”committed”,这个概念十分关键。Raft保证了所有被committed的日志最终都会被各个服务器持久化,并被其对应的状态机所应用。一旦某个日志条目被leader复制到多数的服务器上时,那么我们说这条日志被committed,同时,该日志条目之前的所有日志也是被提交的,包括其他此前leader创建的条目。这种提交方式在后面论证正确性的过程中也会证明是安全和正确的。Leader会持续跟踪他所知道的提交过的最新的日志条目(在AppendEntries请求中会带着这个索引号),这样其他的节点就知道哪些日志应该被提交。follower一旦知道日志已经被提交,那么这条日志会被应用到它自己的状态机中。

raft设计了日志机制来维护不同服务器之间高层次的一致性。这么做的目的是为了使得整个协议更加容易理解和可预测,同时这个也保证了协议的安全性。里面有如下的条目:

  • 两个包含相同index和term的日志条目中所包含的一定是相同的指令
  • 如果两个日志包含相同的index和term,那么他们前面的日志条目也会相同。

Leader在特定的任期内的一个index最多创建一个日志条目,日志条目在日志中的位置也不会改变。而第二个特性则是由AppendEntries请求本身一个对一致性的检查机制保障的。所有的AppendEntries请求都会带着前一个前一个日志条目的index和term,如果follower在他的日志中找不到包含相同index和term号的条目时,那么就会拒绝更新这个新的日志条目。这个过程会被抽象成一个递归的过程,当日志为空时是注定满足日志匹配性的性质,然后一致性的检查保证了日志在扩展的过程中也能保障日志匹配。因此,在AppendEntries返回成功时,leader就能够判断出follower的日志和自己相同。

在Raft算法中,leader通过强制follower复制自己的日志来维持不同节点之间的数据一致性,follower中和leader冲突的日志可能会被leader的日志覆盖掉。如果follower和自己的日志达成一致,leader一定要找到两者达成一致的最大index,删除follower日志中从那个index之后的所有日志,同时将自己那个一致点之后的所有日志同步到follower的日志上面。这些操作都包含在AppendEntries请求的一致性检测以及回复中。Leader会在给follower的请求中会维护一个这个leader要发给follower的下一个日志的索引号nextIndex。每当一个新的leader被选举出来之后,该leader将所有的nextIndex都设置成自己最后的一个日志条目+1。如果follower与leader不一致,那么后面的一致性检测会失败。在这次AppendEntries请求会被follower拒绝,leader收到拒绝请求后,会减小nextIndex然后进行重试(由于出现不一致的情况并不常见,所以这种逐次重试的机制还是可以接受的)直到某个日志条目达到一致,此时与leader所有不一致的日志都会被删除,然后开始复制当前这个leader中的日志。通过这种机制,在leader变更之后就不需要额外的机制来维护所有不一致的日志。

文章的5.4是安全性的论证,这里面我留到博客的最后,先把协议的总体介绍完毕,后面再进行对于协议中的一些小细节进行介绍。我们首先介绍协议对集群成员变更的处理。

集群成员变更

上面的协议都是假设集群中的节点是稳定的。但是实际上,集群中成员的变更是分布式系统中非常常见的现象。显然每当发生集群成员变更都需要重置协议,使得整个集群处于不可用的状态。这显然是不能被接受的,因此在进行协议设计的过程中一定需要考虑到成员变更这一正常现象的。

对于整个集群来讲,是不能出现有两个leader同时在某个term被选出的,那样一定会出现问题(脑裂),然而,如果直接生硬的将旧的集群配置更新为新的集群配置都会出现问题,论文中也有一个典型的事例说明了这一点。

这张图展示了集群配置变更的过程,在这个过程中,不同的服务器在不同的时刻更新服务器配置,因此就出现了两个leader同时被选出的状况,上面三个server同时使用的都是集群中原来就有的,后面两台机器是后来加入的,那么我们看到旧配置下的多数和新配置下的多数会产生分歧。那么也就是说两个不同的leader会在一个term内被选出,就会出现我上面说到过的那个问题。所以需要特殊的机制来处理集群变更,比如划分为两个阶段,一些协议采用的是第一阶段的过程中停掉旧的配置,这样就会使服务不可用。

raft采用的是一种联合一致性的机制来处理这个问题,设置了一种过渡阶段,在这种机制下能够在不停服务的情况下集群配置能够进行平滑的迁移。这里面的联合一致性是指新,老配置的结合

  • 日志条目会赋值给新,老配置中的所有服务器
  • 新,老配置的服务器都可以选举成为leader
  • 达成一直需要在两种配置上分别获取大多数的支持

下面的一张图展示了转换过程

其中,虚线表示创建但未提交的日志条目,实线表示最后被提交的日志条目。这些配置在日志复制过程中以特殊的日志条目来存储和通信。流程如下,leader首先创建了c_old_new的配置条目在自己的日志中,并提交到c_old_new中(c_old的大多数以及c_new的大多数),随后他创建c_new中的条目然后提交到c_new的大多数。防止c_old或c_new同时做出决定。这里面有几个问题需要重点关注

第一个问题,新的服务器在初始化过程中并没有任何日志条目。当这些服务器以这种状态加入到集群中,他们需要一定的时间来追赶日志,在这段时间内没有办法提交新的日志条目。为了避免这种可用性的间隔时间,raft在配置更新配置时使用了一个额外的阶段,在这个阶段,新的服务器加入到集群中,但是没有投票权(leader会把复制日志发送给他们,但是在决策过程中不考虑他们的决定)。一旦新的服务器追赶上了集群中的其他机器,重新配置他们就可以像正常处理流程一样进行。

第二个问题是,集群的leader可能不是新配置中的一员。这种情况下,leader会在提交完c_new之后回退。这中情况下,有一段时间leader管理的集群汇总不包括自己。他参与复制日志但并不考虑自己的决策。当c_new被提交时,会发生领导人过渡,这时是最早新的配置可以独立工作的时间点。在这之前可能只能才c_old选出leader。

第三个问题是,移除不再c_new中的服务器可能会扰乱集群。因为这些服务器将不会再收到新的心跳。在选举超时时,会进行新一轮的leader选举。这是当前的leader可能会回退为follower,但是这些被移除的服务器会再次超时,再次开始选举,会影响集群的可用性。为了能够避免这个问题,当服务器确认当前leader存在时,会忽略请求投票的Rpc。特别的,当服务器在当前最小选举超时时间内收到一个请求投票的rpc,他不会更新当前的任期号或者投出选票。这不会影响正常选举,每个服务器在开始一次选举之前,会等待一个最小的选举超时时间。但是有利于避免被移除的服务器干扰整个集群,如果leader能够发送心跳给集群,他就不会被更大的任务号废掉。

理论性验证

这部分实际上是论文中的一个小节,它在完整介绍完整个raft算法的日志复制和leader选举之后进行的描述,在基础的raft日志复制和leader选举的机制并不能保证每一个状态机按照相同的顺序执行相同的指令。论文中给了一个例子,一个follower可能会进入不可用状态的同时,leader提交了若干的日志条目,然后这个follower可能被选举为leader,并且覆盖这些日志条目,导致不同的状态机可能会执行不同的指令序列。因此论文在上面基本机制的基础上增加了一些额外的限制,保证了整个算法在运行过程中的安全性和可用性。

这个核心的限制为,在选举中进行了如下规定,所有能够被选出的leader必须存储所有已经提交的日志条目。这里有几个概念首先提到一下,首先如何衡量两份日志的新旧程度。这里的规定如下

  • 两份日志中最后一条日志的索引值和任期号定义了哪份日志比较新。如果两份日志最后的任期号不同,那么任期号大的日志比较新。如果任期号相同,则较长的日志比较新。

说完了日志新旧程度的规定,继续聊安全性的问题。在一些一致性算法中,允许不包含前面所有被提交的日志的节点被选举为leader,这些算法中会用额外的的机制来识别丢失的日志,并推送给新的leader。或者选举能够在很短的时间内进行。但是作者认为这种方式的开销过大了,因此规定了所有有资格被选为leader的节点应当存储了所有被commit的。这个限制保证了在更改了leader之后,无需在使用额外的机制检测由于切换leader过程中所损失的日志条目并进行修复。那么raft究竟是如何实现这个约束的呢?

raft规定,除非这个candidate包含了所有已经提交的日志条目,否则将阻止其投票,candidate为了能够赢得选举势必要联系集群中大部分节点,这意味着每一个已经提交的日志条目在这些服务器节点中至少存在于一个节点上。如果candidate的日志至少和大多数的服务器节点一样新,那么他一定有了所有提交的日志条目。所以在请求投票RPC中需要做如下的限制,RPC中包含了candidate的日志,投票人会拒绝那些日志没有自己新的投票请求。

这里面还有一点限制,就是不能简单判断日志条目被复制到大多数服务器上,就说明这条日志可以被提交,因为可能一条已经被大多数节点的老条目,也可能被未来的leader覆盖掉,下面的图中说明了这一点

图中是一个有5各节点的集群,首先在a中,S1是leader,将1复制到所有的服务器上,并且已经生成了2,复制到了S2上。但此时S1崩溃了,这是S5检测到,发起新的选举,任期号变为3,然后赢得了3和4的选票成为了新的leader,然后收到了一条不一样的日志条目放在了2处。到了c中,S5又crash了,此时S1重新启动,此时赢得了多数的选票,成为了新的leader,然后将自己在任期2中的日志复制到了S3上。此时实际上2这个日志已经被复制到了大多数机器上,同时生成了Term4日志。但是没等到正式提交,S1崩溃了,此时S5启动,他可以赢得S2,S3,S4的选票,由于他的日志任期号更新。这个时候他把自己的日志3复制到了其余所有的节点上。这个例子我们看到,旧的日志条目即便是被复制到了多数的服务器上,也可能被未来的leader覆盖掉。在e中,则是另一种情况,是说在C中的S1没有挂掉,而是将4复制到了大多数服务器上。4可以达到提交状态,这时候我们看到在4之前的那个日志2也一定被提交掉了。(由于leader的完整性)。

因此一句话概括这个限制,就是raft永远不会通过计算副本手的方式去提交一个之前任期的日志条目。只有leader当前任期里的日志才会采用这种方式进行提交。即便在某些情况下,leader可以知道一个老的日志条目是否被提交。

下面来总结一下raft保证安全性的两点限制

  • 当前任期内的日志条目必须被复制到了多数服务器上才能被提交
  • 一个candidate只有赢得了多数服务器的vote,才能成为leader,同时必须要求只有candidate比自己的日志新才能进行投票

下图给了一个例子,当前S1是leader(Term T),S1将日志复制到了S1,S2,S3上,之后发生了选举,S5赢得了S3,S4,S5的选票成为了term U的leader,由于也是赢得了大多数的投票,因此一定有一台机器保存了Term T的日志,又参与了Term U的投票(S3)同时我们要求,candidate一定要比自己的日志新,我才能给这个candidate投票,因此Term U中的candidate要比S3S4的日志新,因此S5日志一定是最新的。

其他情况

截止到上文,raft基本的一些机制已经介绍完了,这里面还有一些情况在这里简单说明下

首先是follower和candidate崩溃的情况,raft会在他们发生崩溃时无限重试这些请求,如果崩溃的机器重启了,就会收到一模一样的请求,Raft中的请求都是幂等的,所以正确性会有所保障。

然后就是一些时间的设置,例如广播时间,选举超时时间。这些时间的设置也是有讲究的,如果设置不合理,也会导致整个系统不可用。例如如果消息交换的时间比服务器故障时间长,candidate就没有充分的时间来赢得选举,这会导致raft没有leader变得不可用。raft假设如果满足这个时间,就可以正常提供服务。

所谓的广播时间就是从一个服务器并行的发送rpc给集群中的其他服务器并接受到相应的平均时间,选举超时时间这个我们在上面提到过,平均故障时间是对于一台服务器而言,两次故障之间的平均时间。一般来说,广播时间要比选举的超时时间小一个数量级,扎样,leader才能发送稳定的心跳来组织foller开始进入选举状态。通过随机化的选举超时时间,这个不等式也使得瓜分选票的机会很小。选举的超时时间也比故障时间小上几个数量级,这样系统能够稳定运行。当leader crash掉后,整个系统大约相当于会在选举超时时间内不可用。

广播时间和平均故障时间是系统决定的,但我们可以决定选举超时时间。raft的rpc需要接收到消息并将其保存在持久化的存储中,因此广播时间大约是0.5–20ms,这取决于存储的技术以及网络延迟。选举超时时间可设定为10–500ms,机器的平均故障时间会是几个月或更长,所以上述的不等式还是容易满足的。

至此我们介绍完了raft的全部内容,还有个日志压缩的问题,本文由于篇幅有点长所以没有强调,有兴趣的同学可以自行在论文中一探究竟。这篇文章终于完成也是不易,由于raft这种协议的复杂性,所以我会不断地加深对它的理解,同时修正这个博客。希望和大家一起进步。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章