Distributed systems

Distributed systems

Raft consensus, replication, consistent hashing, saga-style distributed transactions, two-phase commit, and conflict-free replicated data types.

• Consistent hashing

  6 studies
  1. 1.Consistent Hashing: Rings, Virtual Nodes & Replica PlacementModulo remaps ~all keys on membership change; consistent hashing remaps ~K/N via a clockwise hash ring. Vnodes fix skew and fan out failures; RF walks collect distinct physical nodes (topology-aware).
  2. 2.Rendezvous Hashing (HRW): Highest Random WeightHRW scores hash(key, node) and picks the max. No ring to maintain; membership change remaps about 1/N; lookup is O(N) unless approximated. Weights fold into the score.
  3. 3.Jump Consistent Hash: Dense Buckets, Almost No MemoryJump hash maps a key onto 0..N-1 with almost no memory and ~K/N movement. Buckets must be a dense integer range — no arbitrary node ids, weights, or AZ walks.
  4. 4.Vnode Rebalancing & Membership: Stream ~K/N Without Split-BrainAdding a node only steals ~1/N of keys, but streaming those keys still needs throttling, versioned membership, and hinted handoff so clients and replicas do not split-brain.
  5. 5.Topology-Aware Replica Placement: Racks, AZs, and Honest QuorumsRF walks must skip the same host and prefer different racks/AZs. Quorum R+W>RF is not enough if all copies share a failure domain.
  6. 6.Hot Keys & Bounded Loads: When Consistent Hashing Is Not EnoughConsistent hashing balances key cardinality, not QPS. Salt hot partitions, coalesce, or use bounded-load / power-of-two-choices so one viral key does not melt a shard.

• CRDTs

  6 studies
  1. 1.CRDTs — Conflict-Free Types, Convergence & When Consensus WinsInterview map for conflict-free replicated data types: a join that converges, the state versus op versus delta split, and the invariants that still belong on Raft or one ledger.
  2. 2.Counters & Registers — G-Counter, PN-Counter, LWW & MV-RegisterG-Counter and PN-Counter merge per-replica counts with a component-wise max. Last-writer-wins drops a concurrent value. The multi-value register keeps it.
  3. 3.Sets & Maps — G-Set, 2P-Set, OR-Set, OR-MapG-Set only adds. 2P-Set removes forever. An observed-remove set tags each add with a dot so a later add can win. An OR-Map nests a CRDT under each key.
  4. 4.Sequences & Collaborative Text — RGA, LSEQ, Yjs/AutomergeSequence CRDTs give each insert a stable identity so two people typing at the same place converge. RGA, LSEQ, Yjs, and Automerge are that idea with different identifiers. A last-writer-wins string is not.
  5. 5.State-based vs Op-based vs Delta-CRDTs & CompactionThe same abstract type can ship as full state, as operations, or as deltas. The channel, the fresh replica, and the tombstone pile follow from that choice.
  6. 6.Production CRDTs & When NOT to Use Them (Riak, Redis CRDT, collab apps, vs Raft/linearizability)Riak data types, Redis Active-Active, and Yjs or Automerge are production CRDTs. Unique names, non-negative money, and exactly-once effects still belong on a linearizable store.

• Durable Objects

  6 studies
  1. 1.Cloudflare Durable Objects - Single-Instance Actors, Edge State & When to Use ThemHub: a Durable Object is a single-threaded actor with its own SQLite, one live instance per ID worldwide; routing with getByName/idFromName/newUniqueId, stubs and RPC; DO vs KV, D1, R2, Queues, Redis, Postgres row locks, Orleans and Akka with a decision chart; runnable routing simulation; what happens if you pick the alternative.
  2. 2.Durable Objects Storage - SQLite vs Legacy KV, Transactions, Write Coalescing & Point-in-Time RecoveryStorage: SQLite backend vs legacy KV, SQL API, sync KV API, transactionSync, write coalescing, in-memory cache, allowUnconfirmed/noCache, PITR bookmarks with ctx.abort, limits quoted from docs; output-gate and PITR simulations; storage decision chart.
  3. 3.Durable Objects Concurrency - Single Thread, Input & Output Gates, blockConcurrencyWhile & the Races That RemainConcurrency: single thread plus input and output gates, where interleaving still happens (fetch, timers, other objects), blockConcurrencyWhile cost, the external-call oversell race reproduced under wrangler dev (reserved 6 of 3) and fixed with claim-first and version check.
  4. 4.Durable Objects Real-Time - WebSocket Hibernation, Alarms, Chat, Presence & Collaborative EditingReal-time: WebSocket Hibernation API (acceptWebSocket, tags, attachments, auto-response), real chat room with presence and history, alarms, collaborative editing via CRDT or server ordering, fan-out batching and backpressure, hibernation cost math ($20.65 vs $420.65 docs example), transport decision chart.
  5. 5.Durable Objects Scaling - Sharding by ID, Hot Objects, Location Hints, Limits & CostScaling: per-object throughput soft limits, sharding by ID, hot objects and sharded counters, location hints and jurisdictions, cold starts and eviction, pricing; real rate limiter, lease with fencing token and counter run under wrangler dev; shard sizing and global-vs-per-key simulations.
  6. 6.Durable Objects in Production - Resets, Deploys & Class Migrations, Observability, Testing & Interview Q&AProduction: failure catalog (deploys, eviction, write failure resets, blockConcurrencyWhile throws, overloaded vs retryable errors), version skew, declarative exports class lifecycle (create, rename three-deploy alias, transfer, delete), at-least-once alarms, observability, testing with @cloudflare/vitest-plugin (4 real passing tests), interview Q&A.

• Raft consensus

  5 studies
  1. 1.Raft Consensus — Leader Election, Log Replication & SafetySingle leader, append-only log, commit after majority; terms/roles/heartbeats/log matching vs Multi-Paxos; used in etcd/Consul/TiKV/K8s metadata.
  2. 2.Quorums & Majority — Why 2f+1, Read Quorums & Stale ReadsN=2f+1 tolerates f crashes; majority intersection prevents conflicting commits; linearizable reads need ReadIndex/lease not blind follower reads.
  3. 3.Leader Election Deep Dive — Timeouts, Randomized Election, Split VotesHeartbeat silence → new-term election via RequestVote; exclusive votes + up-to-date log; randomized timeouts; pre-vote reduces disruption.
  4. 4.Log Replication & Commit Index — Matching, Conflict Resolution & SafetyAppendEntries + prevLog match; nextIndex backoff; truncate divergent suffixes; commitIndex on majority current-term matchIndex (Figure 8); safety sketch.
  5. 5.Raft vs Multi-Paxos vs Zab — When to Choose WhatSame CFT RSM goal, different models/ops/ecosystems; prefer Raft/etcd/Consul greenfield; keep ZK when watches own estate; custom Multi-Paxos only with deep expertise.

• Sagas & Distributed Transactions

  6 studies
  1. 1.Sagas & Distributed Transactions — Orchestration, Choreography & CompensationsInterview hub on sagas versus 2PC, orchestration versus choreography, compensations, deadlines, and reconciliation for multi-service business transactions.
  2. 2.Two-Phase Commit vs Sagas — Why 2PC Breaks at ScaleWhy 2PC blocks at scale, how that compares with sagas, and when a shared-database ACID transaction still wins.
  3. 3.Orchestration vs Choreography — Central Coordinator vs Event DanceCentral coordinator versus an event dance for sagas, with decision guidance and pointers to outbox, inbox, and deadlines.
  4. 4.Compensating Transactions — Idempotent Undo & Semantic RollbackIdempotent semantic undo for sagas: reverse-order compensations, void versus refund, and reversing ledger entries.
  5. 5.Saga State Machines — Timeouts, Retries & DeadlinesSaga state machines with per-step timers, whole-saga deadlines, bounded retries, and durable state.
  6. 6.Saga Failure Modes — Poison Steps, Partial Failure & ReconciliationPoison steps, partial failure, dead-letter quarantine, and idempotent reconciliation for sagas that miss their SLA.

• Time, Clocks & Ordering

  6 studies
  1. 1.Time, Clocks & Ordering in Distributed Systems - Physical Clocks, Lamport, Vector Clocks, HLC & TrueTimeInterview hub: why no machine knows the real time; wall vs monotonic; the ladder from NTP wall clocks to Lamport, vector clocks, HLC and TrueTime with a decision flow; runnable LWW-on-skewed-clocks data loss vs Lamport vs vector clocks; comparison table incl. timestamp oracles; Cloudflare 2017 leap second, Spanner, CockroachDB, Dynamo, Snowflake/UUIDv7 anchors.
  2. 2.Physical Clocks - NTP/PTP, Drift & Skew, Wall vs Monotonic Time & Leap SecondsHow clocks are kept in sync: oscillator drift (ppm), NTP four-timestamp offset/delay math and the delay/2 error bound (runnable), slew vs step, NTP vs PTP vs cloud time (ClockBound); wall vs monotonic APIs per language; runnable lease bug under an NTP step; leap seconds step vs smear; failure catalog (LWW, leases, TTL/JWT, negative durations).
  3. 3.Lamport Clocks - Happens-Before, Logical Timestamps & Total OrderHappens-before precisely; Lamport clock rules and total order with (ts, pid) tie-break (runnable); runnable proof that the clock condition holds but L(a)<L(b) does not imply causality; Lamport vs wall vs vector vs HLC vs consensus log index; Raft terms and fencing tokens as logical clocks; pitfalls (tie-break, persistence).
  4. 4.Vector Clocks vs Version Vectors - Detecting Concurrent Writes, Siblings & Dotted Version VectorsVector clock rules and four-way compare; runnable Dynamo-style sibling store with context and merge; vector clocks vs version vectors vs client-id vclocks vs dotted version vectors; runnable LWW vs per-server VV (lost write) vs DVV (siblings); size growth and pruning; LWW vs siblings vs CRDTs vs consensus; Dynamo, Riak 2.0, Cassandra.
  5. 5.Hybrid Logical Clocks & TrueTime - Commit Wait, Uncertainty Intervals & External ConsistencyHLC algorithm (l, c) with skewed nodes and a max-offset guard (runnable); CockroachDB max-offset self-termination, MongoDB cluster time, YugabyteDB; TrueTime intervals and commit wait (runnable) plus CockroachDB-style uncertainty restarts; external consistency vs serializability vs SI; TrueTime vs HLC vs timestamp oracle vs single leader.
  6. 6.Distributed ID Generation - Snowflake, UUIDv4 vs UUIDv7, ULID, KSUID & SequencesID schemes compared (sequences, hi-lo, Flickr ticket servers, Snowflake, Instagram, UUIDv4, UUIDv7/RFC 9562, ULID, KSUID); runnable Snowflake with sequence overflow and clock-rollback handling; runnable UUIDv7 with monotonic counter plus B-tree right-edge locality vs UUIDv4; ordering vs locality vs coordination; hot-partition twist; JS 2^53 pitfall.

• Two-Phase Commit — Protocol, Coordinator & Participants

  6 studies
  1. 1.Two-Phase Commit — Protocol, Coordinator & ParticipantsInterview hub: 2PC coordinator, votes, forced logs, blocking vs 3PC, Paxos Commit, and sagas.
  2. 2.Prepare & Commit - Votes, Logging & the DecisionPrepare and commit votes, force-before-send logging, and the decision record.
  3. 3.Failures & Recovery - Blocking, Coordinator Crash & Participant CrashCoordinator and participant crashes, blocking, termination rules, and heuristic decisions.
  4. 4.Optimizations - Presumed Abort, Presumed Commit & Read-Only VotesPresumed abort, presumed commit, and read-only votes without shrinking the uncertainty window.
  5. 5.XA & Database 2PC - Postgres PREPARE, MySQL XA & Heuristic DecisionsX/Open XA, Postgres PREPARE TRANSACTION, MySQL XA, and heuristic commit or rollback.
  6. 6.2PC vs 3PC vs Consensus Commit vs SagasWhy 3PC splits under partition, Paxos Commit as F>0 2PC, and when to use the existing saga series.