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

• 8 shards and 120k teaching writes over 30 days from 51 sensors; sensor-0 holds 40% of writes (fixed seed 7).
• Instantaneous load is one shard's share of one day's writes; monthly load is its share of the whole month. Fan-out is the shards touched by one query.
• Numbers are teaching aids, never benchmarks; the pattern (which shard heats) matters, not the exact figure.

Partition keys determine query fan-out and hotspots. Hash(sensor_id) keeps a hot sensor’s writes together, so a 40% sensor does not spread merely by adding shards. Sensor/time buckets permit splitting at the cost of long-range fan-out. Eight shards and seed 7 make the experiment repeatable. Load share is shard writes / total writes, normalizing comparisons across sample sizes.

1. Name the query first The dominant query is 'one sensor, one month', so we want the range family: key closeness must survive for a range scan to work. That single call removes full-key hashing from the table unless writes outweigh reads.
2. Measure both clocks Timestamp ranges look even monthly (max 13.5%) yet 100% of day 15 lands on one shard — today's shard is always hot. sensor:timestamp sits near 47% on the hot sensor's shard on both clocks: honestly hot, but predictable.
3. Price the hash options hash(sensor_id) keeps reads single-shard but burns time order into a full-shard scan. Full-key hashing spreads writes perfectly (max 12.6%) but drags the same query across 8 shards. Neither cures one hot key's load.
4. Guard and retire Split the 40% sensor with a 00..99 suffix into 100 sub-keys: writes spread, reads merge 100 pieces. Split the hot range (never rehash the world) and drop old months whole-shard by retention. Tripwire: alert when one shard's instantaneous share passes 3x the mean.

Key sensor_id:timestamp; owner = sensor_id % 8 (teaching mapping). Write path: append to the owning shard. Read path for 'one sensor, one month': a single range scan on that shard. A hot-sensor registry adds the 00..99 suffix to sensors above 10%. Retention drops whole old-month shards, never row by row.

Actual demo output (ShardSim): monthly maxima 13.5 / 47.2 / 48.5 / 12.6% and day-15 maxima 100 / 47.0 / 48.1 / 13.1% across the four schemes; 'one sensor, one month' fan-out 8 / 1 / 1 / 8. Timestamp ranges spread the month beautifully and the second terribly.

• If one-sensor-month reads are rare and writes flood in, take full-key hashing: perfectly even writes, 8-shard reads. Accept the merge price openly instead of discovering it in review.
• If the dominant query is 'all sensors in one day', timestamp ranges win: one day lives on one shard. Price: today's shard is always hot — roster capacity for it.

• The sensor grows from 40% to 70% and 100 sub-keys still fill one shard. Guard: a dedicated shard for that sensor (hot key, lonely shard) or a write quota. Without a guard the whole shard sleeps.
• A sensor's late data arrives after its month closed. Guard: last month's shard stays writable for a short grace window (teaching: a few days), then read-only; later data is dropped and counted, never silently lost.
• Losing a shard hides its sensors' months. This scheme needs replication separately (Chapter 6): each shard keeps several copies and reads go to a healthy one.

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

Expected output: Monthly max shares 13.5 / 47.2 / 48.5 / 12.6% and day-15 max shares 100 / 47.0 / 48.1 / 13.1% for ts-range, sensor:ts, hash(sensor), hash(full); one-sensor-month fan-out 8 / 1 / 1 / 8; OK. (actual output of this environment)

Per-shard write counters; alert past 3x-mean instantaneous share; assert fan-out per query type (single-sensor must be 1); periodic drill: drop one month and verify it vanishes from every read path.

• Monthly totals suffice for sizing. Day 15 at 100% on one shard disproves it — always measure the instantaneous clock too.
• hash(sensor) equals hash(full key). Fan-out 1 versus 8 says otherwise: the hash input, not the hash itself, decides the query.
• A random prefix spreads reads too. It spreads writes only; reads must fetch and merge all 100 sub-keys — say both halves.
• Retention means deleting rows from the table. It means dropping whole old shards — row deletes at this scale are the expensive path.

• 10k keys, cluster 10 to 11 and 10 to 9; a stable FNV hash with an fmix finalizer (teaching choice, tested, not a standard).
• Ring carries 100 virtual nodes per physical node; fixed scheme uses 64 logical shards with an explicit ownership table.
• Movement percent is measured key by key; skew (min..max load) and weight behavior are reported beside it, never hidden.

Under ideal uniform distribution, an eleventh node takes roughly 1/11 of keys; this is an expectation, not a finite-ring guarantee. One hundred vnodes reduce share variability at metadata cost; choose the count from skew and node weights. Sixty-four logical shards separate data identity from ownership, but moving ownership still needs data transfer, replication and fencing.

1. Draw the ring by hand Hash each key to a ring point and walk clockwise to the first virtual node — 100 per physical node smooths key counts to 840..1164 at 10 nodes. A join takes exactly the arc between its neighbors.
2. Count the moves Count key by key: mod-N moves 90.8% on 10 to 11 while ring, rendezvous and fixed shards all move ~9%; leaves mirror joins. The pink cell is the whole argument against node-count-inside-mapping.
3. Weigh without rehash A 2x node takes 2x virtual nodes (or 2x logical shards): only its portion grows, every existing key stays put. Raw FNV stole 40% for node n10 until an fmix finalizer fixed the avalanche — test the hash, then trust the shares.
4. Split routing from movement Movement and routing are separate events: data streams first, the versioned map flips second, stale clients forward through the old owner. A leave rehomes only its own ranges while replicas promote locally.

Ring with 100 virtual nodes per node; the ownership map is versioned (v41, v42, ...). Join protocol: stream the joining node's ranges, catch up on fresh writes until lag is near zero, flip the map atomically, forward in-flight requests from the old owner. A leave mirrors the join. Each range keeps two replicas that promote locally, so a single dead node never blocks its ranges.

Actual demo output (HashRing): mod-N 90.8 / 89.9%, ring+vnodes 8.8 / 8.7% at load 840..1164, rendezvous 9.2 / 9.9%, fixed-64 8.7 / 9.3% for 10->11 / 10->9. Bonus finding: raw FNV let n10 win 40% of keys — the fmix finalizer restored ~1/11 each.

• Rendezvous (highest random weight) when you want no ownership map at all: placement is a stateless computation per key, so any node can route. Price: O(nodes) hash computations per lookup and weights need explicit virtual copies.
• Fixed logical shards (say 64) when operations wants coarse, visible moves: a join takes whole shards, and the ownership table is human-readable. Price: pick the count with many divisors up front — resharding later rewrites everything.

• The joining node dies mid-copy. Guard: the map never flipped, so the old owner still serves and the partial copy is discarded data — abort is safe by construction.
• A client with a stale map writes to the old owner. Guard: the old owner forwards or rejects during the window, and the write is idempotent on retry — never silently lands in the wrong place.
• All replicas of one range go down together. No mapping trick helps: the range is unavailable until a copy returns — say so instead of inventing a third copy on the spot.

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

Expected output: mod-N moves 90.8 / 89.9%; ring+vnodes 8.8 / 8.7% (load 840..1164), rendezvous 9.2 / 9.9%, fixed-64 8.7 / 9.3% for 10->11 / 10->9; weighted join needs no full rehash; OK. (actual output of this environment)

Bound moved keys on join and leave (~1/N each); bound per-node load (min..max within ~1.5x mean); assert identical mapping across restarts (stable hash); assert a 2x node's share lands near 2x mean.

• 'Consistent' means replica consistency or ACID. Here it means a key's tendency to stay in its shard — the name is about stability, not correctness.
• Java's hashCode (or any language hash) is fine for sharding. It may change between processes and versions — sharding needs a frozen, tested function, and the raw-FNV episode proves even a decent hash needs its avalanche checked.
• Virtual nodes fix hot keys. They smooth key counts only; one hot key still lands whole on one node — load needs isolation or splitting, not more vnodes.
• Movement percentage is the only metric. Skew, weight behavior and the routing story decide as much — report all three or the comparison lies.

• 4 base shards owning records by id, 2 global index shards owning postings by hashed term; each record carries 2 terms.
• An RPC is one shard request; the measured unit is shards engaged per operation — never milliseconds, which predict nothing about networked p99.
• Index writes travel through a versioned outbox relay; readers can always reach the base shard for revalidation.

A local term index queries all four base shards because the term does not identify record placement. A global term index routes directly but adds outbox/index maintenance. Count RPCs as structural cost: four local SQLite instances do not model network latency. Authoritative validation matters because asynchronous indexes may not yet reflect deletions or ACL changes.

1. Write both paths A local write touches exactly one base shard with its entry in the same commit; a global write commits to the base plus one versioned outbox event per term, applied to each owning index shard. Count base and index shards separately — the audit signal demands it.
2. Read one term, then two Local term queries scatter to all 4 shards and merge (tail latency follows the slowest); global single-term reads hit 1 index shard, then fetch records by id. Two-term AND intersects postings over the network — slow exactly when the lists are long.
3. Break one write A lost brand-index write makes the AND query silently drop a live record (false negative); a lingering posting serves a deleted record (false positive). Both are partial-failure shapes of non-atomic multi-shard writes, and the demo counts each.
4. Contract and tripwires The reader revalidates every id against its base shard and the recorded delete always wins; tripwires fire on fan-out equal to shard count, per-term relay lag, and any index purge without a tombstone first.

Base shards own records by id % 4; index shards own terms by hash(term) % 2. A write commits to its base shard plus one versioned outbox event per term; the relay applies each event to the owning index shard with per-record versions. Reads: local scatters to 4 and merges; global looks up each term on 1 index shard, intersects, then fetches by id. Every fetched id is revalidated against its base shard before it reaches the caller.

Actual demo output (IndexSim): 12 records over 4 base and 2 index shards. Single-term color=red: local 4-shard scatter, global 1 index + 3 base shards. Two-term red AND a: local 4 scatter, global 2 index + fetch. Partial write: the AND query misses id 12. Stale entry: deleted id 3 is filtered at revalidation, phantoms = 1 caught.

• Stay local when queries carry the base key or want just a few results: any single shard answers, no cross-shard write ever exists. Price: the day someone asks for 'all matches', you scatter — name that day in advance.
• Accept async global (DynamoDB-style) when bounded staleness is tolerable: reads stay targeted and writes return fast. Price: an explicit lag SLO plus the reader-revalidation contract below — staleness without a contract is a bug report waiting.

• The outbox relay stalls: base writes march on while the index freezes in the past. Guard: a per-term lag metric with a paging threshold, plus a documented stale-read mode — never silent staleness.
• One index shard goes down mid-query: its terms vanish from AND results. Guard: declare the degraded mode explicitly (partial results flagged, or fail closed for strict queries) — the worst answer is a confident incomplete one.
• A base delete races a two-term read: the reader fetches an id the base just dropped. Guard: revalidate every id against the base and let the delete win — plus per-record versions so an older index event can never resurrect it.

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

Expected output: Write 1 record: local 1 shard, global 1 base + 2 index. Single-term read: local 4-shard scatter, global 1 index + 3 base. Two-term: local 4 scatter, global 2 index + fetch. Partial write: AND misses id 12. Stale entry: deleted id 3 filtered, phantoms=1; OK. (actual output of this environment)

Assert shards engaged per operation (local reads always 4, global single-term 1 index); drill a killed index write and require the AND miss to be detected by audit; drill a deleted-but-indexed id and require zero phantoms surfacing; track per-term relay lag with a paging threshold; forbid latency claims from local counts.

• A global index makes reads free. The postings lookup is one shard, but fetching the records still spans shards and multi-term intersection still crosses the network.
• More shards speed up local-index queries. They grow storage, not query throughput — every query still visits every shard and the slowest sets the tail.
• Four local SQLite timings predict cluster p99. They predict nothing about networked p99 — report counts locally, measure latency on the real cluster.
• The index is the source of truth, or a hand-rolled index without transactions is fine. The base is the truth and partial writes detach any unguarded index — use transactions or an outbox relay, never hope.