System design, part 3 of 12
Data Systems
The depth behind "which database, and why". Building Blocks introduced databases, replication and sharding as boxes on a diagram. This page opens the boxes: how engines store data, what an index and an isolation level really guarantee, how replicas and partitions behave under failure, how to model data, and how analytics, streams and search fit around the primary store. Product behaviour is described at the level that is widely documented; details vary by version, so check the manual before you quote one as fact.
Storage engines
Part 1 of 8 · how a database puts bytes on disk
Almost every store is a write-ahead log plus one of two on-disk structures: a B-tree (update in place, read-optimised) or an LSM-tree (append and merge, write-optimised). Knowing which one sits under a product explains most of its performance behaviour.
- Write-ahead log: durability before anything else
- B-tree: pages updated in place
- LSM-tree: memtable, SSTables, compaction
- B-tree vs LSM-tree: the comparison table
- Row store vs column store: why analytics uses columns
- In-memory stores and persistence: snapshot vs append-only log
Write-ahead log
Rule: a change is appended to a sequential log and flushed to disk before the commit is acknowledged; the data files are updated later. Sequential appends are cheap, random page writes are not, so the log buys durability without paying for random I/O on the commit path.
- Group commit: many transactions share one fsync, which is how a single disk reaches thousands of commits per second.
- Durability knob: fsync on every commit (safe, slower) vs fsync every N ms (faster, can lose the last window on power loss). Most products expose this setting; know which one your design assumes.
- Second life: the same log feeds replication and change data capture (see Replication logs and CDC and outbox).
Failure mode: "committed" means "in the log on this machine's disk". If the disk dies before a replica has the record, the write is gone unless replication is synchronous.
B-tree
A balanced tree of fixed-size pages (commonly 4 to 16 KB). Interior pages hold keys and child pointers; leaves hold the rows or pointers to them, linked for range scans. A write finds the leaf and overwrites the page in place.
- Depth: with a branching factor in the hundreds, 3 to 4 levels cover hundreds of millions to billions of keys. The top levels stay cached, so a point read costs roughly one disk read (order of magnitude).
- Writes: each change goes to the WAL and later rewrites a whole page, even for a one-byte change. A full page splits in two and the parent is updated.
- Costs: random I/O on write, fragmentation (pages are typically partly empty), and random-key inserts (for example random UUID primary keys) touch pages all over the tree.
- Used by: PostgreSQL, MySQL InnoDB, SQL Server, Oracle, SQLite and most relational engines.
LSM-tree
Log-structured merge tree: never update in place. Writes go to the WAL and a sorted in-memory table (memtable); a full memtable is flushed as an immutable sorted file (SSTable); background compaction merges files and drops overwritten and deleted entries.
A read checks the memtable, then SSTables from newest to oldest. A Bloom filter per SSTable answers "definitely not here" or "maybe here", so most files are skipped without a disk read.
- Bloom filter numbers: about 10 bits per key gives roughly a 1% false-positive rate. No false negatives. It helps point lookups, not range scans.
- Deletes are writes of a tombstone; space is reclaimed only when compaction drops it. Many tombstones in a scanned range slow reads.
- Compaction strategy: size-tiered (cheaper writes, more space and more files per read) vs levelled (better reads and space, more rewriting).
- Used by: RocksDB, LevelDB, Cassandra, HBase, ScyllaDB; RocksDB is embedded in many other systems.
Failure mode: if writes outpace compaction, files pile up, reads slow down and the engine eventually stalls or throttles writes. Compaction also competes with foreground traffic for disk, which shows up as p99 spikes.
B-tree vs LSM-tree
Use a B-tree engine for read-heavy and transactional workloads with predictable latency. Use an LSM engine when sustained write volume or storage cost dominates.
| Aspect | B-tree | LSM-tree |
|---|---|---|
| Write path | WAL, then overwrite a page in place (random I/O) | WAL plus memtable; sequential flush and merge |
| Write amplification | Whole page rewritten per change, plus WAL | Each record rewritten several times by compaction; roughly 10x or more with levelled compaction, less with size-tiered (workload dependent) |
| Read path | One root-to-leaf walk; each key lives in one place | Memtable plus several SSTables; Bloom filters and block cache hide most of it |
| Range scans | Follow linked leaves | Merge across levels |
| Space | Fragmentation, partly filled pages | Compresses well; temporary overhead during compaction, stale versions until merged |
| Latency profile | Steadier | Higher write throughput, compaction can hurt tail latency |
| Transactions | Natural fit for row locks on a single copy of each key | Possible, but built on top (snapshots, sequence numbers) |
| Typical products | PostgreSQL, MySQL InnoDB, SQL Server, Oracle | RocksDB, Cassandra, HBase, ScyllaDB, LevelDB |
Senior signal: say "it depends on the workload, and I would measure" and then name the three amplifications you are trading: write, read and space. You can tune any two at the cost of the third.
Row store vs column store
A row store keeps all columns of a row together: ideal for "fetch or update one entity". A column store keeps each column together: ideal for "aggregate a few columns over billions of rows".
- Why columns win for analytics: read only the needed columns; similar values sit together so compression is strong (dictionary, run-length, delta); min/max statistics per block let the engine skip blocks; vectorised execution processes a batch of values per CPU step.
- What you pay: single-row writes and updates are expensive, so column stores ingest in batches and often treat files as immutable.
- Products: Parquet and ORC (file formats), ClickHouse, BigQuery, Snowflake, Redshift, DuckDB.
Naming trap: "wide-column" stores such as Cassandra and HBase are not column stores. They are row-oriented LSM stores with flexible columns per row.
In-memory stores and persistence
In-memory stores (Redis, Memcached) are fast because they avoid disk on the read path and use simple data structures, not because RAM is magic. Sub-millisecond operations are normal; the network round trip usually dominates. The question an interviewer asks next is "what happens on restart?".
| Option | How | Data lost on crash | Cost |
|---|---|---|---|
| None | Pure cache (Memcached) | Everything; cold cache on restart | Nothing |
| Snapshot | Periodic point-in-time dump of the dataset (Redis RDB, via fork and copy-on-write) | Everything since the last snapshot (minutes) | Fork and memory spike on large datasets; compact file, fast restart |
| Append-only log | Log every write command (Redis AOF); fsync always, every second, or left to the OS | About one second with the per-second setting; none of the acknowledged writes with fsync always | Larger file, needs rewriting, slower restart; fsync always costs throughput |
| Both | Snapshot plus log tail | As the log setting | Both costs; common production choice |
| Replication | Replica in another zone | The async replication window | More machines |
Trade-off: persistence makes a cache restart warm; it does not make it a system of record. If losing the data is unacceptable, write to a durable database first and treat the in-memory copy as derived.
Indexes and queries
Part 2 of 8 · making reads cheap without making writes expensive
An index is a second, sorted copy of some columns that the database must keep in step with every write. Every index is a read-versus-write trade.
- Primary, secondary, clustered: where the row actually lives
- Composite and covering indexes: the leftmost-prefix rule
- When an index hurts: write cost and low selectivity
- Reading a query plan: what to look for
- Index types: hash, B-tree, inverted, geospatial
- The N+1 query problem
- Pagination: offset vs keyset
Primary, secondary, clustered
- Primary index: on the primary key; unique, one per table. Secondary index: on any other column(s); may be non-unique.
- Clustered index: the table is the index; leaf pages hold the full rows in key order. Only one per table.
- Non-clustered index: leaves hold a pointer to the row (a physical location, or the primary key).
- Clustered consequences: range scans on the primary key are fast and sequential; the primary key is copied into every secondary index, so keep it short; random keys cause page splits, so prefer time-ordered keys (auto-increment, or a time-sortable ID).
- Heap consequences: no key-order locality for free; an update that moves a row may need index entries updated too.
Composite and covering indexes
A composite index on (a, b, c) is sorted by a, then b within equal a, then c. Leftmost-prefix rule: it can be used efficiently for conditions on a, on a, b, or on a, b, c, but not for b alone.
| Query on index (user_id, status, created_at) | Index use |
|---|---|
WHERE user_id = 7 | Yes, prefix |
WHERE user_id = 7 AND status = 'PAID' ORDER BY created_at DESC | Yes, and the sort comes free from index order |
WHERE user_id = 7 AND created_at > ? | Seeks on user_id only; created_at is filtered while scanning that range |
WHERE status = 'PAID' | No efficient seek; the leading column is missing |
WHERE user_id = 7 AND created_at > ? AND status = 'PAID' on index (user_id, created_at, status) | Seek stops being precise after the range column; status is only a filter |
- Column order rule of thumb: equality columns first, then the range or sort column, then extra columns you only want to read.
- Covering index: the index contains every column the query needs, so the engine answers from the index alone (an "index-only scan") and skips the row fetch. Some engines let you add non-key columns for this (
INCLUDE). - One composite index usually beats several single-column indexes that the planner would have to combine.
When an index hurts
- Write cost: every insert, delete, and update of an indexed column must maintain every affected index. Five indexes means roughly six structures written per insert. Indexes also take memory and disk, and compete with data for the buffer cache.
- Low selectivity: an index on
statuswith three values, or a boolean, returns a large fraction of the table. Fetching that many rows through an index is random I/O, so the planner prefers a sequential scan. Fix with a composite index, or a partial index on the rare value (for example onlystatus = 'PENDING'). - Not usable: wrapping the column in a function (
WHERE lower(email) = ?without an expression index), implicit type casts, and leading wildcards (LIKE '%abc') defeat a B-tree index. - Unused indexes: pure cost. Review index usage statistics and drop them.
- Building one: creating an index on a large live table is a long, I/O-heavy operation; use the online or concurrent build option and expect replica lag.
Interview tip: when you add an index in a design, say which query it serves and what it costs on the write path. "Index on (user_id, created_at) for the feed query; writes are 500/s so the extra index is affordable."
Reading a query plan
A plan is a tree; rows flow from the leaves (table and index accesses) up through joins, sorts and aggregates. EXPLAIN shows the estimate; the "analyze" variant runs the query and shows actual rows and time. The output below is illustrative, in PostgreSQL's style.
| Look for | What it tells you |
|---|---|
| Access method | Sequential (full) scan on a big table for a selective query means a missing or unusable index. A full scan for a query returning most of the table is correct. |
| Estimated vs actual rows | A large mismatch (10x or more) means stale statistics or correlated columns; the planner then picks the wrong join method. |
| Join method | Nested loop: good when the outer side is small and the inner side is indexed. Hash join: large unsorted inputs, equality joins. Merge join: both inputs already sorted. |
| Rows removed by filter | Many rows read and then discarded means the index is not selective enough for this predicate. |
| Sort or hash spilling to disk | The operation did not fit in working memory; add an index that provides the order, or reduce the row set earlier. |
| Loops | An inner node executed thousands of times is the N+1 pattern inside one query. |
Index types
| Type | Structure | Good for | Cannot do | Seen in |
|---|---|---|---|---|
| B-tree | Sorted balanced tree | Equality, ranges, prefix match, ORDER BY | Full-text, suffix match, multi-dimensional proximity | Default in relational databases |
| Hash | Hash table from key to location | Exact-match lookups, O(1) on average | Ranges, ordering, prefix | Key-value stores, hash indexes, hash joins |
| Inverted | Term to sorted list of document ids | Full-text search, "contains" on arrays and JSON | Cheap updates; ordering by arbitrary columns | Lucene, Elasticsearch, PostgreSQL GIN |
| Geospatial | R-tree, or a space-filling curve (geohash, S2, H3 cells) stored in a B-tree | "Within radius", bounding box, nearest neighbours | Anything non-spatial | PostGIS (GiST), MongoDB 2dsphere, Redis GEO |
| Bitmap | One bitmap per distinct value | Combining low-cardinality filters in analytics | High write rates | Column stores, warehouses |
Interview tip: for "find drivers near me", say how the two dimensions become indexable: map latitude and longitude to a cell id (geohash or similar), index the cell id, query the cell and its neighbours, then filter by exact distance.
The N+1 query problem
One query fetches N parents, then the code runs one more query per parent for its children: N+1 round trips. Each query is fast; the page is slow. At about 1 ms per round trip, 200 items cost 200 ms of pure waiting.
- Usually created by lazy loading in an ORM or by a GraphQL resolver per field; the fix is eager loading or a batching loader.
- The same shape exists across services: a loop of single-item RPCs. Offer a batch endpoint.
- Detect it by counting queries per request in tests or tracing, not by looking at slow-query logs (no single query is slow).
Pagination
Use keyset (cursor) pagination for feeds, timelines and any large or changing list. Use offset only for small result sets where "jump to page 37" matters.
| Aspect | Offset | Keyset / cursor |
|---|---|---|
| Cost of page k | Grows with the offset: reads offset + limit rows | Constant: one index seek plus limit rows |
| Concurrent inserts | Rows shift; items are skipped or shown twice | Stable relative to the cursor |
| Jump to arbitrary page | Yes | No, only next and previous |
| Requirements | None | A unique, indexed sort key; add id as a tie-breaker |
| API shape | ?page=3&size=20 | ?after=opaque_cursor&limit=20 |
- Make the cursor opaque (encode the last sort key values) so you can change the scheme later.
- Do not return an exact total count on large lists; counting is a full scan. Return "has more", or an estimate.
- In partitioned stores offset is worse: each shard must return offset + limit rows to the coordinator.
Transactions
Part 3 of 8 · what the database promises when writes overlap
Most correctness bugs in a design come from concurrent transactions, not from crashes. This part is the model; exact behaviour of each isolation level differs by product, so treat the tables as the general picture and verify against the engine you name.
- ACID, precisely
- Isolation levels and anomalies: the table
- MVCC: readers do not block writers
- Lost update: the bank example
- Write skew: the booking example
- Optimistic vs pessimistic locking
- Deadlocks
- A safe balance debit: atomic conditional update
ACID, precisely
| Letter | Precise meaning | Mechanism | Common misreading |
|---|---|---|---|
| Atomicity | All of the transaction's writes take effect, or none do, even on a crash | Undo information, WAL, rollback | It is about abort, not about concurrency |
| Consistency | Each transaction moves the data from one state that satisfies the declared invariants to another | Constraints, plus correct application logic | Not the C in CAP (which means linearizability). Largely the application's job |
| Isolation | Concurrent transactions behave as if they ran in some serial order, to the degree the chosen level provides | Locks, MVCC, conflict detection | The default level is usually weaker than serializable |
| Durability | Once commit is acknowledged, the data survives a crash of this node | WAL flush, replication | It does not cover disk loss unless a replica has the write |
Senior signal: "ACID" on a product page tells you little. Ask which isolation level is the default, and whether a transaction can span more than one partition.
Isolation levels and anomalies
The anomalies first, then which level admits which.
| Anomaly | What happens |
|---|---|
| Dirty read | You read another transaction's uncommitted write, which may later roll back |
| Non-repeatable read | You read the same row twice in one transaction and get different committed values |
| Phantom | You run the same predicate query twice and the set of matching rows changes (rows inserted or deleted by others) |
| Lost update | Two transactions read a value, both compute a new one, and the second write silently overwrites the first |
| Write skew | Two transactions read overlapping data, each writes a different row, and together they break an invariant neither breaks alone |
| Level (general model) | Dirty read | Non-repeatable read | Phantom | Lost update | Write skew |
|---|---|---|---|---|---|
| Read uncommitted | Possible | Possible | Possible | Possible | Possible |
| Read committed | Prevented | Possible | Possible | Possible | Possible |
| Repeatable read (SQL standard) | Prevented | Prevented | Possible per the standard | Implementation dependent | Implementation dependent |
| Snapshot isolation | Prevented | Prevented | Not seen by snapshot reads | Prevented where the engine detects write-write conflicts (first committer wins) | Possible |
| Serializable | Prevented | Prevented | Prevented | Prevented | Prevented |
Names differ by product. The SQL standard defines levels by three anomalies only, and does not mention snapshot isolation, so vendors mapped their implementations onto the standard names differently. Widely documented examples (verify for your version):
| Product | Default | Worth knowing |
|---|---|---|
| PostgreSQL | Read committed | Its "repeatable read" is snapshot isolation: a concurrent update of the same row aborts with a serialization error, write skew is still possible. Its "serializable" is serializable snapshot isolation (optimistic; be ready to retry). Read uncommitted behaves as read committed. |
| MySQL InnoDB | Repeatable read | Plain reads use a consistent snapshot; locking reads and writes use row and gap locks, which block many phantoms. A read-then-write with a plain SELECT can still lose an update, because no write conflict is detected. |
| Oracle | Read committed | Its "serializable" is snapshot isolation, so write skew is possible. |
| SQL Server | Read committed | Offers lock-based repeatable read and serializable, and a separate snapshot level. |
- How serializable is implemented: actual serial execution on one thread (fast only for short in-memory transactions), two-phase locking (readers and writers block each other), or serializable snapshot isolation (run optimistically, abort on detected dependency cycles).
- Cost: stronger levels mean more blocking or more aborts. The application must retry aborted transactions.
Interview tip: do not say "I will use repeatable read to fix it". Name the anomaly (lost update, write skew), then the mechanism that prevents it in your chosen database: an atomic update, a row lock, a constraint, or true serializable.
MVCC
Multi-version concurrency control: a write creates a new version of the row instead of overwriting it. Each transaction reads the versions that were committed as of its snapshot. Result: readers never block writers and writers never block readers; only writers to the same row conflict.
- Snapshot scope: per statement gives read committed; per transaction gives snapshot isolation.
- Garbage: old versions must be cleaned up once no snapshot can see them (PostgreSQL vacuum, InnoDB purge of undo logs).
- Failure mode: one long-running transaction (a forgotten session, a slow analytics query, a stuck replica slot) pins old versions, so tables bloat and queries slow down. Keep OLTP transactions short and run analytics elsewhere.
Lost update
The read-modify-write race. Account 42 has 1000. A debit of 500 and a debit of 300 arrive together; the application reads the balance, subtracts in code and writes the result.
| Fix | How | Note |
|---|---|---|
| Atomic update | UPDATE ... SET balance = balance - 500 | Best when the new value can be computed in SQL; see a safe balance debit |
| Explicit lock | SELECT ... FOR UPDATE, then write | Needed when logic must run in the application between read and write |
| Compare-and-set | UPDATE ... WHERE version = :seen; retry if 0 rows | Optimistic; works across a user's think time |
| Automatic detection | Snapshot isolation that aborts the second writer | Engine specific; the application must retry |
Write skew
Pattern: check a condition with a query, then write a row that changes the result of that query, while another transaction does the same. Booking example: two users book room 12 for 10:00 to 11:00 at the same time.
Bank variant: a customer may overdraw one account as long as savings + current stays at or above zero. Two withdrawals, one from each account, each check the sum on its own snapshot, each pass, and together they push the sum below zero.
| Fix | How | Trade-off |
|---|---|---|
| Constraint | Unique index on (room_id, slot), or an exclusion constraint on overlapping time ranges where the engine supports one | Cheapest and safest; needs the invariant to be expressible as a constraint |
| Lock a parent row | SELECT ... FROM rooms WHERE id = 12 FOR UPDATE before checking (materialising the conflict) | Serialises bookings per room; simple and portable |
| True serializable | Run at a serializable level and retry on abort | General; costs aborts or blocking under contention |
| Single writer | Route all bookings for a room through one queue partition or actor | No database locks; adds latency and a moving part |
Interview tip: any "check then insert" in your design (seat booking, username claim, inventory reserve, coupon redemption) should trigger this discussion before the interviewer raises it.
Optimistic vs pessimistic locking
| Aspect | Pessimistic (SELECT FOR UPDATE) | Optimistic (version column / compare-and-set) |
|---|---|---|
| Assumption | Conflicts are likely | Conflicts are rare |
| On conflict | The second transaction waits | The second write fails and must retry |
| Wins when | High contention on the same rows (flash sale stock, a hot counter); retry storms would waste more work than waiting | Low contention; long gaps between read and write (a user editing a form); no open transaction across a network call |
| Risks | Deadlocks, lock waits, connections held while blocked | Starvation and wasted work under contention |
| Beyond one database | Does not extend to HTTP APIs or stores without transactions | Maps directly to ETags / If-Match and to conditional writes in key-value stores |
- Keep locked sections short: no network calls or user interaction while holding a row lock.
FOR UPDATE SKIP LOCKED(where supported) turns a table into a simple job queue: each worker takes rows nobody else holds.- Optimistic retries need a cap and jittered backoff.
Deadlocks
Two transactions each hold a lock the other needs. Neither can proceed. Classic case: transfer A to B and transfer B to A at the same moment, each locking its source account first.
- Prevent: acquire locks in a consistent global order (always lock the lower account id first); keep transactions short; touch as few rows as possible.
- Survive: the victim gets an error; retry the whole transaction. A lock wait timeout bounds the damage where detection is not available.
- Hidden sources: gap and range locks, foreign key checks, and bulk updates touching rows in different orders.
- Across services there is no detector: use timeouts, and avoid holding a resource while calling another service.
A safe balance debit
Put the check and the change in one statement. The row lock taken by the UPDATE makes the condition and the write atomic, at any isolation level from read committed up.
- Never read the balance into the application, compare, and then write an absolute value.
- A
CHECK (balance_minor >= 0)constraint is a cheap second line of defence. - Idempotency: the unique transfer id (or idempotency key) makes a client retry safe; the duplicate insert fails and the whole transaction rolls back.
- Transfers: debit and credit in one transaction, locking accounts in id order. If the accounts live in different databases you need the saga or two-phase patterns from Distributed Systems Patterns.
- The same idea in a key-value store is a conditional write: "set balance = balance - x if balance >= x".
Replication in depth
Part 4 of 8 · several copies, and what each one may show you
Replication gives availability, read scaling and geographic locality. The price is that copies can disagree, for a moment or for longer. The design question is always "who accepts writes, and what does a reader see?".
- Single-leader, multi-leader, leaderless
- Replication logs: statement, WAL shipping, logical
- Lag anomalies and fixes
- Quorum reads and writes
- Sloppy quorums and repair
- Conflict resolution: LWW, version vectors, CRDTs
Single-leader, multi-leader, leaderless
Default to single-leader. Move to multi-leader only for multi-region writes or offline clients, and to leaderless when write availability matters more than simple consistency.
| Aspect | Single-leader | Multi-leader | Leaderless |
|---|---|---|---|
| Write path | All writes to one leader, which streams changes to followers | Each leader accepts writes and replicates to the others asynchronously | Client or coordinator sends each write to all N replicas and waits for W acks |
| Conflict handling | None: the leader orders all writes | Required: concurrent writes to the same item on different leaders | Required: concurrent writes and missed writes; resolved on read or in the background |
| Failover | Detect failure, promote a follower, repoint clients. Risks: lost unreplicated writes, split brain | Other leaders keep accepting writes; no promotion needed | No failover: other replicas keep serving while quorum holds |
| Consistency you get | Strong on the leader; followers lag unless replication is synchronous | Eventual; conflicts possible | Eventual, tunable per request with R and W |
| Use when | Most OLTP systems | Active-active regions, offline-first and collaborative apps | High write availability, simple key-based access |
| Examples | PostgreSQL, MySQL, MongoDB replica sets | Multi-region active-active setups, CouchDB-style sync | Dynamo-style stores: Cassandra, Riak, ScyllaDB |
- Sync vs async followers: fully synchronous means one slow follower stalls all writes; fully asynchronous means failover can lose acknowledged writes. A common middle is semi-synchronous: one follower must confirm, the rest are async.
- Split brain: two nodes both believe they are leader and both accept writes. Prevent with a majority-based election and fencing tokens (covered in Distributed Systems Patterns).
Replication logs
| Type | What is shipped | Strength | Weakness |
|---|---|---|---|
| Statement-based | The SQL text | Compact | Non-deterministic statements (NOW(), RAND(), auto-increment under concurrency, triggers) can make replicas diverge |
| WAL shipping (physical) | The engine's byte-level log records | Exact copy, low overhead, simple | Tied to the storage format: replicas generally need the same major version; cannot replicate a subset or feed other systems easily |
| Logical (row-based) | Row-level changes: inserted, updated, deleted values | Decoupled from storage format: cross-version upgrades, selective replication, and the feed for change data capture | More verbose; schema changes need care |
Examples: PostgreSQL streaming replication is physical and it also offers logical replication; MySQL's binlog supports statement, row and mixed formats, with row-based the modern default.
Lag anomalies and fixes
With asynchronous followers, a read from a follower can be behind the leader. Lag is usually well under a second and can grow to seconds or minutes under load, long transactions or network trouble.
| Guarantee | Anomaly without it | Fixes |
|---|---|---|
| Read-your-writes | You do not see your own update | Read your own data from the leader; pin a user to the leader for a short window after a write; or send the write's log position and wait until the replica has reached it |
| Monotonic reads | Time goes backwards: a refresh shows older data because it hit a more-lagged replica | Route each user to the same replica (hash of user id); or track the last-seen position and refuse older replicas |
| Consistent prefix | Effects appear before causes: a reply is visible before the question | Keep causally related writes in the same partition so they are applied in order; or track causal dependencies explicitly |
Senior signal: when you add read replicas, say which reads may be stale and which may not. "Profile and timeline reads go to replicas; the page right after an edit, and anything in a checkout flow, reads from the leader."
Quorum reads and writes
Leaderless stores keep N replicas per key. A write succeeds when W replicas acknowledge; a read queries R replicas and takes the newest version. If W + R > N, every read set overlaps every write set in at least one replica.
| N, W, R | Behaviour |
|---|---|
| 3, 2, 2 | The usual balance: tolerates one replica down for both reads and writes |
| 3, 3, 1 | Fast reads; any replica down blocks writes |
| 3, 1, 3 | Fast writes; any replica down blocks consistent reads |
| 3, 1, 1 | Fastest and most available; W + R is not greater than N, so stale reads are expected |
Trade-off: W + R > N is not linearizability. Concurrent writes, a write that reached fewer than W replicas and was reported as failed but not rolled back, sloppy quorums, and replicas restored from older data can all still produce stale or surprising reads.
Sloppy quorums and repair
| Mechanism | What it does | Catch |
|---|---|---|
| Sloppy quorum | If some of a key's home replicas are unreachable, accept the write on other healthy nodes so W can still be met | Higher write availability, but the overlap guarantee is gone until the data is handed back |
| Hinted handoff | The stand-in node stores the write with a hint naming the intended replica and forwards it when that replica returns | Hints are kept for a limited time; a long outage needs full repair |
| Read repair | A read that sees differing versions writes the newest back to stale replicas | Only fixes keys that are read |
| Anti-entropy | A background process compares replicas (commonly with Merkle trees, so only differing ranges are exchanged) and copies missing data | Costs I/O; if it is not run within the tombstone retention period, deleted data can reappear |
These mechanisms come from the Dynamo paper and appear, with variations, in Cassandra, Riak and similar stores.
Conflict resolution
Multi-leader and leaderless systems accept concurrent writes to the same key. Something must decide the outcome.
| Approach | How | What you pay |
|---|---|---|
| Last-write-wins (LWW) | Attach a timestamp to each write; the highest wins, the rest are discarded | Silent data loss. Concurrent writes are dropped, and clock skew can make an older write beat a newer one. Acceptable for caches and immutable or write-once keys |
| Version vectors | Keep a counter per replica with each value; comparing vectors shows whether one version descends from the other or they are concurrent | Detects conflicts without losing data, but then hands the concurrent versions ("siblings") to the application to merge |
| Application merge | Domain logic: union the two carts, keep both edits, ask the user | Code per data type; deletes need tombstones or removed items come back |
| CRDTs | Data types whose merge is built in and always converges | See below |
| Avoid the conflict | Route all writes for a given record to one leader or region | Loses write availability for that record when its home is down |
CRDTs, honestly: conflict-free replicated data types (counters, sets, maps, sequences for text) are designed so that replicas which have received the same updates converge to the same state, in any delivery order, with no coordination. That guarantee is convergence, not correctness of intent: the merged result is deterministic but may not be what either user wanted, and invariants that span values ("balance never below zero", "seat sold once") cannot be enforced by a CRDT alone. They also carry metadata that grows and needs garbage collection. They fit collaborative editing, presence, likes and counters; they do not replace transactions.
Partitioning in depth
Part 5 of 8 · what changes once data is split
Building Blocks covered why to shard, hash vs range keys and consistent hashing. This part covers what comes next: moving data when the cluster changes, finding the right node, indexing across partitions, and skew.
Rebalancing strategies
Goal: when nodes are added or removed, move as little data as possible, keep serving traffic, and end with even load. hash(key) mod N fails the first goal: changing N moves almost every key.
| Strategy | How | Gain | Pay | Seen in |
|---|---|---|---|---|
| Fixed number of partitions | Create many more partitions than nodes up front (for example 1024 for 10 nodes). A new node takes whole partitions from the others; keys never change partition | Simple; only whole partitions move | The count is hard to change later: too few limits growth, too many adds overhead | Redis Cluster (16384 slots), Elasticsearch shards, Riak, Couchbase |
| Dynamic splitting | A partition that grows past a size threshold splits in two; small ones can merge | Partition count follows data volume; works for range partitioning | A new empty table starts as one partition (a hotspot) unless pre-split | HBase, MongoDB chunks, range-partitioned SQL systems |
| Proportional to nodes | A fixed number of partitions (virtual nodes) per node; a new node picks ranges to split and takes half of each | Partition size stays stable as the cluster grows | Random splits can be uneven; needs hash partitioning | Cassandra virtual nodes |
- Throttle the move: rebalancing competes with live traffic for disk and network; it runs for hours on large clusters.
- Automatic vs manual: fully automatic rebalancing plus automatic failure detection can cascade: a slow node is declared dead, its data is moved, and the extra load slows more nodes. Many operators keep a human approval step.
Request routing
Something must know which node owns a key right now, and learn quickly when that changes. Three places to put that knowledge:
| Approach | Gain | Pay | Seen in |
|---|---|---|---|
| Any node forwards or redirects | Simple clients, no extra tier | Possible extra hop; nodes must share the map (gossip) | Cassandra (coordinator node), Redis Cluster (MOVED redirect) |
| Routing tier | Thin clients; routing logic changes in one place | Extra hop and a tier to scale and keep available | MongoDB mongos, proxy-based sharding layers |
| Partition-aware client | No extra hop | Smarter client library in every language; stale maps must be refreshed | Kafka clients, cluster-aware Redis and Cassandra drivers |
The map's source of truth is either a coordination service (ZooKeeper, etcd, or a built-in consensus group) that nodes register with and routers watch, or a gossip protocol among the nodes. A coordination service gives one authoritative answer; gossip avoids the dependency but converges eventually.
Secondary indexes: local vs global
Data is partitioned by primary key. A query on another attribute ("all red cars") does not know which partition to ask.
| Aspect | Local (document-partitioned) | Global (term-partitioned) |
|---|---|---|
| Write | One partition: data and index together, atomically | Data partition plus one or more index partitions; usually updated asynchronously |
| Read by indexed attribute | Scatter-gather across all partitions; latency follows the slowest partition | One index partition, then fetch the rows |
| Consistency | Index always matches the data in its partition | Often eventually consistent with the base data |
| Seen in | MongoDB, Cassandra, Elasticsearch | DynamoDB global secondary indexes |
Interview tip: if the query can include the partition key ("red cars for this dealer"), a local index is enough and there is no scatter. Design the access path so that it usually can.
Hot keys and skew
Hashing spreads keys evenly; it does not spread load evenly when one key receives a large share of traffic (a celebrity account, a viral post, a huge tenant, today's date as a key).
| Cause | Fix | Cost |
|---|---|---|
| One key read very often | Cache it (in process and in a shared cache); add replicas for that partition | Staleness |
| One key written very often | Salt the key: append a suffix 0 to k-1 so writes spread over k partitions | Reads must query k keys and merge; needs bookkeeping of which keys are salted |
| Hot counter (likes, views) | Buffer and batch increments; sharded counters summed on read; approximate counts | Slightly stale or approximate value |
| Monotonic key with range partitioning (timestamp, auto-increment) | Lead the key with something else (tenant, device, hash prefix), keep time second | Global time-range scans now fan out |
| One huge tenant | Give it a dedicated partition or cluster; route by a tenant directory | Special-case operations |
| Partition too large (unbounded rows under one key) | Add a time bucket to the partition key | Queries spanning buckets do several reads |
Senior signal: ask "what is the distribution of the partition key?" before choosing it. Detect hot partitions with per-partition metrics; averages across the cluster hide them.
Cross-partition transactions
- First choice: avoid them. Pick the partition key so that everything one transaction touches lives together (all of a user's orders, all rows of one tenant). Single-partition transactions stay cheap and strongly consistent.
- When you cannot: the options are two-phase commit (atomic, but blocking and slower), sagas with compensating actions (available, but only eventually consistent and visible in intermediate states), or a distributed SQL database that runs consensus and two-phase commit internally and charges you in latency.
- Cross-partition reads (joins, aggregates) are scatter-gather; move them to a derived store built for the query (a search index or a warehouse).
The mechanics, failure cases and when each applies are in Distributed Systems Patterns.
Data modelling
Part 6 of 8 · shaping data for the queries you will run
In a relational database you model the entities and let queries be flexible. In key-value, wide-column and document stores you start from the list of access patterns and build the keys to serve them.
Normalisation vs denormalisation
Start normalised. Denormalise a specific read path when you have measured (or can argue from numbers) that the join or aggregation is the bottleneck, and say how the copy is kept in step.
| Aspect | Normalised | Denormalised |
|---|---|---|
| Idea | Each fact stored once; reference by id | Copy or precompute data where it is read |
| Writes | One place to update; cheap; no update anomalies | Every copy must be updated: fan-out, possible inconsistency |
| Reads | Joins at read time | One lookup; predictable latency |
| Storage | Smaller | Larger |
| Flexibility | New queries are easy | Shaped for known queries; new ones may need a backfill |
| Fits | OLTP with varied queries, strong integrity needs | Read-heavy paths, stores without joins, feeds, counters, search documents |
- Common denormalisations: a counter column (
like_count), a copied display field (author name on a post), a precomputed feed, a materialised view. - Keeping copies in step: same transaction (simple, same database only), asynchronous via change data capture or events (scales, eventually consistent), or periodic rebuild. Always keep a way to recompute from the source of truth.
- Copy values that rarely change (a product name at order time is in fact the correct historical record); avoid copying values that change often.
Modelling for access patterns
In stores such as DynamoDB and Cassandra the partition key decides which node holds an item and the sort key (clustering key) orders items inside the partition. An efficient query names one partition key and a range of sort keys. There are no joins, so each access pattern gets a key design.
Worked example: chat messages.
| Access pattern | Key design |
|---|---|
| Latest 50 messages in a conversation; older pages on scroll | Table messages: partition key conversation_id, sort key message_id (time-sortable), read descending with a limit |
| A user's conversations, most recent first | Table user_conversations: partition key user_id, sort key last_activity_at; rewritten on each new message |
| Fetch one message by id | Same messages table when the caller knows the conversation; otherwise a lookup table or index |
- Partition size: a conversation with millions of messages makes one huge partition. Add a bucket: partition key
(conversation_id, month). - Single-table style (DynamoDB): store several entity types in one table with generic keys, for example
PK = USER#7withSK = PROFILEandSK = ORDER#2026-11-02#9001, so "user with recent orders" is one query. It is efficient and opaque: easy to get wrong, hard to query ad hoc. - Orders by user and by id: base table keyed by
order_id, plus a second table or global index keyed by(user_id, created_at). Two access patterns, two key designs, written together.
Trade-off: you get predictable single-digit-millisecond reads at any scale for the patterns you designed for, and you give up ad hoc queries. A new access pattern usually means a new table or index and a backfill.
Document model trade-offs
Use documents when the data is a self-contained aggregate that is loaded and saved as a whole (a product with its variants, a user profile with settings, a form submission). Avoid when entities are shared and heavily cross-referenced.
| Gain | Pay |
|---|---|
| Locality: one read returns the whole aggregate, no joins | Many-to-many relationships need references and application-side joins, or duplication |
| Flexible schema; fields vary per document | The schema still exists, in the code that reads it ("schema on read"); old shapes must be handled forever or migrated |
| Maps directly to objects in code | Updating a small part may rewrite a large document; documents have size limits (16 MB in MongoDB) |
| Atomic single-document updates | Multi-document transactions exist in several products but cost more and are not the path the store is optimised for |
- Embed what is owned by the parent, bounded in size, and read with it (order lines in an order).
- Reference what is shared, unbounded, or updated independently (the comments on a viral post, the customer on an order).
- Relational databases with JSON columns cover much of this ground; "relational core, JSON for the flexible edge" is a reasonable default.
Time-series modelling
Metrics, sensor readings, prices, events: append-only, arriving roughly in time order, read by time range, valuable when recent and bulky when old.
| Technique | What | Why |
|---|---|---|
| Bucketing | Partition by series and time bucket: key (sensor_id, day), sort by timestamp | Bounds partition size; a range query touches a known, small set of buckets; avoids one hot "now" partition across all series |
| Downsampling | Roll raw points up into 1-minute, 1-hour, 1-day aggregates (min, max, sum, count, percentile sketches) | Long-range queries read thousands of points instead of billions |
| Retention | Raw for days, minute rollups for months, hourly for years; expire by TTL or by dropping whole time partitions | Dropping a partition is nearly free; row-by-row deletes are not |
| Compression | Delta and delta-of-delta encoding for timestamps, XOR-style encoding for values, columnar layout | Neighbouring points are similar; order-of-magnitude size reductions are typical |
- Cardinality is the scaling limit: the number of distinct series (metric x every label combination). A label such as user id or request id multiplies it and can overwhelm a metrics store.
- Store sum and count, not averages, so rollups can be combined correctly. Percentiles cannot be averaged; keep a sketch or histogram.
- Products: Prometheus, InfluxDB, TimescaleDB, or Cassandra and ClickHouse with a bucketed schema.
Schema evolution
During a rolling deploy old and new code run together, and stored data and queued messages outlive the code that wrote them. So every change must be compatible in both directions.
- Backward compatible: new code can read data written by old code.
- Forward compatible: old code can read data written by new code (it must ignore what it does not know, and not destroy it when writing back).
| Change | Protobuf-style (numbered fields) | Avro-style (writer and reader schemas) |
|---|---|---|
| Add a field | Safe with a new field number; old readers skip unknown numbers | Safe if the new field has a default |
| Remove a field | Safe if it was optional; reserve the number and never reuse it | Safe if the removed field had a default |
| Rename a field | Safe on the wire (the number is the identity); breaks JSON mappings | Needs an alias; names are the identity |
| Change a type | Only a few compatible widenings; otherwise add a new field | Only defined promotions (for example int to long) |
| Add a required field | Breaking in both. Avoid "required"; validate in the application | |
| Add an enum value | Old readers see an unknown value; they need a defined fallback | |
- Schema registry: producers register schemas and the registry rejects incompatible changes before they reach a topic.
- Database migrations use the same idea, as expand and contract: add the new column (nullable), write to both, backfill, switch reads, stop writing the old one, drop it. Each step is deployable and reversible on its own.
- Text formats (JSON) have the same rules without the tooling: only add optional fields, never change meaning, tolerate unknown fields.
Money, ledgers, audit and soft delete
For money, the record of what happened is the source of truth and the balance is derived from it.
| Practice | Rule | Why |
|---|---|---|
| Money as integers | Store minor units (paise, cents) in a 64-bit integer with a currency code; or use a fixed-point decimal type. Never binary floating point | 0.1 + 0.2 is not 0.3 in floating point; errors accumulate. Minor-unit exponent varies by currency (0 for JPY, 2 for INR and USD, 3 for KWD) |
| Append-only ledger | Never update or delete an entry; correct a mistake with a reversing entry | Complete history, auditability, reconciliation; balance = sum of entries can always be re-derived |
| Double entry | Every movement debits one account and credits another; entries of a transfer sum to zero | Money cannot appear or vanish; an imbalance is a detectable bug |
| Audit trail | Record who changed what, when, and the before and after values, in an append-only table or stream (triggers, CDC, or application events) | Compliance and debugging; keep it out of reach of the code paths it audits |
| Soft delete | Set deleted_at instead of removing the row | Undo, references stay valid, history kept |
- Soft delete costs: every query must filter on
deleted_at IS NULL(use views or partial indexes); unique constraints must exclude deleted rows; tables grow. It does not satisfy a legal erasure request: personal data then needs real deletion or anonymisation. - Rounding happens once, at a defined point (for example when splitting a bill), with the remainder assigned explicitly so the parts still sum to the total.
Analytics and pipelines
Part 7 of 8 · moving data out of the transactional store
The primary database serves requests. Reports, dashboards, search, machine learning features and other services need the same data in other shapes. This part covers where that data goes and how it gets there.
- OLTP vs OLAP
- Warehouse, lake, lakehouse, and ETL vs ELT
- Batch vs stream, lambda vs kappa
- Stream processing concepts: time, windows, watermarks
- Exactly-once, stated carefully
- CDC and the outbox pattern
- Kafka: the log model
- Kafka: replication and acks
- Kafka: compaction and why it is fast
OLTP vs OLAP
| Aspect | OLTP (transaction processing) | OLAP (analytical processing) |
|---|---|---|
| Query shape | Read or write a few rows by key | Scan and aggregate millions to billions of rows, few columns |
| Users | End users through the application | Analysts, dashboards, batch jobs |
| Volume and latency | Thousands of queries per second, milliseconds each | Few queries, seconds to minutes each |
| Data | Current state | History of events over time |
| Storage | Row-oriented, indexed | Column-oriented, compressed, partitioned by time |
| Schema | Normalised | Star schema: a large fact table plus dimension tables; often wide and denormalised |
| Bottleneck | Disk seeks, lock contention | Scan throughput, memory for joins and aggregates |
| Products | PostgreSQL, MySQL, DynamoDB | BigQuery, Snowflake, Redshift, ClickHouse |
Failure mode: running analytics on the primary. One large scan evicts the hot pages from the cache, holds a snapshot open for minutes and degrades every user request. A read replica is the first step; a separate analytical store is the answer.
Warehouse, lake, lakehouse
| Aspect | Data warehouse | Data lake | Lakehouse |
|---|---|---|---|
| Stores | Structured, modelled tables | Any files: raw logs, JSON, Parquet, images | Open-format files (Parquet) plus a table layer |
| Schema | On write: enforced at load | On read: interpreted by the query | Enforced by the table format, with evolution |
| Storage and compute | Managed together or separated, by the vendor's engine | Cheap object storage; bring your own engine | Object storage; several engines over the same tables |
| Guarantees | ACID tables, fast SQL | None by itself; risk of an unusable "data swamp" | ACID commits, snapshots and time travel over files |
| Best for | BI and reporting | Raw retention, data science, ML training data | One copy serving both BI and ML |
| Examples | Snowflake, BigQuery, Redshift | Files on S3, GCS or HDFS | Delta Lake, Apache Iceberg, Apache Hudi |
ETL vs ELT
| Aspect | ETL: extract, transform, load | ELT: extract, load, transform |
|---|---|---|
| Where transformation runs | In a pipeline, before loading | Inside the warehouse or lake, with SQL, after loading raw data |
| Raw data kept | Often not | Yes: transformations can be re-run when logic changes |
| Fits | Sensitive data that must be masked before landing; constrained targets | Cheap storage and elastic compute; the common modern default |
Batch vs stream
Use batch unless the business needs the answer in seconds. Streaming buys freshness and pays in operational complexity.
| Aspect | Batch | Stream |
|---|---|---|
| Input | Bounded: yesterday's files | Unbounded: events as they arrive |
| Result latency | Minutes to hours | Milliseconds to seconds |
| Complexity | Lower: re-run the job to fix anything | Higher: state, ordering, late data, always-on operations |
| Fault handling | Retry the job or the failed task | Checkpoints and replay from the log |
| Uses | Reports, billing runs, model training, backfills | Fraud detection, alerting, live dashboards, keeping derived stores fresh |
| Tools | Spark, warehouse SQL, scheduled jobs | Flink, Kafka Streams, Spark Structured Streaming |
Lambda architecture
Kappa architecture
- Lambda: gain a simple, trusted batch result that corrects the stream; pay with two codebases that must compute the same thing.
- Kappa: gain one codebase; pay with long log retention (or a tiered archive) and a stream processor that can reprocess history fast enough.
- Many teams land in between: streaming for freshness plus a periodic batch reconciliation for correctness.
Stream processing concepts
- Event time: when the event happened, stamped at the source. Processing time: when the processor sees it. They differ by network delay, retries, and by hours when a phone was offline.
- Use event time for anything that must be correct and reproducible (billing, analytics). Processing time is simpler and acceptable for monitoring the pipeline itself.
| Window | Definition | An event belongs to | Example |
|---|---|---|---|
| Tumbling | Fixed size, no overlap: [10:00, 10:05), [10:05, 10:10) | Exactly one window | Requests per 5 minutes |
| Sliding (hopping) | Fixed size, advances by a smaller step: 5-minute window every 1 minute | Several windows | Moving average, rate limiting |
| Session | Grows while events keep arriving; closes after a gap of inactivity (for example 30 minutes) | One session per key; no fixed size | User visits |
- Watermark trade-off: an aggressive watermark gives fast results and more late events; a conservative one gives complete results later. It is a heuristic, so late data always needs a policy.
- Late data policies: drop and count it; allow a lateness period during which the window result is updated and re-emitted (downstream must accept corrections); or route it to a side output for batch repair.
- State: windows, joins and aggregations hold state per key. It lives in a local store, is checkpointed to durable storage, and must be bounded by a TTL.
Exactly-once, stated carefully
No system delivers a message over a network exactly once; messages are redelivered after failures. What stream processors offer is exactly-once effect on state: after a failure and replay, the results are the same as if each event had been processed once.
| Scope | How it is achieved | Holds when |
|---|---|---|
| Processor's internal state | Periodic consistent checkpoints of state together with input offsets; on failure, restore the checkpoint and replay from those offsets (Flink's approach) | The source is replayable |
| Kafka in, Kafka out | Idempotent producer (sequence numbers remove duplicate sends) plus transactions that commit the output records and the consumed offsets atomically | Downstream consumers read only committed records |
| External sink (database, API, email) | Not automatic. Either a transactional sink tied to the checkpoint (two-phase commit) or idempotent writes: upsert by a deterministic key, or a deduplication table of processed event ids | You build it |
Senior signal: say "at-least-once delivery plus idempotent processing gives effectively-once results" and then show where the idempotency key comes from. A side effect such as sending an email or charging a card cannot be rolled back by a checkpoint.
CDC and the outbox pattern
Both solve the dual-write problem: writing to the database and then to a broker (or cache, or index) as two separate steps means a crash between them leaves the two permanently different.
Change data capture
- A connector (Debezium is the common open-source one) reads the logical replication log and emits one event per row change.
- Gain: no application changes, nothing missed, ordered per row. Pay: events expose table structure (a schema change is a contract change), delivery is at-least-once, and a stalled connector makes the database retain log files until the disk fills.
Transactional outbox
- Gain: the event is a deliberate, versioned contract rather than a table image, and it cannot be lost or published for a rolled-back change.
- Pay: an extra table and a relay (a poller, or CDC on the outbox table); delivery is at-least-once, so consumers must be idempotent.
Idempotent consumers, ordering and the inbox side are covered in Distributed Systems Patterns.
Kafka: the log model
Kafka is a distributed, replicated, append-only log. Consumers do not remove messages; they track a position and can re-read.
| Term | Meaning | Consequence |
|---|---|---|
| Topic | A named stream of records | Split into partitions |
| Partition | One ordered, append-only log on disk | Ordering is guaranteed within a partition only |
| Key | Chooses the partition (hash of key) | Same key, same partition, in order. Changing the partition count changes the mapping for new records |
| Offset | Position of a record in its partition | A consumer's progress is one number per partition; rewind it to replay |
| Consumer group | Consumers sharing a group id divide the partitions among themselves | Max useful consumers in a group = partition count. Different groups each get every record (pub/sub) |
| Rebalance | Partitions reassigned when a consumer joins or leaves | Processing pauses briefly; uncommitted work is redone by the new owner |
| Retention | Records kept by time or size, regardless of consumption | Replay and new consumers are possible until retention expires |
- Offset commit order decides the guarantee: process then commit gives at-least-once (duplicates after a crash); commit then process gives at-most-once (loss after a crash).
- Consumer lag (latest offset minus committed offset) is the key health metric.
Kafka: replication and acks
Each partition has one leader and follower replicas on other brokers. The in-sync replicas (ISR) are the replicas that are caught up with the leader. A record is committed once every in-sync replica has it, and consumers only see committed records.
| Producer acks | Leader replies when | Can lose data when | Latency |
|---|---|---|---|
acks=0 | It does not; the producer does not wait | Any broker or network failure | Lowest |
acks=1 | The leader has written the record | The leader fails before followers copy it | Low |
acks=all | All current in-sync replicas have it | All in-sync replicas fail together; or the ISR has shrunk to the leader alone and min.insync.replicas is 1 | Highest: waits for the slowest in-sync follower |
- Common durable setting: replication factor 3,
min.insync.replicas=2,acks=all. Tolerates one broker down with no loss and no unavailability; with two down, writes are rejected rather than accepted unsafely. - Unclean leader election (letting an out-of-sync replica become leader) trades committed data for availability; keep it off for data you cannot lose.
- Idempotent producer removes duplicates caused by producer retries and preserves order within a partition.
Trade-off: durability vs latency vs availability, per topic. Clickstream can take acks=1; payments events cannot.
Kafka: compaction and why it is fast
Log compaction is an alternative retention policy: instead of deleting by age, keep at least the latest record for each key. A record with a null value (a tombstone) deletes the key. A compacted topic is therefore a durable, replayable table of "current value per key", used for changelogs, CDC snapshots and state restoration.
| Reason it is fast | What it means |
|---|---|
| Sequential I/O | Appends to the end of a file and reads in order. Sequential disk throughput is hundreds of MB/s even on spinning disks; random access is orders of magnitude slower |
| OS page cache | The broker relies on the kernel's file cache rather than its own; recent data is served from memory |
| Batching | Producers group records into batches, brokers store and replicate batches, consumers fetch batches: fewer network round trips and system calls. Batches are compressed as a unit |
| Zero-copy | Bytes go from the page cache to the network socket inside the kernel (sendfile), without being copied through the broker process. Not applicable to connections encrypted with TLS |
| Simple broker | No per-message acknowledgement state or per-consumer queues; a consumer is an offset |
| Partitioning | Scale out by adding partitions and brokers |
- Order-of-magnitude capacity: a well-provisioned cluster handles hundreds of thousands to millions of small messages per second; measure for your message size and acks setting.
- What you pay for the log model: no per-message routing or priority, one slow or failing message blocks its partition (use a retry or dead-letter topic), and more partitions mean more open files, longer recovery and slower rebalances.
Search and specialised stores
Part 8 of 8 · derived stores built for one kind of query
These stores answer questions the primary database answers badly. They are fed from the source of truth and can be rebuilt from it.
- Inverted index and relevance
- Search clusters: shards, replicas, and why not your source of truth
- Vector search and graph databases
- Caches as data systems
Inverted index and relevance
An inverted index maps each term to the sorted list of documents that contain it (a postings list). A query looks up its terms and intersects or unions the lists.
- Analyser = character filters (strip HTML), a tokenizer (split into words), token filters (lowercase, stop words, stemming, synonyms). It decides what can match; a wrong analyser is the usual cause of "search does not find it".
- Text fields are analysed; keyword fields are indexed as exact values for filters, sorting and aggregations.
- Index files (segments) are immutable; an update is a delete plus a new document, and background merges reclaim space, much like LSM compaction.
Relevance scoring: results are ranked, not just matched. The standard baseline, BM25, scores a document higher when a query term appears more often in it (with diminishing returns), when the term is rare across the whole collection, and when the document is short relative to the average. Production ranking then adds field boosts (title over body), business signals such as popularity, recency or distance, and often a second-stage learned re-ranker over the top few hundred results.
Search clusters
Elasticsearch-style layout: an index is split into primary shards (each one a Lucene index), and each primary has replica shards on other nodes. A search is scatter-gather: the coordinating node queries one copy of every shard, merges the top results and fetches the documents.
- Shard count is chosen when the index is created; changing it means a split or a reindex. A common sizing guideline is tens of GB per shard; too many small shards waste memory and slow the cluster.
- Routing: a document goes to
hash(routing key) mod primary shards; a custom routing key (tenant id) keeps a tenant's query on one shard. - Near real time: a new document becomes searchable after the next refresh (about one second by default), not immediately.
- Deep pagination is expensive for the same reason as offset: every shard must return offset + limit hits. Use a search-after cursor.
Why it is not your source of truth: writes are searchable only after a refresh; there are no multi-document transactions or foreign-key style constraints; changing how a field is analysed requires reindexing everything; and the system is tuned for search throughput rather than for transactional guarantees. Keep the authoritative copy in the primary database, feed the index asynchronously (CDC or outbox), and keep the ability to rebuild it from scratch.
Failure mode: dual writes from the application to the database and the index drift apart over time. Feed the index from the database's change stream and run a periodic reconciliation.
Vector search and graph databases
Vector search
A model turns text, images or other items into embeddings (vectors of a few hundred to a few thousand numbers) such that similar items lie close together, and a query becomes "find the nearest vectors to this one". Exact nearest-neighbour search is a full scan, so vector indexes use approximate methods (graph-based such as HNSW, or cluster-based such as IVF) that trade a small, tunable loss of recall for large gains in speed and memory. Result quality depends on the embedding model at least as much as on the index, and most real systems combine vector similarity with keyword matching and metadata filters (hybrid search) rather than relying on vectors alone.
Graph databases
Use a graph database when the relationships are the query: variable-depth traversals and path finding such as friends of friends, fraud rings sharing devices and cards, permission inheritance, or dependency impact.
| Question | Relational | Graph |
|---|---|---|
| Fixed, shallow joins (order with its items) | Natural and fast | No advantage |
| Traversal of unknown depth, shortest path | Recursive queries; cost grows with each hop's join | Each hop follows stored adjacency; cost follows the part of the graph visited |
| Aggregates over all rows | Strong | Weak |
| Horizontal scaling | Well understood | Hard: any partitioning cuts edges, and "supernodes" with millions of edges are hot spots |
Examples: Neo4j, Amazon Neptune, JanusGraph. Many "social graph" features at scale are served from adjacency lists in a key-value or relational store plus caches, because the common query is only one or two hops.
Caches as data systems
A cache is a derived store too, with the same questions: who writes it, how stale may it be, and how is it rebuilt. Everything on this page about replication, partitioning and hot keys applies to a Redis cluster as much as to a database.
- Treat cached data as disposable; the design must be correct, only slower, with an empty cache.
- The same change stream that feeds search can invalidate or refresh cache entries.
Cache-aside, write-through, eviction, stampedes and invalidation are covered in Building Blocks.
Cheat sheet
Workload to store
| Workload | Store | Why | Watch out for |
|---|---|---|---|
| Transactions, relations, varied queries (orders, payments, accounts) | Relational: PostgreSQL, MySQL | ACID, joins, constraints, mature tooling | Single-leader write ceiling; sharding is manual; default isolation is not serializable |
| Relational at global scale with strong consistency | Distributed SQL: Spanner, CockroachDB | Horizontal scale with transactions | Higher write latency (consensus per write); cost; key design still matters |
| Huge key-based read/write volume, known access patterns | Key-value / wide-column: DynamoDB, Cassandra | Predictable latency at any size, high write throughput, multi-region | No joins or ad hoc queries; hot partitions; eventual consistency by default |
| Self-contained aggregates with a flexible shape | Document: MongoDB | One read per aggregate, schema flexibility | Many-to-many relations; unbounded arrays; schema lives in code |
| Hot data, counters, sessions, rate limits, leaderboards | In-memory: Redis | Sub-millisecond, rich data structures | Memory cost; persistence and failover can lose recent writes |
| Full-text and faceted search | Search engine: Elasticsearch, OpenSearch | Inverted index, relevance ranking, aggregations | Near real time; not a source of truth; reindex on mapping change |
| Reports and aggregates over history | Columnar warehouse: BigQuery, Snowflake, ClickHouse | Column scans, compression, elastic compute | Not for point lookups or frequent single-row updates; data arrives with delay |
| Metrics and sensor data | Time-series: Prometheus, InfluxDB, TimescaleDB | Time-bucketed storage, compression, rollups, retention | Series cardinality |
| Event transport, replay, decoupling | Log: Kafka | Durable ordered log, many independent consumers | Ordering per partition only; at-least-once by default; not a query store |
| Files, images, video, backups | Object storage: S3-style | Cheap, durable, effectively unlimited | No partial updates or queries; keep metadata in a database |
| Deep relationship traversals | Graph: Neo4j, Neptune | Hops follow stored adjacency | Hard to shard; supernodes |
| Similarity over embeddings | Vector index (dedicated, or an extension of an existing store) | Approximate nearest-neighbour search | Recall is approximate; filtering and freshness; re-embedding on model change |
Isolation levels, quick view
| Level | Still possible (general model) | Typical mechanism | Remember |
|---|---|---|---|
| Read uncommitted | Everything, including dirty reads | No read protection | Rarely useful; some engines silently give read committed |
| Read committed | Non-repeatable read, phantom, lost update, write skew | Snapshot per statement, or short read locks | The default in PostgreSQL, Oracle and SQL Server |
| Repeatable read | Phantom per the standard; lost update and write skew depend on the engine | Long read locks, or a per-transaction snapshot | The name means different things: snapshot isolation in PostgreSQL; snapshot reads plus gap locks in MySQL InnoDB (its default) |
| Snapshot isolation | Write skew | MVCC snapshot per transaction, first committer wins on write conflicts | Called "serializable" in Oracle and "repeatable read" in PostgreSQL |
| Serializable | None | Two-phase locking, serializable snapshot isolation, or serial execution | Expect blocking or aborts; the application must retry |
One-line rules
- B-tree for reads and transactions; LSM for write volume; columns for analytics.
- Index: equality columns, then range or sort column; every index is paid for on write.
- Keyset pagination for large lists; batch to remove N+1.
- Name the anomaly, then the mechanism: atomic conditional update, row lock, constraint, or serializable.
- Replicas lag: decide which reads may be stale. W + R > N overlaps, it does not linearize.
- Last-write-wins loses data; say so when you choose it.
- Choose the partition key from the access pattern and its load distribution; keep transactions inside one partition.
- Money: integer minor units, append-only double-entry ledger, idempotency key on every movement.
- One source of truth; search, cache and warehouse are derived from its change log and rebuildable.
- Streams: at-least-once delivery plus idempotent consumers; event time with watermarks; order only within a partition.
Next: how several nodes agree, order events and survive partial failure, in Distributed Systems Patterns.