Warmup Guide — Distributed Systems Foundations for Data

Zero-to-principal primer for Phase 01: the log, logical time, partitioning, replication, consistency, failure, idempotency, and backpressure — the small set of ideas that every engine in this track (Kafka, Flink, Spark, Cassandra, Iceberg) is a different expression of. Learn them once; recognise them everywhere after.

Table of Contents

Chapter 1: The Log — One Abstraction Under Everything

From zero. A log is an append-only, totally-ordered sequence of records, each addressed by a monotonic integer offset. That is the entire abstraction — and it is the substrate of the whole field:

  • A Kafka topic-partition is a log.
  • A database's replication stream / WAL is a log.
  • A table is a log compacted by primary key (keep the latest record per key).
  • "Batch" is reading a bounded slice of a log; "streaming" is reading its unbounded tail. They are not two systems — they are two read modes of one log (Kreps's "Kappa" insight; the reason Lambda architectures with two codebases rot).

Why does a principal start here? Because the log is what makes replay possible, and replay is the most valuable property a data platform has: it is how you backfill, how you recover from a bug, how you re-derive a corrupted dataset, how you bootstrap a new consumer. Architectures that discard the log (transform-in-place, no retained source of truth) trade away their own recoverability. Hold this: every "we can't reproduce last month's numbers" incident is a log that wasn't kept or wasn't versioned.

Chapter 2: Time, Clocks, and the Ordering of Events

The single most expensive misconception in distributed data: that you can order events by their wall-clock timestamps. You cannot. Physical clocks on different machines drift, get corrected by NTP (and jump backwards), and are simply unsynchronised at the millisecond scale that matters. Ordering distributed events by wall time produces silently wrong results — duplicated counts, negative durations, "effects before causes."

The principled tools:

  • Lamport clock (scalar): each node keeps a counter; bump it on every local event; on receiving a message stamped t, set local = max(local, t) + 1. Guarantee: if event a happened-before b, then L(a) < L(b). The converse is not true — L(a) < L(b) does not prove causality, which is the clock's limitation.
  • Vector clock: each node keeps a vector of per-node counters. Now you can decide precisely: a happened-before b (every entry ≤ and at least one <), they are equal, or they are concurrent (neither precedes the other). Concurrency detection is what you need to find genuine write conflicts (P11) and to reason about out-of-order events.
  • Sequence numbers / offsets: within a single partition, the log's offset is a total order — which is exactly why per-key ordering (next chapter) is so valuable.
  • Event-time + watermarks (P04): the streaming world's pragmatic answer — trust the event's own timestamp but bound your belief about how out-of-order it can be.

The senior rule: use wall clocks for human-facing display and SLA measurement only; order computation by logical time, offsets, or event-time-with-watermarks — never by arrival.

Chapter 3: Partitioning, Ordering, and Skew

To scale beyond one machine you partition: split the keyspace across N shards by partition = stable_hash(key) % N. Three consequences a principal internalises:

  1. Ordering is per-partition only. A total order across all data does not exist at scale, by design. What you engineer with is per-key ordering: route all events for account_42 to one partition (one key → one partition) and they stay ordered. Choosing the partition key is therefore choosing both your ordering guarantee and your failure-coupling.
  2. The hash must be stable. Language built-in hashes (Python's hash()) are salted per process and change across restarts — using one for partitioning reshuffles every key on every restart and destroys per-key ordering. Use FNV/Murmur/CRC (the lab implements FNV-1a). This is a real, shipped-to-prod bug class.
  3. Skew = hot partitions. If the key is low-cardinality or Zipfian (a few "whale" keys), some partitions get vastly more load. The skew factor = max_load / mean_load is the number you cite ("this key gives a 9× hot partition"). It is the same problem as Kafka hot partitions (P02), Kinesis hot shards (P02), Cassandra hot partitions (P11), and Spark data skew (P06). Fixes: choose a higher-cardinality key, add a salt/bucket component, or use consistent hashing.

Why % N is a resharding trap: changing N remaps almost every key to a new partition (a near-total reshuffle). Consistent hashing (a hash ring with virtual nodes) moves only ~1/N of keys when you add a node — the reason real systems (Cassandra, Dynamo) use it. Extension Project A makes you measure the difference.

Chapter 4: Replication and the Arithmetic of Durability

You replicate data to survive machine loss. The models:

  • Leader/follower (primary/replica): writes go to the leader, which ships them to followers — synchronously (durable but slow, blocks on the slowest follower) or asynchronously (fast but can lose recent writes on leader failure). Kafka's ISR (in-sync replicas) + acks=all + min.insync.replicas is exactly this dial: a write is acknowledged only once it's on ≥ min.insync.replicas members of the ISR.
  • Leaderless / quorum (Dynamo-style): write to W replicas, read from R, and if R + W > N the read set and write set must overlap on at least one up-to-date replica → you read your writes. This is the math behind Cassandra consistency levels (P11). It is a strict inequality: R + W = N is not strong (the lab's boundary test).
  • Durability/availability arithmetic: a quorum operation tolerates N − quorum failures (RF=3, W=2 → survives 1 node down). Sizing redundancy is this subtraction, not a vibe.

The principal framing: replication gives you a dial between durability, latency, and availability, and the right setting is per data product sized by what a lost write costs.

Chapter 5: Consistency Models, CAP, and PACELC

A consistency model is a contract about what a read can return given prior writes. The ladder, strongest to weakest:

  • Linearizable (strong): every operation appears to take effect atomically at a single point between its call and return; there is one real-time order. Expensive; needed for things like leader election and unique-constraint enforcement.
  • Sequential / causal: operations respect program/causal order but not necessarily real-time. Causal consistency (respect happens-before) is often the sweet spot.
  • Read-your-writes / monotonic reads: session guarantees — you never see your own write vanish, never go backwards in time. Often what users actually need.
  • Eventual: replicas converge if writes stop; in between, reads can be stale or conflicting. Cheapest, highest availability.

CAP: when a network Partition happens, you must choose Consistency or Availability — you cannot have both while partitioned. But CAP is a trap because partitions are rare; the everyday tradeoff is PACELC: if Partition then C-or-A, Else (normal operation) then Latency-or-Consistency. The Else clause is the one you tune daily — every "should this read hit the leader or a follower?" is an L-vs-C decision. Saying "PACELC" instead of "CAP" in an interview signals you've operated these systems, not just read the Wikipedia page.

Chapter 6: Failure — The Default State of a Distributed System

In a single process, components either work or the process dies. In a distributed system, the normal state is partial failure: some nodes up, some down, some slow, some lying, the network dropping/reordering/duplicating/delaying messages. Foundational results:

  • The 8 fallacies of distributed computing: the network is not reliable, latency is not zero, bandwidth is not infinite, the network is not secure, topology changes, there is not one admin, transport cost is not zero, the network is not homogeneous. Every one is a bug if you assume otherwise.
  • Two Generals Problem: over a lossy channel, two parties can never be certain they've agreed — no finite number of acknowledgements suffices. Practical consequence: you cannot guarantee "delivered exactly once" over a network. So you change the goal (Ch. 7).
  • FLP impossibility: in a fully asynchronous system with even one faulty process, no deterministic consensus algorithm can guarantee termination. Practical consequence: real consensus (Raft/Paxos, Kafka's KRaft) uses timeouts/randomness to make progress in practice while accepting the theoretical caveat.
  • Gray failure: the worst kind — a node that is slow or partially broken but still "up" to health checks, silently poisoning the system (the stalled follower that's still in the ISR; the disk that's 100× slower but not dead). Detecting gray failure is most of real on-call (P13).

The mindset shift: assume reorder, duplication, loss, delay, and partial failure as the baseline, and design so they don't change the answer. That design is the next chapter.

Chapter 7: Delivery Semantics and Idempotency

Given that the network can lose and duplicate, what can a pipeline promise?

  • At-most-once: send and forget; on failure, data is lost. Rarely acceptable.
  • At-least-once: retry until acknowledged; on failure, duplicates. The practical default — the system must then tolerate duplicates.
  • "Exactly-once" does not mean each message crosses the wire once (Two Generals forbids it). It means at-least-once delivery + idempotent or transactional processing = exactly-once effect. The result is as if each event were processed once.

Two ways to buy it:

  1. Idempotency / dedup: make re-processing a no-op. Dedup by a stable event id (the lab's DedupStore), or use a naturally idempotent sink (upsert by key, set-union, max). Critical subtlety: you can't remember every id forever, so dedup state is bounded (evicted behind a watermark) — which means a duplicate arriving later than the window can slip through. Bounded dedup is a correctness tradeoff, not a free optimisation; you size the window against how late duplicates realistically arrive.
  2. Transactions / atomic commit: commit the output and the input offset atomically, so a crash can't leave them disagreeing. Kafka's transactional producer + read_committed, or the outbox pattern at a service boundary (write the business row and an "event to publish" row in one DB transaction; a relay publishes the outbox).

The interview-grade sentence: "exactly-once is a property of the pipeline's effect on state, purchased with idempotency or atomic offset+output commits, and re-earned at every external boundary — not a network guarantee."

Chapter 8: Backpressure and Flow Control

When a downstream stage is slower than its upstream, something must give. The naive answer — an unbounded in-memory buffer — is always a bug: it converts a throughput problem into an out-of-memory crash, and it hides the slowdown until it's catastrophic. The principled answers:

  • Bounded queues + backpressure: when the buffer fills, slow the producer (block, or signal it to send less). The slowness propagates upstream as flow control instead of silent latency growth. This is Reactive Streams / Akka Streams / Flink's credit-based flow control / Kafka consumer max.poll.records.
  • Little's Law (L = λ × W): the average number of in-flight items equals arrival rate × time in system. It tells you the buffer size you need and what happens when W grows (latency spike) — the queueing-theory floor under all capacity planning (P13).
  • Load shedding: when you can't slow the producer (it's the outside world), drop or sample on purpose, with a metric, rather than collapsing. Better to consciously drop 1% than to topple and lose 100%.

Backpressure is the central health signal in stream processing (P04): rising consumer lag and rising checkpoint duration are backpressure wearing different costumes.

Lab Walkthrough Guidance

Lab 01 — Exactly-Once Kit, suggested order:

  1. fnv1a_32 then hash_partition — verify determinism (same key → same partition across calls); this is the per-key-ordering foundation.
  2. partition_load + skew_factor — feel the difference between uniform keys (~1.0) and a "whale" key (large) — Ch. 3 made tangible.
  3. LamportClock then VectorClock — test that causal chains order under Lamport, and that two independent local ticks are concurrent under vectors (Ch. 2).
  4. DedupStore.check_and_add (first True, then False) and evict (bounded state) — Ch. 7.
  5. exactly_once_apply + simulate_unreliable_delivery — then the payoff test: a reordered, duplicated delivery yields the identical final state (Ch. 7).
  6. quorum_is_strong / tolerated_failures — Ch. 4's arithmetic, including the boundary R + W = N is not strong.

Success Criteria

You are ready for Phase 02 when you can, from memory:

  1. Explain why batch and streaming are read modes of one log, and why that makes replay the platform's key property.
  2. Give a concrete data bug caused by ordering events by wall clock, and the logical-clock fix.
  3. State Kafka's ordering guarantee precisely and explain what choosing the partition key decides.
  4. Compute the durability and read-your-writes properties of RF=3, R=2, W=2.
  5. State CAP and PACELC and give a per-clause data example.
  6. Define exactly-once-effect and both ways to buy it, including why bounded dedup is a correctness tradeoff.
  7. Explain why an unbounded buffer is a bug and what backpressure does instead.

Interview Q&A

Q: A consumer was restarted and now your hourly counts are wrong. Walk me through the suspects. First, duplication: at-least-once redelivery after the restart re-counted events — fixed by dedup on a stable id (and I'd check whether dedup state was bounded such that post-restart duplicates fell outside the window). Second, ordering/partitioning: if the partition key or hash changed (e.g. someone used a salted hash()), keys remapped and per-key aggregation broke. Third, time: if the aggregation keyed on processing time, the restart's catch-up replayed old events into the wrong buckets. The permanent fix is event-time windows + idempotent dedup + a stable partitioner — the three together make the pipeline replayable, which is the actual goal.

Q: Your team wants "strong consistency and high availability." What do you say? That under a network partition they must pick one (CAP) — but I'd reframe to PACELC because partitions are rare and the daily tradeoff is latency vs consistency in normal operation. Then I'd ask what the data is: a balance check needs read-your-writes (route to leader, accept the latency); a recommendation feed is fine eventual (read any replica, win the latency). "Strong + available" isn't one setting; it's a per-data-product dial, and most products don't need the strong end.

Q: What does a vector clock give you that a Lamport clock doesn't, and when do you care? A Lamport clock gives a total order consistent with causality, but L(a) < L(b) can't tell you whether a actually caused b or they were independent. A vector clock can distinguish happens-before from concurrent — which is exactly what you need to detect a genuine write conflict in a leaderless store (two replicas updated the same key independently): concurrent writes need conflict resolution (LWW, or a CRDT merge), causal ones don't. So I care the moment I have multi-writer state — Cassandra, Dynamo, multi-region.

Q: Define exactly-once and then tell me why it's "a lie." Exactly-once delivery over a network is impossible (Two Generals). What's real is exactly-once effect: at-least-once delivery plus idempotent or transactional processing, so retries don't change the result. It's "a lie" only if someone sells it as a network property or a free platform default — it's an end-to-end property of effects on state, re-established at every boundary (and it costs throughput and operability, so you spend it where an error is expensive, not everywhere).

References

  • Martin Kleppmann, Designing Data-Intensive Applications — Ch. 5 (replication), 6 (partitioning), 7 (transactions), 8 (the trouble with distributed systems), 9 (consistency & consensus). This phase is those chapters.
  • Leslie Lamport, Time, Clocks, and the Ordering of Events (1978) — logical clocks
  • Gilbert & Lynch, Brewer's Conjecture (2002) — the CAP proof; Abadi, PACELC (2012)
  • Fischer, Lynch, Paterson, Impossibility of Distributed Consensus with One Faulty Process (FLP, 1985)
  • Jay Kreps, The Log (2013) — the unifying abstraction
  • Nygard, Release It! — bulkheads, circuit breakers, backpressure in practice