Other Kinds of Logging (Redo & Undo/Redo)

Redo Logging

Logs activities with the goal of restoring committed transactions (ignoring incomplete transactions).

Log Records:

Same records as before and…
New meaning of <T, X, v>:
- Transaction T has updated the value of database item $X$ and the new value of $X$ is $v$.
  - Direct response to write(X)
  This happens before $X$ is changed on disk.

Redo logging has the two following fundamental principles:

<COMMIT t> occurs in the log only when the log contains complete information on $T$.
<COMMIT t> doesn’t occur in the log when $T$ hasn’t written anything to disk.

There is also the following syntax:

Time	Transaction	$X$ (Local)	$Y$ (Local)	$X$ (Buffer)	$Y$ (Buffer)	$X$ (Database)	$Y$ (Database)	Log Record Written
0						1	10	`<START T>`
1	read(X)	1		1		1	10
2	X := X * 2	2		1		1	10
3	write(X)	2		2		1	10	`<T, X, 1>`
4	read(Y)	2	10	2	10	1	10
5	Y := Y * 2	2	20	2	10	1	10
6	write(Y)	2	20	2	20	1	10	`<T, Y, 10>`
7								`<COMMIT T>`
8	flush_log							(Log buffer is written to disk.)
9	outcom(X)	2	20	2	20	2	10	($X$ is written from buffer to database.)
10	outcom(Y)	2	20	2	20	2	20	($Y$ is written from buffer to database.)

This is essentially the reverse of undo logging:

Identify all the transactions with a COMMIT log record.
Traverse the log from first to the last item.
If we see <T, X, v> and $T$ has a COMMIT log record, then change the value of $X$ on disk to $v$.
For each incomplete transaction $T$, write <ABORT T> into the log on disk.

This combines the atomicity and durability of undo and redo logging.

Log Records:

Same as before but replace <T, X, v>.
<T, X, v, w> - Transaction $T$ has updates the value of database item $X$, and the old and new values of $X$ are $v$ and $w$ respectively.

Write all log records for all updates to database items first.
Then write updates to disk.
<COMMIT T> can then be written to disk before or after all change have been written to disk.

Recovery needs to process the log in both directions.

Consider the following schedule that needs to be logged using undo/redo logging where:

We can put this in the following table:

Time	Transaction $T_1$	Transaction $T_2$	Local $T_1$ $X$	Local $T_1$ $Y$	Local $T_2$ $X$	Buffer $X$	Buffer $Y$	Disk $X$	Disk $Y$	Buffer Log
0								1	2	`<START T1>`
1	read(X)		1			1		1	2
2	X := X * 2		2			1		1	2
3	write(X)		2			2		1	2	`<T1, X, 1, 2>`
4			2			2		1	2	`<START T2>`
5		read(X)	2		2	2		1	2
6	read(Y)		2	2	2	2	2	1	2
7		X := X * 3	2	2	6	2	2	1	2
8		write(X)	2	2	6	6	2	1	2	`<T1, X, 2, 6>`
9	Y := X + Y		2	4	5	6	2	1	2
10	write(Y)		2	4	6	6	4	1	2	`<T1, Y, 2, 4>`
11			2	4	6	6	4	1	2	`<COMMIT T1>`
12	flush_log		2	4	6	6	4	1	2	(Log is written to disk)
13	output(X)		2	4	6	6	4	6	2
14	output(Y)		2	4	6	6	4	6	4
15			2	4	6	6	4	6	4	`<COMMIT T2>`
16		flush_log	2	4	6	6	4	6	4	(Logs since last flush are written to disk)
17		output(X)	2	4	6	6	4	6	4	No change

Undo ensures atomicity.

We can ensure durability by using force:

This forces the writing of updates to disk before commit.

No force is the opposite of this.
Force is expensive in disk operations.

Redo ensures durability.

We can ensure atomicity by using no steal:

No steal means that uncommitted data may not overwrite committed data on disk.

Steal is not to require this.
No steal is expensive to ensure.

We could ensure atomicity and durability without a log by using no steal and force, however this is:

Hard and expensive to ensure.
- Must write every change to disk made by the transaction while performing the commit.

In practice we use undo/redo as it is cheap and ensures atomicity and durability.