CSEP 545 Transaction Processing for E-Commerce, Winter 2005                       University of Washington

1/25/05

 

Assignment 4

Preliminaries

·      Read Chapter 8, sections 1-5. There’s a typo in the upper right corner of Figure 8.14 on page 260. The last record, which is labeled “LSN 224, Abort2” should say “LSN 224, Abort1”.

Problem

Consider a system that uses LSN-based operation logging with fuzzy checkpoints and logging of undo’s,  as described in the lecture slides and in Chapter 8 of the textbook. Assume that there is no analysis pass before recovery (so there is no dirty page table in the checkpoint record), and that CLR’s (i.e. undo records) are treated as normal updates and do not splice out a portion of the log (as shown on lecture slide 33).

The following sequence of records is found in a database log after a system failure. Data values, such as before and after images, are omitted. The notation P1/r1 means record r1 on page P1.

LSN        Trans     Operation Type   Page/Record         Trans backpointer

11            T0           Update                                  P0/r0                      null

12            T1           Update                                  P1/r1                      null

13            T2           Update                                  P2/r2                      null

14            T2           Update                                   P0/r3                       13        

15            T2           CLR                                       P0/r3                      14

16            T1           Update                                  P0/r4                      12

17            T0           Update                                  P3/r5                      11

18            checkpoint log record, Active transactions: [T0, 17], [T1,16], [T2, 15]

19            T1           Commit

20            T3           Update                                  P2/r6                      null

21            T0           Update                                  P0/r0                      17

22            T2           CLR                                       P2/r2                      15

23            checkpoint log record, Active transactions: [T0, 21], [T2, 22], [T3, 20]

24            T2           End Abort

25            T3           Update                                  P0/r3                      20

26            T4           Update                                  P2/r2                      null

 

Answer each of the following. In each case, explain briefly why it’s the right answer.

 

a.        Show the log records that must be written by the recovery process, in the proper order, and briefly explain why they must be written. The new log records should have LSNs numbered sequentially starting with 27.

b.       What LSN is on each page after recovery?

c.        Based on what you see in the log, what is the smallest LSN of any log record that might have to be redone?

d.       What pages are fetched from disk by the recovery process?

e.        Does the log give you enough information to tell whether record-level or page-level lock granularity is being used? If so, which is it and how can you tell? If not, explain why not.

f.         Would it have been legal for T2 to have written an End Abort record in between LSN 22 and 23? Why?

g.       Suppose the system failed immediately after LSN 23, so that records 24 – 26 were not written to the log. What log records would be written during recovery in order to finish the abort of T2?               

 

Now suppose we modify the example so that it uses an analysis pass.

Each checkpoint record now includes a dirty page table as follows:

·       In LSN 18, Dirty page table = [P0:15, P1:12, P3:17]

·       In LSN23, Dirty page table = [P0:21, P2: 22]

 

h.       At the time of the second checkpoint, what LSNs could be on each page on disk?

i.         What would it mean if the dirty page table in LSN 23 did not have an entry for P2?