System design · The method: framework, arithmetic, APIs, data, storage, caching

Data modeling from the access pattern

A data model is a set of answers to the queries your product will run, so it is built from those queries rather than from the nouns alone. This covers keys that will not hurt you later, one-to-many and many-to-many relationships, normalising first and denormalising for a named read, and how the same domain is laid out differently in a relational store and a partitioned key-value store.

19 min read Free to read Patterns: access-pattern-first, time-ordered-ids, partition-and-sort-key

What you'll be able to do

Before this: the-delivery-framework, api-design

By the time you reach the data model you already have the entities and the interface. The model is where they meet: each call in the interface becomes one or two queries, and the model is whatever makes those queries cheap. Candidates who start from the entities alone draw a tidy schema that answers none of the questions the product asks most often.

Interviewers look for three things here. Do your keys make sense, and will they survive growth? Can you express the relationships without inventing problems? And when you copy data to make a read fast, do you know what you just signed up for on the write path? None of it needs a full schema. It needs the four or five tables that carry the design, with their keys and the indexes that serve the reads you named.

Keys: the decision you cannot easily undo

A primary key is referenced from other tables, cached, put in URLs and logged. Changing it later means migrating every one of those, so it is worth thirty seconds now.

Surrogate versus natural keys. A natural key is a real-world value: an email address, an ISBN, a vehicle registration. A surrogate is a value the system invents, usually a number or a UUID. Prefer surrogates for anything people can edit. Users change email addresses; if email is the primary key, every foreign key pointing at it has to change too. Keep the natural value as a column with a unique constraint, which gives you the lookup and the uniqueness without the coupling.

Identifiers that sort by time. A random UUID (version 4) is easy to generate anywhere without coordination, but it scatters inserts across the whole index. A time-ordered identifier (a millisecond timestamp in the high bits, then a sequence or random bits, which is the idea behind Snowflake-style ids and UUID version 7 in RFC 9562) keeps new rows together at the end of the index and also sorts by creation time for free.

JavaScript
// 1,000 inserts into an index. Where does each new key land?
// Time-ordered ids: millisecond timestamp in the high bits, a sequence in the low bits.
// Random-looking ids: a multiplicative hash of the counter (deterministic stand-in for UUIDv4).
const N = 1000;
const START_MS = 1700000000000n;

const timeOrdered = (n) => ((START_MS + BigInt(n)) << 12n) | BigInt(n % 4096);
const randomLike = (n) => BigInt((n * 2654435761) % 2 ** 32);

function rightEdgeInserts(ids) {
  // An insert "at the right edge" is larger than every key already in the index:
  // it goes into the same hot last page instead of a random page somewhere inside.
  let highest = -1n, count = 0;
  for (const key of ids) {
    if (key > highest) { highest = key; count++; }
  }
  return count;
}

for (const [name, make] of [["time-ordered", timeOrdered], ["random-like ", randomLike]]) {
  const ids = Array.from({ length: N }, (_, i) => make(i + 1));
  const edge = rightEdgeInserts(ids);
  console.log(`${name}: ${String(edge).padStart(4)} of ${N} inserts at the right edge (${(100 * edge / N).toFixed(1)}%)`);
}

With time-ordered keys every insert goes to the last page of the index, which stays in memory. With random keys, after the first handful, almost every insert lands on some page in the middle, so a large table pays a random page read and an eventual page split for each new row. The count of 8 is no accident: in a random sequence the expected number of new maximums among the first n values is the harmonic number, about ln(n) + 0.58, which for 1,000 is about 7.5.

Two caveats keep this from being a rule you apply blindly. Sequential ids reveal volume: if order 10,500 follows order 10,000 a day later, a competitor can count your orders. Use them internally and expose a separate random or encoded id publicly when that matters. And in a store that partitions by key range, monotonically increasing keys send every new write to the last partition, which becomes a hot spot. Hash-partitioned stores do not have that problem; range- partitioned ones need the key prefixed with something that spreads it.

Relationships, and which direction you index them

One-to-many goes as a foreign key on the "many" side. An episode row carries show_id. To list a show's episodes you need an index on (show_id, published_at), not just on show_id, because the query is also sorted. The foreign key constraint itself does not create that index in Postgres; you must create it.

Many-to-many needs a join table whose primary key is the pair. Subscriptions between users and shows become subscriptions(user_id, show_id), primary key (user_id, show_id). That key serves "which shows does this user follow?" as a range scan. The reverse question, "who follows this show?", needs a second index on (show_id, user_id). Say both directions out loud and say which one your interface actually uses; often it is only one.

Hierarchies and graphs. A comment thread is a tree stored as a parent_id; reading a whole thread is a recursive query or a stored path (/12/57/90). If the product asks deep multi-hop questions, such as friends of friends, say that a relational store can do a few hops with recursive queries and that a graph store earns its place only when traversal is the main workload.

Normalise first, then denormalise for a named read

Start normalised: each fact stored once, and everything else joins to it. It is the easiest model to keep correct, because an update changes one row.

Then go through your interface and find the reads that are too slow or too frequent to pay for a join each time. For each one, decide whether to copy a value closer to where it is read. The justification always has the same shape: this read happens N times more often than the write that changes the copied value, and the read cannot afford the join.

Ways to denormalise, from mildest to strongest:

TechniqueExampleThe write you now owe
Cached counterepisode_count on showsIncrement on every new episode, in the same transaction
Copied attributeShow title on each progress rowBackfill every copy if the title changes
Precomputed viewA per-user "new episodes" listFan out on each publish to every subscriber
Embedded childEpisode summary inside the show documentRewrite the parent on any child change

Each row of that table moves cost from reads to writes, and each one creates a second copy that can disagree with the first. That is fine when the copied value rarely changes (show titles) and dangerous when it changes constantly (live counts under contention). State which one you have.

The same domain, two layouts

A relational store lets you add an index later for a query you did not foresee. A partitioned key-value or wide-column store (DynamoDB, Cassandra) does not join, and it serves fast queries only along the key you designed, so you design one table, or one index, per access pattern. The partition key decides which machine holds the data and must appear in every query; the sort key orders rows inside a partition and supports range queries.

The worked example below lays out a podcast app both ways, so the difference is concrete.

1Write the access patterns▾
  1. Show page: the show and its 20 newest episodes.
  2. Resume: my saved position in one episode.
  3. Continue listening: my 10 most recently played episodes, newest first.
  4. Subscribe and unsubscribe, and list my subscriptions.

Volumes that matter: progress is saved every 15 seconds while playing, so writes to progress dwarf everything else. Show titles change perhaps once a year.

2The relational model▾
  • shows(id, title, ...)
  • episodes(id, show_id, published_at, title, audio_url), index (show_id, published_at DESC) for pattern 1.
  • subscriptions(user_id, show_id, created_at), primary key (user_id, show_id) for pattern 4.
  • progress(user_id, episode_id, position_s, updated_at), primary key (user_id, episode_id) for pattern 2, plus index (user_id, updated_at DESC) for pattern 3.

Pattern 3 then joins ten progress rows to episodes and shows. That is ten primary key lookups, which is cheap, so no denormalisation is needed yet. Every pattern is an index range scan or a key lookup.

3The partitioned model▾
TablePartition keySort keyServes
episodes_by_showshow_idpublished_at#episode_idPattern 1, reading 20 rows from one partition
progress_by_useruser_idepisode_idPattern 2, one item
recent_by_useruser_idupdated_at#episode_idPattern 3, the first 10 rows
subs_by_useruser_idshow_idPattern 4

Three differences are worth saying. First, recent_by_user stores the show and episode titles on each row, because there is no join; the price is that a show rename leaves stale titles until a backfill runs, which is acceptable for a value that changes once a year. Second, a sort key cannot be updated in place, so moving an episode to the top of "recent" is a delete of the old row and a write of the new one; with saves every 15 seconds, you would update recent_by_user only when the user starts an episode, not on every save. Third, if you later need "who subscribes to this show?", that is a new table (or a secondary index) and a backfill, not a new index created on the fly. Saying that last point is how you show you know what the partitioned model costs.

4Say which one, and why▾

"Every access pattern here is keyed by user or by show and the data is a few hundred gigabytes, so I'd start relational: Postgres with these four tables and indexes. If progress writes outgrow one primary (two million people listening at once, each saving every 15 seconds, is about 133,000 writes a second), I'd move just progress to a partitioned store keyed by user id, because it's the one table with a simple key-only access pattern and the hardest write load."

That answer picks a default, names the number that would change it, and moves only the part that needs moving.

The checklist

  1. Access patterns written as queries before any table is drawn.
  2. Surrogate primary keys for anything editable; natural values kept unique as columns.
  3. Time-ordered ids where insert locality or time sorting helps, a public id where counts must stay private, and a spread prefix if the store partitions by range.
  4. Foreign keys indexed for the sorted query that uses them; join tables indexed in the directions the interface needs.
  5. No unbounded lists inside a row.
  6. Each denormalisation tied to a named read, with the write it costs and how stale copies get fixed.
  7. For a partitioned store, one table or index per access pattern, with partition and sort keys stated.