Inventory Serving on Spinning Disks with Little RAM

0) Problem Restatement

Apple asked: design software for a machine with no SSD and only a small amount of RAM that must serve inventory requests (look up and update records keyed by item ID, e.g., stock count and location) from spinning hard disks (HDDs). The challenge is physics: a random read on an HDD needs a seek (moving the disk head), which takes ~5–10 ms. That's only ~100–200 random reads per second per disk. Sequential reads and writes are much faster (~100–200 MB/s).

So the whole design is about minimizing random seeks.

1) Numbers to Start With

• 100M items × 200 bytes = 20 GB of data. RAM is maybe 2 GB, so it doesn't fit.
• Random read = ~8 ms. A request that needs 3 random reads = ~24 ms, so ~40 requests/sec per disk. Too slow if we're careless.
• Goal: ≤ 1 seek per lookup, and writes turned into sequential I/O.

2) Design

flowchart LR
    REQ["Requests - get / update item"] --> SVC["Inventory service"]
    SVC --> CACHE["RAM: hot-item cache + in-memory index"]
    CACHE -->|"miss: 1 seek"| DATA[("Data file on HDD - sorted by item_id")]
    SVC -->|"updates"| LOG[("Append-only write log - sequential")]
    LOG --> MRG["Background merge - sequential rewrite"]
    MRG --> DATA

2.1 Reads: at most one seek

• Store records sorted by item ID in large blocks (e.g., 64 KB each).
• Keep a sparse index in RAM: just the first item ID of each block. 20 GB / 64 KB = ~330K blocks × ~16 bytes = ~5 MB of index, which fits easily.
• Lookup: binary-search the in-memory index → one seek to read the right block → scan the block in memory.
• A Bloom filter (small, in RAM) avoids seeks for items that don't exist.

2.2 Cache the hot items

• Inventory lookups are skewed (popular items get most requests). Use the remaining RAM as an LRU cache of records or blocks. With a good hit rate (say 80%), most requests need zero seeks.

2.3 Writes: make them sequential

• Updating a record in place = a random seek per write, which is slow.
• Instead, append updates to a write log (sequential, fast) and keep recent updates in a small in-memory map (so reads see them). This is the LSM tree idea.
• Periodically merge the log into the sorted data file with one sequential read and one sequential write of the file (compaction), during quiet hours or throttled.
• Group commit: flush the log with fsync every few ms for many writes together.

3) Why Not a B+ Tree or Hash Index?

• B+ tree: reads take height (3–4) page reads, but the upper levels fit in RAM, so ~1 seek per read. That's good. In-place updates cost random writes (seeks), though.
• On-disk hash index: 1 seek for reads, but random writes, and no range queries.
• Log-structured + sparse index (our choice): ~1 seek reads (0 on cache hit), sequential writes. The cost is background compaction (read/write amplification).

4) More Tricks

• Batch and sort requests: when many requests are waiting, sort them by disk position and serve them in one sweep (like an elevator), which reduces head movement.
• Several disks: stripe blocks across disks (RAID 0/10) for parallel seeks. Mirror for durability.
• Readahead for scans (reports): read large sequential chunks.
• Crash safety: the write log is replayed on restart. Merges write a new file, then atomically swap the index.

5) Expected Performance

• Cache hit (≈80%): < 1 ms. Miss: ~1 seek ≈ 8 ms. Average ≈ 0.8 × 0.5 + 0.2 × 8 ≈ ~2 ms.
• Writes: ~sequential log appends, thousands per second per disk with group commit.

6) Wrap-Up

Design around seeks: keep records sorted in big blocks with a tiny sparse index and a Bloom filter in RAM, so any lookup costs at most one seek. Use leftover RAM as a hot-item cache, turn updates into sequential log appends with an in-memory buffer and background sequential merges, and batch and sort pending I/O. That gets average latency to a few milliseconds even on spinning disks with little memory.