How Postgres Makes Transactions Atomic — brandur.org
brandur.org
Articles
Atoms
Fragments
Newsletter
Sequences
Now
Uses
About
Auto
How Postgres Makes Transactions Atomic
Article
How Postgres Makes Transactions Atomic 🔗
Published
Aug 16, 2017
Location
San Francisco
See comments and reaction on Hacker News .
I'm on X/Twitter at @brandur.
Aug 16, 2017
Managing concurrent access<br>Transactions, tuples, and snapshotsLifetime-aware tuples<br>Snapshots: xmin, xmax, and xip
Beginning a transaction<br>Committing a transactionDurability and the WAL<br>The commit log<br>All sizes of optimization<br>Defensive programming<br>Signaling completion through shared memory<br>Responding to the client
Checking visibilityHint bits
The box's dark walls
Atomicity (in the sense of “ACID”) states that for a series<br>of operations performed against a database, either every<br>one of them commits together, or they’re all rolled back;<br>no in between states are allowed. For code that needs to be<br>resilient to the messiness of the real world, it’s a<br>godsend.
Instead of bugs that make it to production changing data<br>and then leaving it permanently corrupt, those changes are<br>reverted. The long tail of connections that are dropped<br>midway from intermittent problems and other unexpected<br>states while handling millions of requests might cause<br>inconvenience, but won’t scramble your data.
Postgres’s implementation in particular is known to provide<br>powerful transaction semantics with little overhead. And<br>while I’ve used it for years, it’s never been something<br>that I’ve understood. Postgres works reliably enough that<br>I’ve been able to treat it as a black box – wonderfully<br>useful, but with inner workings that are a mystery.
This article looks into how Postgres keeps the books on its<br>transactions, how they’re committed atomically, and some<br>concepts that are key to understanding it all 1.
Managing concurrent access
Say you build a simple database that reads and writes from<br>an on-disk CSV file. When a single client comes in with a<br>request, it opens the file, reads some information, and<br>writes the changes back. Things are mostly working fine,<br>but then one day you decide to enhance your database with a<br>sophisticated new feature,<br>multi-client support!
Unfortunately, the new implementation is immediately<br>plagued by problems that seem to especially apparent when<br>two clients are trying to access data around the same time.<br>One opens the CSV file, reads, modifies, and writes some<br>data, but that change is immediately clobbered by another<br>client trying to do the same.
Data loss from contention between two clients.
This is a problem of concurrent access and it’s addressed<br>by introducing concurrency control. There are plenty of<br>naive solutions. We could ensure that any process takes out<br>an exclusive lock on a file before reading or writing it,<br>or we could push all operations through a single flow<br>control point so that they only run one at a time. Not only<br>are these workarounds slow, but they won’t scale up to<br>allow us to make our database fully ACID-compliant. Modern<br>databases have a better way, MVCC (multi-version<br>concurrency control).
Under MVCC, statements execute inside of a<br>transaction , and instead of overwriting data<br>directly, they create new versions of it. The original data<br>is still available to other clients that might need it, and<br>any new data stays hidden until the transaction commits.<br>Clients are no longer in direct contention, and data stays<br>safely persisted because they’re not overwriting each<br>other’s changes.
When a transaction starts, it takes a snapshot that<br>captures the state of a database at that moment in time.<br>Every transaction in the database is applied in serial<br>order, with a global lock ensuring that only one is being<br>confirmed committed or aborted at a time. A snapshot is a<br>perfect representation of the database’s state between two<br>transactions.
To avoid the neverending accumulation of rows that have<br>been deleted and hidden, databases will eventually remove<br>obsolete data by way of a vacuum process (or in some<br>cases, opportunistic “microvacuums” that happen in band<br>with other queries), but they’ll only do so for information<br>that’s no longer needed by open snapshots.
Postgres manages concurrent access with MVCC. Lets take a<br>look at how it works.
Transactions, tuples, and snapshots
Here’s the data structure that Postgres uses to represent a<br>transaction (from proc.c):
typedef struct PGXACT<br>TransactionId xid; /* id of top-level transaction currently being<br>* executed by this proc, if running and XID<br>* is assigned; else InvalidTransactionId */
TransactionId xmin; /* minimal running XID as it was when we were<br>* starting our xact, excluding LAZY VACUUM:<br>* vacuum must not remove tuples deleted by<br>* xid >= xmin ! */
...<br>} PGXACT;
Transactions are identified with a xid (transaction, or<br>“xact” ID)....