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

Raft Consensus Algorithm - 会出现这样的 log 吗?

  •  
  •   JasonLaw · 2021-10-24 11:42:13 +08:00 · 1434 次点击
    这是一个创建于 886 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Distributed Consensus with Raft - CodeConf 2016 - YouTube,出现了下图这样的 log 。这样的 log 会出现吗? server 2 怎么可能会成为 term 3 的 leader 呢? server 0 和 server 1 都不会投票给 server 2 的,因为 server 0 和 server 1 的 log 都是[1, 1, 1, 2],而 server 2 的 log 是[1, 1, 1]。

    Lecture 7: Fault Tolerance: Raft (2) - YouTube中,老师也讲了如下的 election restriction ,也能证明“server 2 不可能会成为 term 3 的 leader”。所以,上图的 log 是不是错误的?

    vote "yes" for some candidate who send us over request votes only if candidate has higher term in the last log entry, or (same term in the last log entry and log length >= the server that received the vote request).

    第 1 条附言  ·  2021-10-25 22:19:19 +08:00

    感觉自己还是需要看一下In Search of an Understandable Consensus Algorithm才行,很多细节还是不太明白。

    第 2 条附言  ·  2021-10-28 10:41:19 +08:00
    12 条回复    2021-10-28 10:25:34 +08:00
    oocococo
        1
    oocococo  
       2021-10-24 14:46:24 +08:00 via Android
    server 0 1112 ,server 1 111 ,server2 当选
    JasonLaw
        2
    JasonLaw  
    OP
       2021-10-24 15:09:20 +08:00
    @oocococo #1 也就是刚开始 server 0, 1, 2 都是[1, 1, 1],然后因为某些问题导致新一轮选举,server 0 成为了 term 2 的 leader ,但是 server 0 append 到了自己的 log 之后就跟 server 1 和 server 2 断开网络了,导致新一轮选举,此时 server 0 的 log 为[1, 1, 1, 2],server 1 的 log 为[1, 1, 1],server 1 投票给 server 2 ,server 2 成为了 term 3 的 leader ,然后 server 1 才接收到来自 server 0 的 index 为 3 的日志,此时 server 1 的日志为[1, 1, 1, 2]。对吗?
    JasonLaw
        3
    JasonLaw  
    OP
       2021-10-24 15:15:03 +08:00
    @oocococo #1
    @JasonLaw #2

    如果是这样的话,那么就算 server 2 成为 term 5 的 leader ,然后将 server 0 和 server 1 的 log 都变成[1, 1, 1, 3, 3, 3],也没啥问题吧?因为虽然原本 server 0 和 server 1 的 index 3 都是 2 ,但是对于 client 来说,Raft 是不会告诉它 index 3 是 committed 的,那么被重写也没啥问题。
    edgar
        4
    edgar  
       2021-10-24 19:05:25 +08:00
    term 1 看不出谁是 leader ,三个 server 都可能。
    term 2 server 0 是 leader ,因为三个 server 都有可能成为 leader 。同时只在 server 0 上提交了 index 3 的 log entry ,但是还没有复制到其他 server 。
    term 3 server 2 是 leader ,可以接受自己和 server 1 的投票。同时在 server 2 上提交了 index 3, 4, 5 的 log entry ,但是都没有复制到其他 server 。
    term 4 server 0 是 leader ,可以接受 server 0 和 server 1 的投票。成为 leader 后,第一是将本地的 index 3 复制到 server 1 上,第二是本地提交了 index 4 的 log entry 。
    JasonLaw
        5
    JasonLaw  
    OP
       2021-10-24 19:53:30 +08:00 via iPhone
    @edgar #4 谢谢这么详细的描述,那么 server 2 成为 term 5 的 leader 是可以的吧?
    edgar
        6
    edgar  
       2021-10-24 19:54:28 +08:00
    @JasonLaw 是可以的,可以获得 server 1, 2 的投票
    JasonLaw
        7
    JasonLaw  
    OP
       2021-10-24 20:06:58 +08:00 via iPhone
    @edgar #6 关键是视频里说 server 2 成为 term 5 的 leader 是不正确的😂,因为 server 0 和 server 1 的 index 为 3 的 log entry 被 overwritten 了。
    edgar
        8
    edgar  
       2021-10-24 20:15:25 +08:00
    @JasonLaw 我不清楚这个视频是怎么解释的,这个 log 看着像是 raft 算法中保证 safety 的一个例子。对应的是不要“Committing entries from previous terms”,即 term 4 的 leader server 0 不能因为 index 3 已经复制到大多数节点就 apply 它,这里这个 index 3 的值可能因为 server 2 成为 term 5 的 leader 而被 overwritten 。
    JasonLaw
        9
    JasonLaw  
    OP
       2021-10-25 21:49:26 +08:00
    @edgar #8 想问一下,#2 所描述的情况是合理的吗? server 2 成为了 term 3 的 leader 后,server 1 才接收到来自 term 2 leader server 0 的 index 为 3 的日志,此时 server 1 会做什么处理?直接 append 到 log 吗?
    edgar
        10
    edgar  
       2021-10-25 22:27:46 +08:00
    @JasonLaw term 3 中 server 1 已经投票给 server 2 了,这之后任何 term 低于 3 的请求都会被拒绝,即 server 1 会直接拒绝 server 0 发来的 term 为 2 的请求。
    JasonLaw
        11
    JasonLaw  
    OP
       2021-10-27 17:16:37 +08:00
    @edgar #10 嗯,In Search of an Understandable Consensus Algorithm - https://raft.github.io/raft.pdf 也说了。

    JasonLaw
        12
    JasonLaw  
    OP
       2021-10-28 10:25:34 +08:00
    @edgar #8 你说的没错,“视频说 index 3 是 committed”是错误的,他后面也讲了 Safe log commitment 。THX

    In Search of an Understandable Consensus Algorithm - https://raft.github.io/raft.pdf 也讲了。



    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1022 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:23 · PVG 03:23 · LAX 12:23 · JFK 15:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.