How Databases Work

1 Storage Engines Overview

Every database has a storage engine at its core — the component responsible for writing data to disk and reading it back efficiently. When you issue a SQL query, it passes through several layers before anything touches the disk.

The Journey from SQL to Disk

 ┌──────────────────────────────────────────────────────────┐
 │                    CLIENT APPLICATION                    │
 │                  SELECT * FROM users                     │
 └──────────────────────┬───────────────────────────────────┘
                        │
                        ▼
 ┌──────────────────────────────────────────────────────────┐
 │                  SQL PARSER / LEXER                      │
 │          Tokenize → Parse → Abstract Syntax Tree         │
 └──────────────────────┬───────────────────────────────────┘
                        │
                        ▼
 ┌──────────────────────────────────────────────────────────┐
 │                   QUERY PLANNER                          │
 │    Rewrite rules → Cost estimation → Plan selection      │
 │    "Should I use index scan or sequential scan?"         │
 └──────────────────────┬───────────────────────────────────┘
                        │
                        ▼
 ┌──────────────────────────────────────────────────────────┐
 │                  EXECUTION ENGINE                        │
 │      Volcano/Iterator model: open() → next() → close()  │
 └──────────────────────┬───────────────────────────────────┘
                        │
                        ▼
 ┌──────────────────────────────────────────────────────────┐
 │                  STORAGE ENGINE                          │
 │  ┌──────────┐  ┌──────────┐  ┌───────────────────────┐  │
 │  │ B-Tree   │  │ LSM Tree │  │ Buffer Pool / Cache   │  │
 │  │ Index    │  │ (alt.)   │  │ (pages in memory)     │  │
 │  └────┬─────┘  └────┬─────┘  └───────────┬───────────┘  │
 │       └──────────────┴───────────────────┬┘              │
 └──────────────────────────────────────────┼───────────────┘
                                            │
                        ┌───────────────────┴─────────────┐
                        ▼                                 ▼
                 ┌─────────────┐                  ┌─────────────┐
                 │  DATA FILES │                  │  WAL / LOG  │
                 │  (pages on  │                  │  (append-   │
                 │   disk)     │                  │   only)     │
                 └─────────────┘                  └─────────────┘

Two Major Families

"The storage engine is the beating heart of any database. Everything else — the query optimizer, the transaction manager, the replication layer — depends on its ability to store and retrieve data efficiently." — Alex Petrov, Database Internals

2 Pages & Disk I/O

Databases don't read individual rows from disk — they read pages (also called blocks). A page is the smallest unit of I/O: typically 4 KB (SQLite), 8 KB (PostgreSQL), or 16 KB (MySQL/InnoDB). Understanding pages is fundamental to understanding database performance.

Page Structure

 ┌────────────────────────────────────────────────────────┐
 │                    PAGE (8 KB)                         │
 ├────────────────────────────────────────────────────────┤
 │  Page Header (24 bytes)                                │
 │  ┌──────────────────────────────────────────────────┐  │
 │  │ page_id | lsn | checksum | free_space | flags    │  │
 │  └──────────────────────────────────────────────────┘  │
 ├────────────────────────────────────────────────────────┤
 │  Item Pointers (line pointers) → offsets to tuples     │
 │  [ptr1] [ptr2] [ptr3] [ptr4] ...    → grows downward   │
 ├────────────────────────────────────────────────────────┤
 │                                                        │
 │              ◄── FREE SPACE ──►                        │
 │                                                        │
 ├────────────────────────────────────────────────────────┤
 │  Tuple data (actual rows)           ← grows upward     │
 │  ┌──────────┐ ┌──────────┐ ┌──────────┐               │
 │  │  Row 4   │ │  Row 3   │ │  Row 2   │ │  Row 1  │   │
 │  └──────────┘ └──────────┘ └──────────┘ └─────────┘   │
 ├────────────────────────────────────────────────────────┤
 │  Special space (B-tree pointers, etc.)                 │
 └────────────────────────────────────────────────────────┘

Page Sizes Across Databases

Sequential vs Random I/O

SSD vs HDD Characteristics

The massive random vs sequential gap on HDDs is why B-Trees (with their large fan-out minimizing random reads) were so critical. SSDs narrow the gap but don't eliminate it — sequential I/O is still faster, which is why LSM trees still outperform for write-heavy workloads even on SSDs.

3 Row Store vs Column Store

The way data is physically laid out on disk fundamentally determines what operations are fast. The two dominant approaches — row-oriented and column-oriented storage — optimize for entirely different access patterns.

Data Layout on Disk

 Table: users(id, name, age, city)
 ┌────┬─────────┬─────┬──────────┐
 │ id │  name   │ age │   city   │
 ├────┼─────────┼─────┼──────────┤
 │ 1  │ Alice   │ 30  │ NYC      │
 │ 2  │ Bob     │ 25  │ London   │
 │ 3  │ Charlie │ 35  │ Tokyo    │
 │ 4  │ Diana   │ 28  │ Paris    │
 └────┴─────────┴─────┴──────────┘

 ROW STORE layout (on disk):
 ┌──────────────────────────────────────────────────────┐
 │ [1,Alice,30,NYC] [2,Bob,25,London] [3,Charlie,35,...│
 └──────────────────────────────────────────────────────┘
 → All columns of a row are stored together contiguously
 → Great for: SELECT * FROM users WHERE id = 2

 COLUMN STORE layout (on disk):
 ┌───────────────────────┐
 │ id:   [1, 2, 3, 4]    │  ← column file 1
 ├───────────────────────┤
 │ name: [Alice,Bob,...]  │  ← column file 2
 ├───────────────────────┤
 │ age:  [30, 25, 35, 28] │  ← column file 3
 ├───────────────────────┤
 │ city: [NYC,London,...] │  ← column file 4
 └───────────────────────┘
 → Each column stored separately
 → Great for: SELECT AVG(age) FROM users

Compression Advantage of Column Stores

Because each column file contains values of the same type and often similar values, column stores achieve dramatically better compression:

4 B-Trees & B+ Trees

The B+ Tree is the most important data structure in database engineering. Nearly every relational database uses B+ Trees for its primary indexes. It was designed specifically for disk-based systems, where minimizing the number of I/O operations is paramount.

B+ Tree Structure

                        ┌─────────────────────────┐
                        │    [30 | 60 | 90]       │  ◄─ Root (internal node)
                        │   /    |     |     \    │     Keys act as separators
                        └──/─────|─────|──────\───┘
                          /      |     |       \
            ┌────────────┘  ┌────┘     └────┐   └────────────┐
            ▼               ▼               ▼                ▼
 ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
 │ [10|15|20|25]│ │ [35|40|45|50]│ │ [65|70|75|80]│ │ [95|97|99]   │
 │              │ │              │ │              │ │              │
 │ Internal     │ │ Internal     │ │ Internal     │ │ Internal     │
 └──┬──┬──┬──┬─┘ └──┬──┬──┬──┬─┘ └──┬──┬──┬──┬─┘ └──┬──┬──┬──┘
    │  │  │  │       │  │  │  │       │  │  │  │       │  │  │
    ▼  ▼  ▼  ▼       ▼  ▼  ▼  ▼       ▼  ▼  ▼  ▼       ▼  ▼  ▼
 ┌────┐┌────┐     ┌────┐┌────┐     ┌────┐┌────┐     ┌────┐┌────┐
 │Leaf││Leaf│ ... │Leaf││Leaf│ ... │Leaf││Leaf│ ... │Leaf││Leaf│
 │data││data│     │data││data│     │data││data│     │data││data│
 └──┬─┘└──┬─┘    └──┬─┘└──┬─┘    └──┬─┘└──┬─┘    └──┬─┘└──┬─┘
    └──►───┘──►──────┘──►──┘──►──────┘──►──┘──►──────┘──►──┘
    ▲                                                         ▲
    └─── Leaf nodes linked for range scans ───────────────────┘

Key Properties

Fan-Out & Depth Calculation

Formula: depth = ⌈log_f(n)⌉ where f is fan-out and n is number of rows. With fan-out 500: log₅₀₀(1,000,000,000) ≈ 3.3, so depth = 4.

Operations

1. Search: Start at root. At each internal node, binary search for the correct child pointer. Descend until reaching a leaf. Cost: O(log_f n) page reads, typically 2-4.
2. Insert: Search for the correct leaf. If the leaf has space, insert the key. If the leaf is full, split it into two leaves and push the middle key up to the parent. Splits can cascade to the root, increasing tree height by 1.
3. Delete: Find and remove the key from the leaf. If the leaf becomes less than half full, merge with a sibling or redistribute keys. In practice, many databases delay merges (tombstone-based) to avoid I/O.
4. Range scan: Search for the start key, then follow the leaf linked list until the end key is reached. Extremely efficient for ORDER BY and BETWEEN queries.

"B-Trees are the workhorse of database indexing — not because they're theoretically optimal, but because they map perfectly to the realities of disk-based storage: large pages, high fan-out, and sequential leaf scans." — Adapted from Database Internals by Alex Petrov

5 LSM Trees

The Log-Structured Merge Tree (LSM Tree) is the alternative to B-Trees, optimized for write-heavy workloads. Instead of updating data in-place, LSM Trees buffer writes in memory and periodically flush them as immutable sorted files to disk.

Write Path

 WRITE PATH:
 ┌──────────┐     ┌─────────────────────────────────────┐
 │  Write   │────►│  Write-Ahead Log (append-only)      │
 │  Request │     └─────────────────────────────────────┘
 └────┬─────┘                    │
      │                          │ (crash recovery)
      ▼                          │
 ┌─────────────────────────┐     │
 │     MEMTABLE            │◄────┘
 │  (Red-Black / Skip List)│
 │  Sorted in memory       │
 │  [key1→v, key2→v, ...]  │
 └─────────┬───────────────┘
           │ (when full, ~64MB)
           ▼
 ┌─────────────────────────┐
 │    Immutable Memtable   │──── flush to disk ────┐
 └─────────────────────────┘                       │
                                                   ▼
 DISK (sorted runs / SSTables):
 ┌─────────────────────────────────────────────────────┐
 │ Level 0:  [SST-1] [SST-2] [SST-3]  (may overlap)   │
 ├─────────────────────────────────────────────────────┤
 │ Level 1:  [────── SST-A ──────] [──── SST-B ────]  │
 ├─────────────────────────────────────────────────────┤
 │ Level 2:  [────────────── SST-X ──────────────────] │
 │           (10x larger than level 1)                 │
 └─────────────────────────────────────────────────────┘
           ▲                           │
           └─── COMPACTION ────────────┘
                (merge-sort overlapping SSTables)

Compaction Strategies

Amplification Trade-offs

Read Path

1. Check the active memtable (in memory — fastest).
2. Check immutable memtable(s) awaiting flush.
3. Check Level 0 SSTables (may overlap, check all).
4. For each subsequent level, use the SSTable's index block and optional Bloom filter to quickly determine if the key exists in that file.
5. If found, return the value. If a tombstone is found, the key was deleted.

6 Hash Indexes

Hash indexes provide O(1) average-case lookups for exact-match queries. They work by applying a hash function to the key and using the result to locate the data directly.

 Hash Index Mechanism:
                                      ┌─────────────┐
     hash("alice") = 3  ──────────►   │  Bucket 0   │
     hash("bob")   = 1  ──────┐      ├─────────────┤
     hash("carol") = 3  ───┐  │      │  Bucket 1   │◄── bob → row_ptr
     hash("dave")  = 0  ─┐ │  │      ├─────────────┤
                          │ │  │      │  Bucket 2   │
                          │ │  │      ├─────────────┤
                          │ │  └────► │  Bucket 3   │◄── alice → row_ptr
                          │ └───────► │             │    carol → row_ptr
                          │           ├─────────────┤    (chaining)
                          └─────────► │  Bucket 0   │◄── dave → row_ptr
                                      └─────────────┘

Characteristics

Where Hash Indexes Are Used

7 Bloom Filters

A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set. It can tell you "definitely not in the set" or "probably in the set" — but never gives false negatives.

 Bloom Filter: bit array of m bits, k hash functions

 Insert "alice":
   h1("alice") = 2    h2("alice") = 5    h3("alice") = 9

   Bit array:  [0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
                       ▲           ▲                 ▲
                   set bit 2   set bit 5         set bit 9

 Insert "bob":
   h1("bob") = 1      h2("bob") = 5      h3("bob") = 12

   Bit array:  [0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]
                    ▲                                  ▲
                set bit 1                          set bit 12
                           (bit 5 already set — shared!)

 Query "carol":
   h1("carol") = 2    h2("carol") = 7    h3("carol") = 12

   Check: bit[2]=1 ✓   bit[7]=0 ✗   → DEFINITELY NOT IN SET
   (one bit is 0, so "carol" was never inserted)

 Query "dave":
   h1("dave") = 1     h2("dave") = 5     h3("dave") = 9

   Check: bit[1]=1 ✓   bit[5]=1 ✓   bit[9]=1 ✓  → PROBABLY IN SET
   (all bits set — could be a FALSE POSITIVE if bits were set by others)

False Positive Rate

The probability of a false positive is approximately: p ≈ (1 − e^−kn/m)^k

Usage in Databases

8 SQL Query Lifecycle

Understanding how a SQL statement goes from text to results is crucial for performance tuning and debugging.

 ┌──────────────────────────────────────────────────────────────┐
 │  SELECT u.name, COUNT(o.id)                                  │
 │  FROM users u JOIN orders o ON u.id = o.user_id              │
 │  WHERE u.age > 25                                            │
 │  GROUP BY u.name                                             │
 │  HAVING COUNT(o.id) > 5                                      │
 │  ORDER BY COUNT(o.id) DESC                                   │
 └──────────────────────┬───────────────────────────────────────┘
                        │
          ┌─────────────▼──────────────┐
          │     1. LEXER / TOKENIZER   │
          │  Break SQL into tokens:    │
          │  SELECT, u.name, COUNT,    │
          │  FROM, users, JOIN, ...    │
          └─────────────┬──────────────┘
                        │
          ┌─────────────▼──────────────┐
          │     2. PARSER              │
          │  Build Abstract Syntax     │
          │  Tree (AST). Check syntax. │
          │  Resolve table/column      │
          │  names against catalog.    │
          └─────────────┬──────────────┘
                        │
          ┌─────────────▼──────────────┐
          │     3. QUERY REWRITER      │
          │  Apply rewrite rules:      │
          │  • View expansion          │
          │  • Subquery flattening     │
          │  • Predicate pushdown      │
          │  • Constant folding        │
          └─────────────┬──────────────┘
                        │
          ┌─────────────▼──────────────┐
          │     4. QUERY OPTIMIZER      │
          │  Generate candidate plans.  │
          │  Estimate cost of each.     │
          │  Choose cheapest plan.      │
          │  (join order, index usage,  │
          │   join algorithm, etc.)     │
          └─────────────┬──────────────┘
                        │
          ┌─────────────▼──────────────┐
          │     5. PLAN EXECUTOR        │
          │  Execute the chosen plan.   │
          │  Volcano model:             │
          │  open() → next() → close()  │
          │  Pull tuples through the    │
          │  operator tree.             │
          └─────────────┬──────────────┘
                        │
          ┌─────────────▼──────────────┐
          │     6. RESULT SET           │
          │  Format and send results    │
          │  back to client via wire    │
          │  protocol.                  │
          └────────────────────────────┘

Logical vs Physical Plan

9 Query Optimizer

The query optimizer is arguably the most complex component of a database. Its job: given a logical query, find the cheapest physical execution plan that produces correct results. This is an NP-hard problem in general, so optimizers use heuristics and dynamic programming.

Cost-Based vs Rule-Based

Selectivity Estimation

The optimizer must estimate how many rows each operation produces. Selectivity is the fraction of rows that pass a filter.

Join Ordering

For a query joining n tables, there are n! possible join orders (ignoring commutativity, it's still Catalan numbers — exponential). A 10-table join has over 17 billion possible orderings. Optimizers use:

• Dynamic programming (PostgreSQL for ≤12 tables): enumerate all subsets, build optimal plan bottom-up. Guarantees optimal join order within cost model but expensive for many tables.
• Greedy heuristics (PostgreSQL GEQO for >12 tables): genetic algorithm or greedy approaches. Finds good-enough plans in polynomial time.
• Left-deep plans only: restrict search to left-deep trees (pipeline-friendly). Reduces search space from exponential to O(n × 2ⁿ).

10 Join Algorithms

Joins are the most expensive operation in SQL processing. The choice of join algorithm dramatically affects performance, and the optimizer must choose wisely based on table sizes, available indexes, sort orders, and available memory.

The Three Major Join Algorithms

 NESTED LOOP JOIN:
 for each row r in outer_table:       ┌─────────┐
   for each row s in inner_table:     │ Outer   │──┐
     if r.key == s.key:               │ (small) │  │  for each outer row
       emit (r, s)                    └─────────┘  │
                                                    ▼
 Can use index on inner table         ┌──────────────────┐
 for Index Nested Loop Join           │ Scan Inner table │
 (avoid full inner scan each time)    │ (or index lookup)│
                                      └──────────────────┘

 HASH JOIN:
 Build phase:                         ┌─────────┐
   Build hash table from              │ Build   │ → Hash Table
   smaller table (build side)         │ (small) │   {key: [rows]}
 Probe phase:                         └─────────┘
   Scan larger table, probe           ┌─────────┐
   hash table for matches             │ Probe   │ → Lookup each key
                                      │ (large) │   in hash table
                                      └─────────┘

 MERGE JOIN:
 Both inputs must be sorted on        ┌────────┐  ┌────────┐
 the join key (or index provides      │Sorted A│  │Sorted B│
 sort order)                          │ 1,3,5,7│  │ 2,3,5,8│
                                      └───┬────┘  └───┬────┘
 Two pointers advance together:           │           │
 Like merging two sorted arrays           └─────┬─────┘
                                                ▼
                                          Match: 3, 5

11 Indexing Strategies

Choosing the right indexes is the single most impactful thing you can do for query performance. But more indexes aren't always better — each index adds write overhead and storage cost.

The Composite Index Left-Prefix Rule

 Index on (country, city, street):

 Can satisfy:                            Cannot satisfy:
 ✓ WHERE country = 'US'                  ✗ WHERE city = 'NYC'
 ✓ WHERE country = 'US' AND city = 'NYC' ✗ WHERE street = 'Broadway'
 ✓ WHERE country = 'US' AND city = 'NYC' ✗ WHERE city = 'NYC' AND street = '...'
   AND street = 'Broadway'
 ✓ WHERE country = 'US' ORDER BY city    (skips leftmost prefix!)

 Think of it like a phone book sorted by:
 last_name → first_name → middle_name
 You can look up by last_name, or (last, first), but NOT by first_name alone.

12 ACID Properties

ACID is the set of guarantees that make database transactions reliable. But each letter means something very specific — and most explanations only scratch the surface.

13 Isolation Levels

SQL defines four isolation levels, each preventing different anomalies. Stronger isolation means fewer anomalies but more overhead (locking, version tracking, aborts).

Anomaly Reference

Isolation Level vs Anomaly Matrix

*PostgreSQL's "Repeatable Read" actually uses Snapshot Isolation, which prevents phantom reads but still allows write skew. MySQL/InnoDB uses gap locks at Repeatable Read to prevent phantoms but with different trade-offs.

Default Levels

14 MVCC (Multi-Version Concurrency Control)

MVCC is the key insight that enables high-concurrency databases: readers never block writers, and writers never block readers. Instead of locking rows, the database keeps multiple versions of each row and shows each transaction only the versions it's allowed to see.

PostgreSQL MVCC

 PostgreSQL stores version info IN the heap tuple itself:

 Tuple Header:
 ┌──────────┬──────────┬────────────┬────────────────────┐
 │  xmin    │  xmax    │  ctid      │  infomask bits     │
 │ (created │ (deleted │ (location  │  (committed,       │
 │  by txn) │  by txn) │  on disk)  │   aborted, etc.)   │
 └──────────┴──────────┴────────────┴────────────────────┘

 Example: UPDATE users SET name='Bob2' WHERE id=1;
 (executed by transaction 150)

 BEFORE:
 ┌─────────────────────────────────────────┐
 │ xmin=100  xmax=∞  data: {id:1, Bob}    │  ← visible to all
 └─────────────────────────────────────────┘

 AFTER:
 ┌─────────────────────────────────────────┐
 │ xmin=100  xmax=150 data: {id:1, Bob}   │  ← old version (dead)
 └─────────────────────────────────────────┘
 ┌─────────────────────────────────────────┐
 │ xmin=150  xmax=∞   data: {id:1, Bob2}  │  ← new version (live)
 └─────────────────────────────────────────┘

 Visibility rule (simplified, for Read Committed):
 A tuple is visible if:
   xmin is committed AND (xmax is not set OR xmax is not committed)

MySQL/InnoDB MVCC

 InnoDB stores UNDO LOG pointers in each row:

 Clustered Index Row:
 ┌──────────┬──────────┬──────────────┬──────────┐
 │  trx_id  │ roll_ptr │  actual data │  ...     │
 │ (last    │ (pointer │              │          │
 │  modifier)│ to undo) │              │          │
 └──────────┴────┬─────┴──────────────┴──────────┘
                 │
                 ▼
 ┌──────────────────────────────────┐
 │  Undo Log Entry (prev version)  │
 │  trx_id=140, data: {old values} │
 │  roll_ptr ──────────────────────┼──►  Even older version
 └──────────────────────────────────┘

 → InnoDB builds version chain via undo log
 → PostgreSQL stores all versions in heap (needs VACUUM)

Garbage Collection

15 Write-Ahead Log (WAL)

The WAL is the mechanism that makes durability possible without writing every changed data page to disk on every commit. The core rule: log the change before applying it. If the system crashes, the log is replayed to reconstruct any committed changes.

Why WAL Exists

Write Flow with WAL

 Transaction: UPDATE accounts SET balance = 900 WHERE id = 1;
              UPDATE accounts SET balance = 1100 WHERE id = 2;
              COMMIT;

 ┌────────────────────────────────────────────────────────────┐
 │ 1. Modify pages in BUFFER POOL (in memory)                 │
 │    Page 42: account 1 balance → 900                        │
 │    Page 87: account 2 balance → 1100                       │
 │    (pages marked "dirty" but NOT written to disk yet)      │
 └───────────────────────┬────────────────────────────────────┘
                         │
                         ▼
 ┌────────────────────────────────────────────────────────────┐
 │ 2. Write WAL records (append to WAL file)                  │
 │    LSN 1001: page 42 offset 128 old=1000 new=900           │
 │    LSN 1002: page 87 offset 128 old=1000 new=1100          │
 │    LSN 1003: COMMIT transaction 500                        │
 └───────────────────────┬────────────────────────────────────┘
                         │
                         ▼
 ┌────────────────────────────────────────────────────────────┐
 │ 3. FSYNC the WAL to disk ← DURABILITY GUARANTEE           │
 │    Only after WAL is on disk does COMMIT return to client  │
 └───────────────────────┬────────────────────────────────────┘
                         │
                         ▼
 ┌────────────────────────────────────────────────────────────┐
 │ 4. Later: CHECKPOINT                                       │
 │    Background writer flushes dirty pages to data files     │
 │    Records checkpoint position in WAL                      │
 │    Old WAL segments can be recycled                        │
 └────────────────────────────────────────────────────────────┘

 CRASH RECOVERY:
 ┌────────────────────────────────────────────────────────────┐
 │ 1. Find last checkpoint in WAL                             │
 │ 2. REDO: replay all WAL records after checkpoint           │
 │    → applies committed changes not yet in data files       │
 │ 3. UNDO: roll back uncommitted transactions                │
 │    → ensures atomicity                                     │
 │ 4. Database is consistent — ready to accept connections    │
 └────────────────────────────────────────────────────────────┘

Checkpoint

A checkpoint flushes all dirty buffer pool pages to disk and records the current WAL position. After a checkpoint, the database only needs to replay WAL records after that point on crash recovery. Without checkpoints, recovery would need to replay the entire WAL from the beginning — potentially hours of work. PostgreSQL triggers checkpoints based on time interval (checkpoint_timeout, default 5 min) or WAL volume (max_wal_size, default 1 GB).

16 Replication

Replication copies data across multiple nodes for fault tolerance (survive node failures), read scaling (distribute read load), and geographic proximity (serve users from nearby datacenters).

Replication Topologies

 SINGLE-LEADER (Primary/Replica):
 ┌─────────┐    WAL / binlog stream     ┌─────────┐
 │ PRIMARY │ ──────────────────────────► │ REPLICA │
 │ (R/W)   │ ──────────────────────────► │ (Read)  │
 └─────────┘                             └─────────┘
      │                                  ┌─────────┐
      └────────────────────────────────► │ REPLICA │
                                         │ (Read)  │
                                         └─────────┘

 MULTI-LEADER:
 ┌─────────┐ ◄──────────────────────► ┌─────────┐
 │ LEADER  │    bidirectional          │ LEADER  │
 │ DC-East │    replication            │ DC-West │
 └─────────┘                           └─────────┘
      │                                      │
      ▼                                      ▼
 ┌─────────┐                           ┌─────────┐
 │ REPLICA │                           │ REPLICA │
 └─────────┘                           └─────────┘

 LEADERLESS (Dynamo-style):
 ┌────────┐  ┌────────┐  ┌────────┐  ┌────────┐  ┌────────┐
 │ Node 1 │  │ Node 2 │  │ Node 3 │  │ Node 4 │  │ Node 5 │
 └────────┘  └────────┘  └────────┘  └────────┘  └────────┘
      Client writes to W nodes, reads from R nodes
      Consistency if W + R > N (quorum)

Synchronous vs Asynchronous

Conflict Resolution (Multi-Leader / Leaderless)

17 Sharding & Partitioning

When a single node can't hold all the data or handle all the traffic, we partition (shard) the data across multiple nodes. Each node is responsible for a subset of the data.

Partitioning Strategies

 RANGE PARTITIONING:
 ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
 │  Shard 1     │ │  Shard 2     │ │  Shard 3     │
 │  A - F       │ │  G - N       │ │  O - Z       │
 │  user_ids    │ │  user_ids    │ │  user_ids    │
 │  1-1M        │ │  1M-2M       │ │  2M-3M       │
 └──────────────┘ └──────────────┘ └──────────────┘
 ✓ Range queries efficient   ✗ Hotspots if data skewed

 HASH PARTITIONING:
 shard = hash(key) % num_shards
 ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
 │  Shard 0     │ │  Shard 1     │ │  Shard 2     │
 │  hash%3 == 0 │ │  hash%3 == 1 │ │  hash%3 == 2 │
 └──────────────┘ └──────────────┘ └──────────────┘
 ✓ Even distribution          ✗ Range queries need all shards
 ✓ No hotspots                ✗ Resharding is expensive

 DIRECTORY-BASED:
 ┌────────────────────┐
 │  Lookup Service     │     key → shard mapping
 │  user_1 → shard_2  │     stored in a directory
 │  user_2 → shard_1  │     (e.g., ZooKeeper, etcd)
 │  user_3 → shard_3  │
 └────────────────────┘
 ✓ Flexible placement    ✗ Directory is single point of failure
 ✓ Easy rebalancing      ✗ Extra lookup on every request

Rebalancing

When adding or removing nodes, data must be redistributed. Strategies include:

1. Fixed number of partitions: Create many more partitions than nodes (e.g., 1000 partitions across 10 nodes). When adding a node, move entire partitions. Used by Elasticsearch, Riak, Couchbase.
2. Dynamic partitioning: Split partitions that grow too large, merge small ones. Used by HBase, MongoDB. Adapts to data size but more complex.
3. Consistent hashing: Nodes are placed on a hash ring. Adding a node only moves data from adjacent nodes. Minimizes data movement. Used by Cassandra, DynamoDB.

Cross-Shard Queries

18 CAP Theorem & Consistency Models

"The CAP theorem is widely misunderstood. It does NOT say 'pick 2 of 3'. It says: during a network partition, you must choose between consistency and availability. When there's no partition, you can have both." — Martin Kleppmann, Designing Data-Intensive Applications

What CAP Actually Means

 CAP Theorem (Brewer, 2000; proven by Gilbert & Lynch, 2002):

 In a distributed system, when a NETWORK PARTITION occurs,
 you must choose between:

 ┌─────────────────────────────────┐
 │         CONSISTENCY (C)         │  Every read receives the most
 │                                 │  recent write or an error
 └────────────────┬────────────────┘
                  │
      ┌───────────┴───────────┐
      │   PARTITION (P)       │  Network partition is
      │   (inevitable)        │  not a choice — it WILL happen
      └───────────┬───────────┘
                  │
 ┌────────────────┴────────────────┐
 │         AVAILABILITY (A)        │  Every request receives a
 │                                 │  non-error response
 └─────────────────────────────────┘

 During a partition:
   CP system: refuse to serve requests (unavailable) to maintain consistency
              → e.g., HBase, MongoDB (with majority write concern), etcd
   AP system: serve potentially stale data to remain available
              → e.g., Cassandra, DynamoDB, CouchDB

 When there's NO partition (normal operation):
   You can have BOTH consistency AND availability!
   This is why "CA" is misleading — ALL systems are CA when the network works.

Consistency Models Spectrum

19 Consensus Algorithms

Consensus is the problem of getting multiple nodes to agree on a value despite failures. It is the foundation of fault-tolerant distributed systems — used for leader election, distributed locking, and replicated state machines.

Raft — Simplified Consensus

 RAFT: Three Roles
 ┌──────────┐    ┌──────────┐    ┌──────────┐
 │ LEADER   │    │ FOLLOWER │    │ FOLLOWER │
 │ (1 only) │───►│          │    │          │
 │ Handles  │───►│ Replicate│    │ Replicate│
 │ all      │    │ entries  │    │ entries  │
 │ writes   │───►│          │◄───│          │
 └──────────┘    └──────────┘    └──────────┘

 LEADER ELECTION (term-based):
 ┌──────────────────────────────────────────────────────────┐
 │ 1. Leader sends heartbeats every ~150ms                  │
 │ 2. If a follower doesn't hear from leader for            │
 │    election timeout (150-300ms), it becomes CANDIDATE    │
 │ 3. Candidate increments term, votes for itself           │
 │ 4. Requests votes from all other nodes                   │
 │ 5. Wins if gets majority (N/2 + 1) votes                │
 │ 6. New leader starts sending heartbeats                  │
 └──────────────────────────────────────────────────────────┘

 LOG REPLICATION:
 Client ──► Leader
                │
                ├──► Append to local log
                ├──► Send AppendEntries RPC to all followers
                ├──► Wait for majority acknowledgment
                ├──► COMMIT entry (apply to state machine)
                └──► Respond to client

 Leader Log:    [1:set x=1] [2:set y=2] [3:set x=3] committed
 Follower A:   [1:set x=1] [2:set y=2] [3:set x=3] committed
 Follower B:   [1:set x=1] [2:set y=2]             catching up...
                                         ▲
                                 majority (2/3) = committed

Split Brain Prevention

 NETWORK PARTITION:
 ┌─────────────────────┐        ┌─────────────────────┐
 │  Partition A         │   ✗   │  Partition B         │
 │  ┌────────┐          │  ███  │          ┌────────┐  │
 │  │Leader  │          │  ███  │          │Follower│  │
 │  │(old)   │          │  ███  │          │        │  │
 │  │        │          │  ███  │          └────────┘  │
 │  └────────┘          │  ███  │          ┌────────┐  │
 │  ┌────────┐          │  ███  │          │Follower│  │
 │  │Follower│          │  ███  │          │        │  │
 │  └────────┘          │       │          └────────┘  │
 └─────────────────────┘        └─────────────────────┘
   2 nodes — can't get             3 nodes — CAN elect
   majority (need 3/5)             new leader (3/5 = majority)
   Old leader can't commit!        New leader takes over.

 → Only ONE partition can have a majority → no split brain
 → This is why clusters use odd numbers (3, 5, 7 nodes)

Paxos vs Raft

20 PostgreSQL Internals

PostgreSQL is an excellent case study because it's open-source, well-documented, and contains a full-featured implementation of nearly every concept discussed in this guide.

Architecture Overview

 ┌─────────────────────────────────────────────────────────────┐
 │                    PostgreSQL Architecture                   │
 ├─────────────────────────────────────────────────────────────┤
 │                                                             │
 │  Client ──► Postmaster (listener, PID 1)                    │
 │                │                                            │
 │                ├──► Backend Process 1  (one per connection)  │
 │                ├──► Backend Process 2                        │
 │                └──► Backend Process 3                        │
 │                                                             │
 │  Background Processes:                                      │
 │  ┌──────────────┐ ┌──────────────┐ ┌─────────────────────┐ │
 │  │ WAL Writer   │ │ BG Writer    │ │ Autovacuum Launcher │ │
 │  │ (flush WAL)  │ │ (dirty pages)│ │ → Autovacuum Workers│ │
 │  └──────────────┘ └──────────────┘ └─────────────────────┘ │
 │  ┌──────────────┐ ┌──────────────┐ ┌─────────────────────┐ │
 │  │ Checkpointer │ │ Stats        │ │ Logical Replication │ │
 │  │              │ │ Collector    │ │ Workers             │ │
 │  └──────────────┘ └──────────────┘ └─────────────────────┘ │
 │                                                             │
 │  Shared Memory:                                             │
 │  ┌─────────────────────────────────────────────────────┐   │
 │  │ Shared Buffers (default 128MB, tune to 25% of RAM)  │   │
 │  │ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐      │   │
 │  │ │Page 1│ │Page 2│ │Page 3│ │ ...  │ │Page N│      │   │
 │  │ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘      │   │
 │  ├─────────────────────────────────────────────────────┤   │
 │  │ WAL Buffers │ Lock Table │ CLOG │ Proc Array      │   │
 │  └─────────────────────────────────────────────────────┘   │
 │                                                             │
 │  On Disk:                                                   │
 │  ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────────┐  │
 │  │ Data Dir │ │ WAL Dir  │ │ CLOG     │ │ pg_stat_tmp  │  │
 │  │ (base/)  │ │ (pg_wal/)│ │(pg_xact/)│ │              │  │
 │  └──────────┘ └──────────┘ └──────────┘ └──────────────┘  │
 └─────────────────────────────────────────────────────────────┘

Process Model

PostgreSQL uses a process-per-connection model (not threads). Each client connection gets a dedicated backend process via fork(). This provides excellent isolation (a crash in one backend doesn't affect others) but higher memory overhead compared to thread-per-connection (MySQL) or async I/O (Node.js-style) models. Connection poolers like PgBouncer or pgcat are essential for high-connection workloads.

Key Subsystems

21 Database Comparison

Each database makes different architectural trade-offs. Understanding these trade-offs helps you choose the right tool for your workload.

Architecture Diagrams

"There is no 'best' database — only the best database for your specific workload, consistency requirements, operational capacity, and scale. The engineering art is in understanding the trade-offs deeply enough to make an informed choice." — Adapted from Designing Data-Intensive Applications by Martin Kleppmann