精华内容
下载资源
问答
  • raft协议
    千次阅读
    2021-05-27 15:46:53

    概述

    分布式共识问题(一致性问题)

    什么是分布式共识问题呢 ?简而言之即:
    分布式环境下系统集群存在很多节点,每个节点都可提出议案,我们需要:

    1. 对多个节点提出的议案作裁决并得到一个一致的结论
    2. 让每个节点都感知到最终结论,从而使集群整体状态保持一致
    3. 允许故障一部分节点宕机后集群仍可正常工作,先前通过的议案仍可访问,集群状态仍维持一致;

    举例:

    1. 比如a=2,所有计算机达成一致之后他们的内存中a就是等于2且不可改变。此决定一旦达成不可更改。
    2. 由于各个计算机是相互独立的,故障随时可能发生,在所有计算机上总是达成一致是不可能的。我们当然可以设计一个所有计算机必须都正常才能达成一致的系统,但是一旦发生故障,这个一致性系统就会变得不可用,抵御风险的能力比较弱。所以主流的一致性协议都是能够容忍少数(小于50%)的计算机故障。

    Raft协议

    Raft是一种实现分布式共识(一致性)的协议:也就是多个节点达成一致的协议。
    Raft 算法想解决的核心问题是分布式共识问题。

    分布式存储系统的核心问题之一:维护多个副本的数据一致性。
    raft将一致性算法分为了几个部分,包括:领导选取(leader selection)、日志复制(log replication)、安全性(safety), 成员变更

    前置定义

    三种角色

    一个Node任一时刻肯定处于以下三状态之一:

    • Leader(领导者):leader用来和客户端交互,然后leader将接收到的数据,通知给其他Node。接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。任意时刻最多只有一个Leader
    • Follower(跟随者):接受并持久化Leader同步的日志,在Leader通知日志可以提交之后,提交日志。
    • Candidate(候选人):Leader选举过程中的临时角色

    正常工作期间只有Leader和Followers

    term任期

    任期(term)意思是一个时间周期,每一个term的开始都是Leader选举。
    在成功选举Leader之后,Leader会在整个term内管理整个集群并进行正常操作执行他的当前任期。
    如果Leader选举失败,该term就会因为没有Leader而term结束。
    然后过了一个term就开始下一轮选举,新leader执行他的操作。

    RPC

    Raft 算法中服务器节点之间通信使用远程过程调用(RPC)
    使用了三种RPC:

    1. RequestVote RPC:候选人在选举期间发起。
    2. AppendEntries RPC:领导人发起的一种心跳机制,复制日志也在该命令中完成。
    3. InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。

    1. 领导选举

    选出Leader非常重要。

    两个时间

    1. 选举计时器机制:每个node有一个计时器,是一个随机的值(150ms and 300ms),也叫选举时间,表示的是follower等待成为leader的时间。选举时间超时,则该follower开启选举。
    2. 心跳机制:leader会定期发送心跳给follower,心跳时间比选举时间要短,每次心跳从leader发送给follower时,follower就重新进行选举时间计时,所以当选举时间超时时那么说明心跳时间肯定超时了,这时重新进行选举。

    选举过程

    1. 服务器启动时,所有节点最初都是follower,follower听不到leader的心跳消息时,选举时间超时(心跳肯定超时),说明当前没有leader(或者leader挂了)。
    2. 此时开始选举阶段:谁的选举计时先完成则此follower先成为candidate。Follower将其当前term加一,因为这是开启了一个新的任期。
    3. candidate争取选票,它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。
    4. 此时可能出现以下三种情况:
      1. 如果争取到超过半数的选票,那么该candidate成为leader
      2. 收到了Leader的消息,表示有其它服务器已经抢先当选了Leader;
      3. 没有服务器赢得多数的选票:比如说两个candidate同时发起选举,Leader选举失败,等待选举时间超时后发起下一次选举。
    5. 当选举完成:新Leader会立刻给所有节点发消息,避免其他节点触发新的选举。当候选人被告知Leader已产生,则自行切换为Follower,后面leader会定期发送心跳给follower

    详细动图查看非常容易理解http://thesecretlivesofdata.com/raft/#home

    2. 日志复制(同步)

    https://juejin.cn/post/6844903665275404295

    概念

    日志复制的目的:保证数据一致性(将数据复制到所有节点)
    Leader选出后,就开始接收客户端的请求,所有的请求都需要通过leader然后到达follower,并将日志传递给follower然后保证follower和leader的一致性
    Leader 使用Append Entries 消息,这个消息是使用在心跳中的。

    • 状态机:通常指的是一个输入输出程序或应用,负责执行日志中记录的操作。
    • 已提交:Raft 保证已提交的日志条目是持久化的,并且最终会被所有可用的状态机执行。
    • 规则:leader只接收并发送日志,不删除日志。follower只接收日志发送的信息。

    日志格式

    日志索引,任期,条目,已提交标志

    日志复制步骤

    1. Leader接收到指令后写入到本地日志,在随后的心跳中(AppendEntries)向其他follower发送该指令
    2. 每个follower收到指令会,存储日志,并向leader立即返回确认
    3. leader等待收到过半follower响应确认后,将该条目标志位已提交状态(也就是当日志复制到大多数机器上的时候,就认为该跳命令可以提交了),并发往leader状态机执行该指令执行完成后返回结果给客户端
    4. leader在后续心跳包(AppendEntries)中通知所有追随者该条目为已提交状态。follower就也会更新该条目为已提交状态并且在各自状态机中执行该指令。

    日志一致性

    通过日志复制的步骤,我们就可以让follower和leader保持一致
    下图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目,也有可能包含一些Leader没有的条目,也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

    Leader通过强制Followers复制它的日志来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。

    总结一下就是:当 leader 和 follower 日志冲突的时候,leader 将校验 follower 最后一条日志是否和 leader 匹配,如果不匹配,将递减查询,直到匹配,匹配后,删除冲突的日志。这样就实现了主从日志的一致性。

    3. 安全性

    在Raft协议中,所有的日志条目都只会从Leader节点往Follower节点写入,且Leader节点上的日志只会增加,绝对不会删除或者覆盖。
    这意味着Leader节点必须包含所有已经提交的日志,即能被选举为Leader的节点一定需要包含所有的已经提交的日志。因为日志只会从Leader向Follower传输,所以如果被选举出的Leader缺少已经Commit的日志,那么这些已经提交的日志就会丢失,显然这是不符合要求的。
    这就是Leader选举的限制:能被选举成为Leader的节点,一定包含了所有已经提交的日志条目。

    Raft增加了如下两条限制以保证安全性:

    1. 拥有最新的已提交的log entry的Follower才有资格成为leader。能被选举成为Leader的节点,一定包含了所有已经提交的日志条目。
    2. Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志,旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。

    参考资料

    https://juejin.cn/post/6856630564276371470
    http://thesecretlivesofdata.com/raft/#home
    https://raft.github.io/raft.pdf
    https://knowledge-sharing.gitbooks.io/raft/content/chapter5/5-4.html

    更多相关内容
  • raft协议的go版本,实现功能包括: 选主投票 节点心跳 日志同步 成员变更 日志压缩 存在的问题或需要解决的问题: 完善snapshot快照同步逻辑 成员变更,每次只允许变动一个节点 非leader节点转发请求,考虑改用rpc...
  • Raft协议

    2022-06-25 08:40:48
    Raft协议

    基本概念

    名词解释
    Raft协议一共包含如下3类角色:
    ● Leader(领袖):领袖由群众投票选举得出,每次选举,只能选出一名领袖;
    ● Candidate(候选人):当没有领袖时,某些群众可以成为候选人,然后去竞争领袖的位置;
    ● Follower(群众):这个很好理解,就不解释了。
    然后在进行选举过程中,还有几个重要的概念:
    ● Leader Election(领导人选举):简称选举,就是从候选人中选出领袖;
    ● Term(任期):它其实是个单独递增的连续数字,每一次任期就会重新发起一次领导人选举;
    ● Election Timeout(选举超时):就是一个超时时间,当群众超时未收到领袖的心跳时,会重新进行选举。

    角色转换

    在这里插入图片描述
    这幅图是领袖、候选人和群众的角色切换图,总结如下
    ● 群众 -> 候选人:当开始选举,或者“选举超时”时
    ● 候选人 -> 候选人:当“选举超时”,或者开始新的“任期”
    ● 候选人 -> 领袖:获取大多数投票时
    ● 候选人 -> 群众:其它节点成为领袖,或者开始新的“任期”
    ● 领袖 -> 群众:发现自己的任期ID比其它节点分任期ID小时,会自动放弃领袖位置

    选举

    领导人选举
    在这里插入图片描述
    成为候选人:每个节点都有自己的“超时时间”,因为是随机的,区间值为150~300ms,所以出现相同随机时间的概率比较小,因为节点B最先超时,这时它就成为候选人。
    在这里插入图片描述
    选举领导人:候选人B开始发起投票,群众A和C返回投票,当候选人B获取大部分选票后,选举成功,候选人B成为领袖。
    在这里插入图片描述
    心跳探测:为了时刻宣誓自己的领导人地位,领袖B需要时刻向群众发起心跳,当群众A和C收到领袖B的心跳后,群众A和C的“超时时间”会重置为0,然后重新计数,依次反复。
    这里需要说明一下,领袖广播心跳的周期必须要短于“选举定时器”的超时时间,否则群众会频繁成为候选者,也就会出现频繁发生选举,切换Leader的情况。
    在这里插入图片描述

    领袖挂掉情况

        当领袖B挂掉,群众A和C会的“选举定时器”会一直运行,当群众A先超时时,会成为候选人,然后后续流程和“领导人选举”流程一样,即通知投票 -> 接收投票 -> 成为领袖 -> 心跳探测。
    

    在这里插入图片描述

    出现多个候选者情况

    当出现多个候选者A和D时,两个候选者会同时发起投票,如果票数不同,最先得到大部分投票的节点会成为领袖;如果获取的票数相同,会重新发起新一轮的投票。
    在这里插入图片描述
    当B成为新的候选者,此时的任期Term为5,发起新一轮的投票,其它节点发起投票后,会更新自己的任期值,最后选择新的领袖为B节点。
    在这里插入图片描述

    日志复制

    复制状态机
    复制状态机的基本思想是一个分布式的状态机,系统由多个复制单元组成,每个复制单元均是一个状态机,它的状态保存在操作日志中。如下图所示,服务器上的一致性模块负责接收外部命令,然后追加到自己的操作日志中,它与其他服务器上的一致性模块进行通信,以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制,那么每一个服务器的状态机都将按照操作日志的顺序来处理它们,然后将输出结果返回给客户端。
    在这里插入图片描述

    数据同步流程

    数据同步流程,借鉴了“复制状态机”的思想,都是先“提交”,再“应用”。当Client发起数据更新请求,请求会先到领袖节点C,节点C会更新日志数据,然后通知群众节点也更新日志,当群众节点更新日志成功后,会返回成功通知给领袖C,至此完成了“提交”操作;当领袖C收到通知后,会更新本地数据,并通知群众也更新本地数据,同时会返回成功通知给Client,至此完成了“应用”操作,如果后续Client又有新的数据更新操作,会重复上述流程
    在这里插入图片描述
    日志原理
    每一个日志条目一般包括三个属性:整数索引Log Index、任期号Term和指令Commond。每个条目所包含的“整数索引”即该条目在日志文件中的槽位,“任期号”对应到图中就是每个方块中的数字,用于检测在不同服务器上日志的不一致问题,指令即用于被状态机执行的外部命令,图中就是带箭头的数字。
    领导人决定什么时候将日志条目应用到状态机是安全的,即可被提交的呢?一旦领导人创建的条目已经被复制到半数以上的节点上了,那么这个条目就称为可被提交的。例如,图中的9号条目在其中4节点(一共7个节点)上具有复制,所以9号条目是可被提交的;但条目10只在其中3个节点上有复制,因此10号条目不是可被提交的。
    在这里插入图片描述
    一般情况下,Leader和Follower的日志都是保存一致的,如果Leader节点在故障之前没有向其它节点完全复制日志文件之前的所有条目,会导致日志不一致问题。在Raft算法中,Leader会强制Follower和自己的日志保存一致,因此Follower上与Leader的冲突日志会被领导者的日志强制覆写。为了实现上述逻辑,就需要知道Follower上与Leader日志不一致的位置,那么Leader是如何精准找到每个Follower日志不一致的那个槽位呢?
    Leader为每一个Follower维护了一个nextlndex,它表示领导人将要发送给该追随者的下一条日志条目的索引,当一个Leader赢得选举时,它会假设每个Follower上的日志都与自己的保持-致,于是先将 nextlndex初始化为它最新的日志条目索引数+1,在上图中,由于Leader最新的日志条目index是10 ,所以nextlndex的初始值是11。当Leader向Follower发送AppendEntries RPC时,它携带了(item_id,nextIndex - 1)二元组信息,item_id即为nextIndex - 1这个槽位的日志条目的term。Follower接收到AppendEntries RPC消息后,会进行一致性检查,即搜索自己的日志文件中是否存在这样的日志条目,如果不存在,就像Leader返回AppendEntries RPC失败,然后领导人会将nextIndex递减,然后进行重试,直到成功为止。之后的逻辑就比较简单,Follower将nextIndex之前的日志全部保留,之后的全部删除,然后将Leader的nextIndex之后的日志全部同步过来。
    上面只是讲述了方法,下面举个例子,加深一下理解,还是以上面的图为例。Leader的nextlndex为11,向b发送AppendEntries RPC(6,10),发现b没有,继续发送(6,9)(6,8) (5,7) (5,6) (4,5),最后发送(4,4)才找到,所以对于b,nextlndex=4之后的日志全部删除,然后将Leader的nextlndex=4的日志全部追加过来。

    脑裂情况

    当网络问题导致脑裂,出现双Leader情况时,每个网络可以理解为一个独立的网络,因为原先的Leader独自在一个区,所以向他提交的数据不可能被复制到大多数节点上,所以数据永远都不会提交,这个可以在第4幅图中提现出来(SET 3没有提交)
    当网络恢复之后,旧的Leader发现集群中的新Leader的Term比自己大,则自动降级为Follower,并从新Leader处同步数据达成集群数据一致,同步数据的方式可以详见“3.3.3 日志原理”
    在这里插入图片描述
    当网络恢复之后,旧的Leader发现集群中的新Leader的Term比自己大,则自动降级为Follower,并从新Leader处同步数据达成集群数据一致,同步数据的方式可以详见“3.3.3 日志原理”。
    在这里插入图片描述
    脑裂情况其实只是异常情况的一种,当Leader通知Follower更新日志、Leader提交更新时,都存在各种异常情况导致的问题,这个我就不再详述了,具体可以参考《云原生分布式存储基石-etcd深入解析》书中的“1.4.3 异常情况”这一章,里面讲述的比较清楚。

    展开全文
  • 图解分布式系统raft协议-完整版 图解分布式系统raft协议-完整版
  • 筏 我对 raft 协议的实现
  • 支持乱序执行的Raft协议.pdf
  • Raft协议详解

    千次阅读 2021-09-08 23:23:57
      raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上,因为在学术理论界,最耀眼的还是大名鼎鼎的Paxos。但Paxos是:少数真正理解的人觉得简单,尚未理解的人觉得很难,...

    正文

      raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上,因为在学术理论界,最耀眼的还是大名鼎鼎的Paxos。但Paxos是:少数真正理解的人觉得简单,尚未理解的人觉得很难,大多数人都是一知半解。本人也花了很多时间、看了很多材料也没有真正理解。直到看到raft的论文,两位研究者也提到,他们也花了很长的时间来理解Paxos,他们也觉得很难理解,于是研究出了raft算法。

       raft是一个共识算法(consensus algorithm),所谓共识,就是多个节点对某个事情达成一致的看法,即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币(比特币、区块链)就需要共识算法,而在分布式系统中,共识算法更多用于提高系统的容错性,比如分布式存储中的复制集(replication),在带着问题学习分布式系统之中心化复制集一文中介绍了中心化复制集的相关知识。raft协议就是一种leader-based的共识算法,与之相应的是leaderless的共识算法。

      本文基于论文In Search of an Understandable Consensus Algorithm对raft协议进行分析,当然,还是建议读者直接看论文。

      本文地址:https://www.cnblogs.com/xybaby/p/10124083.html

    raft算法概览

    回到顶部

      Raft算法的头号目标就是容易理解(UnderStandable),这从论文的标题就可以看出来。当然,Raft增强了可理解性,在性能、可靠性、可用性方面是不输于Paxos的。

    Raft more understandable than Paxos and also provides a better foundation for building practical systems

       为了达到易于理解的目标,raft做了很多努力,其中最主要是两件事情:

    • 问题分解
    • 状态简化

       问题分解是将"复制集中节点一致性"这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。在raft,子问题包括,leader election, log replicationsafetymembership changes。而状态简化更好理解,就是对算法做出一些限制,减少需要考虑的状态数,使得算法更加清晰,更少的不确定性(比如,保证新选举出来的leader会包含所有commited log entry)

    Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected.

       上面的引文对raft协议的工作原理进行了高度的概括:raft会先选举出leader,leader完全负责replicated log的管理。leader负责接受所有客户端更新请求,然后复制到follower节点,并在“安全”的时候执行这些请求。如果leader故障,followes会重新选举出新的leader。

       这就涉及到raft最新的两个子问题: leader election和log replication

    leader election

    回到顶部

       raft协议中,一个节点任一时刻处于以下三个状态之一:

    • leader
    • follower
    • candidate

       给出状态转移图能很直观的直到这三个状态的区别

      可以看出所有节点启动时都是follower状态;在一段时间内如果没有收到来自leader的心跳,从follower切换到candidate,发起选举;如果收到majority的造成票(含自己的一票)则切换到leader状态;如果发现其他节点比自己更新,则主动切换到follower。

       总之,系统中最多只有一个leader,如果在一段时间里发现没有leader,则大家通过选举-投票选出leader。leader会不停的给follower发心跳消息,表明自己的存活状态。如果leader故障,那么follower会转换成candidate,重新选出leader。

    term

       从上面可以看出,哪个节点做leader是大家投票选举出来的,每个leader工作一段时间,然后选出新的leader继续负责。这根民主社会的选举很像,每一届新的履职期称之为一届任期,在raft协议中,也是这样的,对应的术语叫term

       term(任期)以选举(election)开始,然后就是一段或长或短的稳定工作期(normal Operation)。从上图可以看到,任期是递增的,这就充当了逻辑时钟的作用;另外,term 3展示了一种情况,就是说没有选举出leader就结束了,然后会发起新的选举,后面会解释这种split vote的情况。

    选举过程详解

       上面已经说过,如果follower在election timeout内没有收到来自leader的心跳,(也许此时还没有选出leader,大家都在等;也许leader挂了;也许只是leader与该follower之间网络故障),则会主动发起选举。步骤如下:

    • 增加节点本地的 current term ,切换到candidate状态
    • 投自己一票
    • 并行给其他节点发送 RequestVote RPCs
    • 等待其他节点的回复

       在这个过程中,根据来自其他节点的消息,可能出现三种结果

    1. 收到majority的投票(含自己的一票),则赢得选举,成为leader
    2. 被告知别人已当选,那么自行切换到follower
    3. 一段时间内没有收到majority投票,则保持candidate状态,重新发出选举

       第一种情况,赢得了选举之后,新的leader会立刻给所有节点发消息,广而告之,避免其余节点触发新的选举。在这里,先回到投票者的视角,投票者如何决定是否给一个选举请求投票呢,有以下约束:

    • 在任一任期内,单个节点最多只能投一票
    • 候选人知道的信息不能比自己的少(这一部分,后面介绍log replication和safety的时候会详细介绍)
    • first-come-first-served 先来先得

       第二种情况,比如有三个节点A B C。A B同时发起选举,而A的选举消息先到达C,C给A投了一票,当B的消息到达C时,已经不能满足上面提到的第一个约束,即C不会给B投票,而A和B显然都不会给对方投票。A胜出之后,会给B,C发心跳消息,节点B发现节点A的term不低于自己的term,知道有已经有Leader了,于是转换成follower。

       第三种情况,没有任何节点获得majority投票,比如下图这种情况:

       总共有四个节点,Node C、Node D同时成为了candidate,进入了term 4,但Node A投了NodeD一票,NodeB投了Node C一票,这就出现了平票 split vote的情况。这个时候大家都在等啊等,直到超时后重新发起选举。如果出现平票的情况,那么就延长了系统不可用的时间(没有leader是不能处理客户端写请求的),因此raft引入了randomized election timeouts来尽量避免平票情况。同时,leader-based 共识算法中,节点的数目都是奇数个,尽量保证majority的出现。

    log replication

    回到顶部

       当有了leader,系统应该进入对外工作期了。客户端的一切请求来发送到leader,leader来调度这些并发请求的顺序,并且保证leader与followers状态的一致性。raft中的做法是,将这些请求以及执行顺序告知followersleader和followers以相同的顺序来执行这些请求,保证状态一致

    Replicated state machines

       共识算法的实现一般是基于复制状态机(Replicated state machines),何为复制状态机:

    If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.

       简单来说:相同的初识状态 + 相同的输入 = 相同的结束状态。引文中有一个很重要的词deterministic,就是说不同节点要以相同且确定性的函数来处理输入,而不要引入一下不确定的值,比如本地时间等。如何保证所有节点 get the same inputs in the same order,使用replicated log是一个很不错的注意,log具有持久化、保序的特点,是大多数分布式系统的基石。

      因此,可以这么说,在raft中,leader将客户端请求(command)封装到一个个log entry,将这些log entries复制(replicate)到所有follower节点,然后大家按相同顺序应用(apply)log entry中的command,则状态肯定是一致的。

      下图形象展示了这种log-based replicated state machine

    请求完整流程

      当系统(leader)收到一个来自客户端的写请求,到返回给客户端,整个过程从leader的视角来看会经历以下步骤:

    • leader append log entry
    • leader issue AppendEntries RPC in parallel
    • leader wait for majority response
    • leader apply entry to state machine
    • leader reply to client
    • leader notify follower apply log

      可以看到日志的提交过程有点类似两阶段提交(2PC),不过与2PC的区别在于,leader只需要大多数(majority)节点的回复即可,这样只要超过一半节点处于工作状态则系统就是可用的,而2PC需要所有节点回复OK才能提交,否则要回滚

      那么日志在每个节点上是什么样子的呢

      不难看到,logs由顺序编号的log entry组成 ,每个log entry除了包含command,还包含产生该log entry时的leader term。从上图可以看到,五个节点的日志并不完全一致,raft算法为了保证高可用,并不是强一致性,而是最终一致性(CAP理论:一致性(C)->在分布式系统中的所有数据备份,在同一时刻是否同样的值),leader会不断尝试给follower发log entries,直到所有节点的log entries都相同。

      在上面的流程中,leader只需要日志被复制到大多数节点即可向客户端返回,一旦向客户端返回成功消息,那么系统就必须保证log(其实是log所包含的command)在任何异常的情况下都不会发生回滚。这里有两个词:commit(committed),apply(applied),前者是指日志被复制到了大多数节点后日志的状态;而后者则是节点将日志应用到状态机,真正影响到节点状态。

    The leader decides when it is safe to apply a log entry to the state machines; such an entry is called committed. Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers

    safety

    回到顶部

      在上面提到只要日志被复制到majority节点,就能保证不会被回滚,即使在各种异常情况下,这根leader election提到的选举约束有关。在这一部分,主要讨论raft协议在各种各样的异常情况下如何工作的。

      衡量一个分布式算法,有许多属性,如

    • safety:nothing bad happens,
    • liveness: something good eventually happens.

      在任何系统模型下,都需要满足safety属性,即在任何情况下,系统都不能出现不可逆的错误,也不能向客户端返回错误的内容。比如,raft保证被复制到大多数节点的日志不会被回滚,那么就是safety属性。而raft最终会让所有节点状态一致,这属于liveness属性。

      raft协议会保证以下属性

    Election safety

      选举安全性,即任一任期内最多一个leader被选出。这一点非常重要,在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader,被称之为脑裂(brain split),这是非常严重的问题,会导致数据的覆盖丢失。在raft中,两点保证了这个属性:

    • 一个节点某一任期内最多只能投一票;
    • 只有获得majority投票的节点才会成为leader。

      因此,某一任期内一定只有一个leader

    在leader执行更新命令时,需要超过majority节点响应才会更新成功,这样即使出现网络分区情况产生了两个leader(不同term),那么有只有最新leader才能更新成功。

    log matching

      很有意思,log匹配特性, 就是说如果两个节点上的某个log entry的log index相同且term相同,那么在该index之前的所有log entry应该都是相同的。如何做到的?依赖于以下两点

    • If two entries in different logs have the same index and term, then they store the same command.
    • If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.

      首先,leader在某一term的任一位置只会创建一个log entry,且log entry是append-only。其次,consistency check。leader在AppendEntries中包含最新log entry之前的一个log 的term和index,如果follower在对应的term index找不到日志,那么就会告知leader不一致。

      在没有异常的情况下,log matching是很容易满足的,但如果出现了node crash,情况就会变得复杂。比如下图

      注意:上图的a-f不是6个follower,而是某个follower可能存在的六个状态

      leader、follower都可能crash,那么follower维护的日志与leader相比可能出现以下情况

    • 比leader日志少,如上图中的ab
    • 比leader日志多,如上图中的cd(有可能出现,但是多出来的log entry不可能在超过majority的节点上存在多出的log entry,如果存在那么当前leader不可能当选
    • 某些位置比leader多,某些日志比leader少,如ef(多少是针对某一任期而言,跟cd一样,多出来的log entry不可能在超过半数的节点上存在)

      当出现了leader与follower不一致的情况,leader强制follower复制自己的log

    To bring a follower’s log into consistency with its own, the leader must find the latest log entry where the two logs agree, delete any entries in the follower’s log after that point, and send the follower all of the leader’s entries after that point.

      leader会维护一个nextIndex[]数组,记录了leader可以发送每一个follower的log index,初始化为leader最后一个log index加1, 前面也提到,leader选举成功之后会立即给所有follower发送AppendEntries RPC(不包含任何log entry, 也充当心跳消息),那么流程总结为:

    s1 leader 初始化nextIndex[x]为 leader最后一个log index + 1
    s2 AppendEntries里prevLogTerm prevLogIndex来自 logs[nextIndex[x] - 1]:最后一个log entry
    s3 如果follower判断prevLogIndex位置的log term不等于prevLogTerm,那么返回 False,否则返回True
    s4 leader收到follower的回复,如果返回值是False,则nextIndex[x] -= 1, 跳转到s2. 否则
    s5 同步nextIndex[x]后的所有log entries

    leader completeness vs elcetion restriction

      leader完整性:如果一个log entry在某个任期被提交(commited apply?),那么这条日志一定会出现在所有更高term的leader的日志里面。这个跟leader election、log replication都有关。

    • 一个日志被复制到majority节点才算committed
    • 一个节点得到majority的投票才能成为leader,而节点A给节点B投票的其中一个前提是,B的日志不能比A的日志旧。下面的引文指处了如何判断日志的新旧

    voter denies its vote if its own log is more up-to-date than that of the candidate.

    If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date.

      上面两点都提到了majority:commit majority and vote majority,根据Quorum,这两个majority一定是有重合的,因此被选举出的leader一定包含了最新的committed的日志。

      raft与其他协议(Viewstamped Replication、mongodb)不同,raft始终保证leade包含最新的已提交的日志,因此leader不会从follower catchup日志,这也大大简化了系统的复杂度。

    corner case

    stale leader

      raft保证Election safety,即一个任期内最多只有一个leader,但在网络分割(network partition)的情况下,可能会出现两个leader,但两个leader所处的任期是不同的。如下图所示

      系统有5个节点ABCDE组成,在term1,Node B是leader,但Node A、B和Node C、D、E之间出现了网络分割,因此Node C、D、E无法收到来自leader(Node B)的消息,在election time之后,Node C、D、E会分期选举,由于满足majority条件,Node E成为了term 2的leader。因此,在系统中貌似出现了两个leader:term 1的Node B, term 2的Node E, Node B的term更旧,但由于无法与Majority节点通信,NodeB仍然会认为自己是leader。

      在这样的情况下,我们来考虑读写。

      首先,如果客户端将请求发送到了NodeB,NodeB无法将log entry 复制到majority节点,因此不会告诉客户端写入成功,这就不会有问题。

      对于读请求,stale leader可能返回stale data,比如在read-after-write的一致性要求下,客户端写入到了term2任期的leader Node E,但读请求发送到了Node B。如果要保证不返回stale data,leader需要check自己是否过时了,办法就是与大多数节点通信一次,这个可能会出现效率问题。另一种方式是使用lease,但这就会依赖物理时钟。

      从raft的论文中可以看到,leader转换成follower的条件是收到来自更高term的消息,如果网络分割一直持续,那么stale leader就会一直存在。而在raft的一些实现或者raft-like协议中,leader如果收不到majority节点的消息,那么可以自己step down,自行转换到follower状态。

    State Machine Safety

      前面在介绍safety的时候有一条属性没有详细介绍,那就是State Machine Safety:

    State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

      如果节点将某一位置的log entry应用到了状态机,那么其他节点在同一位置不能应用不同的日志。简单点来说,所有节点在同一位置(index in log entries)应该应用同样的日志。但是似乎有某些情况会违背这个原则:

      上图是一个较为复杂的情况。在时刻(a), s1是leader,在term2提交的日志只赋值到了s1 s2两个节点就crash了。在时刻(b), s5成为了term 3的leader,日志只赋值到了s5,然后crash。然后在(c)时刻,s1又成为了term 4的leader,开始赋值日志,于是把term2的日志复制到了s3,此刻,可以看出term2对应的日志已经被复制到了majority,因此是committed,可以被状态机应用。不幸的是,接下来(d)时刻,s1又crash了,s5重新当选(备注:节点只会投给比自己log更新的节点,这里的log包含未提交的log!!而不是已提交的log,因此在这里s5能够当选),然后将term3的日志复制到所有节点,这就出现了一种奇怪的现象:被复制到大多数节点(或者说可能已经应用)的日志被回滚。

      究其根本,是因为term4时的leader s1在(C)时刻提交了之前term2任期的日志。这种情况跟在term2提交黄色节点2是有区别的,这种情况下不含黄色节点2的节点是有可能当选的,因为不含黄色节点的节点有可能在term2-term4之间增加了更新的节点,根据选举规则(每个节点只投给比自己日志新的节点,这里的日志可以为未提交的日志)其他节点是有可能选举成功的,为了杜绝这种情况的发生:

    Raft never commits log entries from previous terms by counting replicas.
    Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.

      也就是说,某个leader选举成功之后,不会直接提交前任leader时期的日志,而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了,具体怎么实现了,在log matching部分有详细介绍。那么问题来了,如果leader被选举后没有收到客户端的请求呢,论文中有提到,在任期开始的时候发立即尝试复制、提交一条空的log

    Raft handles this by having each leader commit a blank no-op entry into the log at the start of its term.

      因此,在上图中,不会出现(C)时刻的情况,即term4任期的leader s1不会复制term2的日志到s3。而是如同(e)描述的情况,通过复制-提交 term4的日志顺便提交term2的日志。如果term4的日志提交成功,那么term2的日志也一定提交成功,此时即使s1crash,s5也不会重新当选。

    leader crash

      follower的crash处理方式相对简单,leader只要不停的给follower发消息即可。当leader crash的时候,事情就会变得复杂。在这篇文章中,作者就给出了一个更新请求的流程图。

    例子


      我们可以分析leader在任意时刻crash的情况,有助于理解raft算法的容错性。

    总结

      raft将共识问题分解成两个相对独立的问题,leader election,log replication。流程是先选举出leader,然后leader负责复制、提交log(log中包含command)

      为了在任何异常情况下系统不出错,即满足safety属性,对leader election,log replication两个子问题有诸多约束

    leader election约束:

    • 同一任期内最多只能投一票,先来先得
    • 选举人必须比自己知道的更多(比较term,log index)

    log replication约束:

    • 一个log被复制到大多数节点,就是committed,保证不会回滚
    • leader一定包含最新的committed log,因此leader只会追加日志,不会删除覆盖日志
    • 不同节点,某个位置上日志相同,那么这个位置之前的所有日志一定是相同的
    • Raft never commits log entries from previous terms by counting replicas.

      如果只是相对raft协议有一个简单了解,看这个动画演示就足够了

    references

    https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14
    https://raft.github.io/
    http://thesecretlivesofdata.com/raft/

    展开全文
  • Raft协议原理详解

    2021-02-24 05:44:52
    大名鼎鼎的Paxos算法可能不少人都听说过,几乎垄断了一致性算法领域,再Raft协议诞生之前,Paxos几乎成了一致性协议的代名词。但是对于大多数人来说,Paxos算法太难以理解了,而且难以实现。因此斯坦福大学的两位...
  • 分布式raft协议

    2018-09-06 15:32:29
    分布式raft介绍,主要描述了一致性raft协议。有兴趣的可以研究下。
  • etcd中Raft协议

    千次阅读 2022-01-24 15:57:45
    文章目录前言Raft协议Leader选举日志复制 前言 文章内容来自:《etcd技术内幕》 — 百里燊,感兴趣的读者可以去读一下。 Paxos 算法和 Raft 算法: Paxos 算法诞生于 1990 年,这是一种解决分布式系统一致性的经典...

    前言

    文章内容来自:《etcd技术内幕》 — 百里燊,感兴趣的读者可以去读一下。
    Paxos 算法和 Raft 算法
    Paxos 算法诞生于 1990 年,这是一种解决分布式系统一致性的经典算法 。但是,由于 Paxos 算法非常难以理解和实现,不断有人尝试简化这一算法。到了2013 年才诞生了一个比 Paxos 算法更易理解和实现的分布式一致性算法—Raft 算法。

    Raft协议

    在正式开始介绍 Raft 协议之间,我们有必要简单介绍一下其相关概念。在分布式系统中,一致性是比较常见的概念,所谓一致性指的是集群中的多个节点在状态上达成一致。在程序和操作系统不会崩溃、硬件不会损坏、服务器不会掉电、网络绝对可靠且没有延迟的理想情况下,我们可以将集群中的多个节点看作一个整体,此时要保证它们的一致性并不困难。

    但是在现实的场景中,很难保证上述极端的条件全部满足,节点之间的一致性也就很难保证,这样就需要 Paxos、Raft 等一致性协议。一致性协议可以保证在集群中大部分节点可用的情况下,集群依然可以工作并给出一个正确的结果,从而保证依赖于该集群的其他服务不受影响。这里的“大部分节点可用”指的是集群中超过半数以上的节点可用,例如,集群中共有 5个节点,此时其中有 2 个节点出现故障宕机,剩余的可用节点数为 3,此时,集群中大多数节点处于可用的状态,从外部来看集群依然是可用的。

    常见的一致性算法有Paxos、Raft等,Paxos协议是Leslie Lamport于1990年提出的一种基于消息传递的、具有高度容错特性的一致性算法,Paxos 算法解决的主要问题是分布式系统内如何就某个值达成一致。在相当长的一段时间内,Paxos 算法几乎成为一致性算法的代名词,但是 Paxos 有两个明显的缺点:第一个也是最明显的缺点就是 Paxos 算法难以理解,Paxos 算法的论文本身就比较晦涩难懂,要完全理解 Paxos 协议需要付出较大的努力,很多经验丰富的开发者在看完 Paxos 论文之后,无法将其有效地应用到具体工程实践中,这明显增加了工程化的门槛,也正因如此,才出现了几次用更简单的术语来解释 Paxos 的尝试。Paxos算法的第二个缺点就是它没有提供构建现实系统的良好基础,也有很多工程化 Paxos 算法的尝试,但是它们对 Paxos 算法本身做了比较大的改动,彼此之间的实现差距都比较大,实现的功能和目的都有所不同,同时与Paxos算法的描述有很多出入。例如,著名Chubby,它实现了一个类Paxos的算法,但其中很多细节并未被明确。本章并不打算详细介绍 Paxos 协议的相关内容,如果读者对Paxos感兴趣,则可以参考Lamport发表的三篇论文:《The Part-Time Parliament》、《Paxos made simple》、《Fast Paxos》。

    Raft算法是一种用于管理复制日志的一致性算法,其功能与Paxos算法相同类似,但其算法结构和Paxos算法不同,在设计Raft算法时设计者就将易于理解作为其目标之一,这使得Raft算法更易于构建实际的系统,大幅度减少了工程化的工作量,也方便开发者此基础上进行扩展。虽然Raft论文已经很好理解,但是本章并不打算直接翻译Raft论文,而是尽可能通过示例介绍Raft协议如何处理各种不同的场景,并且重点介绍Raft协议中的Leader选举和日志复制等方面的内容。

    Leader选举

    Raft 协议的工作模式是一个 Leader 节点和多个 Follower 节点的模式,也就是常说的Leader-Follower 模式。在 Raft 协议中,每个节点都维护了一个状态机,该状态机有三种状态,分别是Leader状态、Follower状态和Candidate状态,在任意时刻,集群中的任意一个节点都处于这三个状态之一。各个状态和转换条件如图2-1所示。
    在这里插入图片描述
    在多数情况下,集群中有一个Leader节点,其他节点都处于Follower状态,下面简单介绍一下每个状态的节点负责的主要工作。

    · Leader节点负责处理所有客户端的请求,当接收到客户端的写入请求时,Leader节点会在本地追加一条相应的日志,然后将其封装成消息发送到集群中其他的Follower节点。当Follower节点收到该消息时会对其进行响应。如果集群中多数(超过半数)节点都已收到该请求对应的日志记录时,则 Leader 节点认为该条日志记录已提交(committed),可以向客户端返回响应。Leader 还会处理客户端的只读请求,其中涉及一个简单的优化,后面介绍具体实现时,再进行详细介绍。Leader节点的另一项工作是定期向集群中的 Follower 节点发送心跳消息,这主要是为了防止集群中的其他Follower节点的选举计时器超时而触发新一轮选举。

    · Follower节点不会发送任何请求,它们只是简单地响应来自Leader或者Candidate 的请求;Follower节点也不处理Client的请求,而是将请求重定向给集群的Leader节点进行处理。

    · Candidate节点是由Follower节点转换而来的,当Follower节点长时间没有收到Leader节点发送的心跳消息时,则该节点的选举计时器就会过期,同时会将自身状态转换成Candidate,发起新一轮选举。选举的具体过程在下面详细描述。
    了解了Raft协议中节点的三种状态及各个状态下节点的主要行为之后,我们通过一个示例介绍Raft协议中Leader选举的大致流程。为了方便描述,我们假设当前集群中有三个节点(A、B、C),如图2-2所示。
    在这里插入图片描述
    在Raft协议中有两个时间控制Leader选举发生,其中一个是选举超时时间(election timeout),每个Follower节点在接收不到Leader节点的心跳消息之后,并不会立即发起新一轮选举,而是需要等待一段时间之后才切换成Candidate状态发起新一轮选举。这段等待时长就是这里所说的election timeout(后面介绍etcd的具体实现时会提到,Follower节点等待的时长并不完全等于该配置)。之所以这样设计,主要是 Leader 节点发送的心跳消息可能因为瞬间的网络延迟或程序瞬间的卡顿而迟到(或是丢失),因此就触发新一轮选举是没有必要的。election timeout一般设置为150ms~300ms之间的随机数。另一个超时时间是心跳超时时间(heartbeat timeout),也就是Leader节点向集群中其他Follower节点发送心跳消息的时间间隔。

    当集群初始化时,所有节点都处于 Follower 的状态,此时的集群中没有 Leader 节点。当Follower 节点一段时间(选举计时器超时)内收不到 Leader 节点的心跳消息,则认为 Leader节点出现故障导致其任期(Term)过期,Follower节点会转换成Candidate状态,发起新一轮的选举。所谓 “任期(Term)”,实际上就是一个全局的、连续递增的整数,在 Raft 协议中每进行一次选举,任期(Term)加一,在每个节点中都会记录当前的任期值(currentTerm)。每一个任期都是从一次选举开始的,在选举时,会出现一个或者多个 Candidate 节点尝试成为 Leader节点,如果其中一个Candidate节点赢得选举,则该节点就会切换为Leader状态并成为该任期的Leader节点,直到该任期结束。

    回到前面的示例中,此时节点 A 由于长时间未收到 Leader 的心跳消息,就会切换成为Candidate状态并发起选举(节点A的选举计时器(election timer)已被重置)。在选举过程中,节点A首先会将自己的选票投给自己,并会向集群中其他节点发送选举请求(Request Vote)以获取其选票,如图2-3(1)所示;此时的节点B和节点C还都是处于Term=0的任期之中,且都是Follower状态,均未投出Term=1任期中的选票,所以节点B和节点C在接收到节点A的选举请求后会将选票投给节点A,另外,节点B、C在收到节点A的选举请求的同时会将选举定时器重置,这是为了防止一个任期中同时出现多个Candidate节点,导致选举失败,如图2-3 (2)所示。注意,节点B和节点C也会递增自身记录的Term值。
    在这里插入图片描述
    在节点 A 收到节点 B、C 的投票之后,其收到了集群中超过半数的选票,所以在 Term=1这个任期中,该集群的Leader节点就是节点A,其他节点将切换成Follower状态,如图2-4所示。另外需要读者了解的是,集群中的节点除了记录当期任期号(currentTerm),还会记录在该任期中当前节点的投票结果(VoteFor)。
    在这里插入图片描述
    继续前面的示例,成为Term=1任期的Leader节点之后,节点A会定期向集群中的其他节点发送心跳消息,如图2-5(1)所示,这样就可以防止节点B和节点C中的选举计时器(election timer)超时而触发新一轮的选举;当节点B和节点C(Follower)收到节点A的心跳消息之后会重置选举计时器,如图2-5(2)所示,由此可见,心跳超时时间(heartbeat timeout)需要远远小于选举超时时间(election timeout)
    在这里插入图片描述
    到这里读者可能会问,如果有两个或两个以上节点的选举计时器同时过期,则这些节点会同时由 Follower 状态切换成 Candidate 状态,然后同时触发新一轮选举,在该轮选举中,每个Candidate节点获取的选票都不到半数,无法选举出Leader节点,那么Raft协议会如何处理呢?这种情况确实存在,假设集群中有4个节点,其中节点A和节点B的选举计时器同时到期,切换到Candidate状态并向集群中其他节点发出选举请求,如图2-6(1)所示。

    这里假设节点A发出的选举请求先抵达节点C,节点B发出的选举请求先抵达节点D,如图2-6(2)所示,节点A和节点B除了得到自身的选票之外,还分别得到了节点C和节点D投出的选票,得票数都是2,都没有超过半数。在这种情况下,Term=4这个任期会以选举失败结束,随着时间的流逝,当任意节点的选举计时器到期之后,会再次发起新一轮的选举。前面提到过election timeout是在一个时间区间内取的随机数,所以在配置合理的时候,像上述情况多次出现的概率并不大。
    在这里插入图片描述
    继续上面的示例,这里假设节点A的选举计时器再次到期(此次节点B、C、D 的选举计时器并未到期),它会切换成Candidate状态并发起新一轮选举(Term=5),如图2-7(1)所示,其中节点B虽然处于Candidate状态,但是接收到Term值比自身记录的Term值大的请求时,节点会切换成Follower状态并更新自身记录的Term值,所以该示例中的节点B也会将选票投给节点A,如图2-7(2)所示。
    在这里插入图片描述
    在获取集群中半数以上的选票并成为新任期(Term=5)的 Leader 之后,节点 A 会定期向集群中其他节点发送心跳消息;当集群中其他节点收到Leader节点的心跳消息的时候,会重置选举定时器,如图2-8所示。
    在这里插入图片描述
    介绍完集群启动时的Leader选举流程之后,下面分析Leader节点宕机之后重新选举的场景。继续上述4节点集群的示例,在系统运行一段时间后,集群当前的Leader节点(A)因为故障而宕机,此时将不再有心跳消息发送到集群的其他Follower节点(节点B、C、D),一段时间后,会有一个Follower节点的选举计时器最先超时,这里假设节点D的选举计时器最先超时,然后它将切换为Candidate状态并发起新一轮选举,如图2-9(1)所示。
    在这里插入图片描述
    当节点B和节点C收到节点D的选举请求后,会将其选票投给节点D,由于节点A已经宕机,没有参加此次选举,也就无法进行投票,但是在此轮选举中,节点D依然获得了半数以上的选票,故成为新任期(Term=6)的Leader节点,并开始向其他Follower节点发送心跳消息,如图2-10所示。
    在这里插入图片描述
    当节点A恢复之后,会收到节点D发来的心跳消息,该消息中携带的任期号(Term=6)大于节点A当前记录的任期号(Term=5),所以节点A会切换成Follower状态。在Raft协议中,当某个节点接收到的消息所携带的任期号大于当前节点本身记录的任期号,那么该节点会更新自身记录的任期号,同时会切换为Follower状态并重置选举计时器,这是Raft算法中所有节点最后请读者考虑一个场景:如果集群中选出的Leader节点频繁崩溃或是其他原因导致选举频繁发生,这会使整个集群中没有一个稳定的Leader节点,这样客户端无法与集群中的Leader节点正常交互,也就会导致整个集群无法正常工作。

    Leader选举是Raft算法中对时间要求较为严格的一个点,一般要求整个集群中的时间满足如下不等式:
    广播时间 << 选举超时时间 << 平均故障间隔时间

    在上述不等式中,广播时间指的是从一个节点发送心跳消息到集群中的其他节点并接收响应的平均时间;平均故障间隔时间就是对于一个节点而言,两次故障之间的平均时间。为了保证整个Raft集群可用,广播时间必须比选举超时时间小一个数量级,这样Leader节点才能够发送稳定的心跳消息来重置其他 Follower 节点的选举计时器,从而防止它们切换成 Candidate 状态,触发新一轮选举。在前面的描述中也提到过,选举超时时间是一个随机数,通过这种随机的方式,会使得多个Candidate节点瓜分选票的情况明显减少,也就减少了选举耗时。另外,选举超时时间应该比平均故障间隔时间小几个数量级,这样Leader节点才能稳定存在,整个集群才能稳定运行。当Leader节点崩溃之后,整个集群会有大约相当于选举超时的时间不可用,这种情况占比整个集群稳定运行的时间还是非常小的。

    广播时间和平均故障间隔时间是由网络和服务器本身决定的,但是选举超时时间是可以由我们自己调节的。一般情况下,广播时间可以做到0.5ms~50ms,选举超时时间设置为200ms~1s之间,而大多数服务器的平均故障间隔时间都在几个月甚至更长,很容易满足上述不等式的时间需求。

    日志复制

    通过上一节介绍的Leader选举过程,集群中最终会选举出一个Leader节点,而集群中剩余的其他节点将会成为Follower节点。Leader节点除了向Follower节点发送心跳消息,还会处理客户端的请求,并将客户端的更新操作以消息(Append Entries消息)的形式发送到集群中所有的Follower节点。当Follower节点记录收到的这些消息之后,会向Leader节点返回相应的响应消息。当Leader节点在收到半数以上的Follower节点的响应消息之后,会对客户端的请求进行应答。最后,Leader会提交客户端的更新操作,该过程会发送Append Entries消息到Follower节点,通知Follower节点该操作已经提交,同时Leader节点和Follower节点也就可以将该操作应用到自己的状态机中。

    上面这段描述仅仅是Raft协议中日志复制部分的大致流程,下面我们依然通过一个示例描述该过程,为了方便描述,我们依然假设当前集群中有三个节点(A、B、C),其中A是Leader节点,B、C是Follower 节点,此时有一个客户端发送了一个更新操作到集群,如图 2-11(1)所示。前面提到过,集群中只有Leader节点才能处理客户端的更新操作,这里假设客户端直接将请求发给了节点A。当收到客户端的请求时,节点A会将该更新操作记录到本地的Log中,如图2-11(2)所示。
    在这里插入图片描述
    之后,节点A会向其他节点发送Append Entries消息,其中记录了Leader节点最近接收到的请求日志,如图2-12(1)所示。集群中其他Follower节点收到该Append Entries消息之后,会将该操作记录到本地的Log中,并返回相应的响应消息,如图2-12(2)所示。
    在这里插入图片描述
    当Leader节点收到半数以上的响应消息之后,会认为集群中有半数以上的节点已经记录了该更新操作,Leader 节点会将该更新操作对应的日志记录设置为已提交(committed),并应用到自身的状态机中。同时 Leader 节点还会对客户端的请求做出响应,如图 2-13(1)所示。同时,Leader节点也会向集群中的其他Follower节点发送消息,通知它们该更新操作已经被提交,Follower节点收到该消息之后,才会将该更新操作应用到自己的状态机中,如图2-13(2)所示。
    在这里插入图片描述
    在上述示例的描述中我们可以看到,集群中各个节点都会维护一个本地Log用于记录更新操作,除此之外,每个节点还会维护commitIndex和lastApplied两个值,它们是本地Log的索引值,其中commitIndex表示的是当前节点已知的、最大的、已提交的日志索引值,lastApplied表示的是当前节点最后一条被应用到状态机中的日志索引值。当节点中的 commitIndex 值大于lastApplied值时,会将lastApplied 加1,并将lastApplied对应的日志应用到其状态机中。

    在Leader节点中不仅需要知道自己的上述信息,还需要了解集群中其他Follower节点的这些信息,例如,Leader节点需要了解每个Follower节点的日志复制到哪个位置,从而决定下次发送 Append Entries 消息中包含哪些日志记录。为此,Leader 节点会维护 nextIndex[]和matchIndex[]两个数组,这两个数组中记录的都是日志索引值,其中nextIndex[]数组记录了需要发送给每个 Follower 节点的下一条日志的索引值,matchIndex[]表示记录了已经复制给每个Follower节点的最大的日志索引值。

    这里简单看一下 Leader 节点与某一个 Follower 节点复制日志时,对应 nextIndex 和matchIndex值的变化:Follower节点中最后一条日志的索引值大于等于该Follower节点对应的nextIndex 值,那么通过 Append Entries 消息发送从 nextIndex 开始的所有日志。之后,Leader节点会检测该 Follower 节点返回的相应响应,如果成功则更新相应该 Follower 节点对应的nextIndex值和matchIndex值;如果因为日志不一致而失败,则减少nextIndex值重试。

    下面我们依然通过一个示例来说明nextIndex[]和matchIndex[]在日志复制过程中的作用,假设集群现在有三个节点,其中节点A是Leader节点(Term=1),而Follower节点C因为宕机导致有一段时间未与Leader节点同步日志。此时,节点C的Log中并不包含全部的已提交日志,而只是节点A的Log的子集,节点C故障排除后重新启动,当前集群的状态如图2-14所示(这里只关心Log、nextIndex[]、matchIndex[],其他的细节省略,另外需要注意的是,图中的Term=1表示的是日志发送时的任期号,而非当前的任期号)。
    在这里插入图片描述
    A作为Leader节点,记录了nextIndex[]和matchIndex[],所以知道应该向节点C发送哪些日志,在本例中,Leader节点在下次发送Append Entries消息时会携带Index=2的消息(这里为了描述简单,每条消息只携带单条日志,Raft协议采用批量发送的方式,这样效率更高),如图2-15(1)所示。当节点C收到Append Entries消息后,会将日志记录到本地Log中,然后向Leader 节点返回追加日志成功的响应,当 Leader 节点收到响应之后,会递增节点 C 对应的nextIndex和matchIndex,这样Leader节点就知道下次发送日志的位置了,该过程如图2-15(2)所示。

    在上例中,当Leader节点并未发生过切换,所以Leader节点始终准确地知道节点C对应nextIndex值和matchIndex值。

    如果在上述示例中,在节点C故障恢复后,节点A宕机后重启,并且导致节点B成为新任期(Term=2)的 Leader 节点,则此时节点 B 并不知道旧 Leader 节点中记录的 nextIndex[]和matchIndex[]信息,所以新Leader节点会重置nextIndex[]和matchIndex[],其中会将nextIndex[]全部重置为其自身Log的最后一条已提交日志的Index值,而matchIndex[]全部重置为0,如图2-16所示。
    在这里插入图片描述
    在这里插入图片描述
    随后,新任期中的Leader节点会向其他节点发送Append Entries消息,如图2-17(1)所示,节点A已经拥有了当前Leader的全部日志记录,所以会返回追加成功的响应并等待后续的日志,而节点C并没有Index=2和Index=3两条日志,所以返回追加日志失败的响应,在收到该响应后,Leader节点会将nextIndex前移,如图2-17(2)所示。
    在这里插入图片描述
    然后新 Leader 节点会再次尝试发送 Append Entries 消息,循环往复,不断减小 nextIndex值,直至节点C返回追加成功的响应,之后就进入了正常追加消息记录的流程,不再赘述。

    了解了 Log 日志及节点中基本的数据结构之后,请读者回顾前面描述的选举过程,其中Follower节点的投票过程并不像前面描述的那样简单(先收到哪个Candidate节点的选举请求,就将选票投给哪个Candidate节点),Follower节点还需要比较该Candidate节点的日志记录与自身的日志记录,拒绝那些日志没有自己新的Candidate节点发来的投票请求,确保将选票投给包含了全部已提交(committed)日志记录的 Candidate 节点。这也就保证了已提交的日志记录不会丢失:Candidate节点为了成为Leader节点,必然会在选举过程中向集群中半数以上的节点发送选举请求,因为已提交的日志记录必须存在集群中半数以上的节点中,这也就意味着每一条已提交的日志记录肯定在这些接收到节点中的至少存在一份。也就是说,记录全部已提交日志的节点和接收到Candidate节点的选举请求的节点必然存在交集,如图2-18所示。
    在这里插入图片描述
    如果Candidate节点上的日志记录与集群中大多数节点上的日志记录一样新,那么其日志一定包含所有已经提交的日志记录,也就可以获得这些节点的投票并成为Leader。

    在比较两个节点的日志新旧时,Raft 协议通过比较两节点日志中的最后一条日志记录的索引值和任期号,以决定谁的日志比较新:首先会比较最后一条日志记录的任期号,如果最后的日志记录的任期号不同,那么任期号大的日志记录比较新;如果最后一条日志记录的任期号相同,那么日志索引较大的 比较新。

    这里只是大概介绍一下 Raft 协议的流程和节点使用的各种数据结构,读者需要了解的是Raft 协议的工作原理,如果对上述数据结构描述感到困惑,在后面介绍etcd-raft 模块时,还会再次涉及这些数据结构,到时候读者可以结合代码及这里的描述进一步进行分析。

    网络分区的场景

    接下来,我们来看一下Raft协议是如何处理网络分区情况的。在一个集群中,如果有部分节点的网络发生故障,与集群中另一部分节点的连接中断,就会出现网络分区,如图2-19所示,集群有A、B、C、D、E五个节点,其中节点A、B相互之间网络连通,节点C、D、E相互之间网络连通,但是这两部分节点之间出现网络故障,这就形成了网络分区。
    在这里插入图片描述
    这里依然通过一个示例来说明 Raft 协议对网络分区场景的处理。假设集群中节点 A 是Leader节点,它会向其他四个节点发送Append Entries消息和心跳消息,如图2-20(1)所示。当出现网络出现分区时,节点A的心跳消息只有节点B才能收到,而集群中的其他节点收不到,如图2-20(2)所示(图中节点A发往节点C、D、E的消息由于网络分区,并不会抵达节点C、D、E,故未在图中画出)。
    在这里插入图片描述
    随着时间的流逝,集群中与Leader节点隔离的网络分区(C、D、E)中,会率先有一个节点的选举计时器(election timer)超时,这里假设该节点是E,此时的节点E就会切换成Candidate状态并发起下一轮选举,如图2-21(1)所示。由于网络分区,当前集群中只有节点C、D能够收到节点E的选举请求,这里假设节点C、D都会将选票投给节点E,如图2-21(2)所示。
    在这里插入图片描述
    到此为止,节点 E 在此次选举中收到了得到三票(其中包括它本身的一票),达到集群半数以上,所以节点E成为新任期(Term=2)的Leader节点,如图2-22所示:
    在这里插入图片描述
    当网络故障被修复时,上述的网络分区也就会消失,此时节点 A(任期 Term=1 的 Leader节点)发送的心跳消息会被节点C、D、E接收到(图2-22中虽然省略了这些由于网络分区而无法送达的心跳消息,但实际上节点A依然认为自己是Leader节点,在发送心跳消息时也会向节点C、D、E发送心跳消息),但是这些心跳消息中携带的Term值小于当前C、D、E节点的Term值,会被C、D、E节点忽略;同时,节点E(Term=2任期的Leader节点)发送的心跳消息会被节点 A、B 接收到(图2-22 中同样省略了这些无法送达的心跳消息),不同的是,这些心跳消息携带的Term值大于当前A、B节点的Term值,所以节点A、B会切换成Follower状态,这样整个集群中的Leader节点依然是节点E。

    读者可能会问:如果网络分区时,Leader节点划分到节点较多的分区中,如图2-23所示,此时节点较少的分区中,会有节点的选举计时器超时,切换成Candidate状态并发起新一轮的选举。但是由于该分区中节点数不足半数,所以无法选举出新的 Leader 节点。待一段时间之后,该分区中又会出现某个节点的选举计时器超时,会再次发起新一轮的选举,循环往复,从而导致不断发起选举,Term号不断增长。

    在Raft协议中对这种情况有一个优化,当某个节点要发起选举之前,需要先进入一个叫作PreVote的状态,在该状态下,节点会先尝试连接集群中的其他节点,如果能够成功连接到半数以上的节点,才能真正发起新一轮的选举。通过这种方式就可以解决上述的问题,在后面分析etcd-raft模块时,还会详细介绍其具体实现。
    在这里插入图片描述
    回到前面的示例简单来介绍网络分区恢复时的相关处理。当网络分区恢复时,集群中存在新旧两个Leader节点(A和E),其中节点E的Term值较高,会成为整个集群中的Leader节点。但是由于之前的网络分区,节点A、B的本地Log中可能存在未提交的日志记录,如图2-24(1)所示,此时节点A和B会回滚未提交的日志记录,并重新复制新Leader节点的日志,如图2-24 (2)所示。
    在这里插入图片描述
    这样在网络分区恢复之后,整个集群的日志又会恢复一致。到此为止,网络分区场景下的Leader选举及日志复制过程就介绍完了,希望通过对这种特殊场景的介绍,读者能够更深刻地了解Raft协议的工作原理。

    另一个需要介绍的问题是,网络分区场景下,客户端与集群的交互过程及日志复制的过程。这里我们先简单介绍一下客户端如何与集群进行交互并找到集群的Leader节点。在前面提到过,集群中只有Leader节点可以处理客户端发来的请求,当Follower节点收到客户端的请求时,也必须将Leader节点信息告知客户端,然后由Leader节点处理其请求,具体步骤如下:

    (1)当客户端初次连接到集群时,会随机挑选一个服务器节点进行通信。

    (2)如果客户端第一次挑选的节点不是 Leader 节点,那么该节点会拒绝客户端的请求,并且将它所知道的Leader节点的信息返回给客户端。

    (3)当客户端连接到Leader节点之后,即可发送消息进行交互。

    (4)如果在交互过程中 Leader 节点宕机,那么客户端的请求会超时,客户端会再次随机挑选集群中的节点,并从步骤1重新开始执行。

    这里依然通过一个示例来介绍整个过程,假设集群依然有五个节点,在未发生网络分区时,节点A为集群的Leader节点,此时的客户端请求会发送到节点A,经过前面描述的日志复制过程后,节点A也会向客户端返回响应,与如图2-25(1)和(2)所示。
    在这里插入图片描述
    当节点A、B与节点C、D、E之间发生网络分区之后,客户端发往节点 A的请求将会超时,这主要是因为节点A无法将请求发送到集群中超过半数的节点上,该请求相应的日志记录也就无法提交,从而导致无法给客户端返回相应的响应,该过程如图2-26(1)和(2)所示。

    在这里插入图片描述
    前面已经介绍了网络分区之后的Leader选举过程,这里不再赘述,该示例中假设节点E被选举为新任期(Term=2)的Leader节点。当请求超时之后,客户端会重新随机选择一个节点,并获取新Leader节点的信息,客户端最终会连接到节点E并发送请求,而该网络分区中有超过半数的节点,请求对应的日志记录可以提交,所以客户端的请求不会再次出现超时,之后客户端会一直与节点E进行交互直至下次请求超时。上述过程的如图2-27(1)~(4)所示。
    在这里插入图片描述
    在这里插入图片描述
    在 Raft 协议的论文中,还给出了另一种 proxy 的方案:假设客户端连接到集群中的某个Follower 节点,该 Follower 节点会将客户端发送的所有请求转发给 Leader 节点进行处理,当Leader节点响应Follower节点之后,再由Follower节点响应客户端。当出现请求超时的情况时,客户端同样需要随机选择新的节点进行连接。

    日志压缩与快照

    通过前面章节的描述可知,随着客户端与集群不断地交互,每个节点上的日志记录会不断增加,但是服务器的空间都是有限的,日志量不能无限制地增长。另外,在节点重启时会重放日志记录,如果日志记录过多,则需要花费较长的时间完成重放操作。这就需要压缩和清除机制来减少日志量,从而避免上述情况。

    定期生成快照是最常见也是最简单的压缩方法。在创建快照文件时,会将整个节点的状态进行序列化,然后写入稳定的持久化存储中,这样,在该快照文件之前的日志记录就可以全部丢弃了。例如,集群中变量a的值为100,客户端发送了一个更新请求将变量a更新为13,经过前面描述的日志复制过程之后,该请求对应的日志记录最终被提交并应用到集群中的每个节点中。此时每个节点中维护的变量 a 都是 13,而 a=13 这条日志记录就无须继续保留。在ZooKeeper、Chubby和etcd中都有类似上述的快照处理逻辑,这里只是介绍创建快照文件和压缩日志的基本逻辑,在后面的章节会具体介绍其实现。

    在快照中除了节点当前的数据状态,还包含了其最后一条日志记录的任期号和索引号,如图2-28所示,该快照包含了6条日志记录,在快照的元数据中记录了第6条日志记录的任期号和索引号,在生成快照文件之后,即可将1~6条日志记录丢弃了。
    在这里插入图片描述
    一般情况下,集群中的每个节点都会自己独立、定时地创建快照,在其状态恢复时,都会使用自己本地最新的快照数据。如果Follower节点长时间宕机(或是刚刚加入集群的新节点),就有可能导致其日志记录远远落后于当前的Leader节点,与此同时,Leader节点中陈旧的日志记录已被删除了。在这种场景下,为了将该Follower节点恢复到正确的状态,Leader节点会将快照发送给该Follower节点,Follower节点会使用该快照数据进行状态恢复。当Leader节点需要向Follower节点发送快照时,会发送一种特殊的消息类型(快照消息)。etcd的网络层为了高效地传输消息,会将快照的发送与普通消息(Append Entries消息、心跳消息等)的发送分开在不同的消息通道中完成,在后面介绍etcd网络层时会详细介绍。

    当Follower节点接收到该快照消息时,必须决定如何处理已存在的日志记录,在快照中之所以保留前面介绍的一些元数据,其作用之一就是为了在Follower节点收到快照之后进行一致性检查。一般情况下,快照已包含了该Follower节点中不存在的日志记录,此时Follower节点直接丢弃其所有的日志记录,因为这些日志最终会被Leader传递来的快照所代替。如果Follower节点接收到的快照只包含了自己本地日志的一部分,那么被该快照所包含的全部日志记录会被全部删除,但是快照之后的日志则会保留。

    有的读者可能会考虑过另一种替代方案,即只有Leader节点创建快照,然后发送给所有的Follower 节点。但是该方案有几个缺点:首先就是快照数据会比较大,并且发送快照数据是比较浪费网络带宽的,也比较耗时,这显然比Follower节点从本地直接加载要耗时很多;其次就是Leader的实现会更加复杂。

    在Raft协议中,每个节点都会创建快照,所以创建快照的时机决定了快照的性能。如果创建快照过于频繁,那么就会消耗大量的资源,导致每个节点的性能下降;如果创建快照的频率过低,那么两次创建快照之间积累的日志记录会比较多,快照就无法为节点节约内存等资源。所以我们要在两者之间进行权衡,常见的策略是当日志记录个数达到一个固定阈值的时候,就触发一次创建快照的操作,生成相应的快照文件,我们可以通过调节该阈值来控制创建快照的频率。

    其他技术点

    linearizable语义

    Raft协议的目标是实现linearizable语义,即在客户端每次向集群发送一次读请求时,该请求只会被执行一次。但是根据前面的描述,客户端虽然只是想发送一次请求,但是集群可能多次收到该请求。例如,Leader节点负责提交日志记录(通知了其他Follower节点)并将日志记录应用到了其状态机中,但是在向客户端返回相应的响应消息之前宕机了,那么客户端会连接到新的Leader节点并重发对应的请求,这就导致该请求再次被执行。或者,网络出现故障,导致请求丢失或是延迟,如图2-29所示,就会导致同一条请求被执行两次。
    在这里插入图片描述
    常见的解决方案就是客户端对于每个请求都产生一个唯一的序列号,然后由服务端为每个客户端维护一个Session,并对每个请求进行去重。当服务端接收到一个请求时,会检测其序列号,如果该请求已经被执行过了,那么就立即返回结果,而不会重新执行。

    只读请求

    在介绍 Raft 协议的日志复制时提到,请求对应的日志记录会写入 Leader 节点的本地 Log中并完成复制到集群中半数以上的节点,之后才会真正提交并应用到状态机中。为了提高只读请求的性能,我们可以考虑直接处理而不记录对应的日志记录(也不会经过日志复制的过程)。但是,在不增加任何限制的情况下,这么做可能会冒着返回脏数据的风险,因为Leader节点响应客户端请求时可能已经故障(或是已经发生了网络分区),集群已经选出了新的Leader节点,但是旧的Leader节点自身还不知道。

    为了不返回脏数据,同时为了保证linearizability语义,Raft协议在处理只读请求时,除了直接读取Leader节点对应的状态信息,还需要使用额外的措施。处理只读请求的大致逻辑如下:
    (1)Leader节点必须有关于已提交日志的最新信息,虽然在节点刚刚赢得选举成为Leader时,拥有所有已经被提交的日志记录,但是在其任期刚开始时,它可能不知道哪些是已经被提交的日志。为了明确这些信息,它会在其任期开始时提交一条空日志记录,这样上一个任期中的所有日志都会被提交。

    (2)Leader节点会记录该只读请求对应的编号作为readIndex,当Leader节点的提交位置(commitIndex)达到或是超过该位置之后,即可响应该只读请求。

    (3)Leader节点在处理只读的请求之前必须检查集群中是否有新的Leader节点,自己是否已经被作废,如果该节点已经不再是集群的Leader节点,则该节点中日志记录就可能包含脏数据,必须由新Leader节点来处理此次只读请求。Raft协议中,通过让Leader节点在处理只读请求之前,先和集群中的半数以上的节点交换一次心跳消息来解决这个问题。如果该Leader节点可以与集群中半数以上的节点交换一次心跳,则表示该Leader 节点依然为该集群最新的Leader节点。这样,readIndex值也就是整个集群中所有节点所能看到的最大提交位置(commitIndex)。

    (4)随着日志记录的不断提交,Leader 节点的提交位置(commitIndex)最终会超过上述readIndex,此时Leader就可以响应客户端的只读请求了。

    这里简单介绍一下linearizability的含义,线性化(linearizability)是分布式系统中比较重要的概念。linearizability 是对单对象上的单个操作的一种顺序保证,它提供了对于同一个对象的一系列读写操作都是按照实时时间排序的保证。简单地说,linearizability 保证对于一个对象的写操作一旦完成,需要立即被后续的读操作看到,即读操作一定是读到该对象的最新的值。从该角度来看,linearizability与atomic consistency是同义词,也是CAP原则中的C(consistency)。另外,并且linearizability是可组合的,如果系统中每个对象的操作都是linearizable,则系统中所有操作是linearizable。

    PreVote状态

    在前面介绍网络分区场景时提到,在节点数不足集群半数的网络分区中,始终没有节点可以获取半数以上的选票成为Leader节点,所以每过一段时间,就有节点的选举计时器超时并切换成Candidate状态,发起新一轮的选举。

    这虽然不影响集群的使用(在节点超过半数的网络分区中,已经成功选举出Leader节点并对外提供服务),但是会导致不断发起选举的节点的Term号不断增长。当网络分区结束时,由于该节点的Term值高于集群当前的Leader节点的Term值,就会迫使当前Leader节点发生状态切换,并重新发起一次新的选举。

    Raft 协议为了优化此次无意义的选举,给节点添加了一个 PreVote 的状态:当某个节点要发起选举之前,需要先进入PreVote的状态。在PreVote状态下的节点会先尝试连接集群中的其他节点,如果能够成功连接到半数以上的节点,才能真正切换成Candidate状态并发起新一轮的选举。在后面分析etcd-raft模块时,我们可以看到相关实现。

    Leader节点转移

    通过前面的介绍我们知道,Leader节点在整个集群中的作用至关重要。但是在有的场景中需要对Leader节点进行手动切换。例如,我们要将Leader节点所在的机器进行系统升级或是停机维护等。此时,我们可能需要集群中指定的Follower节点成为新的Leader节点,继续对外提供服务。在原Leader节点所在的机器维护结束之后,我们可能还需要将Leader节点再转移到该机器上(可能该机器的配置等条件优于集群中的其他机器,更适合做 Leader 节点)。这种场景下就需要特定的Follower节点成为下一任期的Leader节点。根据前面介绍的Leader选举过程我们知道,Leader节点的选举在本质上是随机的,无法满足上述需求。

    Raft协议给出的方案是:首先暂停接收客户端请求,让一个指定的Follower节点的本地日志与当前的Leader节点完全同步,在完成同步之后,该特定的Follower节点立刻发起新一轮的选举。由于其Term值较大,原Leader节点自然被其替换下来。该方案需要控制好选举计时器及特定Follower与Leader节点同步的时间,防止其他Follower节点在这段时间内发起选举,当然,发生这种情况的概率还是比较低的。

    展开全文
  • Raft协议分析

    2022-07-10 21:26:23
    分布式系统作为一致性协议较为常用的有两种:raft协议和paxos 协议。两种协议实现的复杂度不同,paxos相对于raft的复杂难度要高出好几个级别,而目前只有zookeeper实现了paxos的简化版本;而使用raft协议的中间件则...
  •   raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上,因为在学术理论界,最耀眼的还是大名鼎鼎的Paxos。但Paxos是:少数真正理解的人觉得简单,尚未理解的人觉得很难,...
  • 本文先对raft协议进行通俗的讲解,然后基于MongoDB 4.4.2 源码版本分析了MongoDB副本集协议的主要实现流程,最后指出raft核心算法在MongoDB副本集协议源码中的体现。 raft协议 提出问题 在我们的生活中,很多...
  • Raft协议-流程演示

    千次阅读 2022-04-17 10:28:34
    Raft协议是比paxos协议更容易理解和实现的一种一致性协议。http://thesecretlivesofdata.com/raft/ 这个网址动态演示了Raft协议的整个过程。跟着记录一下: 1:Raft是一个可被理解接受的分布式一致性协议。 2:...
  • raft协议

    2021-03-22 19:45:47
    http://thesecretlivesofdata.com/raft/ 以上是关于raft协议介绍的一个动画,很便于理解。
  • Raft 协议原理详解

    千次阅读 2020-10-03 18:48:27
    raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上,因为在学术理论界,最耀眼的还是大名鼎鼎的Paxos。但Paxos是:少数真正理解的人觉得简单,尚未理解的人觉得很难,...
  • Raft 协议

    2021-04-02 18:01:00
    1.1 raft协议是什么? 分布式系统之于单机系统,优势之一就是有更好的容错性,分布式系统会对数据做备份(backup)。 一个系统的工作模式:接受客户端的command,系统进行处理,将处理的结果返回给客户端。由此可见...
  • etcd是raft协议的一个实现。如果你使用过zookeeper这样的分布式键值对,你应该知道有个叫paxos的协议,paxos协议是挺复杂的,raft协议是paxos协议的简化版本。大多数同意原则:一群人怎么达成原则,往往是通过投票,...
  • 很有意思的 Raft 原理,带你动画还原,欢迎来戳 ~~ ...大名鼎鼎的 Paxos 算法可能不少人都听说过,几乎垄断了一致性算法领域,在 Raft 协议诞生之前,Paxos 几乎成了一致性协议的代名词。但是对于大多数人来说,Pa...
  • 1.什么是raft协议 在分布式系统中,为了消除单点提高系统可用性,通常会使用副本来进行容错,但这会带来另一个问题,即如何保证多个副本之间的一致性? 所谓的强一致性(线性一致性)并不是指集群中所有节点在任一...
  • ZAB 协议 与 Raft协议 比较

    千次阅读 2020-10-24 22:34:37
    Raft协议是 ZAB 是通过“一切以领导者为准”的强领导者模型和严格按照顺序处理、提交提案,来实现操作的顺序性的。主节点是基于 TCP 协议来广播消息的,并保证了消息接收的顺序性。 Raft 算法(主备、强领导者模型...
  • 阿帕奇·拉蒂斯(Apache Ratis) Apache Ratis是一个实现RAFT协议[1]的Java库。 可以在( )上访问Raft论文。 本文介绍了Raft,并用以下几句话陈述了它的动机: Raft是用于管理复制日志的共识算法。 它产生的结果...
  • 多图讲解Raft协议基础 Raft 是分布式领域中解决一致性的协议,主要包含领导者选举、日志复制两个部分。
  • 大名鼎鼎的Paxos算法可能不少人都听说过,几乎垄断了一致性算法领域,在Raft协议诞生之前,Paxos几乎成了一致性协议的代名词。但是对于大多数人来说,Paxos算法太难以理解了,而且难以实现。因此斯坦福大学的两位...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,376
精华内容 6,950
关键字:

raft协议

友情链接: delphixe.rar