Kapittel 8 · 8A · Forelesning 14

Intro og teori

Notater kap. 15–16. Vokabularet for resten av kapittelet — ACID, schedules, conflict-serializability og recoverability. Klikk deg gjennom eksemplene.

01 · ACID

De fire garantiene

ACID er ikke fire uavhengige funksjoner — det er fire måter å beskrive samme grunnløfte: en transaksjon ser ut som en atomisk, varig, alenestående endring av en konsistent database.

Bokstav	Egenskap	Hva den lover	Hvem leverer
A	Atomicity	Alle stegene gjennomføres, eller ingen. Ingen «halvferdige» transaksjoner kan observeres etterpå.	Recovery (undo)
C	Consistency	Hver transaksjon tar databasen fra én lovlig tilstand til en annen — PK, FK, CHECK osv. holder.	SQL-modellen + bruker
I	Isolation	Selv om mange kjører samtidig, skal effekten være som en eller annen seriell rekkefølge.	Concurrency control (8B)
D	Durability	Etter `COMMIT` overlever resultatet alt — strømbrudd, krasj, OS-kill.	WAL + redo (8C)

Merk

«Consistency» har to betydninger i kurset. I ACID handler det om brukerens integritetskrav. I concurrency control brukes det også om at samtidige effekter er konsistente (samme som serielle). Forelesningen følger første betydning.

Sjekk forståelsen · ACID

En transaksjon overfører 100 kr fra konto A til B. Maskinen krasjer rett etter at A er trukket, men før B er kreditert. Etter recovery er A og B begge tilbake til startverdiene. Hvilken egenskap er nettopp demonstrert?

AAtomicity — alt-eller-ingenting holdt selv ved krasj

BConsistency — saldoen er konsistent

CIsolation — ingen andre så halvferdig overføring

DDurability — endringene overlevde

Atomicity. Recovery rullet tilbake en halvferdig transaksjon — det er definisjonen av «alt eller ingenting». Durability ville handlet om at en committed overføring overlevde. Konsistens følger som konsekvens, men er ikke det som ble demonstrert direkte.

02 · Schedule

Sammenflettede operasjoner

For å kunne snakke matematisk om hva som er lov og ulovlig, abstraherer vi vekk SQL og ser bare på fire operasjoner:

r_i(X) — transaksjon i leser dataelement X
w_i(X) — transaksjon i skriver dataelement X
c_i — commit av T_i
a_i — abort av T_i

En schedule (eller historie) er en sekvens av slike operasjoner fra én eller flere transaksjoner. Seriell schedule = ingen interleaving (én transaksjon helt ferdig før neste begynner).

Seriell:        r1(A); w1(A); c1; r2(A); w2(A); c2;
Interleaved:    r1(A); r2(A); w1(A); w2(A); c1; c2;

Spørsmålet hele dette kapittelet handler om: hvilke interleavede schedules er trygge — det vil si gir samme resultat som en eller annen seriell?

03 · Eksempel

Bankoverføring vs. renteberegning

To transaksjoner kjører samtidig på kontoer A og B (start: A=200, B=100):

T1 — overfør 100 fra B til A: r1(B); w1(B = B−100); r1(A); w1(A = A+100); c1;
T2 — gi 6 % rente på begge: r2(A); w2(A = A·1.06); r2(B); w2(B = B·1.06); c2;

Avhengig av flettingen kan resultatet bli riktig (samme som T1;T2 eller T2;T1) — eller helt feil. Klikk gjennom problemet under:

Steg

T1 — overfør

T2 — rente

r₁(B) → 100

w₁(B = 0)

r₂(A) → 200

w₂(A = 212)

r₂(B) → 0

w₂(B = 0)

c₂

r₁(A) → 212

w₁(A = 312)

c₁

Konto A200

Konto B100

Trykk «Neste» for å starte.

Steg 0 / 10

Sjekk · Bankeksempel

I steget over ble «overføringens andre halvdel» (innskuddet på A) klemt mellom T2 sine to operasjoner. Hva er navnet på selve fenomenet — at T2 så A før T1 var ferdig?

ADirty read

BInkonsistent / feil resultat — schedulen er ikke serializable

CPhantom read

DLost update

Ikke-serializable. «Dirty read» ville krevd at T2 leste en uncommitted verdi fra T1 — her leste T2 bare gamle (committed) verdier. Likevel er resultatet ikke ekvivalent med noen seriell ordning. Vi skal lære navnet på de spesifikke anomaliene i 8B; her holder det å se at noe er galt.

04 · Conflict

Når er to operasjoner i konflikt?

Tre vilkår, alle må være oppfylt:

De tilhører ulike transaksjoner.
De berører samme dataelement.
Minst én av dem er en write.

Par	I konflikt?	Grunn
`r₁(X), r₂(X)`	Nei	Begge leser — å bytte rekkefølge endrer ingenting.
`r₁(X), w₂(X)`	Ja	T1 ser ulike verdier avhengig av rekkefølge.
`w₁(X), r₂(X)`	Ja	Samme grunn motsatt vei.
`w₁(X), w₂(X)`	Ja	Sluttverdien er forskjellig.
`r₁(X), w₂(Y)`	Nei	Ulike dataelementer, helt uavhengige.
`r₁(X), w₁(X)`	Nei	Samme transaksjon — ikke en konflikt mellom transaksjoner.

Intuisjonen: to operasjoner er i konflikt hvis det å bytte rekkefølgen kan gi et annet resultat på databasen.

Tenk selv · Konflikt

Hvor mange par er i konflikt i schedulen r1(A); w2(A); w1(A); r2(B); c1; c2;? List dem.

To par.

r1(A) ↔ w2(A) — ulike Tx, samme element, én er write.
w2(A) ↔ w1(A) — to writes på samme element.

r2(B) er alene om B, så ingen konflikt med noe annet. Commits er ikke operasjoner på dataelementer.

05 · Serializability

Ekvivalent med en seriell

En schedule er serializable hvis det finnes en seriell schedule med samme effekt på databasen. Vi vil ha serializable, ikke seriell — fordi vi vil ha samtidighet uten å gi opp korrekthet.

To viktige underklasser:

Conflict-serializable — kan omformes til en seriell ved å bytte om nabo-operasjoner som ikke er i konflikt. Strengere, men billig å sjekke (precedence-graf).
View-serializable — schedulen leser og produserer samme final-state som en seriell. Mer permissiv, men NP-hardt å avgjøre i alminnelighet.

I praksis brukes conflict-serializability overalt fordi 2PL (kapittel 8B) implementerer akkurat den.

Conflict-serializable ⇒ View-serializable ⇒ Serializable. Motsatt vei holder ikke.

06 · Algoritmen

Sjekk med presedensgraf

Resepten for å avgjøre om en schedule er conflict-serializable:

Lag én node per transaksjon.
For hvert konfliktpar — hvis T_i sin operasjon kommer før T_j sin, tegn en pil T_i → T_j.
Acyclic graf ⇔ schedule er conflict-serializable. En topologisk sortering gir den ekvivalente serielle rekkefølgen.

Eksempel 1 — uten sykel

Schedule H₁: r₂(A); r₁(B); w₂(A); r₃(A); w₁(B); w₃(A); r₂(B); w₂(B);

Klikk «Vis neste konflikt» for å bygge grafen steg for steg:

r2(A) r1(B) w2(A) — konflikt med r2(A)? nei (samme Tx) r3(A) — konflikt med w2(A): T2→T3 w1(B) — w1(B) konfliktbygger med kommende r2(B): T1→T2 w3(A) — konflikter med r2(A), w2(A) men disse er allerede dekket r2(B) — leser etter w1(B): T1→T2 (allerede) w2(B)

Resultat: T1 → T2 → T3. Ingen sykel — schedulen er conflict-serializable, ekvivalent med seriell T1; T2; T3.

Acyclic ✓ — graf har ingen sykel. H₁ er conflict-serializable, og topologisk sortering gir serielle ordning T1; T2; T3.

Eksempel 2 — med sykel

Schedule H₂: r₂(A); r₁(B); w₂(A); r₂(B); r₃(A); w₁(B); w₃(A); w₂(B);

Sykel T1 → T3 → T2 → T1. Ikke conflict-serializable. Ingen seriell ordning gir samme resultat.

Sjekk · Presedensgraf

En presedensgraf for fire transaksjoner har kanter T1→T2, T2→T3, T3→T4, T4→T1. Hva betyr dette?

ASchedulen er conflict-serializable; ordningen er T1, T2, T3, T4

BDet er en sykel — schedulen er ikke conflict-serializable

CSchedulen er view-serializable men ikke conflict-serializable

DDet betyr at minst to transaksjoner må aborteres

Sykel ⇒ ikke conflict-serializable. Vi kan ikke topologisk sortere en syklisk graf. Det betyr ikke automatisk at noen må aborteres — det betyr bare at denne schedulen ikke er ekvivalent med en seriell. Schedulen skal forhindres på forhånd (typisk av 2PL).

07 · Recoverability

Når kan vi angre en abort?

Conflict-serializability handler om resultatet er korrekt hvis ingen aborter. Men aborter skjer hele tiden — deadlocks, krasj, brukervalg. Spørsmålet er: kan vi rulle tilbake en transaksjon uten å ødelegge committed andre?

Recoverable schedule

En schedule er recoverable hvis hver transaksjon T_j som har lest fra T_i, committer etter T_i. Da kan vi alltid rulle tilbake T_i sammen med T_j hvis T_i aborter.

Recoverable:    w1(A); w1(B); r2(A); c1; c2;
Ikke-recoverable: w1(A); w1(B); r2(A); c2; c1;     ← T2 har committed på T1's data, men T1 kan fortsatt aborte!

Avoid Cascading Aborts (ACA / cascadeless)

En sterkere garanti: en transaksjon leser bare committed verdier. Da slipper vi cascading aborts — situasjoner der én abort tvinger frem flere.

Strict

Sterkest: en transaksjon kan verken lese eller skrive over uncommitted verdier. Dette gjør undo trivielt — vi kan rulle tilbake bare ved å skrive «before-image» tilbake.

Tenk selv · Recoverable

Schedule: w1(A); w2(A); c1; c2; — er den recoverable? Cascadeless? Strict?

Recoverable: Ja. T2 leste ikke noe fra T1 — T2 skrev bare. Recoverable trenger bare commit-rekkefølgen for read-from.
Cascadeless: Ja, av samme grunn — T2 leste ingenting uncommitted.
Strict: Nei. T2 skrev over en uncommitted verdi (w1(A)). Hvis T1 aborterer, kan vi ikke gjenopprette w1(A) ved bare å bruke before-image — T2 har allerede skrevet på toppen.

08 · Hierarkiet

Set-relasjonen mellom schedule-klasser

Klassene former et strengt hierarki — strengere lenger ned betyr færre tillatte schedules, mer trygghet, men også mindre samtidighet.

Alle schedulesmatematisk univers
Recoverableaborter ødelegger ikke committed Tx
Cascadeless (ACA)les bare committed verdier
Strictverken les eller overskriv uncommitted

Strict ⊂ ACA ⊂ Recoverable ⊂ Alle schedules

Tilsvarende har vi for samtidighet: Seriell ⊂ Conflict-serializable ⊂ View-serializable ⊂ Alle schedules. De to hierarkiene er ortogonale — recoverability handler om aborter, serializability om samtidighet.

Sjekk · Hierarki

Hvilken kombinasjon vil de fleste kommersielle SQL-databaser i praksis garantere?

ASeriell + recoverable

BConflict-serializable + strict (eller cascadeless)

CView-serializable + recoverable

DAlle schedules + strict

Conflict-serializable + strict. Strict 2PL (kapittel 8B) gir akkurat denne kombinasjonen automatisk: 2PL ⇒ conflict-serializable, og «hold X-låser til commit/abort» ⇒ strict. View-serializable er teoretisk større, men i praksis ikke verdt kompleksiteten å detektere.

09 · Oppsummering

Kort oppsummert

ACID = Atomicity, Consistency, Isolation, Durability. Fire garantier som henger sammen.
En schedule er en sekvens av r/w/c/a-operasjoner fra flere transaksjoner.
To operasjoner er i konflikt hvis de tilhører ulike Tx, samme element, og minst én er write.
Conflict-serializable = kan omformes til seriell ved å bytte ikke-konflikt-naboer ⇔ presedensgraf er acyklisk.
Recoverable ⊃ cascadeless (ACA) ⊃ strict. Strict gjør undo trivielt.
Praksisstandard: conflict-serializable + strict — leveres «gratis» av strict 2PL.

Klar for neste? 8B · Samtidighet og låser →