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

• Single-leader store with asynchronous replication; every write carries a leader LSN or version the router can compare.
• Teaching numbers: lag is fractions of a second normally, seconds to minutes under stress; the one-minute leader window below is illustrative, never a guarantee.
• Replica installation and measurement belong to the extended lab; the interview discussion assumes one leader and two followers exist.

A one-minute leader-read window is a heuristic: lag can exceed it. Compare applied_version ≥ required_version because it directly proves that replica received the required write. Falling back after three seconds uses a user waiting budget, not a replication guarantee. Derive it from the remaining request deadline and distinguish freshness from response latency.

1. Write the three histories Write v7 is ACKed at LSN 7; follower A applies it at once, follower B still sits at LSN 5. Read-your-writes breaks when the first read hits B and sees v5. Monotonic reads break when the second read hits A (v7) and the third hits B (v5): time moved backward. Causal order breaks when reply@7 is read from A while its question@6 never reached B: answer before question.
2. Read-your-writes: pay for the leader Route reads of keys the user may just have written to the leader (or a synchronous follower): always fresh, always costs leader load. The one-minute all-from-leader window and dropping over-lagging followers from the read path are the same idea with a timer — honest only as a heuristic, because lag has no bound.
3. Monotonic and causal: pin or compare Monotonic reads come from pinning each session to one replica (hash of the user ID is the simple form) or from carrying a seen-version floor the answering replica must beat. Causal order needs more: keep causally related writes on one shard, or ship explicit dependencies. Multi-device sessions must keep the last-write metadata central, or the laptop regresses what the phone wrote.
4. No bound: fall back, never sleep A fixed sleep proves nothing: a stalled follower sleeps through it. The version barrier refuses stale replicas with evidence (5 < 7), and when no follower qualifies the router falls back to the leader. If even that is too costly, stop pretending async is synchronous and buy a stronger database — linearizable plus ACID — instead of complicating the application.

The read router takes three inputs: the session lastLsn, a replicaLsn table, and an ownWrite flag. Own-write reads go straight to the leader; other reads go to a replica whose replicaLsn is at least lastLsn, else the leader. The user partition key doubles as the stickiness key, and every read returns the version it saw so the session can raise its floor.

Write v7 lands at LSN 7; A sits at 7 and B at 5. The first read needing 7 reaches B and is refused (5 < 7), so it goes to the leader; the second read reaches A and is admitted with v7 (7 >= 7). If both followers stall at 5 while the leader advances to 9, every read needing 7 falls back. All numbers are teaching numbers.

• Fixed sleep before reading: cheapest to write, guarantees nothing — keep it only as a latency-hiding heuristic with the barrier still enforcing correctness.
• Synchronous or semisynchronous replication: followers are fresh by construction, but one slow follower stalls every write — freshness moved its price to availability.

• Primary dies right after ACK with async replication: ACKed-but-unreplicated writes are lost, so read-your-writes to the new leader misses the user's own write. Guard: semisynchronous replication or state the loss window honestly.
• Pinned replica dies and the session re-pins to a staler one: monotonic reads regress silently. Guard: carry the seen-version floor across the re-pin and refuse replicas below it.

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

Expected output: read-your-writes routes to A; the second read pinned to B is refused for A; causal on B@5 is unsafe for A; unbounded lag falls back to LEADER; closing OK. (actual output of this environment)

• Sleeping a fixed time after writing and calling it consistency. Lag has no bound; a stall outlives any sleep, and the sleep still taxes every read.
• Pinning a session to one replica and claiming read-your-writes. Stickiness stops backward time; it says nothing about a write that landed elsewhere.
• Comparing wall-clock timestamps instead of versions. Clocks skew across machines (that is Chapter 9); only LSNs or version vectors order writes.

• Two devices share one cart, both saw {milk:t1, bread:t2}, then go offline; no fresh adds in phase one.
• No synchronized clocks: timestamps order nothing across devices, tags are unique per add.
• Phase two adds exactly one concurrent fresh add (milk@t3 minted offline); teaching scenario, neutral cart items.

Unique add tags preserve operation identity. Removes record observed tags, so merging removal sets preserves both offline deletions. An unseen fresh add has another tag and survives add-wins semantics. Plain sibling value union lacks this history and can resurrect both items. GC requires evidence that old tags cannot return through replicas or messages; elapsed time without membership rules is insufficient.

1. Observed removals must converge A removes milk having seen t1, B removes bread having seen t2. Union of adds is {milk:t1, bread:t2}, union of removes is the same set, so live is empty on both devices after sync. Nothing resurrects — this is the convergence bar every strategy must clear.
2. LWW votes whole carts Last-write-wins compares one timestamp per cart and keeps the whole winner: if B's clock runs ahead, A's milk removal vanishes and milk is back on the shelf. One lost update per conflict, silent by design, and device clocks skew — the survivor is arbitrary, not correct.
3. Siblings bill a human Sibling union keeps both carts side by side and asks someone to merge them. Nothing is lost, but nothing converges either: right for rare conflicts a person should inspect, wrong for a cart that must check out while offline.
4. OR-Set: tags, then the product call The OR-Set files adds and removes separately and computes live as adds minus removes: observed removals converge exactly. Then B's fresh milk@t3 — minted offline, never saw the remove — survives the subtraction. Add-wins keeps milk, remove-wins cancels even the unseen tag. Same history, two defensible carts: write the rule in the spec.
5. Forget only on stability Bread's t2 tombstone may be forgotten only once every live replica has seen the removal — causal stability. A device offline for a year has not seen it, so it vetoes collection; a lone timer would resurrect bread the day that device syncs.

The OR-Set state is two maps: adds from item to tag sets and removed from item to seen removed tags. add mints a fresh tag, remove files only seen tags, and merge unions both maps; live is their difference. The add-wins/remove-wins rule is a configuration flag beside the merge, not part of the math.

Start {milk:t1, bread:t2} on both devices. Phase one: A removes milk, B removes bread — union of adds equals union of removes, so the cart is {}. Phase two: B's fresh milk@t3 joins adds but not removes, so live is {milk:t3} under add-wins and {} under remove-wins. The t2 tombstone stays until causal stability.

• LWW when conflicts are rare and loss is acceptable: one timestamp, no tombstones, no GC problem — but never for carts, where every conflict carries user intent.
• Central arbiter per cart (one writer orders all edits): perfect agreement, zero offline writes — contradicts the offline-first premise of the exercise.

• Year-offline device returns after premature GC: its converged state still carries bread@t2 as live, and the merge resurrects bread everywhere. Guard: collect a tombstone only past causal stability, or block the straggler's sync until it catches up.
• Reused tag across two adds: the remove files one tag and kills both items' presence. Guard: tags must be unique per add (device ID plus counter is the teaching form).

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

Expected output: phase one merges to an empty cart with no resurrection; phase two gives [t3] under add-wins and [] under remove-wins; GC rule and closing OK. (actual output of this environment)

• Deleting the key and calling it a remove. Without filing the seen tags, the next sync with a replica that still holds them resurrects the item.
• Reading the biggest timestamp as the correct value. LWW orders writes by skewed clocks; it never detects concurrency, it just picks a survivor.
• Expiring tombstones by age. Time does not prove delivery; only causal stability lets a tombstone retire without resurrection.

• Five replicas, w=3, r=3; versions v6/v7/v8 order all writes, no log order exists.
• Teaching cadence for the probe (every 10 seconds) and teaching bounds; production numbers come from measurement.
• Membership is fixed except in the rebalancing scenario, where old and new member sets are named explicitly.

Inclusion–exclusion gives |W∩R|≥|W|+|R|−n; 3+3−5 means at least one shared member. This set proof cannot establish durable contents or replacement history. A ten-second probe interval trades monitoring cost against detection delay: shorter costs more and detects sooner. Version distance cannot become seconds without a production-rate/time reference and uncertainty model.

1. Count what the sum promises Count the arithmetic: C(5,3) sets pairwise intersect in at least one node, so write quorum and read quorum always share a bridge member. That is all the inequality ever says.
2. Walk the happy history Walk the happy versioned history: v7 lands on {n1,n2,n3} with three ACKs; the read of {n3,n4,n5} finds v7 on the bridge and v6 elsewhere, and takes the max. Versions ride writes; the max crosses the bridge.
3. Break the premises, not the sum Break each premise in turn. Lost ACKs: v8 sits on three nodes while the coordinator reports failure — the next read returns the failed write. Stale replacement: n3 is rebuilt from a v6 snapshot and the same overlap carries v6, missing v8. Membership: a read from new members never met the old write set — the sum was computed over two different fives.
4. Probe versions, not seconds Monitor without a log order: probe all five for newest versions, report max, min and the behind-set, and page past a teaching bound with the matching scenario attached. Rebalancing is watched separately with joint quorums.

The staleness monitor is a sampled version prober over all five replicas (teaching: every 10 seconds), a metric of max - min plus the behind-set, a dashboard that shows versions per replica, and a pager that fires past a teaching bound with the matching scenario attached (lost ACK, rebuild, or move). Rebalancing gets a separate joint-quorum watch: old and new quorums must overlap each other, not just themselves.

• Read repair (write back the max version to a quorum before returning): heals laggards on the read path, but a lone background repair without a read-time promise is not linearizability.
• Bigger write quorum (w=5): every later read sees the write, at the price of write latency and availability — the single-leader log buys the same with less.

• Coordinator reports failure while the write sits durable (lost ACKs): a naive retry writes v9 over v8 and forks intent. Guard: fence retries with versions — read before rewriting, or carry the write's identity.
• Replica rebuilt from an old snapshot rejoins and serves reads: every quorum containing it reports older versions. Guard: rebuilt nodes must catch up past the acknowledged frontier before serving, the leaderless cousin of the deletion watermark.
• Concurrent rebalancing moves data while quorums are drawn from both memberships: neither quorum overlaps the other. Guard: joint quorums — require overlap between old and new sets until the move completes.

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

Expected output: happy path sees v7 via {n3}; lost ACKs show a FAILED v8 still readable; stale replacement misses v8; membership overlap is empty; probe reports max/min/behind; closing OK. (actual output of this environment)

• Reading w + r > n as a freshness promise. It promises an intersecting node; freshness additionally needs ACK durability, bridge memory and one membership.
• Treating a reported failure as a rollback. A failed write may sit durable on three nodes and surface in the next read — retry accordingly, with versions.
• Measuring staleness in seconds. Without a log order there is no global clock to be seconds behind; versions and behind-sets are the honest units.