6. Storage Fundamentals: Choosing a Database

6.1 The taxonomy

6.2 How to choose, out loud

1. What are the access patterns? List the top 3–5 queries. Pick the store that serves them by key or by index, not by scan.
2. Do I need multi-row/multi-entity transactions? If yes, start relational.
3. What's the write volume? Under ~10k writes/s, a single relational primary is fine. At hundreds of thousands per second, use wide-column/KV or sharded relational.
4. What's the consistency requirement? Strong and global means Spanner-class or a single-region primary. Eventual is fine for most social and analytics data.
5. What's the team's operational skill? A managed service beats a "better" database nobody can run at 3 a.m.

Default answer in interviews: "Postgres until a specific requirement forces otherwise." Then name the requirement that forces otherwise. That sounds mature; "MongoDB because it scales" doesn't.

6.3 Storage engine internals (asked in depth at Staff+)

B-tree (Postgres, MySQL InnoDB): in-place updates on fixed-size pages, plus a WAL for durability.

• Reads: O(log n), typically 3–4 page reads, mostly cached.
• Writes: random I/O; write amplification from page splits and full-page writes.
• Best for read-heavy workloads with range queries.

LSM-tree (Cassandra, RocksDB, Bigtable, ScyllaDB): writes go to a WAL plus an in-memory memtable, which is flushed to immutable sorted files (SSTables) and merged in the background by compaction.

• Writes: sequential, very fast.
• Reads: may check several SSTables. Bloom filters skip files that can't contain the key.
• Costs: compaction uses I/O and CPU; read and space amplification; tombstones make deletes tricky.
• Best for write-heavy workloads such as time series, events, and messages.

Write path (LSM):
  put(k,v) → append WAL → insert memtable ──(full)──▶ flush to SSTable L0
                                                            │
                                     background compaction  ▼
                                   L0 → L1 → L2 ... (sorted, non-overlapping)
Read path:
  memtable → (bloom filter says maybe?) L0 files → L1 → ... → first hit wins

Indexes: every secondary index speeds reads and slows writes. A covering index answers a query from the index alone. A composite index on (a, b) serves WHERE a=? and WHERE a=? AND b=?, but not WHERE b=?.

6.4 ACID and isolation levels

Write skew example: two on-call doctors each check "at least one other doctor is on call" and both go off call. Snapshot isolation allows it. The fix is SELECT ... FOR UPDATE, serializable isolation, or a materialized constraint. Interviewers love the lost update on a counter variant: fix it with an atomic UPDATE x SET n = n - 1 WHERE n > 0, optimistic concurrency (a version column), or a single-writer queue.

6.5 🏗️ Flow: inside a relational write (Postgres)

 UPDATE accounts SET bal = bal - 10 WHERE id = 7;   COMMIT;
   │
   ▼
 1. Find row via index → page in shared_buffers (load from disk if not cached)
 2. MVCC: write a NEW tuple version (old one marked dead by xmax); indexes updated
    unless HOT update (no indexed column changed, room on same page)
 3. Append change record to WAL buffer
 4. COMMIT → WAL flushed (fsync) to disk  ◀── durability point (commit latency ≈ fsync latency)
    └─ synchronous_commit / sync replica: also wait for standby to confirm
 5. Return success. Dirty data page stays in memory.
 6. Later: checkpointer/bgwriter write dirty pages; WAL streamed to replicas
 7. Later: VACUUM reclaims dead tuples, updates visibility map, freezes old xids

6.6 Deeper: engine internals that cause real incidents

• MVCC and VACUUM (Postgres): updates create new row versions. If VACUUM can't keep up, or a long-running transaction pins old versions, tables and indexes bloat and queries slow down.
• Transaction ID wraparound: Postgres xids are 32-bit. If old rows aren't frozen in time, the database stops accepting writes to protect data. Sentry wrote a well-known postmortem (2015) about exactly this outage. Monitor age(datfrozenxid).
• Clustered index order (MySQL InnoDB): rows are stored in primary-key order. Random UUIDv4 primary keys cause page splits, cache misses, and write amplification. Use time-ordered IDs (UUIDv7, ULID, Snowflake).
• Write amplification and replication format: Uber's 2016 post "Why Uber Engineering Switched from Postgres to MySQL" cited write amplification on secondary indexes (every update touched all indexes, because tuples get new physical locations), WAL-based physical replication shipping that amplification across datacenters, and painful major-version upgrades. The Postgres community disputed parts of it, which is itself a lesson: the "right" database depends on workload and the team's operational capability.
• Aurora's design: "the log is the database". Compute nodes ship only redo log records to a storage tier with 6 copies across 3 AZs, a write quorum of 4/6 and read quorum of 3/6, so it survives losing an AZ plus one more node (SIGMOD 2017 paper).

6.7 🌍 In production: database journeys

6.8 ⚠️ Corner cases & deep details

• DDL lock queues: ALTER TABLE waits for an exclusive lock behind one long-running query, and every new query queues behind the ALTER. The site goes down for a "metadata-only" change. Always set lock_timeout and retry.
• Connection limits: Postgres uses one process per connection, so thousands of app pods × a pool of 10 each overwhelms it. Use PgBouncer or RDS Proxy. Transaction pooling breaks session state (prepared statements, SET, advisory locks) unless the driver is configured for it.
• Collation changes: an OS upgrade that changes glibc collation (glibc 2.28) can silently corrupt the sort order of text indexes, so lookups miss existing rows. Reindex after OS upgrades, or use ICU collations with pinned versions.
• Money as floats: never. Use integer minor units (cents), and remember that some currencies have 0 decimals (JPY) and some have 3 (KWD).
• Timestamps: store UTC (timestamptz). Daylight saving makes "local midnight" ambiguous or nonexistent.
• Large deletes: DELETE FROM events WHERE ts < X with 500M rows causes huge WAL volume, replication lag, and bloat. Use partitioned tables and drop whole partitions instead.
• Hot rows: one counter row updated by 1,000 transactions per second becomes a lock-contention bottleneck. Use sharded counters, batch updates, or move the count to Redis and reconcile it.
• Long-running read on a replica: it conflicts with replayed changes (vacuum cleanup), so either the query is canceled or replication lags (hot_standby_feedback trades one for the other, plus bloat on the primary).