R15 · Week 15 Recall & Drill

Weekly revision · Week 15 · Covers 5 sessions from Mon–Fri.

Sessions covered

• S071 — Replication — Leader/Follower, Multi-Leader, Leaderless
• S072 — Consistency Models — Linearizable, Sequential, Eventual
• S073 — Consensus — Paxos & Raft Intuition
• S074 — Sharding & Partitioning Strategies
• S075 — Message Queues — SQS, RabbitMQ, Kafka as Queue

90-min structure

Blank-page reconstruction · 30 min

S071 · Replication

1. Define the three topologies in one sentence each.
2. Explain the synchronous-versus-asynchronous trade in one sentence, and what you lose either way.
3. Define split-brain and name one common defence.

Gotcha you probably forgot: replication lag is what breaks reading your own writes. A client writes to the primary, is immediately routed to a lagging replica for the next read, and sees the old value — so the user believes their save failed and does it again. The fixes are routing a client's reads to the primary for a short window after a write, or pinning them to a replica known to have caught up past their write position.

S072 · Consistency Models

1. Rank the models from strongest to weakest and name a real system at each rung.
2. State the single property distinguishing the top two rungs.
3. A counter shows a value, then a refresh shows a smaller one. Which guarantee is violated?

Gotcha you probably forgot: cross-shard transactions are dramatically slower than single-shard writes, because they require a coordination protocol across nodes with multiple round trips, and they hold locks for the whole duration. This is why shard-key choice determines what is fast, slow, or effectively impossible — and why "just make everything strongly consistent" is a cost decision disguised as a correctness one.

S073 · Consensus

1. State the impossibility result in one sentence, and say how practical systems sidestep it.
2. Name the three sub-protocols and say what each is responsible for.
3. In a five-node cluster, how many failures can it survive while still accepting writes?

Gotcha you probably forgot: an even cluster size is strictly worse than the odd size below it. Four nodes need three for a majority, exactly as five do, so you have paid for an extra node while tolerating the same single failure — and you have added another thing that can fail. Always size these clusters odd.

S074 · Sharding

1. Name the three strategies and one system that uses each.
2. Explain consistent hashing and the problem it solves.
3. Give the four-step playbook for resharding without downtime.

Gotcha you probably forgot: virtual nodes exist because plain consistent hashing distributes ranges badly with a small number of physical nodes — a handful of random points on the ring produce very unequal arcs. Mapping each physical node to many points on the ring smooths the distribution and also makes the load of a departing node spread across all survivors rather than dumping onto one neighbour.

S075 · Message Queues

1. Explain the difference between a queue and a log in one sentence.
2. Say what a visibility timeout is and what happens when it is too short.
3. Give the rule of thumb for how many delivery attempts before diverting a message.

Gotcha you probably forgot: a downstream failure plus naive retries produces a retry storm — every consumer retries at once, the load on the struggling dependency increases exactly when it needs relief, and the failure sustains itself after the original cause has passed. The defences are exponential backoff with jitter, a circuit breaker that stops calling a failing dependency, and a cap on attempts with diversion to a side channel.

Hands-on drill · 30 min

Task: measure a quorum, watch hashing fail to fix a hot key, and turn a retry storm into a controlled degradation.

mkdir -p ~/projects/w15-drill && cd ~/projects/w15-drill

Step 1 — quorum overlap and cluster sizing (9 min)

# quorum.py
import itertools
 
def guarantees_overlap(n, w, r):
    """W + R > N means every read set intersects every write set."""
    return w + r > n
 
print("N  W  R  overlap  note")
for n in (3, 5):
    for w in range(1, n + 1):
        for r in range(1, n + 1):
            ok = guarantees_overlap(n, w, r)
            if ok and (w + r == n + 1):        # the cheapest configurations that work
                print(f"{n}  {w}  {r}  yes      minimal overlapping config")
    print(f"{n}  1  1  {'yes' if guarantees_overlap(n,1,1) else 'no ':<8} fast, may read stale")
 
print()
print("size  majority  failures tolerated  cost per extra node")
prev = None
for n in range(3, 8):
    majority = n // 2 + 1
    tolerated = n - majority
    verdict = "" if prev is None or tolerated > prev else "  <-- no gain over previous size"
    print(f"{n:>4}  {majority:>8}  {tolerated:>18}{verdict}")
    prev = tolerated

Expected outcome: the second table shows that going from three to four nodes tolerates exactly one failure either way — the even size buys nothing and adds a component that can fail. Five tolerates two. That table is the whole reason consensus clusters are sized odd. In the first table, note that the fastest configuration — writing to one and reading from one — never guarantees overlap, which is precisely the trade you make when you choose speed over freshness.

Step 2 — hashing does not fix a hot key (10 min)

# hotshard.py
import hashlib
import random
 
rng = random.Random(11)
 
def shard_of(key: str, shards: int) -> int:
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % shards
 
# 10k keys, uniformly hashed. But traffic follows a heavy-tailed distribution.
keys = [f"user-{i}" for i in range(10_000)]
traffic = []
for _ in range(200_000):
    if rng.random() < 0.5:
        traffic.append("user-0")            # one celebrity account
    else:
        traffic.append(rng.choice(keys))
 
def load(traffic, shards, salt_hot=False, salts=16):
    counts = [0] * shards
    for k in traffic:
        if salt_hot and k == "user-0":
            k = f"{k}#{rng.randrange(salts)}"    # spread one key across many shards
        counts[shard_of(k, shards)] += 1
    return counts
 
for shards in (4, 16, 64):
    c = load(traffic, shards)
    print(f"shards={shards:<3} keys spread evenly, but busiest={max(c):<7} "
          f"idlest={min(c):<6} ratio={max(c)/max(min(c),1):.1f}")
 
c = load(traffic, 16, salt_hot=True)
print(f"shards=16  with the hot key salted: busiest={max(c)} idlest={min(c)} "
      f"ratio={max(c)/max(min(c),1):.1f}")

Expected outcome: adding shards leaves the busiest shard essentially unchanged, because every request for the hot key hashes to the same place no matter how many shards exist. Salting the hot key drops the ratio sharply. The cost, which you must state when proposing this: reads for that key now have to query every salt bucket and merge, so you have traded write concentration for read fan-out. That is the actual shape of the fix — not free, just better.

Step 3 — retry storm versus backoff and breaker (11 min)

# retrystorm.py
import random
 
rng = random.Random(5)
 
class Dependency:
    """Fails while overloaded. Load itself is what keeps it overloaded."""
    def __init__(self, capacity=50):
        self.capacity, self.calls_this_tick, self.down_until = capacity, 0, 20
 
    def call(self, tick):
        self.calls_this_tick += 1
        if tick < self.down_until:
            return False
        return self.calls_this_tick <= self.capacity      # overload -> more failures
 
def simulate(mode, ticks=60, consumers=200):
    dep = Dependency()
    pending = [{"attempts": 0, "next": 0} for _ in range(consumers)]
    dead_letter, done, total_calls = 0, 0, 0
    breaker_open_until = -1
 
    for t in range(ticks):
        dep.calls_this_tick = 0
        for m in pending:
            if m.get("finished") or m["next"] > t:
                continue
            if mode != "naive" and t < breaker_open_until:
                m["next"] = breaker_open_until               # breaker: do not even call
                continue
            total_calls += 1
            if dep.call(t):
                m["finished"] = True
                done += 1
            else:
                m["attempts"] += 1
                if mode == "naive":
                    m["next"] = t + 1                        # immediate retry, every tick
                else:
                    if m["attempts"] >= 5:
                        m["finished"] = True                 # divert, stop retrying
                        dead_letter += 1
                        continue
                    backoff = 2 ** m["attempts"]
                    m["next"] = t + backoff + rng.randint(0, backoff)   # jitter
        if mode != "naive" and dep.calls_this_tick > dep.capacity:
            breaker_open_until = t + 5
    return total_calls, done, dead_letter
 
for mode in ("naive", "backoff+breaker"):
    calls, done, dlq = simulate(mode)
    print(f"{mode:<16} calls made={calls:<7} succeeded={done:<5} diverted={dlq}")

Expected outcome: the naive mode issues vastly more calls at the struggling dependency, and the extra load is what sustains the failure past its original cause. The protected mode makes far fewer calls, recovers, and diverts the messages that genuinely cannot be processed instead of retrying them forever. Note the jitter specifically: without it, every consumer backs off by the same amount and they all return simultaneously, which reproduces the storm on a delay.

Gap analysis + next week preview · 10 min

• Did the cluster-sizing table match your intuition, or had you assumed more nodes always means more fault tolerance?
• In Step 2, did you state the read fan-out cost of salting before reading it here? Proposing a fix without its cost is how fixes get rejected.
• Could you list the four parts of the retry-storm defence from memory? You will need all four; three of them is still an outage.

Next week (S076–S080) builds on this into system design proper: designing a URL shortener and a rate limiter; designing a feed and a notification system; observability and service level objectives; capacity estimation; and the design-interview framework itself. Every trade-off from this week — replication, consistency rung, shard key, delivery semantics — becomes a decision you must state and defend in those designs.

Part of the 6-month evergreen learning plan.