Recovery — livet etter krasj

Hva skal recovery levere?

Recovery manager har bare ett oppdrag: gjenopprette databasen til en konsistent tilstand etter en feil — og det med to ACID-bokstaver i bagasjen, A og D.

• Atomicity — alle uavsluttede transaksjoner ved krasj skal rulles tilbake (undo).
• Durability — alle committed transaksjoner ved krasj skal være på disken etterpå (redo om nødvendig).

I tillegg må recovery-prosessen være idempotent (gir samme resultat uansett hvor mange ganger den kjøres): hvis maskinen krasjer igjen midt under recovery, skal det å starte recovery på nytt fortsatt gi riktig resultat. Det er kompenserende loggposter (CLR — Compensating Log Records, seksjon 06 nedenfor) som gjør dette mulig.

Tre typer feil

1. Transaksjons-abort under normal drift — manglende data, brukervalg, deadlock.
2. System-krasj — strømbrudd, OS-kill, software-feil. RAM forsvinner, disk overlever.
3. Mediefeil — disken selv er ødelagt. Trenger backup + redo. (Utenfor pensum.)

Hvilke transaksjoner var egentlig ferdige?

Når strømmen gikk, var noen transaksjoner committed (vi vet det fordi commit-loggposten — en oppføring i loggen som markerer at transaksjonen committet — var på disk), andre var midt i. De første kalles winners, de andre losers.

Etter krasj må recovery-prosessen:

1. Finne ut hvem som var winner og hvem som var loser (Analysis-fasen).
2. Sørge for at alle winners' endringer er på disk (Redo-fasen).
3. Rulle tilbake alle losers' delvise endringer (Undo-fasen).

Force og steal

Hvilken algoritme et DBMS trenger avhenger av to designvalg om buffer-poolen (RAM-området der databasen mellomlagrer datasider fra disk — kap. 6):

• Force: Tvinger systemet at alle data-sider skrives til disk ved commit?
  • Ja (force) — durability lett, men dyr commit (mange random writes).
  • Nei (no-force) — billig commit, men trenger redo etter krasj.
• Steal: Kan en plass i bufferpoolen «stjeles» (skrives til disk) fra en uavsluttet transaksjon?
  • Ja (steal) — fleksibel buffer-bruk, men trenger undo for halvskrevne sider.
  • Nei (no-steal) — uavsluttede sider holdes i buffer til commit. Begrenset.

ARIES (Algorithms for Recovery and Isolation Exploiting Semantics — den klassiske recovery-algoritmen, fra IBM på 90-tallet) sitter i steal/no-force-hjørnet: maksimal fleksibilitet for buffer manager, men krever både undo- og redo-logging. Det er prisen for ytelse i moderne SQL-databaser.

Append-only kronologi

Loggen er en sekvensiell, append-only (bare tilføy, aldri overskriv) fil på en egen disk. Hver loggpost har en stadig voksende LSN (Log Sequence Number — et unikt løpenummer).

Generisk log-record

(LSN, TransID, PrevLSN, OpType, PageID, Offset, BeforeImage, AfterImage)

• LSN — unik, voksende. Også brukt som PageLSN på datasiden.
• PrevLSN — peker bakover til forrige log-record fra samme transaksjon. Lager en lenket kjede per Tx.
• OpType — update / insert / delete / commit / abort / CLR / checkpoint.
• BeforeImage / AfterImage — hva som lå der før og etter (brukes til hhv. undo og redo).

PageLSN — koblingen mellom logg og data

Hver dataside har et felt PageLSN som inneholder LSN-en til siste log-record som ble brukt på siden. Det er den sjekken redo-fasen bruker for å avgjøre om en endring allerede er reflektert på siden.

Write-ahead logging

Hele recovery-arkitekturen hviler på én regel:

WAL-regelen: Før en endret dataside skrives til disk, må alle loggposter som beskriver endringen være på disk først.

Konkret: før vi skriver dirty side P med PageLSN = L til disk, må FlushedLSN ≥ L. Hvis ikke, kunne et krasj rett etter side-skrivingen latt oss stå med en delvis oppdatert side på disk uten noen log-record som forteller hvordan vi skulle rulle den tilbake — atomicity brutt.

WAL har egentlig to deler:

1. Undo-WAL — log først, data etterpå (ovenfor). Sikrer atomicity.
2. Force-log-at-commit — ved COMMIT, tving log-bufferen til disk før suksess returneres til klient. Sikrer durability.

Side C kan ikke skrives til disk før log-record 102 er på disk (FlushedLSN ≥ 102).

Compensating Log Records

Tenk: under undo for en aborted transaksjon krasjer maskinen. Når den starter på nytt — hvor langt har vi kommet i å rulle tilbake? Skal vi rulle tilbake samme record igjen?

ARIES sin eleganse: når vi undoer en loggpost, skriver vi en ny loggpost som beskriver «jeg har angret den endringen». Den heter en CLR (Compensating Log Record — kompenserende loggpost). PageLSN på siden oppdateres til CLR-ens LSN.

Egenskaper:

• CLR-er kan redoes hvis krasj skjer under undo, men undoes aldri.
• Undo-prosessen følger PrevLSN i den opprinnelige (non-CLR) loggposten for å finne neste loggpost å angre.
• CLR-en lar undo bli en roll-forward-operasjon (vi går framover i loggen i stedet for bakover) — andre operasjoner kan fortsette på samme blokk.

Resultat: idempotent recovery. Du kan krasje, restarte, krasje igjen — slutt-tilstanden er den samme.

Det ARIES holder rede på

To tabeller i RAM. De kopieres periodisk til loggen via et sjekkpunkt — en loggpost som lagrer et øyeblikksbilde av TT og DPT, slik at recovery slipper å lese loggen fra start og kan begynne der. (Full mekanikk i §10.)

Transaction Table (TT)

Én rad per aktiv transaksjon. Inneholder:

• TransID
• Status — active / committed / aborted
• LastLSN — siste loggpost skrevet av denne Tx (start på undo-kjeden)

Dirty Page Table (DPT)

Én rad per dirty side i buffer (modifisert, men ikke skrevet til disk). Inneholder:

• PageID
• RecLSN — LSN av første loggpost som gjorde siden dirty etter siste flush. Det er det tidligste punktet redo må gå tilbake til for denne siden.

Hvorfor skiller vi RecLSN fra PageLSN? Begge gjelder samme side, men ulike formål: RecLSN sier hvor langt tilbake redo må starte; PageLSN sier hvor langt redo allerede er kommet.

Tre faser ved restart

Etter krasj går recovery-prosessen gjennom nøyaktig tre faser, alltid i denne rekkefølgen. Klikk «Spill av» for å se rekkefølgen:

Restart-algoritmen i pseudokode

Et sjekkpunkt skrives som to loggposter — begin_checkpoint og end_checkpoint (med TT/DPT-snapshotet) — og en log anchor (master record på disk) peker til siste fullførte begin_checkpoint. Detaljer i §10.

function RESTART():
    # ── ANALYSIS ──
    finn siste begin_checkpoint i loggen via log anchor
    TT, DPT ← snapshot fra end_checkpoint
    for hver log-record fra begin_checkpoint og fremover:
        if record er Update / Insert / Delete:
            if Tx ikke i TT: legg til (status=active, lastLSN=LSN)
            else: oppdater Tx.lastLSN = LSN
            if PageID ikke i DPT: legg til (RecLSN=LSN)
        else if record er Commit:
            TT[Tx].status = committed
        else if record er Abort:
            TT[Tx].status = aborted
    losers ← {Tx i TT der status ≠ committed}

    # ── REDO ──
    startLSN ← min(RecLSN over alle sider i DPT)
    for hver log-record fra startLSN og fremover:
        if PageID ikke i DPT: skip
        if LSN < DPT[PageID].RecLSN: skip
        les inn siden; if PageLSN ≥ LSN: skip
        utfør operasjonen; sett PageLSN = LSN

    # ── UNDO ──
    for hver loser Tx:
        L ← Tx.lastLSN
        while L ≠ 0:
            record ← logg[L]
            if record er CLR:
                # CLR-er undoes aldri — hopp via PrevLSN av non-CLR-en
                # som CLR-en kompenserte for
                L ← PrevLSN av non-CLR-en CLR-en peker på
            else:
                angre operasjonen; skriv CLR
                # PageLSN på berørt side = CLR-ens LSN
                L ← record.PrevLSN
    skriv "end_recovery" til logg

CLR-er er redo-only. Ved krasj under undo: ny restart finner siste CLR fra loseren og fortsetter via PrevLSN av den loggposten CLR-en kompenserte for — derfor blir aldri samme operasjon angret to ganger.

Bla gjennom kortene under for å sjekke at du forstår fasene og hvorfor de er nødvendige.

Analysis i praksis

La A, B, C være data-sider. Etter krasj finner vi følgende logg:

(ckpt = checkpoint, sjekkpunkt — se §10.)

Ved sjekkpunkt (LSN 105) hadde TT og DPT følgende:

Etter Analysis

Vi skanner forover fra LSN 106:

• LSN 106 (T3, Update A) — T3 er ny i TT, status active, lastLSN=106. A er ny i DPT, RecLSN=106.
• LSN 107 (T2, Update C) — T2 sin lastLSN oppdateres til 107. C eksisterer allerede i DPT med RecLSN=101 — vi oppdaterer ikke RecLSN (vi vil ha eldste!).
• LSN 108 (T2, Commit) — T2 sin status blir committed.

T3 er den eneste loseren — den må undoes. Redo starter ved minste RecLSN i DPT = 101.

Redo-test

For hver log-record (101..108) sjekker vi i denne rekkefølgen:

1. Hopp over hvis PageID ikke er i DPT.
2. Hopp over hvis log-record sin LSN < sidens RecLSN.
3. Les inn siden fra disk. Hopp over hvis sidens PageLSN ≥ log-record sin LSN.
4. Ellers: redo. Skriv AfterImage til siden. Sett PageLSN = log-record sin LSN.

Anta at A, B, C på disk har PageLSN = 106, 102, 101 ved start av redo:

Undo

T3 sin LastLSN er 106. Vi går baklengs (PrevLSN=0, så bare denne ene), skriver en CLR for LSN 106 og angrer endringen på A.

Større eksempel — undo-kjede med CLR-er

Tenk deg samme strukturen, men nå har vi to losere som har gjort flere endringer hver. Loggen ved krasj-tidspunktet:

Etter analysis: T4 er winner (commit på LSN 250), T5 er loser (ingen commit). T5 sin lastLSN = 260.

Undo-fasen, steg for steg

Vi følger PrevLSN-kjeden bakover fra T5.lastLSN, skriver en CLR for hver angring og oppdaterer PageLSN. Hver CLR peker tilbake til den non-CLR-en den kompenserer for — det er den recorden vi følger PrevLSN av hvis vi krasjer:

Loggen etter recovery inneholder altså både de opprinnelige loggpostene og CLR-ene 270, 280, 290 + sluttmarkøren 300. Sidene P1, P2, P3 har nå PageLSN = 280, 290, 270 — pekende på CLR-ene, ikke de angrede recordene.

Hva om vi krasjer under undo?

Anta krasj rett etter at vi skrev CLR 270 (som angrer 260) og siden P3 ble flushed til disk. Vi starter recovery på nytt:

1. Analysis ser nå LSN 270 som siste record fra T5. T5 har fortsatt status «active» (ingen commit funnet), så T5 er fortsatt loser.
2. Redo kjøres på vanlig vis. Når den treffer LSN 270 (CLR), redo-er den om PageLSN(P3) < 270 — men siden ble flushed, så PageLSN(P3) = 270 ⇒ skip. Ingen dobbel-undo.
3. Undo starter på T5.lastLSN = 270 (CLR-en, ikke 260!). Siden CLR-er aldri undoes, hopper vi forbi 270 og finner non-CLR-en CLR-en peker på (LSN 260). Derfra følger vi PrevLSN(260) = 230. Resten av kjeden: angrer 230, så 210, ferdig. Vi har ikke forsøkt å angre 260 to ganger.

Det er nøyaktig dette CLR-mekanismen er bygd for: idempotens. Krasj når som helst — neste restart finner siste CLR for hver loser og fortsetter undo via PrevLSN av den loggposten CLR-en kompenserte for, og produserer samme slutt-tilstand.

Begrens hvor langt tilbake recovery må gå

Uten sjekkpunkter må Analysis lese hele loggen fra start hver gang vi krasjer. Et sjekkpunkt er en periodisk «her var vi» — og recovery kan starte derfra.

Stop-the-world checkpoint (gammelt)

1. Stopp alle nye operasjoner.
2. Vent til alle aktive transaksjoner er ferdige (eller i hvert fall stille).
3. Flush alle dirty sider til disk.
4. Skriv «checkpoint»-record i loggen.
5. Slipp alle løs igjen.

Korrekt, men lammer systemet i sekunder — uakseptabelt for OLTP-trafikk.

Fuzzy checkpoint (ARIES)

1. Skriv begin_checkpoint-loggpost.
2. Skriv en end_checkpoint-loggpost som inneholder et øyeblikksbilde (snapshot) av TT og DPT akkurat nå.
3. Oppdater log anchor (et lite, fast sted på disk — også kalt master record) til å peke på begin_checkpoint.
4. Bakgrunnsprosess flusher dirty sider uten å blokkere drift.

Recovery starter ved begin_checkpoint; den vet hva TT/DPT så ut da, og leser videre forover for å bygge nåværende tilstand.

Hvorfor to records og ikke bare én?

Mens vi skriver TT og DPT (som kan være store), kjører resten av databasen videre — nye transaksjoner kommer til, andre committer. Snapshotet i end_checkpoint reflekterer altså tilstanden ved et punkt et sted mellom begin og end. Recovery må derfor begynne ved begin_checkpoint for å garantert fange alle endringer som ikke er reflektert i snapshotet.

Hva om vi krasjer mellom begin og end?

Log anchor pekes først oppdatert etter at end_checkpoint er på disk. Krasj mellom begin og end ⇒ log anchor peker fortsatt på forrige sjekkpunkt. Det fuzzy-sjekkpunktet vi var i ferd med å skrive eksisterer som «ufullstendig» i loggen, men recovery ignorerer det og bruker det forrige. Litt mer logg å skanne, men korrekt.

Penultimate checkpointing (nest siste sjekkpunkt)

En annen variant pensum nevner: skriv data ved sjekkpunkting, men bruk nest siste sjekkpunkt som startpunkt for recovery. Garanterer at all data referert i loggen før det punktet er på disk, så Analysis/REDO trenger ikke gå lenger tilbake. Ikke ARIES — ARIES bruker fuzzy checkpoint og DPT i stedet.

Trade-off: hyppige sjekkpunkter ⇒ kort recovery, mer normaldrift-overhead. I praksis kjører kommersielle systemer fuzzy checkpoint hvert 5–10 minutt eller hver N-te MB logg.

Kort oppsummert

• Recovery garanterer Atomicity (undo) og Durability (redo).
• Winners = committed før krasj. Losers = in-flight ved krasj.
• ARIES = steal/no-force ⇒ trenger både undo- og redo-logging.
• WAL-regelen: log-records på disk før dataside. Force-log-at-commit: synkron logg ved commit.
• CLR gjør undo idempotent. PageLSN på siden følger med.
• Datastrukturer: Transaction Table (aktive Tx) og Dirty Page Table (sider med endringer i buffer).
• ARIES tre faser: Analysis → Redo → Undo. Redo «repeating history» — også fra løsere.
• Fuzzy checkpoint: tar snapshot av TT/DPT uten å blokkere drift.

Du har nå gått gjennom hele kapittel 8. Last igjen oversikten, eller hopp tilbake til alle kapitlene.