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

• Teaching log: 200,000 lines with 19,782 distinct URLs (skewed popularity), from the runnable demo below — not a production benchmark.
• Memory cap stated up front: one 20,000-line chunk in RAM; anything past it must spill to temp files.
• Exact top-5 required; the approximate variant is a separate regime with its own error budget.
• Single machine with local temp disk; distributed shuffle belongs to the next exercises.

Hash aggregation holds state proportional to distinct keys U; more lines with fixed U do not have the same memory growth. External sorting bounds RAM by spilling chunks and paying disk I/O. Two hundred thousand lines and 20k-line chunks force visible spills, not a universal threshold. Compare time with peak memory and temporary bytes so an over-budget design does not win on speed alone.

1. Name the working set Multiply distinct keys by per-entry overhead: that product is the working set, and it — not total lines — decides whether hash fits.
2. Hash with a spill escape Route hot partitions to RAM counters and cold ones to sorted spill files; both reconverge on one ranker with exact counts.
3. Sort that always finishes Sort bounded chunks, spill runs, k-way merge with O(runs) lines in RAM, count adjacent equals, rank top-K.
4. Benchmark equal outputs Fix input, cap and K; assert identical top-K on both paths; then compare time and spill bytes — the demo below does exactly this.
5. Approximation relaxes exactness If only an approximate top-100 is asked, grant an error budget and pick a sketch or sample-then-count: tiny memory for bounded error.

Stages: extract (URL per line) → partition-or-chunk (bounded RAM) → spill store (sorted runs on temp disk) → merge (k-way, one line per run in RAM) → rank (top-K heap).

Config: one explicit chunk_cap (lines or bytes); spill directory with free-space reserve; deterministic seed for the teaching generator.

Contracts: runs are sorted and checksummed; the merge holds O(runs) lines, never O(urls); the ranker keeps K entries; both paths emit identical top-K for identical input.

Demo numbers (teaching, this environment): 200,000 lines, 19,782 distinct, chunk cap 20,000 → 10 runs, 1,517,486 spilled bytes. Both paths print /p/0:7453, /p/1:1842, /p/2:1287, /p/3:1066, /p/4:913; equal_top5=true.

Interpretation: equality first (same answer), then cost (spill bytes and time). Move the cap or the cardinality and re-run — the row, not the anecdote, is the finding.

• Pure in-memory hash with no spill path: fastest while the working set fits, but the first oversized input kills the job with OOM instead of slowing it down. Keep it only behind a measured cardinality guard with a spill fallback.
• Sketch plus heap (e.g. count-min with a top-K heap): tiny bounded memory and one pass, but answers are approximate with a stated error bound. Wins only when the interview explicitly allows an approximate top-100.

• OOM misread as slowness: the hash job dies instead of degrading. Guard with an explicit cap, a spill path, and an alert on spill ratio — treat OOM as a wrong answer, not a slow one.
• Disk-full mid-spill: runs stop landing and the merge reads a truncated set. Guard with a spill-space reserve, per-run checksums, and fail-fast instead of silent truncation.
• Unequal benchmark: different inputs, caps or K across the two paths make the comparison meaningless. Guard by fixing input, cap and K, and asserting identical top-K before timing.

Run: javac TopUrlsDemo.java && java TopUrlsDemo — stdlib Java only, temp files auto-cleaned.

Expected output: lines=200000 distinct=19782 chunk_cap=20000 runs=10 spilled_bytes=1517486; both paths print /p/0:7453 down to /p/4:913; equal_top5=true; OK. (actual output of this environment)

• Quoting a universal distinct-URL threshold ('hash breaks at N million URLs'). The spill point depends on entry overhead, heap cap and disk on that machine — measure it per environment, never quote it as a constant.
• Treating OOM as ordinary slowness. A hash job past RAM does not finish late — it dies. Design the spill path and the alert before the big input arrives.
• Benchmarking unequal work: different inputs, memory caps or K, then declaring a winner. Fix input, cap and K first; assert identical outputs; only then compare time.

• Teaching files: 30,000 clicks over 3,500 ids, 3,000 unique profiles (user_id,dob) — both exceed the 1,000-row chunk cap, so spills are real, not staged.
• One unique profile per user, declared up front; history and duplicates are handled as explicit failure cases, not silent fan-out.
• Left-join semantics: every click emits exactly once, with NULL plus a counter when its profile is missing.

With separate streams, advance the profile cursor to the click’s user_id; unique profiles require one retained record. O(1) describes join state, not all external-sort memory. Early clicks in a mixed stream need buffering until their profile arrives; profile-first removes that buffering. Thirty thousand and three thousand records exceed the 1k-row chunk to force spills. Duplicate profiles violate the uniqueness premise and need a separate policy.

1. Declare uniqueness and join type State left-join semantics and profile uniqueness before touching data: every click emits once, missing means NULL plus a counter.
2. Sort both past memory Sort each side by user_id with bounded chunks and real spills; each side yields exactly one ordered stream.
3. Merge with one profile held Walk both orders with two cursors: advance the lagging side, hold at most one profile, emit (url, dob) on equality, count the missing.
4. Contrast the mixed contract Contrast the mixed stream: one interleaved input per reducer needs profile-first secondary sort — or explicit buffering with a bound. Two separate streams need neither.
5. Skew and history, priced Price skew with salt-and-combine and settle history with the live-at-ts rule; both declared before the run, both monitored during it.

Formats: clicks user_id,url,ts, profiles user_id,dob; sort key user_id on both sides; spill runs are sorted CSV temp files.

Merge: two file cursors; advance the lagging side; on equality hold one profile and emit per click; missing clicks go to the NULL counter, profiles without clicks are skipped.

Skew and history: hot users split by salt with a combine step (priced openly); versioned profiles join by the live-at-ts rule declared before the run.

Demo numbers (teaching, this environment): 30,000 clicks, 3,000 profiles, chunk cap 1,000 rows → real spills on both sides. Emitted 25,692 visits, 4,308 counted missing, max_profiles_held=1.

Interpretation: completeness first (emitted plus missing equals clicks), then the invariant (one profile), then cost (spill I/O). Sample emits read /p/203 -> 1990-01-01.

• Broadcast (map-side) join: when the profile side fits in RAM, load it into a hash table once and stream clicks past it — no sort of the big side at all. Wins while profiles fit; loses the day they stop fitting, when you fall back to this solution.
• Mixed-reducer join with profile-first secondary sort: the right answer when one shuffle delivers clicks and profiles interleaved. It pays a stronger sort key to recover streaming; do not pay it for two already-separate files.

• Duplicate profiles break declared uniqueness: equality fans out into several rows per click. Guard with a dedupe assert on the profile side before the merge, and fail the job — never emit the fan-out silently.
• Hot-user skew: one user owns a huge click share and its join worker stalls while others idle. Guard by measuring key distribution, salting the heavy key, joining parts, then combining — priced, not hidden.
• Versioned history without a rule: several profiles share one user and the join is undefined. Guard with the live-at-ts rule declared before the run; without it, stop instead of joining.

Run: javac SortMergeJoinDemo.java && java SortMergeJoinDemo — stdlib Java only.

Expected output: clicks=30000 profiles=3000 chunk_cap=1000 (both files exceed it: real spill); three sample emits such as /p/203 -> 1990-01-01; emitted=25692 missing_profile=4308 max_profiles_held=1; OK. (actual output of this environment)

• Demanding profile-first secondary sort for two separately sorted streams. It adds sort work for zero correctness gain: the merge only compares join keys. Profile-first belongs to the mixed single-stream contract — say exactly where each breaks instead of applying one rule everywhere.
• Silently dropping clicks without profiles. Absence is a business fact (deleted user, late dimension) — emit NULL, count it, alert on its ratio.
• Holding every profile in memory because 'dimensions are small'. Small today is big next quarter: the merge holds one profile by construction, so growth never revisits this decision.

• Teaching shuffle: 2 mappers, 3 partitions, 12 keys × 25 values (300 records) — colocation and recompute are observable, not benchmarks.
• Partition function floorMod(hash, R), identical on all workers and versioned with the job; changing it reshuffles everything.
• Mappers are deterministic and side-effect free, so rerun replays the same records — stated as a precondition, verified by the demo.

Hash(key) mod R colocates a key’s values, requiring identical versioned partition functions on all mappers. Three partitions and two mappers expose the paths. Sorting orders records within a partition and serves a different purpose. Deterministic, side-effect-free mappers reproduce output on retry, but publication must still select one attempt through a commit manifest.

1. One function everywhere Fix one partition function on every worker and version it with the job: same key, same partition, every mapper, every run.
2. Sort locally, write files Sort each partition slice inside the mapper and write one checksummed mPrR file per partition — the fetchable contract.
3. Fetch and merge per partition Fetch one partition's files from all mappers and k-way merge with one line per file in RAM: same keys arrive together, sorted.
4. Combiner and checksums Pre-aggregate with a combiner where associativity holds, and checksum every file so corruption is detected, never silent.
5. Scoped lineage rerun On loss, rerun only the owning mapper from its immutable split under a fresh attempt id; deterministic replay makes the rewrite equal the lost file.

Files: one sorted checksummed file per (mapper, partition) named mPrR; the file set is the shuffle contract the reducer fetches.

Attempts: every mapper run carries an attempt id; a retry rewrites whole files under a fresh id and never appends to the failed one's.

Reducer: fetches one partition's files from all mappers, k-way merges with one line per file in RAM, groups equal keys; combiner pre-aggregates associative work (counts, sums — never a bare average) before any byte crosses the network.

Demo numbers (teaching, this environment): 2 mappers, 3 partitions, 300 records. Before corruption each reduce holds 100 records over 4 keys with colocated=true sorted=true; m1r2.txt is corrupted; mapper 1 reruns as attempt 1 from its split; after recompute the same invariants hold.

Interpretation: recovery is scoped (one mapper) and verified (same predicates before and after), not narrated.

• Range partitioning: each reducer owns a key range, so output comes out globally sorted. Wins when downstream needs total order; loses on skew, because one range can hold half the data with no hash to spread it.
• Broadcast the small side and skip the shuffle entirely when one input fits in every worker's RAM. Wins by deleting network, combiner and merge; stops winning the day the 'small' side stops fitting.

• Corrupt intermediate file: bytes on disk no longer match the checksum. Guard by failing that partition's fetch and rerunning only the owning mapper from its split — never the whole job.
• Mapper crash mid-write: a partial mPrR file looks complete at a glance. Guard with attempt ids plus checksums: the retry rewrites whole files under a fresh id, and fetch refuses unchecked files.
• Nondeterministic mapper or outside side effects: rerun replays different records or repeats external writes. Guard by construction — deterministic mapping, no outside writes — because no retry protocol fixes a mapper that lies.
• Partition function changed mid-job: old and new files disagree on key placement and grouping silently breaks. Guard by versioning the function with the job and refusing mixed-version fetches.

Run: javac ShuffleDemo.java && java ShuffleDemo — stdlib Java only.

Expected output: partitions=3 mappers=2 partition_fn=floorMod(hash, 3); before corruption each reduce holds 100 records / 4 keys with colocated=true sorted=true; corrupted m1r2.txt; reran mapper=1 attempt=1; after recompute identical invariants; OK. (actual output of this environment)

• Rerunning the whole job for one lost file. Lineage names the exact mapper; scoped rerun is the whole point of immutable splits plus attempt isolation.
• Reusing file names across attempts so two runs of one mapper both look current. Fresh attempt ids per retry; fetch accepts exactly one committed generation.
• Side effects inside the mapper (external writes, non-idempotent calls). Replay then repeats the outside world — keep mappers pure or rerun is unsafe by definition.

• Teaching job: 4 tasks × 500 rows from immutable shards; a seeded killer dies mid-write with probability 0.5 per task attempt — failures are injected, not hoped for.
• Local temp filesystem where pointer swap stands in for the atomic step; the object-store atom (conditional write) is designed in text, with its different cost.
• Readers resolve the pointer once per read session and pin that manifest; single-writer publishing unless the CAS follow-up applies.

Do not expose partial files as complete output. Each attempt writes immutable output; a manifest selects one winning attempt per task, and switching the pointer changes visibility. A 0.5 crash probability injects frequent failures, not a real failure rate. Atomic rename assumes one supporting filesystem; object storage needs its own documented conditional-write/CAS semantics.

1. Invisible attempt outputs Freeze immutable input shards and let each task write exactly one checksummed attempt file per attempt id — attempts are invisible by construction.
2. Delete partial, fresh id On crash, delete the partial file first, then rerun the same input under a fresh id; commit only on checksum.
3. Barrier before publish Hold every publish behind a barrier that counts committed tasks: all-or-nothing is enforced in code, not promised in prose.
4. One atomic pointer swap Swap one pointer atomically — local rename on filesystems, conditional write on object stores — so readers move between complete versions only.
5. Pin, serve, retire Readers pin one manifest per session; old versions serve out their grace, then garbage-collect with pin counts.

Attempts: task-{t}-attempt-{n}.txt with checksums; a retry deletes the partial first and runs n+1; fetch and readers never see attempt names, only manifests.

Manifest: manifest-v3.txt lists exactly the committed attempt files plus a version; CURRENT holds one manifest name and moves atomically.

Publish atom per storage: local filesystem — atomic rename of CURRENT; object store — conditional write (CAS) on the pointer key, loser retries the whole publish; concurrent publishers resolved by exactly one CAS winner.

Cleanup: partial attempts deleted on retry; superseded versions kept through a grace period for pinned readers, then garbage-collected.

Demo numbers (teaching, this environment): 4 tasks × 500 rows with kill probability 0.5 per attempt. Attempts per task [2, 0, 1, 0]; manifest-v1.txt published via pointer CURRENT; reader sees 2,000 of 2,000 rows with all_or_nothing=true.

Interpretation: failures happened (three retries) yet the reader observes exactly one complete version — retries are invisible by design.

• In-place overwrite of the live output: no old version, no time travel, and readers mid-job see a mix of old and new rows. Cheaper storage, weaker everything else — acceptable only when nobody reads during the job and history never matters.
• Staging directory plus rename on a local filesystem: tasks land in a versioned staging dir, one atomic rename publishes it. Simple and correct locally — but the rename is the atom, and that atom does not transfer to object storage.

• Keeping the partial and appending on retry: two generations interleave and checksums may pass on garbage. Guard by deleting before writing — the demo's commented lines show the corpse and its deletion.
• Publishing before the barrier: readers see half the job and cache it downstream. Guard with the barrier as code (count committed tasks, refuse early publish), not as convention.
• Torn reader: resolving CURRENT twice in one session can straddle a swap. Guard by pinning once per session and reading only the pinned manifest.
• Local rename assumed on object storage: renames may be copy-plus-delete — visible, slow, non-atomic. Guard by choosing the store's own atom (conditional write, versioned pointer) and testing torn reads explicitly.

Run: javac RetryPublishDemo.java && java RetryPublishDemo — stdlib Java only.

Expected output: attempts_per_task=[2, 0, 1, 0]; published manifest-v1.txt via atomic pointer CURRENT; reader sees rows=2000 expected=2000 all_or_nothing=true; OK. (actual output of this environment)

• Generalizing local rename atomicity to object storage. A POSIX rename is atomic; an object-store 'rename' is often copy plus delete. Choose and test the store's own atom instead of assuming the familiar one travels.
• Confusing task commit with job publication. A committed attempt is finished but hidden; only the barrier plus the pointer swap makes anything visible. Debugging reads attempts, serving reads manifests.
• Garbage-collecting versions that pinned readers still hold. The old version is a live contract until its grace expires — GC after grace, with pin counts, never by age alone.