If you look superficially at read-committed isolation, you could be forgiven for thinking that it does everything that a transaction needs to do: it allows aborts (required for atomicity), it prevents reading the incomplete results of transactions, and it prevents concurrent writes from getting intermingled. Indeed, those are useful features, and they’re much stronger guarantees than you can get from a system that doesn’t support transactions.
However, there are still plenty of ways to have concurrency bugs when using this isolation level. For example, Figure 8-6 illustrates a problem that can occur with read-committed isolation.
Say Aaliyah has $1,000 of savings at a bank, split across two accounts with $500 each. A transaction transfers $100 from one of her accounts to the other. If she is unlucky enough to look at her list of account balances in the same moment as that transaction is being processed, she may see one account balance before the incoming payment has arrived (still at $500) and the other after the outgoing transfer has been made (the new balance being $400). To Aaliyah, it now appears as though she has only a total of $900 in her accounts—it seems that $100 has vanished into thin air.
This anomaly is called read skew, and it is an example of a nonrepeatable read: if Aaliyah were to read the balance of account 1 again at the end of the transaction, she would see a different value ($600) than she saw in her previous query. Read skew is considered acceptable under read-committed isolation: the account balances that Aaliyah saw were indeed committed at the time when she read them.
Diagram illustrating a concurrency issue where Aaliyah observes her account balances inconsistently during a transfer transaction, leading to a perceived total of $900 instead of $1000.
Figure 8-6. Read skew: Aaliyah observes the database in an inconsistent state
Note
The term skew is unfortunately overloaded. We previously used it in the sense of an unbalanced workload with hot spots (see “Skewed Workloads and Relieving Hot Spots”), whereas here it means a timing anomaly.
In Aaliyah’s case, this is not a lasting problem, because she will most likely see consistent account balances if she reloads the online banking website a few seconds later. However, such temporary inconsistency is not tolerable in the following, for example:
Backups
Taking a backup requires making a copy of the entire database, which may take hours for a large database. During the time that the backup process is running, writes will continue to be made to the database. Thus, you could end up with some parts of the backup containing an older version of the data and other parts containing a newer version. If you need to restore from such a backup, the inconsistencies (such as disappearing money) become permanent.
Analytical queries and integrity checks
Sometimes you may want to run a query that scans over large parts of the database. Such queries are common in analytics (see “Operational Versus Analytical Systems”), or they may be part of a periodic integrity check that everything is in order (monitoring for data corruption). These queries are likely to return nonsensical results if they observe parts of the database at different points in time.
Snapshot isolation is the most common solution to this problem. The idea is that each transaction reads from a consistent snapshot of the database—that is, it sees all the data that was committed in the database at the start of that. Even if the data is subsequently changed by another transaction, each transaction sees only the old data from that particular point in time.
Snapshot isolation is a boon for long-running, read-only queries such as backups and analytics. It is very hard to reason about the meaning of a query if the data on which it operates is changing at the same time as the query is executing. When a transaction can see a consistent snapshot of the database, frozen at a particular point in time, it is much easier to understand.
Snapshot isolation is a popular feature: variants of it are supported by PostgreSQL, MySQL with the InnoDB storage engine, Oracle, SQL Server, and others, although the detailed behavior varies from one system to the next. Some databases, such as Oracle, TiDB, and Aurora DSQL, even choose snapshot isolation as their highest isolation level. Cloud data warehouses such as BigQuery frequently use snapshot isolation as well, as it provides a point-in-time view of the database for analytical queries.
Multiversion concurrency control
As with read-committed isolation, implementations of snapshot isolation typically use write locks to prevent dirty writes (see “Implementing read-committed”), which means that a transaction that makes a write can block the progress of another transaction that writes to the same row. However, reads do not require any locks. From a performance point of view, a key principle of snapshot isolation is readers never block writers, and writers never block readers. This allows a database to handle long-running read queries on a consistent snapshot at the same time as processing writes normally, without any lock contention between the two.
To implement snapshot isolation, databases use a generalization of the mechanism we saw for preventing dirty reads in Figure 8-4. Instead of two versions of each row (the committed version and the overwritten-but-not-yet-committed version), the database must potentially keep several committed versions of a row, because various in-progress transactions may need to see the state of the database at different points in time. Because it maintains several versions of a row side by side, this technique is known as multiversion concurrency control (MVCC).
Figure 8-7 illustrates how MVCC-based snapshot isolation is implemented in PostgreSQL (other implementations are similar). When a transaction is started, it is given a unique, always-increasing transaction ID (txid). Whenever a transaction writes anything to the database, the data it writes is tagged with the transaction ID of the writer. (To be precise, transaction IDs in PostgreSQL are 32-bit integers, so they overflow after approximately 4 billion transactions. The vacuum process performs cleanup to ensure that overflow does not affect the data.)
Diagram illustrating snapshot isolation implementation using multiversion concurrency control. Each version of a row is tagged with the transaction ID that inserted and, if applicable, the transaction ID that deleted that row.
Figure 8-7. Implementing snapshot isolation using multiversion concurrency control
Each row in a table has an inserted_by field, containing the ID of the transaction that inserted that row into the table. Each row also has a deleted_by field, which is initially empty. If a transaction deletes a row, the row isn’t removed from the database but instead is marked for deletion by setting the deleted_by field to the ID of the transaction that requested the deletion. At a later time, when it is certain that no transaction can any longer access the deleted or overwritten data, a garbage collection (GC) process in the database removes any rows marked for deletion and frees their space.
An update is internally translated into a delete and an insert. For example, in Figure 8-7, transaction 13 deducts $100 from account 2, changing the balance from $500 to $400. The accounts table now contains two rows for account 2: a row with a balance of $500 that was marked as deleted by transaction 13, and a row with a balance of $400 that was inserted by transaction 13.
All the versions of a row are stored within the same database heap (see “Storing Values Within the Index”), regardless of whether the transactions that wrote them have committed. The versions of the same row form a linked list, going either from newest version to oldest or the other way round, so that queries can internally iterate over all versions of a row.
Visibility rules for observing a consistent snapshot
When a transaction reads from the database, transaction IDs are used to decide which row versions it can see and which are invisible. By carefully defining visibility rules, the database can present a consistent snapshot of its contents to the application. This works roughly as follows:
-
At the start of each transaction, the database makes a list of all the other transactions that are in progress (not yet committed or aborted) at that time. Any writes that those transactions have made are ignored, even if the transactions subsequently commit. This ensures that the application sees a consistent snapshot that is not affected by another transaction committing.
-
Any writes made by transactions with a later transaction ID (i.e., which started after the current transaction started, and which are therefore not included in the list of in-progress transactions) are ignored, regardless of whether those transactions have committed.
-
Any writes made by aborted transactions are ignored, regardless of when the abort happened. This has the advantage that when a transaction aborts, we don’t need to immediately remove the rows it wrote from storage, since the visibility rule filters them out. The GC process can remove them later.
-
All other writes are visible to the application’s queries.
These rules apply to both insertion and deletion of rows. In Figure 8-7, when transaction 12 reads from account 2, it sees a balance of $500 because the deletion of the $500 balance was made by transaction 13 (according to rule 2, transaction 12 cannot see a deletion made by transaction 13), and the insertion of the $400 balance is not yet visible (by the same rule).
Put another way, a row is visible if both of the following conditions are true:
-
At the time when the reader’s transaction started, the transaction that inserted the row had already committed.
-
The row is not marked for deletion, or if it is, the transaction that requested deletion had not yet committed at the time when the reader’s transaction started.
A long-running transaction may continue using a snapshot for a long time, continuing to read values that (from other transactions’ points of view) have long been overwritten or deleted. By never updating values in place but instead inserting a new version every time a value is changed, the database can provide a consistent snapshot while incurring only a small overhead.
Indexes and snapshot isolation
How do indexes work in a multiversion database? The most common approach is that each index entry points at one of the versions of a row that matches the entry (either the oldest or the newest version). Each row version may contain a reference to the next-oldest or next-newest version. A query that uses the index must then iterate over the rows to find one that is visible and where the value matches what the query is looking for. When GC removes old row versions that are no longer visible to any transaction, the corresponding index entries can also be removed.
Many implementation details affect the performance of multiversion concurrency control. For example, PostgreSQL has optimizations for avoiding index updates if different versions of the same row can fit on the same page. Some other databases avoid storing full copies of modified rows and store only differences between versions, to save space.
Another approach is used in CouchDB, Datomic, and LMDB. Although they also use B-trees (see “B-Trees”), they use an immutable (copy-on-write) variant that does not overwrite pages of the tree when they are updated but instead creates a new copy of each modified page. Parent pages, up to the root of the tree, are copied and updated to point to the new versions of their child pages. Any pages that are not affected by a write do not need to be copied and can be shared with the new tree.
With immutable B-trees, every write transaction (or batch of transactions) creates a new B-tree root, and a particular root is a consistent snapshot of the database at the point in time when it was created. There is no need to filter out rows based on transaction IDs because subsequent writes cannot modify an existing B-tree; they can only create new tree roots. This approach also requires a background process for compaction and GC.
Snapshot isolation, repeatable read, and naming confusion
MVCC is a commonly used implementation technique for databases, and often it is used to implement snapshot isolation. However, different databases sometimes use different terms to refer to the same thing—for example, snapshot isolation is called “repeatable read” in PostgreSQL and “serializable” in Oracle. In addition, sometimes different systems use the same term but with a different meaning—for example, while in PostgreSQL “repeatable read” means snapshot isolation, in MySQL it means an implementation of MVCC with weaker consistency than snapshot isolation, and IBM Db2 uses “repeatable read” to refer to serializability.
The reason for this naming confusion is that the SQL standard doesn’t have the concept of snapshot isolation, because the standard is based on System R’s 1975 definition of isolation levels and snapshot isolation hadn’t yet been invented then. Instead, it defines repeatable read isolation, which looks superficially similar to snapshot isolation. PostgreSQL calls its snapshot isolation level repeatable read because it meets the requirements of the standard and so it can claim standards compliance.
Unfortunately, the SQL standard’s definition of isolation levels is flawed—it is ambiguous, imprecise, and not as implementation-independent as a standard should be. Even though several databases implement repeatable read isolation, there are big differences in the guarantees they provide, despite those guarantees being ostensibly standardized. This isolation level has been formally defined in the research literature, but most implementations don’t satisfy that formal definition. As a result, nobody really knows what repeatable read isolation means.