DDIA Chapter 7: Transactions

Reading link

This chapter covers database-level ACID, focusing on the levels of the “I” in ACID: the trade-offs of different isolation approaches and how isolation is implemented.

ACID

Atomicity means indivisibility.

It makes a transaction appear to be either before or after its operation. In implementation, this is part of what the “I” handles. If a transaction aborts, atomicity lets the application retry it without other concerns.

Consistency is an application-level property: the data contains no invalid state.

Isolation means concurrently executing transactions do not interfere with one another.

Durability

Store data somewhere safe so it is not lost.

Single-object and multi-object operations

Single-object writes

Atomicity and isolation also apply when a single object changes. For example, suppose you are writing a 20 KB JSON document to a database:

If the network disconnects after the first 10 KB is sent, does the database store an unparsable 10 KB JSON fragment?
If power fails while the database overwrites the previous value on disk, does it end up with a mixture of old and new data?
If another client reads the document during the write, can it see a partially updated value?

Transactions are commonly understood as a mechanism for grouping multiple operations on multiple objects into one unit of execution.

Why multi-object transactions are needed

Without atomicity, error handling becomes much more complex; without isolation, concurrency problems follow.

Handling errors and aborts

Retrying an aborted transaction is a simple and effective error-handling mechanism, but it is not perfect:

Problem	Approach
The transaction may have succeeded, but a network interruption makes it appear to have failed. Retrying can duplicate work.	Deduplicate at the application layer.
Retrying can worsen an error caused by system overload.	Limit retry attempts.
Retrying a permanent failure, such as a constraint violation, is pointless.	Do not retry.
Side effects outside the database may already have occurred even when the transaction aborts.	Consider two-phase commit.
The client may fail during retries, leaving no application responsible for retrying.	No general solution.

Weak Isolation Levels

Concurrency problems (race conditions) arise when a transaction reads data that another transaction is modifying at the same time, or when two transactions try to modify the same data concurrently.

Read Committed

The most basic transaction isolation level is read committed, which provides two guarantees:

When reading from the database, you see only committed data (no dirty reads).
When writing to the database, you do not overwrite another transaction’s uncommitted changes (no dirty writes).

Implementing read committed:

Preventing dirty writes: row-level locks. When a transaction wants to modify a particular object (row or document), it must first acquire that object’s lock and hold it until the transaction commits or aborts.

Preventing dirty reads: one option is to use the same locks, but that harms performance. Most databases keep two versions: the old value and the new value that the lock-holding transaction intends to set. Other reads see the old value before commit and the new value afterward.

Read Uncommitted

It prevents dirty writes, but not dirty reads.

Imagine that a transaction has written data to the database but has not yet committed or aborted. Can another transaction see that uncommitted data? If so, it is a dirty read.

What if a later write overwrites a value written by an earlier uncommitted transaction? That is a dirty write.

Snapshot isolation and repeatable reads

Alice has $1,000 in savings split across two bank accounts, $500 each. A transaction transfers $100 from one account to the other. If she views the balance list during the transaction, she may see the recipient account before the transfer completes ($500) and the source account after it completes ($400). To Alice, her accounts seem to contain only $900—the $100 appears to have vanished.

This anomaly is called a non-repeatable read or read skew. If Alice reads account 1 again when the transaction ends, she sees a different value ($600) from the one in her earlier query. Under read-committed isolation, this is acceptable: each balance Alice saw had indeed been committed when read.

Snapshot isolation: each transaction reads from a consistent snapshot of the database—every value committed when the transaction began. Even if another transaction changes those values later, the transaction sees only the data from that specific point in time.

Implementing snapshot isolation: use multi-version concurrency control (MVCC). A typical implementation gives read committed a separate snapshot per query, while snapshot isolation uses the same snapshot for the entire transaction.

Every table row has a created_by field containing the ID of the transaction that inserted it, and an initially empty deleted_by field. Deleting a row does not immediately remove it; the database marks it deleted by setting deleted_by to the deleting transaction ID. Later, once no transaction can access the deleted data, garbage collection removes marked rows and frees their space.

Visibility rules for a consistent snapshot:

When the read transaction began, the transaction that created the object had committed.
The object is not marked deleted, or, if it is, the deleting transaction had not committed when the read transaction began.

Indexes and snapshot isolation

How do indexes work in a multi-version database?

One option is for an index to point to every version of an object, with index queries filtering versions invisible to the current transaction. When garbage collection removes versions no longer visible to any transaction, it can remove their index entries too.
Each write transaction, or batch of transactions, creates a new B-tree. The tree grown from that root is a consistent database snapshot. There is no need to filter objects by transaction ID because later writes cannot modify an existing B-tree; they can only create a new root. This approach still needs a background process for compaction and garbage collection.

Preventing Lost Updates

Lost updates can occur when an application reads a value from the database, modifies it, and writes the modified value back—a read-modify-write sequence.

Solutions

Atomic writes

Many databases provide atomic update operations, eliminating the need for an application-level read-modify-write sequence. If your logic can be expressed with these operations, that is usually the best solution. For example, the following statement is concurrency-safe in most relational databases:

```sql
UPDATE counters SET value = value + 1 WHERE key = ‘foo’;


- Explicit locking

  - If the database's built-in atomic operations do not provide the needed functionality, another option is for the application to explicitly lock the object to be updated. The application can then perform its read-modify-write sequence, forcing any concurrent transaction that tries to update the same object to wait until the first **read-modify-write sequence** completes.

  - ```sql
    BEGIN TRANSACTION;
    SELECT * FROM figures
    	WHERE name = 'robot' AND game_id = 222
    FOR UPDATE;

    UPDATE figures SET position = 'c4' WHERE id = 1234;
    COMMIT;

The FOR UPDATE clause tells the database to lock every row returned by the query.

Automatic detection
- Another approach is to let them run in parallel; if the transaction manager detects a lost update, it aborts the transaction and forces it to retry its read-modify-write sequence.
Compare-and-set (CAS)
- Permit an update only if the current value has not changed since it was last read. If the current value does not match the previously read value, the update has no effect and the read-modify-write sequence must be retried.

Conflict Resolution and Replication

Because data replicas exist on multiple nodes and data on different nodes may be modified concurrently, additional steps are necessary to prevent lost updates.

A common approach in replicated databases is to let concurrent writes create multiple conflicting versions of a value (also called siblings), then resolve and merge them afterward using application code or special data structures.

Atomic operations work well with replication, especially when they are commutative—that is, they can be applied in different orders on different replicas and still yield the same result. Incrementing a counter and adding elements to a set are commutative operations. This is the idea behind Riak 2.0 data types, which prevent lost updates across replicas: when different clients update a value concurrently, Riak automatically merges those updates.

Write Skew and Phantom Reads

First, imagine this example: you are writing a doctor-shift scheduling program for a hospital. A hospital usually requires several doctors to be on call at once, but the minimum is one doctor on call. A doctor can give up a shift (for example, if they are ill), as long as at least one colleague remains on duty.

Write skew is neither a dirty write nor a lost update, because the two transactions update different objects (Alice’s and Bob’s on-call records). The conflict is less obvious, but it is clearly a race condition: if the two transactions ran one after another, the second doctor could not take leave. The anomalous behavior is possible only when the transactions run concurrently.

A write in one transaction that changes the result of another transaction’s search query is called a phantom read. Snapshot isolation avoids phantoms in read-only queries, but in read-write transactions such as the example above, phantoms can cause particularly difficult write-skew cases.

If the transaction is read-only, snapshot isolation solves the problem. If it also writes, write skew occurs and true serializable isolation is needed.

From the perspective of reads, write skew is a phantom read. From the perspective of writes, it is a lost update.

—from Chong Wang’s notes

Serializable Isolation

Serializable isolation is generally considered the strongest isolation level. It guarantees that even if transactions execute in parallel, the final result is the same as if they had run one at a time without any concurrency. Thus, if transactions work correctly in isolation, the database guarantees they remain correct when run concurrently—in other words, it prevents every possible race condition.

Most databases that provide serializability currently use one of three techniques:

Literally execute transactions serially, in order.
Two-phase locking (2PL), for decades the only viable option.
Optimistic concurrency-control techniques, such as serializable snapshot isolation (SSI).

Literal Serial Execution

Execute only one transaction at a time, in order, on a single thread. This entirely sidesteps detecting and preventing inter-transaction conflicts, and the resulting isolation is exactly the definition of serializability.

Every transaction must be small and fast; one slow transaction delays all transaction processing.
This is limited to cases where the active data set fits in memory. Rarely accessed data can move to disk, but the system becomes very slow if a single-threaded transaction needs to access it.
Write throughput must be low enough for a single CPU core, or transactions must be partitionable into a single partition without cross-partition coordination.
Cross-partition transactions are possible, but their use is heavily constrained.

Two-Phase Locking (2PL)

Two-phase locking is similar to read committed, but imposes stronger locking requirements. As long as there is no write, multiple transactions may read the same object simultaneously. But once an object is written (modified or deleted), exclusive access is required:

If transaction A reads an object and transaction B wants to write it, B must wait until A commits or aborts. (This ensures B cannot change the object unexpectedly underneath A.)
If transaction A writes an object and transaction B wants to read it, B must wait until A commits or aborts.

Implementing Two-Phase Locks

Blocking reads and writes is implemented by adding a lock to every database object. A lock may be in shared mode or exclusive mode. It works as follows:

To read an object, a transaction must first acquire a shared lock. Multiple transactions may hold shared locks at the same time, but if another transaction already holds an exclusive lock, they must wait.
To write an object, a transaction must first acquire an exclusive lock. No other transaction may hold either a shared or exclusive lock simultaneously, so the transaction must wait if the object has any lock.
If a transaction reads and then writes an object, it may upgrade its shared lock to an exclusive one. Upgrading works the same as acquiring an exclusive lock directly.
After acquiring a lock, a transaction must hold it until the transaction ends (commits or aborts). This is the source of the name “two-phase”: acquire locks in the first phase while the transaction executes, then release all locks in the second phase when it ends.

Performance

Performance is poor. This is partly due to the overhead of acquiring and releasing all those locks, but more importantly to reduced concurrency. By design, if two concurrent transactions attempt anything that could lead to a race condition, one must wait for the other to finish.

Predicate Locks

Predicate locks are similar to the shared/exclusive locks described above, but they do not belong to a particular object (such as a table row). They belong to all objects matching a certain search condition.

The key idea is that predicate locks also apply to objects that do not yet exist in the database but may be added in the future (phantoms). If two-phase locking includes predicate locks, the database prevents all forms of write skew and other race conditions, achieving serializable isolation.

Index-Range Locks

Unfortunately, predicate locks perform poorly: if active transactions hold many locks, checking for matching locks can be very expensive. Therefore, most databases using 2PL actually implement index-range locks (also called next-key locking), a simplified approximation of predicate locks.

Serializable Snapshot Isolation (SSI)

Pessimistic and Optimistic Concurrency Control

Two-phase locking is a pessimistic concurrency-control mechanism. It follows the principle that if something might go wrong—as indicated by a lock held by another transaction—it is best to wait until the situation is safe before doing anything. This resembles mutexes used to protect data structures in multithreaded programming.

Serializable snapshot isolation is an optimistic concurrency-control technique. Here, optimistic means not blocking a transaction even when danger is possible, but letting it continue in the hope that everything works out. When a transaction wants to commit, the database checks whether anything bad happened—that is, whether isolation was violated. If so, it aborts the transaction and it must retry. Only serializable transactions may commit.

If there is a great deal of contention (many transactions trying to access the same object), performance is poor because a large fraction of transactions must abort. If the system is already near maximum throughput, the additional load from retried transactions can make it worse.

However, if there is enough spare capacity and contention between transactions is not too high, optimistic concurrency control is often better than pessimistic control. Commutative atomic operations can reduce contention: for example, if multiple transactions increment a counter concurrently, the order of those increments does not matter (as long as the counter is not read within the same transaction), so every concurrent increment can be applied without conflict.

Making Decisions Based on Stale Preconditions

How does a database know whether a query result may have changed? There are two cases to consider:

Detecting reads of stale MVCC object versions (an uncommitted write existed before the read).
Detecting writes that affect earlier reads (a write occurred after the read).

Detecting Reads of Stale MVCC Objects

To prevent this anomaly, the database must track when a transaction ignored another transaction’s writes due to MVCC visibility rules. When the transaction wants to commit, the database checks whether any ignored writes have now committed. If so, the transaction must abort.

Why wait until commit? When a stale read is detected, why not abort the transaction immediately?

If the transaction is read-only, it need not abort because there is no risk of write skew.
The other transaction may abort at commit time or may still be uncommitted, so the read may not ultimately be stale.

Detecting Whether Writes Affect Earlier Reads

When a transaction writes to the database, it must look up in the index other transactions that recently read the affected data. This is similar to acquiring a write lock on the affected key range, but it does not block the writer while those read transactions finish; it merely warns them that the data they read may no longer be current.

Performance of Serializable Snapshot Isolation

As usual, many engineering details affect an algorithm’s real-world performance. One trade-off is the granularity of tracking transaction reads and writes. If a database tracks each transaction’s activity in detail (fine-grained), it can accurately determine which transactions must abort, but bookkeeping overhead can become significant. Coarser tracking is faster but may cause more unnecessary transaction aborts.

The greatest advantage of SSI is that one transaction does not need to block waiting for a lock held by another. As with snapshot isolation, writes do not block reads and vice versa. This design makes query latency more predictable, with fewer variables. In particular, read-only queries can run on a consistent snapshot without any locks, which is very attractive for read-heavy workloads.

Compared with serial execution, SSI is not limited to the throughput of a single CPU core.

Abort rate significantly affects SSI’s overall performance. For example, transactions that read and write data for a long time are likely to conflict and abort, so SSI requires read-write transactions to be as short as possible (long read-only transactions may be fine). For slow transactions, SSI may be less sensitive than two-phase locking or serial execution.

Summary

	Dirty reads	Dirty writes	Non-repeatable reads	Write skew	Phantoms
Read uncommitted	×	×	×	×	×
Read committed	√	√	×	×	×
Snapshot isolation (repeatable read)	√	√	√	×	×
Serializable	√	√	√	√	√