Introduction to Database Systems CSE 444 Lectures 11-12 Transactions: Recovery (ARIES) 1Readings 2 Material(in(today’s(lecture(NOT(in(the(book( Instead,(read(Sec:ons(1,(2.2,(and(3.2(of:(Michael(J.(Franklin.(Concurrency(Control(and(Recovery.(The(Handbook(of(Computer(Science(and(Engineering,(A .(Tucker,(ed.,(CRC(Press,(Boca(Raton,(1997.(( (Also,(chapter(18(of(the(“cow(book”)(Review: the ACID properties 3 Atomicity( All(ac:ons(of(a(Xact(happen,(or(none(happen( Consistency( If(each(Xact(is(consistent,(and(the(DB(starts(consistent,(it(ends(up(consistent( Isola:on( Execu:on(of(one(Xact(is(isolated(from(others( Durability( If(a(Xact(commits,(its(effects(persist(Which(ones(does(the(Recovery(Manager(help(with?(*(also(consistency(related(rollbacks)(Buffer Manager 4 Disk(Main(memory(Page(requests(from(higher^level(code(Buffer(pool(Disk(page(Free(frame(1(page(corresponds(to(1(disk(block(Disk(=(collec:on(of(blocks(Disk(space(manager(Buffer(pool(manager(Files(and(access(methods(choice(of(frame(dictated(by(replacement*policy*• Data(must(be(in(RAM(for(DBMS(to(operate(on(it!(• Buffer(pool(=(table(of(<frame#,(pageid>(pairs(READ/WRITE(INPUT/O UTPUT(0(1(1(1(0(2(pin(count(dirty(Buffer Manager Policies 5 STEAL*or*NO5STEAL* Can(an(update(made(by(an(uncommihed(transac:on(overwrite(the(most(recent(commihed(value(of(a(data(item(on(disk?( FORCE*or*NO5FORCE* Should(all(updates(of(a(transac:on (be(forced(to(d isk(b efore(the(transac:on(commits?(No(Steal(Steal(No(Force(Fastest(Force(Slowest(No(Steal(Steal(No(Force(No(UNDO(REDO(UNDO(REDO(Force(No(UNDO(No(REDO(UNDO(No(REDO(ARIES Recovery Algorithm Overview 6 Three phases: 1. Analysis Figure out what was going on at time of crash List of dirty pages and active transactions 2. Redo Redo all operations, even for transactions that will not commit Get back to state at the moment of the crash 3. Undo Remove effects of all uncommitted transactions Log changes during undo in case of another crash during undo Algorithms(for(Recovery(and(Isola:on(Exploi:ng(Seman:cs(ARIES Recovery Algorithm Overview 7 Three principles: 1. Write-Ahead Logging (WAL) Any change to a DB object is first recorded to the log A log record must be written to disk before the corresponding object 2. Repeating history Reinstate the exact state of the system before the crash 3. Logging changes during UNDO Log UNDOs so we don’t repeat in a subsequent crashWrite-Ahead Log 8 1. Must(force(the(log(record(of(an(update(before(the(corresponding(data(page(gets(to(disk(2. Must(force(all(log(records(for(a(Xact(before(commit( Xact(is(considered(commihed(when(its(commi t(log(record(makes(it(to(stable(storage.(#1((with(UNDO(info)(helps(guarantee(atomicity(#2((with(REDO(info)(helps(guarantee(durability(<T,X,u,v>(OUTPUT(X)(Disk Disk before(<T,X,u,v>…<COMMIT(T>(Xact(commit(Disk before(The Log 9 Each(log(record(h as(a(un iq ue((( (Log(Sequence(Number((LSN)( Always(increasing( Each(data(page(contains(a(pageLSN( The(LSN(of(the(most(recent(log(record(that(updated(that(page( System(keeps(track(of(flushedLSN( Max(LSN(flushed(to(stable(storage(Log(records(flushed(to(disk(“log(tail”(in(RAM(Pagei(pageLSNi(flushedLSN(LSN(increasing(Types of Log Records 10 Update( Whenever(a(page(is(modified,(and(update(record(is(appended(to(the(log(tail( Commit( When(a(Xact(commits(it(force^writes(a(commit(log(record((i.e.(flushes(the(log(tail,(up(to(and(including(this(record ).( The(Xact(is(considered(commihed(the(moment(this(reco rd(is(on(stable(storage( Abort( When(a(transac:on(is(aborted((ini:ates(rollb ack)( End( When(a(Xact(aborts(or(commits(addi:onal(ac:ons(are(ini:ated((e.g.(rollback).(Once(those(fini sh,(an(end (record(is(appended( CLR( Compensa:on(Log(Record :(Logs(th e(UNDOs( Checkpoint(Log Records 11 CLR(records( REDO(only:(they(do(not(get(undone( Only(contain(amer^image( Addi:onal(undoNextLSN(field( Points(to(the(next(log(record(of(the(Xact(that(shou ld( be(und on e(LSN(prevLSN(transID(type(pageID(length(offset(before^image(amer^image(Fields(common(to(all(log(records(Addi:onal(fields(for(update(log(records(The(previous(LSN(of(the(Xact.(NULL(if(this(is(the(first(record(The(ID(of(the(disk(page(that(is(modified(Other Recovery-Related Structures 12 transID(status(lastLSN(Transac:on(Table(The(most(recent(log(record(for(the(Xact(pageID(recLSN(Dirty(Page(Table(First(log(entry(that(dir:ed(the(page(running/comminng/abor:ng(Example of Recovery Structures 13 LSN(prevLSN(transID(type(pageID(length(offset(before^image(amer^image(10(null(T1(update(P5(3(21(ABC(DEF(transID(status(lastLSN(Transac:on(Table(pageID(recLSN(Dirty(Page(Table(Buffer(Pool(Example of Recovery Structures 14 LSN(prevLSN(transID(type(pageID(length(offset(before^image(amer^image(10(null(T1(update(P5(3(21(ABC(DEF(transID(status(lastLSN(T1(running(10(Transac:on(Table(pageID(recLSN(P5(10(Dirty(Page(Table(P5(pageLSN=10(Buffer(Pool(Example of Recovery Structures 15 LSN(prevLSN(transID(type(pageID(length(offset(before^image(amer^image(10(null(T1(update(P5(3(21(ABC(DEF(20(null(T2(update(P6(3(41(HIJ(KLM(transID(status(lastLSN(T1(running(10(Transac:on(Table(pageID(recLSN(P5(10(Dirty(Page(Table(P5(pageLSN=10(Buffer(Pool(Example of Recovery Structures 16 LSN(prevLSN(transID(type(pageID(length(offset(before^image(amer^image(10(null(T1(update(P5(3(21(ABC(DEF(20(null(T2(update(P6(3(41(HIJ(KLM(transID(status(lastLSN(T1(running(10(T2(running(20(Transac:on(Table(pageID(recLSN(P5(10(P6(20(Dirty(Page(Table(P5(pageLSN=10(P6(pageLSN=20(Buffer(Pool(Example of Recovery Structures 17 LSN(prevLSN(transID(type(pageID(length(offset(before^image(amer^image(10(null(T1(update(P5(3(21(ABC(DEF(20(null(T2(update(P6(3(41(HIJ(KLM(30(20(T2(update(P5(3(20(GDE(QRS(transID(status(lastLSN(T1(running(10(T2(running(20(Transac:on(Table(pageID(recLSN(P5(10(P6(20(Dirty(Page(Table(P5(pageLSN=10(P6(pageLSN=20(Buffer(Pool(Example of Recovery Structures 18
View Full Document
Unlocking...