Picking a datastore, for a reason you can state

"Would you use SQL or NoSQL here?" is a question you will be asked, and answering it directly is a trap. Not because either answer is wrong, but because the category is not what determines the outcome. Postgres and MySQL differ from each other in ways that matter more than either differs from some NoSQL stores; "NoSQL" spans a document store, a wide-column store, a key-value cache and a graph database, which have almost nothing in common except the name they were given in opposition to something else.

What actually decides the choice is four questions, none of which mention the categories.

The four questions

1. What is the access pattern? Not "what is the data" — what are the queries. A system whose only read is "give me the last fifty rows for this one user id" has a completely different answer from one whose reads are "find every user matching these five filters, sorted by relevance". Write the two or three actual queries down. Most datastore arguments dissolve the moment the queries are on the board, because most datastores are obviously good or obviously bad at a specific query shape.

2. What consistency does the product require? Not what you would like. What breaks if it is violated. "A user must see their own comment immediately" is a real requirement with teeth. "The data should be consistent" is not a requirement; it is a mood.

3. Does it fit on one machine? You computed this last lesson. If a single primary with a read replica holds the data and serves the traffic, then almost every distributed-database argument is irrelevant and choosing one anyway is a mark against you.

4. What is the write pattern — and is it append-heavy or update-heavy? This is the question that most often gets skipped, and it is the one that reaches all the way down into the storage engine.

Below the category: two ways to arrange bytes on a disk

Almost every persistent store you can name is built on one of two structures. Knowing which one, and what it optimises, lets you predict a database's behaviour rather than memorising it.

A B-tree keeps the data sorted in fixed-size pages, updated in place. To change a row, you find its page, modify it, and write the page back. Reads are excellent and predictable: a lookup is a handful of page reads, bounded by the tree's depth, and a range scan walks sorted pages in order. This is Postgres, MySQL/InnoDB, and most traditional relational engines.

An LSM tree never updates in place. Writes go to an in-memory table and a sequential log; when the memory table fills, it is flushed to disk as an immutable sorted file. A background process merges those files into larger ones — compaction. Writes are fast and sequential; reads may have to consult several files. This is Cassandra, RocksDB, LevelDB, HBase, and the storage layer under a great many "fast at writes" systems.

That last sentence is where the two structures earn their reputations, so let us make the reputations precise instead of vibes.

WatchGaurav Sen · 11:29

The clearest public explanation of the probabilistic-structure trade that the next two sections rely on: give up exactness, get a constant-size answer. HyperLogLog is for cardinality rather than membership, but the reasoning is the same one Bloom filters use, and seeing it derived once makes the Bloom filter arithmetic below obvious rather than magical.

HyperLogLog — counting distinct elements without storing them Play “HyperLogLog — counting distinct elements without storing them” on YouTube

Read amplification, and what Bloom filters actually buy

An LSM tree's cost is on reads: the key you want could be in the memory table, or in any of the on-disk levels, and you have to look until you find it.

// A point lookup in an LSM tree may have to ask every level. Per-level Bloom
// filters are what stop "may ask" from meaning "does disk I/O".
const LEVELS = 7;
const FPR = 0.01;   // 1% false-positive rate per level — a common tuning

// Worst realistic case: the key lives in the oldest level, so every younger
// level is a Bloom check that should say "not here".
const withoutBloom = LEVELS;
const withBloom = 1 + (LEVELS - 1) * FPR;

console.log("levels                 :", LEVELS);
console.log("disk reads, no bloom   :", withoutBloom.toFixed(2));
console.log("disk reads, with bloom :", withBloom.toFixed(2));
console.log("saved                  :", (withoutBloom / withBloom).toFixed(1) + "x");

// And the case Bloom filters do NOT help with: the key is absent entirely.
const absentWithBloom = LEVELS * FPR;
console.log("absent key, with bloom :", absentWithBloom.toFixed(2), "reads (vs", LEVELS + " without)");

# A point lookup in an LSM tree may have to ask every level. Per-level Bloom
# filters are what stop "may ask" from meaning "does disk I/O".
LEVELS = 7
FPR = 0.01   # 1% false-positive rate per level — a common tuning

# Worst realistic case: the key lives in the oldest level, so every younger
# level is a Bloom check that should say "not here".
without_bloom = LEVELS
with_bloom = 1 + (LEVELS - 1) * FPR

print("levels                 :", LEVELS)
print("disk reads, no bloom   :", f"{without_bloom:.2f}")
print("disk reads, with bloom :", f"{with_bloom:.2f}")
print("saved                  :", f"{without_bloom / with_bloom:.1f}" + "x")

# And the case Bloom filters do NOT help with: the key is absent entirely.
absent_with_bloom = LEVELS * FPR
print("absent key, with bloom :", f"{absent_with_bloom:.2f}", "reads (vs", str(LEVELS) + " without)")

levels                 : 7
disk reads, no bloom   : 7.00
disk reads, with bloom : 1.06
saved                  : 6.6x
absent key, with bloom : 0.07 reads (vs 7 without)

The middle line is the one to internalise. With a per-level Bloom filter, a point lookup costs just over one disk read instead of seven, because the filters answer "definitely not in this level" from memory. A Bloom filter can produce a false positive but never a false negative, which is exactly the asymmetry this needs: a "no" is trustworthy and free, a "yes" costs you a disk read to verify.

And the last line is the case that surprises people: for a key that is not in the database at all, the Bloom filters make the lookup cost less than one disk read on average. A non-existent key is the cheapest query an LSM tree serves, which is the opposite of the intuition most candidates bring.

Write amplification: both engines amplify

The received wisdom is that LSM trees have write amplification and B-trees do not. That is not true, and saying it is one of the easier ways to sound like you learned this from a blog post rather than from operating something.

// Write amplification: how many bytes hit the disk per byte you asked to store.
// Both engines amplify. They just amplify for different reasons.
const ROW_BYTES = 128;

// B-tree: the unit of write is a page, so a 128-byte row update rewrites the
// whole page — plus the write-ahead log entry that makes it crash-safe.
const PAGE = 8 * 1024;
const btreeWA = (PAGE + ROW_BYTES) / ROW_BYTES;

// LSM leveled compaction: each level is T times the size of the one above, so a
// byte is rewritten about T times on its way through each level.
const T = 10, LEVELS = 7;
const lsmWA = T * (LEVELS - 1);

console.log("B-tree WA (8 KB page):", btreeWA.toFixed(0) + "x");
console.log("LSM WA  (T=10, L=7)  :", lsmWA.toFixed(0) + "x");
console.log("");
// The difference isn't the magnitude — it's the ACCESS PATTERN.
console.log("B-tree: random 8 KB writes, scattered across the file");
console.log("LSM   : sequential multi-MB writes during compaction");
// Which is why the ratio that matters is sequential vs random throughput.
const SEQ_MBPS = 2000, RAND_MBPS = 200;   // rough NVMe figures
console.log("");
console.log("effective B-tree throughput:", (RAND_MBPS / btreeWA).toFixed(1), "MB/s of user data");
console.log("effective LSM    throughput:", (SEQ_MBPS / lsmWA).toFixed(1), "MB/s of user data");

# Write amplification: how many bytes hit the disk per byte you asked to store.
# Both engines amplify. They just amplify for different reasons.
ROW_BYTES = 128

# B-tree: the unit of write is a page, so a 128-byte row update rewrites the
# whole page — plus the write-ahead log entry that makes it crash-safe.
PAGE = 8 * 1024
btree_wa = (PAGE + ROW_BYTES) / ROW_BYTES

# LSM leveled compaction: each level is T times the size of the one above, so a
# byte is rewritten about T times on its way through each level.
T, LEVELS = 10, 7
lsm_wa = T * (LEVELS - 1)

print("B-tree WA (8 KB page):", f"{btree_wa:.0f}" + "x")
print("LSM WA  (T=10, L=7)  :", f"{lsm_wa:.0f}" + "x")
print("")
# The difference isn't the magnitude — it's the ACCESS PATTERN.
print("B-tree: random 8 KB writes, scattered across the file")
print("LSM   : sequential multi-MB writes during compaction")
# Which is why the ratio that matters is sequential vs random throughput.
SEQ_MBPS, RAND_MBPS = 2000, 200   # rough NVMe figures
print("")
print("effective B-tree throughput:", f"{RAND_MBPS / btree_wa:.1f}", "MB/s of user data")
print("effective LSM    throughput:", f"{SEQ_MBPS / lsm_wa:.1f}", "MB/s of user data")

B-tree WA (8 KB page): 65x
LSM WA  (T=10, L=7)  : 60x

B-tree: random 8 KB writes, scattered across the file
LSM   : sequential multi-MB writes during compaction

effective B-tree throughput: 3.1 MB/s of user data
effective LSM    throughput: 33.3 MB/s of user data

The first two lines land in the same ballpark — both engines rewrite your data on the order of tens of times. So amplification alone does not explain anything.

What explains it is the two lines after: the B-tree's amplified writes are small and random, and the LSM's are large and sequential. Storage devices are much faster at sequential writes than random ones, so the same amplification factor costs far less when it is paid sequentially. That is the real mechanism behind "LSM trees are good at writes", and it is why the advantage narrows on hardware where the random/sequential gap is smaller.

The final two numbers in that cell are computed from the nominal device throughputs written just above them — change those two constants to your own hardware's figures and the ratio moves. Treat the direction as the lesson and the magnitude as an input you should state aloud rather than assert.

Choosing, out loud

Here is the decision as a table you can reconstruct from the four questions. Note that nothing in the left column is a product name — the products are consequences.

Two things to say when you use this table in a round.

Say the property, then the product. "I need a store that keeps rows for one partition key physically together and takes appends cheaply — that's a wide-column LSM store, so Cassandra." If the interviewer's shop uses something else, you have still said the right thing, and they will often supply their own name for it.

Expect to name more than one. Real systems are polyglot, and the strong version of this answer usually splits the storage: blobs in object storage, metadata in a relational store, the hot set in a cache, and search in an index. Saying "these four, and here's which data lives where" is a better answer than any single choice — provided you can also say what the split costs you, which is that you have just given up cross-store transactions and will need to reason about the write ordering between them.

Denormalisation is a consequence, not a preference

Candidates often propose denormalising because it sounds like the scaling-minded thing to do. It is a real technique with a real justification, and the justification is always the same shape: a read that must be fast is currently a join, so we pay at write time instead.

Say it that way and the trade-off comes with it for free:

The feed read has to be one lookup, and building it from a join across posts and follows at read time won't hold p99 under 200 ms at 46,000 reads a second. So I'll materialise it: when someone posts, write a row into each follower's timeline. That moves the cost to the write path, which is a hundred times smaller — 460 writes a second becomes 460 times the average follower count, which is the number I now have to check. And it means a follow is no longer a single row insert, because the new follower's timeline needs backfilling.

That paragraph contains the technique, the arithmetic that justifies it, and the two consequences you have accepted. It is also the setup for the celebrity fan-out problem, which is the classic deep dive for this system — and the classic deep dive precisely because this denormalisation is what creates it.

What to carry into the next lesson

You now have numbers from lesson 2 and a storage layer chosen for a stated reason. What sits between them and the latency target is the cache — and the cache is where the numbers you computed earlier turn out to depend on an eviction policy and a stampede you have not yet accounted for. That is next.