Skip to content

Consistent reads are confirmed by a single follower reply (ReadIndex needs a fresh majority) #35

Open

Description

@resetius

Problem

A --consistent read on the leader is confirmed too early.

  • TRaft::OnAppendEntries passes the seqno of every successful AppendEntries reply to CommitAdvance (raft.cpp#L254-L262), which does CommitSeqno = max(CommitSeqno, seqno) (raft.cpp#L84-L86). So the reply of any single follower with a high enough seqno is enough to release the read in ProcessWaiting (raft.cpp#L669-L670).
  • TRaft::ApproveRead stores the seqno in an int and returns it as uint64_t (raft.cpp#L410-L416); Seqno is uint64_t (raft.h#L152), so the value is truncated after 2^31 messages and the comparison with CommitSeqno breaks.

Scenario

5-node cluster with a stale leader L (it has been partitioned from the majority, which has already elected a new leader, but L does not know yet). L is still connected to one follower F. A client sends a --consistent read to L. L sends heartbeats, F replies with a seqno at or above the read barrier, CommitSeqno advances, and L answers the read from its local state. Only 2 of 5 nodes (L and F) took part, so the answer can miss writes already committed by the new leader: the read is not linearizable.

In a 3-node cluster the leader plus one follower is already a majority, so the problem shows from 5 nodes up.

Expected

ReadIndex (Ongaro, PhD thesis 2014, section 6.4) requires that, after the read request arrived, the leader has committed an entry of its current term and has received acknowledgements to heartbeats sent after the read arrived from a majority of the cluster (itself included). That needs a read barrier seqno, an acknowledged seqno per peer, and a quorum computation over those, and ApproveRead must keep the full 64-bit seqno.

Fix in PR #31

PR #31 (closed, not merged) has the fix in d114d5d (read barrier seqno, per-peer acknowledged seqno, quorum in CommitSeqno, current-term precondition) and the reply correlation it needs in cbbbfa1. Tests that cover it: test_strong_reads_require_fresh_majority_in_all_cluster_sizes, test_stale_leader_with_one_follower_cannot_serve_strong_read, test_new_read_cannot_reuse_previous_read_quorum, test_delayed_pre_read_replies_cannot_confirm_new_read. It touches CommitAdvance next to the majority fix, so a trivial rebase between the two is expected. Since the PR is closed, the fix would come as a separate small PR.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions