Learnings

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

Storage engines

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.

The commit waits only for the log flush. Data files catch up in the background and are rebuilt from the log after a crash.
  • 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

Storage engines

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.

A lookup walks root to leaf, three page reads here. Each leaf also points to its right-hand neighbour, so a range scan continues along the leaves without going back up.
  • 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

Storage engines

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.

The write path is two sequential operations: a log append and a memory insert. All disk writes are sequential.

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.

The Bloom filter is checked in memory per SSTable; only a "maybe" costs 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

Storage engines

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.

AspectB-treeLSM-tree
Write pathWAL, then overwrite a page in place (random I/O)WAL plus memtable; sequential flush and merge
Write amplificationWhole page rewritten per change, plus WALEach record rewritten several times by compaction; roughly 10x or more with levelled compaction, less with size-tiered (workload dependent)
Read pathOne root-to-leaf walk; each key lives in one placeMemtable plus several SSTables; Bloom filters and block cache hide most of it
Range scansFollow linked leavesMerge across levels
SpaceFragmentation, partly filled pagesCompresses well; temporary overhead during compaction, stale versions until merged
Latency profileSteadierHigher write throughput, compaction can hurt tail latency
TransactionsNatural fit for row locks on a single copy of each keyPossible, but built on top (snapshots, sequence numbers)
Typical productsPostgreSQL, MySQL InnoDB, SQL Server, OracleRocksDB, 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

Storage engines

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".

Same table, two layouts. The point read touches one contiguous row; the aggregate touches one contiguous column and never reads names or countries.
  • 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

Storage engines

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?".

OptionHowData lost on crashCost
NonePure cache (Memcached)Everything; cold cache on restartNothing
SnapshotPeriodic 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 logLog every write command (Redis AOF); fsync always, every second, or left to the OSAbout one second with the per-second setting; none of the acknowledged writes with fsync alwaysLarger file, needs rewriting, slower restart; fsync always costs throughput
BothSnapshot plus log tailAs the log settingBoth costs; common production choice
ReplicationReplica in another zoneThe async replication windowMore 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

Indexes and queries

  • 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).
In a clustered table a secondary lookup is two tree walks (index, then primary key). In a heap table every index points straight at the row.
  • 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

Indexes and queries

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 = 7Yes, prefix
WHERE user_id = 7 AND status = 'PAID' ORDER BY created_at DESCYes, 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

Indexes and queries

  • 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 status with 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 only status = '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

Indexes and queries

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 forWhat it tells you
Access methodSequential (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 rowsA large mismatch (10x or more) means stale statistics or correlated columns; the planner then picks the wrong join method.
Join methodNested 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 filterMany rows read and then discarded means the index is not selective enough for this predicate.
Sort or hash spilling to diskThe operation did not fit in working memory; add an index that provides the order, or reduce the row set earlier.
LoopsAn inner node executed thousands of times is the N+1 pattern inside one query.

Index types

Indexes and queries

TypeStructureGood forCannot doSeen in
B-treeSorted balanced treeEquality, ranges, prefix match, ORDER BYFull-text, suffix match, multi-dimensional proximityDefault in relational databases
HashHash table from key to locationExact-match lookups, O(1) on averageRanges, ordering, prefixKey-value stores, hash indexes, hash joins
InvertedTerm to sorted list of document idsFull-text search, "contains" on arrays and JSONCheap updates; ordering by arbitrary columnsLucene, Elasticsearch, PostgreSQL GIN
GeospatialR-tree, or a space-filling curve (geohash, S2, H3 cells) stored in a B-tree"Within radius", bounding box, nearest neighboursAnything non-spatialPostGIS (GiST), MongoDB 2dsphere, Redis GEO
BitmapOne bitmap per distinct valueCombining low-cardinality filters in analyticsHigh write ratesColumn 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

Indexes and queries

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

Indexes and queries

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.

AspectOffsetKeyset / cursor
Cost of page kGrows with the offset: reads offset + limit rowsConstant: one index seek plus limit rows
Concurrent insertsRows shift; items are skipped or shown twiceStable relative to the cursor
Jump to arbitrary pageYesNo, only next and previous
RequirementsNoneA 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

Transactions

LetterPrecise meaningMechanismCommon misreading
AtomicityAll of the transaction's writes take effect, or none do, even on a crashUndo information, WAL, rollbackIt is about abort, not about concurrency
ConsistencyEach transaction moves the data from one state that satisfies the declared invariants to anotherConstraints, plus correct application logicNot the C in CAP (which means linearizability). Largely the application's job
IsolationConcurrent transactions behave as if they ran in some serial order, to the degree the chosen level providesLocks, MVCC, conflict detectionThe default level is usually weaker than serializable
DurabilityOnce commit is acknowledged, the data survives a crash of this nodeWAL flush, replicationIt 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

Transactions

The anomalies first, then which level admits which.

AnomalyWhat happens
Dirty readYou read another transaction's uncommitted write, which may later roll back
Non-repeatable readYou read the same row twice in one transaction and get different committed values
PhantomYou run the same predicate query twice and the set of matching rows changes (rows inserted or deleted by others)
Lost updateTwo transactions read a value, both compute a new one, and the second write silently overwrites the first
Write skewTwo transactions read overlapping data, each writes a different row, and together they break an invariant neither breaks alone
Level (general model)Dirty readNon-repeatable readPhantomLost updateWrite skew
Read uncommittedPossiblePossiblePossiblePossiblePossible
Read committedPreventedPossiblePossiblePossiblePossible
Repeatable read (SQL standard)PreventedPreventedPossible per the standardImplementation dependentImplementation dependent
Snapshot isolationPreventedPreventedNot seen by snapshot readsPrevented where the engine detects write-write conflicts (first committer wins)Possible
SerializablePreventedPreventedPreventedPreventedPrevented

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):

ProductDefaultWorth knowing
PostgreSQLRead committedIts "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 InnoDBRepeatable readPlain 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.
OracleRead committedIts "serializable" is snapshot isolation, so write skew is possible.
SQL ServerRead committedOffers 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

Transactions

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.

Two transactions read the same row at the same moment and each sees the version valid for its own snapshot.
  • 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

Transactions

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.

Both transactions commit successfully and the money is wrong; read committed allows this.
FixHowNote
Atomic updateUPDATE ... SET balance = balance - 500Best when the new value can be computed in SQL; see a safe balance debit
Explicit lockSELECT ... FOR UPDATE, then writeNeeded when logic must run in the application between read and write
Compare-and-setUPDATE ... WHERE version = :seen; retry if 0 rowsOptimistic; works across a user's think time
Automatic detectionSnapshot isolation that aborts the second writerEngine specific; the application must retry

Write skew

Transactions

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.

The two transactions write different rows, so there is no write-write conflict for snapshot isolation to detect, and no existing row to lock.

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.

FixHowTrade-off
ConstraintUnique index on (room_id, slot), or an exclusion constraint on overlapping time ranges where the engine supports oneCheapest and safest; needs the invariant to be expressible as a constraint
Lock a parent rowSELECT ... FROM rooms WHERE id = 12 FOR UPDATE before checking (materialising the conflict)Serialises bookings per room; simple and portable
True serializableRun at a serializable level and retry on abortGeneral; costs aborts or blocking under contention
Single writerRoute all bookings for a room through one queue partition or actorNo 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

Transactions

AspectPessimistic (SELECT FOR UPDATE)Optimistic (version column / compare-and-set)
AssumptionConflicts are likelyConflicts are rare
On conflictThe second transaction waitsThe second write fails and must retry
Wins whenHigh contention on the same rows (flash sale stock, a hot counter); retry storms would waste more work than waitingLow contention; long gaps between read and write (a user editing a form); no open transaction across a network call
RisksDeadlocks, lock waits, connections held while blockedStarvation and wasted work under contention
Beyond one databaseDoes not extend to HTTP APIs or stores without transactionsMaps 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

Transactions

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.

A cycle in the waits-for graph. The database detects it and aborts one transaction as the victim.
  • 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

Transactions

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 in depth

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.

Where a write may land: one node, one node per region, or any replica of the key.
AspectSingle-leaderMulti-leaderLeaderless
Write pathAll writes to one leader, which streams changes to followersEach leader accepts writes and replicates to the others asynchronouslyClient or coordinator sends each write to all N replicas and waits for W acks
Conflict handlingNone: the leader orders all writesRequired: concurrent writes to the same item on different leadersRequired: concurrent writes and missed writes; resolved on read or in the background
FailoverDetect failure, promote a follower, repoint clients. Risks: lost unreplicated writes, split brainOther leaders keep accepting writes; no promotion neededNo failover: other replicas keep serving while quorum holds
Consistency you getStrong on the leader; followers lag unless replication is synchronousEventual; conflicts possibleEventual, tunable per request with R and W
Use whenMost OLTP systemsActive-active regions, offline-first and collaborative appsHigh write availability, simple key-based access
ExamplesPostgreSQL, MySQL, MongoDB replica setsMulti-region active-active setups, CouchDB-style syncDynamo-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

Replication in depth

TypeWhat is shippedStrengthWeakness
Statement-basedThe SQL textCompactNon-deterministic statements (NOW(), RAND(), auto-increment under concurrency, triggers) can make replicas diverge
WAL shipping (physical)The engine's byte-level log recordsExact copy, low overhead, simpleTied 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 valuesDecoupled from storage format: cross-version upgrades, selective replication, and the feed for change data captureMore 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

Replication in depth

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.

The read-your-writes violation: the write succeeded but the next read hit a replica that had not caught up.
GuaranteeAnomaly without itFixes
Read-your-writesYou do not see your own updateRead 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 readsTime goes backwards: a refresh shows older data because it hit a more-lagged replicaRoute each user to the same replica (hash of user id); or track the last-seen position and refuse older replicas
Consistent prefixEffects appear before causes: a reply is visible before the questionKeep 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

Replication in depth

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 = 3, W = 2, R = 2. The reader's two replicas include node 2, so it sees v2, returns it, and can repair node 3.
N, W, RBehaviour
3, 2, 2The usual balance: tolerates one replica down for both reads and writes
3, 3, 1Fast reads; any replica down blocks writes
3, 1, 3Fast writes; any replica down blocks consistent reads
3, 1, 1Fastest 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

Replication in depth

MechanismWhat it doesCatch
Sloppy quorumIf some of a key's home replicas are unreachable, accept the write on other healthy nodes so W can still be metHigher write availability, but the overlap guarantee is gone until the data is handed back
Hinted handoffThe stand-in node stores the write with a hint naming the intended replica and forwards it when that replica returnsHints are kept for a limited time; a long outage needs full repair
Read repairA read that sees differing versions writes the newest back to stale replicasOnly fixes keys that are read
Anti-entropyA background process compares replicas (commonly with Merkle trees, so only differing ranges are exchanged) and copies missing dataCosts 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

Replication in depth

Multi-leader and leaderless systems accept concurrent writes to the same key. Something must decide the outcome.

ApproachHowWhat you pay
Last-write-wins (LWW)Attach a timestamp to each write; the highest wins, the rest are discardedSilent 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 vectorsKeep a counter per replica with each value; comparing vectors shows whether one version descends from the other or they are concurrentDetects conflicts without losing data, but then hands the concurrent versions ("siblings") to the application to merge
Application mergeDomain logic: union the two carts, keep both edits, ask the userCode per data type; deletes need tombstones or removed items come back
CRDTsData types whose merge is built in and always convergesSee below
Avoid the conflictRoute all writes for a given record to one leader or regionLoses 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

Partitioning in depth

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.

StrategyHowGainPaySeen in
Fixed number of partitionsCreate 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 partitionSimple; only whole partitions moveThe count is hard to change later: too few limits growth, too many adds overheadRedis Cluster (16384 slots), Elasticsearch shards, Riak, Couchbase
Dynamic splittingA partition that grows past a size threshold splits in two; small ones can mergePartition count follows data volume; works for range partitioningA new empty table starts as one partition (a hotspot) unless pre-splitHBase, MongoDB chunks, range-partitioned SQL systems
Proportional to nodesA fixed number of partitions (virtual nodes) per node; a new node picks ranges to split and takes half of eachPartition size stays stable as the cluster growsRandom splits can be uneven; needs hash partitioningCassandra 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

Partitioning in depth

Something must know which node owns a key right now, and learn quickly when that changes. Three places to put that knowledge:

The partition map lives in the nodes themselves (1), in a router (2) or in the client (3); a coordination service or gossip keeps it current.
ApproachGainPaySeen in
Any node forwards or redirectsSimple clients, no extra tierPossible extra hop; nodes must share the map (gossip)Cassandra (coordinator node), Redis Cluster (MOVED redirect)
Routing tierThin clients; routing logic changes in one placeExtra hop and a tier to scale and keep availableMongoDB mongos, proxy-based sharding layers
Partition-aware clientNo extra hopSmarter client library in every language; stale maps must be refreshedKafka 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

Partitioning in depth

Data is partitioned by primary key. A query on another attribute ("all red cars") does not know which partition to ask.

Local indexes make the read fan out to every partition; a global index makes each write fan out to the index instead.
AspectLocal (document-partitioned)Global (term-partitioned)
WriteOne partition: data and index together, atomicallyData partition plus one or more index partitions; usually updated asynchronously
Read by indexed attributeScatter-gather across all partitions; latency follows the slowest partitionOne index partition, then fetch the rows
ConsistencyIndex always matches the data in its partitionOften eventually consistent with the base data
Seen inMongoDB, Cassandra, ElasticsearchDynamoDB 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

Partitioning in depth

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).

CauseFixCost
One key read very oftenCache it (in process and in a shared cache); add replicas for that partitionStaleness
One key written very oftenSalt the key: append a suffix 0 to k-1 so writes spread over k partitionsReads 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 countsSlightly stale or approximate value
Monotonic key with range partitioning (timestamp, auto-increment)Lead the key with something else (tenant, device, hash prefix), keep time secondGlobal time-range scans now fan out
One huge tenantGive it a dedicated partition or cluster; route by a tenant directorySpecial-case operations
Partition too large (unbounded rows under one key)Add a time bucket to the partition keyQueries 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

Partitioning in depth

  • 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

Data modelling

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.

AspectNormalisedDenormalised
IdeaEach fact stored once; reference by idCopy or precompute data where it is read
WritesOne place to update; cheap; no update anomaliesEvery copy must be updated: fan-out, possible inconsistency
ReadsJoins at read timeOne lookup; predictable latency
StorageSmallerLarger
FlexibilityNew queries are easyShaped for known queries; new ones may need a backfill
FitsOLTP with varied queries, strong integrity needsRead-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

Data modelling

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 patternKey design
Latest 50 messages in a conversation; older pages on scrollTable messages: partition key conversation_id, sort key message_id (time-sortable), read descending with a limit
A user's conversations, most recent firstTable user_conversations: partition key user_id, sort key last_activity_at; rewritten on each new message
Fetch one message by idSame messages table when the caller knows the conversation; otherwise a lookup table or index
One partition holds one conversation, already sorted. The query is a single-node sequential read; other conversations are never touched.
  • 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#7 with SK = PROFILE and SK = 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

Data modelling

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.

GainPay
Locality: one read returns the whole aggregate, no joinsMany-to-many relationships need references and application-side joins, or duplication
Flexible schema; fields vary per documentThe 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 codeUpdating a small part may rewrite a large document; documents have size limits (16 MB in MongoDB)
Atomic single-document updatesMulti-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

Data modelling

Metrics, sensor readings, prices, events: append-only, arriving roughly in time order, read by time range, valuable when recent and bulky when old.

TechniqueWhatWhy
BucketingPartition by series and time bucket: key (sensor_id, day), sort by timestampBounds partition size; a range query touches a known, small set of buckets; avoids one hot "now" partition across all series
DownsamplingRoll 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
RetentionRaw for days, minute rollups for months, hourly for years; expire by TTL or by dropping whole time partitionsDropping a partition is nearly free; row-by-row deletes are not
CompressionDelta and delta-of-delta encoding for timestamps, XOR-style encoding for values, columnar layoutNeighbouring 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

Data modelling

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).
ChangeProtobuf-style (numbered fields)Avro-style (writer and reader schemas)
Add a fieldSafe with a new field number; old readers skip unknown numbersSafe if the new field has a default
Remove a fieldSafe if it was optional; reserve the number and never reuse itSafe if the removed field had a default
Rename a fieldSafe on the wire (the number is the identity); breaks JSON mappingsNeeds an alias; names are the identity
Change a typeOnly a few compatible widenings; otherwise add a new fieldOnly defined promotions (for example int to long)
Add a required fieldBreaking in both. Avoid "required"; validate in the application
Add an enum valueOld 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

Data modelling

For money, the record of what happened is the source of truth and the balance is derived from it.

Entries are only ever inserted. A transfer posts at least two entries that sum to zero; the account balance is a cached total of its entries.
PracticeRuleWhy
Money as integersStore minor units (paise, cents) in a 64-bit integer with a currency code; or use a fixed-point decimal type. Never binary floating point0.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 ledgerNever update or delete an entry; correct a mistake with a reversing entryComplete history, auditability, reconciliation; balance = sum of entries can always be re-derived
Double entryEvery movement debits one account and credits another; entries of a transfer sum to zeroMoney cannot appear or vanish; an imbalance is a detectable bug
Audit trailRecord 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 deleteSet deleted_at instead of removing the rowUndo, 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

Analytics and pipelines

AspectOLTP (transaction processing)OLAP (analytical processing)
Query shapeRead or write a few rows by keyScan and aggregate millions to billions of rows, few columns
UsersEnd users through the applicationAnalysts, dashboards, batch jobs
Volume and latencyThousands of queries per second, milliseconds eachFew queries, seconds to minutes each
DataCurrent stateHistory of events over time
StorageRow-oriented, indexedColumn-oriented, compressed, partitioned by time
SchemaNormalisedStar schema: a large fact table plus dimension tables; often wide and denormalised
BottleneckDisk seeks, lock contentionScan throughput, memory for joins and aggregates
ProductsPostgreSQL, MySQL, DynamoDBBigQuery, 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

Analytics and pipelines

AspectData warehouseData lakeLakehouse
StoresStructured, modelled tablesAny files: raw logs, JSON, Parquet, imagesOpen-format files (Parquet) plus a table layer
SchemaOn write: enforced at loadOn read: interpreted by the queryEnforced by the table format, with evolution
Storage and computeManaged together or separated, by the vendor's engineCheap object storage; bring your own engineObject storage; several engines over the same tables
GuaranteesACID tables, fast SQLNone by itself; risk of an unusable "data swamp"ACID commits, snapshots and time travel over files
Best forBI and reportingRaw retention, data science, ML training dataOne copy serving both BI and ML
ExamplesSnowflake, BigQuery, RedshiftFiles on S3, GCS or HDFSDelta Lake, Apache Iceberg, Apache Hudi

ETL vs ELT

AspectETL: extract, transform, loadELT: extract, load, transform
Where transformation runsIn a pipeline, before loadingInside the warehouse or lake, with SQL, after loading raw data
Raw data keptOften notYes: transformations can be re-run when logic changes
FitsSensitive data that must be masked before landing; constrained targetsCheap storage and elastic compute; the common modern default

Batch vs stream

Analytics and pipelines

Use batch unless the business needs the answer in seconds. Streaming buys freshness and pays in operational complexity.

AspectBatchStream
InputBounded: yesterday's filesUnbounded: events as they arrive
Result latencyMinutes to hoursMilliseconds to seconds
ComplexityLower: re-run the job to fix anythingHigher: state, ordering, late data, always-on operations
Fault handlingRetry the job or the failed taskCheckpoints and replay from the log
UsesReports, billing runs, model training, backfillsFraud detection, alerting, live dashboards, keeping derived stores fresh
ToolsSpark, warehouse SQL, scheduled jobsFlink, Kafka Streams, Spark Structured Streaming

Lambda architecture

Two pipelines over the same events: batch is complete and slow, speed is fresh and approximate; the query layer merges them.

Kappa architecture

One streaming pipeline. To change the logic, run a new version over the retained log from the start and switch readers when it catches up.
  • 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

Analytics and pipelines

  • 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.
WindowDefinitionAn event belongs toExample
TumblingFixed size, no overlap: [10:00, 10:05), [10:05, 10:10)Exactly one windowRequests per 5 minutes
Sliding (hopping)Fixed size, advances by a smaller step: 5-minute window every 1 minuteSeveral windowsMoving average, rate limiting
SessionGrows while events keep arriving; closes after a gap of inactivity (for example 30 minutes)One session per key; no fixed sizeUser visits
A watermark is the processor's estimate that no more events older than that time will arrive; it is what lets an event-time window close.
  • 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

Analytics and pipelines

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.

ScopeHow it is achievedHolds when
Processor's internal statePeriodic 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 outIdempotent producer (sequence numbers remove duplicate sends) plus transactions that commit the output records and the consumed offsets atomicallyDownstream 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 idsYou 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

Analytics and pipelines

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

The application writes once. Everything downstream is derived from the database's own log, in commit order.
  • 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

The business row and the event row commit together or not at all; a relay then publishes outbox rows to the broker.
  • 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

Analytics and pipelines

Kafka is a distributed, replicated, append-only log. Consumers do not remove messages; they track a position and can re-read.

Within a group each partition is read by exactly one consumer, so partitions are the unit of both ordering and parallelism.
TermMeaningConsequence
TopicA named stream of recordsSplit into partitions
PartitionOne ordered, append-only log on diskOrdering is guaranteed within a partition only
KeyChooses the partition (hash of key)Same key, same partition, in order. Changing the partition count changes the mapping for new records
OffsetPosition of a record in its partitionA consumer's progress is one number per partition; rewind it to replay
Consumer groupConsumers sharing a group id divide the partitions among themselvesMax useful consumers in a group = partition count. Different groups each get every record (pub/sub)
RebalancePartitions reassigned when a consumer joins or leavesProcessing pauses briefly; uncommitted work is redone by the new owner
RetentionRecords kept by time or size, regardless of consumptionReplay 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

Analytics and pipelines

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.

With acks=all the producer's acknowledgement waits for the in-sync followers, which pull from the leader.
Producer acksLeader replies whenCan lose data whenLatency
acks=0It does not; the producer does not waitAny broker or network failureLowest
acks=1The leader has written the recordThe leader fails before followers copy itLow
acks=allAll current in-sync replicas have itAll in-sync replicas fail together; or the ISR has shrunk to the leader alone and min.insync.replicas is 1Highest: 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

Analytics and pipelines

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 fastWhat it means
Sequential I/OAppends 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 cacheThe broker relies on the kernel's file cache rather than its own; recent data is served from memory
BatchingProducers 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-copyBytes 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 brokerNo per-message acknowledgement state or per-consumer queues; a consumer is an offset
PartitioningScale 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 and specialised stores

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.

"Cars" and "car" meet at the same term because the same analyser runs at index time and at query time.
  • 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

Search and specialised stores

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.

A primary and its replica never share a node. A query needs one copy of each shard; replicas add read capacity and survive a node loss.
  • 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

Search and specialised stores

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.

QuestionRelationalGraph
Fixed, shallow joins (order with its items)Natural and fastNo advantage
Traversal of unknown depth, shortest pathRecursive queries; cost grows with each hop's joinEach hop follows stored adjacency; cost follows the part of the graph visited
Aggregates over all rowsStrongWeak
Horizontal scalingWell understoodHard: 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

Search and specialised stores

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

WorkloadStoreWhyWatch out for
Transactions, relations, varied queries (orders, payments, accounts)Relational: PostgreSQL, MySQLACID, joins, constraints, mature toolingSingle-leader write ceiling; sharding is manual; default isolation is not serializable
Relational at global scale with strong consistencyDistributed SQL: Spanner, CockroachDBHorizontal scale with transactionsHigher write latency (consensus per write); cost; key design still matters
Huge key-based read/write volume, known access patternsKey-value / wide-column: DynamoDB, CassandraPredictable latency at any size, high write throughput, multi-regionNo joins or ad hoc queries; hot partitions; eventual consistency by default
Self-contained aggregates with a flexible shapeDocument: MongoDBOne read per aggregate, schema flexibilityMany-to-many relations; unbounded arrays; schema lives in code
Hot data, counters, sessions, rate limits, leaderboardsIn-memory: RedisSub-millisecond, rich data structuresMemory cost; persistence and failover can lose recent writes
Full-text and faceted searchSearch engine: Elasticsearch, OpenSearchInverted index, relevance ranking, aggregationsNear real time; not a source of truth; reindex on mapping change
Reports and aggregates over historyColumnar warehouse: BigQuery, Snowflake, ClickHouseColumn scans, compression, elastic computeNot for point lookups or frequent single-row updates; data arrives with delay
Metrics and sensor dataTime-series: Prometheus, InfluxDB, TimescaleDBTime-bucketed storage, compression, rollups, retentionSeries cardinality
Event transport, replay, decouplingLog: KafkaDurable ordered log, many independent consumersOrdering per partition only; at-least-once by default; not a query store
Files, images, video, backupsObject storage: S3-styleCheap, durable, effectively unlimitedNo partial updates or queries; keep metadata in a database
Deep relationship traversalsGraph: Neo4j, NeptuneHops follow stored adjacencyHard to shard; supernodes
Similarity over embeddingsVector index (dedicated, or an extension of an existing store)Approximate nearest-neighbour searchRecall is approximate; filtering and freshness; re-embedding on model change

Isolation levels, quick view

LevelStill possible (general model)Typical mechanismRemember
Read uncommittedEverything, including dirty readsNo read protectionRarely useful; some engines silently give read committed
Read committedNon-repeatable read, phantom, lost update, write skewSnapshot per statement, or short read locksThe default in PostgreSQL, Oracle and SQL Server
Repeatable readPhantom per the standard; lost update and write skew depend on the engineLong read locks, or a per-transaction snapshotThe name means different things: snapshot isolation in PostgreSQL; snapshot reads plus gap locks in MySQL InnoDB (its default)
Snapshot isolationWrite skewMVCC snapshot per transaction, first committer wins on write conflictsCalled "serializable" in Oracle and "repeatable read" in PostgreSQL
SerializableNoneTwo-phase locking, serializable snapshot isolation, or serial executionExpect 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.