Zero-downtime database migrations and Little's law
A schema change that takes milliseconds can still make a busy PostgreSQL database unavailable, because of the queries that queue behind it while it waits for its lock. Little's law explains the outage, and a simulation shows the queue growing.
Many database migration outages are caused by migrations that are fast to execute but must wait for a lock.
A column addition that takes five milliseconds in development can take a busy production service down for half a minute. The migration itself is not slow. While it waits for its lock, every other query on the table queues behind it. The effect is invisible in development and severe in production, and queueing theory explains it directly.
This article reproduces the effect on PostgreSQL, explains it with Little's law, and presents two mitigations. A simulation shows the effect of traffic, waiting time and pool size.
The relevant literature and documentation are as follows.
Little (1961) proved that for any stable queueing system, regardless of the distribution of arrivals or service times. It is widely used in capacity planning because it requires so few assumptions.
The PostgreSQL documentation ("Explicit Locking") describes the lock modes, which statements take which lock, and the queueing of lock requests; the ALTER TABLE reference documents which forms rewrite the table and which are metadata-only.
Ambler and Sadalage (2006) catalogued database refactorings as small, reversible steps with transition periods. Sato (2014), on Martin Fowler's site, named the general pattern parallel change, also known as expand and contract.
The experiment
On PostgreSQL 16, I created a table with 100,000 rows and ran three sessions:
- A long-running transaction that reads the table and stays open for a few seconds, like a report or a forgotten idle session.
- A migration:
ALTER TABLE orders ADD COLUMN note text. On its own this is a metadata-only change that completes in milliseconds. - Three ordinary queries, each looking up one row by primary key.
The migration needs an ACCESS EXCLUSIVE lock on the table and has to wait for the reporting transaction to finish. The notable effect concerns the ordinary queries. pg_locks showed (output trimmed):
AccessShareLock | granted | begin; select count(*) from orders; ...
AccessExclusiveLock | waiting | alter table orders add column note text;
AccessShareLock | waiting | select count(*) from orders where id=2;
AccessShareLock | waiting | select count(*) from orders where id=1;
AccessShareLock | waiting | select count(*) from orders where id=3;
Each of the three lookups waited 6.0 seconds for a query that normally takes a fraction of a millisecond. They do not conflict with the reporting transaction at all. They conflict with the waiting migration, and PostgreSQL queues lock requests so that a request arriving later does not jump ahead of one already waiting for a conflicting lock. The migration, while not yet executing, blocks every query behind it.
Road traffic shows the same pattern. On a single-lane road, a car waiting to turn across oncoming traffic stops every car behind it, although those cars only want to continue straight ahead and have no conflict with the oncoming traffic. The queue grows as long as the turning car waits, at the rate at which cars arrive.
Little's law applied to a lock
For any stable queueing system, Little's law says the average number of items in the system equals the arrival rate times the average time each spends there:
Apply it to the blocked table. If queries arrive at per second and the migration waits seconds behind a long transaction, then about
queries accumulate. Long before that, the application's connection pool is exhausted: a pool of 100 connections is full after seconds. Externally this appears as a full outage, caused by a change that would have taken five milliseconds.
The same reasoning explains why the risk grows with traffic. Doubling the request rate doubles the queue for the same wait, so a migration that was harmless at night can take the service down at noon.
Mitigation 1: a lock timeout
The simplest mitigation is to limit the wait. In PostgreSQL, lock_timeout makes a statement give up if it cannot obtain its lock in time:
SET lock_timeout = '2s';
ALTER TABLE orders ADD COLUMN note text;
-- ERROR: canceling statement due to lock timeout
In the same experiment with a two-second timeout, the migration failed cleanly, and a query issued immediately afterwards returned in about 12 milliseconds. The worst case is now bounded: queries can wait at most as long as the timeout, so by Little's law the queue is at most about .
A failed migration is then retried, preferably with a randomised backoff. If each attempt fails with probability (the chance of colliding with a long transaction), the number of attempts needed is geometric with mean : even with , two attempts on average.
Mitigation 2: expand and contract
The second mitigation is to avoid changes that need a strong lock for long, by splitting them into small, backward-compatible steps. The expand and contract pattern (also called parallel change) for, say, adding a mandatory column:
- Expand. Add the new column as nullable. Since PostgreSQL 11, adding a column with a constant default is also a metadata-only change, with no table rewrite.
- Migrate. Deploy code that writes the new column, then backfill existing rows in small batches, each in its own short transaction.
- Enforce. Add a constraint
CHECK (note IS NOT NULL) NOT VALID, which is fast, thenVALIDATE CONSTRAINT, which scans the table under a weaker lock that does not block reads or writes. Since PostgreSQL 12, a subsequentSET NOT NULLcan use the validated constraint and skip its own full-table scan. - Contract. Once no code depends on the old structure, remove it in a later release.
Indexes follow the same principle: CREATE INDEX CONCURRENTLY builds an index without blocking writes, at the cost of taking longer and not being allowed inside a transaction block. Changes that rewrite the table, such as most column type changes, are best done by adding a new column and migrating to it.
The figure below simulates the queue. Once a migration is waiting for its lock, the queue behind it grows at the arrival rate, so its peak is λ times the wait; a lock timeout caps the wait and therefore the queue.
Suggested settings:
- Peak traffic. With 500 queries per second and a 30-second transaction ahead of the migration, about 15,000 queries accumulate, and a pool of 100 connections is exhausted after 0.2 seconds.
- Low traffic. Lower the rate to 20 per second. The queue peaks around 600 and the pool still runs out, after five seconds. The same migration is harmless at low traffic only if the pool is larger than λ times the wait.
- Lock timeout. With
lock_timeout = 2s, the peak at 500 per second falls to about 1,000. The pool still fills, but for two seconds instead of thirty, and the migration retries later. - Safe operating range. With the timeout on, adjust the traffic until the peak stays below the pool. With a pool of 100 and a 2-second timeout, that is about 50 queries per second. Above that, combine the timeout with expand-and-contract steps scheduled for quiet periods.
Derivation of λW. While the migration waits for seconds, every query arriving at rate joins the queue and none leaves, so after seconds the queue holds about queries; its peak, when the lock is finally granted, is . More generally, Little's law holds for the long-run averages of any stable system, which is why it also gives the right answer for a series of migrations with different waits. With a lock timeout , the wait is , so the peak is at most . The pool of size is exhausted when , at .
The database should be treated as a queue. For any change, the relevant questions are how long it takes, what waits behind it and how fast that queue grows.
- Set
lock_timeout(and astatement_timeout) in every migration session, and retry with backoff. - Check for long transactions before migrating;
pg_stat_activityshows them, including sessions idle in a transaction. - Prefer many small, reversible steps to one large one. That also makes the change easier to review and to roll back, the same reason I gave for applying only reviewed plans in Terraform as a change-management control.
References
- J. D. C. Little, "A proof for the queuing formula: L = λW", Operations Research, 9(3), 383-387, 1961.
- PostgreSQL Global Development Group, PostgreSQL 16 Documentation, sections "Explicit Locking" and "ALTER TABLE".
- S. W. Ambler and P. J. Sadalage, Refactoring Databases: Evolutionary Database Design, Addison-Wesley, 2006.
- D. Sato, "ParallelChange", martinfowler.com, 2014.