Skip to content

Raft commit index is not monotonic #166

@tangruize

Description

@tangruize

Describe the bug

According to the raft paper, commitIndex should increase monotonically. But under certain conditions pysyncobj violates it.

The root cause is that self.__raftCommitIndex is set to min(leaderCommitIndex, self.__getCurrentLogIndex()) unconditionally when processing msg append_entries.

self.__raftCommitIndex = min(leaderCommitIndex, self.__getCurrentLogIndex())

To Reproduce

  1. Init a cluster with 3 nodes.
  2. Node 1 becomes Leader and send append_entries to other nodes. And its log is [{"cmd":"NO_OP","idx":1,"term":0},{"cmd":"NO_OP","idx":2,"term":1}]
  3. Node 2 and Node 3 receive the append_entries, and replies next_node_idx 2
  4. Node 1 receives the next_node_idx 2.
  5. Node 1 sends append_entries
  6. Node 2 and Node 3 receive the append_entries, and replies next_node_idx 3
  7. Node 1 receives the next_node_idx 3 and updates its __raftMatchIndex of other nodes to 2.
  8. Node 1 advances __raftCommitIndex to 2.
  9. Node 2 election times out, becomes leader, and sends append_entries with __raftCommitIndex=1.
  10. Node 1 receives the append_entries, and sets __raftCommitIndex=1, which violates the monotonicity specification.

A Possible Fix

Add a condition check:

if leaderCommitIndex > self.__raftCommitIndex:
    self.__raftCommitIndex = min(leaderCommitIndex, self.__getCurrentLogIndex())

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions