Re: why do you apply undo before redo?

From: Wayne Warren <>
Date: Tue, 20 Apr 2004 13:13:38 GMT
Message-ID: <6m9hc.86418$>

"Dan" <> wrote in message news:0x6hc.24485$
> "Wayne Warren" <> wrote in message
> news:WWTgc.85993$
> > I'm not sure that the book is correct. I wrote a transaction processing
> > system (released on 1993 as Velocis Database Server, now called Birdstep
> > Server) which performs redo operations just prior to undo operations. I
> can
> > assure you that in practice it works.
> >
> > If transactions have maintained proper Isolation (the "I" in ACID) from
> one
> > another, then the order of redo/undo should be irrelevant.
> But we still have to worry about getting the database to a consistent
> regardless of active interleaving at time of failure. The use of caches
> means that some commited transactions might not have been written to disk,
> or in other cases, parts of uncompleted transactions did get written to
> and need to be undone. Though there might be interleaving across
> transactions at the time of failure, the DBMS doesn't need to consider
> of these transactions if they were propery persisted. Thus some
> serializable schedule might no longer apply.
> - Dan
Again I can speak from my experience, and not about Oracle. The mechanisms used by RDM Server are checkpoints (controlled, safe buffer flushes to disk) and a change log (sync'ed to disk to commit every transaction). The change log is *always* up to date, but the database files are only as recent as the latest checkpoint, which could have been seconds or hours ago.

The checkpoint occurs at time T1 and the crash at T2. There are four positions that transactions may have among T1 and T2:

1) Starts before T1, active at T2. -UNDO
2) Starts before T1, committed before T2. -REDO
3) Starts after T1, committed before T2. -REDO
4) Starts after T1, active at T2. -nothing

The recovery must UNDO all uncommitted changes that existed in the last checkpoint (T1). It must REDO all committed changes that occurred after T1. The change log holds all of the clues. It shows when the checkpoint occurred, and can determine which transactions need to be completed since T1 or rolled back from T1. So from the list above, REDO's are applied for 2 and 3 (known to be committed) from T1 to commit point, and UNDO's are applied for 1 backward from T1. Position 4 is ignored because none of the changes were ever checkpointed.

Atomicity and Durability are achieved and maintained through this recovery process. Isolation was maintained while the system was operational through locking mechanisms. Because of that, the recovery process does not need to be concerned about the ordering of UNDO and REDO. Ours does REDO first.

The above will be true for any system where a checkpoint occurrs at a single point in time. If this is not the case, things become much more complicated.

> > specifics may dictate the order, but the transaction recovery concept
> > not.
> >
> > "Ryan" <> wrote in message
> > news:_Ulgc.4499$uF3.1441_at_lakeread04...
> > > I'm reading a generic database textbook and it states that when
> databases
> > > are recovering undo is applied before redo. It doesn't say why. Does
> > anyone
> > > know?
> > >
> > >
> >
> >
Received on Tue Apr 20 2004 - 15:13:38 CEST

Original text of this message