Recovery
Types of Failures
Wrong data entry
- Prevent by having constraints in the database
- Fix with data cleaning
Disk crashes
- Prevent by using redundancy (RAID, archive)
- Fix by using archives
Fire, theft, bankruptcy…
- Buy insurance, change profession…
System failures: most frequent (e.g. power)
- Use recovery
System Failures
Each transaction has internal state
When system crashes, internal state is lost
- Don’t know which parts executed and which didn’t
Remedy: use a log
- A file that records every single action of the transaction
Transactions
Assumption: the database is composed of elements
Usually 1 element = 1 block
Can be smaller (=1 record) or larger (=1 relation)
Assumption: each transaction reads/writes some elements
Correctness Principle
There exists a notion of correctness for the database
- Explicit constraints (e.g. foreign keys)
- Implicit conditions (e.g. sum of sales = sum of invoices)
Correctness principle: if a transaction starts in a correct database state, it ends in a correct database state
Consequence: we only need to guarantee that transactions are atomic, and the database will be correct forever
Primitive Operations of Transactions
INPUT(X)
- read element X to memory buffer
READ(X,t)
- copy element X to transaction local variable t
WRITE(X,t)
- copy transaction local variable t to element X
OUTPUT(X)
- write element X to disk
The Log
An append-only file containing log records
Note: multiple transactions run concurrently, log records are interleaved
After a system crash, use log to:
- Redo some transaction that didn’t commit
- Undo other transactions that didn’t commit
Undo Logging
Log records
transaction T has begun
T has committed
T has aborted
<T,X,v> T has updated element X, and its old value was v
Undo-Logging Rules
U1: If T modifies X, then <T,X,v> must be written to disk before X is written to disk
U2: If T commits, then must be written to disk only after all changes by T are written to disk
Hence: OUTPUTs are done early
Recovery with Undo Log
After system’s crash, run recovery manager
Idea 1. Decide for each transaction T whether it is completed or not
Idea 2. Undo all modifications by incompleted transactions
Recovery manager:
Read log from the end; cases:
- : mark T as completed
- : mark T as completed
- <T,X,v>: if T is not completed
then write X=v to disk
else ignore - : ignore
阅读方向，从下向上
Note: all undo commands are idempotent, If we perform them a second time, no harm is done
stop reading the log:
- We cannot stop until we reach the beginning of the log file
- This is impractical
- Better idea: use checkpointing
Checkpointing
Checkpoint the database periodically
- Stop accepting new transactions
- Wait until all curent transactions complete
- Flush log to disk
- Write a log record, flush
- Resume transactions
Redo Logging
Log records
<T,X,v>= T has updated element X, and its new value is v
R1: If T modifies X, then both <T,X,v> and must be written to disk before X is written to disk
Hence: OUTPUTs are done late
After system’s crash, run recovery manager
Step 1. Decide for each transaction T whether it is completed or not
Step 2. Read log from the beginning, redo all updates of committed transactions
Undo/Redo Logging
Log records, only one change
<T,X,u,v>= T has updated element X, its old value was u, and its new value is v
Recovery with Undo/Redo Log
After system’s crash, run recovery manager
Redo all committed transaction, top-down
Undo all uncommitted transactions, bottom-up
总结
日志undo先写日志（从下向上读）redo先写磁盘（从上到下读）
冲突可串行 & 两阶锁
两个事物使用同一个资源并有一个是写就是冲突的，简单讲就是在冲突可串行并发操作的前驱图中是没有环路的，前驱图无环就是冲突可串行的。
每个事物在使用资源的时候都是先统一取再统一放的，也就是其图示先增后减，斜率不会出现其他变动。
E.g.
Consider the following schedule：
T1 STARTS
T1 reads item B
T1 writes item B with old value 11, new value 12
T2 STARTS
T2 reads item B
T2 writes item B with old value 12, new value 13
T3 STARTS
T3 reads item A
T3 writes item A with old value 29, new value 30
T2 reads item A
T2 writes item A with old value 30, new value 31
T2 COMMITS
T1 reads item D
T1 writes item D with old value 44, new value 45
T3 COMMITS
T1 COMMITS
(a) What serial schedule is this equivalent to? If none, then explain why.
The serializability graph for the above schedule is: T1T2 T3. Any order that complies with the
topological order of the graph like T1 T3 T2 is an equivalent serial schedule for our schedule
(b) Is this schedule consistent with two phase locking? Explain why.
If we assume that all transactions get the locks exactly before the operation and release them afterwards, it is not consistent with two phase locking. This is because T1 releases its lock on B after its second operation while acquiring a lock on D at its last two operations. By removing the last two operations of T1 the schedule becomes 2PL.
If we assume that the transactions get all the locks they need at the beginning of the transaction, and release them after the finish the operation, this schedule will be 2PL. The minimum operations that could be added to the schedule will be “T1 reads item A”. In this case, T1 has to acquire the lock on A again after releasing its lock on A after its first write.（这段话太深奥了，我用百度翻译都没看懂。。。）