Logging (ACID)

acid

Definition

Logging (ACID)

When starting, a transaction $T$ registers itself in the log: $[T\text{start}]$.

When modifying data item $X$ by write $(X,x)$ in transaction $T$:

1. Add log entry with:

• $[T,X,V_{old},V_{new}]$
• transaction’s ID (i.e., $T$)
• data item name (i.e., $X$)
• old value of the item
• new value of the item

2. Write new value of the item

When committing transaction $T$: $[T\text{commit}]$

When aborting a transaction $T$: $[T\text{abort}]$

Example:

Recovery

Available operations:

• Redo: perform the changes to the database again
• Undo: restore database to state prior to execution

Example:

Given a database:

Resource	Value
A	100
B	300
C	5
D	60
E	80

and log records:

1. [ T1, start ]
2. [ T1, B, 300, 400]
3. [ T1, C, 5, 10 ]
4. [ T2, start ]
5. [ T2, E, 80, 480 ]
6. [ T1, A, 100, 560 ]
7. [ T1, commit ]
8. [ T2, A, 560, 570 ]
9. [ T2, D, 60, 530 ]

Phases 1 - REDO:

Start with an empty undo list: $U=\varnothing$:

1. $T1$ started. Accept $T_1$ into undo list: $U=\{T_1\}$.

2. $T_1$ updated $B$ $300\to 400$. Update database:

Resource	Value
A	100
B	$\cancel{300}400$
C	5
D	60
E	80

3. $T_1$ updated $C$ $5\to 10$. Update database:

Resource	Value
A	100
B	400
C	$\cancel{5}10$
D	60
E	80

4. $T_2$ started. Accept $T_2$ into undo list: $U=\{T_1,T_2\}$.

5. $T_2$ updated $E$ $80\to 480$. Update database:

Resource	Value
A	100
B	400
C	10
D	60
E	$\cancel{80}480$

6. $T_1$ updated $A$ $100\to 560$. Update database:

Resource	Value
A	$\cancel{100}560$
B	400
C	10
D	60
E	480

7. $T_1$ committed. Remove $T_1$ from undo list: $U=\{T_2\}$.

8. $T_2$ updated $A$ $560\to 570$. Update database:

Resource	Value
A	$\cancel{560}570$
B	400
C	10
D	60
E	480

9. $T_2$ updated $D$ $60\to 530$. Update database:

Resource	Value
A	570
B	400
C	10
D	$\cancel{60}530$
E	480

Phases 2 - UNDO:

Resource	Value
A	570
B	400
C	10
D	530
E	480

$T_2\in U=\{T_2\}$. Undoing changes caused by $T_2$ in reverse order.

• Reversing $[T_2,D,60,530]$ and add $[T_2,D,60]$ to end of log entries:

Resource	Value
A	570
B	400
C	10
D	$\cancel{530}60$
E	480

1. [ T1, start ]
2. [ T1, B, 300, 400 ]
3. [ T1, C, 5, 10]
4. [ T2, start ]
5. [ T2, E, 80, 480 ]
6. [ T1, A, 100, 560 ]
7. [ T1, commit ]
8. [ T2, A, 560, 570 ]
9. [ T2, D, 60, 530 ]
10. [ T2, D, 60 ]

• Reversing $[T_2,A,560,570]$ and add $[T_2,A,560]$ to end of log entries:

Resource	Value
A	$\cancel{570}560$
B	400
C	10
D	60
E	480

1. [ T1, start ]
2. [ T1, B, 300, 400 ]
3. [ T1, C, 5, 10]
4. [ T2, start ]
5. [ T2, E, 80, 480 ]
6. [ T1, A, 100, 560 ]
7. [ T1, commit ]
8. [ T2, A, 560, 570 ]
9. [ T2, D, 60, 530 ]
10. [ T2, D, 60 ]
11. [ T2, A, 560 ]

• Reversing $[T_2,E,80,480]$ and add $[T_2,E,80]$ to end of log entries:

Resource	Value
A	560
B	400
C	10
D	60
E	480

1. [ T1, start ]
2. [ T1, B, 300, 400 ]
3. [ T1, C, 5, 10]
4. [ T2, start ]
5. [ T2, E, 80, 480 ]
6. [ T1, A, 100, 560 ]
7. [ T1, commit ]
8. [ T2, A, 560, 570 ]
9. [ T2, D, 60, 530 ]
10. [ T2, D, 60 ]
11. [ T2, A, 560 ]
12. [ T2, E, 80 ]

• Found $[T_2,\text{start}]$. Remove $T_2$ from undo list, i.e. $U=\varnothing$ , and add $[T_2,\text{abort}]$ to end of log entries:

1. [ T1, start ]
2. [ T1, B, 300, 400 ]
3. [ T1, C, 5, 10 ]
4. [ T2, start ]
5. [ T2, E, 80, 480 ]
6. [ T1, A, 100, 560 ]
7. [ T1, commit ]
8. [ T2, A, 560, 570 ]
9. [ T2, D, 60, 530 ]
10. [ T2, D, 60 ]
11. [ T2, A, 560 ]
12. [ T2, E, 80 ]
13. [ T2, abort ]