mateusz@systems ~/book/state-management $ cat section.md

State Management & Consensus

Managing state in distributed systems requires explicit failure semantics. Stateless handlers are generally easier to replace and scale when their dependencies have headroom. Stateful services require deliberate placement, durability, consistency, and recovery choices; some designs use replication and consensus, but not all do.

# Stateless vs Stateful Services

Stateless Services

A stateless service does not depend on instance-local state retained from earlier requests. It may read or write shared external state, and any healthy instance can handle a request without session affinity.

Request 1 GET /user/123 Request 2 GET /user/456 Any Web Server no instance-local session state Database source of truth Any healthy server can handle either request
Stateless web server — requests do not depend on session state retained by a particular instance. Any healthy instance can use the request and shared dependencies, such as the database, to respond, so later requests do not require session affinity.

Advantages:

  • Easier to route and scale: requests can go to any healthy instance, subject to shared bottlenecks and available headroom
  • Easier to replace: no instance-local session state must migrate, although external state still must persist
  • Less per-instance reconciliation: there is no local session copy to conflict, but shared backends retain their own consistency requirements

Potential examples when implemented without instance-local session state: REST-conforming API handlers, web frontends using self-contained tokens, CDN request handlers, and proxy servers.

Stateful Services

A stateful service depends on state retained across operations, whether stored locally or on attached storage. Authoritative or correctness-critical state must be durable or recoverable across failures; disposable cached state can be rebuilt.

Request: row 500 × Shard A rows 1-1000 Shard B rows 1001-2000 MUST serve row 500 doesn't have that data If Shard A fails, rows 1-1000 are unavailable (unless replicated)
Stateful database sharding — each server owns a disjoint range of rows. A request for row 500 can only be served by Shard A; Shard B has no path to that data. Because each shard is a single copy, losing Shard A makes rows 1-1000 unavailable unless the shard is replicated.

Challenges:

  • Scaling: may require partitioning, rebalancing, read replicas, caching, or scaling up rather than adding interchangeable handlers
  • Failure: requires a chosen durability and recovery model, such as replication, failover, reconstruction, or durable storage
  • Consistency: replicas need an explicit consistency and conflict model; some systems use consensus

Examples: Databases, caches (if used as source of truth), session stores, distributed locks, leader election services.

# Quorum and Split-Brain Scenarios

When a network partition occurs, how do you ensure only one group continues operating? Quorum solves this. Split-brain happens when quorum fails.

Quorum Basics

A quorum is the minimum number of nodes required to make decisions. Typically: majority (N/2 + 1).

A B C D E Normal operation — quorum = 3 of 5, all nodes online Network partition A B C Group 1 — 3 nodes, has quorum accepts writes D E Group 2 — 2 nodes, no quorum read-only / halted
Quorum in a 5-node cluster — normally all five nodes participate (quorum = 3). After a network partition splits them into a 3-node and a 2-node group, only the 3-node group has a majority and keeps accepting writes; the 2-node group goes read-only or halts. Because two groups can never both hold a majority, this prevents split-brain.

Why majority? Two groups can't both have majority. This prevents conflicting decisions.

Split-Brain Scenario

Split-brain occurs when a partition allows both sides to operate independently, creating conflicting state.

Primary A continues as primary Replica B promotes itself network partition Accepts write email = a@example.com Accepts write email = b@example.com Partition heals which email wins?
Split-brain with two nodes — without a quorum check, a network partition leaves Primary A and Replica B each unable to tell if the other is alive, so both promote themselves and keep accepting writes. Both update the same row (id 1) with different values; when the partition heals, the conflict must be resolved by hand. Fix: require a majority of 3+ nodes before promoting.

Prevention: Use quorum. With 3 nodes, only the side with 2+ nodes can elect a leader.

# Case Study: GitHub Cross-Region Failover (October 2018)

A 43-second interruption between GitHub's East Coast network hub and primary East Coast datacenter caused the East Orchestrator leader to deselect under Raft. West Coast and East Coast public-cloud Orchestrator nodes formed a quorum and began cross-region promotion. Brief unreplicated East writes followed by writes to the promoted West primaries produced divergent datasets; GitHub kept West canonical and rebuilt East.

The incident shows that a valid consensus quorum does not make every database promotion safe. Promotion boundaries must reflect application topology, old writers must be fenced, and the complete failover policy must be tested. See Notable Incidents & Lessons for the full chronology and recovery.

# Consensus Protocols (High-Level)

Consensus protocols help distributed systems agree on state despite failures and partitions.

Raft

Raft is a consensus algorithm designed to be understandable. Used in etcd, Consul, CockroachDB.

Key concepts:

  • Leader election: Cluster elects one leader. Only leader accepts writes.
  • Log replication: Leader appends entries to log, replicates to followers.
  • Quorum: Write is committed when majority of nodes acknowledge.
  • Leader failure: Followers detect timeout, start new election.
Client write Leader Follower Follower Follower Follower Replicate to 2+ followers (quorum reached) Commit write when majority confirms
Raft leader election and replication — one node is elected Leader; all client writes go to it. The Leader replicates each entry to its Followers and commits the write once a majority (quorum) of the cluster has acknowledged it.

Paxos

Paxos predates Raft. Chubby uses a Paxos-based replicated state machine, and Cassandra uses Paxos for lightweight transactions.

Key idea: Basic Paxos uses prepare/promise and accept/accepted exchanges to choose a value; learners then learn the chosen value. Replicated-log variants repeat and optimize that process, and production implementations remain non-trivial.

When to Use Consensus

Consensus is expensive (latency, coordination overhead). Use when you need:

  • Leader election (who's the primary?)
  • Configuration management (distribute config changes consistently)
  • Distributed locks (ensure only one process holds lock)
  • Strongly consistent metadata (file locations, shard assignments)

Avoid for: High-throughput data plane operations. Use consensus for control plane, not data plane.

# State Replication Strategies

Synchronous Replication

Write completes only after replicas acknowledge. Guarantees consistency but adds latency.

Client Write Primary receives write Replicate to all replicas (wait for ACK) All replicas confirm Return success to client Latency: max replica response time Consistency: strong (all replicas confirmed)
Synchronous replication — the primary waits for every replica to acknowledge before returning success. Latency is bounded by the slowest replica, but consistency is strong: a client never sees a successful write that isn't already durable on all replicas.

Asynchronous Replication

With asynchronous replication, the primary can acknowledge after its own commit without waiting for a replica; replicas receive or apply the change later. This reduces commit-path latency, but failover to a lagging replica can lose acknowledged transactions.

Client Write Primary receives write Return success to client (without waiting for a replica) Replicate to replicas (background, async) If failover selects a lagging replica: acknowledged transactions may be absent
Asynchronous replication — the primary returns success without waiting for replica confirmation. This reduces commit-path latency, but if recovery promotes a replica that has not received the transaction, an acknowledged write can be lost.

Semi-Synchronous Replication

In MySQL 8.4 semi-synchronous replication, the source waits until the configured number of replicas (one by default) acknowledge receiving and logging the transaction, then returns. The acknowledgement does not mean the replica has applied or committed the transaction.

Client Write Primary receives write Replicate to replicas Wait for configured replica ACKs (default: one; received and logged) Return success to client Other replicas continue on their own schedules
MySQL 8.4 semi-synchronous replication — the source waits for the configured number of replicas (one by default) to acknowledge that they received and logged the transaction. This adds at least network round-trip time relative to asynchronous replication; it does not mean a replica has applied the transaction or create a consensus quorum.

# Key Takeaways

  • Stateless handlers are often easier to replace and scale, but shared backends and workload bottlenecks still set limits
  • Stateful services require explicit placement, durability, consistency, and failure handling; replication or quorum may be appropriate for some designs
  • Quorum (majority) prevents split-brain—two groups can't both have majority
  • GitHub 2018: A valid Raft quorum initiated an unsafe cross-region promotion; quorum, topology-aware promotion, and writer fencing solve different parts of failover safety
  • Consensus protocols (Raft, Paxos) enable agreement despite failures, but add latency
  • Use consensus for control plane (leader election, config), not high-throughput data plane
  • Replication trade-offs: sync (consistent, slow), async (lower commit latency, possible loss on lagging-replica failover), semi-sync (implementation-specific acknowledgement trade-off)