Reliable Storage - Operating Systems: Principles and Practice - page 411

Undo logging
Although transactions are often implemented with redo logging in which updates and
the commit are written to the log and then the updates are copied to their final locations,
transactions can also be implemented with undo logging.
To update an object, a transaction first writes the old version of the object to the
log. It then writes the new version to its final storage location. When the transaction
completes, it simply appends commit to the log. Conversely, if the transaction rolls back,
the updates are undone by writing the old object versions to their storage locations.
The recovery process takes no action for committed transactions it finds in the log,
but it undoes uncommitted transactions by rewriting the original object versions stored
in the log.
Undo logging allows writes to objects to be sent to disk when they are generated and
requires them to be stored on disk before a transaction is committed. This pattern is
similar to update-in-place approaches, so in some cases it may be easier to add undo
logging than redo logging to legacy systems. On the other hand, for storage systems
like disks whose sequential bandwidth dominates their random I/O performance, undo
logging may require more random I/Os before a transaction is committed (hurting la-
tency) and it may give up chances to improve disk-head scheduling by writing large
numbers of transactions' updates as a batch.
Undo/redo logging stores both the old and new versions of an object in the log. This
allows updated objects to be written to their final storage locations whenever conve-
nient, whether before or after the transaction is committed. If the transaction rolls back,
any modified objects can be restored to the proper state, and if the system crashes, any
committed transactions can have their updates redone and any uncommitted transac-
tions can have their updates undone.
from the location indicated by the persistent log-head pointer.
As long as the records are intact, recovering from the per-
sistent log-head pointer rather than the volatile one may
waste some work, but it will not affect correctness.
Ordering is essential. It is vital to make sure that all of a transaction's
updates are on disk in the log before the commit is, that the commit is on
disk before any of the write-backs are, and that all of the write-backs are
before a transaction's log records are garbage collected.
In Linux, an application can call sync() or fsync() to tell the operating
system to force buffered writes to disk. These calls return only once the
updated blocks are safely stored. Within the operating system, a request
can be tagged with a BIORWBARRIER tag, which ensures that all preceding
writes and no subsequent ones are stored to disk before the tagged request
is.