4/27/10'1'Recovery'Management'CISC437/637,'Lecture'#18'Ben'Cartere@e'1'Copyright'©'Ben'Cartere@e'ACID'Review'Atomicity'–'all'acJons'in'the'transacJon'happen'or'none'do'Consistency'–'each'transacJon'starts'with'consistent'database'and'ends'with'consistent'database'IsolaJon'–'each'transacJon'is'executed'independently'of'others'Durability'–'aPer'a'transacJon'commits,'its'effects'persist'• Concurrency'control/locking'ensures'consistency'and'isolaJon'• The'recovery+manager'ensures'atomicity'and'durability+2'Copyright'©'Ben'Cartere@e'4/27/10'2'AssumpJons'• Assume'the'database'is'using'concurrency'control'– Specifically,'assume'strict'twoUphase'locking'– (TransacJons'do'not'release'exclusive'locks'unJl'aPer'commiWng)'• Assume'updates'happen'in'place'– Updated'data'is'overwri@en'or'deleted'on'disk;'no'redundancy'in'storage'– (ProducJon'database'would'usually'use'some'storage'redundancy)'• Assume'wriJng'a'page'to'disk'is'atomic'– The'system'won’t'crash'while'a'write'is'in'progress'– (ProducJon'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'aPer'transacJon'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'4/27/10'3'Data'Access'• Pages'move'from'disk'to'memory'via'two'operaJons:'– Input(B)'transfers'a'physical'page'B'to'memory'– Output(B)'transfers'a'buffer'page'B'to'disk,'replacing'the'corresponding'physical'page'• Each'transacJon'has'its'own'memory'space'for'local'copies'of'the'data'it'needs'– For'transacJon'Ti'accessing'data'item'O,'we’ll'refer'to'its'local'copy'as'Oi'Copyright'©'Ben'Cartere@e' 5'Data'Access'• TransacJons'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'• TransacJons'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'aPer'write()s'Copyright'©'Ben'Cartere@e' 6'4/27/10'4'Handling'the'Buffer'• Two'quesJons'about'buffer'management:'1. Should'writes'be'forced'to'disk'aPer'transacJons'commit?'2. Should'transacJons'be'allowed'to'steal'pages'from'each'other?'(i.e.'if'transacJon'Ti'modifies'object'O'in'the'buffer,'and'transacJon'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'opJmal'operaJon'of'the'DBMS'Copyright'©'Ben'Cartere@e' 7'Forcing'and'Stealing'• To'force'or'not'to'force'– Forcing'gives'bad'response'Jme'–'frequentlyUaccessed'pages'are'constantly'being'wri@en'to'disk'for'high'I/O'overhead'– Without'forcing,'those'pages'can'be'kept'in'the'buffer'unJl'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'realisJc'– With'stealing,'pages'can'be'wri@en'to'disk'as'needed'to'fit'everything'in'memory'• But'what'if'a'transacJon'aborts?''How'do'we'enforce'atomicity?'Copyright'©'Ben'Cartere@e' 8'4/27/10'5'LogUBased'Recovery'• A'transac<on+log+on'stable'storage'is'used'to'allow'a'nonUforcing,'stealing'buffer'manager'– And'thus'more'opJmal'DBMS'operaJon'• The'log'maintains'a'record'of'update'acJviJes'on'the'DBMS'• It'needs'to'store'enough'informaJon'to'allow:'– UNDOing'a'write'of'page'B'to'disk,'so'that'robbed'transacJons'can'be'rolled'back'– REDOing'modificaJons'of'pages'that'happened'in'memory'but'were'never'forced'to'disk''Copyright'©'Ben'Cartere@e' 9'LogUBased'Recovery'• Write'a'minimal'amount'of'informaJon'to'the'log'to'support'UNDOs/REDOs'– Minimal'informaJon'to'ensure'that'mulJple'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'descripJon'Copyright'©'Ben'Cartere@e' 10'4/27/10'6'NoUForce,'NoUSteal'• Deferred+database+modifica<on'– Record'modificaJons'to'log;'defer'all'disk'writes'unJl'aPer'parJal'commit'(but'never'force'them)'• Log'entries:'– TransacJon'starts'by'wriJng'<Ti,'start>'to'log'– Each'Jme'it'executes'a'write(O):'• <Ti,'O,'V>'wri@en'to'log,'where'V'is'the'new'value'of'O'– When'it'reaches'parJalUcommit'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'TransacJons'• Effects'of'the'transacJon'T'are'wri@en'to'disk'via'execuJon'of'a'redo(T)'operaJon'– 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'aPer'the'redo()'• Redo()'only'happens'if'both'start'and'commit'records'exist'for'the'transacJon'Copyright'©'Ben'Cartere@e' 12'4/27/10'7'NoUForce,'Stealing'Allowed'• Immediate+database+modifica<on'– Pages'may'be'wri@en'to'disk'before'transacJon 'completes'– If'a'transacJon'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'Jme'before'or'aPer'the'transacJon'has'commi@ed'– The'order'in'which'output()s'happen'may'be'diff erent'from'the'order'pages'were'write()n'Copyright'©'Ben'Cartere@e' 13'Undo'and'Redo'• Undo'and'redo'operaJons'implemented'as'fol lows:'– 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'–