Lampson's lecture 5/7/03


high performance recovery for atomic actions
- more than just correctness is needed
- tolerate disk slowness


start state + sequence of ops to get there
- time cost is proportional to change


isolation:
want commutativity between actions
locks conflict only when operations don't commute (by definition)


atomicity properties for recovery
---------------------------------


disk (persistent store):  vars -> values  [disk addr -> 512 bytes]
log:  sequence of ops, x:=value


recoverability (old method):
- start with disk state
- calculate desired volatile state w/ops
- write ops to log
- commit record (change state)
- update disk


new method goals:


- disk is slow, so use a cache
   (behaves like a writeback cache:
     write to cache and flush to disk asynchronously)


- decouple commit from install (install = update disk)
   may want to install either before commit or much later
    - before commit:  clear some cache in preparation for a big
   transaction
    - much later:  save disk writes in periods of high activity


- decouple recover from install
   a large log could cause a very slow recovery, resulting in downtime


- decouple cache from commit
   there should be only 2 places for data (disk and cache)


- allow the log to be truncated
   can't let the log grow too much
    - memory limitations
    - large log means large recovery time
   question:  when do we no longer need log entries?


cache:  vars -> values
install:  write to disk from cache


volatile state (VS):  disk + log = disk + cache
(depend on log for recovery, execute ops against cache)


persistent state (PS):  VS + undo's of uncommitted ops


decoupling commit:  need undo if action doesn't commit
- log an undo entry with each operation entry
- abort:  turn undo info into real ops
- undo's must commute with all later operations until commit (ex?)


recover:


apply the log
- just like normal op
- if cache is large enough, we can use it to apply the whole log,
   therefore recovery is CPU bound


we now have VS
- abort uncommitted transactions, because crash lost the tail of the log
- apply undo's to get PS


install:


don't change VS:  disk + log = disk + writes + log
log = writes + log -> 'idempotence'
this works if the log only uses 'blind writes,' e.g. x:=3


truncating the log:


VS = disk + old + tail = disk + tail
old + tail = tail


- old is all committed
- truncate entries from log if writes are done or superceded
   cache keeps LSN (log sequence number) to cross-reference log entries


summary:
- need undo -> log undo info
- recover:  redo everything, apply undo's to uncommitted
- install and truncate don't change VS