Capstone: Operating Systems for Databases

Open the source tree of any mature database and you will find, with slightly different names, every subsystem we have studied in this course. There is a component that decides which query runs on which CPU and for how long — that is a scheduler. There is a component that caches disk pages in RAM and evicts the cold ones — that is a page-replacement policy. There is a component that lets many transactions touch the same table without corrupting each other — that is synchronization. There is a component that detects when two transactions are stuck waiting on each other and kills one — that is deadlock detection and recovery. A database is not built on top of these ideas by accident; it is built out of them.

The obvious question is: the OS already provides all of this, so why does the database do it again? The answer is the theme of the whole chapter. A general-purpose kernel is deliberately ignorant of what any one program is doing — it has to be, to be fair to all of them. The database is not ignorant of itself. It knows a page it just read will probably be read again in the next millisecond; it knows a transaction holds exactly these rows; it knows a sequential scan will touch ten thousand pages in order. Armed with that workload knowledge, the database can make better decisions than a fair, general kernel — so it takes the mechanism back into its own hands.

DBMS

The database management system — the server process(es) that store data, run queries, and guarantee transactions. Postgres, MySQL/InnoDB, Oracle, SQLite are all DBMSes.

Transaction

A group of reads and writes that must appear to happen all-or-nothing and in isolation — the database’s unit of work, and the source of most of its OS-flavoured problems.

Workload knowledge

What a database knows about its own access patterns that the kernel cannot know — the justification for re-implementing OS services in user space.

The very first design decision a database makes is one we studied directly: process or thread? Back when we separated the two, the trade was stark. Processes give you isolation — a crash in one cannot corrupt another’s memory — at the cost of expensive creation and expensive communication, since they do not share an address space. Threads give you cheap creation and free data sharing, because they live in one address space, at the cost that one bad pointer can take down everything. Two of the most-deployed databases in the world chose opposite sides of that trade, and both were right for their reasons.

PostgreSQL is process-per-connection. A supervisor process (historically the postmaster) forks a dedicated backend process for every client connection — this is fork() and the process model straight out of the chapter on the PCB. The backends do not share an address space, so to share the buffer pool, the lock table, and other global state they attach a System V / POSIX shared-memory segment: the "shared_buffers" region. That is shared-memory IPC, exactly as we covered it — the one form of interprocess communication fast enough to be the beating heart of a database, because after setup it needs no syscall at all to read or write. Postgres pays for a heavier per-connection footprint and buys robustness: a backend that segfaults on a bad query takes itself down, not the server.

MySQL with the InnoDB engine is thread-per-connection. One server process hosts many threads, all sharing the same address space and therefore the same buffer pool with no special shared-memory setup — sharing is the default when you are threads, as we saw. Context switches between threads are cheaper than between processes because the address space and its page tables do not change. The cost is the thread model’s cost: less isolation, and a discipline of careful locking so threads do not corrupt shared structures. Neither choice is "better" in the abstract; each database picked the point on the isolation-versus-sharing curve that matched its goals.

This is also why connection pooling exists, and why it is not optional at scale. Each new connection means a new backend process (Postgres) or thread plus its stack and per-connection buffers (MySQL). Ten thousand clients opening ten thousand direct connections would drown the machine in context-switching and memory — the exact scheduler and memory pressures we studied. A pooler (PgBouncer, or a client-side pool like HikariCP) keeps a small fixed set of real connections and multiplexes many clients over them, so the number of actual backends stays near the CPU count where the scheduler is happy.

# PostgreSQL — one OS process per connection (fork from the postmaster)
$ ps -e -o pid,comm | grep postgres
  1421 postgres                 # postmaster (supervisor)
  1439 postgres: walwriter
  1502 postgres: backend  app  # <- one backend per client
  1547 postgres: backend  app  # <- another client, another process

# MySQL — one process, many threads (Threads_connected, not processes)
$ mysql -e "SHOW STATUS LIKE 'Threads_connected';"
+-------------------+-------+
| Variable_name     | Value |
| Threads_connected | 214   |   # 214 threads inside ONE server process
+-------------------+-------+

When we studied virtual memory and demand paging, one quiet hero was the OS page cache: the kernel keeps recently-used file blocks in otherwise-free RAM, so the second read() of a file is served from memory instead of the disk. It is automatic, it is transparent, and for most programs it is a gift. A database looks at that same gift and says: thank you, but I will do it myself. Every serious DBMS maintains its own user-space cache of disk pages, called the buffer pool (InnoDB) or shared buffers (Postgres).

Why not just trust the page cache? Because the database, again, knows more. It can pin the pages of a hot index in memory and refuse to evict them; it can use a replacement policy tuned for scans and index lookups rather than the kernel’s general-purpose LRU approximation; it can coordinate eviction with its write-ahead log so it never writes a dirty page to disk before the log record that describes it (the "write-ahead" rule). The kernel, being fair and ignorant of all this, cannot make those guarantees. So the database allocates a big chunk of RAM up front and manages page eviction itself — a page-replacement algorithm from the memory chapters, running in user space.

This creates a genuinely famous problem: double caching. If the database has its own buffer pool AND reads its files through the normal filesystem interface, then every page can end up cached twice — once in the kernel’s page cache and once in the buffer pool — wasting RAM and paying to copy the data across the user/kernel boundary twice. Two responses exist. Postgres deliberately keeps its shared_buffers relatively modest and lets the OS page cache do a second layer of caching, accepting some double-caching as the price of a simpler, more portable design. Others — InnoDB in its common configuration, Oracle, and Postgres shops that care — open data files with O_DIRECT, which tells the kernel "do not cache this file; hand me the bytes straight from the device". That eliminates the double copy and the wasted RAM, at the cost that the database now owns caching entirely and had better be good at it.

Buffer pool / shared buffers

The database’s own in-RAM cache of disk pages, managed by its own eviction policy — a user-space page cache.

OS page cache

The kernel’s automatic cache of file blocks in free RAM (ch23). Transparent to normal programs; redundant to a DB that caches the same pages itself.

Double caching

The same page held in both the buffer pool and the page cache — wasted memory and an extra copy across the boundary.

O_DIRECT

An open() flag that bypasses the page cache so reads/writes go straight to the device, letting the DB avoid double caching and own its memory.

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 42;

-- Index Scan using orders_customer_id_idx on orders
--   (actual time=0.021..0.084 rows=17 loops=1)
--   Buffers: shared hit=6 read=2
--            ^^^^^^^^^^^^^^^^^^^^
--   hit=6  -> 6 pages already in the buffer pool (fast)
--   read=2 -> 2 pages fetched from below (page cache or disk)

The "D" in a transaction’s guarantees is durability: once the database tells you COMMIT succeeded, that data must survive even if the power dies one millisecond later. This is precisely the crash-consistency problem we met when studying file systems, and the database solves it with precisely the file system’s trick: write-ahead logging, which is journaling by another name.

Here is the tension. The actual data lives in pages scattered across the disk, and those pages sit dirty in the buffer pool. Writing them all out at every commit would mean random I/O all over the disk — slow, as we learned when we compared sequential and random access. So the database cheats intelligently. Before it touches the real data pages, it writes a small, compact description of the change to the write-ahead log (WAL in Postgres, the redo log in InnoDB), and the log is append-only, so writing to it is sequential I/O — the fast kind. The rule that gives the technique its name: the log record must reach durable storage before the data page it describes. If the machine crashes, recovery replays the log to reconstruct any committed change whose data page never made it to disk. This is the journaling idea, applied to your rows instead of to filesystem metadata.

But writing to the log is not enough, and here is where the whole course pays off. A normal write() only copies your bytes into the OS page cache; the kernel flushes them to the device whenever it feels like it. If the power fails in that window, the "written" log is gone. So at COMMIT the database must issue fsync() — the syscall that forces the file’s data all the way down to durable storage and does not return until the device confirms it. fsync is the single most important syscall in the database world, and it is expensive: it is a synchronous trip to the disk, and it cannot be buffered away, because buffering it away is exactly the thing that would lose your data.

Because fsync is costly and every commit needs one, databases use group commit: instead of one fsync per transaction, the server briefly batches the log records of many transactions committing at nearly the same instant and flushes them with a single fsync, amortising that one expensive crossing across dozens of commits — the same "batch to amortise the syscall" reflex we saw with buffered I/O. And then there is the infamous "fsync gate": consumer disks (and some cloud volumes) have their own volatile write cache and will happily acknowledge an fsync before the data truly hits the platter — the disk lies. Databases have had real data-loss bugs from disks and even from mishandled fsync error returns. The lesson is sobering and pure OS: durability is only as honest as the weakest layer in the write path.

BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;   -- writes the WAL record, then fsync() forces it to disk
          -- only now is the transfer durable; the data pages
          -- themselves are flushed back lazily, much later

# Postgres: fsync=off makes commits fast and UNSAFE — a crash can
# lose committed transactions and corrupt the cluster. Never in prod.
fsync = on                 # (default) fsync the WAL at commit
synchronous_commit = on    # (default) COMMIT waits for the flush

# The honest way to go faster: group commit, one fsync for many txns
commit_delay = 100         # microseconds to gather a batch

The moment two transactions touch the same data, we are back in the concurrency chapters — race conditions, critical sections, mutexes — only now the shared data is your rows. Databases draw a distinction that maps perfectly onto ideas we already have, and confusing the two is one of the most common misunderstandings among engineers: locks versus latches.

A lock is logical and long-lived. It protects a row or a table for the duration of a transaction — potentially seconds, across many statements — and it is tracked in a lock manager, a data structure that records who holds what and who is waiting. Locks come in modes (a shared read lock lets many readers coexist; an exclusive write lock stands alone), which is exactly the readers-writer pattern from the synchronization chapter. A latch, by contrast, is physical and momentary: it is a short in-memory mutex or spinlock that guards an internal structure — a buffer-pool page, a spot in the WAL buffer — for the handful of instructions it takes to modify it safely. A latch is the OS mutex we studied, used exactly as the OS uses it; a lock is a higher-level, transaction-scoped concept the database builds on top.

The rule that makes transaction locking give you correct isolation is two-phase locking (2PL): a transaction may only acquire locks in a first "growing" phase and only release them in a later "shrinking" phase — in practice, it holds every lock until it commits. That discipline is what guarantees serializability, and it is the same reasoning we used about holding a mutex across a whole critical section rather than dropping it early. The trade is the same too: hold locks longer and you get stronger correctness but more waiting; the more transactions contend for the same hot rows, the more they queue, and throughput collapses — lock contention, precisely the phenomenon from the concurrency chapters, now visible as a database that "gets slow under load".

BEGIN;
-- take an exclusive lock on this row; other writers to it now WAIT
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;   -- the lock is released here, not before (2PL shrinking phase)

Lock

A logical, transaction-scoped guard on a row or table, tracked in the lock manager; held (under 2PL) until COMMIT. Can participate in deadlock.

Latch

A short in-memory mutex/spinlock guarding an internal structure for a few instructions — the OS mutex from ch15, used verbatim.

Shared vs exclusive

Read locks (shared, many at once) vs write locks (exclusive, one at a time) — the readers-writer pattern applied to rows.

Two-phase locking (2PL)

Acquire locks in a growing phase, release in a shrinking phase — hold to commit — which yields serializable isolation.

Pure locking has an ugly cost: if writers take exclusive locks and readers must wait for them, then a long-running report can block every update, or a busy writer can stall every reader. Most modern databases — Postgres, InnoDB, Oracle — largely avoid this with multi-version concurrency control (MVCC), and MVCC turns out to be a database retelling of an OS trick we already studied: copy-on-write.

The idea: instead of overwriting a row in place, a write creates a new version of the row, stamped with the transaction that made it, while the old version stays around. Every transaction sees a consistent snapshot of the database as of the moment it started — it simply reads whichever version was current then. The headline consequence is the one that makes MVCC beloved: readers do not block writers, and writers do not block readers. A long analytics query reads an old, stable snapshot while OLTP writes race ahead creating new versions; neither waits on the other. Compare that with pure 2PL, where that same reader would have frozen the table.

If that "make a new copy on write instead of mutating in place" pattern sounds familiar, it is exactly copy-on-write from the virtual-memory chapter — the same mechanism the kernel uses when fork() gives a child its parent’s pages read-only and only makes a private copy when someone writes. MVCC applies the identical principle to rows: share the old version freely with readers; branch a new version only for the writer. Same insight, different layer.

Nothing is free, and MVCC’s cost is pure OS too: those old versions pile up as garbage once no transaction can still see them, and something must reclaim the space. In Postgres that job is VACUUM (and autovacuum); in InnoDB it is the purge threads. This is garbage collection, with the same failure mode GC always has — if it falls behind the rate of writes, dead versions accumulate, tables bloat, and performance degrades. A "long-running transaction" is dangerous precisely because it holds an old snapshot alive and forbids vacuum from cleaning anything newer than it, exactly as a lingering reference stops a garbage collector from freeing memory.

-- Session A (reader, REPEATABLE READ): opens a snapshot
BEGIN;
SELECT balance FROM accounts WHERE id = 1;  -- sees 500

-- Session B (writer), meanwhile — does NOT block A
BEGIN;
UPDATE accounts SET balance = 400 WHERE id = 1;  -- creates a new version
COMMIT;

-- Session A again, same transaction: still its snapshot
SELECT balance FROM accounts WHERE id = 1;  -- STILL sees 500
COMMIT;   -- old version 500 is now garbage -> VACUUM will reclaim it

Everything we said about deadlock among processes applies, without a single change, to transactions. The four Coffman conditions — mutual exclusion, hold-and-wait, no preemption, circular wait — describe a database deadlock exactly as they describe an OS one. The classic shape: transaction T1 locks row A and then wants row B; transaction T2 has already locked row B and now wants row A. Each holds what the other needs, neither will release before it commits (that is 2PL), and so they wait for each other forever. Draw the wait-for graph and there is a cycle — the same diagnostic we drew for processes.

How does the database handle it? Not by prevention or the banker’s-algorithm-style avoidance we studied — those are too restrictive for a general query workload. Databases use detection and recovery, the other branch from the deadlock chapters. A background deadlock detector periodically builds the wait-for graph and looks for a cycle; when it finds one, it chooses a victim (often the transaction that has done the least work, so the least is lost), aborts and rolls it back to break the cycle, and lets the survivor proceed. The victim’s application gets an error. This is textbook detect-a-cycle-and-preempt-a-victim recovery, running automatically inside your database many times an hour under load.

Which leads to the single most important practical habit for any engineer writing transactional code: deadlocks are not bugs to be eliminated, they are a normal condition to be handled. Because the database resolves a deadlock by killing one transaction, your application must be ready to catch that specific error and simply retry the transaction. Well-written data-access code wraps transactions in a retry loop keyed on the deadlock error code. You can also make deadlocks rarer by always acquiring locks in a consistent global order — the exact "impose an ordering on resources to break circular wait" prevention technique from the deadlock chapters, applied to which rows you touch first.

-- Session 1                      -- Session 2
BEGIN;                          BEGIN;
UPDATE accounts                 UPDATE accounts
  SET bal=bal-10 WHERE id=1;      SET bal=bal-10 WHERE id=2;
                                -- both now hold one row...
UPDATE accounts                 UPDATE accounts
  SET bal=bal+10 WHERE id=2;      SET bal=bal+10 WHERE id=1;
-- (waits for session 2)        -- (waits for session 1) => CYCLE

-- The detector fires; one session receives:
ERROR:  deadlock detected
DETAIL: Process 1502 waits for ShareLock on transaction 998;
        blocked by process 1547.
HINT:   See server log for query details.
SQLSTATE: 40P01

for attempt in 1..3:
    try:
        BEGIN;
        ... the two UPDATEs ...
        COMMIT;
        break                      # success
    except DeadlockError:          # SQLSTATE 40P01 / MySQL 1213
        ROLLBACK;
        sleep(random_backoff())    # then try the whole txn again

A query’s speed is decided by two schedulers and the physics of a disk, all of which we have studied. First, the two schedulers. The database has its own notion of scheduling — which worker runs which query, how many parallel workers a big scan gets — and underneath it the kernel’s CPU scheduler (Linux’s CFS, from the scheduling chapters) decides which of those OS threads actually gets a core. The two must cooperate: give the database more parallel workers than the machine has cores and you do not get more speed, you get context-switch thrashing as the kernel scheduler juggles threads that are all fighting for the same CPUs — the classic over-subscription problem we studied, now expressed as max_parallel_workers set too high.

Second, and often dominant, is I/O shape: sequential versus random, the distinction from the disks-and-SSDs chapter. This is why storage-engine design is really a bet about I/O. A B-tree (Postgres’ default, InnoDB’s clustered index) keeps data sorted for fast lookups and range scans, but updates scatter writes randomly across the tree — random I/O, the slow kind on any medium and murderous on a spinning disk. An LSM-tree (RocksDB, Cassandra) makes the opposite bet: buffer writes in memory, then flush them as one big sorted run — turning random writes into sequential writes, which is why LSM engines excel at write-heavy workloads. The query planner reasons about exactly this when it chooses between an index scan (few random reads) and a sequential scan (many ordered reads): on real hardware a sequential scan of many pages can beat an index scan that would cause thousands of random seeks, and that trade is encoded in the planner’s cost constants.

Finally, memory tuning for databases is applied virtual-memory knowledge, and two settings surprise people. Transparent Huge Pages (THP) — the kernel automatically promoting 4 KB pages to 2 MB ones — is widely recommended OFF for databases, because its background defragmentation causes latency spikes that hurt the low, predictable latency a DB wants; instead you allocate explicit HugePages for the buffer pool to shrink the page tables and TLB pressure the paging chapters warned about. And on a multi-socket server, NUMA matters: if the buffer pool lives in memory attached to socket 0 but the query runs on socket 1, every access pays the cross-node penalty from the multiprocessor chapter. So DBAs pin the database to a NUMA node (or interleave memory deliberately) so its threads and its RAM sit on the same node — non-uniform memory access made concrete.

EXPLAIN SELECT * FROM events WHERE ts > now() - interval '1 day';

-- Seq Scan on events  (cost=0.00..21520.00 rows=980000 width=64)
--   Filter: (ts > ...)
-- ^ planner chose a SEQUENTIAL scan: the query touches most of the
--   table, and reading pages in order beats a million random
--   index seeks. random_page_cost vs seq_page_cost encode the bet;
--   lower random_page_cost on SSDs, where random I/O is cheaper.

# Transparent Huge Pages OFF (latency spikes hurt DBs)
$ echo never > /sys/kernel/mm/transparent_hugepage/enabled

# Explicit HugePages for the buffer pool (smaller page tables, less TLB miss)
$ sysctl -w vm.nr_hugepages=4200

# Pin the DB to one NUMA node so threads + buffer pool share local RAM
$ numactl --cpunodebind=0 --membind=0 postgres -D /var/lib/pgdata

Step all the way back. We began this course with a simple promise: to replace "it just works" with "I know exactly what the OS is doing". We started from what an operating system even is — the referee between programs and hardware, and the guarded system-call doorway into the kernel. We watched a program become a process, saw threads share an address space, and let the scheduler decide who runs. We fought race conditions with locks and semaphores, and learned how deadlock arises and how to break it. We built the illusion of virtual memory, traced pages through the MMU and the page cache, and pushed data down through fsync and journaling to survive a crash. And in this final chapter, every one of those ideas walked back on stage wearing a database uniform.

That is the real lesson, and it is bigger than databases. The database is only the clearest example of a universal truth: every system you build rides on the operating system’s mechanisms, whether you look at them or not. Your web server’s throughput is a scheduling and syscall-cost story. Your container is namespaces and cgroups — process isolation and resource limits — wearing a friendly name. Your cache is a page-replacement policy. Your message queue’s durability is somebody’s fsync. The stack goes app → framework → runtime → database → kernel → hardware, and each layer is quietly spending the mechanisms of the layer beneath it.

• ▸When a service is slow, you no longer shrug — you ask whether it is CPU scheduling, lock contention, page-cache misses, or fsync latency, and you can tell which.
• ▸When you choose Postgres or MySQL, a B-tree or an LSM store, you are choosing a point on trade-offs — isolation vs sharing, random vs sequential I/O — you now understand from first principles.
• ▸When you size a connection pool, a buffer pool, or a huge-page reservation, you are tuning the exact OS resources this course made visible.
• ▸When the deadlock error fires at 3 a.m., you read the wait-for cycle, add a retry, fix the lock ordering, and go back to sleep.

This is what separates guessing from engineering. Two developers can hit the same slow query or the same mysterious stall; one restarts the server and hopes, the other reasons about the layer underneath and actually fixes it. The difference between them is not talent — it is knowing what the machine is really doing. That knowledge does not go stale when a framework does. The languages, the databases, and the clouds will keep changing; processes and threads, scheduling, locks and deadlock, virtual memory, and durable I/O will still be underneath all of it, doing the same jobs they have done for fifty years.