Intro og teori

De fire garantiene

ACID står for Atomicity, Consistency, Isolation, Durability — de fire garantiene en transaksjon gir. Det er ikke fire uavhengige funksjoner, men fire måter å beskrive samme grunnløfte: en transaksjon ser ut som en atomisk, varig, alenestående endring av en konsistent database.

Sammenflettede operasjoner

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

• ri(X) — transaksjon i leser dataelement X
• wi(X) — transaksjon i skriver dataelement X
• ci — commit av T_i (transaksjonen erklærer seg ferdig og endringene blir permanente)
• ai — abort av T_i (transaksjonen avbrytes og endringene rulles tilbake)

Når vi vil vise hvilken verdi som skrives, bruker vi notasjonen wi(X = uttrykk) — for eksempel w1(B = B−100) betyr at T1 skriver verdien B−100 til B.

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

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

(I løpetekst skriver vi r1(A) i stedet for r1(A) for å spare plass — det er samme.)

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

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:

Når er to operasjoner i konflikt?

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

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

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

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.

Pensum bruker en presis underklasse — conflict-serializable:

• To historier er konfliktekvivalente hvis de har samme rekkefølge for konfliktoperasjoner.
• En historie er conflict-serializable hvis den er konfliktekvivalent med en eller annen seriell historie.
• Dette er det vi sjekker mekanisk — typisk via en presedensgraf (neste seksjon).

Conflict-serializability impliserer serializability, men ikke omvendt. 2PL (two-phase locking — forklart i 8B) implementerer nettopp conflict-serializability.

Sjekk med presedensgraf

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

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

Eksempel 1 — uten sykel

Schedule H₁: r2(A); r1(B); w2(A); r3(A); w1(B); w3(A); r2(B); w2(B);

Eksempel 2 — med sykel

Schedule H₂: r2(A); r1(B); w2(A); r2(B); r3(A); w1(B); w3(A); w2(B);

Bla gjennom kortene under for å øve på å lese presedensgrafer. Klikk et svaralternativ for å se forklaringen.

Når kan vi angre en abort?

Conflict-serializability handler om resultatet er korrekt hvis ingen aborter. Men aborter skjer hele tiden — deadlock (to transaksjoner som venter på hverandres låser — forklares i 8B), krasj, brukervalg. Spørsmålet er: kan vi rulle tilbake en transaksjon uten å ødelegge committed andre?

«Read-from»-relasjonen

Vi sier at T_j leser fra T_i (skrives Ti → Tj via X) hvis:

1. T_i skriver X (wi(X)),
2. T_j leser X etterpå (rj(X)),
3. og ingen annen transaksjon skriver X mellom disse to operasjonene.

Det er denne relasjonen vi bruker når vi resonnerer om recoverable, cascadeless og strict.

Recoverable schedule

En schedule er recoverable hvis: for hvert par der T_j leser fra T_i, committer T_i før T_j committer. 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» (verdien som lå der før endringen) tilbake.

Bla gjennom kortene for å øve på å klassifisere schedules i hierarkiet Strict ⊂ ACA ⊂ Recoverable. Velg sterkeste klasse schedulen tilhører.

Set-relasjonen mellom schedule-klasser

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

Strict ⊂ ACA ⊂ Recoverable ⊂ Alle schedules

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

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 →