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: hvis maskinen krasjer igjen midt under recovery, skal det å starte recovery på nytt fortsatt gi riktig resultat. Det er CLR-ene (kapittel 06 her) 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-loggrecorden 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:

• 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 buffer-slot stjeles fra en uavsluttet transaksjon (skrives til disk)?
  • Ja (steal) — fleksibel buffer-bruk, men trenger undo for halvskrevne sider.
  • Nei (no-steal) — uavsluttede sider holdes i buffer til commit. Begrenset.

ARIES 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 fil på en egen disk. Hvert log-record har en monotont voksende LSN (Log Sequence Number).

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 log-records 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 log-record, skriver vi en ny log-record som beskriver «jeg har angret den endringen». Den heter en CLR (Compensating Log Record). PageLSN på siden oppdateres til CLR-ens LSN.

Egenskaper:

• CLR-er er redo-only — de undoes aldri.
• De har et UndoNextLSN-felt som peker til det neste som skal undoes (forbi den vi nettopp angret).
• Hvis krasj skjer under undo, kan vi gjenkjenne CLR-er ved restart og hoppe rett til der vi var.

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

Det ARIES holder rede på

To tabeller i RAM (kopieres til logg ved sjekkpunkter):

Transaction Table (TT)

Én rad per aktiv transaksjon. Inneholder:

• TransID
• Status — active / committed / aborted
• LastLSN — siste log-record 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 log-record 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:

Analysis i praksis

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

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.

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.

Fuzzy checkpoint (ARIES)

1. Skriv begin_checkpoint-record.
2. Skriv en end_checkpoint-record som inneholder snapshot av TT og DPT akkurat nå.
3. Oppdater log anchor (et lite, fast sted på disk) 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.

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.