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

实现 Raft 时遇到的一个细节问题,求指点

  •  
  •   streamo · 2018-06-04 14:55:05 +08:00 · 2083 次点击
    这是一个创建于 2124 天前的主题,其中的信息可能已经有所发展或是发生改变。
    假设有 5 台服务器编号 1 到 5,编号 1 的服务器是 leader,其他(也就是编号 2 到 5 的四台)都是 follower。

    在 term 1 的某一时刻 leader 已提交了截至 index 为 100 及之前的所有日志(即 leader 的 commitIndex=100 ),此时 leader 向四个 follower 通过 AppendEntries 成功发送了 index 为 105 及之前的所有日志,这些 AppendEntries 里的 leaderCommit 跟 leader 上的 commitIndex 保持一致也就是 100,发送完毕后 leader 立刻 fail。

    四台 follower 收到 AppendEntries 后将截至 index 为 105 前的所有日志都添加到 log[]中,但因为收到的 leaderCommit 是 100,所以只会将 index 100 及之前的日志应用到状态机。因为之前的 leader server 1 挂掉不再发送心跳,所以另外四台服务器超时后发起选举,就假设 server 2 被选成 term 2 的 leader,其余四台成为 follower。

    因为各台 server 的 log[]里都有 index 为 105 及之前的日志,leader 的 matchIndex[]会通过 AppendEntries 很快更新到全部都是 105 的状态,尽管此时 matchIndex[]里的多数(这个例子是全部)都是 105,但因为 leader 的 log[]中 index 为 105 和之前的日志 term 是 1 而不是当前 term 2,所以包括 101-105 这几条日志并不会在现在 term 2 的 leader server 2 上被提交,但这些日志又不能被放弃,于是 leader 就卡在这了……

    这个过程我一定是哪里想错了,求指点是哪里出了问题。
    5 条回复    2018-06-04 21:00:18 +08:00
    wqlin
        1
    wqlin  
       2018-06-04 15:34:20 +08:00
    嗯,如果在 term 2 的时候没有 propose 新的日志,那么 server 2 就不能 commit 101-105 这几条日志,所以就可能出现活锁的问题。Raft 作者在论文提到新的 leader 上任后可以提交一个空的日志,帮助 commit,但是一时没找到在哪里...
    streamo
        2
    streamo  
    OP
       2018-06-04 16:15:31 +08:00 via Android
    @wqlin 求论文里提到这个问题的具体位置(好吧我还是看论文不够仔细)
    wqlin
        3
    wqlin  
       2018-06-04 16:36:42 +08:00
    @streamo #2 找到了,在 raft thesis 中 6.4 Processing read-only queries more efficiently 中提到了:
    >
    If the leader has not yet marked an entry from its current term committed, it waits until it
    has done so. The Leader Completeness Property guarantees that a leader has all committed
    entries, but at the start of its term, it may not know which those are. To find out, it needs to
    commit an entry from its term. Raft handles this by having each leader commit a blank no-op
    entry into the log at the start of its term. As soon as this no-op entry is committed, the leader ’ s
    commit index will be at least as large as any other servers ’ during its term.
    >
    streamo
        4
    streamo  
    OP
       2018-06-04 20:50:12 +08:00 via Android
    @wqlin 看了下这个似乎是对只读操作的优化,所以按作者的意思如果不需要这个只读优化的话让这个活锁不断循环也没什么大碍?
    wqlin
        5
    wqlin  
       2018-06-04 21:00:18 +08:00   ❤️ 1
    @streamo #4 不记得是不是只有这里涉及了 blank no-op,但是思想是相同的,就是新的 leader 上任后可以自己 propose 一个 command 帮助 commit,SO 的这个问题 https://stackoverflow.com/questions/37210615/raft-term-condition-to-commit-an-entry 有提到:
    >
    What this means in practice is when a leader is elected, it typically commits a no-op entry to force a commit in its current term. The leader doesn't increase its commitIndex until the no-op entry is stored on a majority of servers.
    >
    而且找到一个 Raft 实现,详见: https://github.com/yahoo/gondola,专门分出了一个 blank command:
    >
    Note blank commands (command 3) are written into the log after a leader election. This is due to a Raft requirement that entries are not considered committed unless the last committed entry is of the current term. Applications need to ignore these blank commands.
    >

    活锁是否重要取决于应用程序,如果能保证 client 会不同的 propose,那么不处理也没事。但是通常情况下都无法保证,所以一般使用 blank command 帮助 commit
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5486 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 08:16 · PVG 16:16 · LAX 01:16 · JFK 04:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.