5/17/11%1%Recovery%Management%CISC437/637,%Lecture%#19%Ben%Cartere?e%1%Copyright%©%Ben%Cartere?e%ACID%Review%Atomicity%–%all%acIons%in%the%transacIon%happen%or%none%do%Consistency%–%each%transacIon%starts%with%consistent%database%and%ends%with%consistent%database%IsolaIon%–%each%transacIon%is%executed%independently%of%others%Durability%–%aOer%a%transacIon%commits,%its%effects%persist%• Concurrency%control/locking%ensures%consistency%and%isolaIon%• The%recovery+manager%ensures%atomicity%and%durability+2%Copyright%©%Ben%Cartere?e%5/17/11%2%AssumpIons%• Assume%the%database%is%using%concurrency%control%– Specifically,%assume%strict%twoUphase%locking%– (TransacIons%do%not%release%exclusive%locks%unIl%aOer%commiWng)%• Assume%updates%happen%in%place%– Updated%data%is%overwri?en%or%deleted%on%disk;%no%redundancy%in%storage%– (ProducIon%database%would%usually%use%some%storage%redundancy)%• Assume%wriIng%a%page%to%disk%is%atomic%– The%system%won’t%crash%while%a%write%is%in%progress%– (ProducIon%database%would%not%assume%this)%Copyright%©%Ben%Cartere?e% 3%Data%Access%• Up%to%now,%we%have%assumed%that%data%access%happens%via%disk%access%only%• In%reality,%disk%accesses%are%used%to%transfer%data%to%memory%– Data%may%persist%in%memory%aOer%transacIon%accessing%it%completes%– The%buffer%manager%decides%when%to%move%data%from%memory%back%to%disk%• Physical+pages%are%pages%stored%on%disk%(“permanently”)%• Buffer+pages%are%pages%temporarily%in%main%memory%%Copyright%©%Ben%Cartere?e% 4%5/17/11%3%Data%Access%• Pages%move%from%disk%to%memory%via%two%operaIons:%– Input(B)%transfers%a%physical%page%B%to%memory%– Output(B)%transfers%a%buffer%page%B%to%disk,%replacing%the%corresponding%physical%page%• Each%transacIon%has%its%own%memory%space%for%local%copies%of%the%data%it%needs%– For%transacIon%Ti%accessing%data%item%O,%we’ll%refer%to%its%local%copy%as%Oi%Copyright%©%Ben%Cartere?e% 5%Data%Access%• TransacIons%transfer%data%from%the%buffer%to%their%private%workspace%– Read(O)%assigns%the%O%in%memory%to%Oi%in%the%local%workspace%– Write(O)%assigns%the%value%of%Oi%in%the%local%workspace%to%the%O%in%memory%– If%the%physical%page%in%which%O%lives%is%not%in%memory,%an%Input()%may%have%to%happen%first%• TransacIons%only%operate%on%the%data%in%the%buffer%– A%buffer%manager%determines%when%to%perform%input()s%and%output()s%– Output()s%may%not%happen%immediately%aOer%write()s%Copyright%©%Ben%Cartere?e% 6%5/17/11%4%Handling%the%Buffer%• Two%quesIons%about%buffer%management:%1. Should%writes%be%forced%to%disk%aOer%transacIons%commit?%2. Should%transacIons%be%allowed%to%steal%pages%from%each%other?%(i.e.%if%transacIon%Ti%modifies%object%O%in%the%buffer,%and%transacIon%Tj%requires%an%input(),%can%the%buffer%manager%write%O%to%disk%to%make%space%for%a%new%page?)%• Forcing%with%no%stealing%trivially%ensures%durability%and%atomicity,%but%not%opImal%operaIon%of%the%DBMS%Copyright%©%Ben%Cartere?e% 7%Forcing%and%Stealing%• To%force%or%not%to%force%– Forcing%gives%bad%response%Ime%–%frequentlyUaccessed%pages%are%constantly%being%wri?en%to%disk%for%high%I/O%overhead%– Without%forcing,%those%pages%can%be%kept%in%the%buffer%unIl%their%access%frequency%has%dropped%• But%what%if%there’s%a%crash?%%How%do%we%enforce%durability?%• To%steal%or%not%to%steal%– No%stealing%assumes%all%currentlyUused%pages%will%fit%in%memory,%which%is%not%realisIc%– With%stealing,%pages%can%be%wri?en%to%disk%as%needed%to%fit%everything%in%memory%• But%what%if%a%transacIon%aborts?%%How%do%we%enforce%atomicity?%Copyright%©%Ben%Cartere?e% 8%5/17/11%5%LogUBased%Recovery%• A%transac<on+log+on%stable%storage%is%used%to%allow%a%nonUforcing,%stealing%buffer%manager%– And%thus%more%opImal%DBMS%operaIon%• The%log%maintains%a%record%of%update%acIviIes%on%the%DBMS%• It%needs%to%store%enough%informaIon%to%allow:%– UNDOing%a%write%of%page%B%to%disk,%so%that%robbed%transacIons%can%be%rolled%back%– REDOing%modificaIons%of%pages%that%happened%in%memory%but%were%never%forced%to%disk%%Copyright%©%Ben%Cartere?e% 9%LogUBased%Recovery%• Write%a%minimal%amount%of%informaIon%to%the%log%to%support%UNDOs/REDOs%– Minimal%informaIon%to%ensure%that%mulIple%updates%fit%on%a%single%page%of%the%log%• Each%record%contains%<trans%ID,%page%ID,%offset,%length,%old%data,%new%data>%– <trans%ID,%page%ID,%old%data,%new%data>%are%the%most%important%for%our%descripIon%Copyright%©%Ben%Cartere?e% 10%5/17/11%6%NoUForce,%NoUSteal%• Deferred+database+modifica<on%– Record%modificaIons%to%log;%defer%all%disk%writes%unIl%aOer%parIal%commit%(but%never%force%them)%• Log%entries:%– TransacIon%starts%by%wriIng%<Ti,%start>%to%log%– Each%Ime%it%executes%a%write(O):%• <Ti,%O,%V>%wri?en%to%log,%where%V%is%the%new%value%of%O%– When%it%reaches%parIalUcommit%state,%<Ti,%commit>%is%wri?en%to%log%• Log%records%can%then%be%read%to%actually%execute%the%deferred%writes%Copyright%©%Ben%Cartere?e% 11%Redoing%TransacIons%• Effects%of%the%transacIon%T%are%wri?en%to%disk%via%execuIon%of%a%redo(T)%operaIon%– Redo()%sets%all%values%in%the%database%to%new%values%in%log,%regardless%of%current%values%– As%long%as%the%log%reflects%a%consistent%database,%the%database%will%be%consistent%aOer%the%redo()%• Redo()%only%happens%if%both%start%and%commit%records%exist%for%the%transacIon%Copyright%©%Ben%Cartere?e% 12%5/17/11%7%NoUForce,%Stealing%Allowed%• Immediate+database+modifica<on%– Pages%may%be%wri?en%to%disk%before%transacIon%completes%– If%a%transacIon%has%to%be%rolled%back,%the%effects%will %need%to%be%undone%• Log%entries%must%include%previous%value%• As%long%as%a%write()%has%been%logged,%output()%to%disk%can%happen%any%Ime%before%or%aOer%the%transacIon%has%commi?ed%– The%order%in%which%output()s%happen%may%be%different%from%the%order%pages%were%write()n%Copyright%©%Ben%Cartere?e% 13%Undo%and%Redo%• Undo%and%redo%operaIons%implemented%as%follows:%– Undo(Ti)%moves%backward%through%the%log,%seWng%the%value%of%every%data%item%updated%by%Ti%to%its%previous%value%– Redo(Ti)%moves%forward%through%the%log,%seWng%the%value%of%every%data%item%updated%by%Ti%to%its%new%value%• Undo%and%redo%must%be%idempotent%–
View Full Document