In a single-node transaction, you have a single machine that is in charge of executing the transaction logic, such as the concurrency control algorithms for transaction isolation. If your database uses single-leader replication, the transaction execution happens only on the leader, and the followers simply apply the log of writes that were committed by transactions on the leader.
However, what if multiple nodes are involved in a transaction? For example, perhaps you have a transaction that needs to touch multiple shards of a sharded database, or a global secondary index (in which the index entry may be on a different node from the primary data; see “Sharding and Secondary Indexes”). This is called a distributed transaction.
The algorithms for concurrency control in distributed transactions are broadly similar to those for single-node concurrency control. We discussed serial execution on sharded databases previously; 2PL works in a distributed setting, and for SSI there are distributed serializability checkers. We won’t go into any more detail on these.
Achieving atomicity in a distributed transaction is a whole new challenge, though, and that’s what the rest of this topic will focus on.
For single-node transactions, atomicity is commonly implemented by the storage engine. When the client asks the database node to commit the transaction, the database makes the transaction’s writes durable (typically in a write-ahead log; see “Making B-trees reliable”) and then appends a commit record to the log on disk. If the database crashes in the middle of this process, the transaction is recovered from the log when the node restarts. If the commit record was successfully written to disk before the crash, the transaction is considered committed; if not, any writes from that transaction are rolled back.
Thus, on a single node, transaction commitment crucially depends on the order in which data is durably written to disk: first the data, then the commit record. The key deciding moment for whether the transaction commits or aborts occurs when the disk finishes writing the commit record—before that moment, it is still possible to abort (because of a crash), but after that moment, the transaction is committed (even if the database crashes). Thus, it is a single device (the controller of one particular disk drive, attached to one particular node) that makes the commit atomic.
In a distributed transaction, determining whether a transaction has committed is not so straightforward. For example, when a transaction wants to commit, it is not sufficient to simply send a commit request to all the nodes and independently commit the transaction on each one. It could easily happen that the commit succeeds on some nodes and fails on others (as shown in Figure 8-12), for various reasons:
-
Some nodes may detect a constraint violation or conflict, making an abort necessary, while other nodes are successfully able to commit.
-
Some of the commit requests might be lost in the network, eventually aborting because of a timeout, while other commit requests get through.
-
Some nodes may crash before the commit record is fully written and roll back the transaction on recovery, while others successfully commit it.
Diagram showing a transaction across two databases where User 1's data written to Database 1 fails to commit but is visible in Database 2, leading to inconsistency.
Figure 8-12. When a transaction involves multiple database nodes, it may commit on some and fail on others.
If some nodes commit the transaction but others abort it, the nodes become inconsistent with one another. And once a transaction has been committed on one node, it cannot be retracted again if it later turns out that it was aborted on another node. This is because once data has been committed, it becomes visible to other transactions under read-committed or stronger isolation. For example, in Figure 8-12, by the time user 1 notices that its commit failed on database 1, user 2 has already read the data from the same transaction on database 2. If user 1’s transaction was later aborted, user 2’s transaction would have to be reverted as well, since it was based on data that was retroactively declared not to have existed.
A better approach is to ensure that the nodes involved in a transaction either all commit or all abort and to prevent a mixture of the two. Achieving this is known as the atomic commitment problem.