Principles of Transaction-Oriented Database Recovery

liaju

697

31页

4次

2020-06-19

免费下载

Principles of Transaction-Oriented Database Recovery

THEO HAERDER

Fachbereich Informatik, University of Kaiserslautern, West Germany

ANDREAS

REUTER 1

IBM Research Laboratory, San Jose, California 95193

In this paper, a terminological framework is provided for describing different transaction-

oriented recovery schemes for database systems in a conceptual rather than an

implementation-dependent way. By introducing the terms materialized database,

propagation strategy, and checkpoint, we obtain a means for classifying arbitrary

implementations from a unified viewpoint. This is complemented by a classification

scheme for logging techniques, which are precisely defined by using the other terms. It is

shown that these criteria are related to all relevant questions such as speed and scope of

recovery and amount of redundant information required. The primary purpose of this

paper, however, is to establish an adequate and precise terminology for a topic in which

the confusion of concepts and implementational aspects still imposes a lot of problems.

Categories and Subject Descriptors: D.4.5

[Operating Systems]:

Reliability--fau/t

tolerance;

H.1.0

[Models and

Principles]: General; H.2.2

[Database Management]:

Physical

Design--recovery and restart;

H.2.4

[Database Management]:

Systems--

transactmn processing;

H.2.7 [Database Management]: Database Administration--

logging and recovery

General Terms: Databases, Fault Tolerance, Transactions

INTRODUCTION

Database technology has seen tremendous

progress during the past ten years. Con-

cepts and facilities that evolved in the sin-

gle-user batch environments of the early

days have given rise to efficient multiuser

database systems with user-friendly inter-

faces, distributed data management, etc.

From a scientific viewpoint, database sys-

tems today are established as a mature

discipline with well-approved methods and

Permanent address: Fachbereich Informatik, Uni-

versity of Kaiserslautern, West Germany.

technology. The methods and technology

of such a discipline should be well repre-

sented in the literature by systematic sur-

veys of the field. There are, in fact, a num-

ber of recent publications that attempt to

summarize what is known about different

aspects of database management [e.g., As-

trahan et al. 1981; Stonebraker 1980; Gray

et al. 1981; Kohler 1981; Bernstein and

Goodman 1981; Codd 1982]. These papers

fall into two categories: (1) descriptions of

innovative prototype systems and (2) thor-

ough analyses of special problems and their

solutions, based on a clear methodological

and terminological framework. We are con-

Permission to copy without fee all or part of this material is granted provided that the copies are not made or

distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its

date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To

copy otherwise, or to republish, requires a fee and/or specific permission.

Computing

Surveys, Vol. 1•, No. 4, December 1983

288 • T. Haerder and A. Reuter

CONTENTS

INTRODUCTION

1. DATABASE RECOVERY: WHAT IT IS

EXPECTED TO DO

1.1 What Is a Transaction?

1.2 Which Failures Have to Be Anticipated

1.3 Summary of Recovery Actions

2. THE MAPPING HIERARCHY OF A DBMS

2.1 The Mapping Process: Objects and Operations

2.2 The Storage Hierarchy: Implementational

Environment

2.3 Different Views of a Database

2.4 Mapping Concepts for Updates

3. CRASH RECOVERY

3.1 State of the Database after a Crash

3.2 Types of Log Information to Support

Recovery Actions

3.3 Examples of Recovery Techniques

3.4 Examples of Logging

and

Recovery Components

3 5 Evaluation of Logging

and

Recovery Concepts

4. ARCHIVE RECOVERY

5 CONCLUSION

ACKNOWLEDGMENTS

REFERENCES

tributing to the second category in the field

of database recovery. In particular, we are

establishing a systematic framework for es-

tablishing and evaluating the basic con-

cepts for fault-tolerant database operation.

The paper is organized as follows. Sec-

tion 1 contains a short description of what

recovery is expected to accomplish and

which notion of consistency we assume.

This involves introducing the transaction,

which has proved to be the major paradigm

for synchronization and recovery in ad-

vanced database systems. This is also the

most important difference between this pa-

per and Verhofstadt's survey, in which

techniques for file recovery are described

without using a particular notion of con-

sistency [Verhofstadt 1978]. Section 2 pro-

vides an implementational model for data-

base systems, that is, a mapping hierarchy

of data types. Section 3 introduces the key

concepts of our framework, describing the

database states after a crash, the type of

log information required, and additional

measures for facilitating recovery. Crash

recovery is demonstrated with three sample

implementation techniques. Section 4 ap-

plies concepts addressed in previous sec-

tions on media recovery, and Section 5

summarizes the scope of our taxonomy.

1. DATABASE RECOVERY: WHAT IT IS

EXPECTED TO DO

Understanding the concepts of database re-

covery

requires a clear comprehension of

two factors:

• the type of failure the database has to

cope with, and

• the notion of consistency that is assumed

as a criterion for describing the state to

be reestablished.

Before beginning a discussion of these

factors, we would like to point out that the

contents of this section rely on the descrip-

tion of failure types and the concept of a

transaction given by Gray et al. [1981].

1.1

What Is a Transaction?

It was observed quite early that manipulat-

ing data in a multiuser environment re-

quires some kind of isolation to prevent

uncontrolled and undesired interactions. A

user (or process) often does things when

working with a database that are, up to a

certain point in time, of tentative or prelim-

inary value. The user may read some data

and modify others before finding out that

some of the initial input was wrong, inval-

idating everything that was done up to that

point. Consequently, the user wants to re-

move what he or she has done from the

system. If other users (or processes) have

already seen the "dirty data" [Gray et al.

1981] and made decisions based upon it,

they obviously will encounter difficulties.

The following questions must be consid-

ered:

• How do they get the message that some

of their input data has disappeared, when

it is possible that they have already fin-

ished their job and left the terminal?

• How do they cope with such a situation?

Do they also throw away what they have

done, possibly affecting others in turn?

Do they reprocess the affected parts of

their program?

Computing Surveys, Vol. 15, No. 4, December 1983

of 31

免费下载

database

关注

评论