mufassall

Cheat sheet · Data & storage

Consensus and leader election

15 min · Advanced · mufassall.dtwin.uz/en/l/consensus/

← Open the lesson

The problem

Two copies of a nightly payout job must agree which one runs it. Pinging each other fails, one lock server is a single point of failure. How a five-node cluster elects a leader, keeps a replicated log and avoids split brain by counting to a majority.

What you learn

  • Why two nodes cannot safely decide who is leader on their own
  • How a Raft-style cluster replicates a log and commits on a majority
  • What terms and votes do when the leader dies or is cut off
  • Why a lock still needs a fencing token, and where to keep it (etcd, ZooKeeper)
Final scene
30%

Diagram as code

The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.

Mermaid: flowchart

flowchart LR
  n_w1("Payout worker 1")
  n_w2("Payout worker 2")
  n_ledger[("Payouts DB")]
  n_n1["Node 1"]
  n_n2["Node 2"]
  n_n3["Node 3"]
  n_n4["Node 4"]
  n_n5["Node 5"]
  n_w1 --x n_ledger
  n_w2 --> n_ledger
  n_n2 --> n_n3
  n_n2 --> n_n4
  n_w1 --> n_n2
  n_n2 --> n_n1
  n_n2 --> n_n5
  classDef slow fill:#fff4d6,stroke:#b26a00,color:#3d2600
  class n_w1 slow

Mermaid: request sequence

sequenceDiagram
  participant n_w2 as Payout worker 2
  participant n_ledger as Payouts DB
  participant n_n1 as Node 1
  participant n_w1 as Payout worker 1
  participant n_n2 as Node 2
  participant n_n3 as Node 3
  Note over n_w2,n_ledger: Two workers, both think they are in charge
  n_w2->>n_ledger: INSERT INTO payouts (run, merchant, amount)
  n_ledger-->>n_w2: INSERT 0 312
  Note over n_w2,n_n1: Ask a third party: one lock server
  n_w2->>n_n1: POST /v1/locks/payouts HTTP/1.1
  n_n1-->>n_w2: HTTP/1.1 409 Conflict
  Note over n_w1,n_n1: The lock server is the new single point of failure
  n_w1-xn_n1: POST /v1/locks/payouts HTTP/1.1
  Note over n_n1,n_n2: Five nodes, one leader, one replicated log
  n_n1->>n_n2: AppendEntries n1 -#62; n2
  n_n2-->>n_n1: AppendEntries reply
  Note over n_w1,n_n1: A write is safe once a majority has it
  n_w1->>n_n1: POST /v1/locks/payouts HTTP/1.1
  n_n1-->>n_w1: HTTP/1.1 200 OK
  Note over n_w1,n_n1: The leader is cut off with one follower
  n_w1->>n_n1: POST /v1/locks/payouts HTTP/1.1
  n_n1-->>n_w1: HTTP/1.1 503 Service Unavailable
  Note over n_n2,n_n3: The majority side elects a new leader
  n_n2->>n_n3: RequestVote n2 -#62; n3
  n_n3-->>n_n2: RequestVote reply
  Note over n_n2,n_n1: The old leader comes back and steps down
  n_n2->>n_n1: INFO n1: AppendEntries with term 2 #62; my term 1
  Note over n_w1,n_ledger: A paused worker wakes up with an old lock
  n_w1->>n_ledger: UPDATE payout_runs SET fence = 42, status = 'running'
  n_ledger-->>n_w1: UPDATE 0

D2

direction: right

n_w1: "Payout worker 1" {
  shape: rectangle
  style.multiple: true
  style.fill: "#fff4d6"
  style.stroke: "#b26a00"
}
n_w2: "Payout worker 2" {
  shape: rectangle
  style.multiple: true
}
n_ledger: "Payouts DB" {
  shape: cylinder
}
n_n1: "Node 1" {
  shape: rectangle
}
n_n2: "Node 2" {
  shape: rectangle
}
n_n3: "Node 3" {
  shape: rectangle
}
n_n4: "Node 4" {
  shape: rectangle
}
n_n5: "Node 5" {
  shape: rectangle
}

n_w1 -> n_ledger {
  target-arrowhead.shape: cross
}
n_w2 -> n_ledger
n_n2 -> n_n3
n_n2 -> n_n4
n_w1 -> n_n2
n_n2 -> n_n1
n_n2 -> n_n5

PlantUML: request sequence

@startuml
participant "Payout worker 2" as n_w2
database "Payouts DB" as n_ledger
participant "Node 1" as n_n1
participant "Payout worker 1" as n_w1
participant "Node 2" as n_n2
participant "Node 3" as n_n3
note over n_w2, n_ledger : Two workers, both think they are in charge
n_w2 -> n_ledger : [duplicate] INSERT INTO payouts (run, merchant, amount)
n_ledger --> n_w2 : INSERT 0 312
note over n_w2, n_n1 : Ask a third party: one lock server
n_w2 -> n_n1 : POST /v1/locks/payouts HTTP/1.1
n_n1 --> n_w2 : HTTP/1.1 409 Conflict
note over n_w1, n_n1 : The lock server is the new single point of failure
n_w1 ->x n_n1 : [lost] POST /v1/locks/payouts HTTP/1.1
note over n_n1, n_n2 : Five nodes, one leader, one replicated log
n_n1 -> n_n2 : AppendEntries n1 -> n2
n_n2 --> n_n1 : AppendEntries reply
note over n_w1, n_n1 : A write is safe once a majority has it
n_w1 -> n_n1 : POST /v1/locks/payouts HTTP/1.1
n_n1 --> n_w1 : HTTP/1.1 200 OK
note over n_w1, n_n1 : The leader is cut off with one follower
n_w1 -> n_n1 : POST /v1/locks/payouts HTTP/1.1
n_n1 --> n_w1 : HTTP/1.1 503 Service Unavailable
note over n_n2, n_n3 : The majority side elects a new leader
n_n2 -> n_n3 : RequestVote n2 -> n3
n_n3 --> n_n2 : RequestVote reply
note over n_n2, n_n1 : The old leader comes back and steps down
n_n2 -> n_n1 : INFO n1: AppendEntries with term 2 > my term 1
note over n_w1, n_ledger : A paused worker wakes up with an old lock
n_w1 -> n_ledger : UPDATE payout_runs SET fence = 42, status = 'running'
n_ledger --> n_w1 : UPDATE 0
@enduml

PlantUML: components

@startuml
left to right direction
collections "Payout worker 1" as n_w1 #fff4d6;line:b26a00
collections "Payout worker 2" as n_w2
database "Payouts DB" as n_ledger
component "Node 1" as n_n1
component "Node 2" as n_n2
component "Node 3" as n_n3
component "Node 4" as n_n4
component "Node 5" as n_n5
n_w1 -[#c62828]-> n_ledger
n_w2 --> n_ledger
n_n2 --> n_n3
n_n2 --> n_n4
n_w1 --> n_n2
n_n2 --> n_n1
n_n2 --> n_n5
@enduml

Recap

Agreeing on a leader needs a majority, not a ping.

1) Run 3 or 5 nodes: they survive 1 or 2 failures. 2) A change is committed only when a majority stored it. 3) Terms and votes give at most one leader per term; a minority can never commit. 4) Locks carry a fencing token that the protected resource checks. Do not build this yourself: keep locks, leaders and config in etcd, ZooKeeper or Consul.

Numbers: at the start and at the end

MetricStartEnd
Paid twice48 000 $0 $
No lock available0 s0.4 s
Lock write time2 ms7 ms

Steps

  1. Problem Two workers, both think they are in charge

    The nightly payout job runs on two servers for safety.

  2. Fix Ask a third party: one lock server

    Now a separate lock server decides.

  3. Problem The lock server is the new single point of failure

    The lock server's disk fails.

  4. Fix Five nodes, one leader, one replicated log

    The lock service now runs on five nodes.

  5. Case A write is safe once a majority has it

    Worker 1 asks for the lock.

  6. Problem The leader is cut off with one follower

    A switch fails.

  7. Fix The majority side elects a new leader

    Nodes 2, 3 and 4 stop hearing from the leader.

  8. Case The old leader comes back and steps down

    The switch is replaced.

  9. Case A paused worker wakes up with an old lock

    Worker 1 freezes for 20 s in a long garbage-collection pause.

  10. Recap Recap

    Agreeing on a leader needs a majority, not a ping.

Terms

Consensus (Raft)
Several nodes agree on a leader and a shared log by majority vote. A change is committed once a majority stored it, and terms and votes allow at most one leader per term.
Fencing token
An increasing number handed out with every new lock. The protected resource remembers the highest number it has seen and rejects writes from a worker that wakes up with an old lock.