分布式协议与算法实战
韩健
腾讯资深工程师
立即订阅
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?
分布式协议与算法实战
登录|注册

08 | Raft算法(二):如何复制日志?

韩健 2020-02-28
你好,我是韩健。
通过上一讲的学习,你应该知道 Raft 除了能实现一系列值的共识之外,还能实现各节点日志的一致,不过你也许会有这样的疑惑:“什么是日志呢?它和我的业务数据有什么关系呢?”
想象一下,一个木筏(Raft)是由多根整齐一致的原木(Log)组成的,而原木又是由木质材料组成,所以你可以认为日志是由多条日志项(Log entry)组成的,如果把日志比喻成原木,那么日志项就是木质材料。
在 Raft 算法中,副本数据是以日志的形式存在的,领导者接收到来自客户端写请求后,处理写请求的过程就是一个复制和应用(Apply)日志项到状态机的过程。
那 Raft 是如何复制日志的呢?又如何实现日志的一致的呢?这些内容是 Raft 中非常核心的内容,也是我今天讲解的重点,我希望你不懂就问,多在留言区提出你的想法。首先,咱们先来理解日志,这是你掌握如何复制日志、实现日志一致的基础。

如何理解日志?

刚刚我提到,副本数据是以日志的形式存在的,日志是由日志项组成,日志项究竟是什么样子呢?
其实,日志项是一种数据格式,它主要包含用户指定的数据,也就是指令(Command),还包含一些附加信息,比如索引值(Log index)、任期编号(Term)。那你该怎么理解这些信息呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《分布式协议与算法实战》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(35)

  • 花家舍 置顶
    http://thesecretlivesofdata.com/raft/
    动画演示 比文章牛逼多了

    编辑回复: 这个资源好,推荐

    2020-03-13
    7
  • Scott
    我有一个问题,考虑下面这种情况,假设集群有1 leader 多 follower
    1. leader发出一条set x = 1,index为最新的appendEntries到所有的follower
    2. 只有一台follower响应了,所以leader对client返回fail
    3. 这时leader挂了,剩余机器重新进行选举,因为前面那台follower有最新的uncommited的日志,所以它会被选举为leader

    这时就会有一个不一致,外部client认为set x = 1没有成功,但是实际上x = 1是成功的,这种情况合法吗?
    2020-03-01
    14
    7
  • XHH
    提供一个Raft算法动态演示教程,很清晰: http://thesecretlivesofdata.com/raft/
    2020-02-28
    2
    5
  • 葉月喵
    上一章跟随者投票时会比较日志索引号大小,用的是已提交的日志,还是已经复制的日志?

    作者回复: 复制的,uncommited的。

    2020-02-28
    1
    4
  • Mars
    老师,我有个问题,在那个复制日志的五个过程里,如果第四步执行返回结果成功了,leader突然挂了,此时leader 的状态机已经更新,follower状态机没有更新,此时新选举出来的leader怎么处理这个流程来保证上一个leader的状态机更新apply到其他节点上了呢?
    2020-03-11
    3
    2
  • DZ
    老师,请教下如果在指定时间内没有收到大部分follower复制成功响应,只收到少数,那么领导者如何处理这次提交?是直接不做任何处理,由心跳或者下次提交重新对齐日志?还是有重试或者rollback机制?
    2020-03-19
    1
  • 阿kai(aeo
    感觉处理日志一致性问题的时候非常不efficient,如果follower落后得多了,那么来回的RPC大部分都是failure,很耗时间和带宽。follower是否可以直接返回它拥有的最新index,然后leader根据那个index开始看是否match自己的日志,如果match就直接一次性把剩余日志都给follower发过去。这样会有效率一些吧?
    2020-03-16
    1
    1
  • zjm_tmac
    有两个问题,状态机指的是上层应用方的状态机吗?比如etcd-raft对应的状态机是etcd的wal模块吗?另外如果日志已经commit但未apply的情况下提交给状态机失败了,比如唯一性冲突了,这种情况下日志会怎么处理呢?
    2020-03-01
    1
  • 深海极光
    这时,领导者会递减要复制的日志项的索引值,并发送新的日志项到跟随者,这个消息的 PrevLogEntry 值为 6,PrevLogTerm 值为 3。如果跟随者和leader差的远,比如是3,那就是要从7到3要5次RPC调用才能开始同步,是不是有性能问题

    作者回复: 在代码实现时,这块可做优化。

    2020-02-29
    1
  • 沈飞龙
    老师 有个疑问,当领导者提交日志到本地状态机后与客户端网络出问题了,此时客户端会以为本次写入不成功,这样就导致客户端与集群信息不一致,该怎么处理呢?

    作者回复: 重试,指令操作具有冥等性就可以了,比如,set x = v。

    2020-02-28
    1
    1
  • Jialin
    1.Raft 日志格式:
    • 指令:一条由客户端请求指定的、状态机需要执行的指令。即客户端提交的数据
    • 索引值:日志项对应的整数索引值,用来标识日志项的,是一个连续的、单调递增的整数号码
    • 任期编号:创建这条日志项的领导者的任期编号
    2.理想的日志复制阶段:
    • 接收到客户端请求后,领导者基于客户端请求中的指令,创建一个新日志项,并附加到本地日志中
    • 领导者通过日志复制 RPC,将新的日志项复制到其他的服务器
    • 当领导者将日志项,成功复制到大多数的服务器上的时候,领导者会将这条日志项提交到它的状态机中
    • 领导者将执行的结果返回给客户端
    • 当跟随者接收到心跳信息,或者新的日志复制 RPC 消息后,如果跟随者发现领导者已经提交了某条日志项,而它还没提交,那么跟随者就将这条日志项提交到本地的状态机中
    3.实际生产环境中,复制日志的时候遇到进程崩溃、服务器宕机等问题,这些问题会导致日志不一致。Raft 算法按照“Raft 是通过以领导者的日志为准,来实现各节点日志的一致的”原则处理不一致日志,实现日志的一致,具体如下:
    • 领导者通过日志复制 RPC 的一致性检查,找到跟随者节点上与自己相同日志项的最大索引值。也就是说,这个索引值之前的日志,领导者和跟随者是一致的,之后的日志是不一致的了。
    • 领导者强制跟随者更新覆盖的不一致日志项,实现日志的一致

    课后思考题:领导者接收到大多数的“复制成功”响应后,就会将日志提交到它自己的状态机,然后返回“成功”响应客户端。如果此时有个节点不在“大多数”中,也就是说它接收日志项失败,那么在这种情况下,Raft 会通过日志复制 RPC 的一致性检查,找到失败者节点上,与自己相同日志项的最大索引值,然后领导者强制该失败者更新覆盖的不一致日志项,实现日志的一致

    作者回复: 加一颗星:)

    2020-02-28
    1
  • 每天晒白牙
    处理日志项一致通过RPC一致性检查,找到追随者中与自己相同日志项的最大索引,然后把后面的日志项同步过去,让追随者复制更新

    作者回复: 加一颗星:)

    2020-02-28
    1
  • 每天晒白牙
    老师我有个小疑惑,就是Raft在处理日志不一致时会给追随者发送RPC一致性检查,找到和自己相同日志项的最大值,这里是对每个追随者而言的还是所有的追随者而言的?

    作者回复: 每个跟随者:)。日志复制信息,对每个跟随者,都要单独维护的。

    2020-02-28
    2
    1
  • static
    老师好,我有个一直以来的疑问,例如raft算法中客户端写数据set A,此时leader发起一次日志写并且RPC复制日志给follower,如果leader收到多数请求后,且成功提交状态机,但在下一次心跳之前它挂了,其他节点还没有收到leader最新提交的心跳消息,导致最后一条数据在follower中处于未提交状态(没提交状态机),那这条数据是不是就丢了?如果其他节点成为了leader,那是不是这台挂了的机器在恢复后,也会把这条已经提交的抹掉,因为这是一条和最新的主节点不一致的数据?
    类比到分布式锁来说,如果我现在加了一个分布式锁在raft算法上,但是此时leader节点挂了,follower还没应用锁信息到状态机,并且follower变为leader,此时又有一个客户端来加分布式锁,一看没锁就成功获取到锁,此时就破坏了分布式锁的同步性质?
    2020-03-21
  • 王兵
    老师,follower节点的日志项被覆盖时,是不是意味着这个节点的状态要被回滚:)
    2020-03-20
  • 密码123456
    什么是状态机?
    2020-03-17
  • 姜川
    百度了一下,如果leader在提交状态机后,在发送下一次心跳之前挂了,这条数据应该不会丢,如果这台彻底挂了,其他节点成为leader后只能操作自己任期内的日志,所以之前领导告诉的未提交的日志是不会删除的,
    然后之前的leader如果恢复了,主会同步它的日志数据,但任意一条已经提交到状态机的日志,它是不会被覆盖删除的,新的leader发现旧leader有一条提交了,但自己却没有提交,且不是自己任期内的,应该就会按已提交的结果更新自己吧
    2020-03-17
  • 姜川
    有个疑问,如果leader收到多数请求后,且成功提交状态机,但在下一次心跳之前它挂了,其他节点还没有收到leader最新提交的心跳消息,导致最后一条数据在follower中处于未提交状态,那这条数据是不是就丢了,如果其他节点成为了leader,那是不是这台挂了的机器在恢复后,也会把这条已经提交的抹掉,因为这是一条和最新的主节点不一致的数据
    2020-03-17
  • 请问,raft第二阶段提交中,文章中说跟随者采用RPC日志复制来进行提交操作,是不是就是依据PrevLogEntry以及PrevLogTerm和自己状态机中的数据做对比,然后进行提交的?
    2020-03-15
  • panda
    客户端并不知道谁是leader,怎么保证客户端的请求一定是由lead来处理的?
    2020-03-11
收起评论
35
返回
顶部