分布式协议与算法实战
韩健
腾讯资深工程师
立即订阅
4631 人已学习
课程目录
已更新 19 讲 / 共 22 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 想成为分布式高手?那就先把协议和算法烂熟于心吧
免费
理论篇 (4讲)
01 | 拜占庭将军问题:有叛徒的情况下,如何才能达成共识?
02 | CAP理论:分布式系统的PH试纸,用它来测酸碱度
03 | ACID理论:CAP的酸,追求一致性
04 | BASE理论:CAP的碱,追求可用性
协议和算法篇 (11讲)
05 | Paxos算法(一):如何在多个节点间确定某变量的值?
06 | Paxos算法(二):Multi-Paxos不是一个算法,而是统称
07 | Raft算法(一):如何选举领导者?
08 | Raft算法(二):如何复制日志?
09 | Raft算法(三):如何解决成员变更的问题?
10 | 一致哈希算法:如何分群,突破集群的“领导者”限制?
11 | Gossip协议:流言蜚语,原来也可以实现一致性
12 | Quorum NWR算法:想要灵活地自定义一致性,没问题!
13 | PBFT算法:有人作恶,如何达成共识?
14 | PoW算法:有办法黑比特币吗?
15 | ZAB协议:如何实现操作的顺序性?
实战篇 (3讲)
16 | InfluxDB企业版一致性实现剖析:他山之石,可以攻玉
17 | Hashicorp Raft(一):如何跨过理论和代码之间的鸿沟?
18 | Hashicorp Raft(二):如何以“集群节点”为中心使用API?
分布式协议与算法实战
登录|注册

07 | Raft算法(一):如何选举领导者?

韩健 2020-02-26
你好,我是韩健。
通过前两节课,我带你打卡了 Paxos 算法,今天我想和你聊聊最常用的共识算法,Raft 算法。
Raft 算法属于 Multi-Paxos 算法,它是在兰伯特 Multi-Paxos 思想的基础上,做了一些简化和限制,比如增加了日志必须是连续的,只支持领导者、跟随者和候选人三种状态,在理解和算法实现上都相对容易许多。
除此之外,Raft 算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统(比如 Cubby、Spanner)都是在 Raft 算法发布前开发的,当时没得选;而全新的系统大多选择了 Raft 算法(比如 Etcd、Consul、CockroachDB)。
对你来说,掌握这个算法,可以得心应手地处理绝大部分场景的容错和一致性需求,比如分布式配置系统、分布式 NoSQL 存储等等,轻松突破系统的单机限制。
如果要用一句话概括 Raft 算法,我觉得是这样的:从本质上说,Raft 算法是通过一切以领导者为准的方式,实现一系列值的共识和各节点日志的一致。这句话比较抽象,我来做个比喻,领导者就是 Raft 算法中的霸道总裁,通过霸道的“一切以我为准”的方式,决定了日志中命令的值,也实现了各节点日志的一致。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《分布式协议与算法实战》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(28)

  • Jialin
    Raft 算法本质:通过一切以领导者为准的方式,实现一系列值的共识和各节点日志的一致
    服务节点状态:
    • 领导者(Leader):处理写请求、管理日志复制、与跟随者间维持心跳服务
    • 跟随者(Follower):接受和处理来自领导者的消息,当领导者节点故障时,推荐自己进行选举
    • 候选人(Candidate):向其他跟随者节点发送请求投票 RPC 消息,通知投票,若获得大多数节点的投票,则成功竞选为领导者。
    服务节点状态变更:
    • 跟随者 -> 候选人 -> 领导者
    • 领导者 -> 跟随者
    • 候选人 -> 跟随者
    Raft 算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等,保证了一个任期只有一位领导,也极大地减少了选举失败的情况。具体的选举细节如下:
    • 节点间通讯方式:RPC 通讯,分为请求投票 RPC 和日志复制 RPC。投票 RPC 由候选人发起,通知其他阶段进行投票选举; 日志复制 RPC 由领导者发起,用于日志复制和维持心跳服务。
    • 领导者任期:与现实生活中领导者任期不同的是,这里的任期是指任期编号,而非任期时间。跟随者在等待领导者心跳信息超时后,推举自己为候选人时,会增加自己的任期号;如果一个服务器节点,发现自己的任期编号比其他节点小,那么它会更新自己的编号到较大的编号值。
    • 在 Raft 算法中约定,如果一个候选人或者领导者,发现自己的任期编号比其他节点小,那么它会立即恢复成跟随者状态
    • 如果一个节点接收到一个包含较小的任期编号值的请求,那么它会直接拒绝这个请求
    • 选举规则:
    • 领导者周期性地向所有跟随者发送心跳信息,维持自己的领导者状态
    • 跟随者在随机超时时间内没有收到领导者的心跳信息,则发起领导者选举,节点状态变更为候选人,进入选举阶段
    • 选举阶段,候选人收到超过半数以上的投票,节点状态变更为领导者,选举结束
    • 选举阶段,一个服务节点最多会对一个任期编号投出一张选票,按照“先来先服务”原则进行投票;若任期编号同,则按照“日志完整性”原则进行投票。(日志完整性是服务节点的最后一条日志项对应的任期编号值和索引号。一般情况下,任期编号值更大,索引号更大)。
    • 随机超时时间:
    • 跟随者等待领导者心跳信息超时的时间间隔,是随机的
    • 当没有候选人赢得过半票数,选举无效了,这时需要等待一个随机时间间隔,也就是说,等待选举超时的时间间隔,是随机的
    2020-02-28
    7
  • 欧阳
    请问任期一般多长呢?还是只要不故障,任期一直不变?任期索引是用32位整数表示么?如果达到最大int,怎么处理呢?
    2020-03-10
    1
    2
  • Geek_niu
    候选者在向别的节点发布请求投票的RPC时,他是通过广播洪泛,还是gossip那样的方式
    2020-03-02
    2
  • 每天晒白牙
    Raft这种"一切以我为主"的强领导模型和上一讲中的chubby有点类似,chubby是只能从主节点读取,相当于单机,性能和吞吐量有限
    Raft的强领导模型是写要以主为主,也相当于单机了。性能和吞吐量也会受到限制

    作者回复: 加一颗星:)

    2020-02-26
    2
  • 旅途
    老师 问个问题 如果 大多数跟随者节点 被相同任期编号 但是日志序号小的 先联络到了 这样的话 不是日志序号小节点 当选了吗
    2020-03-09
    1
  • 波波
    老师你好,如果一个跟随者因为网络原因未收到领导者心跳,这时这个节点变成候选节点,此时这个节点发起的投票,其他正常的节点会回应投票结果么?
    2020-03-08
    1
    1
  • 高山仰止
    老师你好!如果有一个跟随者因领导者心跳检测超时,变成了候选者,那么此时该候选者的提交任期编号是基于节点上一次接受到的最大任期编号+1,还是随机生成呢?
    2020-03-01
    1
  • Jialin
    https://zhuanlan.zhihu.com/p/27207160 这篇文档值得看看
    2020-02-29
    1
  • 范瑞
    老师您好,如果加了随机的超时时间,但是为了选取日志完整性较高的节点,导致一轮下来还是没有选举成功,那么会进行第二轮选举吗?此时的第二轮选举任期编号会 +1 吗?
    2020-02-28
    1
  • panda
    某个节点为收到心跳,于是发起新一轮投票,其他节点如何处理,毕竟任期编号+1
    2020-02-27
    1
  • 忆水寒
    单点故障
    2020-02-26
    1
  • 月迷津渡
    问题:如果出现多个候选者发起投票都不过半数,那么此时会重新选举。我的问题是某个候选节点怎么知道这次投票结束了呢,就是说在没有满足票过半数情况的下,节点怎么知道是没有新的投票进来了呢,是会每次接受投票有个超时时间还是?
    2020-03-22
  • 往事随风,顺其自然
    有没有可能任期编号和日志完整性都相同的情况
    2020-03-13
  • 岁月如歌
    raft算法的局限:
    1、强领导模型对于写功能基本退化单机性能,量大任然会出现性能瓶颈,适得其反。
    2、选举期间会集群将出现短暂不可用现象,影响时长与选举时间相关。

    有几个细节需要跟韩老师请教:
    1、raft集群如何感知其他节点呢?候选节点如何判断获得的票数已经过半,从而晋升为领导者?
    2、节点是如何存储任期编号?集群如果关闭重启是否任期编号归零?
    3、
    {1.当任期编号相同时,日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。比如节点 B、C 的任期编号都是 3,节点 B 的最后一条日志项对应的任期编号为 3,而节点 C 为 2,那么当节点 C 请求节点 B 投票给自己时,节点 B 将拒绝投票。}
    -------------------------------------------------------------
    文中该陈述应该标注为 选举有哪些规则 第6点。且表达意思与配图有所冲突: B节点(任期编号3)、C节点(任期编号4),C节点任期编号更大,为何B节点拒绝C节点投票请求? 请老师解析一下。
    2020-03-06
  • HuaMax
    当任期编号相同时,日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。比如节点 B、C 的任期编号都是 3,节点 B 的最后一条日志项对应的任期编号为 3,而节点 C 为 2,那么当节点 C 请求节点 B 投票给自己时,节点 B 将拒绝投票。
    ————
    关于这种情况,跟配图不太一致,如果B,C任期编号相同,都是3,节点C发起的选举投票应该是4,B不就应该接受投票吗?麻烦老师解惑
    2020-02-28
  • Dovelol
    老师好,想问一个问题,规则中为啥还要求日志完整性呢,那是不是选举通信还要带上自己完整的日志数据?如果特别多,会不会影响通信的效率。
    2020-02-27
    1
  • 施耀南
    局限在于领导的单机性能问题,而且可能选了处理速度不佳的领导!当然我有些对日志全是否等于性能好不大了解

    作者回复: 加一颗星:),单机性能瓶颈。一般而言,集群中的机型是相同的,节点的处理性能都是相同的。日志全和性能好,不是一回事,性能主要指的是写入性能,因为写操作必须在领导者节点上处理。

    2020-02-27
  • Purson
    Raft是CP还是AP,怎么快速区别?
    2020-02-27
  • 石头
    在一次选举中,每一个服务器节点最多会对一个任期编号投出一张选票,并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3,先收到了 1 个包含任期编号为 4 的投票请求(来自节点 A),然后又收到了 1 个包含任期编号为 4 的投票请求(来自节点 B)。那么节点 C 将会把唯一一张选票投给节点 A,当再收到节点 B 的投票请求 RPC 消息时,对于编号为 4 的任期,已没有选票可投了。

    老师你好!如果A先来,但他之前不是前任领导者,B后来的他是前任领导者。极端情况下领导者可能反复切换,是否会受影响?
    2020-02-27
  • 邵邵
    raft节点中的日志如何理解?

    作者回复: 存储用户指定的指令的一种数据格式,可以简单理解为一组指令:)

    2020-02-27
收起评论
28
返回
顶部