Read an Excerpt
Chapter 15: Recovery System
A computer system, like any other device, is subject to failure. There is a variety of causes of such failure, including disk crash, power failure, software error, a fire in the machine room, or even sabotage. In each of these cases, information may be lost. Therefore, the database system must take actions in advance to ensure that the atomicity and durability properties of transactions, introduced in Chapter 13, are preserved, in spite of such failures. An integral part of a database system is a recovery scheme that is responsible for the restoration of the database to a consistent state that existed prior to the occurrence of the failure.15.1 Failure Classification
There are various types of failure that may occur in a system, each of which needs to be dealt with in a different manner. The simplest type of failure to deal with is one that does not result in the loss of information in the system. The failures that are more difficult to deal with are those that result in loss of information. In this chapter, we shall consider only the following types of failure:
- Transaction Failure. There are two types of errors that may cause a transaction to fail:
- Logical error. The transaction can no longer continue with its normal execution, owing to some internal condition, such as bad input, data not found, overflow, or resource limit exceeded.
- System error. The system has entered an undesirable state (for example, deadlock), as a result of which a transaction cannot continue with its normal execution. The transaction, however, can be reexecuted at a later time.
- System crash. There is a hardwaremalfunction, or a bug in the database software or the operating system, that causes the loss of the content of volatile storage, and brings transaction processing to a halt. The content of nonvolatile storage remains intact, and is not corrupted.
The assumption that hardware errors and bugs in the software bring the system to a halt, but do not corrupt the nonvolatile storage contents, is known as the fail-stop assumption. Well-designed systems have numerous internal checks, at the hardware and the software level, which bring the system to a halt when there is an error. Hence, the fail-stop assumption is a reasonable one.
- Disk failure. A disk block loses its content as a result of either a head crash or failure during a data transfer operation. Copies of the data on other disks, or archival backups on tertiary media, such as tapes, are used to recover from the failure.
To determine how the system should recover from failures, we need to identify the failure modes of those devices used for storing data. Next, we must consider how these failure modes affect the contents of the database. We can then propose algorithms to ensure database consistency and transaction atomicity despite failures. These algorithms are known as recovery algorithms, although they have two parts:
1. Actions taken during normal transaction processing to ensure that enough information exists to allow recovery from failures.
2. Actions taken following a failure to recover the database contents to a state that ensures database consistency, transaction atomicity, and durability.
15.2 Storage Structure
As we saw in Chapter 10, the various data items in the database may be stored and accessed in a number of different storage media. To understand how to ensure the atomicity and durability properties of a transaction, we must gain a better understanding of these storage media and their access methods.
15.2.1 Storage Types
There are various types of storage media; they are distinguished by their relative speed, capacity, and resilience to failure.
- Volatile storage. Information residing in volatile storage does not usually survive system crashes. Examples of such storage are main memory and cache memory. Access to volatile storage is extremely fast, both because of the speed of the memory access itself, and because it is possible to access any data item in volatile storage directly.
- Nonvolatile storage. Information residing in nonvolatile storage survives system crashes. Examples of such storage are disk and magnetic tapes. Disks are used for online storage, whereas tapes are used for archival storage. Both, however, are subject to failure (for example, head crash), which may result in loss of information. At the current state of technology, nonvolatile storage is slower than volatile storage by several orders of magnitude. This distinction is the result of disk and tape devices being electromechanical, rather than based entirely on chips, as is volatile storage. In database systems, disks are used for most nonvolatile storage. Other nonvolatile media are normally used only for backup data.
- Stable storage. Information residing in stable storage is never lost (never should be taken with a grain of salt, since theoretically never cannot be guaranteed - for example, it is possible, although extremely unlikely, that a black hole may envelop the earth and permanently destroy all data!). Although stable storage is theoretically impossible to obtain, it can be closely approximated by techniques that make data loss extremely unlikely. Stable-storage implementation is discussed in Section 15.2.2.
The distinctions among the various storage types are often less clear in practice than in our presentation. Certain systems provide battery backup, so that some main memory can survive system crashes and power failures. Alternative forms of nonvolatile storage, such as optical media, provide an even higher degree of reliability than do disks.
15.2.2 Stable-Storage Implementation
To implement stable storage, we need to replicate the needed information in several nonvolatile storage media (usually disk) with independent failure modes, and to update the information in a controlled manner to ensure that failure during data transfer does not damage the needed information.
Recall (from Chapter 10) that RAID systems guarantee that the failure of a single disk (even during data transfer) will not result in loss of data. The simplest and fastest form of RAID is the mirrored disk, which keeps two copies of each block, on separate disks. Other forms of RAID offer lower costs, but at the expense of lower performance.
RAID systems, however, cannot guard against data loss due to disasters such as fires or flooding. Many systems store archival backups of tapes off-site to guard against such disasters. However, since tapes cannot be carried off-site continually, updates since the most recent time that tapes were carried off-site could be lost in such a disaster. More secure systems keep a copy of each block of stable storage at a remote site, writing it out over a computer network, in addition to storing the block on a local disk system. Since the blocks are output to a remote system as and when they are output to local storage, once an output operation is complete, the output is not lost, even in the event of a disaster such as a fire or flood.
In the remainder of this section, we discuss how storage media can be protected from failure during data transfer. Block transfer between memory and.....