R15 · Week 15 Recall & Drill

Assessment scope

Attempt the recall prompts unaided, then work through the implementations and answer keys. The local programs use explicit fixtures and independent checks; product behavior is tied to named primary sources, not inferred from the toy models. Service deployment and production readiness are separate from this conceptual review. Timing budgets are adjustable practice suggestions.

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

By the end of this revision you can

• Contrast the three replication topologies in one sentence each, and explain the durability-versus-latency dial between synchronous and asynchronous.
• State what the quorum inequality guarantees, and describe split-brain plus its two mainstream defences.
• Compare consistency guarantees without a false total ordering, and choose explicit guarantees for a cart, a counter and a ledger.
• Walk through leader election, log replication, and safety, and say why safety is the hard part.
• Name the three partitioning strategies, explain consistent hashing, and give three concrete fixes for a hot partition.
• Design a consumer that survives duplicates and poison messages without creating a retry storm.

90-min structure

The 90-minute budget is pacing guidance, not a claim that full execution and every extension fit every learner's session.

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.

Answer key — topology does not specify the whole protocol. Leader/follower sends writes through one leader and copies them to followers; multi-leader allows writes at multiple leaders and needs conflict semantics; leaderless clients/coordinators contact multiple replicas and reconcile versions under specified read/write rules. Full read replicas of one shard generally apply its write stream, so adding them does not divide that shard's logical write workload. They can improve read capacity, durability/failover or read/write resource isolation, but not by a guaranteed linear factor. Partial replication and sharding are distinct designs; replication itself is not “useful for reads and nothing else.”

Synchronous acknowledgement waits for a declared replica/durability condition, increasing coordination latency and potentially rejecting writes if that condition cannot be met. Asynchronous acknowledgement can complete earlier but acknowledged writes may be lost if failover selects a replica that has not received them. Neither word alone specifies fsync, number of replicas or failure domains. For read-your-writes, read from a node proven at or beyond the returned write position or use a supported session token; a fixed short primary-sticky interval is a heuristic, not a lag-independent proof.

Split-brain means multiple actors can act as write authority for overlapping state. Use a quorum/consensus-backed authority decision and fencing enforced at the protected resource so a stale leader cannot continue writing. A lock with an expired lease is insufficient if the old holder keeps running and the sink accepts its writes. Quorum set intersection, computed below, is necessary to many protocols but does not supply their version, commitment or fencing rules.

S072 · Consistency Models

1. State implication and scope relationships among the models, with documented examples rather than a universal vendor ranking.
2. Explain real-time precedence as the distinction between linearizability and sequential consistency.
3. A counter shows a value, then a refresh shows a smaller one. Which guarantee is violated?

Answer key — compare guarantees, not six interchangeable rungs. Linearizability requires each operation to appear atomic between invocation and response in an order respecting real-time precedence. Sequential consistency preserves each process's program order in a single legal order but need not respect cross-process wall-clock precedence. Causal consistency preserves causally related operations, allowing independent concurrent operations different orders. Eventual convergence says replicas settle to the same value under the model's no-new-update/delivery assumptions; it says little by itself about intermediate reads.

Read-your-writes and monotonic reads are session guarantees, not two global consistency levels in a universal chain. Read-your-writes prevents a session reading a state older than its own completed write; monotonic reads prevents that session moving backward in the version order it has observed. A numeric counter going from 8 to 7 only demonstrates a violation if the workload is increment-only and those observations represent ordered versions; a valid decrement or reset is not evidence of stale reads. A causal protocol's precise session and visibility assumptions still matter.

For documented system examples, Cosmos DB names Strong, Bounded Staleness, Session, Consistent Prefix and Eventual levels; its Session documentation specifies read-your-writes and write-follows-reads under its session-token assumptions. Those product levels are not a proof of a six-rung textbook ladder or a universal implementation of every model above. A cart can use session visibility plus explicit concurrent add/remove merge rules; a noncritical analytics counter may allow eventual visibility, whereas a quota counter may require atomic conditional updates. A money ledger needs invariant-preserving transactions/uniqueness and a specified read contract—merely choosing a “strong” individual read does not prevent double spending across records. Cross-shard coordination adds work and can add latency, but not every implementation holds traditional locks or has the same slowdown.

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?

Answer key — separate safety from progress. FLP rules out guaranteed termination for deterministic consensus in a fully asynchronous system with even one possible crash; it does not say no practical consensus can work. Practical protocols use timing/partial-synchrony assumptions and randomized election timeouts to obtain progress when conditions recover while maintaining their stated safety rules. A long timeout is not a mathematical proof that a remote node died.

Raft organizes the problem around leader election, log replication and safety restrictions. In a term, a candidate needs a majority and voters apply the log up-to-date rule. AppendEntries checks the preceding log position/term and reconciles conflicting suffixes. A leader advances commitment by the majority rule for an entry in its current term; prior entries become committed through that prefix. Election restrictions and persistent term/vote/log state are part of safety, not disposable liveness machinery. These rules establish that a committed entry is present in later leaders under Raft's crash-failure assumptions; Byzantine nodes are outside the basic protocol.

Five voters need three for a majority and can make progress with two unavailable if the other three communicate and elect a valid leader. Three need two and tolerate one; four need three and also tolerate one. Odd sizes are economical at these static majority thresholds, not an “always odd” theorem: topology, membership transitions and operational constraints can justify an even count. Membership changes require the protocol's overlapping-quorum procedure, not instantly changing the denominator in a running cluster.

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.

Answer key — distribute the unit that is actually hot. Range partitioning places nearby keys together and supports range scans but can concentrate monotone inserts; hash partitioning spreads keys yet scatters ranges; directory/lookup routing maps logical partitions to placements and adds metadata ownership/caching requirements. MongoDB supports ranged and hashed sharding and maintains placement metadata; these strategies can coexist rather than being disjoint vendor categories.

A consistent-hash ring assigns a key to the next point clockwise. Adding a point moves only keys in its newly owned interval instead of remapping most keys as modulo-N often does. Virtual nodes give each physical node several ranges, improving expected balance and spreading transfers, not guaranteeing equal traffic. A single indivisible key still has one owner. For a hot read key, cache/replicate reads subject to freshness; for decomposable writes such as counts, salt into subkeys and merge; for isolation, dedicate/move the tenant, recognizing the dedicated shard still has finite capacity. Salting ordered updates to one account without a semantic merge is not a free fix.

Four-step resharding playbook: (1) provision target capacity and a versioned routing/ownership plan, retaining the source of truth; (2) copy a consistent snapshot and catch up a change log, using stable IDs/version checks so replay does not duplicate effects; (3) validate counts/checksums/invariants and cut over under a fenced, versioned routing transition, draining or forwarding old routes; (4) observe and reconcile, then retire old copies only after the rollback/retention window. Snapshot copy alone races with writes. A rollback must reconcile writes made after cutover, not just flip a DNS record.

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. Choose a delivery-attempt cap from the failure class, latency budget and retry policy rather than a universal number.

Answer key — delivery is not the business effect. A work queue gives competing consumers work to acknowledge; a retained log keeps ordered records for independent consumer positions and replay until retention removes them. This is a usage distinction, not a disjoint product taxonomy: Kafka consumer groups distribute a partition's work among group members while other groups can read the same retained records independently. Ordering is scoped to a partition, not all partitions, and committing a consumer offset does not by itself atomically commit a remote business effect.

In SQS, receiving a message makes it temporarily invisible to other receives; successful processing must still delete it. If processing takes 45 seconds but visibility is only 30 seconds, the message can become eligible for another worker while the first is still working. Set and, where needed, extend visibility for the observed processing duration with a bounded heartbeat policy. Visibility is not a distributed lock or an exactly-once guarantee: standard queues can deliver duplicates even within the timeout. Keep the transaction/idempotency boundary in Step 3 regardless of the chosen timeout.

Classify a malformed message as permanent and divert it with diagnostic context; retry a transient timeout only within a shared attempt and elapsed-time budget. For example, with a 60-second deadline and up to five 2-second calls, backoff delays of 2, 4, 8 and 16 seconds consume at most 40 seconds before jitter/queue delay; four independent jitter additions bounded by their corresponding delay could raise that to 70 seconds. Enforce the elapsed deadline too rather than assuming the attempt cap suffices. Backoff/jitter spreads retry arrivals, a breaker pauses calls during failure, and a load/concurrency limit protects recovery; these are different controls. Own the dead-letter queue with alerts, diagnosis and a controlled redrive policy. Redrive must retain the idempotency identity and avoid dumping an entire failed backlog onto a newly recovered dependency.

Hands-on drill · 30 min

Use exhaustive small sets where a proof is possible, and label finite scheduling experiments where it is not. These programs execute no database cluster or queue service.

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

from itertools import combinations
 
def every_pair_intersects(n, w, r):
    if not 1 <= w <= n or not 1 <= r <= n:
        raise ValueError('quorum sizes must be in 1..N')
    writes = [set(x) for x in combinations(range(n),w)]
    reads = [set(x) for x in combinations(range(n),r)]
    return all(a & b for a in writes for b in reads)
 
for n in range(1,7):
    for w in range(1,n+1):
        for r in range(1,n+1):
            assert every_pair_intersects(n,w,r) == (w+r > n)
assert [(n,n//2+1,n-(n//2+1)) for n in (3,4,5)] == [(3,2,1),(4,3,1),(5,3,2)]
print('all quorum pairs for N=1..6 agree with W+R>N')

Proof: if read/write sets were disjoint their union would have size R+W, which cannot exceed N. Conversely if R+W is at most N, take the first W nodes for writes and the next R for reads; they are disjoint. This establishes set intersection, not “the read always returns the latest value.” The latter also needs completed-write, membership, version-selection and concurrent-operation semantics.

Counterexample with overlap: x=1 completes on A/B. A concurrent x=2 is written only to C and pauses before its W=2 acknowledgement. Read A/C sees versions 1 and 2 and naively returns 2; a later read A/B returns 1. Both read sets have R=2, both intersect the last completed write set, yet the 2→1 history of these ordered reads is not linearizable for this register. Correct protocols need commit/version/read-repair or equivalent rules, not a slogan. No extra node in the enumeration supplies Raft's log safety.

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

import hashlib
from collections import Counter
 
def digest(key):
    return int.from_bytes(hashlib.sha256(key.encode()).digest()[:8], 'big')
def shard_load(traffic, shards, salt=False):
    if shards <= 0:
        raise ValueError('positive shard count required')
    counts = [0]*shards
    partial = Counter()
    for i,key in enumerate(traffic):
        bucket = i % 16 if salt and key == 'hot' else 0
        routed = f'{key}#{bucket}' if salt and key == 'hot' else key
        counts[digest(routed)%shards] += 1
        partial[(key,bucket)] += 1
    merged = Counter()
    for (key,_),amount in partial.items():
        merged[key] += amount
    return counts,merged
 
traffic = ['hot']*1600 + [f'user-{i}' for i in range(400)]
for shards in (4,16,64):
    counts,merged = shard_load(traffic,shards)
    assert max(counts) >= 1600 and merged == Counter(traffic)
salted,merged = shard_load(traffic,16,True)
assert merged == Counter(traffic) and max(salted) < 1600
print('salted peak',max(salted),'total',sum(salted))
 
def ring_owner(key, points):
    if not points:
        raise ValueError('nonempty ring required')
    h = digest(key)
    ordered = sorted(points)
    return next((owner for point,owner in ordered if point >= h),ordered[0][1])
ring = [(digest('node-A'),'A'),(digest('node-B'),'B'),(digest('node-C'),'C')]
expanded = ring + [(digest('node-D'),'D')]
keys = [f'key-{i}' for i in range(1000)]
changed = [k for k in keys if ring_owner(k,ring) != ring_owner(k,expanded)]
assert changed and all(ring_owner(k,expanded) == 'D' for k in changed)
print('ring keys moving to the new node',len(changed))

Answer: an unsalted shard must handle at least the 1,600 hot-key requests, regardless of shard count. This deterministic salting splits the count into 16 partial counters and exactly recombines them; it changes the operation from one-key lookup to fan-out/merge. It does not implement a sharded money balance or preserve per-key event order. The ring exercise measures membership movement separately from load; SHA-256 here is just a stable key-to-integer choice, not a claim about any product's partitioner. Read costs, write fencing and migration remain outside the count model.

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

The dependency is unavailable until tick 12, then accepts at most 8 calls per tick. Overload rejects excess calls; it does not extend the outage automatically. The old explanation claimed a self-sustaining outage its code did not model. Every message receives at most five attempted calls here. poison fails permanently; the protected mode can classify it immediately. A breaker opens after three consecutive failed calls and permits a later probe; jitter schedules retries of individual messages. All of these are discrete toy policies, not queue-runtime behavior.

import random
 
def retry_sim(protected, ticks=120, count=40):
    rng = random.Random(5)
    jobs = [{'id':i,'tries':0,'next':0,'state':'pending'} for i in range(count)]
    total_calls, open_until, consecutive = 0, 0, 0
    effect_ids = set()
    calls_by_tick = []
    for tick in range(ticks):
        used = 0
        for job in jobs:
            if job['state'] != 'pending' or job['next'] > tick:
                continue
            if protected and tick < open_until:
                continue
            job['tries'] += 1
            total_calls += 1; used += 1
            poison = job['id'] == 0
            success = tick >= 12 and used <= 8 and not poison
            if success:
                effect_ids.add(job['id'])
                job['state'] = 'done'; consecutive = 0
            else:
                consecutive += 1
                if job['tries'] >= 5 or (protected and poison):
                    job['state'] = 'dlq'
                else:
                    delay = min(32,2**job['tries']) if protected else 1
                    job['next'] = tick + delay + (rng.randrange(delay+1) if protected else 0)
                if protected and consecutive >= 3:
                    open_until = tick+5; consecutive = 0
        calls_by_tick.append(used)
    states = Counter(j['state'] for j in jobs)
    assert sum(states.values()) == count
    assert all(j['tries'] <= 5 for j in jobs)
    assert len(effect_ids) == states['done']
    return {'calls':total_calls,'states':dict(states),'peak':max(calls_by_tick),'jobs':jobs}
 
naive = retry_sim(False)
protected = retry_sim(True)
assert naive['states'] == {'dlq':40}
assert protected['states'].get('done',0) > 0
assert protected['peak'] <= 11  # 8 accepted calls plus at most 3 failures before opening
print('naive', {k:v for k,v in naive.items() if k != 'jobs'})
print('protected', {k:v for k,v in protected.items() if k != 'jobs'})

Interpretation: immediate retry spends the entire five-attempt budget before recovery, sending all 40 jobs to the DLQ. Spacing and breaker pauses allow work to reach the recovered dependency in this fixture. The breaker is reactive, not an 8-call hard rate limiter: a tick can include 8 successes and 3 failures before opening, hence the tested peak bound of 11. Compare successes, pending, diverted and calls, not calls alone: dropping everything can make a call-count graph look excellent. The timing bound is not a general guarantee under another outage duration or seed. Layered retries can multiply, so assign one budget across the request path.

Duplicate-effect exercise with an actual transaction: record processed ID and balance mutation together. An acknowledgement lost after commit leads to redelivery, not another increment. This is an in-memory SQLite transaction demonstration; it does not claim to atomically commit a remote payment.

import sqlite3
with sqlite3.connect(':memory:') as db:
    db.executescript('CREATE TABLE done(id TEXT PRIMARY KEY); CREATE TABLE total(n INTEGER); INSERT INTO total VALUES(0);')
    def consume(message_id, amount, fail=False):
        with db:
            inserted = db.execute('INSERT OR IGNORE INTO done VALUES(?)',(message_id,)).rowcount
            if inserted:
                db.execute('UPDATE total SET n=n+?',(amount,))
                if fail:
                    raise RuntimeError('transaction aborted before commit')
        return bool(inserted)
    assert consume('a',7) and not consume('a',7)
    try: consume('b',3,True)
    except RuntimeError: pass
    assert db.execute('SELECT n FROM total').fetchone() == (7,)
    assert consume('b',3)
    assert db.execute('SELECT n FROM total').fetchone() == (10,)

The business contract here binds one immutable amount to each message ID. A production record must store/check a payload fingerprint as well, or a reused ID with a different amount could hide an error. Acknowledge only after commit; protect deduplication retention relative to the redelivery horizon and investigate poison messages before redrive.

Recall quiz — proof obligations

1. What does R+W>N establish? Every selected read set intersects every selected write set on the same fixed membership; it does not alone establish the latest committed answer or a total order.
2. Three/four/five majority sizes? 2/3/3, with static crash tolerances 1/1/2. Four is not said to need the same majority as three.
3. Is election only about liveness? No: log freshness and one-vote-per-term rules contribute to safety; commitment preservation spans both election and replication.
4. Three hot-key remedies and costs? Cache reads (freshness), salt decomposable writes (merge/fan-out), or dedicate capacity (isolation but a finite ceiling).
5. Queue recovery recipe? Durable idempotent effects, failure classification, bounded attempts/time, backoff+jitter, bounded load, breaker/probes and an owned DLQ. A model pass does not promise every incident needs exactly the same four knobs.

Answer constraints and corrections

Majorities are two of three, three of four and three of five: the original claim that both three- and four-node clusters require three was wrong. Both sizes tolerate one crash under a majority-progress model. Raft safety additionally relies on log/election rules; the inequality alone is not its proof. Retry models assume an explicit failure and idempotency boundary.

Gap analysis + next week preview · 10 min

• Did you compute 2/3/3 majorities for three/four/five voters and separate intersection from commitment safety?
• Can you merge salted counts and state the fan-out/ordering cost before proposing salting?
• Can you account for done, DLQ and pending work and distinguish the reactive breaker from a hard rate limiter?

Mark each answer unaided, hinted or not yet; select a failed assumption and use a new counterexample for the retest rather than memorizing one fixture. Keep the input contract, boundary case and independent expected answer next to any execution result.

Next week: S076–S080 cover multi-region recovery, metrics/logs/traces, Prometheus/OpenTelemetry, SLOs and incident response. Use the failure, replay and consistency contracts above to define recovery and measurement.

Corrective source notes

• Apache Kafka 4.0 introduction and design — retained topic records, per-partition order, consumer-group offsets/replay and the external-effect coordination boundary. Exact official passages checked 2026-10-09.
• PostgreSQL 16 warm standby — PostgreSQL asynchronous log shipping admits acknowledged-data loss if the primary fails before logs reach a standby. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Gilbert and Lynch CAP proof, 2002 — Atomic/linearizable register operations respect real-time completed-write/read ordering; this differs from merely preserving process program order. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Lamport, sequential consistency (1979) — Lamport sequential consistency preserves each processor program order within one legal sequential execution; it does not add cross-process real-time precedence. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Azure Cosmos DB consistency levels — Cosmos product levels are Strong, Bounded Staleness, Session, Consistent Prefix and Eventual, not an invented six-rung universal hierarchy. Cosmos session guarantees depend on session-token/writer assumptions; read-your-writes is scoped, not a universal cross-client guarantee. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Fischer–Lynch–Paterson, impossibility of consensus (1985) — FLP shows possible nontermination with one unannounced crash in a fully asynchronous setting; practical progress requires further assumptions. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Raft extended paper, 2014 — Raft uses randomized election timeouts to reduce split votes; this is not a perfect failure detector. Election log freshness restrictions are part of Raft safety, not merely leader-selection convenience. Raft commits current-term entries by counting replicas and prior entries indirectly; generic quorum intersection alone is not this safety rule. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• MongoDB 8.0 shard keys — MongoDB uses ranges of shard-key or hashed-key values and placement chunks; hashing keys alone does not promise equal traffic. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Amazon SQS at-least-once delivery — SQS standard consumers must tolerate processing the same message more than once. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Amazon SQS visibility timeout - Amazon Simple Queue Service — Receiving a queue message hides it temporarily until deletion/timeout, not immediately deleting its business obligation. Standard SQS at-least-once behavior can duplicate a delivery even during visibility timeout; deduplication remains necessary. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.

These passages support the named propositions, not blanket product certification. The lesson-specific derivations and fixtures are separate evidence; runtime boundaries are stated beside each worked exercise.