Samtidighet og låser

Klassiske anomalier

Før vi snakker om låser, må vi se hva som går galt uten dem. Disse fem mønstrene er årsaken til at samtidighetskontroll (concurrency control) finnes.

Eksempel — Lost update

Konto X = 100. T1 vil legge til 50, T2 vil legge til 30. Begge leser X først, regner ut, og skriver tilbake:

T1: r1(X=100) ............... w1(X=150) ; c1
T2: ......... r2(X=100) ; w2(X=130) ; c2 ............

Sluttverdi: X = 150 (T1 sin skriving overskriver T2 sin) — eller 130 om rekkefølgen er motsatt. Riktig svar var 180. Begge oppdateringer leste samme «gamle» X = 100, og én av dem ble effektivt slettet. Det skjer fordi ingen lås beskytter read-modify-write-sekvensen.

Eksempel — Dirty write

To transaksjoner registrerer samme salg, men fletter operasjonene slik at buyer og invoice ender opp ulike — Bob får varen, Alice får regningen:

Shared og exclusive

Den enkleste mekanismen mot anomaliene: tving transaksjonene til å ta låser (markører som reserverer et dataelement for transaksjonen) før de leser/skriver, og slipp dem etterpå.

• Shared (S, read lock) — flere transaksjoner kan holde S-lås på samme element samtidig.
• Exclusive (X, write lock) — bare én transaksjon kan holde X-lås, og ingen andre kan ha S-lås samtidig.

Forholdet mellom dem oppsummeres i kompatibilitetsmatrisen:

Tommelfingerregel: writers lockes ut alle. Readers tolererer hverandre.

Låser administreres av en låstabell i RAM. Hver aktiv transaksjon har en oppføring som peker til de låsene den allerede holder («has locks») og de den venter på («wants locks»). Operasjoner som må vente blir blokkert (settes på vent til lås kan tildeles).

Two-phase locking

Bare det å bruke S/X-låser er ikke nok. Det er hvordan vi tar og slipper låsene som gir korrekthet:

2PL-regelen: Alle låser tas i en vokse-fase; så snart første lås er sluppet, går transaksjonen over til en krympe-fase hvor den bare kan slippe.

Resultatet ligner et fjell — låstellet vokser, peaker, og krymper. Aldri «tilbake opp» etter første unlock.

Hovedteorem: Hvis alle transaksjoner følger 2PL, er enhver schedule de produserer conflict-serializable. Det er grunnen til at 2PL er den de-facto standarden.

Hvorfor virker det?

Tenk: hvis en kant T_i→T_j finnes i presedensgrafen (T_i hadde en konfliktende op før T_j), må T_i ha sluppet sin lås før T_j tok sin. Hvis det også var en kant T_j→T_i, måtte T_i ha sluppet, deretter tatt en ny lås — brudd på 2PL. Altså: 2PL ⇒ ingen sykler ⇒ conflict-serializable.

Fire smaker av 2PL

I praksis bruker de fleste databaser strict 2PL eller rigorous 2PL — fordi de gjør recovery (gjenoppretting etter krasj — kapittel 8C) enkel (undo via before-image fungerer). Basic 2PL er teoretisk korrekt, men gir cascading aborts.

Profilene visualisert

Hver variant har en distinkt form når man plotter antall holdte låser over tid. Den blå kurven er låstellet; den brune prikken merker commit:

Gjennomgått eksempel — rigorous 2PL i sekvens

Vi setter låser med rigorous 2PL for følgende sekvens som kommer inn til databasen, og finner ut i hvilken rekkefølge transaksjonene committer:

r1(A); r2(A); w1(A); r3(B); c1; w2(B); c2; r3(C); c3;

Regel ved blokkering: hvis en transaksjon blokkeres på en lås, settes alle dens videre operasjoner på vent — neste operasjon i sekvensen utføres som vanlig. (Dette er hva pensumnotatet kaller «de neste operasjonene i historien blir utført i sekvens».)

Commit-rekkefølge: T3 → T2 → T1. Det er motsatt rekkefølge av hvordan de først dukket opp i sekvensen — typisk for kjeder av blokkeringer: den siste i kjeden er ikke blokkert av noen og frigjør de andre én etter én.

Bla gjennom kortene under for å sjekke at du skiller variantene fra hverandre — og at du kan lese rigorous-2PL-eksempler.

Når begge venter på hverandre

Prisen for låser: noen ganger venter to transaksjoner på hverandre samtidig. Klassisk eksempel:

(Notasjon: read_lock(X) = «be om S-lås på X», write_lock(X) = «be om X-lås på X». ✓ betyr lås tildelt.)

Wait-for-graf

Tegn en kant T_i → T_j hvis T_i venter på en lås T_j holder. Sykel ⇔ deadlock.

Tre strategier

1. Forebygging (unngåelse) — conservative 2PL (alle låser opp foran), eller rangér ressurser globalt så alle tar låser i samme rekkefølge.
2. Deteksjon + offer — periodisk sjekk wait-for-grafen; finn sykel; abort en transaksjon (ofte den yngste eller den som har gjort minst).
3. Timeout — om en transaksjon ikke fullfører innen X sekunder, abort. Enkelt, men vanskelig å sette gode timeouts.

De fleste kommersielle systemer (PostgreSQL, MySQL/InnoDB) bruker en kombinasjon av deteksjon og timeout.

Lock upgrade — en stille deadlock-felle

Pensum nevner at låser kan oppgraderes (read_lock → write_lock) og nedgraderes. En typisk oppskrift: T1 leser X (tar read_lock(X)), regner litt, og bestemmer seg for å skrive — den ber om oppgradering til write_lock(X). Men hvis T2 også holder read_lock(X) og samtidig ber om oppgradering, sitter begge og venter på at den andre skal slippe sin S-lås — deadlock:

T1: read_lock(X) ........... write_lock(X)  ← venter på T2
T2: ......... read_lock(X) . write_lock(X)  ← venter på T1
                                  DEADLOCK

Begge T-ene følger 2PL korrekt. Likevel havner de i sykel — dette er en vanlig årsak til deadlock i praksis selv når ingen «øyeblikkelig» konflikt foreligger ved den initielle låsingen.

Hva låser vi egentlig?

Granularitet = hvor stort eller lite område én lås dekker. I 2PL-teori snakker vi om «et dataelement», men i virkeligheten har vi et hierarki av muligheter:

Pensum lister fem typer låser:

• Postlåser — fineste granularitet, høy samtidighet, men stor låsetabell.
• Blokklåser — én lås dekker alle records i blokken.
• Tabellåser — coarse: én skribent stenger ute alle.
• Range-/verdiområdelåser — låser et nøkkelintervall, brukes for å unngå fantomer.
• Predikatlåser — låser alle rader som matcher et predikat. Også for fantomer, mer presis enn range-låser.

Moderne databaser bruker typisk post- og range-låser. Trade-off er klart: grovere granularitet ⇒ mindre metadata, men mer konkurranse om de samme låsene. Finere granularitet ⇒ mer samtidighet, men dyrere lock manager.

Multi-version concurrency control

Problem med rene låser: en read blokkerer en write og omvendt. Det betyr at en lang rapporterings-spørring kan stenge ute hele OLTP-traffikken (Online Transaction Processing — vanlige korte forretningstransaksjoner).

MVCC (også kalt snapshot isolation) løser dette ved å la hver write lage en ny versjon i stedet for å overskrive. Reads ser et konsistent øyeblikksbilde fra et bestemt tidspunkt — typisk transaksjonens starttid.

Reads låser ikke writes, og writes låser ikke reads. Bare write/write-konflikter krever låsing eller (i optimistiske varianter — der vi lar transaksjoner kjøre fritt og sjekker konflikter ved commit) abort av en transaksjon ved commit hvis det er konflikt.

PostgreSQL, Oracle, SQL Server (RCSI), MySQL/InnoDB — alle bruker MVCC. Det er de-facto i moderne SQL.

Fire isolation levels

SQL-standarden definerer fire nivåer i henhold til hvilke anomalier som kan forekomme:

«Nivå» = strengere lenger ned. Mer korrekthet, mindre samtidighet.

Standard vs. virkelighet

Standarden er stort sett ikke fulgt i detaljer av leverandørene:

• Oracle har ingen «REPEATABLE READ» — SERIALIZABLE er egentlig snapshot isolation.
• PostgreSQL sin REPEATABLE READ er snapshot isolation.
• MySQL InnoDB sin REPEATABLE READ tillater phantoms i noen tilfeller.

Tommelfingerregel: les dokumentasjonen til din database før du stoler på navnet.

Kort oppsummert

• Klassiske anomalier: dirty read, dirty write, unrepeatable read, incorrect summary, phantom.
• S/X-låser + kompatibilitetsmatrise styrer tilgang.
• 2PL (vokse-fase, krympe-fase) garanterer conflict-serializability.
• Strict 2PL = standard i praksis: X-låser holdes til commit, gir cascadeless.
• Deadlock = sykel i wait-for-graf. Løsninger: forebygging, deteksjon, timeout.
• Granularitet: tabell ↔ side ↔ record. Trade-off mellom kontensjon og overhead.
• MVCC / snapshot isolation: writers låser ikke readers og omvendt. Standard i moderne SQL.
• SQL isolation levels: READ UNCOMMITTED → READ COMMITTED → REPEATABLE READ → SERIALIZABLE. Sjekk hva din DB faktisk leverer.

Klar for siste etappe? 8C · Recovery →