Information Technology Reference
In-Depth Information
RAID), and rely on software that to detect failures soon after they occur
and to repair failures qucikly (e.g., background processes that regularly
attempt to read all stored data and algorithms that parallelize recovery
when a device failes.) Systems that fail to properly use these techniques
may be significantly less reliable than expected.
14.1
Transactions: Atomic updates
When a system needs to make several updates to nonvolatile storage, and a crash
occurrs, some of those updates may be stored and survive the crash and others
may not. Because a crash may occur without warning, storage systems and
applications need to be constructed so that no matter when the crash occurs,
the system's nonvolatile storage is left in some sensible state.
This problem occurs in many contexts. For example, if a crash occurs while
you are installing an update for a suite of applications, upon recovery you would
like to be able to use either the old version or the new version, not be confronted
with an mishmash of incompatible programs. For example, if you are moving
a subdirectory from one location to another when a crash occurs, when you
recover you want to see the data in one location or the other; if the subdirectory
disappears because of an untimely crash, you will be (justifiably) upset with the
operating system designer. Finally, if a bank is moving $100 from Alice's account
to Bob's account when a crash occurs, it wants to be certain that upon recovery
either the funds are in Alice's account and records show that the transfer is still
to be done or that the funds are in Bob's account and the records show that
the transfer has occurred.
This problem is quite similar to the critical section problem in concurrency.
In both cases, we have several updates to make and we want to avoid having
anyone observe the state in an intermediate, inconsistent state. Also, we have
no control when other threads might try to access the state in the first case or
when a crash might occur in the second|we must develop a structured solution
that works for any possible execution. The solution is similar, too; we want to
make the set of updates atomic. But, because we are dealing with nonvolatile
storage rather than main memory, the techniques for achieving atomicity differ
in some significant ways.
Transactions extend the concept of atomic updates from memory to stable
storage, allowing systems to atomically update multiple persistent data struc-
tures.
14.1.1
Ad hoc approaches
Until the mid 1990's many le systems used ad hoc approaches to solving the
problem of consistently updating multiple on-disk data structures.
