Distributed Systems Cheatsheet

CAP and consistency models, clocks, consensus, partitioning, replication, observability and system-design estimation. Each entry gives the problem, how it works, the real systems that use it, trade-offs and a Go sketch.

Updated: 2026-10-07

22 entries

Quick tables

Consistency models, quorum settings, latency numbers and estimation formulas to scan during design discussions and interviews.

Consistency model spectrum

From strongest to weakest. Stronger models cost latency and availability under partition.

Consistency model spectrum
ModelGuaranteeCostTypical systems
LinearizableEvery operation appears atomic at one point between its call and return; reads see the latest writeA quorum round trip per op; unavailable on the minority side of a partitionetcd, ZooKeeper (writes / sync), Spanner
SequentialAll nodes see operations in one total order that respects each client's program order (not real time)Cheaper than linearizable; reads may be staleZooKeeper reads, many replicated caches
CausalOperations that are causally related are seen in order everywhere; concurrent ones may differTrack dependencies (vector clocks / metadata)MongoDB causally consistent sessions, COPS / Eiger (research)
Session guaranteesRead-your-writes, monotonic reads, monotonic writes, writes-follow-reads for one clientSticky routing or version tokensAzure Cosmos DB session level, MongoDB client sessions
EventualIf writes stop, all replicas converge; no bound on whenLowest latency; clients may read stale or conflicting dataCassandra at ONE, DynamoDB default reads, DNS

Quorum (N / W / R) cheat table

W + R > N guarantees every read set overlaps the latest write set (given no sloppy quorum).

Quorum (N / W / R) cheat table
NWRW + R > NToleratesUse when
322yes1 node down for reads and writesDefault balanced setup
331yes0 down for writes, 2 for readsRead-heavy, rare writes
313yes2 down for writes, 0 for readsWrite-heavy, rare reads
311no2 downEventual consistency, lowest latency
533yes2 nodes downSame as Raft/Paxos majority on 5 nodes

Overlap alone does not give linearizability: concurrent writes, sloppy quorums and clock-based last-write-wins can still return stale data.

Back-of-the-envelope latency numbers

Orders of magnitude every engineer should know; scale by 10x either way for your hardware.

Back-of-the-envelope latency numbers
OperationLatencyRelative
L1 cache reference~0.5 ns
Main memory reference~100 ns200× L1
Compress 1 KB (Snappy)~3 µs
Send 1 KB over 1 Gbps network~10 µs
Random 4 KB read, SSD~150 µs~1,500× memory
Round trip inside one datacenter~0.5 ms
Read 1 MB sequentially from SSD~1 ms
HDD seek~10 ms
Read 1 MB sequentially from HDD~20 ms
Round trip across continents~150 ms300× in-DC

Design consequence: a quorum write across availability zones costs about one cross-zone round trip; across regions it costs 50–150 ms, which is why multi-region strong consistency is slow.

Capacity estimation formulas

The handful of formulas that answer most system-design estimation questions.

Capacity estimation formulas
QuantityFormulaExample
Average QPSrequests per day ÷ 86,400100 M/day ≈ 1,160 QPS
Peak QPSaverage QPS × 2–5 (use the peak/average ratio you measure)1,160 × 3 ≈ 3,500 QPS
Storage per yearwrites/day × bytes per record × 365 × replication factor10 M × 1 KB × 365 × 3 ≈ 11 TB
BandwidthQPS × payload size (× 8 for bits)3,500 × 10 KB ≈ 35 MB/s ≈ 280 Mbps
Cache sizedaily read data × 20% (hot set)500 GB/day → ~100 GB
Servers neededpeak QPS ÷ QPS per server, then add 30–50% headroom3,500 ÷ 500 → 7 → ~10
Read/write splitreads = QPS × read ratio; writes = QPS × (1 − read ratio)100:1 read-heavy → cache + replicas

Handy conversions & availability

Handy conversions & availability
ItemValue
Seconds per day86,400 ≈ 10⁵
1 M requests / day≈ 12 QPS
1 B requests / day≈ 11,600 QPS
2¹⁰ / 2²⁰ / 2³⁰ / 2⁴⁰1 KB / 1 MB / 1 GB / 1 TB (≈ 10³ steps)
99.9% availability8.76 hours downtime / year
99.99% availability52.6 minutes / year
99.999% availability5.26 minutes / year
UUID16 bytes binary, 36 bytes as text

Core theory

During a network partition you must choose consistency or availability; PACELC adds the latency-vs-consistency choice when there is no partition.

The problem

Replicated systems communicate over networks that drop and delay messages. CAP says what you must give up when that happens, so you can choose deliberately instead of discovering it during an outage.

How it works

  • C = linearizability (every read sees the latest write); A = every non-failing node answers every request; P = the system keeps working when the network splits nodes into groups.
  • Partitions are not optional in a real network, so the real choice is CP vs AP *during a partition*: refuse some requests (CP) or answer with possibly stale/divergent data (AP).
  • Without a partition you can have both C and A — CAP says nothing about normal operation.
  • PACELC: if Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Even with no partition, strong consistency costs a round trip to a quorum.
  • Classification is per-operation and tunable, not per-database: Cassandra at QUORUM behaves CP-ish, at ONE AP-ish.
  • CAP's “consistency” is not ACID's “consistency”, and “availability” is a stricter definition than uptime.

In real systems

  • etcd / ZooKeeper / Consul — CP / PC-EC: minority side of a partition cannot serve writes (or linearizable reads).
  • Cassandra / DynamoDB / Riak — AP / PA-EL by default: accept writes on both sides, reconcile later; tunable per query.
  • Spanner — CP (PC-EC) but engineered for very high availability with Paxos groups and TrueTime.
  • MongoDB — PA-EC by default: primary election pauses writes during partition; readConcern/writeConcern tune the trade-off.
  • Kafka — unclean.leader.election.enable=true picks availability over consistency; false (default) picks consistency.

Trade-offs

Pros

  • CP: no stale reads or divergent state, simpler application logic
  • AP: stays writable on both sides of a partition, lower latency

Cons

  • CP: minority partitions are unavailable; every write pays a quorum round trip
  • AP: applications must tolerate stale reads and resolve conflicts

ACID gives single-node transactional guarantees; BASE trades them for availability and scale with soft state and eventual consistency.

The problem

ACID transactions are easy to reason about but get expensive when data is spread over many nodes. BASE describes the relaxed contract that large-scale systems adopt to stay available and fast.

How it works

  • Atomicity: all or nothing (undo/redo log). Consistency: constraints hold before and after (an application-level invariant). Isolation: concurrent transactions behave as if serial (levels: read committed, repeatable read/snapshot, serializable). Durability: committed data survives crashes (WAL + fsync).
  • BASE = Basically Available, Soft state (state may change without input while replicas converge), Eventually consistent.
  • Not a binary choice: many systems offer ACID within a partition/shard and BASE across partitions.
  • Isolation anomalies to know: dirty read, non-repeatable read, phantom, lost update, write skew.
  • Making BASE safe: idempotent operations, versioned writes, compensations, and reading your own writes via sessions.

In real systems

  • PostgreSQL / MySQL InnoDB — Classic single-node ACID; Postgres default is read committed, MySQL InnoDB default is repeatable read.
  • Spanner / CockroachDB / TiDB — Distributed ACID with serializable (or snapshot) isolation via consensus plus 2PC.
  • Cassandra / DynamoDB — BASE by design; lightweight transactions (Paxos) / TransactWriteItems add scoped ACID.
  • Kafka — Transactions give atomic multi-partition writes and read-committed consumers, not general ACID.

Trade-offs

Pros

  • ACID: simple correctness model, fewer application bugs
  • BASE: higher availability, horizontal scale, lower latency

Cons

  • ACID: coordination cost, lower availability when distributed
  • BASE: anomalies leak into the application; needs idempotency and reconciliation

From linearizable to eventual: what each model promises readers, and what it costs in latency and availability.

The problem

“Consistent” means different things to different systems. A model is a contract: which values a read may return given the writes that happened before it. Pick the weakest model your application can tolerate.

How it works

  • Linearizable (strong): operations appear to take effect atomically at some instant between invocation and response, consistent with real time. Needs consensus or a single leader serving reads.
  • Sequential: one global order consistent with each client's own order, but not with real time.
  • Causal: if A could have influenced B, everyone sees A before B; concurrent operations may be seen in different orders. Tracked with vector clocks or dependency metadata.
  • Session guarantees: read-your-writes, monotonic reads, monotonic writes, writes-follow-reads — cheap and what most apps actually need.
  • Eventual: replicas converge when updates stop. Add convergence rules (LWW, CRDT merge) or you only get “eventually something”.
  • Distinguish from transaction isolation (serializable, snapshot): consistency models are about single objects/ops; isolation is about multi-object transactions. Strict serializability = serializable + linearizable.

Go sketch

Go
// Read-your-writes with a version token: the client remembers the log
// index of its last write and only reads from a replica that has applied it.
type Replica interface {
    AppliedIndex() uint64
    Read(key string) string
}

func ReadYourWrites(replicas []Replica, key string, lastWriteIndex uint64) (string, bool) {
    for _, r := range replicas {
        if r.AppliedIndex() >= lastWriteIndex {
            return r.Read(key), true
        }
    }
    return "", false // every replica is behind: fall back to the leader
}

In real systems

  • etcd / Consul — Linearizable reads by default (read index); `serializable` reads in etcd trade freshness for latency.
  • ZooKeeper — Writes are linearizable; reads are served by the connected server in per-client order and may be stale unless you call sync().
  • Cassandra — Consistency level per query (ONE … ALL); LWT for linearizable compare-and-set.
  • MongoDB — readConcern local/majority/linearizable and causally consistent sessions.
  • DynamoDB — Eventually consistent reads by default; ConsistentRead=true for strongly consistent reads in the same region.
  • Spanner — External consistency (strict serializability) using TrueTime commit wait.

Trade-offs

Pros

  • Stronger models: simplest application logic, fewer anomalies
  • Weaker models: lower latency, higher availability, offline-friendly

Cons

  • Stronger models: quorum round trips, unavailable on minority side of a partition
  • Weaker models: stale reads, conflicts and anomalies are the application's problem

Atomic updates across services or shards: 2PC blocks for strong atomicity, Saga and TCC trade isolation for availability.

The problem

One business operation (place an order, move money) updates data owned by several services or shards. A local ACID transaction cannot span them, so you need a protocol that makes the updates succeed together or be undone.

How it works

  • 2PC: the coordinator asks all participants to prepare (lock + durably log), and if all vote yes, tells them to commit; otherwise abort. Strong atomicity.
  • 2PC's flaw: after voting yes a participant is blocked holding locks until the coordinator returns. Mitigate by replicating the coordinator (Paxos/Raft) as Spanner does.
  • Saga: a sequence of local transactions, each with a compensating action run in reverse on failure. Orchestration (a central coordinator) vs choreography (events). No isolation — expose intermediate states or add semantic locks.
  • TCC (Try-Confirm-Cancel): Try reserves resources (freeze funds), Confirm commits the reservation, Cancel releases it. Application-level 2PC without long DB locks.
  • TCC pitfalls: idempotent Confirm/Cancel, empty rollback (Cancel arrives before Try), and suspension (Try arrives after Cancel) — record transaction state to reject late Try.
  • Transactional outbox: write the business change and an outgoing event in one local transaction, then publish reliably — avoids dual writes.
  • Always design steps to be idempotent and retriable; exactly-once is idempotency plus at-least-once delivery.

Go sketch

Go
import "context"

type Step struct {
    Name       string
    Do         func(ctx context.Context) error
    Compensate func(ctx context.Context) error // must be idempotent
}

// RunSaga runs the steps in order. When one fails, the steps that already
// succeeded are compensated in reverse order.
func RunSaga(ctx context.Context, steps []Step) error {
    for i, s := range steps {
        if err := s.Do(ctx); err != nil {
            for j := i - 1; j >= 0; j-- {
                // Production: persist progress and retry until it succeeds.
                _ = steps[j].Compensate(ctx)
            }
            return err
        }
    }
    return nil
}

In real systems

  • MySQL XA / PostgreSQL PREPARE TRANSACTION — 2PC primitives for cross-database transactions.
  • Spanner / CockroachDB / TiDB — 2PC across consensus groups, with the coordinator state replicated.
  • Seata — Java framework offering AT, TCC, Saga and XA modes.
  • Temporal / Cadence / AWS Step Functions — Durable workflow engines that implement saga orchestration.
  • Kafka + Debezium — Outbox pattern: CDC reads the outbox table and publishes events.

Trade-offs

Pros

  • 2PC: atomic and isolated, familiar semantics
  • Saga / TCC: no long locks, services stay autonomous, available under partial failure

Cons

  • 2PC: blocking, latency of two round trips, coordinator becomes critical
  • Saga / TCC: no isolation, compensation logic is hard to get right, more code per step

Clocks & ordering

A single counter that orders events consistently with causality without synchronized wall clocks.

The problem

Machine clocks drift and cannot be perfectly synchronized, so timestamps from different nodes cannot reliably order events. Lamport clocks order events by causality using only counters.

How it works

  • Each process keeps a counter L, starting at 0.
  • Local event or send: L = L + 1, and attach L to the message.
  • Receive a message with timestamp T: L = max(L, T) + 1.
  • Guarantee: if A happened-before B, then L(A) < L(B). The converse is false — L(A) < L(B) does not imply A caused B.
  • Total order: break ties by (L, process id); this is what distributed mutual exclusion and replicated state machines built on it use.

Go sketch

Go
import "sync"

type Lamport struct {
    mu sync.Mutex
    t  uint64
}

// Tick is called for a local event or before sending a message.
func (c *Lamport) Tick() uint64 {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.t++
    return c.t
}

// Observe is called when a message with timestamp remote arrives.
func (c *Lamport) Observe(remote uint64) uint64 {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.t = max(c.t, remote) + 1
    return c.t
}

In real systems

  • Lamport's mutual exclusion / replicated state machines — Requests are ordered by (timestamp, node id).
  • Raft term numbers — A logical clock for leadership epochs: higher term always wins.
  • ZooKeeper zxid — Epoch + counter totally orders all transactions.
  • Kafka leader epoch — Fences stale leaders and truncates divergent logs.

Trade-offs

Pros

  • Tiny: one integer per process, no clock synchronization
  • Gives a total order consistent with causality

Cons

  • Cannot tell concurrent events from causally related ones
  • Timestamps are not related to wall-clock time

One counter per node; comparing vectors tells you whether two events are ordered or concurrent, so conflicts can be detected.

The problem

Lamport clocks cannot say whether two events are causally related or concurrent. Replicas that accept concurrent writes need that distinction to detect conflicts instead of silently overwriting data.

How it works

  • Each node i keeps a vector V with one counter per node.
  • Local event / write at node i: V[i]++. Send: attach V.
  • Receive with vector W: V[k] = max(V[k], W[k]) for every k, then V[i]++.
  • Compare a and b: a ≤ b if every a[k] ≤ b[k]. If a ≤ b (and a ≠ b), a happened before b. If neither a ≤ b nor b ≤ a, the events are concurrent — a conflict.
  • Dynamo-style stores return all concurrent versions (siblings); the client merges and writes back with a vector that dominates both.
  • Vectors grow with the number of writers: prune old entries, or use dotted version vectors keyed by replica (not client) to bound size.

Go sketch

Go
type VectorClock map[string]uint64

type Order int

const (
    Before Order = iota
    After
    Equal
    Concurrent
)

// Tick records a local event on node.
func (v VectorClock) Tick(node string) { v[node]++ }

// Merge folds a received clock into v (call Tick afterwards).
func (v VectorClock) Merge(o VectorClock) {
    for k, n := range o {
        if n > v[k] {
            v[k] = n
        }
    }
}

// Compare reports how a relates to b.
func Compare(a, b VectorClock) Order {
    aAhead, bAhead := false, false
    for k, av := range a {
        if av > b[k] {
            aAhead = true
        }
    }
    for k, bv := range b {
        if bv > a[k] {
            bAhead = true
        }
    }
    switch {
    case aAhead && bAhead:
        return Concurrent
    case aAhead:
        return After
    case bAhead:
        return Before
    default:
        return Equal
    }
}

In real systems

  • Dynamo / Riak — Vector clocks (Riak: dotted version vectors) to surface sibling versions.
  • Voldemort — Versioned values with vector clocks and client-side reconciliation.
  • CouchDB — Revision trees detect conflicting document edits during replication.
  • Cassandra (contrast) — Deliberately avoids vector clocks; uses per-cell timestamps (LWW) for simplicity.

Trade-offs

Pros

  • Precisely detects concurrency, so no write is silently lost
  • Works without synchronized clocks

Cons

  • Metadata grows with the number of nodes/clients
  • Pushes conflict resolution to the application

Physical time plus a logical counter: timestamps stay close to wall-clock time yet never go backwards or violate causality.

The problem

Pure logical clocks are unrelated to real time (you cannot ask “what happened at 14:00?”), while wall clocks drift and can jump backwards. HLC keeps timestamps close to physical time yet monotonic and causally consistent.

How it works

  • A timestamp is (l, c): l = highest physical time this node has seen, c = logical counter for events within the same l.
  • Local / send: pt = now(); if pt > l then (l, c) = (pt, 0) else c++.
  • Receive (rl, rc): l' = max(l, rl, pt); c' = max(c, rc)+1 if l' equals both, c+1 if l' = l only, rc+1 if l' = rl only, else 0.
  • l never falls behind physical time and stays within the clock-skew bound of it, so timestamps remain meaningful and fit in 64 bits (48 bits ms + 16 bits counter).
  • Compared with TrueTime: HLC needs no special hardware but gives no uncertainty bound, so it cannot give external consistency without commit-wait tricks.
  • Keep NTP running and alert on skew; a node far ahead of the others drags everyone's l forward.

Go sketch

Go
import (
    "sync"
    "time"
)

type HLC struct {
    mu sync.Mutex
    l  int64  // highest physical time seen (ms)
    c  uint16 // logical counter within l
}

// Now stamps a local or send event.
func (h *HLC) Now() (int64, uint16) {
    h.mu.Lock()
    defer h.mu.Unlock()
    pt := time.Now().UnixMilli()
    if pt > h.l {
        h.l, h.c = pt, 0
    } else {
        h.c++
    }
    return h.l, h.c
}

// Observe merges a timestamp (rl, rc) received from another node.
func (h *HLC) Observe(rl int64, rc uint16) (int64, uint16) {
    h.mu.Lock()
    defer h.mu.Unlock()
    pt := time.Now().UnixMilli()
    next := max(h.l, rl, pt)
    switch {
    case next == h.l && next == rl:
        h.c = max(h.c, rc) + 1
    case next == h.l:
        h.c++
    case next == rl:
        h.c = rc + 1
    default:
        h.c = 0
    }
    h.l = next
    return h.l, h.c
}

In real systems

  • CockroachDB / YugabyteDB — HLC timestamps order MVCC versions and transactions; --max-offset (default 500 ms) bounds the read uncertainty interval, and a node whose clock drifts too far from its peers shuts itself down.
  • MongoDB — Cluster time is a hybrid of seconds and an increment, gossiped between nodes for causal consistency.
  • Spanner (contrast) — TrueTime exposes [earliest, latest] bounds from GPS/atomic clocks and waits out the uncertainty.
  • Kubernetes / etcd — Use revisions (logical counters) for ordering instead of wall-clock time.

Trade-offs

Pros

  • Human-meaningful timestamps that never go backwards
  • Causality preserved, fixed small size, no special hardware

Cons

  • Correctness of ordering depends on bounded clock skew
  • No uncertainty interval: weaker than TrueTime for external consistency

Consensus

Leader-based consensus: randomized-timeout election, log replication with majority commit, and snapshots to bound the log.

The problem

A replicated state machine needs every replica to apply the same commands in the same order, even as nodes crash and the network drops messages. Raft makes that understandable by splitting it into leader election, log replication and safety.

How it works

  • Roles: Follower, Candidate, Leader. Time is divided into terms; each term has at most one leader.
  • Election: a follower that hears no heartbeat within a randomized timeout (e.g. 150–300 ms) becomes a candidate, increments the term, votes for itself and asks for votes. A majority wins. Randomization avoids repeated split votes.
  • A node votes at most once per term, and only for a candidate whose log is at least as up to date (last log term, then last log index) — this is the election restriction that preserves committed entries.
  • Log replication: the leader appends a command, sends AppendEntries to followers (it doubles as the heartbeat), and an entry is committed once stored on a majority. The leader only directly commits entries from its own term.
  • Log Matching: AppendEntries carries (prevLogIndex, prevLogTerm); a follower that does not match rejects and the leader backs up until logs agree, then overwrites the divergent suffix.
  • Snapshots: each node periodically snapshots its state machine and discards the log prefix; InstallSnapshot brings far-behind followers up to date.
  • Membership changes: joint consensus, or one server at a time. Optimizations: PreVote (disrupted nodes do not inflate terms), ReadIndex / lease reads for linearizable reads without a log write.
  • Persist currentTerm, votedFor and the log before answering any RPC. Cluster of 2f+1 nodes tolerates f failures: 3 → 1, 5 → 2.

Go sketch

Go
import (
    "math/rand"
    "sync"
    "time"
)

type VoteRequest struct {
    Term         uint64
    CandidateID  string
    LastLogIndex uint64
    LastLogTerm  uint64
}

type VoteReply struct {
    Term    uint64
    Granted bool
}

type Node struct {
    mu           sync.Mutex
    currentTerm  uint64 // persist before replying
    votedFor     string // persist before replying
    lastLogIndex uint64
    lastLogTerm  uint64
    isFollower   bool
}

// HandleRequestVote implements the receiver side of RequestVote.
func (n *Node) HandleRequestVote(req VoteRequest) VoteReply {
    n.mu.Lock()
    defer n.mu.Unlock()

    if req.Term < n.currentTerm {
        return VoteReply{Term: n.currentTerm}
    }
    if req.Term > n.currentTerm { // newer term: step down and forget the old vote
        n.currentTerm, n.votedFor, n.isFollower = req.Term, "", true
    }
    upToDate := req.LastLogTerm > n.lastLogTerm ||
        (req.LastLogTerm == n.lastLogTerm && req.LastLogIndex >= n.lastLogIndex)
    if (n.votedFor == "" || n.votedFor == req.CandidateID) && upToDate {
        n.votedFor = req.CandidateID // also reset the election timer here
        return VoteReply{Term: n.currentTerm, Granted: true}
    }
    return VoteReply{Term: n.currentTerm}
}

// electionTimeout is randomized so nodes rarely time out together.
func electionTimeout() time.Duration {
    base := 150 * time.Millisecond
    return base + time.Duration(rand.Int63n(int64(base)))
}

In real systems

  • etcd — Raft stores all Kubernetes API server state; every write is a committed log entry, so latency tracks disk fsync and peer RTT. Defaults: 100 ms heartbeat, 1000 ms election timeout (the paper suggests 150–300 ms on a LAN); tune both to your RTT.
  • Consul / Nomad / Vault (integrated storage) — Raft for server state and leadership.
  • CockroachDB / TiKV / YugabyteDB — A Raft group per range/region, thousands of groups per cluster (Multi-Raft).
  • ClickHouse Keeper / Kafka KRaft — Raft-based replacements for ZooKeeper as the coordination / metadata quorum.
  • Redis (contrast) — Sentinel/Cluster use their own failure detection and async replication, not Raft — acknowledged writes can be lost.

Trade-offs

Pros

  • Understandable, with a strong leader and a precise spec; many production-grade libraries
  • Linearizable writes and no data loss for committed entries
  • Tolerates f failures of 2f+1 nodes

Cons

  • Every write goes through one leader and a majority round trip; throughput does not scale with nodes
  • Needs an odd, small cluster (3–7) and stable low-latency links; cross-region Raft is slow
  • Minority side of a partition is unavailable (CP); disk fsync latency dominates

Two-phase protocol (prepare/accept) that agrees on one value; Multi-Paxos keeps a stable leader to agree on a log cheaply.

The problem

Several nodes must agree on a single value even if proposers compete and nodes crash — and once chosen, the value must never change. Paxos is the foundational protocol that solves this with only a majority of acceptors alive.

How it works

  • Roles: proposers, acceptors, learners (often the same process). Every proposal has a unique, increasing number n.
  • Phase 1a/1b Prepare/Promise: proposer sends Prepare(n); an acceptor promises to ignore proposals numbered below n and replies with the highest-numbered proposal it already accepted, if any.
  • Phase 2a/2b Accept/Accepted: after promises from a majority, the proposer sends Accept(n, v), where v must be the value of the highest-numbered accepted proposal reported (else any value). Acceptors accept unless they promised a higher number.
  • A value is chosen once a majority of acceptors accept the same proposal; learners are told afterwards.
  • Safety comes from majorities overlapping: any later proposer sees the chosen value in at least one promise and must re-propose it.
  • Liveness is not guaranteed: two proposers can keep preempting each other (livelock) — elect a distinguished proposer or use randomized backoff.
  • Multi-Paxos: a stable leader runs Phase 1 once for many slots and then only Phase 2 per command, giving a replicated log; gaps are filled with no-ops. Raft is effectively a specialized Multi-Paxos with extra structure.

Go sketch

Go
import "sync"

type Promise struct {
    OK            bool
    AcceptedNum   uint64
    AcceptedValue []byte
}

// Acceptor is the single-decree Paxos acceptor. Persist its fields
// before replying to any message.
type Acceptor struct {
    mu            sync.Mutex
    promised      uint64 // highest proposal number promised
    acceptedNum   uint64
    acceptedValue []byte
}

func (a *Acceptor) Prepare(n uint64) Promise {
    a.mu.Lock()
    defer a.mu.Unlock()
    if n <= a.promised {
        return Promise{}
    }
    a.promised = n
    return Promise{OK: true, AcceptedNum: a.acceptedNum, AcceptedValue: a.acceptedValue}
}

// Accept succeeds unless a higher-numbered Prepare was already promised.
func (a *Acceptor) Accept(n uint64, v []byte) bool {
    a.mu.Lock()
    defer a.mu.Unlock()
    if n < a.promised {
        return false
    }
    a.promised, a.acceptedNum, a.acceptedValue = n, n, v
    return true
}

// Proposer rule: after a majority of promises, propose the value of the
// highest AcceptedNum among them; only if none, propose your own value.

In real systems

  • Google Chubby / Spanner — Chubby lock service; Spanner replicates each tablet with a Paxos group.
  • Cassandra — Lightweight transactions (IF NOT EXISTS / IF col = x) run single-decree Paxos per partition.
  • ZooKeeper (contrast) — ZooKeeper chose ZAB for primary-order guarantees instead of plain Multi-Paxos.
  • Megastore / Azure Storage — Paxos-family protocols behind replicated metadata or log layers.

Trade-offs

Pros

  • Proven safety under crashes, delays and message loss with only a majority alive
  • Flexible: many optimizations and variants (Fast, Flexible, EPaxos)

Cons

  • Notoriously hard to implement correctly; the paper leaves log, membership and leader details open
  • Basic Paxos needs two round trips per value; contention causes livelock
  • Minority partitions cannot make progress

Primary-backup atomic broadcast behind ZooKeeper: discovery, synchronization and broadcast phases give total-order delivery.

The problem

ZooKeeper clients need updates applied in the exact order the leader issued them, even across leader changes — a stronger requirement than agreeing on a log. ZAB (ZooKeeper Atomic Broadcast) provides total-order broadcast with primary-order guarantees.

How it works

  • A transaction id zxid = (epoch, counter): the 32-bit epoch identifies the leader generation, the 32-bit counter orders proposals within it.
  • Phase 0/1 Discovery: servers elect a prospective leader (Fast Leader Election prefers the highest zxid), which collects the latest history from a quorum and proposes a new epoch.
  • Phase 2 Synchronization: the new leader brings followers to its history using DIFF, TRUNC or SNAP, and only then is established as leader.
  • Phase 3 Broadcast: the leader sends PROPOSAL over FIFO (TCP) channels, followers log and ACK, and after a quorum of ACKs the leader sends COMMIT — similar to a 2PC without aborts.
  • Guarantees: updates from one primary are delivered in order, and a new primary delivers all transactions committed by previous primaries before its own.
  • Reads are served locally by any server (ordered per client, possibly stale); call sync() before a read to see the latest committed state. Observers add read capacity without joining the quorum.
  • Naming: the ZooKeeper internals documentation describes two phases, leader activation and active messaging; the Zab papers split the same flow into discovery, synchronization and broadcast.
  • Cluster sizing is the same as other majority protocols: 3 or 5 voting servers; keep the data directory and transaction log on separate disks.

Go sketch

Go
// zxid packs the leader epoch into the high 32 bits and a per-epoch
// counter into the low 32 bits, so comparing zxids compares history.
type Zxid uint64

func NewZxid(epoch, counter uint32) Zxid {
    return Zxid(epoch)<<32 | Zxid(counter)
}

func (z Zxid) Epoch() uint32   { return uint32(z >> 32) }
func (z Zxid) Counter() uint32 { return uint32(z) }

// Next is the zxid of the following proposal in the same epoch.
func (z Zxid) Next() Zxid { return NewZxid(z.Epoch(), z.Counter()+1) }

// A follower only logs a proposal that directly extends its history.
func (z Zxid) Extends(prev Zxid) bool {
    return z.Epoch() == prev.Epoch() && z.Counter() == prev.Counter()+1
}

In real systems

  • ZooKeeper — The znode tree, sessions, watches and ephemeral nodes all sit on top of ZAB.
  • Kafka (legacy) / HBase / Hadoop HDFS HA — Use ZooKeeper for controller election, region assignment and NameNode failover.
  • ClickHouse — ReplicatedMergeTree needs ZooKeeper or ClickHouse Keeper (Raft) for its replication log and part metadata.
  • Raft (contrast) — Newer systems pick Raft; the main behavioural difference is ZAB's explicit primary-order guarantee and synchronization phase.

Trade-offs

Pros

  • Strict primary-order delivery that suits coordination primitives (locks, config, election)
  • Cheap local reads; observers scale read-heavy workloads

Cons

  • All writes funnel through one leader; not meant for high write volume or large data
  • Reads are stale unless sync() is used
  • Less widely implemented than Raft — essentially only ZooKeeper

Data partitioning

Hash partitioning spreads load evenly but loses ordering; range partitioning keeps scans cheap but risks hot spots.

The problem

One node cannot hold or serve all the data, so keys must be split across shards. The partitioning function decides which queries stay cheap, how evenly load spreads, and how painful resharding is.

How it works

  • Hash partitioning: shard = hash(key) mod N (or hash → slot → shard). Uniform spread, but neighbouring keys scatter, so range scans hit every shard.
  • Range partitioning: sorted key space cut at split points. Range scans and prefix queries touch few shards; monotonic keys (timestamps, auto-increment ids) pile onto the last shard.
  • Hybrid: hash a prefix for spread, keep the rest sorted within the shard (Cassandra partition key + clustering key, DynamoDB partition + sort key).
  • Resharding: mod-N moves almost every key; fixed slots (Redis 16384), consistent hashing or range splits move only part of the data.
  • Hot keys are a separate problem: one celebrity key overloads one shard under either scheme — add key salting, caching or per-key replicas.

Go sketch

Go
import (
    "hash/fnv"
    "sort"
)

// Hash partitioning: even spread, but no range scans.
func hashPartition(key string, shards int) int {
    h := fnv.New32a()
    h.Write([]byte(key))
    return int(h.Sum32() % uint32(shards))
}

// Range partitioning: bounds[i] is the exclusive upper bound of shard i;
// the last shard is open-ended. Keys in [a, b) land on adjacent shards.
func rangePartition(key string, bounds []string) int {
    return sort.Search(len(bounds), func(i int) bool { return key < bounds[i] })
}

In real systems

  • Cassandra — Murmur3 hash of the partition key; clustering columns sort rows inside a partition.
  • Redis Cluster — CRC16(key) mod 16384 selects a slot; slots are assigned to nodes.
  • Kafka — Default producer partitioner hashes the key to pick a partition (ordering holds per key).
  • ClickHouse — Distributed tables route rows by a sharding_key expression, e.g. cityHash64(user_id) % shard weight.
  • HBase / TiKV / CockroachDB / Spanner — Range partitioning: regions / ranges split automatically as they grow.

Trade-offs

Pros

  • Hash: even load, simple routing, no manual split points
  • Range: efficient range scans, ordered iteration, natural data locality

Cons

  • Hash: range queries become scatter-gather; mod-N resharding is expensive
  • Range: hot spots on monotonic keys; needs split/merge machinery and a metadata service

Map keys and nodes onto a ring so adding or removing a node only remaps about k/n keys, instead of nearly all of them.

The problem

With hash(key) mod N, adding or removing a node changes N and remaps almost every key, causing a cache stampede or a massive data shuffle. Consistent hashing limits the movement to the keys next to the changed node: about k/n of k keys over n nodes.

How it works

  • Hash ring: map both keys and nodes into the space [0, 2^32) and treat it as a ring.
  • Lookup: hash the key, walk clockwise to the first node position (binary search over sorted positions, wrap at the end).
  • Add a node: it takes over only the arc between its predecessor and itself; remove a node: its arc moves to the next node clockwise.
  • Virtual nodes: place each physical node at 100–200 positions so the arcs even out (see Virtual Nodes).
  • Replication on the ring: store a key on the next R distinct physical nodes clockwise (skip positions owned by the same machine).
  • Alternatives: rendezvous (HRW) hashing needs no ring, Jump Consistent Hash needs no memory but only supports numbered, append-only buckets.

Go sketch

Go
import (
    "hash/crc32"
    "sort"
    "strconv"
)

type Ring struct {
    replicas int               // virtual nodes per physical node
    hashes   []uint32          // sorted positions on the ring
    owner    map[uint32]string // position -> node
}

func NewRing(replicas int) *Ring {
    return &Ring{replicas: replicas, owner: map[uint32]string{}}
}

func (r *Ring) Add(node string) {
    for i := 0; i < r.replicas; i++ {
        h := crc32.ChecksumIEEE([]byte(node + "#" + strconv.Itoa(i)))
        r.hashes = append(r.hashes, h)
        r.owner[h] = node
    }
    sort.Slice(r.hashes, func(a, b int) bool { return r.hashes[a] < r.hashes[b] })
}

func (r *Ring) Remove(node string) {
    kept := r.hashes[:0]
    for _, h := range r.hashes {
        if r.owner[h] == node {
            delete(r.owner, h)
            continue
        }
        kept = append(kept, h)
    }
    r.hashes = kept
}

// Get returns the first node clockwise from hash(key).
func (r *Ring) Get(key string) string {
    if len(r.hashes) == 0 {
        return ""
    }
    h := crc32.ChecksumIEEE([]byte(key))
    i := sort.Search(len(r.hashes), func(i int) bool { return r.hashes[i] >= h })
    if i == len(r.hashes) {
        i = 0 // wrap around
    }
    return r.owner[r.hashes[i]]
}

In real systems

  • Redis Cluster — A variant: 16384 fixed hash slots assigned to nodes; resharding moves slots, not a ring.
  • Cassandra / DynamoDB — Token ring partitions data; vnodes (num_tokens) smooth the distribution.
  • Nginx — `hash $key consistent;` in an upstream block enables ketama consistent hashing (the docs cite compatibility with 160 points per server).
  • Envoy / HAProxy / Maglev — Ring-hash and Maglev load balancing keep a client pinned to the same backend.
  • memcached clients — Ketama is the classic way to shard a cache fleet without mass invalidation.

Trade-offs

Pros

  • Node changes move only ~k/n keys
  • Supports heterogeneous nodes via weights (more virtual nodes)
  • Clients can route without a central coordinator

Cons

  • More complex than mod-N; ring membership must be consistent across clients
  • Virtual nodes cost memory and lookup time (O(log V))
  • Distribution is statistically even, not strictly uniform; hot keys are not solved

Give each physical node many positions on the ring to smooth skew, weight heterogeneous machines and spread rebalancing load.

The problem

With one position per node, arc lengths on the ring vary a lot, so some nodes own 2–3x the keys of others; when a node dies, all its load lands on a single neighbour. Virtual nodes fix both.

How it works

  • Each physical node is hashed to many ring positions (vnodes / tokens), typically 100–256.
  • More vnodes → smaller variance: standard deviation of the share shrinks roughly like 1/√V.
  • When a node leaves, its vnodes' arcs are taken over by many different neighbours, spreading the rebalancing load.
  • Weighted capacity: give a node vnodes proportional to its CPU / disk (a 2x machine gets 2x vnodes).
  • Cassandra defaults to 16 tokens (num_tokens) in recent versions; older versions used 256 — fewer tokens speeds up repair and streaming.

Go sketch

Go
import (
    "fmt"
    "hash/crc32"
    "sort"
)

type point struct {
    hash uint32
    node string
}

// distribution counts how many of "keys" land on each node.
func distribution(nodes []string, vnodes, keys int) map[string]int {
    var ring []point
    for _, n := range nodes {
        for i := 0; i < vnodes; i++ {
            h := crc32.ChecksumIEEE([]byte(fmt.Sprintf("%s#%d", n, i)))
            ring = append(ring, point{hash: h, node: n})
        }
    }
    sort.Slice(ring, func(a, b int) bool { return ring[a].hash < ring[b].hash })

    counts := map[string]int{}
    for k := 0; k < keys; k++ {
        h := crc32.ChecksumIEEE([]byte(fmt.Sprintf("key-%d", k)))
        i := sort.Search(len(ring), func(i int) bool { return ring[i].hash >= h })
        counts[ring[i%len(ring)].node]++
    }
    return counts
}

// vnodes = 1   -> shares often differ by 2-3x
// vnodes = 150 -> every node within a few percent of 1/n

In real systems

  • Cassandra — num_tokens vnodes per node; token allocation algorithm balances ownership.
  • DynamoDB (Dynamo paper) — Strategy 3: Q/S equal-sized tokens per node, decoupling partitioning from placement.
  • Riak — Fixed ring of partitions (default 64) assigned to nodes as virtual nodes.
  • Nginx / ketama — Weight multiplies the number of points a server gets on the ring.

Trade-offs

Pros

  • Smooths data skew without changing the algorithm
  • Spreads rebalancing and failure load across many nodes
  • Easy weighting for heterogeneous hardware

Cons

  • Memory for V×n positions and O(log(V×n)) lookups
  • Too many vnodes slows streaming/repair and makes replica placement bookkeeping heavier
  • Still probabilistic: a small cluster can stay uneven unless tokens are allocated deliberately

Replication

One node accepts writes and streams its log to followers; sync vs async replication sets the durability/latency trade-off.

The problem

A single copy of the data is a single point of failure and a read bottleneck. Replicating from one leader keeps writes ordered and simple while followers add read capacity and standby copies.

How it works

  • The leader assigns every write a position in a replication log; followers apply the log in order.
  • Asynchronous: leader acknowledges immediately — lowest latency, but an acknowledged write can be lost on failover.
  • Synchronous / semi-synchronous: wait for at least one (or a quorum of) followers — no loss for acknowledged writes, higher latency, availability depends on followers.
  • Failover: detect leader failure by timeout, pick the most up-to-date follower, repoint clients, fence the old leader (split-brain!).
  • Replication lag breaks read-your-writes on followers: route a user's reads to the leader for a while after a write, or pass a log position (LSN/GTID) to the replica.
  • Log shipping formats: statement-based (non-deterministic functions bite), WAL/physical, logical row-based.

Go sketch

Go
import (
    "errors"
    "sync"
)

type Follower interface {
    Append(index uint64, entry []byte) error
}

type Leader struct {
    mu        sync.Mutex
    log       [][]byte
    followers []Follower
}

// Write appends locally, then waits for syncAcks followers.
// syncAcks = 0 is fully asynchronous; len(followers) is fully synchronous.
func (l *Leader) Write(entry []byte, syncAcks int) error {
    l.mu.Lock()
    l.log = append(l.log, entry)
    index := uint64(len(l.log))
    l.mu.Unlock()

    results := make(chan error, len(l.followers))
    for _, f := range l.followers {
        go func(f Follower) { results <- f.Append(index, entry) }(f)
    }

    acked, failed := 0, 0
    for acked < syncAcks {
        if failed > len(l.followers)-syncAcks {
            return errors.New("not enough followers acknowledged")
        }
        if err := <-results; err != nil {
            failed++
        } else {
            acked++
        }
    }
    return nil // the rest keep replicating in the background
}

In real systems

  • MySQL / PostgreSQL — Binlog / WAL streaming; semi-sync (MySQL) or synchronous_commit with synchronous_standby_names (Postgres).
  • Kafka — Each partition has one leader; followers in the ISR replicate it. acks=all + min.insync.replicas sets the durability bar.
  • Redis — Async replica replication; Sentinel promotes a replica on failure (run at least three, on independent machines: the quorum only detects the failure, a majority of Sentinels authorizes the failover, and acknowledged writes can still be lost). Persistence: RDB snapshots (compact, can lose minutes) vs AOF (everysec loses ~1 s; always is slow) — replication does not replace persistence.
  • Redis Cluster — Each shard is a leader with replicas; the cluster promotes a replica when the leader is voted failed by a majority of leaders.

Trade-offs

Pros

  • Simple mental model; single writer means no write conflicts
  • Read scaling and warm standbys
  • Mature tooling in every major database

Cons

  • Write throughput is capped by one node
  • Async replication loses data on failover; sync reduces availability
  • Failover is the hard part: split-brain, lagging replicas, client redirection

Several nodes accept writes and replicate to each other; you gain local write latency and must resolve write conflicts.

The problem

A single leader means every write travels to one place — slow for users in other regions, and unusable if that region is cut off. Multi-leader lets each region (or device) accept writes locally and replicate asynchronously.

How it works

  • Each leader accepts writes and ships them to the other leaders; every leader is also a follower of the rest.
  • Conflicts are inevitable when two leaders modify the same key concurrently — detect them with version vectors.
  • Resolution strategies: last-write-wins (simple, loses data), per-field merge, keep siblings and let the app merge, or CRDTs that merge automatically.
  • Avoid conflicts instead of resolving them: route all writes for one entity (user, document) to one home leader.
  • Topologies: all-to-all is robust; circular/star topologies are fragile and need loop prevention via replica ids on writes.
  • Hazards: auto-increment ids, unique constraints and triggers behave surprisingly across leaders.

Go sketch

Go
// Value is a last-write-wins register. Every replica applies Merge,
// so replicas converge no matter the order updates arrive in.
type Value struct {
    Data string
    TS   int64  // wall-clock or HLC timestamp
    Node string // tie-breaker so concurrent equal timestamps are deterministic
}

func Merge(a, b Value) Value {
    if a.TS != b.TS {
        if a.TS > b.TS {
            return a
        }
        return b
    }
    if a.Node > b.Node {
        return a
    }
    return b
}

In real systems

  • ClickHouse ReplicatedMergeTree — Any replica accepts INSERTs; ClickHouse Keeper (or ZooKeeper) coordinates the replication log and replicas fetch parts from each other.
  • Cassandra / DynamoDB global tables — Multi-region writes with last-writer-wins (timestamps) conflict resolution.
  • CouchDB / PouchDB — Offline-first sync between devices; conflicts kept as revisions.
  • Riak / Redis CRDB / Automerge — CRDT data types merge concurrent updates deterministically.
  • MySQL group replication, Galera — Multi-primary modes with certification-based conflict detection.

Trade-offs

Pros

  • Low write latency from the nearest leader
  • Writes survive a region or network partition
  • Offline operation (devices as leaders)

Cons

  • Write conflicts need a resolution policy; LWW silently drops writes
  • Weaker guarantees: no linearizability, constraints are hard
  • Operationally the most complex replication mode

Writes go to N replicas and succeed on W acks, reads query R; W + R > N makes read and write sets overlap.

The problem

Leader failover is slow and disruptive. Leaderless (Dynamo-style) systems let any replica take reads and writes, using quorums so that a few failed or slow nodes do not block the request.

How it works

  • N replicas hold each key; a write is sent to all N and succeeds after W acknowledge; a read asks R replicas.
  • If W + R > N, every read quorum overlaps every write quorum, so a read sees at least one up-to-date replica; it returns the highest version.
  • Tunable: R=1,W=N for fast reads; W=1,R=N for fast writes; W=R=⌈(N+1)/2⌉ balanced.
  • Read repair: the coordinator writes the newest value back to stale replicas it noticed.
  • Anti-entropy: background Merkle-tree comparison fixes replicas that are rarely read.
  • Sloppy quorum + hinted handoff: when home replicas are down, write to other nodes that hand data back later — higher availability, but the overlap guarantee is gone.
  • Version conflicts are detected with vector clocks / version vectors, or resolved by timestamps (LWW).

Go sketch

Go
import (
    "context"
    "errors"
)

type Versioned struct {
    Value   []byte
    Version uint64
}

type Replica interface {
    Get(ctx context.Context, key string) (Versioned, error)
    Put(ctx context.Context, key string, v Versioned) error
}

type reply struct {
    rep Replica
    v   Versioned
    err error
}

// QuorumRead queries every replica, returns once r answered, and
// repairs the stale replicas it saw (read repair).
func QuorumRead(ctx context.Context, replicas []Replica, key string, r int) (Versioned, error) {
    ch := make(chan reply, len(replicas))
    for _, rep := range replicas {
        go func(rep Replica) {
            v, err := rep.Get(ctx, key)
            ch <- reply{rep: rep, v: v, err: err}
        }(rep)
    }

    var got []reply
    for range replicas {
        if rp := <-ch; rp.err == nil {
            got = append(got, rp)
        }
        if len(got) >= r {
            break
        }
    }
    if len(got) < r {
        return Versioned{}, errors.New("quorum not reached")
    }

    newest := got[0].v
    for _, g := range got[1:] {
        if g.v.Version > newest.Version {
            newest = g.v
        }
    }
    for _, g := range got {
        if g.v.Version < newest.Version {
            go g.rep.Put(context.WithoutCancel(ctx), key, newest)
        }
    }
    return newest, nil
}

In real systems

  • Cassandra — Per-query consistency level: ONE, QUORUM, LOCAL_QUORUM, ALL; read repair, hinted handoff and nodetool repair (Merkle trees).
  • DynamoDB (Dynamo paper) — The origin: N, R, W configurable, vector clocks, sloppy quorum and hinted handoff.
  • Riak / Voldemort — Dynamo derivatives with tunable n_val / r / w and siblings.
  • etcd / ZooKeeper (contrast) — Majority quorum inside a consensus protocol with a leader — gives linearizable writes, which leaderless quorums do not.

Trade-offs

Pros

  • No failover: tolerates node failures and slow nodes transparently
  • Tunable consistency/latency per request
  • Scales writes across all replicas

Cons

  • Not linearizable even with W + R > N (concurrent writes, clock skew in LWW, sloppy quorums)
  • Needs conflict resolution and repair machinery
  • Higher read/write amplification: every op touches several nodes

Observability

Propagate a trace context across services so one request becomes a tree of spans with timings you can inspect.

The problem

One user request fans out across dozens of services. Metrics say something is slow and logs are scattered; tracing reconstructs the path of a single request with timings so you can see which hop is responsible.

How it works

  • Trace = the whole request, identified by a 128-bit trace id. Span = one unit of work (an RPC, a DB query) with id, parent id, name, start/end time, attributes and events.
  • Context propagation: pass trace id + parent span id in headers across process boundaries — W3C `traceparent: 00-<trace-id>-<span-id>-<flags>` — and in `context.Context` inside a process.
  • Instrument at boundaries (HTTP/gRPC server and client, DB driver, message producer/consumer); for async messaging, put the context in message headers and link spans instead of parent-child.
  • Sampling: head-based (decide at the root, e.g. 1 %) is cheap; tail-based (decide after the trace finishes, keep errors and slow traces) is more useful but needs a collector buffering whole traces.
  • Keep attributes low-cardinality and free of PII; use semantic conventions (http.request.method, db.system, ...).
  • Correlate: put trace_id in every log line, and attach exemplars to latency histograms to jump from a slow bucket to a trace.

Go sketch

Go
import (
    "crypto/rand"
    "encoding/hex"
    "fmt"
    "net/http"
    "strings"
)

type SpanContext struct {
    TraceID  string // 32 hex chars, shared by the whole request
    SpanID   string // 16 hex chars, unique per span
    ParentID string
    Sampled  bool
}

func newID(n int) string {
    b := make([]byte, n)
    _, _ = rand.Read(b)
    return hex.EncodeToString(b)
}

// Inject writes the W3C traceparent header: version-traceid-spanid-flags.
func Inject(h http.Header, sc SpanContext) {
    flags := "00"
    if sc.Sampled {
        flags = "01"
    }
    h.Set("traceparent", fmt.Sprintf("00-%s-%s-%s", sc.TraceID, sc.SpanID, flags))
}

// Extract continues the caller's trace with a fresh child span,
// or starts a new trace when the header is missing or malformed.
func Extract(h http.Header) SpanContext {
    parts := strings.Split(h.Get("traceparent"), "-")
    if len(parts) != 4 || len(parts[1]) != 32 || len(parts[2]) != 16 {
        return SpanContext{TraceID: newID(16), SpanID: newID(8), Sampled: true}
    }
    return SpanContext{
        TraceID:  parts[1],
        SpanID:   newID(8),
        ParentID: parts[2],
        Sampled:  parts[3] == "01",
    }
}

In real systems

  • OpenTelemetry — Vendor-neutral APIs/SDKs plus the Collector; OTLP is the wire protocol.
  • Jaeger / Grafana Tempo / Zipkin — Trace backends; Tempo stores traces cheaply in object storage and queries by trace id.
  • Kafka — Producers inject context into record headers; consumers continue the trace (OTel instrumentation).
  • Istio / Envoy service mesh — Sidecars emit spans automatically, but the app must still propagate headers between inbound and outbound calls.
  • Kubernetes — API server and etcd emit spans (OTel) for control-plane request tracing.

Trade-offs

Pros

  • Pinpoints the slow or failing hop across services
  • Reveals real dependency graphs and fan-out

Cons

  • Needs consistent propagation everywhere — one broken hop splits the trace
  • Overhead and storage cost; sampling hides rare cases unless tail-based
  • Instrumentation and attribute hygiene take ongoing effort

RED (rate, errors, duration) for request-driven services; USE (utilization, saturation, errors) for resources.

The problem

A system can emit thousands of metrics, and nobody knows which to look at during an incident. RED and USE are small, systematic checklists: RED for what users experience, USE for what the machine is doing.

How it works

  • RED for every request-driven service: Rate (requests/s), Errors (failed requests/s or ratio), Duration (latency distribution, not the average).
  • USE for every resource (CPU, memory, disk, NIC, thread pool, connection pool, queue): Utilization (% busy), Saturation (queued/waiting work), Errors.
  • Google's four golden signals = latency, traffic, errors, saturation — RED plus saturation.
  • Latency: record histograms and alert on p95/p99, split successful vs failed requests (a fast error hides slowness).
  • Percentiles cannot be averaged across instances; aggregate histogram buckets, then compute quantiles (histogram_quantile).
  • SLI/SLO: define the SLI (e.g. share of requests under 300 ms and non-5xx), set an SLO (99.9 %), alert on error-budget burn rate rather than raw thresholds.
  • Cardinality: labels multiply series; never put user id, URL with ids, or trace id into metric labels.

Go sketch

Go
import (
    "net/http"
    "sync/atomic"
    "time"
)

type statusWriter struct {
    http.ResponseWriter
    status int
}

func (w *statusWriter) WriteHeader(code int) {
    w.status = code
    w.ResponseWriter.WriteHeader(code)
}

// Upper bounds of the latency buckets; the last bucket is +Inf.
var bounds = [...]time.Duration{
    5 * time.Millisecond, 10 * time.Millisecond, 25 * time.Millisecond,
    50 * time.Millisecond, 100 * time.Millisecond, 250 * time.Millisecond,
    500 * time.Millisecond, time.Second,
}

// RED holds Rate, Errors and Duration for one service.
type RED struct {
    Requests atomic.Uint64
    Errors   atomic.Uint64
    Buckets  [len(bounds) + 1]atomic.Uint64
}

func (m *RED) Wrap(next http.Handler) http.Handler {
    return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        start := time.Now()
        sw := &statusWriter{ResponseWriter: w, status: http.StatusOK}
        next.ServeHTTP(sw, r)

        m.Requests.Add(1)
        if sw.status >= 500 {
            m.Errors.Add(1)
        }
        d, i := time.Since(start), 0
        for i < len(bounds) && d > bounds[i] {
            i++
        }
        m.Buckets[i].Add(1)
    })
}

In real systems

  • Prometheus + Grafana — Counters for rate/errors, histograms for duration; rate() and histogram_quantile() queries.
  • Kafka — RED on producers/consumers; USE on brokers; consumer lag (saturation) is the key alert.
  • ClickHouse — system.query_log / system.metrics: query duration and errors (RED), merges and parts count (saturation).
  • Redis — Ops/s and latency (RED); used_memory vs maxmemory, evicted_keys, connected_clients, replication offset lag (USE).
  • Kubernetes — kube-state-metrics + cAdvisor for utilization and saturation (CPU throttling, OOMKills, pending pods).

Trade-offs

Pros

  • Small, uniform checklist: dashboards and alerts look the same for every service
  • Symptom-based alerts (RED) page on user impact, cause-based (USE) help diagnose

Cons

  • RED/USE tell you *that* and roughly *where*, not *why* — you still need traces and logs
  • Histograms need sensible buckets; percentiles are approximate
  • High-cardinality labels can take down the metrics backend

Emit key-value JSON with trace ids, stable field names and bounded cardinality so logs can be queried and joined with traces.

The problem

Free-text logs are written for humans and cannot be filtered, aggregated or joined across services. Structured logs are events with named fields, so a machine can answer “all errors for order 42 in the last 10 minutes”.

How it works

  • One event per line, JSON (or logfmt) with a stable schema: timestamp (UTC, RFC 3339), level, message, service, version, env.
  • Messages are constant strings; variable data goes into fields (`msg="order placed" order_id=42`), never interpolated into the message.
  • Always include trace_id / span_id and a request or correlation id so logs join with traces and across services.
  • Levels: ERROR = needs action, WARN = unexpected but handled, INFO = business and lifecycle events, DEBUG = off by default. Don't log and rethrow: log once at the boundary that handles the error.
  • Control cardinality and volume: sample noisy debug logs, avoid logging in hot loops, bound field size; log errors with stack/cause chain.
  • Never log secrets, tokens, full payloads or PII; redact at the logger, not at call sites.
  • Write to stdout/stderr and let the platform (container runtime, Fluent Bit, Vector) ship them; the app does not manage files or retries.

Go sketch

Go
import (
    "context"
    "log/slog"
    "os"
)

type ctxKey struct{}

func WithLogger(ctx context.Context, l *slog.Logger) context.Context {
    return context.WithValue(ctx, ctxKey{}, l)
}

func FromContext(ctx context.Context) *slog.Logger {
    if l, ok := ctx.Value(ctxKey{}).(*slog.Logger); ok {
        return l
    }
    return slog.Default()
}

func handleOrder(ctx context.Context, traceID string) {
    base := slog.New(slog.NewJSONHandler(os.Stdout, &slog.HandlerOptions{
        Level: slog.LevelInfo,
    }))
    logger := base.With("service", "checkout", "trace_id", traceID)
    ctx = WithLogger(ctx, logger)

    // Constant message, variable data in fields.
    FromContext(ctx).Info("order placed",
        "order_id", 42, "amount_cents", 1999, "duration_ms", 37)
}

In real systems

  • Go log/slog — Standard-library structured logging with JSON and text handlers, With() for shared fields and context-aware logging.
  • Loki / Elasticsearch / ClickHouse — Log stores: Loki indexes labels only; ClickHouse-based stacks (SigNoz, Uptrace) store logs as columns for fast aggregation.
  • Kubernetes — Containers log to stdout; the node agent (Fluent Bit / Vector / OTel Collector) adds pod, namespace and labels.
  • OpenTelemetry Logs — Log records carry trace and span ids so a log line links to its trace.

Trade-offs

Pros

  • Queryable, aggregatable and joinable with traces and metrics
  • Stable schemas make alerts and dashboards on logs reliable

Cons

  • Less readable raw; needs tooling (jq, a log UI) to read comfortably
  • Field names become an API: renames break queries
  • Verbose logs cost storage and ingestion money; high-cardinality fields hurt some backends

System design

Partitioned log, consumer groups and offsets, delivery semantics, ordering, backpressure and dead-letter handling.

The problem

Services need to hand work to each other without waiting, absorb traffic spikes, and survive consumer downtime. A message queue or log decouples producers from consumers — and brings its own questions about ordering, delivery guarantees and backpressure.

How it works

  • Partitioned log: a topic is split into partitions, each an append-only, replicated log. Order is guaranteed only within a partition; choose the partition key (e.g. order id) to keep related messages together.
  • Consumer groups: each partition is assigned to exactly one consumer in a group, so parallelism ≤ partition count; different groups read the same data independently.
  • Offsets: a consumer tracks its position per partition and commits it. Commit before processing → at-most-once; after processing → at-least-once; atomically with the side effect → effectively once.
  • Exactly-once inside Kafka = idempotent producer + transactions + read_committed consumers. Anything touching an external system still needs an idempotent sink (dedup key, upsert).
  • Durability: replication factor 3, acks=all, min.insync.replicas=2 — a produce succeeds only when enough replicas have it.
  • Backpressure: pull-based consumers set their own pace; watch consumer lag; bound in-flight work; scale consumers up to the partition count.
  • Failures: retry with exponential backoff, then route poison messages to a dead-letter queue/topic; keep messages small and idempotent.
  • Rebalances pause consumption: use cooperative-sticky assignment and static membership to limit disruption.
  • Sizing: partitions ≈ max(target throughput ÷ per-partition producer throughput, target throughput ÷ per-consumer throughput); don't over-partition (more files, longer failover).

Go sketch

Go
import "context"

type Message struct {
    ID        string // business or producer-assigned unique id
    Partition int
    Offset    int64
    Key       []byte
    Value     []byte
}

type Consumer interface {
    Poll(ctx context.Context) ([]Message, error)
    Commit(msgs ...Message) error
}

// Consume gives at-least-once delivery. Combined with an idempotent handler
// (ideally the dedup record is written in the same DB transaction as the
// side effect) the result is effectively once.
func Consume(ctx context.Context, c Consumer, seen map[string]struct{}, handle func(Message) error) error {
    for ctx.Err() == nil {
        msgs, err := c.Poll(ctx)
        if err != nil {
            return err
        }
        for _, m := range msgs {
            if _, dup := seen[m.ID]; dup {
                continue // redelivered after a crash or rebalance
            }
            if err := handle(m); err != nil {
                return err // not committed, so it will be redelivered
            }
            seen[m.ID] = struct{}{}
        }
        if err := c.Commit(msgs...); err != nil { // commit AFTER processing
            return err
        }
    }
    return ctx.Err()
}

In real systems

  • Kafka — Partitioned replicated log, consumer groups, offsets in __consumer_offsets, transactions, log compaction, KRaft metadata quorum.
  • RabbitMQ — Broker queue model: per-message acks, prefetch for backpressure, dead-letter exchanges; classic queues delete on ack, streams are log-like.
  • Pulsar — Separates serving (brokers) from storage (BookKeeper); subscriptions can be shared, failover or key-shared.
  • AWS SQS — At-least-once standard queues, FIFO queues with message groups; visibility timeout instead of offsets.
  • Redis Streams — Append-only log with consumer groups and pending-entries list for ack/claim; limited by memory and async replication.

Trade-offs

Pros

  • Decouples teams and failure domains; absorbs bursts
  • Replayable log supports new consumers, reprocessing and audit
  • Scales horizontally by partitions

Cons

  • Ordering only per partition; hot keys unbalance partitions
  • At-least-once means duplicates: consumers must be idempotent
  • Operational weight: rebalances, lag monitoring, partition planning, schema evolution

Leases with fencing tokens: a lock without a monotonic token cannot be made safe against pauses and clock jumps.

The problem

Several processes must not run the same critical section at once (a cron job, a leader duty, an exclusive write). A lock that lives on one machine does not work, and a naive timeout-based one is unsafe: a paused process can wake up believing it still holds the lock.

How it works

  • Lock = a lease: acquiring it gives exclusive ownership for a TTL; the holder renews it while alive, and it expires if the holder dies.
  • Failure mode: GC pause, VM freeze or network delay → lease expires → another client acquires → the first resumes and writes. Clock jumps cause the same.
  • Fencing token: the lock service hands out a monotonically increasing number with each acquisition; the protected resource rejects any request carrying a token lower than the highest it has seen. This is what makes the lock actually safe.
  • Redis single node: `SET key <random-token> NX PX <ttl>`; release with a Lua script that deletes only if the value still equals your token. No fencing token, so only suitable when correctness is not at stake (efficiency locks).
  • Redlock (N independent Redis nodes) relies on bounded clock drift and process pauses and gives no fencing token — criticised by Martin Kleppmann; avoid it for correctness-critical locks.
  • Consensus-backed locks (etcd lease + revision, ZooKeeper ephemeral sequential znodes, Consul sessions) are linearizable and expose a revision/zxid usable as a fencing token.
  • Prefer not needing a lock: idempotent operations, compare-and-set / optimistic version checks, or a single-writer partition.

Go sketch

Go
import (
    "context"
    "errors"
    "sync"
    "time"
)

var ErrStaleToken = errors.New("stale fencing token")

type Lease struct {
    Token   uint64 // strictly increasing across acquisitions
    Expires time.Time
}

type LockService interface {
    Acquire(ctx context.Context, name string, ttl time.Duration) (Lease, error)
    Release(ctx context.Context, name string, token uint64) error
}

// FencedStore is the protected resource: it remembers the highest token it
// has seen and rejects writers holding an older lease.
type FencedStore struct {
    mu      sync.Mutex
    highest uint64
    data    map[string][]byte
}

func (s *FencedStore) Write(token uint64, key string, value []byte) error {
    s.mu.Lock()
    defer s.mu.Unlock()
    if token < s.highest {
        return ErrStaleToken // a newer lock holder has already written
    }
    s.highest = token
    if s.data == nil {
        s.data = map[string][]byte{}
    }
    s.data[key] = value
    return nil
}

func WithLock(ctx context.Context, svc LockService, name string, work func(token uint64) error) error {
    lease, err := svc.Acquire(ctx, name, 10*time.Second)
    if err != nil {
        return err
    }
    defer svc.Release(ctx, name, lease.Token)
    return work(lease.Token) // pass the token on EVERY write to the resource
}

In real systems

  • Kubernetes — Controller leader election uses coordination.k8s.io Lease objects (client-go leaderelection) stored in etcd.
  • etcd — Lease + transaction on a key's create revision; the revision is the fencing token (etcd concurrency.Mutex).
  • ZooKeeper / Curator — Ephemeral sequential znodes; the lowest sequence holds the lock; watches wake the next waiter.
  • Redis — SET NX PX plus Lua release for efficiency locks; Redlock is contested for safety-critical use.
  • Database — SELECT … FOR UPDATE, advisory locks (pg_advisory_lock) and a version column give a lock/CAS with the DB as the arbiter.

Trade-offs

Pros

  • Coordinates exclusive work across processes and machines
  • Leases free the lock automatically when a holder crashes
  • Fencing tokens make the lock safe even with pauses and clock jumps

Cons

  • Needs a CP backend and a fencing-aware resource to be truly safe
  • Adds latency and a dependency on the lock service's availability
  • TTL tuning: too short → spurious expiry, too long → slow recovery after a crash

Token bucket, leaky bucket and sliding-window algorithms; the hard part is keeping counters correct across many nodes.

The problem

Without limits, one noisy client, a retry storm or a bug can saturate a service and take down everyone else. A rate limiter enforces fair use and protects downstream systems — and in a cluster the difficulty is counting correctly across many nodes.

How it works

  • Token bucket: a bucket of capacity B refills at rate r; each request takes a token. Allows bursts up to B, then a steady r/s. The default choice.
  • Leaky bucket: requests enter a queue drained at a constant rate — smooths traffic, adds queueing delay (nginx limit_req).
  • Fixed window counter: count per time bucket — cheap, but 2× bursts at window boundaries.
  • Sliding window log: store timestamps — exact but O(requests) memory. Sliding window counter: weight the previous and current windows — cheap and close to exact.
  • GCRA (generic cell rate algorithm) tracks one value per key (theoretical arrival time) and is equivalent to a token bucket with O(1) state.
  • Distributed: keep counters in Redis and make check-and-decrement atomic with a Lua script (or INCR + EXPIRE); or limit locally per node using quota ÷ N and sync periodically; or push the limit to a gateway.
  • Decide the key (user, API key, IP, tenant) and the failure mode: fail open (protect availability) or fail closed (protect the downstream) when the limiter backend is down.
  • On rejection return HTTP 429 with Retry-After and RateLimit headers; clients should back off exponentially with jitter.

Go sketch

Go
import (
    "sync"
    "time"
)

// TokenBucket allows bursts of up to capacity, then rate tokens per second.
type TokenBucket struct {
    mu       sync.Mutex
    capacity float64
    tokens   float64
    rate     float64 // tokens added per second
    last     time.Time
}

func NewTokenBucket(capacity, rate float64) *TokenBucket {
    return &TokenBucket{capacity: capacity, tokens: capacity, rate: rate, last: time.Now()}
}

func (b *TokenBucket) Allow() bool { return b.AllowN(time.Now(), 1) }

func (b *TokenBucket) AllowN(now time.Time, n float64) bool {
    b.mu.Lock()
    defer b.mu.Unlock()

    // Refill lazily from the elapsed time instead of running a timer.
    b.tokens = min(b.capacity, b.tokens+now.Sub(b.last).Seconds()*b.rate)
    b.last = now
    if b.tokens < n {
        return false
    }
    b.tokens -= n
    return true
}

In real systems

  • nginx — limit_req (leaky bucket with burst/nodelay) and limit_conn per key.
  • Envoy / Istio — Local rate limit (token bucket per proxy) and a global rate limit service backed by Redis.
  • Redis — Lua token bucket / INCR+EXPIRE counters; Redis modules like redis-cell implement GCRA.
  • Cloud API gateways — AWS API Gateway and Cloudflare use token-bucket / sliding-window counters per key with 429 responses.
  • Go x/time/rate — Standard token-bucket limiter: rate.NewLimiter(rate.Limit(10), 20).Allow().

Trade-offs

Pros

  • Protects services and enforces fairness and quotas
  • Token bucket: simple, O(1) state, tolerates bursts
  • Central counters give exact global limits

Cons

  • A central counter adds latency and is itself a dependency; local limits are approximate
  • Fixed windows allow boundary bursts; sliding logs cost memory
  • Limits need tuning and clear client signalling or they cause retry storms