CS计算机代考程序代写 database concurrency algorithm 2021/4/28 Implementing Recovery

程序代写 CS代考 / Algorithm算法代写代考, concurrency, database

2021/4/28 Implementing Recovery
Implementing Recovery
Recovery
Logging
Undo Logging Checkpointing
Redo Logging Undo/Redo Logging Recovery in PostgreSQL
>>
COMP9315 21T1 ♢ Implementing Recovery ♢ [0/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
1/22

2021/4/28 Implementing Recovery
∧ >>
❖ Recovery
For a DBMS to recover from a system failure, it
needs
a mechanism to record what updates were “in train” at failure time
methods for restoring the database(s) to a valid state afterwards
Assume multiple transactions are running when failure occurs
uncommitted transactions need to be rolled back (ABORT)
committed, but not yet nalised, tx’s need to be completed
A critical mechanism in achieving this is the
transaction (event) log
COMP9315 21T1 ♢ Implementing Recovery ♢ [1/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
2/22

2021/4/28 Implementing Recovery
❖ Logging
Three “styles” of logging
undo … removes changes by any uncommitted tx’s
redo … repeats changes by any committed tx’s undo/redo … combines aspects of both
All approaches require:
a sequential le of log records
each log record describes a change to a data item
log records are written before changes to data actual changes to data are written later
Known as write-ahead logging (PostgreSQL uses WAL)
COMP9315 21T1 ♢ Implementing Recovery ♢ [2/20]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
3/22

2021/4/28 Implementing Recovery
❖ Undo Logging
Simple form of logging which ensures atomicity. Log le consists of a sequence of small records:
…transactionTbegins …transactionTcompletes
successfully
…transactionTfails(nochanges)
… transaction T changed value of X from v
Notes:
we refer to generically as log records
update log entry created for each WRITE (not OUTPUT)
update log entry contains old value (new value is not recorded)
COMP9315 21T1 ♢ Implementing Recovery ♢ [3/20]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
4/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Undo Logging (cont)
Data must be written to disk in the following
order:
1. transaction log record
2. log records indicating changes 3. the changed data elements themselves 4. log record
Note: sufcient to have output before X, for each X
COMP9315 21T1 ♢ Implementing Recovery ♢ [4/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
5/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Undo Logging (cont)
For the example transaction, we would get:
t Action v B(A) B(B) D(A) D(B) Log ——————————————————– (0)BEGIN . . . 8 5 (1)READ(A,v) 8 8 . 8 5
(2)v=v*2 16 8 . 8 5 (3) WRITE(A,v) 16 16 . 8 5 (4) READ(B,v) 5 16 5 8 5 (5)v=v+1 616585



(6) WRITE(B,v)
(7) FlushLog
(8) StartCommit
(9) OUTPUT(A)
(10) OUTPUT(B)
(11) EndCommit
(12) FlushLog
6 16 68 5
6 16 616 5 6 16 616 6
Note that T is not regarded as committed until (12) completes.
COMP9315 21T1 ♢ Implementing Recovery ♢ [5/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
6/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Undo Logging (cont)
Simplied view of recovery using UNDO logging:
scan backwards through log
if,markTascommitted
if and T not committed, set X to v on disk
ifandTnotcommitted,put inlog
Assumes we scan entire log; use checkpoints to limit scan.
COMP9315 21T1 ♢ Implementing Recovery ♢ [6/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
7/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Undo Logging (cont)
Algorithmic view of recovery using UNDO logging:
committedTrans = abortedTrans = startedTrans = {}
for each log record from most recent to oldest {
switch (log record) {
: add T to committedTrans
: add T to abortedTrans
: add T to startedTrans
: if (T in committedTrans)
// don’t undo committed changes else // roll-back changes
{ WRITE(X,v); OUTPUT(X) }
}}
for each T in startedTrans {
if (T in committedTrans) ignore
else if (T in abortedTrans) ignore
else write to log
}
flush log
COMP9315 21T1 ♢ Implementing Recovery ♢ [7/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
8/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Checkpointing
Simple view of recovery implies reading entire log
le.
Since log le grows without bound, this is infeasible.
Eventually we can delete “old” section of log.
i.e. where all prior transactions have committed
This point is called a checkpoint.
all of log prior to checkpoint can be ignored for
recovery
COMP9315 21T1 ♢ Implementing Recovery ♢ [8/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
9/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Checkpointing (cont)
Problem: many concurrent/overlapping
transactions.
How to know that all have nished?
1. periodically, write log record
(contains references to all active transactions ⇒ active tx table)
2. continue normal processing (e.g. new tx’s can start)
3. when all of T1,..,Tk have completed,
write log record and ush log
Note: tx manager maintains chkpt and active tx
information
COMP9315 21T1 ♢ Implementing Recovery ♢ [9/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
10/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Checkpointing (cont)
Recovery: scan backwards through log le
processing as before.
Determining where to stop depends on …
whether we meet or rst
If we encounter rst:
we know that all incomplete tx’s come after
prev
thus, can stop backward scan when we reach

Ifweencounterrst: crash occurred during the checkpoint period
any of T1,..,Tk that committed before crash are ok
for uncommitted tx’s, need to continue backward scan
COMP9315 21T1 ♢ Implementing Recovery ♢ [10/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
11/22

2021/4/28 Implementing Recovery
❖ Redo Logging Problem with UNDO logging:
all changed data must be output to disk before committing
conicts with optimal use of the buffer pool
Alternative approach is redo logging:
allow changes to remain only in buffers after
commit
write records to indicate what changes are “pending”
after a crash, can apply changes during recovery
COMP9315 21T1 ♢ Implementing Recovery ♢ [11/20]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
12/22

2021/4/28 Implementing Recovery
❖ Redo Logging (cont)
Requirement for redo logging: write-ahead rule. Data must be written to disk as follows:
1. start transaction log record
2. update log records indicating changes
3. then commit log record (OUTPUT)
4. then OUTPUT changed data elements themselves
Note that update log records now contain ,
where v’ is the new value for X.
COMP9315 21T1 ♢ Implementing Recovery ♢ [12/20]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
13/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Redo Logging (cont)
For the example transaction, we would get:
t Action v B(A) B(B) D(A) D(B) Log ——————————————————– (0)BEGIN . . . 8 5 (1)READ(A,v) 8 8 . 8 5
(2)v=v*2 16 8 . 8 5 (3) WRITE(A,v) 16 16 . 8 5 (4) READ(B,v) 5 16 5 8 5 (5)v=v+1 616585



(6) WRITE(B,v)
(7) COMMIT
(8) FlushLog
(9) OUTPUT(A)
(10) OUTPUT(B)
6 16
6 16 6 16
68 5
616 5 616 6
Note that T is regarded as committed as soon as (8) completes.
COMP9315 21T1 ♢ Implementing Recovery ♢ [13/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
14/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Redo Logging (cont)
Simplied view of recovery using REDO logging:
identifyallcommittedtx’s (backwardsscan) scan forwards through log
if and T is committed, set X to v on disk
ifandTnotcommitted,put inlog
Assumes we scan entire log; use checkpoints to limit scan.
COMP9315 21T1 ♢ Implementing Recovery ♢ [14/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
15/22

2021/4/28 Implementing Recovery
<< ∧ >>
❖ Undo/Redo Logging UNDO logging and REDO logging are
incompatible in
orderofoutputtingandchanged data
how data in buffers is handled during checkpoints
Undo/Redo logging combines aspects of both
requires new kind of update log record gives both old and new values for X
removes incompatibilities between output orders
As for previous cases, requires write-ahead of log records.
Undo/redo loging is common in practice; Aries algorithm.
COMP9315 21T1 ♢ Implementing Recovery ♢ [15/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
16/22

2021/4/28 Implementing Recovery
<< ∧ >> ❖ Undo/Redo Logging (cont)
For the example transaction, we might get:
t Action v B(A) B(B) D(A) D(B) Log ——————————————————– (0)BEGIN . . . 8 5 (1)READ(A,v) 8 8 . 8 5
(2)v=v*2 16 8 . 8 5 (3) WRITE(A,v) 16 16 . 8 5 (4) READ(B,v) 5 16 5 8 5 (5)v=v+1 616585



(6) WRITE(B,v)
(7) FlushLog
(8) StartCommit
(9) OUTPUT(A)
(10)
(11) OUTPUT(B)
6 16
6 16 6 16
68 5
616 5 616 6
Note that T is regarded as committed as soon as (10) completes.
COMP9315 21T1 ♢ Implementing Recovery ♢ [16/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
17/22

2021/4/28 Implementing Recovery
<< ∧ >> ❖ Undo/Redo Logging (cont)
Simplied view of recovery using UNDO/REDO logging:
scan log to determine committed/uncommitted txs
foreachuncommittedtxTaddto log
scan backwards through log
if and T is not committed, set X
tovondisk
scan forwards through log
if and T is committed, set X to w on disk
COMP9315 21T1 ♢ Implementing Recovery ♢ [17/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
18/22

2021/4/28 Implementing Recovery
<< ∧ >> ❖ Undo/Redo Logging (cont)
The above description simplies details of undo/redo logging.
Aries is a complete algorithm for undo/redo logging.
Differences to what we have described:
log records contain a sequence numnber (LSN)
LSNs used in tx and buffer managers, and stored in data pages
additional log record to mark (of commit or abort)
contains only a timestamp contains tx and dirty page info
COMP9315 21T1 ♢ Implementing Recovery ♢ [18/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
19/22

2021/4/28 Implementing Recovery
<< ∧ >> ❖ Recovery in PostgreSQL
PostgreSQL uses write-ahead undo/redo style logging.
It also uses multi-version concurrency control, which
tags each record with a tx and update timestamp
MVCC simplies some aspects of undo/redo, e.g.
some info required by logging is already held in each tuple
no need to undo effects of aborted tx’s; use old version
COMP9315 21T1 ♢ Implementing Recovery ♢ [19/20]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html
20/22

2021/4/28 Implementing Recovery
<< ∧ ❖ Recovery in PostgreSQL (cont) Transaction/logging code is distributed throughout backend. Core transaction code is in src/backend/access/transam. Transaction/logging data is written to les in PGDATA/pg_wal a number of very large les containing log records old les are removed once all txs noted there are completed new les added when existing les reach their capacity (16MB) number of tx log les varies depending on tx activity COMP9315 21T1 ♢ Implementing Recovery ♢ [20/20] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html 21/22 2021/4/28 Implementing Recovery Produced: 20 Apr 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-recovery/slides.html 22/22

Related Posts