Data modeling & storage engines

This is the lesson the rest of the course quietly leans on. Partitioning (07), replication (08), messaging (11) and transactions (12) all assume you know what a write-ahead log is, why a B-tree and an LSM-tree make opposite bets, and what an index physically costs. We build all of that here, from one idea: you model the queries, not the entities, and the engine underneath is just a machine for making your chosen queries cheap and the rest expensive.

1. Model the queries, not just the entities

Newcomers start by drawing entities — User, Order, Product — and wiring up relationships. That is necessary but not sufficient. The schema that actually survives contact with production is shaped by the access patterns: what reads and writes happen, how often, and how big. Those numbers come straight out of the estimate step from lesson 01 — QPS, read:write ratio, payload sizes, growth.

So before any tables, write the query list. For a social feed it might be:

• "Get the 20 most recent posts by the people I follow" — extremely hot, must be fast.
• "Create a post" — moderate rate, can be a touch slower.
• "Count a user's followers" — read often, written rarely.

Those three sentences decide more about your design than the entity diagram does. The hot read ("recent posts by followees") tells you what to index, what to denormalise, and eventually what to shard on (07). The rule: list the top ~5 queries by frequency and latency-sensitivity first; the schema is whatever makes those cheap.

Entities, keys, relationships — the vocabulary

• Primary key: the unique identifier for a row (e.g. user_id). It is also, in most engines, the key the data is physically sorted/located by — which is why choosing it well matters far beyond uniqueness.
• Foreign key: a column that references another table's primary key (order.user_id → user.id), encoding a relationship.
• Cardinality: one-to-one, one-to-many (a user has many orders), many-to-many (students↔courses, via a join table). Many-to-many is the relationship that joins — and denormalisation — fight over.

2. Normalisation vs denormalisation — the core modelling trade

This is the first real fork, and it is the same write-vs-read trade as everything else, in miniature.

Normalise means: store each fact exactly once, in one place, and reference it by key. A user's display name lives only in the users table; an order row stores user_id, not the name. Benefits: one source of truth, so a name change is one write and nothing can drift. The cost: to show an order with the buyer's name, the read must join — go fetch the matching user row. Reads do more work.

Denormalise means: deliberately duplicate data so a single fetch answers the query. Store the buyer's name on the order row. Benefit: the read is one lookup, no join — fast. The cost: that name now lives in N places, so a change is N writes, and if any write is missed the copies drift (the dreaded update anomaly). You traded cheap writes and correctness-by-construction for cheap reads.

3. SQL vs NoSQL — a decision, not a religion

The framing that loses interviews is "NoSQL is web-scale, SQL is old." The framing that wins: relational and non-relational engines make different default trades, and you pick by your access patterns and consistency needs.

Relational (SQL) — Postgres, MySQL. Data in tables with a fixed schema; the engine does joins for you, supports ACID transactions (Atomic, Consistent, Isolated, Durable — see 12), and answers ad-hoc queries you didn't plan for (a query planner figures out how). You pay with a rigid schema and harder horizontal scaling (joins across machines are expensive — the reason sharding in 07 is painful).

Non-relational (NoSQL) is a family, not one thing:

• Key–value (Redis, DynamoDB): a giant hash map, key → blob. Blazing point lookups, trivial to shard by key. No queries other than "get by key."
• Document (MongoDB): JSON-ish documents, flexible schema, query within a document. Great when data is naturally a nested aggregate fetched together.
• Wide-column (Cassandra, Bigtable): rows keyed by a partition key, each holding many columns; the table is literally shaped around one access pattern. Enormous write throughput, linear horizontal scaling.

The shared theme of NoSQL: flexible or access-pattern-shaped schema, horizontal scale, and no joins. No joins is the load-bearing constraint — it forces you to denormalise and model one table per query. You give up ad-hoc flexibility and (often) multi-key transactions to get scale and predictable single-key latency.

4. Storage-engine internals — the heart of the lesson

Now the part later lessons assume. SQL-vs-NoSQL is a packaging question; underneath, a database is a storage engine — code that turns "set key K to value V" and "get key K" into disk I/O. Two facts about disks drive everything:

1. Sequential writes are ~100× cheaper than random writes (append to the end of a file vs seek to a random spot and overwrite). This gap was enormous on spinning disks (a seek costs milliseconds); it shrinks on SSDs but stays real, because random writes still trigger erase-block churn and write amplification. Re-use the latency ladder from 01: a disk seek dwarfs a sequential append.
2. A crash can happen mid-write. Durability means a committed write survives a power loss — even if the box dies one instruction later.

The write-ahead log (WAL) — durability, cheaply

Here is the trick that makes durable databases fast. Before touching the actual data structure (which lives in random places on disk), the engine first appends the change to a sequential log — the write-ahead log — and flushes that. Only then does it update the data in place (or it does so lazily, in the background). The rule is in the name: write to the log ahead of writing the data.

Why this is brilliant: the append is sequential (cheap), so the latency the user waits for is one fast sequential write, not a slow random one. Durability is satisfied the instant the log entry is flushed. Think of a WAL like a kitchen's order-ticket rail: the server spikes the written ticket on the rail before anyone starts cooking, so if the kitchen is overwhelmed or "crashes" mid-service, the tickets are the durable record of what was promised, and you replay them to rebuild every in-flight order. And on crash recovery, the engine simply replays the log from the last checkpoint — every committed change is there, in order — to rebuild the correct on-disk state. You get durability at the price of a sequential append instead of a synchronous random write.

B-tree — read-optimised, update-in-place

The default engine for relational databases (Postgres, MySQL/InnoDB). A B-tree keeps keys sorted on disk in a balanced tree of fixed-size pages (typically 4–16 KB). To find a key you walk from the root down: each node read narrows the search, so a point lookup is O(log n) — a handful of page reads even for billions of rows. Because keys are sorted and adjacent, range queries ("all orders between March and April") are also cheap: find the start, then scan sequentially.

Writes update in place: find the right page, modify it, write it back. The cost lives here:

• Write amplification: changing one row rewrites a whole page; if the page is full, it splits into two and parent pointers update — one logical write becomes several physical ones.
• In-place overwrite is unsafe across a crash (a half-written page corrupts the tree), which is exactly why a B-tree engine needs the WAL — log first, then overwrite.

Net: a B-tree makes reads (point and range) cheap and pays on writes. It is the right default for read-heavy and mixed workloads.

LSM-tree — write-optimised, append + compact

The log-structured merge-tree (Cassandra, RocksDB/LevelDB, ScyllaDB) makes the opposite bet: never update in place, only append. The flow:

Walk it: a write lands in an in-memory sorted memtable (and is appended to a WAL for durability). When the memtable fills, it is flushed as an immutable sorted file — an SSTable (Sorted String Table). Writes are thus pure sequential appends — fast, the whole point. Over time SSTables pile up, so a background process called compaction merges them: combining sorted files, keeping only the newest value for each key and physically dropping deleted/overwritten ones.

The costs, named:

• Read amplification: a key could be in the memtable or any SSTable level, so a read may check several places. Mitigated by a Bloom filter — a tiny probabilistic bitset per SSTable that answers "is key K definitely not here?" so reads skip files that can't contain the key (it never gives a false negative).
• Compaction overhead: merging rewrites data repeatedly (CPU + extra write I/O = its own write amplification over the file's life) and transiently doubles space (old + new files coexist) — space amplification.

B-tree vs LSM-tree — the trade table

One sentence to carry: read-heavy with range scans → B-tree; write-heavy ingest → LSM. The widget below makes that quantitative.

5. Indexes — turning O(n) into O(log n)

A query like WHERE email = 'x@y.com' on an unindexed table must read every row to find matches: a full table scan, O(n). On 100M rows that's seconds. An index fixes it.

Physically, an index is a second sorted data structure (usually its own B-tree, or built into the LSM) that maps a column value → the locations of rows with that value. Because it's sorted, a lookup is O(log n) — a few page reads. That's how a 1-second scan becomes a 1-millisecond lookup. The gain is biggest when the column is selective (few rows per value — like email); indexing a low-selectivity column (e.g. a boolean) barely helps, because you still read a huge fraction of rows.

The cost — and there is always a cost:

• Every write must update every index. Five indexes means an insert does six writes (table + 5 indexes). Indexes trade write throughput and space for read speed — the same trade as the whole lesson.
• They consume disk and memory (the index must be kept hot to be fast).

So: index the columns your hot reads filter/sort on, and don't index columns nothing queries — each one is a tax on every write.

Composite, covering, and the clustering key

• Composite index on (a, b): sorted by a then b. Serves filters on a, and on a AND b — but not b alone (the leftmost-prefix rule). Order the columns to match your query.
• Covering index: includes every column the query needs, so the engine answers from the index alone and never touches the table (an "index-only scan"). Buys a skipped lookup; costs a wider index.
• Primary / clustering key: the key the table's rows are physically ordered by on disk (an InnoDB table is its primary-key B-tree). Rows with adjacent keys sit together, so range scans on that key are nearly free — which is exactly why the shard-key choice in 07 matters: it is the clustering key at cluster scale, and a bad one creates hotspots. That lesson also covers local vs global secondary indexes — whether each shard indexes only its own data (cheap writes, scatter-gather reads) or there's one cluster-wide index (cheap reads, expensive writes) — the same read/write trade, distributed.

6. Schema evolution — changing the model without downtime

Schemas change while the system is live and old code is still running. The discipline is the same as API versioning (03): make changes backward-compatible so old and new can coexist.

• Additive changes are safe: adding a nullable column or a new table breaks nothing — old code ignores it, new code uses it.
• Destructive changes are not: renaming or dropping a column that running code reads will crash it.
• Online migrations: on a big table, an ALTER that rewrites or locks every row can stall writes for minutes. Use tools / techniques that build the change in the background and swap atomically.

Try it: a B-tree vs LSM workload advisor

Pick a read:write mix, say how much range scans matter, and set write volume. The widget estimates a rough write-amplification and read-amplification for each engine and recommends one. The model is deliberately simple but directionally honest — see the hint for the formula.

Interview prompts you should be ready for