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

• Workload is a teaching mix: roughly 80% writes, 20% point reads plus occasional range scans. Real ratios come from your access log, not from this page.
• Teaching sizes: 4 KB pages, memtable flush at a few MB, branching factor in the hundreds. They illustrate the shapes, not your capacity plan.
• Durability means the WAL fsync before the ack. The memtable and the per-segment indexes are speed structures, not durability.
• Single-node engine comparison. Replication, partitioning and crash recovery across machines belong to later chapters.

LSM batches sorted disk writes to reduce random I/O, paying in compaction and read amplification. B-trees support ordered lookups and ranges with page-update cost. An 80% write mix and 4 KB pages define a comparison scenario, not a universal choice. Re-measure latency and amplification for read-heavy workloads. Fsync before ACK protects acknowledged writes.

1. Every write lands twice The WAL append + fsync is the durability write; the memtable update is the visibility write. Ack the client only after the fsync, never after the RAM update alone.
2. Flush turns RAM into a file When the memtable passes a few megabytes it is written out sorted as one immutable SSTable — the newest segment — and a fresh memtable takes over. Every read checks the memtable first, then segments newest to oldest.
3. Compaction merges and cleans Compaction reads segments side by side like mergesort: for duplicate keys only the newest version survives, and a tombstone tells the merge to drop the older values. Size-tiered merging favors write throughput, leveled merging favors reads and space.
4. Crash between flush and manifest A flushed file that is not yet in the manifest is simply ignored on restart; the checksummed WAL replays the memtable and its corrupt tail is dropped. No half-visible state ever serves reads.
5. Count the three amplifications Write amplification (disk bytes per user byte: high at LSM compaction, ~1-2x page rewrites in a B-tree), read amplification (several segments versus 3-4 page depth), space amplification (old plus new until merged versus pages plus WAL). Teaching ratios, not benchmarks. Verdict: write-heavy goes LSM, predictable reads and ranges go B-tree.

Parts: append-only checksummed WAL with fsync per write (or group commit); sorted memtable with sequence numbers; manifest of live segments updated atomically; one sparse index plus one Bloom filter per segment; a background compactor. Write path: put to log fsync to memtable to ack. Read path: memtable to Bloom to sparse index to segments newest to oldest; ranges use a merging iterator over the sorted segments. Delete: a tombstone carrying a fresh seq that kills older versions at merge.

Teaching demo from this environment: segments [u1=a2, u2=b] and [u2=<tombstone>, u3=c] merge to {u1=a2, u3=c} — the u2 delete applies exactly because the tombstone is newer. WAL replay gives the same map. Teaching arithmetic: one million 100-byte writes are 100 MB of raw data; at a teaching write amplification of 10x that is about 1 GB of disk bytes. A point read checks the memtable plus at most N segments, and a Bloom filter at ~10 bits per key gives ~1% false positives (the chapter's rule of thumb).

• B-tree when reads dominate: each lookup costs a predictable 3-4 page fetches and ranges walk the leaf chain with no compaction stalls. Cost: random writes rewrite whole pages, splits and write-ahead logging add their own overhead.
• Hash-indexed log (Bitcask style) for pure point lookups whose key set fits RAM: O(1) reads, sequential writes. Cost: no range queries and a full-log rebuild after restart.

• Crash between flush and manifest: before, the memtable plus WAL hold the writes; after restart, the unlisted SSTable file is ignored and WAL replay rebuilds the memtable. Recovery: replay checksummed records, drop the corrupt tail, re-register only manifested files.
• Tombstone dropped too early: a compaction that does not include the oldest segment must keep the tombstone, otherwise the surviving older copy resurrects the deleted key. Rule: drop a tombstone only when merging the oldest segment holding that key, or after a stated grace period with no older copies.
• Compaction falls behind a write spike: memtables pile up, segment count grows, read amplification and space amplification spike together. Mitigation: throttle writes, prefer leveled merging, alert on pending compaction bytes before reads degrade.

Run: javac LsmToy.java && java LsmToy — stdlib only, instant. Change the put sequence to replay your own crash case.

Expected output: seg1: [u1=a2, u2=b]; seg2: [u2=, u3=c]; merged: {u1=a2, u3=c}; wal-replay matches the merge.

• Calling the memtable durable. RAM is lost on crash; only the fsynced WAL prefix survives. Replay, not memory, is the recovery story.
• Treating a tombstone as an instant delete. The key stays readable from older segments and keeps costing space until a covering compaction removes it.
• Reporting a benchmark without fsync mode, cache state and data-to-RAM ratio. An fsync-free, fully cached run measures nothing about production durability or disk behavior.

• Teaching scale: a 14-row demo you can run here; imagine the same shape at millions of rows. Ratios below are teaching numbers, not benchmarks.
• Five product categories, weekday derived from the date dimension, amounts in one currency with no tax or returns logic.
• One nightly load: facts are complete for past days, and late corrections arrive as restatements, not silent edits.

Column storage helps when queries read only a few columns: approximate bytes as selected rows × needed column widths, plus metadata. RLE benefits from consecutive repetition; shuffling identical values demonstrates why order matters. Fourteen rows make the result inspectable, not predictive at millions of rows. Late data must restate earlier reports under an explicit contract.

1. Shape the star first fact_sales(day, pid, qty, amount) holds one row per sale; dim_date(day, weekday, year) and dim_product(pid, category) stay small and joined by key. Facts stay narrow so scans stay cheap.
2. Write the SQL Join facts to both dimensions, filter year = last year, group by category and weekday, sum the amount. The SELECT list names only the columns the report needs — that list is the pruning contract.
3. Keys decide what is skipped Partition by year and month so last year's predicate discards all older blocks unopened; sort each file by day then category so equal categories sit together for run-length compression and weekday ranges prune. The demo reads day, pid and amount lanes only.
4. Compress by cardinality, watch skew Five categories fit a bitmap: one bit per row per value, AND the category and weekday bitmaps, then fetch amounts only for surviving rows. High-cardinality ids get dictionary plus run-length encoding instead — raw bitmaps would explode. A hot product crowds one sort block and weakens range pruning; isolate or re-sort it.
5. History keeps both labels A June category move must not rewrite January: keep both labels as a slowly changing dimension and report the category at sale time unless the brief explicitly asks for a restated view — and then say so on the report.

Tables: fact_sales(day, pid, qty, amount), dim_date(day, weekday, year), dim_product(pid, category). Partition key: year and month on the fact files. Sort key inside each file: day, then category. Read path: open only last-year partitions, only the day, pid and amount lanes, filter year = last year, join the two small dimensions, GROUP BY category, weekday with SUM(amount). The full SQL is SELECT p.category, d.weekday, SUM(f.amount) FROM fact_sales f JOIN dim_date d ON f.day = d.day JOIN dim_product p ON f.pid = p.pid WHERE d.year = last_year GROUP BY p.category, d.weekday.

Java demo from this environment (JDK 27, 14 teaching rows): the group-by prints A|0 -> 90.0, A|1 -> 90.0, A|3 -> 40.0, A|4 -> 170.0, A|5 -> 130.0; the bitmap filter for category B and weekday 2 gives rows = [9] and reads a single amount, [100.0]. Interpretation: one row in fourteen survives, so the amount lane pays one fetch instead of fourteen — that ratio is the whole argument for pruning, at teaching scale.

• Row store with a B-tree index when the workload is point lookups (one order by id), not scans. Cost: every analytical query pays full-row reads and no pruning applies.
• Pre-aggregated cube when the same category-by-weekday report runs unchanged every morning. Cost: storage per slice plus a refresh contract; ad-hoc questions still need the base facts.

• Late-arriving fact: a correction for March lands in April's load. Before: March partition already reported. After: restate the March partition with a visible correction note and re-run affected reports — never silently edit history.
• Mid-year category move without a slowly changing dimension: January sales silently take June's label and year-over-year comparisons lie. Rule: keep both labels, report category-at-sale-time by default.
• Hot-product skew plus high-cardinality ids: one product crowds a sort block so range pruning degrades, and raw bitmaps on millions of ids explode. Mitigation: isolate or re-sort the hot key, dictionary-encode ids, reserve bitmaps for low-cardinality lanes.

Run: javac ColumnarToy.java && java ColumnarToy — stdlib only, instant. Add a 2024 block to watch partition pruning skip it.

Expected output: A|0 -> 90.0, A|1 -> 90.0, A|3 -> 40.0, A|4 -> 170.0, A|5 -> 130.0; bitmap AND rows = [9]; amounts read for those rows = [100.0].

• Writing SELECT star and reading every lane. Column pruning only works when the query names its columns — the SELECT list is the contract.
• Bitmap-indexing a high-cardinality id lane. One bit per row per value explodes; dictionary plus run-length encoding is the stated alternative.
• Restating history under today's labels without saying so. The numbers look clean and the year-over-year story is quietly false.

• Eleven short teaching documents; the trigram demo runs on their real text here.
• Recall demo uses synthetic 1-D vectors in 4 clusters, not real embeddings — it teaches the metric, not production recall.
• Latency is p50/p95 over 20,000 repeated in-process runs on this machine — a teaching harness, not a benchmark.
• Single-tenant demo; multi-tenancy is a stated filter rule, not a second index in the code.

A trigram is three consecutive characters, so literal appl contains app and ppl. Both may occur separately in a document, hence regex verification. Recall@k is the fraction of exact top-k recovered: eight shared results out of ten gives 0.8. More probes inspect more candidates and usually improve recall at greater cost. Measure p95 because the mean hides slow queries. The demo’s 1-D vectors teach the metric only.

1. Postings first Tokenize all docs into term-to-postings lists once. At query time intersect the red and apples lists (bitwise AND over sorted ids) down to doc 0. Phrase and ranking refinements come later; the intersection is the exact boolean core.
2. Candidates, then proof The literal appl contains app and ppl. Their postings intersect in eight candidates; document 10 has both separately and fails regex verification. Compare the result with a full regex scan to assert that no actual match was lost.
3. Name the fallback The literal appl contains app and ppl. Their postings intersect in eight candidates; document 10 has both separately and fails regex verification. Compare the result with a full regex scan to assert that no actual match was lost.
4. Measure recall and latency IVF splits vectors into clusters and each query probes nprobe of them. Ground truth is the exact top-k over all vectors; the teaching run gives mean recall@3 of 0.900, 0.967 and 1.000 for nprobe 1, 2 and 4, with approx p95 below exact p95 in the same harness.
5. Rank hybrid, isolate tenants The literal appl contains app and ppl. Their postings intersect in eight candidates; document 10 has both separately and fails regex verification. Compare the result with a full regex scan to assert that no actual match was lost.

Parts: a tokenizer feeding an inverted index (term to sorted postings); a trigram index (fixed substring to doc set); a regex verifier running java.util.regex only over candidates; an IVF vector index (clusters plus nprobe); one hybrid ranker merging lexical and vector scores with stated weights; a tenant predicate pushed below the search; a refresh window after which writes become visible. Read path for red AND apples: intersect the two postings lists. Read path for /appl./: extract fixed trigram app, fetch candidates, verify each, drop doc 10.

Java demo from this environment (JDK 27): red AND apples = [0]; trigram 'app' candidates = [0, 1, 3, 4, 6, 7, 9, 10]; regex /appl./ verified = [0, 1, 3, 4, 6, 7, 9]; doc10 candidate but not verified = true. Recall on synthetic vectors: nprobe=1 mean recall@3=0.9, nprobe=2 mean recall@3=0.967, nprobe=4 mean recall@3=1.0. Latency harness (20,000 runs, this machine): exact p50=333ns p95=583ns, approx p50=250ns p95=375ns. Interpretation: one probe costs a tenth of recall and buys the lower p95 — a teaching measurement, not a benchmark.

• Full scan for a tiny corpus or a regex with no fixed trigram: no index to maintain, exact by construction. Cost: O(corpus) per query — fine for hundreds of docs, hopeless for millions.
• Exact kNN when the vector set is small enough that a full scan meets the p95 budget. Cost: linear scan per query; the day it misses the budget, IVF with measured recall replaces it.

• Stale index serves a deleted doc: the write landed but the refresh window has not passed. Contract: every result carries the index version, and deletes win visibly at the next refresh — never silently.
• Tenant leak through a shared index: one missing predicate returns another tenant's docs. Rule: the tenant filter is pushed below the search (or a per-tenant index), and a test asserts foreign docs never surface.
• nprobe too low silently drops the best match: recall falls with no error. Mitigation: monitor recall@k against the exact ground truth per query cohort and page when it drifts.

Run: javac RetrievalToy.java && java RetrievalToy — stdlib only, seconds. Raise the doc count or dims to feel the recall cost.

Expected output: red AND apples = [0]; candidates [0,1,3,4,6,7,9,10]; verified [0,1,3,4,6,7,9]; doc10 drops; recall@3 0.9 / 0.967 / 1.0 for nprobe 1/2/4; exact p50=333ns p95=583ns; approx p50=250ns p95=375ns (this machine, teaching harness).

• Calling a trigram hit a match. The trigram is a necessary condition, not a sufficient one — doc 10 proves the verify step is load-bearing.
• Quoting recall without a ground truth. recall@k is a fraction against the exact top-k; without it the number is decoration.
• Leaving nprobe at 1 because it is fast. Speed without measured recall is a silent quality cut — the demo's 0.900 says what one probe costs.