A system is components chosen to work with each other.
2 figures
what-is-a-system
Pick one from each bin
The goal is a car that will do 150 mph on a road. Pick one row from each bin; the car then runs at its slowest part and costs every part in it. E3+C1+W3 spends $2.05M and travels at walking pace: C1 is the bottleneck, and no engine above it matters. E3+C3+W3 has no bottleneck at all and is still wrong, because 100 mph of it is past anything the goal asked for, at $7.05M. E2+C2+W1 hits 150 on all three parts at once for $22,600.
Notes ↗what-is-a-system · The same problem, for data
Same idea, for a data system
Same bins, same arithmetic, and a goal of ten thousand requests a second. S3+D1+P3 puts everything in memory and rents two hundred nodes, then serves it all through one local database: D1 is the bottleneck, so the system does a thousand a second and pays $34,200 a month to miss the goal. S3+D3+P3 has no bottleneck and is still wrong, at ten times the goal for $49,000. S2+D2+P2 hits it exactly for $5,600. Storage, database and servers do the job the engine, chassis and wheels did.
Latency in a modern data center spans eight orders of magnitude, from a nanosecond on-chip to a hundred milliseconds across the planet.
1 figure
data-centers · Latency Tiers
One data center: seven orders of magnitude of latency
Seven tiers in one data center, fastest to slowest, from L1 cache at 1 ns to a cross-continent round trip at 100 ms. End to end is 100,000,000x, eight orders of magnitude, and a read from the wrong tier costs up to 10,000,000x more.
Linux runs on hardware and exports processes. A process includes a private memory space that Linux maps to physical RAM, a set of open files referenced through handles, and time on a CPU that the kernel schedules via context switches. Postgres runs as a program inside a process and uses only these interfaces.
A short pool of pages over a big file of them, and two workers on one page
A table occupies many DB-pages on disk. The buffer pool holds a small subset of those DB-pages, pulled from scattered locations. Multiple workers can access the same cached DB-page, including one worker that reads it and another that modifies it. Linux treats both workers as ordinary processes that read and write ordinary memory.
Notes ↗os-and-databases · From one machine to many
A notebook and a paperback: page size against page count
Page size and page count vary independently. A DB-page also has a fixed size, and a table spans as many DB-pages as its data requires.
Notes ↗os-and-databases · From one machine to many
One DB-page magnified into the OS-pages it is made of
A table on disk consists of DB-pages. Each DB-page spans an integer number of 4 KB OS-pages on x86-64. Postgres groups two OS-pages into one 8 KB DB-page. A big-data system groups 16,384 OS-pages into one 64 MB DB-page.
Paging & Storage: How Does One Machine Process 128 GB with Only 16 GB of RAM?
Disks and SSDs read in fixed-size pages (typically 64 MB in big-data systems).
4 figures
storage-paging · Paging: From CPU to RAM
The CPU works through cache and RAM, never the SSD, and data moves one page at a time
SSD-to-RAM transfers move one page per IO. One 64 MB IO costs the same whether the query needs one row or the whole block, and transfer time dominates, so moving 64 MB at about 5 GB/s takes ~13 ms. RAM-to-CPU transfers move 64-byte cache lines into L1/L2/L3 in nanoseconds, and the core executes out of cache and registers. RAM holds 256 pages (16 GB) and the SSD holds 2048 pages (128 GB), so the dataset passes through RAM one page at a time.
Notes ↗storage-paging · Why Paging Matters: The Speed Gap
Why paging matters: the speed gap scaled to human time
Rescale latency so an L1 cache hit takes one second. RAM becomes 1.5 minutes, an SSD read becomes 3 hours, and a hard disk read becomes 4 months. Paging keeps the working set in RAM. A query that reads from disk on every page pays the hard disk or SSD cost once per page.
Notes ↗storage-paging · Storage Hierarchy: Speed, Cost, and Capacity
The storage hierarchy as a staircase
Cache, RAM, SSD, and HDD form a latency ladder. Each step down runs roughly 100x to 1,000x slower and costs less per terabyte while providing more capacity: RAM at 100 ns and $3,500/TB, SSD at 10 µs and $75/TB, HDD at 10 ms and $25/TB. An algorithm chooses a working set size that fits within a tier.
Notes ↗storage-paging · Modern Reality: CPUs/GPUs Can't Escape the Disk Bottleneck
One machine: compute is free, the link is the bottleneck
Link bandwidth caps end-to-end throughput inside one machine. The GPU does ~3x1014 ops/s, while PCIe moves ~32 GB/s and an SSD supplies ~5 GB/s. Reading a 1 TB dataset across the PCIe link to the GPU takes ~30 s, while computation over it takes ~0. RAM (red) is volatile and the SSD (green) is durable, and both connect through the same links. A server adds cores, RAM, and SSDs as additional devices and capacity, while link speed stays similar.
You need to read 200 pages with the following cache hierarchy:
Check RAM first for all pages (90% hit rate)
For RAM misses (10%): 75% found in SSD, 25% in HDD
Calculate the total read time, including the cost of checking RAM.
Notes ↗problems-io-cost · Problem 3: Cache Hit Rate Impact
Cache hierarchy: reading 200 pages
Of 200 page reads, the RAM check is always paid (200 × 0.00064s = 0.128s) and serves 180 hits at 90% (green). The 20 misses split into 15 SSD fetches (0.192s, amber) and 5 HDD fetches (3.25s, red), for 3.57s total. The 5 HDD reads account for 2.5% of requests and 91% of wall-clock time (3.25 / 3.57).
Figure 1. Of 200 page reads, the RAM check is always paid (200 × 0.00064s = 0.128s) and serves 180 hits at 90% (green). The 20 misses split into 15 SSD fetches (0.192s, amber) and 5 HDD fetches (3.25s, red), for 3.57s total. The 5 HDD reads account for 2.5% of requests and 91% of wall-clock time (3.25 / 3.57).
Show Solution
Step 1: Check RAM for ALL pages
Must check RAM for all 200 pages to determine hits/misses
RAM Check Cost = numPages × C_r = 200 × (100ns + 64MB/100GB/s)
= 200 × 0.00064 = 0.128 seconds
Results: 180 pages found (90% hit), 20 pages miss (10%)
Step 2: Fetch misses from lower levels
Of the 20 misses:
→ 15 pages (75%) found in SSD
→ 5 pages (25%) found in HDD
SSD Fetch Cost = numPages × C_r = 15 × (10μs + 64MB/5GB/s)
= 15 × 0.01281 = 0.192 seconds
HDD Fetch Cost = numPages × C_r = 5 × (10ms + 64MB/100MB/s)
= 5 × 0.65 = 3.25 seconds
Notes ↗problems-io-cost · Problem 5: Network vs Local Storage
Reading one 64 MB page: local vs network
Reading one 64 MB page costs about 0.00064s from local RAM (green), 0.0128s from local SSD (amber), and 0.65s from local HDD (red). Network RAM includes a remote read (0.00064s), a network transfer (0.0064s), and a local write (0.00064s), for 0.0077s total (orange).
Figure 2. Reading one 64 MB page costs about 0.00064s from local RAM (green), 0.0128s from local SSD (amber), and 0.65s from local HDD (red). Network RAM includes a remote read (0.00064s), a network transfer (0.0064s), and a local write (0.00064s), for 0.0077s total (orange).
A hash function maps a key to a fixed-size bucket id, so you can find or insert in expected O(1) by reading the page where the bucket lives.
1 figure
basic-hashing · Integer Hashing
Integer hashing with h(x) = x % 10
h(x) = x % 10 maps four integers into ten buckets numbered 0 through 9. 42 and 1042 both land in bucket 2 (orange) because both end in 2, while 157 and 89 fall in distinct grey buckets. The collision is the point: an index must handle two keys reaching the same bucket. Chaining stores a list per bucket. Open addressing probes for an empty slot.
Case Study 2.1: How Uber and Google Maps use Geo-hashing
Geo-hashing converts a 2-D (lat, lng) coordinate into a 1-D grid key.
4 figures
case-study-geohashing · Why hexagons, not squares
Why hexagons, not squares: a hexagon's neighbours are all the same distance
Cell shape determines the neighbor ring. A square has eight neighbors at two distances: four edge-neighbors one cell away, four corner-neighbors farther by a factor of root two. A hexagon has six neighbors, each at the same distance from the center, which yields a symmetric ring for a radius query.
Notes ↗case-study-geohashing · Uber H3: hexagons in practice
Nearby points share a cell, far points do not
H3 codes for three Stanford campus buildings and SF Mission. At resolution 8 the three campus buildings map to 8828347417fffff and SF Mission, 29 miles away, maps to a different cell. At resolution 12 the three campus buildings split into three cells, differing in the trailing digits (orange), and SF Mission remains in a different cell.
Notes ↗case-study-geohashing · The hash and the lookup
Geo-hashing: a location becomes a cell code
Hashing maps each (lat, lng) to the H3 cell that contains it. Ten million orders start as coordinates. The system computes the cell ID per order and stores orders by that ID. Nearby orders share a cell ID. Distant orders map to different IDs.
Notes ↗case-study-geohashing · The hash and the lookup
Geo-hashing lookup: a radius query is a bounded handful of cell reads
A radius query hashes the driver location to one cell, then reads the six adjacent cells that the radius can cross. The query performs up to seven cell lookups. Those seven cell IDs can map to seven different pages, which yields up to seven reads. The read count stays constant as the table grows from ten thousand orders to ten million.
Columnar compression (run-length, dictionary, delta) exploits repetition inside one column, typically shrinking on-disk size 10× and cutting IO by the same factor.
2 figures
compression-basics · When to Use What?
Four columnar compression techniques at a glance
Four columnar techniques compress a column by removing repeated structure. RLE stores each run as a value plus a count. Dictionary encoding maps each distinct value to a small integer code. Delta encoding stores differences between adjacent sorted numbers. Bit packing stores small integers in the minimum number of bits. The raw input is grey, the encoded result orange. Ratios run from about 4x (bit packing) to 100x (RLE on sorted data); choose based on the column's value distribution.
A 1M-row user_id column sorted by user_id with ~25,000 active users compresses by chaining encodings. RLE collapses the sorted runs (4 MB to 200 KB). Dictionary encoding then replaces ids with codes; 25,000 ids fit in a 2-byte code rather than a 4-byte int (to 100 KB). zstd entropy-codes the remaining byte patterns (to 50 KB), a 98.75% reduction. Unsorted data or high cardinality leaves little for these encoders to remove.
A Bloom filter stores a set in a bit array and uses k hash functions to map each item to k bit positions.
1 figure
bloom-filters · Visual: How Bloom Filters Work
Bloom filter: a bit array plus k hash functions
A Bloom filter stores a 16-bit array and k = 3 hash functions. INSERT "alice" hashes to bits 3, 7, and 14 and sets them (orange). Earlier inserts also set bits 9 and 11. LOOKUP "bob" hashes to bits 3, 9, and 2. bit[2] = 0 guarantees "bob" is not in the set (green). Any 0 bit implies "definitely not in the set." All 1s imply "probably in the set," so false positives occur and false negatives do not.
Case Study 2.2: How does Google Chrome protect 3 billion users using Bloom Filters?
Chrome ships a Bloom filter of known-malicious URL hashes to every device (the classic Safe Browsing design).
1 figure
case-study-bloomfilters
Chrome Safe Browsing: a local Bloom filter, a prefix to Google only on a maybe
A device carries a 125 MB Bloom filter, derived from Google's 8 GB blocklist and shrunk 64 times. A safe URL gets a local answer and sends nothing. A maybe URL sends a 32-bit hash prefix to Google; Google returns the hashes with that prefix, and the device completes the match locally. Google receives a prefix and does not receive the URL, so 100M URLs and 3 billion users leak almost nothing.
An ordinary hash spreads inputs across buckets. Two near-identical vectors (cat A and cat B) land in unrelated buckets, 7 and 3. The bucket index carries no information about distance, so a similarity query still scans every bucket. Locality-sensitive hashing groups near vectors instead.
Each item becomes a feature vector, an embedding, then a short LSH code, then a bucket. The two similar cats receive code 1011 and share a bucket, while the dog and car map to different buckets. A query for items like the cat reads that one bucket instead of comparing against every stored vector. Code bits come from random cuts of the space.
Each cut asks one yes-or-no question: above the line is 0, below is 1, and the code assembles one bit at a time. The same four items as Figure 2. The two cats end on 111 because no cut fell between them, so they share a bucket; the dog differs on cut 1 and the car on cut 3, so each lands elsewhere. Nothing measures a distance, which is what turns a near-duplicate lookup into a hash-table lookup: cost O(N) becomes about O(N / 2k). Misses happen when a cut does fall between a close pair.
The cut is always one dimension less than the space
A cut is always a flat one dimension below the space it cuts. In two dimensions that is a line, which is what Figure 3 drew; in three it is an ordinary plane, drawn here; in an embedding’s few hundred dimensions it is a hyperplane (harder to picture). Nothing else changes: above or below is still the only question. Watch what one cut is worth. After the first plane the dog is still in the cat’s bucket, because one cut halves the space and a coin flip put it on that side. The second ejects it, and the near-duplicate survives all three. Each plane roughly halves the candidates: 200, then 94, then 43, then 19.
Case Study 2.3: How OpenAI and Facebook Speed Up Queries with Vector Databases
You built LSH, an approximate-nearest-neighbour (ANN) index.
4 figures
case-study-vectordb · The problem: a dot product against every row
The exact scan: one query against every vector
Exact scan against all N vectors. At a million vectors: a million 1,536-D L2 distances, about 1.5 billion multiply-adds and ~6 GB scanned per query. In FAISS this exact index is IndexFlatL2.
Notes ↗case-study-vectordb · The fix: an approximate nearest-neighbour index
HNSW is built in layers
How the graph is built. Layer 0 holds every vector, each linked to its nearest neighbours with short local links. Layer 0 is the local streets. A few vectors are promoted to layer 1, where they link much further: the expressways. Fewer still reach layer 2, with the longest links of all: the freeways. The dashed verticals are the same vector appearing on more than one layer. This is built once, when vectors are added, never per query.
Notes ↗case-study-vectordb · The fix: an approximate nearest-neighbour index
HNSW search: the query walks toward itself, layer by layer
HNSW search. The query vector defines a distance from the query to any visited node. The walk starts at a top-layer entry node, moves to the closest neighbour, then drops layers when it cannot improve. The search touches only the visited path and skips the rest of the graph.
Notes ↗case-study-vectordb · The fix: an approximate nearest-neighbour index
Brute-force scan vs an ANN index
Exact scan compares the query against all million 1,536-D vectors: ~1.5 billion multiply-adds and ~6 GB scanned per query. An ANN index probes only nearby vectors, either the IVF cells it selects or the HNSW neighbours it visits, so a query touches a small fraction of the data in well under a millisecond and can miss a neighbour. Same recall target, roughly 100 to 1000x less work.
A float32 embedding index stores more precision than search needs.
4 figures
case-study-vector-compression · The demo worked. Production did not.
The demo fit in RAM; production does not
Float32 storage size. Embeddings often have about a thousand dimensions or more. OpenAI's smaller embedding model is 1,536-D and the large one is 3,072-D. At 1,536-D float32 that is about 6 KB per vector, so 10 million vectors take ~60 GB in RAM for fast search. The large model uses double. Quantizing each coordinate to a few bits shrinks the index 8 to 32 times and brings it under the RAM limit.
Notes ↗case-study-vector-compression · Most of the information hides in a few directions
A random spin turns the grid, not the points
Eight frames from 0° to 58°. The three cities sit at identical coordinates in every frame, so you can check for yourself that only the grid moved. San Francisco and Berkeley begin in one cell and end in different ones. Stanford, much further off, is untouched.
case-study-vector-compression · Most of the information hides in a few directions
Four bits buys 16 levels. Before the rotation, 5 get used.
The same idea at 256 dimensions, where it earns its keep. A 4-bit budget is 16 levels. Before the rotation the coordinates are so uneven that only 5 levels are ever used, which is 2.3 bits of information in the 4 bits you are paying to store. After it, 15 levels are in play at 3.9 bits. Storage is 4 bits per coordinate either way; only the useful fraction changes.
Notes ↗case-study-vector-compression · Then just drop the precision
Drop the precision, keep the distance
Scalar quantization of one coordinate. 0.4327 stored in 32 bits maps to a 2-bit bucket 10 and decodes to about 0.4. One coordinate contributes little signal, but a distance aggregates hundreds of coordinates. In high dimensions, quantization errors across coordinates behave close to independent and tend to cancel. The rotation enforces a shared distribution across coordinates, so the same quantizer works across coordinates and across datasets without training. Two bits gives 16× compression, and one bit gives 32×.
data-structures-problem-solving · Putting it together
Two levers for a too-big problem: partition the lookup, or shrink each item
Two levers for a too-big problem. Lever 1 partitions the lookup so a query examines one slice instead of all N: exactly, by hashing to a bucket; approximately, by pruning what is definitely absent (Bloom) or bucketing by similarity (LSH, IVF, HNSW) and checking only the candidates near the query. Lever 2 shrinks each item: losslessly by dropping the redundancy the data already has (only if it has structure), or lossily by dropping precision while keeping the rank order (a random rotation reframes the data so one coarse quantizer fits any of it). The exact-vs-approximate split inside each lever is the module's Basic-vs-Approximation track. Production composes both, IVF-PQ is partition plus compress, the vector database.
