跳转至

Raft Algorithm

复制状态机#

复制状态机（Replicated state machine）的概念

  • __相同的初始状态 + 相同的输入 = 相同的结束状态 __
  • 多个节点上，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态
  • 在Raft中，leader将客户端请求（command）封装到一个个log entry中，将这些log entries复制到所有follower节点，然后各节点按相同顺序应用log entries中的command，根据复制状态机的理论，各节点的结束状态肯定是一致的
  • 可以说，我们使用共识算法，就是为了实现复制状态机。一个分布式场景下的各节点间，就是通过共识算法来保证命令序列的一致，从而始终保持它们的状态一致，从而实现高可用的。（投票选主是一种特殊的命令）
  • 这里稍微拓展一点，复制状态机的功能可以更加强大。比如两个副本一个采用行存储的数据结构存储数据，另一个采用列存储，只要它们初始数据相同，并持续发给他们相同的命令，那么同一时刻从两个副本中读取到的结果也是一样的，这就是一种HTAP的实现方法（比如TiDB）

状态简化#

  • 在任何时刻,每一个服务器节点都处于__leader、follower__或__candidate__这三个状态之一
  • 相比于Paxos,这一点就极大简化了算法的实现,因为Raft只需要考虑状态的切换而不用像Paxos那样考虑状态之间的共存与互相影响

选举与状态迁移#

  • Raft把时间分割成任意长度的任期（term），任期用连续的整数标记

  • 每一段任期从一次选举开始。在某些情况下，一次选举无法选出leader（比如两个节点 收到了相同的票数），在这种情况下，这一任期会以没有leader结束；

一个新的任期（包含一次新的选举）会很快重新开始。Raft保证在任意一个任期内，最多只有一个 leader

  • Raft算法中服务器节点之间使用RPC进行通信，并且Raft中只有两种主要的RPC：
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//请求投票RPC Request
type RequestVoteRequest struct {
    term int //自己的当前任期号
    candidateld int //自己的ID
    lastLogindex int //自己最后一个日志号
    lastLogTerm int //自己最后一个日志的任期
}
//请求投票RPC Response
type RequestVoteRespon struct {
    term int //自己当前的任期号
    voteGranted bool //是否投票
} 
//追加日志RPC Request
type AppendEntriesRequest struct {
    term int //自己的当前任期号
    leaderId int //leader(即自己)的ID
    prevLogindex int //前一个日志的日志号
    prevLogTerm int //前一个日志的任期号
    entries []byte //当前日志体
    leaderCommit int //leader的已提交日志号
}
//追加日志RPC Response
type AppendEntriesResponse struct {
    term int //自己当前任期号
    success bool //如果follower包括前一个日志则为true
}    
//注:当leaderCommit > commitIndex,那么把commitIndex设为min(leaderCommit, index of last new entry)
//这样可以保证follower能够依据追加日志内容判断leader目前的提交状态
  • RequestVote RPC（请求投票）：由candidate在选举期间发起。
  • AppendEntries RPC（追加条目）：由leader发起，用来复制日志和提供一种心跳机制
  • 服务器之间通信的时候会交换当前任期号；如果一个服务器上的当前任期号比其他的__小__， 该服务器会将自己的任期号__更新__为较大的那个值
  • 如果一个candidate或者leader发现自己的任期号__过期__了，它会立即回到follower状态
  • 如果一个节点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求

领导者选举#

心跳机制#

​ Raft内部有一种心跳机制，如果存在leader，那么它就会周期性地向所有follower发送心跳，来维持自己的地位。如果follower一段时间没有收到心跳，那么他就会认为系统中没有可用的leader了，然后开始进行选举

选举流程#

​ 开始一个选举过程后，follower先增加自己的当前任期号，并转换到candidate状态。然后投票给自己，并且并行地向集群中的其他服务器节点发送投票请求（RequestVote RPC)

​ 对于没有成为candidate的follower节点,如果是__同一个任期__,会按照__先来先得__的原则投出自己的选票.如果自己当前任期号__大于__candidate的任期号,则不投出自己的选票.

最终会有三种结果：

  1. 它获得超过半数选票赢得了选举 -> 成为leader并开始发送心跳
  2. 其他节点赢得了选举 -> 收到新leader的心跳后，如果新leader的任期号不小于自己 当前的任期号，那么就从candidate回到follower状态
  3. 一段时间之后没有任何获胜者 -> 每个candidate都在一个自己的随机选举超时时间后 增加任期号开始新一轮投票。

​ 为什么会没有获胜者?比如有多个follower同时成为candidate,得票太过分散,没有任何一个candidate得票超过半数.论文中给出的随机选举超时时间为150~300ms(在实际应用中会根据具体情况调整,若太长则降低了Raft可用性,若太短则由于网络延迟无法选举出leader)

日志复制#

当leader被选举出来后,就会开始为客户端请求提供服务.这就引起一个问题:

客户端如何确定新leader是谁?#

首先客户端会随机挑选一个节点,这个节点有三种可能的状态:

  • leader:若为leader,则直接进行服务
  • follower:若为follower,则该follower可以通过__心跳__得知leader信息,然后告知client应该找谁
  • 无响应(node宕机):此种情况下,client直接找另一个节点即可

客户端指令如何执行?#

leader在接收到客户端的指令后,会把指令作为一个新的条目追加到__日志__中去.

而一条日志具有三个信息:状态机指令 & leader的任期号 & 日志号(日志索引)

raft_logs

leader会__并行__发送AppendEntries RPC给follower,让它们__复制__该条目.当该条目被__超过半数__的follower复制后,leader就可以在__本地执行该执行并把结果返回客户端__

我们把本地执行指令,也就是leader应用日志于状态机这一步,称作__提交__

Some Edge Cases#

​ 在处理客户端指令过程中,leader或者follower随时都有崩溃或处理缓慢的可能性,Raft必须要在有宕机的情况下继续支持日志复制,并且保证每个副本日志顺序一致(从而保证复制状态机的实现).那么就会有一下几种边界情况:

  • 如果follower因为某些原因没有给leader响应,那么leader会__不断重发__追加条目请求(AppendEntries RPC),哪怕leader已经回复了客户端.

  • 如果有follower从崩溃中恢复,此时Raft追加条目的__一致性检查__将生效.保证follower能按顺序恢复崩溃后的缺失的日志.

  • leader崩溃:此时崩溃的leader可能__已经复制了日志到部分follower但还没有提交__,而被选出的新leader又可能不具备这些日志,这样就有部分follower中的日志和新leader的日志不同.

Raft在这种情况下,leader通过__强制__follower复制它的日志(进行一致性检查)来解决不一致的问题,这意味着follower中跟leader__冲突的日志条目__会被新leader的日志条目__覆盖__(因为没有提交,所以不违背外部一致性)

一致性检查#

​ Raft的一致性检查：leader在每一个发往follower的追加条目RPC中，会放入前一个日志条目的索引位置和任期号，如果follower在它的日志中找不到前一个日志，那么它就会拒绝此日志，leader收到follower的拒绝后，会发送前一个日志条目，从而逐渐向前定位follower第一个缺失的日志.

​ 显然,这样的方式过于"低效"了,我们可以利用二分查找或者follower发送冲突条目的任期号以及自己存储的那个任期的第一个logIndex来快速定位冲突位置.

​ 不过在实践中,这样的优化是没有必要的,因为失败不常发生并且不太可能有很多不一致的日志条目.

​ 通过这种机制，leader在当权之后就不需要任何特殊的操作来使日志恢复到一致状态, Leader只需要进行正常的操作，然后日志就能在回复AppendEntries一致性检查失败的 时候自动趋于一致, Leader从来不会覆盖或者删除自己的日志条目(Append-Only).只要过半的服务器能正常运行，Raft就能够接受、复制并应用新的日志条目.在正常情况下，新的日志条目可以在一个RPC来回中被复制给集群中的过半机器,而单个运行慢的follower不会影响整体的性能.

安全性#

​ 领导者选举和日志复制两个子问题实际上已经涵盖了共识算法的全程，但这两点还不能 完全保证每一个状态机会按照相同的顺序执行相同的命令所以Raft通过几个补充规则完善整个算法，使算法可以在各类宕机问题下都不出错.这些规则包括:

  1. Leader宕机处理：选举限制
  2. Leader宕机处理：新leader是否提交之前任期内的日志条目
  3. Follower和Candidate宕机处理
  4. 时间与可用性限制

Leader宕机处理:选举限制#

​ 如果一个follower落后了leader若干条日志（但没有漏一整个任期），那么下次选举中，按照领导者选举里的规则，它依旧有可能当选leader。它在当选新leader后就永远也无法补上之前缺失的那部分日志，从而造成状态机之间的不一致。所以需要对领导者选举增加一个限制，保证被选出来的leader一定包含了之前各任期的所有__被提交__的日志条目

​ 具体通过以下方式实现:RequestVote RPC执行了这样的限制：RPC中包含candidate的日志信息(lastLogIndex & lastLogTerm)，如果投票者自己的日志比candidate的还新，它会拒绝掉该投票请求。Raft通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁的日志比较新。如果两份日志最后条目的任期号不同，那么任期号大的日志更“新”。如果两份日志最后条目的任期号相同，那么日志较长的那个更"新"

​ 那么,为什么这样做可以保证选举出来的leader一定包含了之前各任期的所有__被提交__的日志条目呢? 首先要明确,是需要超过半数的节点进行了日志复制以后,leader才会进行提交操作的,而如果一个candidate并不包含所有被提交的日志条目,那么至少还有一半的follower是拥有所有被提交的日志的也就是说这些follower的日志比candidate更"新",因此follower也就不会把票投给该candidate,则该candidate不可能当选leader.

Leader宕机处理:新leader是否提交之前任期内的日志条目#

​ 一旦__当前任期内__的某个日志条目已经存储到__过半__的服务器节点上,leader就知道该日志条目可以被__提交__了.而follower可以根据下一个AppendEntries RPC得知leader提交的日志信息:通过心跳或者新日志.

​ 当某个leader在提交某个日志条目__之前__崩溃了,以后的leader会试图完成该日志条目的__复制__,但并不会进行提交.Raft永远不会通过计算副本数是否达到半数的方式来提交之前任期内的日志条目.只有leader__当前任期内__的日志条目才通过计算副本数是否达到半数的方式来进行提交.一旦当前任期的某个日志条目以这种方式被提交,那么由于日志匹配特性,之前的所有日志条目也都会被间接地提交.

​ 注:如果出现leader向客户端返回结果,但还没有向follower发送心跳请求同步提交信息,而这时leader宕机了,那么"已经向客户端提交结果"这个信息无法再传达给整个集群了.当然,与客户端的交互并不属于Raft管辖的范围,论文中也因此没有进行讨论,这个问题交由客户端处理.通常,要解决这种问题,需要一个集群提交的概念,也就是集群中超过半数的节点都提交了,便可认为该指令已经提交.

Follower和Candidate宕机处理#

​ Follower和Candidate崩溃后的处理方式比leader崩溃要简单的多，并且两者的处理方式是相同的。如果follower或candidate崩溃了，那么后续发送给他们的RequestVote和AppendEntries RPCs都会失败。Raft通过__无限重试__来处理这种失败。如果崩溃的机器重启了，那么这些RPC就会成功地完成。如果一个服务器在完成了一个RPC，但是还没有相应的时候崩溃了，那么它重启之后就 会再次收到同样的请求。(Raft的RPC都是幂等的)

时间与可用性限制#

​ raft算法整体不依赖客观时间，也就是说，哪怕因为网络或其他因素，造成后发的RPC先到，也不会影响raft的正确性。（这点和Spanner不同）只要整个系统满足下面的时间要求，Raft就可以选举出并维持一个稳定的leader：

广播时间(broadcastTime)<<选举超时时间(electionTimeout)<<平均故障时间(MTBF)

​ 广播时间和平均故障时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft的RPC需要接受并将信息落盘，所以广播时间大约是0.5ms到20ms，取决于存储的技术。因此，选举超时时间可能需要在10ms到500ms之间。大多数服务器的平均故障间隔时间都在几个月甚至更长

集群成员变更#

​ 在需要改变集群配置的时候(如增减节点、替换宕机的机器或者改变复制的程度)，Raft可以进行 配置变更自动化。自动化配置变更机制最大的难点是保证转换过程中不会出现同一任期的两个leader，因为转换期间整个集群可能划分为两个独立的子集群

​ 在此章中,将会讲解多节点变更和单节点变更两种方式.

多节点变更#

​ 多节点变更的采用了一种两阶段的方法.集群先切换到一个过渡的配置,称之为__联合一致__(joint consensus).

​ 第一阶段,leader发起 Cold,new(也是一种AppendEntriesRequest),使整个集群进入__联合一致__状态,这是,所有RPC都要在新旧两个配置集群中都达到大多数才算成功.

​ 第二阶段,leader发起Cnew,使整个集群进入新配置状态.此时,所有RPC只要在新配置下能达到大多数就算成功.

​ 一旦某个服务器将该配置日志条目增加到自己的日志中,它就会用改配置来做出未来所有的决策(服务器总是使用它日志中最新的配置,无论该配置日志是否已经被提交).这也就以为这leader不用的等待Cold,new和Cnew返回,就会直接使用其中的新规则来作出决策.

​ 这样看起来会有一些问题,因此我们假设leader可以在集群成员变更的任何时候宕机,大概有一下几种可能:

  • leader在Cold,new未提交时宕机
  • leader在Cold,new已提交,但Cnew未发起时宕机
  • leader在Cnew已发起时宕机

leader在Cold,new未提交时宕机#

​ 假设集群中有S1~S3,S3为leader,此时扩充S4与S5,S3将Cold,new复制给S4与S5然后宕机(或者发生网络分区),此时S1与S2超时,它们之中由于采用旧配置(3节点),因此会产生一个leader,而S3由于处于联合一致状态,因此S3需要在旧配置和新配置(5节点)中均拿到半数选票才能当选,因此此时的S3并不能获得S1和S2的选票也就不能当选leader.这样也就导致集群成员变更失败,但是并不会产生两个leader.

​ 第二种情况,S1获得了Cold,new副本并且当选leader,但由于该副本并不属于自己任期,因此按照安全性限制,它不能提交Cold,new,不过可以让S1继续发送Cnew来进行集群成员变更.S1复制Cnew给其他节点,Cnew的提交规则如果按照新集群的配置,那么提交Cnew以后导致Cold,new也被提交,但是有可能并不满足联合一致提交规则,从而不安全(论文中并没有讨论这一情况).因此,在某些Raft实现中,会强制让Cnew按照联合一致规则进行提交,如果leader无法满足条件,就会自动退位.

leader在Cold,new已提交,但Cnew未发起时宕机#

​ 此时拥有Cold,new副本的节点在新旧配置集群中均过半,由于选举限制,新选出的leader一定具有Cold,new(拥有Cold,new的节点不会给没有该副本的节点投票),因此不可能出现两个leader的情况.

leader在Cnew已发起时宕机#

​ 一旦Cnew发起,就说明Cold,new已经被复制到大多数节点,也就不需要去管老配置了,如果leader在Cnew已发起时宕机,已经复制了Cnew的节点会只按新配置选举,没有复制Cnew的节点会按新老配置选举.如果有Cnew的节点当选,那么继续配置更新流程,如果没有Cnew的节点当选,它也会继续发送Cnew,因此不影响配置更新流程.

​ 有一种情况:S1S5缩减为S1S3,S3为leader,此时均有Cold,new,S2与S3拥有Cnew,如果S3宕机,由于没有Cnew的节点处于联合一致状态,因此S1S4S5需要在新旧配置集群总均获得大多数选票才能选举成功,而新集群中的S2S3由于拥有Cnew,因此并不会给它们投票,也就是说只有S2能够当选leader,因此已提交的Cnew也就不会被覆盖掉.

总结#

​ 在Cold,new发起但未提交时，raft集群还未进入联合一致状态。这时leader宕机，可以仅靠老 配置选出来的新leader。一旦Cold,new提交，raft集群就进入了联合一致状态，这时leader宕机，选出的新leader也要 符合联合一致的选票规则了。Cold,new提交后，leader就可以发起Cnew，从发起Cnew开始，集群就可以仅靠新配置进行选举和日志复制了。如果是缩减集群的情况下，leader可能自身就是缩减的对象，那么它会在Cnew复制完成后自动退位，这点我们接下来会进行补充说明.

​ 集群成员变更还有三个补充规则需要说明一下：

  • 新增节点时，需要等新增的节点完成日志同步再开始集群成员变更,这点是防止集群在新增节点还未同步日志时就进入联合一致状态或新配置状态，影响正常命令日志提交。
  • 缩减节点时，leader本身可能就是要缩减的节点，这时它会在完成Cnew的提交后自动退位。在发起Cnew后，要退出集群的leader就会处在操纵一个不包含它本身的raft集群的状态下。这时它可以发送Cnew日志，但是__日志计数时不计自身__
  • 为了避免下线的节点超时选举而影响集群运行，服务器会在它确信集群中有leader存在时拒绝Request Vote RPC。因为Cnew的__新leader不会再发送心跳给要退出的节点__，如果这些节点没有及时下线，它们会超时增加任期号后发送Request Vote RPC。虽然它们不可能当选leader，但会导致raft集群进入投票选举阶段，影响集群的正常运行。为了解决这个问题，Raft在Request Vote RPC上补充了一个规则：一个节点如果在最小超时时间 之内收到了Request Vote RPC，那么它会拒绝此RPC(因为不可能在最小超时时间内发生投票行为)。这样，只要follower连续收到leader的心跳，那么退出集群节点的Request Vote RPC就不会影响到raft集群的正常运行了

单节点变更#

​ 在Diego Ongaro的博士论文，和后续的大部分对raft实现中，都使用的是另一种更简单的单节点并更方法，即一次只增减一个节点，称为单节点集群成员变更方法。每次只增减一个节点，相比于多节点变更，最大的差异是__新旧配置集群的大多数，是一定会有重合的__。

raft_singleNodeChange

​ 如图所示,在四种情况下均只会产生一个leader(因为如果在旧配置中产生leader,那么新配置不能够获得足够选票,如果在新配置中产生leader,那么旧配置不能获得足够选票),因此直接解决了双leader问题.

​ 具体地,当新增一个节点,将会先开启日志同步流程,分多轮进行,每一轮leader记录当前日志位置,然后进行同步,在进行十轮(论文中给出的数)同步以后,可以认为新增节点的日志已经足够新了,可以进行配置变更.然后leader开始复制Cnew到各个节点,直到Cnew被复制到大多数节点,leader完成Cnew的提交,此时配置变更完成.

​ 如果在Cnew没有复制到大多数节点时leader宕机,那么选出的新leader可能具有Cnew,则继续变更流程,如果选出的新leader不具有Cnew,那么变更失败.

缺陷#

  • 联合一致支持一步完成机器的替换,而单节点变更需要两步(如a,b,c替换为a,b,d需要先变为a,b再变为a,b,d)
  • 单节点变更必定经历偶数节点的状态,这会降低集群的可用性.

raft_evenNodes

  • 连续两次变更,如果第一步变更过程中leader宕机,那么紧接着的第二次变更可能发生错误.

​ 例:现有集群S1~S4,S3为leader,其将Cnew1复制给S5,此时S3宕机,S1通过S1S2S4的选票当选,然后添加S6节点,并把Cnew2复制给S2和S6,此时Cnew2数量达到大多数(3 > 5/2, S1并不知道S5的存在),并把Cnew2提交.接着S1宕机,S3通过S4和S5的选票当选leader(此时S3并不知道S6的存在).此时S3会继续变更流程,将Cnew1复制到所有节点(不包括S6),这样的话S1和S2已提交的Cnew2就被覆盖了,这是不安全的.

​ 解决方法就是规定新leader必须提交一条自己任期内的__no-op日志__(即节点当选leader以后立刻发送一个自己当前任期的空日志体的AppendEntries RPC。这样就可以把之前任期内满足提交条件的日志都提交了),之后才能进行单节点集群成员变更.

​ 如例子中的情况,当S1当选新leader以后,就先通过no-op操作把未提交的Cnew1给覆盖掉,然后再进行Cnew2的复制,这样就没有问题了

总结与性能测试#

深入理解复制状态机#

把复制状态机需要同步的数据量按大小进行分类，它们分别适合不同类型 的共识算法。

  • 数据量非常小，如集群成员信息、配置文件、分布式锁、小容量分布式 任务队列。

无leader的共识算法(如Basic Paxos)，实现有Chubby等。

  • 数据量比较大但可以拆分为不相干的各部分，如大规模存储系统。

有leader的共识算法(如Multi Paxos，Raft, ZAB)，实现有GFS，HDFS, zookeeper等

  • 不仅数据量大，数据之间还存在关联。一个共识算法集群容纳不了所有的数据。这种情况下，就要把数据分片（partition）到多个状态机中，状态机之间通过两阶段提交来保证一致性

这类场景就主要是一些如Spanner、OceanBase、TiDB等支持分布式事务的分布式数据库。它们通常会对Paxos或Raft等共识算法进行一定的改造，来满足事务级的要求#

Raft基本概念总结#

共识算法的三个主要特性：#

  • 共识算法可以保证在任何__非拜占庭情况__下的正确性。通常来说，共识算法可以解决网络延迟、网络分区、丢包、重复发送、乱序问题，无法解决拜占庭问题（如存储不可靠、消息错误）。
  • 共识算法可以保证在大多数机器正常的情况下集群的高可用性，而少部分的机器缓慢不影响整个集群的性能。
  • 不依赖外部时间来保证日志的一致性。这一点既是共识算法的优势，因为共识算法不受硬件影响，不会因外部因素造成错误。但也造成了一些限制，让共识算法受网络影响很大，在异地容灾场景下，共识算法的支持性比较差。

raft区分于其他共识算法的三个特征：#

  • Strong leader：在Raft中，日志只能从leader流向其他服务器。这简化了复制日志的管理，使得raft更容易理解。
  • Leader election: Raft使用随机计时器进行leader选举。这只需在任何共识算法都需要的心跳（heartbeats）上增加少量机制，同时能够简单快速地解决冲突。
  • Membership changes: Raft使用一种共同一致(joint consensus)的方法来处理集群成员变更的问题，变更时，两种不同的配置的大多数机器会重叠。这允许整个集群在配置变更期间可以持续正常运行

no-op补丁#

​ 一个节点当选leader后，立刻发送一个自己当前任期的空日志体的AppendEntries RPC。这样，就可以把之前任期内满足提交条件的日志都提交了。一旦no-op完成复制，就可以把之前任期内符合提交条件的日志保护起来了(因为如果no-op成功提交说明之前的日志已经复制到大多数节点,可以提交了)，从而就可以使它们安全提交。因为没有日志体，这个过程应该是很快的。目前大部分应用于生产系统的raft算法，都是启用no-op的。

日志压缩机制#

​ 为什么要进行日志压缩呢，因为随着raft集群的不断运行，各状态机上的log也在不断地累积，总会有一个时间会把状态机的内存打爆，所以我们需要一个机制来安全地清理状态机上的log。Raft采用的是一种快照技术，每个节点在达到一定条件之后，可以把当前日志中的命令都写入自己的快照，然后就可以把已经并入快照的日志都删除了。快照中一个key只会留有最新的一份value，占用空间比日志小得多。(类似AOF重写)

​ 如果一个follower落后leader很多，如果老的日志被清理了，leader怎么同步给follower呢？Raft的策略是直接向follower发送自己的快照。

只读操作处理#

​ 要追求强一致性读的话，就需要让这个读的过程或结果，也在大多数节点上达到共识。

​ 稳妥的方法：把读也当做一个log，由leader发到所有的所有节点上寻求共识，这个读的log提 交后，得到的结果是一定符合线性一致性的。

优化后的方法，符合以下规则：

  • 线性一致性读一定要发往leader。

  • 如果一个leader在它的任期内还没有提交一个日志，那么它要在提交了一个日志后才能反馈client读请求。（可以通过no-op补丁来优化这一点）因为只有在自己任期内提交了一个日志，leader才能确认之前任期的哪些日志已被提交，才不会出现已提交的数据读取不到的情况.安全性规则能保证被选出的leader一定具有所有已被提交的日志，但它可能有的日志还没有提交，它并不能确定哪些日志是已提交的，哪些日志没提交，而在它任期内提交一个日志，就能确定这一点

  • 在进行读操作前，leader要向所有节点发送心跳，并得到大多数节点的反馈。（为了确保自己仍是leader）

  • leader把自己已提交的日志号设为readIndex，只要leader应用到了readIndex的日志，就可以查询状态机结果并返回client了

Q:leader应用到readIndex就可以查询状态机结果怎么理解，readIndex不就是leader的已提交日志号吗为什么还要等待应用?

A:实际上raft中的一个节点提交(落盘)一个日志，和把这个日志里的命令应用到状态机，并不是一个动作，虽然它们两个往往同时发起的。这个有点像数据库中，写write ahead log和修改库中的数据，也是往往同时发生，但它们操纵的毕竟不是同一个数据对象。在这个条件下，已提交的日志未必已经应用，还需要确认这个日志已经应用到状态机，才能开始读取状态机。 如果我们只讨论raft的话，大部分情况下其实没必要太过于纠结这一点，所以我在视频里大部分时候都是默认commit后就把日志应用到状态机了。

  • leader也可以不用等待应用到readIndex，在确认自己是leader后可以直接向客户端返回读结果，前提是当前leader必须已经应用了当前term的第一个Log。(因为leader自身是拥有所有client请求数据的)

​ 优化过后的线性一致性读，也至少需要一轮RPC（leader确认的心跳）。并不比写操作快多少（写操作最少也就一轮RPC）。所以，还可以更进一步，因为读的这轮RPC仅仅是为了确认集群中没有新leader产生。那么如果leader上一次心跳发送的时间还不到选举超时时间的下界，集群就不能选出一个新leader，那么这段时间就可以不经过这轮心跳确认，直接返回读的结果。（但不建议使用这种方法,因为分布式系统由于时钟偏移、full GC之类的情况,导致时间是不可靠的）

​ 如果不要求强一致性读，怎么样利用follower承载更大的读压力呢?

  • follower接收到读请求后，向leader请求readIndex(注意,这里是follower主动向leader请求数据,因此不使用leaderCommit)
  • follower等待自身状态机应用日志到readIndex
  • follower查询状态机结果，并返回客户端

性能及与Paxos比较#

分析Raft的性能#

​ 最根本的，每完成一个日志（命令）的复制与提交，需要的网络（RPC）来回次数。raft在理想情况下，只需要一次AppendEntries RPC来回即可提交日志（理论上的极限）。

影响Raft性能的因素以及优化方法:

  • 选举及维持leader所需的代价->合理设置选举超时时间

  • Batch：一个日志可以包含多个命令，然后批量进行复制，来节省网络

  • Pipeline: leader不用等待follower的回复，就继续给follower发送下一个日志

leader可以同时进行自己数据的落盘以及发送给follower

  • Multi-Raft：将数据分组，每组数据是独立的，用自己的raft来同步

Raft与Paxos比较#

​ “raft不允许日志空洞，所以性能没Paxos好。”

​ 这里的Paxos，实际上指的是一个能完美处理所有日志空洞带来的边界情况，并能保证处理这些边界情况的代价，要小于允许日志空洞带来的收益的共识算法。

​ 总结：raft确实有不允许日志空洞这个性能上限，但大部分系统实现，连raft的上限，都是远远没 有达到的。所以无需考虑raft本身的瓶颈。

​ raft允许日志空洞的改造,那便是ParallelRaft

总结#

​ Raft论文原文中有这样一段话:在所有基于leader的共识算法中，leader最终都需要存储所有已提交的日志

​ 在一些共识算法中，一个leader可以在被选举出来时没有所有已提交的日志，然后通过额外的机制来识别并补充这些日志。但__额外的机制__(如parallel Raft)就会造成更高的复杂度和理解成本。所以Raft选择一种更简单的方式，来使__leader在被选出时天然就具有所有已提交的日志__。这样就可以让__日志只能从leader流向 follower，leader永远不会复写自己的日志__

最后更新: September 25, 2023
创建日期: September 24, 2023