Lab 01 — Partitioner, Idempotency & Exactly-Once Kit

Phase: 01 — Distributed Systems Foundations | Difficulty: ⭐⭐⭐☆☆ | Time: 5–6 hours

Every distributed data system is built from four primitives: partition the work, order it without trusting wall clocks, make re-processing safe, and replicate for durability without lying about consistency. This lab implements all four — and proves the one property the whole field exists to deliver: an unreliable, reordered, duplicated delivery produces the identical final state as a clean one.

What you build

  • fnv1a_32 / hash_partition / partition_load / skew_factor — deterministic partitioning (the basis of per-key ordering) and the skew measurement that names a hot partition with a number
  • LamportClock / VectorClock — logical time: Lamport (causality ⇒ order) and vector (distinguish happens-before from concurrent, the basis of conflict detection)
  • DedupStore — bounded idempotency: first-seen is True, duplicates are no-ops, and state is evicted behind a watermark so it can't grow forever
  • exactly_once_apply / simulate_unreliable_delivery — at-least-once delivery + dedup = exactly-once effect, demonstrated under reorder + duplication
  • quorum_is_strong / tolerated_failures / quorum_available — replication math: R + W > N, and how many failures a quorum survives

Key concepts

ConceptWhat to understand
Stable hashinghash() is salted per process; partitioning needs a stable hash or per-key order breaks on restart
Skew factormax/mean load — the number behind "hot partition"
Lamport vs vectorscalar gives order from causality; vector also detects concurrency
Exactly-once effectthe only exactly-once that exists; dedup makes duplicates no-ops
Bounded dedupyou can't remember every id forever — eviction is a real correctness tradeoff
R + W > Nstrict; equality is not strong; tolerated failures = N − quorum

Run

pip install -r requirements.txt
pytest test_lab.py -v
LAB_MODULE=solution pytest test_lab.py -v

Success criteria

  • All tests pass — test_exactly_once_effect_under_duplicates_and_reorder and test_exactly_once_is_order_independent are the ones that certify understanding.
  • You can explain why bounded dedup (evict) is a correctness tradeoff, not a free optimisation (a duplicate later than the retention window slips through).
  • You can state, with numbers, the durability of RF=3 / W=2 / R=2.

Extensions

  • Replace modulo partitioning with consistent hashing (a hash ring with virtual nodes) and measure how many keys move when you add a partition — the reason real systems don't use % N for resharding (foreshadows P02 rebalancing, P11 Cassandra).
  • Add a transactional outbox: apply a state change and record its id atomically, then show crash-recovery doesn't double-apply (foreshadows P05 CDC, P04 exactly-once sinks).
  • Implement read-repair: given replicas with vector-clocked values, return the merged value and detect a genuine conflict (foreshadows P11 last-write-wins vs CRDTs).