Transaction recovery and rollback

Question

As I understand:

UNDO: Undoing a write item operation consists of examining its log entry [write_item, T, X, old_value, new_value] and setting the value of item X in the database to old_value. UNDO is always performed in the reverse order from the order in which the operations were written in the log.

REDO: Redoing a write item operation consists of examining its log entry [write_item, T, X, new_value] and setting the value of item X in the database to new_value.

In a transaction recovery algorithm, for example the one outlined in the Q & A Understanding Transaction Recovery

and let's say we have a schedule such as:

R1(X) R2(Y) W1(X) C W2(Y)

where C denotes a crash. According to the algorithm, we should UNDO T1, but REDO T2, since it is still active at the time of crash. But T2 hasn't had any Write operations, so what exactly does an UNDO entail here? Does anything need to actually happen? And where does the concept of a rollback come in? Is that just implicit in an UNDO?

Answer 1

Assuming that R means Read and W means Write, then the work you're proposing is like this:

W1(x) C

That's it. Reads are irrelevant for recovery. And a crash denotes the end, you can't have a write after crash. So the task of recovery is to redo the one write and then undo it, since there is no Commit.

The algorithm is very simple:

• Redo everything, in forward order
• Undo anything not committed, in reverse order, generating a compensating write for every action being undone.

A good explanation is the ARIES paper.

See also How to read and interpret the SQL Server log on my blog.

Answer 2

It depends on the DBMS system being used and the time frame you are trying to examine.

Your question is very simplified and leaves a lot of room for interpretation.

I put your transactions and crashes into a timeline and added one for the CHEKPOINT, because (depending on the DBMS) without a CHECKPOINT no write to disk.

Memory Time Line T1
     R1(X)-----W1(X)
-----1---------1-------------> (t)

Memory Time Line T2
          R2(Y)------W2(Y)
----------2----------2-------> (t)

Checkpoint Time Line (C)
                 Checkpoint
-----------------C-----------> (t)

Crash Time Line CR (X)
                   Crash
-------------------X---------> (t)

If T1 decides to begin a transaction R1(X) and the commits the transaction W1(X) then everything is still in memory. At a certain point in time the DBMS will decide to write the contents of memory to disk (Transaction Log in SQL Server/UNDO - REDO Tablespace in Oracle). The Transaction Log then has knowledge of the transaction that were previously in memory. They are on disk. This includes the start of the transaction T2 with its Read R2(Y)

When the system crashes and no writes can be performed, then everything in memory is lost.

Your disk timeline (TLog / Redo - Undo TS) will look like this at the point of the crash:

Disk Time Line 
     R1(X)------W1(X)
-----1----------1C-----------> (t) [T1]
          R2(Y)--|
----------2------C-----------> (t) [T2]
-----------------C-----------> (t) [Checkpoint]
-------------------X---------> (t) [Crash]

Everything after the CHECKPOINT that couldn't be written to disk is lost and everything that was CHECKPOINT-ed will either have to be COMMIT-ed or UNDO-ne.

The interval at which CHECKPOINTs are issued is controlled by the DBMS and can be modified (e.g. Microsoft SQL Server) by the DBA to prevent data loss.

A crash will end any transactions that were in memory. Any BEGIN transactions that happened after the CHECKPOINT won't be stored on disk and don't have to be UNDO-ne or REDO-ne.

Microsoft SQL Server

Database Checkpoints (SQL Server)

A checkpoint creates a known good point from which the SQL Server Database Engine can start applying changes contained in the log during recovery after an unexpected shutdown or crash.

Configure the recovery interval Server Configuration Option

The recovery interval option defines an upper limit on the time recovering a database should take. The SQL Server Database Engine uses the value specified for this option to determine approximately how often automatic checkpoints to issue automatic checkpoints on a given database.