7) Distributed systems theory — detailed guide

A) CAP, PACELC, and consistency models

CAP (only forces a choice during partitions)

• P (partition): timeouts, packet loss, region split, long GC pauses that look like a split.
• Under P, you can’t guarantee both C (linearizable reads) and A (always respond successfully).
• Real design: choose which endpoints become “strict” (C) vs “serve something” (A) when P happens.

PACELC (adds the normal-day trade)

• If P → choose A or C.
• Else → choose Latency or Consistency (e.g., cross-region quorum adds RTT).

Consistency models you can name in interviews

• Linearizable (strong): reads see the latest committed write globally.
• Sequential: everyone agrees on one order, but reads may not be “latest”.
• Causal: preserves “happens-before”; independent writes may be seen in different orders.
• Eventual / bounded staleness: replicas converge; may be stale for N seconds.
• Session guarantees: read-your-writes, monotonic reads/writes (amazing UX win).

B) Consensus & coordination (Raft/Paxos, ZooKeeper/etcd)

What consensus gives you

• Single chosen leader (at a time) + quorum decisions.
• Replicated log: committed entries survive node failures.
• Safety: committed log entries aren’t “uncommitted” later (with correct Raft/Paxos).

Where to use (and where NOT to)

• Use: leader election, distributed locks (with fencing), config/feature flags, membership metadata.
• Don’t use: storing high-QPS business data (it will bottleneck and hurt reliability).

C) Leader election & fencing tokens (split-brain protection)

The real problem: split brain

• GC pause or flaky network can make an old leader “think” it’s still leader.
• Meanwhile a new leader is elected. Now two writers exist → corruption risk.

Fencing tokens (the fix)

• Coordinator issues a monotonic token on leadership acquisition.
• Every side-effect must carry the token; downstream stores max token and rejects lower.

token = coordinator.acquire_leadership()     # monotonic, e.g. 1051

while coordinator.lease_valid(token):
    write_to_downstream(token, payload)

# Downstream:
# if token < max_seen_token_for_shard: reject as stale

D) Clocks & ordering (NTP, Lamport, vector clocks, HLC)

Clock types (what to use them for)

• Wall clock (NTP): can jump backward/forward → fine for UI timestamps, risky for correctness.
• Monotonic clock: timeouts, deadlines, backoff (per-node only).
• Lamport clock: “happens-before” ordering without detecting concurrency.
• Vector clock: detects concurrent updates (metadata grows with participants).
• HLC: hybrid logical clock → near-time + monotonic, common in multi-region DBs.

Practical ordering rules

• Total order needs consensus/log (Raft) or global sequencer.
• Per-entity order is easy: partition by entity key (order within partition).
• Don’t use timestamps for “latest wins” unless you control versioning (server-issued).

E) Conflict resolution & CRDTs (LWW, merges, repair)

Conflict strategies

• LWW (last-write-wins): simplest; risks losing intent under concurrent writes.
• CRDTs: converge via commutative/idempotent merges (great for counters/sets).
• App merges: field-wise rules (sum/max/union), with audit + repair.

Repair / anti-entropy

• Read repair: fix divergence when you read (good for hot keys).
• Background repair: periodic reconciliation for cold keys.
• Merkle trees: compare hashes to find divergent ranges efficiently.

Mini stance: multi-region settings (a clean design story)

Common pitfalls & fixes (what interviewers love)

• Pitfall: “We’re strongly consistent” (everywhere). Fix: choose per endpoint; name invariants.
• Pitfall: wall-time used for correctness. Fix: server-issued versions, consensus, HLC where needed.
• Pitfall: leader election without fencing. Fix: monotonic tokens + downstream checks.
• Pitfall: “exactly-once” belief. Fix: idempotency keys + atomic commits + dedupe stores.
• Pitfall: no repair strategy. Fix: read-repair + background repair + monitoring.

One-liners for interviews (memorable, accurate)

• “CAP is about partitions; PACELC explains latency vs consistency on normal days.”
• “Consensus is for control-plane choices; data plane stays partitioned for throughput.”
• “Leader election needs fencing tokens; downstream must reject stale leaders.”
• “Ordering is per partition unless you pay for a sequencer or consensus log.”
• “CRDTs preserve user intent for counters/sets; LWW is for safe single-writer-ish fields.”