Method and apparatus for incremental undo

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C707S793000, C707S793000, C714S015000

Reexamination Certificate

active

06185577

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to log files in a database management system, and more specifically to a method and apparatus for incrementally applying an undo record during transaction recovery or rollback.
BACKGROUND OF THE INVENTION
In a database management system (DBMS) executing a transaction that updates, deletes or modifies a body of data, the possibility exists for the transaction to fail (e.g., a communication failure) or for the computer system to fail (e.g., a device failure or a power failure). In either event, it is likely that changes made by one or more committed transactions will not yet have been written to disk, and/or that changes made by one or more uncommitted transactions will have been written to disk.
Transaction failures and computer failures are highly undesirable in a DBMS. One reason why failures in a DBMS can be particularly undesirable is because a DBMS can have hundreds or even thousands of users concurrently accessing and updating data. Changes written to disk by uncommitted transactions that fail can corrupt the database by placing the database in an inconsistent state. Similarly, the database can be corrupted by a failure if changes made by a committed transaction are lost before they are written to disk.
Maintaining log files is one method for protecting data from becoming corrupted by the occurrence of failures. A redo log is a record of changes made by transactions. An undo log is a record of how to undo changes made by transactions. Together, the redo log and the undo log assist in recovery of a DBMS after a failure.
FIG. 1
depicts a recovery process
100
that involves two general phases: a “redo” phase and an “undo” phase. Database
102
needs to be recovered (e.g., a power failure occurred). Prior to the failure, two transactions
132
and
136
performed changes to data contained in database
102
. One of those transactions, transaction
132
, committed prior to the failure. Transaction
132
is said to have committed because the change(s) completed and were persistently saved to disk in redo log
112
, even though the changes themselves were not applied to the database
102
. Transaction
136
was also written to redo log
112
, which was persistently saved to disk; it too did not get applied to disk. However, transaction
136
did not commit.
Referring to the state of the DBMS depicted in
FIG. 1
, immediately after the power failure, changes made by committed transaction
132
are not reflected in database
102
. However, changes made by a committed transaction must be durable, which means that they must persist on disk even if a failure occurred.
Redo log
112
fixes part of the problem. The redo log
112
contains a series of redo records that save changes made by statements in each transaction. (The redo log
112
may contain data for multiple transactions.) Redo log
112
is temporarily stored in memory and is saved to disk at a regular interval, called a savepoint, or by explicit or implicit instruction from a user or process (e.g., a redo log runs out of space in memory and must flush the redo to disk).
Redo log
112
contains redo records for changes made by committed transaction
132
and uncommitted transaction
136
. When the database
102
is recovered, the first step in the recovery process is to apply the redo log
112
, specifically, to apply the changes recorded in redo log
112
to database
102
. After the redo log
112
has been applied, the database
102
will look like database
104
, which reflects the changes made by transactions
132
and
136
.
As may be apparent, applying redo log
112
created a problem, specifically, changes made by uncommitted transaction
136
are reflected in database
104
. However, changes made by an uncommitted transaction must be removed from the database after a failure occurs. Uncommitted transactions should not be durable. Thus, the data modified by the changes made by transaction
136
is in an inconsistent state. The undo log
120
is designed to fix this problem.
Undo log
120
comprises one or more rollback segments. For example, segment
122
contains data for undoing the changes made by uncommitted transaction
136
. After the redo phase, an “undo phase” is performed. During the undo phase, the undo log
120
is used to remove from the database
104
changes that were made to the database
104
by uncommitted transactions. Database
106
is a version of database
104
after applying undo log
120
. Notice that changes made by uncommitted transaction
136
are not contained in database
106
.
Thus, the changes made by uncommitted transaction
136
, which were made when redo log
112
was applied in the redo phase can be “rolled back” using undo log
120
in the undo phase. As uncommitted transaction
136
is rolled back, each change made by transaction
136
is undone, one complete undo record at a time, in an opposite order than the order in which the changes were made.
The undo process described above, whereas simple and predictable, has significant drawbacks. For example, each undo record in the undo log
120
comprises an undo header and a single rollback entry (or “change”). Consequently, when rollback entries in the same undo block store similar information in their headers (e.g., same table space, block identifier, etc.) valuable space is wasted in the undo block. Further, valuable processing resources may also be wasted when generating a header for every rollback entry, as well as when reading the header for every rollback entry.
Further still, the undo records are applied to disk one complete undo record at a time, and then removed from the undo block to prevent the change from being applied more than once. This process further taxes valuable processing cycles.
There is a need for an improved method for applying an undo log.
SUMMARY OF THE INVENTION
A method and system for incremental undo is provided. According to one aspect of the techniques described herein, an undo record can correspond to more than one data block. In one embodiment, a process, executing in a database management system, establishes a rollback entry as a current rollback entry. The rollback entry, which was selected from a set of rollback entries in an undo record, corresponds to a change made by a transaction to a data block in the system. The process determines whether the rollback entry has been applied. In one embodiment, this is accomplished by testing a status flag in the undo record.
According to one embodiment, if the rollback entry has been applied to the data block, then the rollback entry is not re-applied. Subsequently, a next rollback entry is established in the undo record and the process repeats. If the rollback entry has not been applied, then undo information from the rollback entry is retrieved from the undo record so the change recorded in the rollback entry may be applied to the data block. A change is generated for the data block based upon the rollback entry and the status flag is set to indicate that the entry has been applied. Subsequently, a next rollback entry corresponding to the data block is retrieved. The process repeats until there are no more rollback entries corresponding to the data block. According to one embodiment, the application of a plurality of rollback entries is performed as a single atomic operation.
An advantage of the techniques described herein is that more than one change can be stored in an undo record. Further, less overhead is used when recording changes in the undo record. Additionally, the undo information takes up less space both in memory and on persistent storage. Further, more than one change may be applied to disk in a single atomic operation. The overall result is a more efficient recovery process.


REFERENCES:
patent: 4498145 (1985-02-01), Baker et al.
patent: 5363473 (1994-11-01), Stolfo et al.
patent: 5481699 (1996-01-01), Saether
patent: 5524205 (1996-06-01), Lomet et al.
patent: 5835698 (1998-11-01), Harris et al.
patent: 5850507 (1998-12-01), Ngai et al.
patent: 5864849 (1999-01-01), Bohannon et al.
patent:

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for incremental undo does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for incremental undo, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for incremental undo will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2585748

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.