Everything above the database can be rewritten in a sprint. The
store you pick, the key you shard on, and the consistency you promise are the
decisions that are still shaping the company three years later.
05
Databases
SQLNoSQLindexingnormalisationaccess patterns
Why it exists
Different stores make different things cheap. A relational database makes
arbitrary queries cheap and known queries merely fine; a key-value store
makes one known query nearly free and everything else impossible. You are not
choosing a technology, you are choosing which queries you are willing to make
expensive.
"I'll start with Postgres. It gives me transactions and joins while the access
patterns are still moving, and a single primary handles tens of thousands of
writes a second — well past what we estimated. If write volume outgrows one
node I'd shard by tenant, and I'd move only the one hot, append-heavy table to
Cassandra rather than migrating everything."
Why this scores:
"Postgres unless proven otherwise" is a defensible default with a named exit.
Reaching for a distributed store at 300 writes/second is the single most common
over-engineering flag.
Design from access patterns, not from entities
The relational instinct is to model the world and then query it. The NoSQL
discipline is to list the queries first and build storage that answers them:
# List the access patterns before you draw a single table
A1 get user by id # 10,000 /s
A2 get a user's last 20 orders, newest first # 2,000 /s
A3 get an order by id # 500 /s
A4 list all orders for a merchant, by day # 5 /s (reporting)# Now the schema falls out — in DynamoDB single-table form:
PK SK attributes
USER#42 PROFILE name, email # A1
USER#42 ORDER#2026-08-29#9x2 total, status # A2: SK sorts
ORDER#9x2 META items, address # A3
GSI1: MERCHANT#7 2026-08-29#9x2 # A4 via index# A4 is rare and analytical → don't distort the main table for it.
# Stream to a warehouse and query there.
Indexing
An index is a second data structure that makes reads fast and writes slower.
Every index must be maintained on every insert, update and delete, and it consumes
memory and disk.
Index
Answers
Notes
B-tree
Equality, range, prefix, ORDER BY
The default. Sorted, so it serves ranges and ordering for free.
Hash
Equality only
Slightly faster point lookups, useless for ranges. Rarely worth it.
Composite (a, b, c)
Queries on a, a+b, a+b+c
Leftmost prefix rule: a query on b alone cannot use it. Order columns by selectivity and by how you filter.
Covering
The whole query, from the index alone
Include the selected columns so the engine never touches the heap. Big win on hot queries.
Partial / filtered
A subset of rows
WHERE status='pending' on a table that is 99% completed — tiny index, huge win.
Low cardinality is not worth indexing. An index on a boolean
that's 50/50 will be ignored — reading half the rows via an index is slower than
scanning.
Functions kill indexes.WHERE LOWER(email) = ?
can't use an index on email. Index the expression, or store the
normalised form.
Writes pay for every index. Ten indexes on a hot write table
means each insert does eleven writes. Audit for unused indexes.
The optimiser decides, not you. Read the query plan
(EXPLAIN ANALYZE). Stale statistics are a very common cause of "the
index exists but isn't used".
Normalisation vs denormalisation
Normalised
Denormalised
Each fact stored
Once
Many times
Writes
Cheap, single-place, no anomalies
Expensive fan-out; must update every copy
Reads
Joins — more expensive, worse across shards
One lookup, no joins
Consistency
Guaranteed by the schema
Your problem; copies drift
Use when
Write-heavy, integrity matters, query shapes still changing
Read-heavy at scale, known queries, joins can't cross shards
The practical middle: normalise the source of truth, denormalise into
purpose-built read models that are rebuilt from it. Then drift is recoverable —
you can always replay the truth — rather than permanent.
Storage engines: B-tree vs LSM
B-tree (Postgres, MySQL/InnoDB)
LSM tree (Cassandra, RocksDB, ScyllaDB)
Writes
Update in place — random I/O
Append to memtable, flush sequentially — very fast
Reads
Predictable, one tree descent
May check several SSTables; Bloom filters mitigate
Space
Fragmentation
Compaction reclaims, but needs headroom and background I/O
Latency shape
Steady
Great p50, compaction shows up in p99
Pick when
Mixed read/write, transactions
Write-heavy ingest, time-series, huge datasets
ACID and isolation levels
Atomicity — all or nothing. Consistency —
constraints hold. Isolation — concurrent transactions don't
corrupt each other. Durability — committed means it survives a
crash. Isolation is the one with dials:
Level
Prevents
Still allows
Read uncommitted
Nothing
Dirty reads. Effectively never used.
Read committed
Dirty reads
Non-repeatable reads, phantoms. Postgres default.
Repeatable read
+ non-repeatable reads
Phantoms (in the standard); write skew. MySQL default.
Snapshot isolation
Read anomalies via MVCC
Write skew — two transactions each reading a valid state and jointly breaking an invariant.
Serializable
Everything
Nothing — but costs throughput and produces retryable conflicts.
The one to be able to explain: write skew. Two doctors are both
on call; each transaction checks "at least one other doctor is on call", sees the
other, and both go off call. Neither read a stale value, no row was written twice,
and the invariant still broke. Fix with SERIALIZABLE, an explicit
SELECT … FOR UPDATE, or a constraint the database can enforce.
One machine runs out of disk, memory, IOPS or CPU. Vertical scaling buys time
and then stops. Partitioning splits the data so each machine holds a slice — the
only way to scale writes past one box. The price is that anything spanning
slices (joins, transactions, global ordering, unique constraints) becomes hard or
impossible.
Strategies
Strategy
How
Wins
Loses
Range
A–F → s1, G–M → s2 …
Range scans stay on one shard; sorted iteration is natural
Hotspots are almost guaranteed — sequential keys (timestamps, auto-increment IDs) all land on the newest shard
Hash
hash(key) % N
Even distribution, no thought required
Range queries must hit every shard; changing N remaps nearly everything
Consistent hashing
Keys and nodes on a ring
Adding/removing a node moves only ~1/N of keys
More machinery; still needs virtual nodes to be even
Directory / lookup
An explicit key → shard table
Total control; move any tenant anywhere; great for multi-tenant
The lookup service is a new dependency and a single point of failure — it must be cached
Geographic
By user region
Low latency, data residency compliance
Uneven population; cross-region users are awkward
Vertical
Different tables → different databases
Simple first step; isolates a hot table
Only buys a fixed factor; kills joins between the split tables
Consistent hashing, properly
Consistent hashing minimises movement; virtual nodes make the distribution actually even. Used by Cassandra, DynamoDB, and every serious cache cluster.
Choosing the shard key — the four tests
High cardinality. Enough distinct values to spread across
every shard and every future shard. country fails; user_id
passes.
Even access. Not just even data — even traffic. A
perfectly balanced dataset where one key gets 30% of reads is still broken.
Present in your hot queries. If the read path doesn't know
the shard key, every read becomes a scatter-gather across all shards. This is the
mistake that quietly destroys a design.
Keeps together what's read together. Sharding by
message_id means loading one conversation touches every shard.
Sharding by conversation_id makes it one hop.
Hotspots — the three flavours
Sequential keys. Timestamps or auto-increment IDs with range
partitioning send 100% of writes to the last shard. Fix: hash the key,
or prefix it with a bucket — (hash(id) % 16, timestamp).
Celebrity keys. One user with 100M followers. Fix:
special-case them — read-path fan-out instead of write-path
(topic 21), or split the key across sub-keys
and aggregate.
Skewed tenants. One customer is 40% of your data.
Fix: directory-based sharding so that tenant gets dedicated shards.
Resharding without downtime
The best resharding is the one you don't do — so over-partition up front. Create
1,024 logical partitions on day one and map many of them to each
physical node. Growing then means moving whole logical partitions between nodes,
which is a copy-and-repoint operation, not a rehash of every row. (This is
Vitess's and Elasticsearch's model, and Redis Cluster's 16,384 hash slots.)
When you must actually reshard live:
1. Add the new shards, empty. Routing still points at the old layout.
2. Dual-write: every write goes to old AND new locations.
3. Backfill historical rows in the background, throttled.
4. Verify: compare checksums / row counts old vs new; fix drift.
5. Flip reads to the new layout — per-tenant or per-percentage, reversible.
6. Bake. Keep dual-writing for a while so rollback stays free.
7. Stop dual-writing, drop the old data.
# Step 4 is the one people skip and the one that catches the bug.
Routing: who knows where the data lives?
Approach
How
Tradeoff
Client-side
The app library computes the shard
No extra hop, lowest latency; every client must be redeployed to change topology
Proxy
A router tier in front (Vitess, ProxySQL, Twemproxy)
Topology changes are invisible to apps; adds a hop and a component to run
Coordinator / gossip
Any node can route (Cassandra, DynamoDB)
Simplest for clients; the database itself is more complex
What partitioning takes away
Joins across shards — do them in the application, or
denormalise so you don't need them.
Transactions across shards — needs two-phase commit (slow,
blocking on the coordinator) or a saga
(topic 26). Prefer designing so a transaction
fits inside one shard.
Global unique constraints — UNIQUE(email) across
shards needs a separate global index or a dedicated uniqueness service.
Global ordering — no shard knows the global sequence. Use
Snowflake-style IDs (timestamp + machine + counter) for roughly-sortable unique
IDs without coordination.
Cheap aggregates — COUNT(*) becomes
scatter-gather, and its p99 is the slowest shard's p99.
Say this
"I'd shard on conversation_id, hashed, with 1,024 logical
partitions mapped onto 16 physical nodes. Hashed because message IDs are
time-ordered and range partitioning would put every write on the newest shard;
conversation_id because every hot read is 'the last 50 messages in
this conversation', so that read is a single-shard query. The cost is that
'all messages by this user across conversations' becomes a scatter-gather — I'd
serve that from a secondary index rather than distorting the primary key."
07
Replication
leader-followermulti-leaderquorumlagfailover
Why it exists
Four distinct reasons, and they pull in different directions: durability
(a disk dies), availability (a machine dies), read
scale (spread reads over copies), and latency (a copy
near the user). Partitioning splits data to scale writes; replication copies data
to survive failure and scale reads. Real systems do both.
No data loss — but any replica failure blocks writes
Semi-sync
At least one replica
Moderate
No loss if the acked replica survives. Usually the right answer.
Quorums
N = replicas, W = acks required to write, R = replicas read
W + R > N → read and write sets overlap → reads see the latest write
N=3, W=2, R=2 balanced; survives 1 failure either way # the default
N=3, W=3, R=1 fast reads, no write availability if any node is down
N=3, W=1, R=1 fastest, W+R < N → eventually consistent
N=5, W=3, R=3 survives 2 failures; higher latency
Two caveats worth stating aloud: quorum overlap guarantees you read the
latest write, not that concurrent writers are ordered — you still need
last-write-wins or version vectors to resolve conflicts. And "sloppy quorums" with
hinted handoff (Dynamo-style) accept writes on the wrong nodes during a partition,
which buys availability at the cost of the overlap guarantee.
Replication lag and what it breaks
Symptom
What the user sees
Fix
No read-your-writes
Posts a comment, refreshes, it's gone
Route that user's reads to the leader for a few seconds after their write; or read from a replica known to be caught up (compare log positions)
Non-monotonic reads
Sees a comment, refreshes, it vanishes — two replicas at different positions
Pin a user to one replica (hash of user ID)
Causal violation
Sees the reply before the message
Causal consistency, or keep causally related writes on one partition
Stale aggregate
Dashboard shows yesterday's number
Usually fine — but say so out loud rather than letting the interviewer find it
Failover
The steps: detect the leader is gone (a timeout — and you cannot distinguish
"dead" from "slow"), elect a new leader (most up-to-date replica, via consensus),
reconfigure clients to point at it, and handle the old leader coming back.
Split brain
The old leader wasn't dead — it was partitioned. Now two nodes accept writes
and diverge, and reconciling them means choosing whose data to throw away.
Defences: require a majority quorum to elect (a minority
partition cannot form one); use fencing tokens — a monotonically
increasing epoch number that storage checks, so the old leader's writes are
rejected on arrival (see topic 15); and STONITH
— forcibly kill the old node before promoting.
Automatic vs manual failover
Automatic failover has a real failure mode: a transient network blip triggers a
promotion, the promotion loses the un-replicated tail of the write log, and you
have caused an outage to avoid one. Many mature teams run automatic failover for
stateless tiers and human-confirmed failover for the primary database.
Saying this in an interview reads as operational experience.
Say this
"One leader per shard with two followers: one semi-synchronous in another AZ
so a committed write is on at least two machines, one asynchronous for read
scaling and backups. Reads go to followers except right after a user's own write,
where I route to the leader for a few seconds so read-your-writes holds. Failover
is quorum-elected with fencing tokens, because the dangerous case isn't a dead
leader — it's a partitioned one that thinks it's still the leader."
08
Consistency
strongeventualcausalread-after-writemonotonic
Why it exists
The moment data lives in more than one place, "what is the current value?" stops
having one answer. A consistency model is a contract about which answers
are allowed. Stronger models are easier to program against and slower;
weaker models are faster and push the surprises into your application code.
The spectrum
Model
Guarantee
Cost
Use for
Linearizable (strong)
Every read sees the most recent committed write. The system behaves as if there were one copy.
Coordination on every operation; cross-region latency; unavailable during partitions
Balances, inventory at checkout, locks, leader election, uniqueness
Sequential
All nodes see operations in the same order, though not necessarily real-time order
Cheaper than linearizable
Replicated state machines
Causal
Cause is seen before effect. Concurrent writes may be seen in any order.
Track causality (version vectors); no global coordination
Comments and replies, chat, collaborative editing — the sweet spot for social products
Eventual
If writes stop, replicas converge. No promise about when.
Nearly free, always available
Like counts, view counts, DNS, caches, analytics
Session guarantees — the ones users actually notice
These are cheap to provide, sit between eventual and strong, and eliminate most
visible weirdness. Naming them is a strong signal in an interview.
Guarantee
Promise
How to implement
Read-your-writes
You always see your own updates
After a write, route that user to the leader for N seconds; or stamp the client with the write's log position and only read replicas at or past it
Monotonic reads
Time never goes backwards for a reader
Pin a session to one replica (consistent hash of user/session ID)
Monotonic writes
Your writes apply in the order you made them
Same-session writes through the same path, or sequence numbers
Writes follow reads
A write that responds to a read is ordered after it
Attach the read's version to the write
Say this
"I don't want one consistency level for the whole system — I want one per
feature. Posting and immediately seeing your own post needs read-your-writes, so
I'll route a user to the leader briefly after they write. The follower count can
be eventually consistent — nobody notices a two-second lag on a number. The
payment ledger has to be strongly consistent and I'll take the latency hit, and
I'll keep it inside one region so that hit stays small."
Precision that gets noticed
"Eventually consistent" is not "sometimes wrong forever". It is a convergence
promise with an unbounded window. The useful engineering question is how
wide is the window in practice (usually milliseconds), what does a user
see inside it, and what breaks if it's 30 seconds during an incident.
Answer those three and you have said something real.
09
CAP & PACELC
partition toleranceCPAPlatency
Why it exists
CAP names the one tradeoff you cannot design around: when the network splits,
you must choose. It exists to stop people promising both. It is also the most
misquoted theorem in the field, so being precise about it is free credibility.
What CAP actually says
During a network partition (P), a distributed system must choose
between consistency (C — every read sees the latest write) and
availability (A — every request gets a non-error response).
The correction most candidates miss: you don't choose P. Networks
partition; that's physics, not architecture. So the theorem is really "when
partitioned, pick C or A" — CP or AP. A system described as "CA" is a
single-node system, or a system that hasn't thought about it.
The whole theorem in one picture. Everything else is which side of it your feature belongs on.
PACELC — the more useful question
CAP only describes the rare case. PACELC covers the other 99.9% of the time:
if (P)artition: choose (A)vailability or (C)onsistency
(E)lse: choose (L)atency or (C)onsistency
The "else" branch is what you live with daily. Every synchronous cross-region
replication is a decision to spend latency on consistency — and that decision is
made on every request, not once a year during an outage.
System
PACELC
In plain terms
Cassandra / DynamoDB (default)
PA/EL
Stay up during partitions; keep normal reads fast. Both tunable per query.
MongoDB (default settings)
PA/EC
Replica set keeps serving; normal reads go to the primary.
HBase, Zookeeper, etcd
PC/EC
Correctness over uptime, always. That's why they hold cluster metadata.
Google Spanner
PC/EC
Strong globally — paid for with atomic clocks and commit-wait latency.
MySQL with async replicas
PC/EL
Writes stop without a primary; reads are fast and possibly stale.
Say this
"For the shopping cart I'd go AP — if a region is partitioned I would much
rather accept the add-to-cart and merge later than show an error; a merged cart
with one extra item is a far better outcome than a failed sale. For the payment
and inventory decrement at checkout I'd go CP: I'd rather fail the transaction
than double-sell the last unit. Same product, opposite answers, because the cost
of being wrong is different. And under PACELC, in the normal no-partition case,
the cart is EL and the ledger is EC."
Don't say
"We'll pick CA." Not an option in a distributed system.
"CAP means you pick two of three." Sloppy — you always have P; you pick
between C and A during a partition.
"Cassandra is AP." Nearly right, but it's tunable: QUORUM reads
and writes buy you strong-ish consistency per query. Saying "AP by default,
tunable per query" is the accurate version.
Applying one letter to a whole product. CAP applies per operation.