V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
phpcyy
V2EX  ›  程序员

一个关于 Raft 协议的疑问

  •  1
     
  •   phpcyy · 2020-07-02 08:57:39 +08:00 · 4465 次点击
    这是一个创建于 1365 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如果有 A 、B 、C 、D 、E 一共 5 个节点,A 是 Leader 。 原本的 logIndex 都是 3,如果 A 发送了 4 的日志,B 、C 确认,获得多数 ack,会返回 client 成功。

    第一个问题: 这时候如果 Leader 挂掉,B 、C 还没来得及接收下次心跳进入 committed 状态,4 这条日志仍然能保存成功吗?

    第二个问题: 如果这时候 A 、B 挂掉,4 这条日志还能确保可以成功保存吗?

    最近在看 Raft 相关文章,都没理解上边的这个情况该如何处理,所以求教大家,不胜感激。

    我的理解是第一种情况,需要获得多数节点 4 这条日志的状态,B 、C 加上必然存在该消息的 Leader,可以过半,因此可以保存成功。

    第二种情况看起来系统已经不能正常工作了,无法确认这条 uncommited 的消息是否需要保存。

    第 1 条附言  ·  2020-07-02 18:59:08 +08:00
    非常感谢大家的回复,很多回复都非常有价值,对我帮助很大。

    我大概已经理解了我问的 2 个问题,也对 Raft 有了更清晰的理解。

    我给了一些非常有帮助的回复点了红心,另外一些也很有价值的回复我没有点红心,是为了让之后的感兴趣的读者能够更快找到答案。

    再次感谢大家。
    42 条回复    2020-07-03 14:40:48 +08:00
    chihiro2014
        1
    chihiro2014  
       2020-07-02 09:05:08 +08:00   ❤️ 3
    看 mit 6.824 岂不是更香?里面都有讲解这块的
    https://www.bilibili.com/video/av91748150
    BBCCBB
        2
    BBCCBB  
       2020-07-02 09:08:11 +08:00   ❤️ 2
    第一个问题, 可以保存成功, 因为 D,E 的日志比 B,C 上的旧, 所以下一轮选举 B,C 是不会投给 D,E 的, 下一轮的 leader 只会从 B,C 中选出.

    第二个问题, 因为 C 的日志比 D,E 的新, 剩下 C,D,E 3 个节点, 就是说要所有投票投给一个节点才能继续工作, 那肯定也只有所有投票投给 C 才能继续工作, 所以 4 依然是已经保存了的..

    我做 6.824 过了好几个月了, 可能有误, 仅供参考, 欢迎指正
    luckyrayyy
        3
    luckyrayyy  
       2020-07-02 09:08:48 +08:00   ❤️ 1
    phpcyy
        4
    phpcyy  
    OP
       2020-07-02 09:12:36 +08:00
    @BBCCBB

    针对第二种情况,如果 A 、B 挂了,C 的 4 可能是 2 种情况,A 、C 上有,A 、B 、C 上有,如果前一种情况那么没达成共识,如果后一种情况达成了共识,C 无法断定是哪一种情况啊。
    OSDI
        5
    OSDI  
       2020-07-02 09:16:53 +08:00 via Android
    原论文图八说明的情况就是,都不能保证的吧
    BBCCBB
        6
    BBCCBB  
       2020-07-02 09:21:40 +08:00   ❤️ 1
    @phpcyy 我以为你说的第二种是 4 已经提交到 A,B,C 了呢... 按你说的 A,B,C 都已经提交 4 了呀..

    如果 4 已经被 commit 了, 那肯定没问题

    如果 4 没被提交, 剩下 C,D,E 节点, 4 被包含在里面也没啥问题, 只是成了脏数据..


    > 毕竟 raft, paxos 这种是肯定保证如果多数确认, 并且提交了, 那数据肯定不会丢失的..
    kmyzzy
        7
    kmyzzy  
       2020-07-02 09:28:54 +08:00
    @phpcyy A 、B 挂了只有 C 能成为 Leader,C 会把 4 发给 D 、E,所以只要 C 能在自己的 Term 成功 commit 一个 log,4 就一定能保存。
    phpcyy
        8
    phpcyy  
    OP
       2020-07-02 09:32:12 +08:00
    @BBCCBB

    我的意思是 A 提交了 4,B 、C 收到了进入 uncommited 状态,需要在 A 下一次心跳的时候变为 commited,但是 A Commit 后没来得及心跳就挂了,B 、C 处于 uncommited 状态,这时候发生了重新选举。

    1. 在这种情况下,如果 A 挂了,B 、C 活着,能否保证 4 这条消息不会丢失。

    2. 如果 A 、B 挂了,C 活着,能否保证 4 这条消息不会丢失。

    第一种情况下,B 、C 理论上仍然可以就 4 这条消息达成多数。
    第二种情况下,C 无法确认 4 这条消息是否达成多数,丢弃和不丢弃无法确定,因为它不知道 B 是否保存过 4 这条消息。
    phpcyy
        9
    phpcyy  
    OP
       2020-07-02 09:33:53 +08:00
    @kmyzzy 是这样的,C 的 4 这条消息是 uncommited 状态,如果它采纳了,那么可能是脏数据;如果不采纳,可能会丢失数据。除非整个集群不工作了等待 A 、B 复活。
    lance6716
        10
    lance6716  
       2020-07-02 09:36:05 +08:00 via Android
    4 这个日志会在本地持久化的因此不会丢,并且协议保证其他机器的 4 不会有不用的日志 append 成功
    phpcyy
        11
    phpcyy  
    OP
       2020-07-02 09:38:37 +08:00
    @lance6716 4 这个消息会持久化到 A,那其他节点若正常工作,在我描述的情况下 4 会被正常复制到其他节点吗?
    OSDI
        12
    OSDI  
       2020-07-02 09:40:08 +08:00 via Android
    @OSDI 抱歉,看错了
    BBCCBB
        13
    BBCCBB  
       2020-07-02 09:43:19 +08:00   ❤️ 1
    @phpcyy
    第二种情况, C 不需要确认 4 是否达成多数, 这个是由 A 来判断的, A 判断多数已经提交了, 那就可以返回 4 已经保存成功..

    A,B 宕机后, C 日志最新, 会成为 Leader, 所以 4 依然不会丢失.
    BBCCBB
        14
    BBCCBB  
       2020-07-02 09:44:21 +08:00
    @OSDI 哈哈, figure 8 是处理不能主动提交上一个 term 的 log 吧
    lllllIIIlll
        15
    lllllIIIlll  
       2020-07-02 10:28:35 +08:00   ❤️ 1
    第二种情况下,C 无法确认 4 这条消息是否达成多数,丢弃和不丢弃无法确定,因为它不知道 B 是否保存过 4 这条消息。
    ---------------
    这应该也是当前 Term 的 Leader 不主动提交上一个 Leader 的原因吧,因为 C 无法根据自己的信息确认上一个 term 的消息是否复制到了大多数节点。
    按你说的第二种情况,C 并不知道 log 4 是否已经复制到了大多数节点上,但是由于 C 此时的 log 是 more up-to-date 的,所以一定是 C 当选 leader,然后 C 会与其他 follower 同步日志,并且在成功 commit 一条自己 Term 中的日志后隐式地提交 log 4 。
    针对 log 4 的两种情况:
    1. A 没有把 log 4 复制到大多数节点 =>那么 C 在同步日志时,相当于代替 A 复制了 log 4 。
    2. A 把 log 4 复制到了大多数节点 => 那么 C 同步日志没有问题,相当于代替 A commit 了 log4 。
    并不会产生错误。

    很久之前看的 raft 了,不保证细节完全正确。
    @phpcyy
    bilosikia
        16
    bilosikia  
       2020-07-02 10:31:50 +08:00   ❤️ 1
    1. 第一个是能保存成功的,1. leader 选出新的 leader 一定包含最新的 log 2. 前任 leader 的 log 谁着新任 leader 一起提交
    2. 半数以上节点可用就行,A,B 挂了,只有 C 节点能当选新 leader
    sunznx
        17
    sunznx  
       2020-07-02 10:44:04 +08:00   ❤️ 1
    如果有 A 、B 、C 、D 、E 一共 5 个节点,A 是 Leader 。 原本的 logIndex 都是 3,如果 A 发送了 4 的日志,B 、C 确认,获得多数 ack,会返回 client 成功。

    第一个问题: 这时候如果 Leader 挂掉,B 、C 还没来得及接收下次心跳进入 committed 状态,4 这条日志仍然能保存成功吗?
    ------------
    能成功,因为 A 已经成功返回给 client 了。

    第二个问题: 如果这时候 A 、B 挂掉,4 这条日志还能确保可以成功保存吗?
    ------------
    可以,因为 raft 保证日志一旦被提交给客户端,就一定是成功的
    phpcyy
        18
    phpcyy  
    OP
       2020-07-02 10:47:07 +08:00
    @lllllIIIlll

    针对 log 4 的两种情况:
    1. A 没有把 log 4 复制到大多数节点 =>那么 C 在同步日志时,相当于代替 A 复制了 log 4 。
    ---------------------------------------------------------

    C 代替 A 复制了 log 4 并 commit,即使 A 可能出现未 commit 的情况,对吗?

    好像有点明白了,只保证 leader 已 commit 的必定会保存,但是原 leader 未 commit 的消息仍然会由新 leader 广播其他节点保存,但 client 可能收不到响应,不知道是不是这样?
    noogler67
        19
    noogler67  
       2020-07-02 11:24:00 +08:00 via iPhone
    第二个问题,raft 会保证选举出来的 leader 带有 4 。选举 leader 的时候会判断 candidate 的 log ( term 更旧则拒绝,相同 term 更短则拒绝),所以只有 c 能当选。
    这也是 raft 的核心,一旦 commit,就肯定能保存记录。
    misaka19000
        20
    misaka19000  
       2020-07-02 11:36:11 +08:00
    想起来当初自己折腾 raft 的时光。。。现在已经全部忘光了
    ZingLix
        21
    ZingLix  
       2020-07-02 11:43:56 +08:00 via Android
    @phpcyy 我一直理解的是日志提交的条件是被多数结点 append,而不是 Leader 将其 commit 。一旦满足就一定会在之后某个时刻把 commit 通知到所有节点上去。
    client 在请求后,Leader 挂了没有响应似乎的确可能发生,但正确性还是在的。
    fishofcat
        22
    fishofcat  
       2020-07-02 11:46:31 +08:00
    5 个节点有三个节点有数据,那么 A 挂了肯定 b,c 选,如果 a,b 挂了,这时候投票原则还是 c 会被选出来,因为 logindex 最大,c 会把数据同步到其它节点。

    这时候其实关心的主要问题应该是,a 挂了,a 也没有给 client 回复消息,这时候怎么办?用户如果再次请求,服务端怎么办?(幂等性),如果客户端不请求了,这个数据也会被添加到 log 里面,这时候咋办??
    sunznx
        23
    sunznx  
       2020-07-02 11:48:56 +08:00
    接下来的选举中,C 一定可以成为 leader 。只剩下 3 个节点,这些节点要想成为 leader,就必须获得 >= 3 的节点同意,只有 C 有最完整的 log,所以一定是 C 当选,Term 也跟着变了
    phpcyy
        24
    phpcyy  
    OP
       2020-07-02 11:51:30 +08:00
    @noogler67 没错,你说的都对,特别感谢。不过要澄清一点,我提出问题二的原因是,如果 B 没收到 4,C 收到了 4,C 当选 Leader 并提交了这条日志,但是 A 之前未收到多数并没有提交,也就是 client 并不知道这条日志已经提交了,感觉不太合逻辑,所以才会有这个疑问。
    phpcyy
        25
    phpcyy  
    OP
       2020-07-02 11:58:50 +08:00
    @fishofcat 对啊,我现在的主要问题点变成了你这个问题,客户端不知道集群已经执行了该命令,该怎么办
    lllllIIIlll
        26
    lllllIIIlll  
       2020-07-02 13:02:35 +08:00
    @phpcyy 但 client 可能收不到响应,不知道是不是这样?
    ----------------------------------------------------------------
    这个应该是属于上层实现的问题了,raft 应该不保证这一点。无论是哪一任 leader commit 一个 log 应该都可以有办法通知到上层,Mit6.824 应该是用一个 apply channel 来通知的。但是如果客户端超时错过了通知怎么办,应该取决于应用的实现了。可以参考一下具体的实现,比如 tikv 。
    noogler67
        27
    noogler67  
       2020-07-02 13:07:47 +08:00
    client 继续请求 C 的话,C 本身会把 log 复制给别的机器。等 C 复制超过一半机器,就会给 client 返回 commit 成功的消息。
    noogler67
        28
    noogler67  
       2020-07-02 13:09:16 +08:00
    每一条 log 可以记录 client 的请求的序列号 id 。可以知道是 client 的之前的那条请求。
    noogler67
        29
    noogler67  
       2020-07-02 13:16:03 +08:00   ❤️ 1
    如果 client 超时中断请求,那 client 就不知道后续状态了。
    如果 client 超时,继续请求,client 就能知道状态。根据 raft 协议的话,认为 raft 集群不会挂的情况下,client 应该选择不懈地请求直到 commit 。6.824 lab 中是这样做的。
    fishofcat
        30
    fishofcat  
       2020-07-02 13:35:21 +08:00
    @noogler67 不用等继续请求的,只要选出主来,c 就会用自己的 term append 一个本 term 的空 entry,老的也会被一起 append 上,其它的解释是对的。client 端一般是要求要重试的。像支付失败,如果 client 端断网,那么你也会收到短信。
    wqlin
        31
    wqlin  
       2020-07-02 13:57:53 +08:00   ❤️ 1
    我觉得大前提不对,需要日志 committed + apply 才会返回给 client 。
    第一个问题的话可能会保存成功,也有可能不会(取决于 B/C 是否成功当选)
    第二个问题的话比较难了。
    Raft 中只有 committed 的日志才是安全不丢的( index <= committed index ),其他情况下都是不安全的。
    一家之言,仅供参考
    wqlin
        32
    wqlin  
       2020-07-02 13:59:03 +08:00
    保存不代表已经 committed 了,一切以 leader 日志为准
    phpcyy
        33
    phpcyy  
    OP
       2020-07-02 14:05:21 +08:00
    @fishofcat 如果一个命令 client 提交了,然后 client 连接的 leader 宕机,该消息可能成功也可能失败;只要该日志在 leader 宕机之前发给了其他节点,其他节点中的有该最新日志的一台会当选为新的 leader,该命令执行成功;如果在宕机之前没有发给其他节点,该命令不会出现在其他节点,该命令会执行失败。

    所以需要依赖具体应用的实现去让客户端在失败时去请求集群,获取之前命令是否执行成功。
    phpcyy
        34
    phpcyy  
    OP
       2020-07-02 14:10:13 +08:00
    @wqlin 你说的是对的,我省略了一些步骤,就是返回 client 成功的时候一定是 commited + applied 的。

    我提出问题的时候想的是其他节点并不知道 Leader 已经 commited 且 applied,所以如何判断是否保存之前处于 uncommited 的消息。

    现在看来是他们会由于日志更新而当选 Leader,并将该消息 commit 且 apply 。
    wqlin
        35
    wqlin  
       2020-07-02 14:17:11 +08:00
    @phpcyy 你忽略了一个前提。leader 要 committed 的话,一定要集群多数派都收到了日志并且 ack 了。这种情况下才能 committed 。
    日志 committed 之后就算原 leader 挂掉了,其他节点还会有日志。并且按照 raft 的选举条件,也是拥有最多 committed 日志的节点当选
    phpcyy
        36
    phpcyy  
    OP
       2020-07-02 14:20:53 +08:00
    @wqlin 已经 commited 的日志一定是不会丢的,因为多数节点已经接收到了日志,所以只要这个系统还在工作,这个日志一定还是会在新的 Leader 上的。我之前的疑问是,一些老 Leader 没有 commit 的消息,其他节点也可能会将其 commit,因为他们无法区分老 Leader 是否提交了该日志。
    Caskia
        37
    Caskia  
       2020-07-02 16:21:25 +08:00   ❤️ 1
    @phpcyy 第二问题 @noogler67 解释的很清楚,client 会在超时之前等待这次操作的结果,也就是说就算选举出了新的 leader,那么新的 leader 也会告诉 client 这次操作 committed 。这里有个你忽视的地方,你认为 client 请求 leader1 的时候,leader1 挂掉了,此时 client 就认为失败了,然后会有一个超时时间差,在这段时间里,新的 leader 会把结果告诉 client,在实践的时候是看的集群挂掉了才是真的失败。
    diveIntoWork
        38
    diveIntoWork  
       2020-07-02 17:33:59 +08:00
    多数 ack 的 log,是一定不会丢的,这个是 raft 的 leader 完整性约束保证的
    NoobPhper
        39
    NoobPhper  
       2020-07-02 18:00:49 +08:00
    有点乱:

    你屡屡思路, 如果 A 挂 理想状态 BCD 任何一个都没有发生 P,那么 BCD 收到了 Leader 的 apply 请求,并且 Ack 了,那么 4 这条日志肯定不会丢鸭

    还有 leader 挂了, 客户端立马就知道了,这个时候应该是客户端重试, 重试又会有新的 revision, 不复杂,复杂的是
    leader 挂了,然后极端情况下 bcd 出现了 P, 场景复杂很多,建议看下 etcd 的 文档将了一部分这些东西
    wqlin
        40
    wqlin  
       2020-07-03 10:04:24 +08:00
    @phpcyy 只有 leader 能 commit 。。老 leader 不知道 commit,然后其他节点 commit 了。这种情况下只能是老 leader 要么挂掉了要么成为 follower 了,总之已经有新 leader 了
    fishofcat
        41
    fishofcat  
       2020-07-03 13:12:45 +08:00
    @Caskia 新的 leader 怎么回复 client 端?原先的 leadera 都挂掉了,长链接都断开了,原先的 leader 怎么知道 client 的地址的????应该是 client 会重新发起请求,然后新的 leader 根据某个条件判断是否请求过了。其实我没太搞懂的是 client 重发的时候服务端怎么判断已经请求过了。。。
    Caskia
        42
    Caskia  
       2020-07-03 14:40:48 +08:00
    两种实现方式:
    1. 如果超时,客户端会访问其他的任意服务,这时候服务会把新的 leader 给 client,所以 client 是可以跟新的 leader 进行交流的。
    2. 如果是 client 重新发起请求,文档中有说过对发起的请求要做唯一性,也就是给每一个请求都有一个标号,这样服务端可以做幂等处理,新的 leader 看到这个重复的标号,那么就知道是之前处理过的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3369 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 13:16 · PVG 21:16 · LAX 06:16 · JFK 09:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.