Distributed Transactions - Part 2

Hello World!

Welcome to the second part of the distributed transaction series. In the first part, we discussed the basics of transactions, the meaning of ACID, and Single-Object and Multi-Object operations. In this part, we will discuss about weak isolation levels and how they work in a distributed setting. We touch upon the concepts of dirty reads, dirty writes, lost updates, write skew, and phantoms.

Weak Isolation Levels

Concurrency issues only come into play when one transaction tries to read the data, i.e., concurrently being modified by another transaction or multiple transactions are trying to modify the same data. Databases have handled this concurrency issue for us by providing transaction isolation. Unfortunately, it has a performance cost, and many databases don’t want to pay it. Therefore, it’s prevalent in databases to provide weak isolation levels that protect against some concurrency issues but not all.

Read Committed

This basic transaction isolation level makes two guarantees

1. When reading from the database, you will only see data that has been committed (no dirty reads)
2. When writing to the database, you will only overwrite data that has been committed (no dirty writes)

No Dirty Reads

Any reads by a transaction only become visible to others when that transaction is committed. Few reasons why preventing dirty reads is helpful.

• If a transaction needs to update several objects, then dirty reads mean that another transaction might see some updates on the object that other transactions may not see
• If a transaction is aborted, any writes it made need to be rolled back. If the database allows dirty reads, that means a transaction may see data that is later rolled back

No Dirty Writes

Transactions running at the read committed level must prevent dirty writes, usually by delaying the 2nd write until the first write transaction has been committed or aborted.

Implementing Read Committed

Row-level locks are the most common way to prevent dirty writes: when a transaction wants to update an object, then first, it has to take a lock on it and keep that lock until the transaction is committed or aborted. Only one transaction can have a lock on an object at one time, and if another transaction wants to modify the same object, it has to wait for the lock to be released by the first transaction.

One option to prevent dirty reads is to use the same row-level locks, but this doesn’t work well in practice as multiple read-only transactions will be blocked by one long-running write transaction, and the response times will shoot up. The slowness of one transaction has a domino effect on other transactions. For this simple reason, most databases for every object that is written remember the old committed value and the new value set by the transaction that currently holds the lock. So when a read transaction comes in, it returns the old value.

Issues with Read Committed

Let’s take an example of a banking app where Rahul has two accounts with Rs. 30,000 each and transfers Rs. 10,000 from one account to another. If he checks the receiving bank account balance immediately while the transaction is still processing, he may see Rs. 30,000 in the receiving bank account and then go on to check the sender account. In the meantime, the transaction processes, so the outgoing bank account shows Rs. 20,000. Rs. 10,000 seems to have disappeared in thin air. This anomaly is known as non-repeatable read or read skew. However, for Rahul, this isn’t a long-lasting problem because he will see consistent account balances if he reloads the app after a few seconds.

Snapshot Isolation

Snapshot Isolation is the most common solution. The idea is that each transaction reads from a consistent snapshot of the database. The transaction sees all the committed data at the start of the transaction, even if concurrently, the data is being modified by another transaction.

Implementing Snapshot Isolation

To prevent dirty writes, write locks are used, but no locks are required for reads. From a performance point of view, a key principle of snapshot isolation is that readers never block writers, and writers never block readers. The database keeps several different committed versions of an object because various in-progress transactions may need to see the state of the database at different points in time. Because the database maintains multiple versions of the object side by side, this technique is known as multi-version concurrency control (MVCC)

The typical approach is that read committed uses a separate snapshot for each query, while snapshot isolation uses the same snapshot for an entire transaction. Here are some visibility rules for observing a consistent snapshot

1. At the start of each transaction, the database makes a list of transactions that are in progress (i.e., not committed nor aborted) at the time. Any writes that those transactions have made are ignored, even if the transactions are committed subsequently.
2. Any writes made by aborted transactions are ignored.
3. Any writes made by transactions with later transaction IDs are ignored, regardless of those transactions being committed.
4. All other writes are visible to the application’s queries.

How do indexes work in a multi-version database? One option is to have the index plainly point to all versions of an object and let it figure out which one is relevant to the current transaction. When old versions are no longer needed, they and their corresponding index entries can be removed. Another approach is to use B-Trees using an append-only/ copy-on-write variant that doesn’t overwrite the pages of the trees 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 latest versions of child pages. This approach requires a background process for compaction and garbage collection.

Preventing Lost Updates

The lost update problem can occur if an application reads some value from the database, modifies it, and writes back the modified value. If two transactions do this concurrently, one of the modifications can be lost because the second write doesn’t include the first modification.

Atomic Write Operations

Atomic operations are usually implemented by taking an exclusive lock on the object when it is read so that no other transaction can read it until the update has been applied. This technique is called cursor stability. Another option is to simply force all atomic operations to be executed on a single thread. Unfortunately, ORM frameworks make it easy to accidentally write code that performs unsafe read-modify-write cycles instead of using atomic operations provided by the database.

Explicit Locking

The application takes an explicit lock on the objects that are going to be updated. Then the application performs a read-modify-write cycle, and if any other transaction tries to concurrently read the same object, it is forced to wait until the first read-modify-write cycle has completed.

BEGIN TRANSACTION

SELECT * FROM people
WHERE city = "Bangalore" AND name LIKE "as%"
FOR UPDATE;

UPDATE people SET city = "Bengaluru";

COMMIT;

The FOR UPDATE clause indicates that the database should take a lock on all rows returned by the query.

Automatically detecting lost updates

Atomic operations and explicit locks are two ways of preventing lost updates. An alternative to both these methods is to allow them to execute in parallel, and if the transaction manager detects a lost update, abort the transaction and force it to retry its read-modify-write cycle. The advantage of this approach is that the database can perform this check efficiently in conjunction with snapshot isolation. This method is less error-prone because you may forget to take a lock or an atomic operation, but detection happens automatically and requires no application code.

Compare-and-set (CAS)

In databases that don’t provide the functionality of transactions, you sometimes find an atomic compare-and-set operation. The purpose of this operation is to avoid lost updates by allowing an update to happen only if the value hasn’t changed since you last read it. If the current value doesn’t match what you previously read, the update has no effect, and the read-modify-write cycle must be retried.

Conflict resolution and replication

Locks and CAS operations assume that there is a single up-to-date copy of the data. Databases with multi-leader or leaderless replication usually allow several writes to happen concurrently and replicate them asynchronously. The common approach is to allow concurrent writes to create several conflicting versions of a value and use application code or special data structure to resolve and merge these versions. Atomic operations can work well in a replicated context, especially if they are commutative.

Write Skew and Phantoms

Write skew is a generalization of the lost update problem. Write skew can occur if two transactions read the same objects and then update some of those objects.

Preventing write skews

Atomic single-object operations don’t help as multiple objects are involved. Automatic detection of lost updates doesn’t help, as write skew can’t be detected automatically. Some databases allow configuring constraints with the help of triggers or materialized views. Try explicitly locking the rows that the transaction depends upon.

Phantom causing write skew

Where a write in one transaction changes the result of a search query in another transaction is called a phantom. Snapshot isolation avoids phantoms in read-only queries.

Parting Words

This is it for part 2 of the series. In the next one, we will discuss about serializability. I will meet you in the next one!

If you liked the blog, then you can support it by buying me a coffee here, sharing on your socials, and following me on X/ Twitter.

References

• Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems by Martin Kleppmann