حل آموزشی تمرین‌های فصل 9Chapter 9 exercise solutions, explained

• One counter service, one client, at-most-two attempts per request in the demo (teaching numbers).
• Layered-retry math uses 3 layers x 3 attempts each (teaching numbers) — the shape matters, not the constants.
• The result log keeps (request ID, payload hash, result) past the maximum retry window (teaching retention) — retry after the window is fail-loud, not guesswork.

Timeout proves no response arrived, not that execution did not happen; retry the same intent with the same ID. Three layers with three attempts can cause 3×3×3=27 downstream calls because each upper attempt repeats lower attempts. Shared deadlines, retry budgets and jitter bound load. Two demo attempts expose duplication; production counts depend on transient errors and spare capacity.

1. Timeout is not 'not executed' Name the unknown first: a timeout fits three histories — request lost (nothing applied), server dead (maybe applied), reply lost (applied, unconfirmed). No client-side evidence separates them, so the design must work under all three.
2. Same ID, stored result Give the intent one ID and the server one memory: the client mints a UUID per intent and keeps it across retries; the server inserts-or-looks-up (ID, payload hash, result) atomically, returning the stored result on repeats.
3. Bind payload, retain results Bind the ID to the payload and keep it past the retry window: the same ID with a different payload is rejected (client bug, caught loud), and lookups after retention expiry fail loud instead of applying blind.
4. Budget the layers Bound the storm, not just the attempt: per-attempt deadlines cut tails, backoff plus jitter spreads the herd, and a shared retry budget sheds load — 3 layers x 3 attempts peak at 27 downstream tries in the teaching math.

Request ID: one UUID per caller intent, minted by the client before the first send and kept across retries. Server table (request_id UNIQUE, payload_hash, result, kept_until): on arrival, insert-or-lookup in one atomic step — a present ID returns its stored result (or rejects on payload mismatch), an absent ID applies once and stores. Retention covers the longest retry window plus clock slack; reads after expiry fail loud. Every retry carries the same ID, a per-attempt deadline, backoff with jitter, and charges a shared retry budget that sheds load when the downstream is slow.

Teaching math: 3 layers, up to 3 attempts each, so the worst downstream fan-out is 3 x 3 x 3 = 27 attempts for one caller try. A shared retry budget of a teaching 10% of traffic means the 28th concurrent retry waits or fails loud instead of joining the stampede. Backoff with jitter spreads the survivors: without it all 27 arrive in lockstep; with it they spread across the backoff window and the downstream recovers between waves.

• Read-back-first when the outcome is queryable ('did you apply req-7?'): one lookup can settle the unknown without any retry policy. Cheaper than full idempotency when reads are cheap and the result log is indexed by request ID — but useless when the operation has no readable state.
• Fail-loud when the operation is neither idempotent nor queryable: return an explicit error and let a human or a higher layer reconcile. Costs a visible failure, buys zero corruption — the right trade when a double charge is worse than a rejected request.

• Retry storm on a slow downstream: without a budget every client hammers at once and layered retries multiply (up to 27x). Guard with a shared retry budget, backoff plus jitter, per-attempt deadlines, and load shedding when the budget drains.
• Result-log entry lost before retention ends (disk loss, early expiry): a retry then looks new and double-applies. Guard with durable, replicated result storage and fail-loud after the retention window instead of guessing.
• Payload confusion: two different caller intents share one ID (client bug). The binding check rejects the second payload — loud, safe, and debuggable — instead of silently applying the wrong intent.

Run: javac TimeoutDemo.java && java TimeoutDemo — stdlib Java only, instant.

Expected output: Six scenario lines: naive retry double-applies only in APPLIED_REPLY_LOST (counter=2, effects=2); same-ID retry keeps counter=1 and effects=1 in all three truths. Then 3^3 = 27, the payload-mismatch REJECTED line, and the OK line. (actual output of this environment)

• Reading a timeout as 'it did not execute' and blindly resending: in the lost-reply case the effect already exists, so the resend doubles it. Timeout means unknown — always.
• Minting a fresh request ID per attempt: the server cannot link the retry to the original, so dedup never fires and every retry is a new charge. The ID belongs to the caller intent, not to the attempt.
• Unbounded retries at every layer: three innocent-looking 'retry 3 times' policies stack into 27 downstream attempts, and without jitter they arrive in lockstep. Bound attempts globally with a budget, not just locally with a count.

• Demo numbers are teaching MOCKS: +250ms B-ahead skew, 40ms sample RTT, -500ms NTP step, 120ms of real work.
• Two hosts means two independent clocks (separate VMs/hosts); one host with two containers means one clock.
• LWW register keeps the value with the greatest wall timestamp, ties broken arbitrarily.

RTT/2 estimates one-way delay under symmetry; it is not a measured one-way delay. Asymmetry shifts offset estimates, so timestamp exchange should report a possible interval with processing and drift accounted for. The 250ms skew and 500ms step make the effect visible; skew exceeding the true write separation can reverse LWW order. Monotonic clocks measure local duration without wall-clock steps.

1. One job per clock Split the clocks by job: monotonic (CLOCK_MONOTONIC) for how-long on one host — durations, timeouts, TTL waits; wall (CLOCK_REALTIME) for what-time for humans and logs. The demo's NTP step turns 120ms of work into a -380ms wall duration while monotonic stays exact.
2. Two hosts plus uncertainty Measure real skew on two independent hosts or VMs: exchange timestamps, halve the RTT for the uncertainty (40ms RTT gives +-20ms), and report raw diff plus uncertainty plus method. Containers on one host share the clock — that experiment measures ~0 by construction.
3. Mock openly or not at all When you cannot use two hosts, mock openly: inject a stated shift (+250ms on B), label every shifted number MOCK, and keep the uncertainty math identical. A mock teaches the mechanism; only the label keeps it from becoming a false measurement.
4. Wall stamps never arbitrate Never order on wall: with B 250ms ahead, B's truth-t write (stamp t+250) beats A's truth-t+100 write (stamp t-400) — LWW keeps the earlier write and drops the later one silently. Cross-host last-write needs causality or an uncertainty wait, never a stamp compare.

Teaching numbers from the demo run: B ahead by a MOCK 250ms; one sample over a MOCK 40ms RTT reports rawDiff=250ms with uncertainty=+-20ms — the true skew sits somewhere in 230..270ms, and a second sample could legitimately disagree by 40ms. The MOCK NTP step of -500ms mid-measurement turns 120ms of real work into a wall duration of -380ms: negative time, the signature of a stepped clock. LWW then compares stamp t+250 (truth t) against stamp t-400 (truth t+100) and keeps the earlier write.

• TrueTime-style uncertainty waits: when you have a bounded clock uncertainty epsilon, a writer waits epsilon past its timestamp before committing, turning wall time into safe order at the cost of latency. Right when cross-host order on wall stamps is unavoidable — overkill for timeouts and durations, where monotonic is free.
• Logical clocks for order: Lamport timestamps or version vectors decide 'who wrote last' from causality, not from wall readings. Right whenever writers live on machines whose clocks you do not trust — which, across hosts, is always.

• NTP steps the wall clock backwards: every wall-measured duration, timeout and TTL in flight lies at that moment (the demo shows -380ms for 120ms of work). Guard by measuring all spans on the monotonic clock; wall is for stamps only.
• Cross-host monotonic compare: monoA=999 against monoB=5 looks decisive and means nothing — different zeroes, different rates. Guard by never comparing them; order across hosts needs logical clocks or uncertainty intervals.
• Single-host 'skew experiment': two containers on one host share the underlying clock (unless time namespaces split them), so the measured diff is ~0 and proves nothing about real skew. Guard with two independent hosts/VMs, or label the shift MOCK and report the RTT-based uncertainty.
• Wall-stamped LWW across writers: the ahead clock's earlier write wins over the later real write, silently. Guard by never ordering on wall stamps — use per-key causality, logical clocks, or an uncertainty wait.

Run: javac SkewDemo.java && java SkewDemo — stdlib Java only, instant.

Expected output: Five lines: the MOCK sample (rawDiff=250ms, uncertainty=+-20ms), the NTP step (wall duration=-380ms lying, mono 120ms true), LWW keeping from-B, the meaningless monoA=999 vs monoB=5 compare, and the OK line. (actual output of this environment)

• Measuring 'skew' with two containers on one host: same underlying clock, ~0 diff, zero information about real divergence. Independence means separate kernels Clocks, not separate namespaces.
• Comparing monotonic readings across hosts (monoA vs monoB): each starts at its own boot and ticks its own rate — the comparison is numerology. Monotonic is strictly single-host.
• Ordering writes by wall timestamps (LWW on wall): the fastest liar wins — an ahead clock's stale write beats a later honest one with no error. Wall stamps record, they do not arbitrate.

• Epochs 7 then 8, one paused holder A and one successor B (teaching scenario from the brief).
• The lock service issues durable, monotonic epochs; storage compares and writes atomically (single synchronized step in the demo).
• An op_id uniquely identifies a logical operation and remains unchanged across its retries; retain dedup while valid redelivery remains possible.

Epoch numbers order ownership; any increasing pair can replace 7 and 8. Reject token<highest so the current owner can perform multiple same-epoch writes; requiring token>highest for every write wrongly rejects its second operation. Keep op_id stable across retries of one operation. Persist highest and dedup with data because restart erases process memory.

1. Expiry cannot stop a sleeper See why expiry is not safety: A's lease ends, B is granted epoch 8, but paused A never learns this — its epoch-7 write arrives later in full confidence. Any guard that lives in A's head (timers, lease clocks) cannot guard a sleeper.
2. Reject stale epochs in storage Move the verdict into storage: every write carries (token, opId); storage atomically rejects token below highest-seen, records the new highest, and only then applies. The paused writer is disarmed at the data, not at its own clock.
3. Epoch for turn, op for attempt Split the two identities: the epoch says whose turn it is (one live epoch per resource), the operation ID says which attempt this is. Same epoch plus new op is a second legitimate write; same epoch plus seen op is a retry to absorb.
4. Durability is the fence Persist the verdict: highest-seen and the applied-op set live on durable storage with the data, written before the ack. A restart that forgets them accepts stale epochs — the demo's HAZARD line — so memory alone is a fencing bug.

Lock service: issue() returns a durable, strictly monotonic epoch per lease grant (one per epoch, not per write) and persists the counter before answering. Storage write path, one atomic step: if token < highest: reject; highest = token; if opId seen: dedup; else apply. The highest-seen epoch and the applied-op set both live on durable storage, replicated with the data — memory alone reopens the split brain on restart. Token allocation rule: exactly one live epoch per resource; a new grant always exceeds every earlier one, even across lock-service failover.

• Lease expiry alone ('A's lease ended, so A cannot write'): works only if every participant obeys the lease clock — a paused process never got the memo. Cheaper (no token plumbing), but it trusts the very node that is, by hypothesis, unreachable. Use only where pauses are bounded and measured, never across GC or VM pauses.
• Single-writer fencing via consensus (Raft/ZAB term as the epoch): same shape, stronger issuer — the epoch comes from an elected leader term instead of a lock service counter. Right when the lock service itself must survive failures; heavier than a counter, and still enforced at the storage check.

• Lease-expiry-only fencing (the no-fence line): A's stale write overwrites leader=B with leader=A — no error, two truths. Guard with the storage-side token check; expiry moves ownership, only the check enforces it.
• Restart amnesia: highest-seen kept in memory is forgotten on crash, and the next stale write applies — the HAZARD line in the demo. Guard by persisting highest-seen (and the op set) on every accept, before acknowledging.
• Same-epoch duplicate without op dedup: B's retried op-b2 would apply twice (x=1 written twice — harmless here, a double charge elsewhere). Guard with the applied-op set as a separate concern from the epoch compare.
• Forked token issuer: two lock services (or a failover that resets the counter) hand out the same epoch twice, and fencing compares equal against equal. Guard with a single issuer per resource — consensus term or fenced counter — so epochs never fork.

Run: javac FencingDemo.java && java FencingDemo — stdlib Java only, instant.

Expected output: Nine lines: B's epoch-8 write ACCEPTs, A's epoch-7 write REJECTs as stale, B's second same-epoch write ACCEPTs, its retry DEDUPs, final leader=B; then the no-fence overwrite (leader=A) and the restart-amnesia HAZARD (stale 7 accepted); OK line. (actual output of this environment)

• Trusting lease expiry to stop a paused writer: expiry is a clock reading, and the paused process cannot read clocks. The stale write arrives after expiry with full confidence — only the storage check stops it.
• Minting one token per write instead of per epoch: then 'stale' has no meaning — every token is fresh, the compare passes everything, and the paused writer sails through. The token must name the ownership generation, shared by all its writes.
• Keeping highest-seen in memory only: it works until the first restart, then every old epoch is young again. Durability is not an optimization here — it is the fence.

• One queue consumer, string message IDs, redelivery possible after any crash or partition (at-least-once transport).
• Effects are per-message counters in the demo (teaching stand-ins for real application effects).
• Liveness deadlines are teaching bounds ('eventually' always ships with a stated time, network and capacity assumption).

Safety excludes forbidden states in every permitted execution; one counterexample refutes it. Liveness requires eventual completion under network, processor and capacity progress assumptions; a finite timeout test cannot prove it universally. An operational deadline differs from theoretical eventually. At-most-once can prevent duplicates while discarded messages destroy business progress.

1. Effects, not deliveries Count effects, not deliveries: the wire may duplicate, lose, or reorder — the application effect per message ID is the only thing the business feels. 'Applied once per ID' is the safety sentence; everything else is transport.
2. Dedup that survives Enforce safety with surviving dedup: check-then-apply under one atomic step, persisted before the ack, so the restart that triggers redelivery cannot wipe the memory of the first effect. Dedup is the fence; the set is its posts.
3. Liveness with assumptions Bound liveness with three named assumptions: the partition heals within H, consumer capacity stays above arrivals, and every valid message effects within T. A permanent partition then breaks exactly the assumption it names — liveness violated, safety untouched.
4. Four cells, independent Prove independence with the four-cell matrix: redelivery holds both, partition breaks liveness only, dedup-loss breaks safety only, reject-all holds safety vacuously with liveness dead. Any property that cannot break alone is two properties wearing one name.

Consumer state, two structures: dedup: Set[messageID] (seen means effected) and effects: Map[messageID, count], updated in one atomic step — check-then-apply under the same lock, persisted before the ack. Delivery contract: at-least-once transport with unbounded redelivery; the consumer absorbs all of it. Liveness contract, stated per queue: valid messages take effect within T provided the partition heals within H and consumer capacity stays above arrival rate — a bound with three named assumptions, not a bare 'eventually'.

Teaching matrix from the demo run: redelivery of m1 with dedup gives effects={m1=1, m2=1} — SAFETY HOLDS, LIVENESS HOLDS. A permanent partition (m3 never arrives) — SAFETY HOLDS on nothing-applied-twice, LIVENESS VIOLATED on never-effected. Dedup wiped across restart gives effects={m1=2} — SAFETY VIOLATED, LIVENESS HOLDS. Reject-all gives effects={} — SAFETY HOLDS vacuously, LIVENESS VIOLATED. Four cells, four verdicts, zero shared fate.

• At-most-once delivery as the safety statement ('each message delivered at most once'): simpler to observe on the wire, but a lost message is then a safety-preserving data loss — it hides progress failures inside a green light. Prefer the effect-based statement unless the transport truly cannot redeliver.
• End-to-end acknowledgments plus operator replay for liveness: instead of promising automatic progress, promise detection (every un-acked message is visible) plus a runbooked replay path. Right when automatic redelivery is unsafe (non-idempotent effects) — liveness becomes a human-in-the-loop bound, stated honestly.

• Permanent partition: the valid message never arrives — liveness violated, safety untouched. Guard with the stated healing assumption plus buffering and replay on heal; without the assumption the liveness claim is a wish.
• Dedup state lost across restart: the redelivery that healing brings double-applies — safety violated while liveness holds. Guard by persisting the dedup set before acking, replicated with the effects.
• Reject-all outage (poison config, closed gate): every message refused — safety vacuously green, liveness dead, and the dashboard lies by omission. Guard with a progress metric (effected-per-minute) beside every safety light, paging when progress hits zero.
• At-most-once delivery sold as 'no duplicates, no loss': a dropped message is counted as success by the safety metric while the business effect never happens. Guard by stating effects, not deliveries — count effected messages, redeliver the rest, and let liveness own the gap.

Run: javac SafetyLivenessDemo.java && java SafetyLivenessDemo — stdlib Java only, instant.

Expected output: Four scenario lines: redelivery+dedup (both HOLDS), permanent-partition (safety HOLDS, liveness VIOLATED), dedup-lost (safety VIOLATED with effects={m1=2}, liveness HOLDS), reject-all (safety HOLDS vacuously, liveness VIOLATED); plus the OK line. (actual output of this environment)

• Stating safety on deliveries ('at most once') and calling it done: a lost message preserves at-most-once delivery while the business effect vanishes. Safety must be stated on effects, or loss hides inside the guarantee.
• Promising liveness without recovery assumptions ('every message is eventually delivered'): eventually is not a time, a partition is not a delay, and a full disk is not a network. Unconditional liveness is a wish — name heal, capacity, and deadline or withdraw the claim.
• Reading safety-green as healthy during a reject-all outage: zero effects means zero duplications, so the light stays green while the business stands still. Every safety dashboard needs its progress twin.