05-07-2012, 12:46 PM
D-ARIES: A Distributed Version of the ARIES Recovery Algorithm
D-ARIES.pdf (Size: 144.77 KB / Downloads: 41)
Abstract.
This paper presents an adaptation of the ARIES recovery algorithm
that solves the problem of recovery in Shared Disk (SD) database
systems, whilst preserving all the desirable properties of the original algorithm.
Previous such adaptations of the ARIES algorithm have failed
to solve some of the problems associated with SD systems, resulting in
a number of undesirable compromises being made. The most signicant
problem is how to assign log sequence numbers (LSNs) in such a way
that the system is recoverable after a crash. Existing adaptations have
required, among other things, a perfectly synchronised global clock and a
central merge of log data either during normal processing or crash recovery,
which clearly imposes a signicant overhead on the database system.
This adaptation of ARIES removes this requirement entirely.
Introduction
Introduced by Mohan et al. [1], the ARIES (Algorithm for Recovery and Isolation
Exploiting Semantics) algorithm has had a signicant impact on current thinking
on database transaction logging and recovery. It has been incorporated into Lotus
Notes as well as a number of major database management systems (DBMSs) [2].
ARIES, like many other algorithms, is based on the WAL (Write Ahead
Logging) protocol that ensures recoverability of a database in the presence of a
crash. However, ARIES' Repeating History paradigm sets it apart from all other
WAL based protocols. The repeating history paradigm requires, during recovery,
that the database be returned to the same state as it was before the crash
occurred. This aspect of ARIES allows it to support ne granularity locking,
operation locking (i.e. increment and decrement) and partial rollbacks. ARIES
further supports the use of buer managers that use the Steal and No-Force
approach to page replacement [3].
Solutions
The algorithm proposed in this paper addresses the problem of recovery within
a SD system whilst addressing the aforementioned problems. In particular, the
need to have LSNs monotonically increasing across all systems has been removed.
This removes all reliance on clocks and allows the correspondence between LSNs
and the physical location of the corresponding log records to be preserved. The
algorithm also removes any need for the merging of log data (during normal
processing or recovery), but requires that all nodes participate in crash recovery.
ARIES
This section provides a brief overview of the original ARIES algorithm. The
reader is referred to [1] for the details about ARIES and to [9] for an introduction
in the ARIES family of algorithms.
ARIES, like many other algorithms, is based on the WAL protocol that ensures
recoverability of a database in the presence of a crash. All updates to all
pages are logged (e.g. in logical fashion). ARIES uses an LSN stored on each page
to correlate the state of the page with logged updates of that page. By examining
the LSN of a page (called the PageLSN) it can be easily determined which
logged updates are re
ected in the page. Being able to determine the state of a
page w.r.t. logged updates is critical whilst repeating history, since it is essential
that any update be applied to a page once and only once. Failure to respect this
requirement will in most cases result in a violation of data consistency.
Logging
Previous adaptations of the ARIES algorithm require that the LSNs be globally
monotonically increasing across all nodes in the system. This requirement introduces
the problem of how to ensure that the LSNs are monotonically increasing
on a global basis and means that the physical address of a log record can no
longer be inferred from its LSN.
The adaptation of the ARIES algorithm presented here no longer requires
LSNs to be globally monotonically increasing, however it is required that LSNs be
monotonically increasing within each node. This requirement for monotonically
increasing LSNs within a node is not a burden, but rather a benet, since it
allows a direct correspondence between a log record's physical address and logical
address to be maintained.
Conclusions
The algorithm presented in this paper oers an adaptation of ARIES that solves
the problem of recovery in SD database systems. The desirable properties of
ARIES, such as ne granularity locking5, operation locking and partial rollbacks,
have been preserved without imposing signicant overhead on the system.
The original ARIES algorithm relies on the LSNs being globally monotonically
increasing in order to ensure recoverability of the database after a crash. As
such, previous adaptations have sought to ensure that LSNs are monotonically
increasing throughout the SD system rather than resolve this reliance.