SD9.3 · LESSON 3 OF 6

Consensus and replicated logs

Explain consensus, logical ordering, leases and fencing under stated failure and timing assumptions.

THE IDEA

Consensus and replicated logs

Consensus protocols let a group agree on an ordered history of decisions despite failures. Raft splits the problem into leader election, log replication and safety rules. Storing an entry on a majority is part of the story but not all of it: terms stop old leaders, each server votes once per term, a candidate needs a log at least as up-to-date as the voter's, and a leader commits an entry by counting replicas only if it is from its own current term.

A term-3 leader and a 5-node group. Entries and their terms:

entry 1 (term 2): nodes storing it3entry 2 (term 2): nodes storing it3entry 3 (term 3): nodes storing it3

entry	term	on	majority (3)?	current term?
1	2	3/5	yes	no
2	2	3/5	yes	no
3	3	3/5	yes	yes

committed up to entry 3 a leader commits an entry by counting replicas only when it is from ITS OWN term; older entries become committed along with it election and replication rules (terms, one vote per term, up-to-date logs) are what make "stored on a majority" safe

Change how many nodes store each entry.

Predict first. Can ignoring term and election rules break a majority-based sketch?

Chapter context

Coordination lets multiple processes agree on selected shared decisions even though messages can be delayed or lost and participants can stop. Agreement is achieved by a protocol, not by adding a shared timestamp or an informal majority rule.

TRY IT YOURSELF

Part 1. Do it hands-on

Apply the commit rule by hand, then write it with the voting rules.

A term-3 leader and a 5-node group. Entries and their terms:

entry 1 (term 2): nodes storing it3entry 2 (term 2): nodes storing it3entry 3 (term 3): nodes storing it3

entry	term	on	majority (3)?	current term?
1	2	3/5	yes	no
2	2	3/5	yes	no
3	3	3/5	yes	yes

copies needed in a 5-node group term-2 entry on 3 nodes, term-3 leader: committed by counting? term-3 entry on 3 nodes? can ignoring terms break it? (yes/no)

To do: A 5-node Raft group: copies of an entry needed (a majority) before the leader may consider it committed?
To do: The leader is in term 3. An entry from term 2 sits on 3 of 5 nodes. Counting replicas alone, does the leader commit it directly? Type yes or no (the Raft rule: only entries from the current term are committed by counting)
To do: An entry from term 3 is stored on 3 of 5 nodes. Committed by the leader of term 3? Type yes or no
To do: Can ignoring term and election rules break a majority-based sketch? Type yes or no

Part 2. Do it in code

majority(n): ⌊n/2⌋ + 1.
can_commit(entry_term, replicated_on, n, leader_term): True only if the entry is stored on a majority AND was created in the leader's current term (the Raft rule that avoids committing old-term entries by counting alone).
commit_index(log_terms, replica_counts, n, leader_term): log_terms[i] is the term of entry i+1; replica_counts[i] how many nodes store it. Return the highest index (1-based) of an entry that can_commit; all earlier entries are then committed with it. 0 if none.
vote_granted(voter, candidate): voter = {"term", "voted_for", "last_term", "last_index"}; candidate = {"id", "term", "last_term", "last_index"}. Grant the vote only if candidate term >= voter term AND (the voter has not voted in this term, or voted for this candidate) AND the candidate's log is at least as up-to-date (higher last_term, or equal last_term and last_index >= the voter's).
wins_election(votes, n): True if votes >= majority(n).

def majority(n):
    pass

def can_commit(entry_term, replicated_on, n, leader_term):
    pass

def commit_index(log_terms, replica_counts, n, leader_term):
    pass

def vote_granted(voter, candidate):
    pass

def wins_election(votes, n):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can ignoring term and election rules break a majority-based sketch?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For a fixed n-member majority group, quorum size is $\lfloor n/2\rfloor+1$ . A 2f+1-member group can lose f members while retaining a majority, provided the remaining participants can communicate and the protocol's other assumptions hold. Fencing requires monotonically ordered tokens and enforcement at the resource.

Worked example

Five members require three votes, allowing two unavailable members while a communicating majority remains. Separately, a resource has already accepted token 8 from a new owner. An old owner's delayed operation bearing token 7 must be rejected, regardless of whether the old process still believes it owns the lease.

Reference code

The following example uses the Python standard library and does not call a remote service.

members=5
quorum=members//2+1
assert quorum == 3 and members-quorum == 2
highest=8
def accept(token):
    global highest
    if token < highest: return False
    highest=token
    return True
assert not accept(7)
assert accept(8)
assert accept(9)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A timeout cannot establish a remote process's state. Quorums require full protocol rules. Fencing is ineffective if the resource accepts stale tokens or an attacker can invent authorized tokens.