Transaction Management in the R* Distributed Database Management System – Part II

~ Adrian Colyer

Transaction Management in the R* Distributed Database Management System – Mohan et al. 1986

This is part 7 of a 7 part series on (database) ‘Techniques Everyone Should Know.’ It also the second of two posts examining this paper.

Yesterday we looked at the base two-phase commit protocol, today I’ll examine the presumed abort and commit optimisations.

Presumed Abort

Recall that in the standard 2PC protocol if a recovery process finds no information about a transaction, it aborts that transaction.

A careful examination of this scenario reveals the fact that it is safe for a coordinator to ‘forget’ a transaction immediately after the decision to abort it (e.g. by receiving a NO VOTE) and to write an abort record.

This means that:

  • The abort record need not be forced (both by the coordinator and each of the subordinates)
  • No ACKs need to be sent by subordinates for aborts
  • The coordinator need not record the names of the subordinates in the abort records, nor write an end record after an abort record.
  • If the coordinator notices the failure of a subordinate while attempting to send an ABORT to it, the coordinator does not need to hand the transaction over to the recovery process. It will let the subordinate find out about the abort when the recovery process of the subordinate’s site sends an inquiry message.

We can do even better if we take advantage of completely or partially read-only transactions. A partial read-only transaction is one where one or more of the processes involved do not perform any updates, yet others do. We don’t need to know of the read-only status in advance. In addition to the YES VOTE and NO VOTE of the base protocol, we add a READ VOTE:

  • If a subordinate receives a prepare and it has not done any updates, it sends a READ VOTE, releases its locks, and ‘forgets’ the transaction. No log records are written – it makes no difference to it whether the transaction is aborted or committed.
  • The coordinator does not send any COMMIT or ABORT messages to participants that sent a READ VOTE.

If the coordinator is read-only and only receives READ VOTEs then there will not be a second phase to the protocol, and the coordinator also writes no log records.

The set of refinements discussed so far consitute the Presumed Abort protocol.

The name arises from the fact that in the no information case the transaction is presumed to have aborted, and hence the recovery process’s response to an inquiry is an ABORT.

Presumed Commit

Since most transactions are expected to commit, it is only natural to wonder if, by requiring ACKs for ABORTS, commits could be made cheaper by eliminating the ACKs for COMMITS. A simplistic idea that comes to mind is to require that ABORTS be acknowledged, while COMMITS need not be, and also that abort records be forced while commit records need not be by the subordinates. The consequences are that, in the no information case, the recovery process responds with a COMMIT when a subordinate inquires. There is, however, a problem with this approach…

Consider a coordinator that has sent out PREPARE messages and is still waiting for all of the votes to come back. A subordinate sends a YES VOTE and enters the prepared state. The coordinator then crashes. At this point the coordinator will have written no log records. When the coordinator’s site recovers it will therefore find no information about the transaction and hence abort and ‘forget’ it. But when the subordinates recovery process inquires, upon finding no information it would be sent a COMMIT message, leading to inconsistency.

To solve this the coordinator needs to record the names of its subordinates safely before sending any PREPARE messages. It does this by force-writing a collecting record. Then when a coordinator aborts on recovery it will know who to inform (and get ACKs) about the abort.

The coordinator modifications to the Presumed Abort protocol in total are:

  • Force-writing a collecting record before sending PREPARE
  • Force-writing abort records (and commit records for a root process)
  • Requiring ACKs for ABORTs, but not for COMMITs.
  • Writing an end record only after an abort record

Subordinates force-write only abort records, and not commit records. They ACK only ABORTs, and not COMMITs.

On restart, if the recovery process finds for some transaction a collecting record but no following records, it follows the abort protocol. In the no information case, it responds to an inquiry with a COMMIT.

These modifications gives us the Presumed Commit protocol. The name arises from the fact that in the no information case the transaction is presumed to have committed and hence the response to an inquiry is a COMMIT.

Performance assessment

We can compare the performance of the 2P, PA, and PC protocols when committing update and read-only transactions by considering how many messages are sent, how many log records are written, and how many of those log records are forced. For a standard two level process tree we get the following:

Two-phase

For both update and read-only transactions we have the following:

  • Coordinator writes two log records, one of which is forced, and sends two messages to each subordinate.
  • Subordinate writes two log records, both forced, and sends two messages to the coordinator.

Presumed Abort

For an update transaction:

  • Coordinator writes two log records, one of which is forced, and sends two messages to each YES VOTing participant, and one message to each READ VOTing participant.
  • Subordinate writes two log records, both forced, and sends two messages to the coordinator (as per two-phase)

For a read-only transaction:

  • Coordinator does not write any log records and sends only one message
  • Subordinate does not write any log records and sends only one message

Presumed Commit

For an update transaction:

  • Coordinator writes two log records, both forced, and sends two messages to each YES VOTing participant, and one message to each READ VOTing participant.
  • Subordinate writes two log records, only one of which is forced, and sends one message to the coordinator

For a read-only transaction:

  • Coordinator does not write any log records and sends only one message
  • Subordinate does not write any log records and sends only one message

Comparison

Presumed Abort is better than or equal to 2P under all circumstances. PA also does better than PC in the case of completely read-only transactions (and also in the case of partially read-only transactions in which only the coordinator does any updates.

For transactions with only one update subordinate, PA and PC are equal in terms of log writes, but PC saves one message (an ACK) over PA. For a transaction with n > 1 update subordinates both PA and PC require the same number of records to be written, but PA will force n-1 times whereas PC wil not. PA will also send n extra ACK messages.