5 — Databases: indexes, transactions and isolation

The database is usually the hardest part of a system to change and scale. Application servers can be replaced in minutes, but data has to survive everything. A good share of system design is about choosing a data store and using it well.

Relational and non-relational

A relational database, such as PostgreSQL or MySQL, stores data in tables with a fixed schema. Tables link through keys, and SQL can combine them in any way, including ways nobody planned for.

Non-relational databases, often called NoSQL, come in several shapes.

The real difference is what each one is optimized for. A relational database offers flexible queries and strong guarantees. Key-value and wide-column stores offer predictable performance at huge scale, in exchange for designing tables around known queries. Relational databases handle far more scale than their reputation suggests, so they’re a sensible default.

How indexes work

Without an index, finding a row means reading the whole table. An index is a separate sorted structure that maps values to rows, like the index at the back of a book.

Most indexes are B-trees, which keep keys sorted in a shallow tree of pages. A lookup touches only a handful of pages, even across billions of rows, and sorted order makes range queries efficient too.

Indexes aren’t free.

• Every write has to update each index on the table.
• They take disk space and memory.

A composite index covers several columns, and column order matters. An index on (country, city) helps a query on country, or on both, but not one on city alone, for the same reason a phone book sorted by surname doesn’t help with first names.

A covering index holds every column a query needs, so the query never has to read the table.

To see how a database will run a query, EXPLAIN shows the plan, and a full table scan on a large table is the first thing to look for.

ACID transactions

A transaction groups several operations into one unit. Moving money between accounts has to subtract from one and add to the other, and both must happen or neither.

Isolation and its anomalies

Isolation is the subtle one. Full isolation is slow, so databases offer weaker levels, and each permits certain anomalies.

The SQL standard defines four levels. PostgreSQL’s implementation differs from the names in useful ways.

Serializable is safest, but aborted transactions need to be retried, so application code has to be ready for that.

A lost update

This is the anomaly that catches people most often. Two sessions in PostgreSQL each read the stock level and then write a new value, at the default Read Committed level:

CREATE TABLE stock (item text PRIMARY KEY, qty int);
INSERT INTO stock VALUES ('widget', 10);

-- Session A                                 -- Session B
SELECT qty FROM stock;      -- 10
                                             SELECT qty FROM stock;      -- 10
UPDATE stock SET qty = 9;   -- 10 - 1
                                             UPDATE stock SET qty = 9;   -- 10 - 1
SELECT qty FROM stock;      -- 9, two sold, should be 8

The fix is a single statement:

UPDATE stock SET qty = 10;

-- Session A                                 -- Session B
UPDATE stock SET qty = qty - 1;
                                             UPDATE stock SET qty = qty - 1;
SELECT qty FROM stock;      -- 8

Both sessions read 10, and both wrote 9, so one sale vanished. The fix is to let the database do the arithmetic in a single statement. Other fixes are SELECT ... FOR UPDATE, which locks the row, or optimistic locking, where each row has a version number and an update only succeeds if the version hasn’t changed.

Write skew

A hospital requires at least one doctor on call. Two doctors are on call, and each asks to go off call at the same moment. Each transaction checks that another doctor is on call, sees one, and removes itself. Both commit, and nobody is on call. Neither transaction changed the row the other one changed, so a simple row check doesn’t catch it. Serializable isolation does.

Multi-version concurrency control

Many databases, including PostgreSQL, use MVCC. A write creates a new version of a row, and each transaction sees the versions that existed at its snapshot. So readers don’t block writers, and writers don’t block readers. The cost is old versions that need cleaning up, which PostgreSQL does in a process called vacuum.

Connection pools

Opening a database connection is slow, and each one uses server memory. So applications keep a connection pool of open connections and share them.

The pool size sets a hard limit. With 20 connections and 10 ms queries, the maximum is 2,000 queries a second. Larger pools aren’t always better, because the database has to split its CPU and locks among more active queries, and past a point, throughput falls.

Slow queries are especially dangerous here. If queries slow from 10 ms to 1 second, the same pool now handles 20 a second, and every request queues for a connection. This is one of the most common ways a small database slowdown turns into a full outage.

The N+1 problem

An object-relational mapper can hide a costly pattern. Listing 100 posts and their authors can produce one query for the posts and 100 more for the authors, one at a time. On a page, that’s 101 round trips where two would do. The fix is to fetch all the authors in one query, with a join or WHERE id IN (...).

Normalization and denormalization

Normalization stores each fact in one place, which keeps data consistent. Denormalization stores copies to make reads faster, at the cost of keeping them in sync. A social feed that stores a precomputed like count is a typical example.

The usual approach is to normalize first, and denormalize specific things when measurement shows a need.

Schema changes

Changing the schema of a large live table is risky, because some operations lock it. The safe pattern is expand and contract:

1. Add the new column, nullable.
2. Deploy code that writes to both old and new.
3. Backfill old rows in small batches.
4. Deploy code that reads from the new column.
5. Remove the old column.

Each step can be rolled back, and the system keeps running throughout.

Scaling reads and writes

Reads usually scale with read replicas (chapter 10). Writes are harder, and the usual options are a bigger machine, then partitioning (chapter 9).

The takeaway

Indexes make reads fast at a cost to writes. Transactions are a powerful tool, but their default isolation level allows anomalies, and the lost update is the one to watch for. Most database incidents involve a slow query and a full connection pool.