CoursesSystem design from first principles to design review

Puzzle 10 · 11 of 19

Who can confirm a write when regions cannot talk?

Understand majority agreement and the cost of losing contact.

All puzzles in this course

The problem

Each replica can have a different view while messages are delayed. Three nodes maintain a shared decision history. One is cut off but still receives requests. Can both sides independently grant the same last space?

See it

A two-to-one split after the first grant Three voting nodes A B C Leader Grant 17 Grant 17 A alone: 1 vote B + C: 2 votes 1 vote

Scroll sideways to see the full diagram.

  1. A leads a cluster of three voting nodes. For this example, all start with identical committed history.

    Step 1 of 4
  2. A replicates its current-term entry for grant 17 to B. A and B form a majority, so the leader commits it and replies to Ada.

    A and B have committed grant 17. Now A is isolated. Can A confirm another shared grant alone?

    Step 2 of 4
  3. A becomes isolated. It can still receive a client request but cannot replicate a new entry to a majority. Ben cannot get a new confirmation there.

    Step 3 of 4
  4. B has the newer log and can win an election with C. The pair can commit new current-term entries. A can neither elect itself nor commit alone.

    Step 4 of 4

The building block

A log is a list of decisions with numbered positions. Replicating it means storing copies on several nodes. A leader proposes the next entry. A term is a numbered election period. An entry keeps the term in which its leader created it, even after a new election starts. A majority of three is two. Any two majorities intersect. Raft combines this property with election rules, numbered leadership terms and rules for committing entries. Counting two arbitrary replies does not implement consensus. A leader also needs evidence that its decisions belong to the correct history.

In a two-plus-one split, the pair can continue committing under a valid leader. The solitary node cannot independently confirm a new grant in that protocol. It can refuse or serve a read whose contract permits stale data. Continuing one global order costs write availability on the isolated side. An ordinary asynchronous database copy does not become a consensus protocol by adding another replica.

The CAP theorem describes a choice during a network partition. An isolated node cannot always complete every valid operation successfully while maintaining the behavior of one current copy. Here the desired consistency is linearizability: completed operations fit one order that respects real-time precedence. Choose a contract per operation. Map reads and last-space writes can have different contracts.

Reason from the driver's timeline

A, B and C are voting nodes. Ada receives a successful grant after the current leader A commits it with B. A becomes isolated. B and C can elect a valid new leader under Raft's election rules. A may still think it leads, but it cannot commit another shared grant on its own. A driver reaching only A might therefore time out even though another driver can use B.

In a fresh run, isolate C before Ada makes her reservation. Move Ben's read until after Ada receives confirmation from A. If Ben asks C for the latest committed inventory and sees the original free space, that history violates the real-time ordering promise in this one-space example. A map read explicitly allowed to be stale can return the very same value within its age limit. Check the operation's contract before calling either result correct.

First decide who can get a vote

A is unreachable. C wants to lead in election term 4 and can vote for itself. It still needs B. B’s last stored entry is from term 3 at position 8. C’s last entry is from term 2 at position 9. C has more entries. Should B vote for C?

Raft compares the terms of the two last entries first. Only if they match does it compare positions. The election term on the request and the term on the candidate’s last stored entry are two different numbers. Starting election 4 does not turn C’s term-2 entry into a term-4 entry.

Run B’s decision on three possible histories for C. Each row is an independent case. B has not voted in term 4, the request is for that term, and both nodes are voters. Predict the first row, then ask what changes between the second and third.

WITH voter(last_term, last_position) AS (VALUES (3, 8)),
candidate(example, last_term, last_position) AS (
  VALUES ('1. Longer, older term', 2, 9),
         ('2. Same term, shorter', 3, 7),
         ('3. Same term, tied', 3, 8)
)
SELECT example, candidate.last_term, candidate.last_position,
       CASE WHEN (candidate.last_term, candidate.last_position)
                  >= (voter.last_term, voter.last_position)
            THEN 'grant vote' ELSE 'deny vote' END AS b_decides
FROM candidate CROSS JOIN voter
ORDER BY example;

B denies the first request because term 2 is older than term 3. In the second row the terms tie but position 7 is behind 8. In the third row both numbers tie, so B can grant its vote. To test which number wins, change only the first candidate’s position from 9 to 90. B still denies it. Now restore 9 and change its last term from 2 to 3. B grants the vote. The order of this comparison is the same pair comparison you used for the history cursor in puzzle 05.

This code isolates the log comparison in Raft section 5.4.1. In the real protocol a voter also checks the request term and whether it has already voted. A vote helps elect a leader. The next puzzle within this lesson asks what an elected leader may tell a driver about one entry.

Then decide what the leader can commit

A term can end without a leader being elected. Consider an elected leader in term 4 with voters A, B and C. Its log positions 1 through 8 match on A and B. Position 8 was written in term 3. May the new leader mark position 8 committed just by counting those copies?

def can_advance(index, entry_term, leader_term, matched_through):
    majority = len(matched_through) // 2 + 1
    copies = sum(position >= index for position in matched_through)
    return entry_term == leader_term and copies >= majority

print(can_advance(8, 3, 4, [8, 8, 6]))
print(can_advance(9, 4, 4, [9, 8, 6]))
print(can_advance(9, 4, 4, [9, 9, 6]))

Each list entry gives the last log position known to match on one voter. Run with Python 3. The lines read False, False, True. In the last case the current-term entry at 9 can advance the commit position. The preceding entries in the leader's log, including 8, become committed with it. Counting replicas of the older entry directly would discard a condition on which Raft's safety argument depends.

Change only the final list to five positions: 9, 9, 8, 8, 6. Two copies at 9 no longer suffice. This function isolates one rule for an established leader with a fixed voting group and a candidate position beyond the current commit position. A deployable protocol also needs leader election, durable logs, matching prefixes and recovery. See sections 5.3 and 5.4.2 of the Raft paper.

Try it

Compare two write acknowledgements across a real PostgreSQL promotion

Trace what a driver sees on each side. Compare refusal with the preallocated local rights from the previous lesson. Repeat with five nodes: three mutually reachable survivors can form a majority. After reconnection, inspect the entire history of confirmations, not only the final counter.

Check yourself

How many form a majority of five?

Not quite. Two groups of two need not intersect. Re-read that part ↑

Right. Two groups of two need not intersect.

What can the isolated node safely do here?

Right. One node does not form a majority of three.

Not quite. One node does not form a majority of three. Re-read that part ↑

What else protects the history besides voting counts?

Right. Client time does not establish a valid log.

Not quite. Client time does not establish a valid log. Re-read that part ↑

Sources

What you now know

During a split, the minority cannot safely keep accepting globally ordered grants on its own.

A booking is one decision. What changes when a separate payment provider controls the charge?