Problem RestatementProblem
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.
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.
Design
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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 --> DATA2.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.
Deep Dive — Choosing an index for spinning disks and little RAMDeep dive
The constraint drives everything: a seek costs milliseconds, sequential throughput is fine, and there is not enough memory to hold the data. The index has to buy seeks.
Scan the file
Keep records in a flat file and read through it to find an item.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["Look up item 88210"] --> SCAN["Read the file from the start"]
SCAN --> GB["Hundreds of GB at disk throughput"]
SCAN --> SEC["Seconds to minutes per lookup"]
UPD["Update a record"] --> RW["Rewrite in place - another full pass to find it"]Every operation is proportional to the dataset. Nothing about this survives the first request.
A B+ tree or an on-disk hash index
A B+ tree is three or four levels deep; the upper levels fit in RAM, so a read costs roughly one seek. An on-disk hash index gives one seek for reads too, at the cost of losing range queries.
Reads are solved. Writes are the problem: both structures update in place, so every write is a random write — a seek — and the workload updates stock counts constantly. On a spinning disk, a write-heavy load against a random-write structure is the slowest thing the hardware can be asked to do.
Log-structured storage with a sparse in-memory index
Append all writes to a log sequentially, and keep a sparse index in RAM — one entry per block rather than per record:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
W["Update item 88210"] --> APP["Append to the current segment - sequential write"]
APP --> SEG[("Segment files on disk")]
SPARSE["Sparse index in RAM - one key per block"] --> FIND["Locate the block"]
Q["Read item 88210"] --> SPARSE
FIND --> SEEK["One seek, read the block, scan within it"]
SEG --> COMP["Background compaction - merge segments, drop superseded records"]
COMP --> SEG- Writes become sequential, which is where a spinning disk is fastest — the single biggest win available on this hardware.
- Reads stay at about one seek, and zero when the block is already cached, because the sparse index narrows to a block and the block is scanned in memory.
- RAM scales with blocks, not records. A sparse index over 4 KB blocks is a few thousand times smaller than a full one, which is what makes it fit.
The cost is compaction: superseded records accumulate, so background merges rewrite segments to reclaim space. That is read and write amplification running continuously, and it has to be throttled so it does not compete with serving traffic for the same disk arm — on one spindle, compaction and lookups are contending for the same resource.
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.
Expected PerformanceScale
- 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.
Wrap-UpWrap-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.