Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 36 ยท Practice and Review

Distributed Systems Cheat Sheet

A one-page distributed systems cheat sheet: delivery guarantees, consistency levels, quorum formulas, algorithm summaries, decision tables and a failure checklist.

This page is a quick reference for everything in the Distributed Systems tutorial: the guarantees, the formulas, the algorithms in one line each, and a checklist of failures to think about. It is meant to be scanned, not read. Every row links to the lesson that explains it.

Remember these five

Partial failure Slow and dead look the same.
Retries need idempotency Delivery is at-least-once.
Majority = n/2 + 1 Two majorities always overlap.
Trust causality, not clocks Wall clocks lie.

Most designs come down to these four ideas.

1 / 2

Delivery guarantees

Guarantee Meaning How you get it Risk
At-most-once Sent once, never retried No retry Message can be lost
At-least-once Retried until acknowledged Retry plus ack Duplicates
Exactly-once processing Effect happens once At-least-once plus idempotent receiver Needs durable dedup state
Exactly-once delivery Network delivers once Not achievable Myth

See messaging and RPC and idempotency.

Consistency models (strong to weak)

Model Promise Typical cost
Linearizable One copy; operations appear instant, in real-time order Coordination on every operation
Sequential One global order that respects each client's order Coordination, but no real-time rule
Causal Causes are seen before effects Metadata (vector clocks)
Read-your-writes You see your own writes Sticky sessions or version checks
Monotonic reads You never go back in time Session affinity
Eventual Replicas converge if writes stop Stale reads, conflicts

See consistency models.

Formulas

Formula Meaning
majority = n // 2 + 1 Smallest group that always overlaps another majority
tolerated crashes = n - majority Crashes a majority-based system survives ((n - 1) / 2 for odd n)
R + W > N Read and write quorums overlap in at least one replica
W > N / 2 Two writes cannot both succeed on disjoint replica sets
P(at least one of k succeeds) = 1 - (1 - p)^k Retries, replicas, hedged requests (if independent)
P(all k up) = a^k Needing every replica multiplies unavailability
P(slow fan-out) = 1 - (1 - q)^n Tail latency amplification: q slow chance per call, n calls
delay = random(0, min(cap, base * 2^attempt)) Exponential backoff with full jitter
moved keys โ‰ˆ 1 / (n + 1) Consistent hashing, adding the (n+1)-th node
Lamport: on receive t = max(t, m) + 1 Logical clock update
Python Quorum and majority calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Change the triples to check a configuration before you trust it. N=5, W=2, R=2 fails both overlap tests, which is the typical "fast but stale" setting.

Algorithms in one line

Topic Algorithm One-line summary
Ordering Lamport clock One counter; a โ†’ b implies L(a) < L(b)
Ordering Vector clock One counter per node; detects concurrency
Replication Single leader One node orders writes; followers copy the log
Replication Quorum Write to W, read from R, R + W > N
Replication Anti-entropy Background comparison and repair of replicas
Replication CRDT Merge is commutative, associative, idempotent
Partitioning Consistent hashing Ring with virtual nodes; few keys move
Transactions Two-phase commit Prepare, then commit; blocks if coordinator dies
Transactions Saga Local transactions plus compensating actions
Membership Heartbeats / SWIM Probe nodes, share suspicion by gossip
Election Bully / terms Highest id or highest term wins; fence old leaders
Consensus Paxos Prepare/promise, then accept; majority decides a value
Consensus Raft Leader per term, log replicated to majority, commit on majority
Locks Lease + fencing token Expiring lock; storage rejects stale tokens
Caching Cache-aside Read cache, else load and fill; coalesce misses
Load Power of two choices Sample two servers, pick the less loaded
Spreading data Gossip Each round, tell a few random peers; spreads in about log n rounds
Resilience Circuit breaker Stop calling a failing service for a while

CAP and PACELC at a glance

Situation Consistent (CP) choice Available (AP) choice
During a partition Minority side refuses requests Both sides answer; reconcile later
No partition (PACELC) Higher latency for stronger consistency Lower latency, weaker consistency
Good fit Money, inventory, locks, metadata Feeds, carts, counters, caches

See CAP and PACELC.

Decision tables

Which replication style?

Need Choose
Simplicity and strong consistency Single leader with synchronous follower
Writes in several regions Multi-leader, with a conflict plan
Always-writable, tolerates stale reads Leaderless with quorums and CRDTs or siblings

Which conflict rule?

Data Rule
Cache entry, "last seen" time Last write wins
Counters, sets, flags CRDT
Documents, carts Keep siblings and merge in the application
Money Avoid conflicts: single writer or consensus

Which partitioning?

Workload Choice
Range scans, time series Range partitioning (beware hot spots)
Even load by key Hash partitioning
Nodes join and leave often Consistent hashing with virtual nodes

Which retry policy?

Operation Policy
Idempotent read Retry with backoff and jitter, with a deadline
Non-idempotent write Retry only with an idempotency key
Dependency clearly down Circuit breaker, fail fast
Overloaded service Shed load, do not retry harder

Failure checklist

Walk through this list for any design:

  • A node crashes in the middle of an operation. Is the state recoverable?
  • A message is lost, duplicated, delayed or reordered. Is each handler idempotent?
  • A network partition splits the cluster. Which side keeps serving, and is that safe?
  • A node is slow but not dead. Do timeouts cause duplicate work or double leaders?
  • A paused process wakes up with stale beliefs. Are leases fenced?
  • Clocks jump or drift. Does any correctness rely on wall-clock time?
  • A dependency is down. Is there a timeout, a fallback and a circuit breaker?
  • Load doubles suddenly. Is there backpressure or load shedding?
  • A poison message arrives. Does it go to a dead-letter queue instead of looping?
  • You must restore from backup. Is the order of events and the dedup state preserved?
  • You can't tell what happened. Do you have logs, metrics and a trace id?
Python Fan-out latency amplification (quick estimate)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The more backends one request touches, the more the slow 1% matters. This is why large systems measure p99 and p99.9 instead of averages and use hedged requests and timeouts (see observability and tail latency).

Check your understanding

Quick check ยท 3 questions

of 3 answered You scored / 3 ยท perfect!

  1. 1. In a 7-node cluster that needs a majority, how many crashed nodes can it tolerate?

    The majority of 7 is 4, so up to 7 - 4 = 3 nodes may be down.
  2. 2. Which setting does NOT guarantee that reads overlap with the latest write (N = 5)?

    2 + 3 = 5, which is not greater than N. The other pairs sum to 6.
  3. 3. Which data fits a last-write-wins rule best?

    Losing a concurrent update to a last-seen timestamp is harmless. For the other examples, a lost update is a real bug.

Summary

  • Delivery is at-least-once; correctness comes from idempotent processing.
  • Use R + W > N for read/write overlap and n // 2 + 1 for majorities.
  • Choose consistency per operation; money wants strong consistency, counters and feeds do not.
  • Consistent hashing, gossip, leases with fencing and circuit breakers are the standard building blocks.
  • Walk the failure checklist for every design.

You have reached the end of the Distributed Systems tutorial. Review the interview questions, redo the exercises, or revisit what a distributed system is to see how far you have come.