10.22 — Database Choice & Storage Engines

Data lives at the center of every system. Choosing how to store it isn't just about picking a popular brand; it's about understanding how bits are written to disk, how they are retrieved, and what guarantees the system makes when things go wrong.

ACID Guarantees

When designing systems, we rely on databases to protect us from chaos. The ACID properties are the contract a relational database makes with the application.

• Atomicity: "All or nothing." If a transaction fails halfway through, the database rolls back all partial changes.
• Consistency: Data always moves from one valid state to another. Constraints (like foreign keys) are never violated.
• Isolation: Concurrent transactions do not see each other's unfinished work. Be careful with the famous example. If Alice and Bob try to buy the last concert ticket at the same moment, whether only one succeeds depends on the isolation level and on how the code is written. A single UPDATE tickets SET sold = true WHERE id = 7 AND sold = false is safe at PostgreSQL's default level, because the database checks and writes in one step. "Read the row, decide in application code, then write" is not safe at the default level, and both buyers can succeed. That case needs a row lock (SELECT ... FOR UPDATE) or serializable isolation (7.4.1).
• Durability: Once a transaction commits, it survives power loss, crashes, and explosions. The data is on disk.

How Durability Works: The Write-Ahead Log (WAL)

Writing to a data file on disk is slow and random. If a database crashed mid-write, data would corrupt. To solve this, databases use a Write-Ahead Log (WAL).

Before modifying the actual data file, the database appends a record of the change to the WAL. Appending to a sequential file is blazing fast.

Write-Ahead Log (WAL) Sequence

If the server crashes after sending "OK" but before flushing to the actual data files, the database reads the WAL on reboot and re-applies the changes.

Storage Engines: How Data is Stored

The storage engine is the heart of the database. There are two dominant architectures: B-Trees and LSM Trees.

B-Trees (Read-Optimized)

B-Trees (specifically B+ Trees) are the standard for relational databases like PostgreSQL and MySQL. They keep data sorted and allow for fast reads, updates, and range queries.

• Mechanism: Data is stored in pages of fixed size (usually 4KB or 8KB). The tree structure allows the database to find any record in O(\log N) time, typically requiring only 3-4 disk seeks even for tables with billions of rows.
• Best for: Systems with high read volume, frequent point updates, and where strong consistency is required.
• Trade-off: Writes are slower. Updating a row means finding the right page, modifying it, and sometimes splitting pages, which creates random disk I/O.

B-Tree Index Structure

Log-Structured Merge (LSM) Trees (Write-Optimized)

LSM trees power Cassandra, ScyllaDB, HBase and RocksDB (which in turn sits underneath many other databases). They are designed for massive write throughput. DynamoDB is often listed here, but it is not an LSM store: AWS's 2022 paper on DynamoDB describes each storage replica as holding a write-ahead log and a B-tree.

• Mechanism: Every write is first appended to a write-ahead log on disk, so it survives a crash, and then inserted into a sorted in-memory table (the MemTable). When the MemTable fills up, it is written to disk in one sequential pass as an immutable Sorted String Table (SSTable). Nothing on disk is ever updated in place, so the disk only sees fast sequential writes. The full mechanism, including compaction and Bloom filters, is 7.3.3.
• Best for: Heavy write workloads (logs, IoT data, time-series).
• Trade-off: Reads are slower. Finding a record requires checking the MemTable, then checking multiple SSTables on disk. A background process called "compaction" periodically merges SSTables to optimize reads.

SQL vs. NoSQL: The Core Trade-offs

The choice between SQL and NoSQL comes down to schema flexibility, scaling patterns, and relational complexity.

Feature	SQL (PostgreSQL, MySQL)	NoSQL (MongoDB, Cassandra)
Schema	Rigid, enforced on write.	Flexible, enforced on read.
Scaling	Vertical (bigger machines). Sharding is hard.	Horizontal (more machines). Sharding is native.
Relationships	Joins are fast and native.	Joins are slow or unsupported. Data is denormalized.
Transactions	Strong ACID guarantees.	Often eventual consistency (BASE), limited ACID.

Treat that table as the folk version, because every row has a well-known exception. Distributed SQL databases (Spanner, CockroachDB, YugabyteDB) shard horizontally while keeping SQL and ACID transactions. PostgreSQL scales out with extensions such as Citus. MongoDB has supported multi-document ACID transactions since version 4.0 (2018). The question that actually decides the choice is your access pattern: if you know every query in advance and they all look up by one key, a key-value or wide-column store fits; if you need joins and new queries you have not thought of yet, start relational. 7.5 works through the NoSQL families one at a time.

Specialized Databases

Modern systems rarely use one database for everything (Polyglot Persistence).

Full-Text Search (Elasticsearch, Solr)

Relational databases are terrible at searching unstructured text (e.g., "Find products matching 'red running shoes'"). Full-text search engines use an Inverted Index. Instead of mapping documents to words, they map words to documents.

Inverted Index Mapping

Vector Databases (Pinecone, Milvus)

Used for AI and semantic search. Instead of exact word matches, they store mathematical representations of data (embeddings). They use algorithms like HNSW (Hierarchical Navigable Small World) to find the "nearest neighbors" to a query vector, enabling queries like "Find images similar to this one" or "Find documents conceptually related to 'finance'."

Connection Pools

Opening a database connection is expensive (TCP handshake, authentication, allocating memory). If a web server opens a new connection for every request, it will collapse under load.

A Connection Pool maintains a cache of open connections. When an application needs to talk to the DB, it borrows a connection, runs the query, and returns it.

TypeScript Example: Transaction with Connection Pool

Here is a concrete example of an e-commerce checkout using a connection pool and transactions in TypeScript (using pg for PostgreSQL).

import { Pool } from 'pg';

// 1. Initialize the Connection Pool once per application
const pool = new Pool({
  host: 'db.internal',
  user: 'app_user',
  max: 20, // Max 20 concurrent connections
  idleTimeoutMillis: 30000,
});

async function processCheckout(userId: string, productId: string, amount: number) {
  // 2. Checkout a connection from the pool
  const client = await pool.connect();

  try {
    // 3. Begin Transaction (Atomicity)
    await client.query('BEGIN');

    // 4. Deduct inventory (Check consistency)
    const inventoryRes = await client.query(
      'UPDATE inventory SET stock = stock - 1 WHERE product_id = $1 AND stock > 0 RETURNING id',
      [productId]
    );

    if (inventoryRes.rowCount === 0) {
      throw new Error('Out of stock');
    }

    // 5. Create order
    await client.query(
      'INSERT INTO orders (user_id, product_id, total_amount) VALUES ($1, $2, $3)',
      [userId, productId, amount]
    );

    // 6. Commit transaction (Durability guaranteed by WAL)
    await client.query('COMMIT');
    console.log('Checkout successful');

  } catch (error) {
    // 7. Rollback on failure
    await client.query('ROLLBACK');
    console.error('Checkout failed, rolling back:', error);
    throw error;
  } finally {
    // 8. Return connection to the pool
    client.release();
  }
}

What the interviewer will push on

1. "How does an LSM tree handle deletions?"
   • Answer: LSM trees are append-only. They handle deletes by writing a special marker called a "tombstone". During compaction, when the system merges SSTables, it sees the tombstone and drops the actual record.
2. "We have a massive surge in traffic, and our Postgres DB is at 100% CPU. What do you do?"
   • Answer: First, check connection pooling (are we thrashing connections?). Second, look for missing indexes causing full table scans. Third, implement read replicas to offload read traffic. Finally, cache hot data in Redis.
3. "When would you choose NoSQL over SQL?"
   • Answer: When you need to scale writes horizontally beyond what a single massive machine can handle, when your schema changes rapidly (e.g., storing varied JSON metadata), or when latency requirements demand the write-optimization of an LSM tree.

Recall

• ACID: Atomicity, Consistency, Isolation, Durability. The bedrock of predictable data.
• WAL: Write-Ahead Log. Fast sequential disk writes that guarantee durability before data is flushed.
• B-Trees: Read-optimized, heavily used in SQL databases. Fast lookups, slower random writes.
• LSM Trees: Write-optimized, used in NoSQL. Append-only memory buffers flushed to immutable files on disk.
• Inverted Index: The core data structure for full-text search. Maps words to documents.
• Connection Pools: Crucial for performance. Reuses expensive database connections instead of creating new ones per request.

Quiz

1. Why is writing to the WAL faster than updating a row in a table directly?
2. What happens to read performance in an LSM tree if compaction doesn't run often enough?
3. In the TypeScript example, what happens if the application crashes exactly after client.query('COMMIT') completes?

Next: 10.23 goes one layer down: block, file and object storage, and how a storage system keeps your bytes when disks fail.