Section 11

Undo-Redo Log-Based Recovery

Based on the undo-redo log shown below, answer the following questions.

LSN	transaction	action	item	old value	new value	olsn
00	T1	begin
10	T1	update	D1	100	70	0
20	T2	begin
30	T1	commit
40	T2	update	D1	70	400	10
50		checkpoint
60	T2	update	D3	“hello”	“howdy”	0
70	T3	begin
80	T3	update	D2	15	70	0
90	T2	commit
100	T3	update	D1	400	55	40
		*crash*

Does this log use logical logging? Why or why not?

Yes, since each log record stores the old log sequence number (olsn), the LSN of the log record corresponding to the data item’s previous value. This allows us to only redo the updates that are necessary based on the value on disk.

However, each update record stores both the old value and the new value, which isn’t necessary. If we were using real logical logging, we would only need to store how to get the new value from the old value (e.g., log record 10 could be stored as “decrement D1 by 30”).

The update records above are idempotent: that is, a given update could be redone more than once and the final value would always be the same. With real logical logging, the records might not be idempotent, so it would be important to only undo or redo an update once.
What other information must be included in log record 50?

The list of active transactions, which in this case is only T2.
At the start of recovery, what are the possible values that D1 could have on disk?

400 (from T2’s update) or 55 (from T3’s update).
At the start of recovery, what are the possible values that D1 could have on disk if we were using undo-only logging?

400 (from T2’s update) or 55 (from T3’s update).
At the start of recovery, what are the possible values that D1 could have on disk if we were using redo-only logging?

70 (from T1’s update) or 400 (from T2’s update).
Do all of the log records shown need to be examined during recovery? Why or why not?

No. We only need to go back to log record 50 — the one describing the checkpoint. In general, we need to go back to the oldest start record for any transaction that needs to be aborted (i.e., a transaction that is listed as active in the checkpoint record but isn’t on the commit list). This allows us to undo any changes made by such transactions.

In this case, the only transaction listed in the checkpoint record is T2, and it’s on the commit list. Because T2 committed, we will never need to undo any of its operations that might’ve occurred before the checkpoint, and thus there’s no need to go any further back.
At the start of recovery, assume that we have the following LSNs associated with the data items on disk:
- D1: 100
- D2: 0
- D3: 60
Given these datum LSNs, trace through the steps taken in the backward and forward passes.
Backward pass. We start with the last log record and work backwards.
- 100: T3 is not on the commit list
  D1’s datum LSN = 100
  LSN of log record = 100
  because the LSNs are equal, we undo this change
  this gives D1 a value of 400 and a datum LSN of 40
- 90: add T2 to the commit list
- 80: T3 is not on the commit list
  D2’s datum LSN = 0
  LSN of log record = 80
  not equal, so no need to undo, because this change didn’t make it to disk
- 70: nothing to do
- 60: T2 is on the commit list, so we skip this record for now
- 50: the only active transaction in the checkpoint record (T2) is on the commit list, so we can stop here
Forward pass. We start at the first record after the checkpoint (60) and work forward.
- 60: T2 is on the commit list
  D3’s datum LSN = 60
  OLSN in log record = 0
  datum LSN != OLSN, so no need to redo, because this change already made it to disk (or was overwritten by a later change)
- 70: nothing to do
- 80: T3 is not on the commit list; skip
- 90: nothing to do
- 100: T3 is not on the commit list; skip
How would this log be different if we had used undo-only logging?

With undo-only logging, we only store the information needed to undo operations (the old values). Our log would not need the “new value” column. During recovery, we’d only need to perform the backward pass.
How would this log be different if we had used redo-only logging?

With redo-only logging, we only store the information needed to redo operations (the new values). Our log would not need the “old value” column. During recovery, we’d only need to perform the forward pass.

Last updated on November 21, 2024.