A paper a day keeps the doctor away: Efficient Commit Protocols for the Tree of Processes Model of Distributed Transactions
The two-phase commit
protocol is widely known in the database community, yet despite its notoriety,
finding the paper that first described it proved pretty difficult. The closest
find is the paper about
commit protocols for distributed transactions, which describes the protocol
in detail, and introduces two additional modifications. The paper references
the original publications of the protocol by Gray, Lamport, and others, however
I could not find these notesonline.
The paper describes
the 2PC protocol, both under normal operation, and when failures occur. For
normal operation, when the user decides to commit a transaction, the
coordinator initiates the first phase of the protocol--the prepare phase, by
sending prepare messages to all its subordinates. Each subordinate that can
commit the transaction, writes a prepare log record, and sends an ACK back to
the coordinator. The subordinates that can't commit the transaction, write an
abort log record, andrespond with an
Abort message to the coordinator. An abort message vetoes the transaction, and
so the subordinates that cannot commit the transaction can just abort it, and
forget about it.
coordinator receives all the responses from its subordinates, it initiates the
second phase of the protocol. If all responses were YES votes, the coordinator
moves to the commit phase, where it writes a commit record, and sends a commit
message to all the subordinates.Upon
receiving the commit message, the subordinates write a commit log, send an ACK
to the coordinator, and commit the transaction.
On the other hand if
one subordinate vetoed the transaction, the coordinator moves to the abort
phase, writes an abort record, and sends abort messages to all the subordinates
that are in the prepared state. Each subordinate writes an abort record, sends
an ACK to the coordinator, and aborts the transaction. Once the coordinator
receives all the ACK messages from its subordinates, it writes an end record,
and forgets about the transaction.
In the protocol, all
record writes happen before sending messages, which minimizes communications
with the coordinator when recovering from failure.
With all these
messages going around it is hard to envision that everything will go on
smoothly. The authors then describe the 2PC protocol in the presence of
failures due to site and networking issues. The authors assume that as part of
the recovery, there is a process that reads the logs on stable storage and
accumulates information about the executing transactions at the time of the
crash. This information is used to respond to queries from other sites. The
authors then present a comprehensive state machine of where the transaction
failed during the 2PC protocol, and how to recover from it.For example, if the transaction was in the
prepared state, the recovery process tries to contact the coordinator to see how
to proceed with the transaction. When the recovery site responds, the recovery
process proceeds with handling the Commit/Abort response according to the 2PC
in the absence of failures. If the recovery process finds a transaction without
a commit log, it rolls back the transaction. If it finds a transaction in the
committing/aborting states--when the node is acting as a coordinator, before
the crash--the recovery process periodically tries to send Commit/Abort
messages to the subordinates that have not acknowledged yet. Once all ACKs are
received, the recovery process ends the transaction, and moves along.
The authors then
present modifications of the 2PC commit that optimize the messages sent between
the coordinators, and the subordinates. They observe that in the absence of any
information in the crashed site about a transaction, the correct response is to
abort the transaction. This observation leads to the presumed abort protocol.
The protocol takes advantage of knowing that some subordinates might execute
complete and partial read-only transactions: ones where there is no UNDO/REDO
logs written. For these transactions, we can skip parts of the 2PC protocol.
For example, if a subordinate during a prepare statement finds the transaction
read-only, it issues a READ vote to the coordinator, and forgets the
transaction.The coordinator then does
not include the subordinate in the COMMIT/ABORT phase of the protocol. The
coordinator also skips the second phase of the 2PC protocol if it is READ only,
and gets READ votes from its subordinates. The authors present other states of
the presumed abort protocol, and what messages in the 2PC protocol are skipped.
The authors then
examine what would happen if they eliminated the ACKs to the COMMIT messages.
The observations lead to the presumed commit modification of the 2PC protocol.
In presumed commit, the coordinator behaves similar to the presumed abort
protocol, with minor modifications:
Before sending a prepare
statement, the coordinator collects the names of all subordinates
It writes both abort and
It requires ACKs for aborts,
and not for commits
It writes an end record after
aborts and not for commits
For read only transactions,
it does not write any record
The authors end by
comparing the log I/O performance, and messages sent of the 2PC protocol, vs
Presumed Abort, and Presumed Commit protocols, and describing how to extend the
protocols to multi-level tree of processes, where non-leaf nodes act as coordinators
as well as subordinates, while leaf nodes act as subordinates, with the root
node as a coordinator.