Caching & Databases · lesson 6 of 8 · about 26 min
How to choose a database from the shape of your data and your access patterns: the five families and what each trades away, embedding versus joining, why queries that do not include the shard key are slow, what a graph store really saves, how much a single node can carry, and the cost of picking for scale you do not have. Tap any for a plain-language card.
The families
A useful rule: pick a relational database by default (it handles surprisingly large workloads and is the easiest to change your mind about), and pick something else when a specific access pattern or scale demands it. Tap each family to see its data model, where it shines and where it hurts.
Look at what each family cannot do: the weakness is usually the reason it can do the other thing so well.
| Data model | Tables of rows with a fixed schema; relationships through foreign keys; a declarative query language. |
| Examples | PostgreSQL, MySQL, SQL Server |
| Typical query | SELECT … JOIN … WHERE … GROUP BY |
| Good at | Ad-hoc queries and joins, transactions across rows, constraints that protect the data, a mature ecosystem. |
| Weak at | Scaling writes beyond one machine needs sharding you build yourself; schema changes on huge tables need care. |
Relational (SQL): Ad-hoc queries and joins, transactions across rows, constraints that protect the data, a mature ecosystem. The price: scaling writes beyond one machine needs sharding you build yourself; schema changes on huge tables need care.
A summary of how these systems describe themselves; real products blur the lines (PostgreSQL stores JSON documents, DynamoDB offers transactions).
Joins versus embedding
The trade is that embedded copies must be kept consistent. Changing a product's name in a relational database updates one row. If thousands of order documents each embed that name, either you update them all (a huge fan-out write that is not atomic) or you accept that old orders keep the old name. For orders that is often correct (an invoice should keep the price paid), but for a user's display name shown on every comment it is a bug. Choose per field.
With 50,000 orders embedding a product, one rename means 50,000 document writes; in SQL it is one row.
An order with 5 items takes about 7 lookups with a join and 1 with an embedded document, a real win for read-heavy pages. Renaming a product that appears in 50,000 orders is 1 write in SQL and 50,000 in the document model, so embed data that is read together and rarely changes, and reference data that changes often.
Counts of operations, not times. Relational read = orders lookup + items index lookup + one row per item (a simplification).
Key-value and wide-column
That slowest-of-N effect is the tail-latency problem from the latency lesson: with 50 shards you meet the p99 of a single shard almost every time. The remedies are in the data model: design the key around the queries you need (a composite partition key and a sort order, as in Cassandra), maintain a second table or index for each additional query, and accept that you must know your queries in advance.
At one shard a query takes about 5 ms. At 200 shards the same query takes nearly double: the median is the single shard's p99.
By key, one shard answers in about 5.1 ms. A query that must visit 50 shards waits for the slowest: 12.1 ms at the median and 20.5 ms at p99, and it also costs 50 requests of cluster capacity for one user question.
8,000 seeded queries: each shard's time is log-normal (σ = 0.4) around the median; scatter-gather takes the maximum over the shards visited.
Graph databases
Be honest about the size of the win, though: it is a constant factor per hop (the number of index levels), not an exponential. The number of people you reach grows as bdepth either way (50 friends at 6 hops is fifteen billion paths), and that explosion, not the storage model, is what you must tame with limits and pruning. Graph stores earn their keep for recommendations, fraud rings, access-control hierarchies and dependency graphs, where depth and shape vary.
Compare depth 2 with depth 5 at 50 friends each: the graph is always about five times fewer reads, but both climb by a factor of 50 per hop.
50 friends over 3 hops means 125 thousand paths. A relational database does about 625 thousand page reads for them, a graph store about 125 thousand pointer hops: 5× fewer. At this size either approach is fast.
Cost model: a relational hop = index descent of ⌈log₂₀₀(n)⌉ pages plus the row; a graph hop = one pointer. Constant factors only; it ignores caching.
Scale
The honest question is arithmetic: how much data, how many queries per second, how fast is growth, and what does one machine of the kind you can rent actually handle (measure it with your workload; the figures below are slider assumptions, not benchmarks). If the answer is one node plus replicas, use the simplest database that fits. When it is not, you will be or choosing a store built to scale out, and you will know why.
2 TB and 5,000 queries a second need a single node. Push to 30 TB and 100,000 queries a second and you need a fleet.
2 TB and 5,000 queries a second fit on one node (limits 4 TB and 20,000 q/s). A single relational database with replicas is the simplest design that works, and keeps joins and transactions.
Nodes = max(⌈data ÷ per-node data⌉, ⌈rate ÷ per-node rate⌉). The per-node limits are sliders for your own benchmark results, not universal numbers.
Which store?
Pick the family whose strengths match the access pattern, not the one with the best marketing. Each answer is worth 20 XP.
Ask: how is it read, how is it written, do records change together, and how big will it get?
Web session data looked up by session id, millions of times a second, expiring after 30 minutes.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published systems and the shapes they chose.
a key-value store for the shopping cart
The Dynamo paper described a key-value store built for availability: any node can accept a write, versions are reconciled later, and the access pattern (get and put by primary key) is simple enough to partition by hashing. Amazon used it for services such as the shopping cart.
a wide-column store
Bigtable stores a sparse, sorted map from (row key, column, timestamp) to value, split into tablets and written through an LSM-style log. Applications such as web indexing, Maps and Gmail used it, designing their row keys around the scans they needed.
a distributed graph store
Facebook's TAO paper describes a graph API (objects and associations) for the social graph, served from a caching tier in front of sharded MySQL. Even a graph workload ended up on a relational store underneath, with the graph shape provided by the API.
sharded PostgreSQL
Instagram's engineering blog described sharding its PostgreSQL databases logically across many servers with its own ID scheme, rather than moving to a different type of store, to serve a very large user base.
Interview angle
Six questions, each worth 20 XP. 'Why this database?' is one of the most common design-interview questions.
Start from access patterns and consistency needs, say what you give up, and do the capacity arithmetic.
When unsure, which is the safest default?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
The second cost is correctness. A business action that touches two records (create the order and reduce the stock) needs a transaction; without one, a crash between the two writes leaves them disagreeing, and the application grows hand-written compensation code, background reconcilers and a dashboard of mismatches. These are all features a relational database already has. Move the sliders to see both costs.
With 50 orders on a page and a 2 ms round trip, the loop takes about 100 ms against 4.5 ms for one SQL join. Then raise the crash rate.
Listing 50 orders with an application-side join costs 51 sequential round trips: 102 ms, against 4.5 ms for a single join. And with 1 crashes per 10,000 actions between two related writes, about 50 actions per million leave the order and the stock disagreeing. A relational database does both jobs for free.
N+1 latency = (1 + N) × round trip; a join is one round trip plus a little work per row. Mismatches = crash chance × 1,000,000 × 0.5 (half of the crashes fall between the two writes).
Where to go next