Kapittel 8 · 8B · Forelesning 15

Samtidighet og låser

Notater kap. 16–17. Hvordan databasen faktisk gjennomtvinger isolation når flere transaksjoner går samtidig — uten å bli for treg.

01 · Hvorfor

Klassiske anomalier

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

Dirty read

T2 leser en verdi T1 har skrevet, men ikke committed. Hvis T1 aborter, har T2 jobbet på en fantasi-verdi.

Lost update

T1 og T2 leser samme verdi, modifiserer hver sin kopi, og skriver tilbake. Den som skriver sist «vinner» — den andres oppdatering forsvinner.

Non-repeatable read

T1 leser X to ganger. Mellom de to leseoperasjonene har T2 oppdatert X og committed. T1 ser to ulike verdier i samme transaksjon.

Phantom read

T1 utfører en spørring to ganger. Mellom dem har T2 satt inn en ny rad som matcher predikatet. Den «dukker opp» i andre kjøring.

Eksempel — Lost update

Begge transaksjonene leser samme initial verdi X = 100 og legger til 10:

Steg

r1(X) → 100

r2(X) → 100

w1(X = 110)

w2(X = 110)

X100

Trykk «Neste» for å starte.

Steg 0 / 6

Sjekk · Anomalier

En transaksjon T1 utfører SELECT COUNT(*) FROM ordrer WHERE status='ny' to ganger. Mellom de to kjøringene har T2 satt inn en ny ordre med status='ny'. Hvilken anomali er dette?

ADirty read

BLost update

CNon-repeatable read

DPhantom read

Phantom. Phantoms oppstår når et nytt rad-sett dukker opp på grunn av en INSERT (eller forsvinner pga. DELETE) som matcher T1 sitt predikat. Non-repeatable read handler om at en eksisterende rad endrer verdi mellom to SELECT-er. Forskjellen er hva slags låsing som trengs: phantoms krever predikat-/range-låser, ikke bare radlåser.

02 · Låser

Shared og exclusive

Den enkleste mekanismen mot anomaliene: tving transaksjonene til å ta låser 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:

Holder lås på X		Vil sette lås
Holder lås på X		S	X
Eksisterende	S	✓	✗
Eksisterende	X	✗	✗

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 til lås frigjøres.

03 · 2PL

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.

2PL: antall holdte låser øker monotont til lock point, deretter avtar monotont. Aldri vri.

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.

Sjekk · 2PL

En transaksjon T1 tar S-lås på A, leser A, slipper S-låsen, og prøver så å ta X-lås på B. Følger T1 2PL?

AJa, så lenge alle låser slippes til slutt

BNei — T1 slapp en lås før den tok en ny, brudd på vokse/krympe-regelen

CJa, fordi det var ulike dataelementer

DNei — S-låser kan ikke slippes før commit

Brudd på 2PL. Vokse/krympe-regelen sier: så snart en lås er sluppet, kan ingen ny lås tas. Det betyr ikke noe at det er ulike data eller ulike låstyper. (Strict 2PL er enda strengere: X-låser må holdes til commit/abort.)

04 · Varianter

Fire smaker av 2PL

Variant	Når slippes låser?	Egenskaper
Basic 2PL	Når som helst etter peak — så lenge regelen holder.	Conflict-serializable. Ikke nødvendigvis cascadeless.
Conservative 2PL	Alle låser tas på forhånd, før første operasjon.	Deadlock-fri (alle Tx venter eller starter), men dårlig samtidighet.
Strict 2PL	X-låser holdes til commit/abort. S-låser kan slippes tidligere.	Conflict-serializable + strict schedule. Standard i praksis.
Rigorous 2PL	Alle låser holdes til commit/abort.	Enklest å implementere. Litt mindre samtidighet enn strict.

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

05 · Deadlock

Når begge venter på hverandre

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

Steg

read_lock(X) ✓

read_lock(Y) ✓

write_lock(Y) — venter på T2

write_lock(X) — venter på T1

⌛ deadlock

Wait-for-graf

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

Sykel i wait-for-grafen ⇒ deadlock. Eneste vei ut: abort en av transaksjonene.

Tre strategier

Forebygging — conservative 2PL (alle låser opp foran), eller rangér ressurser globalt så alle tar låser i samme rekkefølge.
Deteksjon + offer — periodisk sjekk wait-for-grafen; finn sykel; abort en transaksjon (ofte den yngste eller den som har gjort minst).
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.

Sjekk · Deadlock

Hvilken 2PL-variant garanterer at deadlocks aldri oppstår?

AStrict 2PL

BRigorous 2PL

CConservative 2PL

DBasic 2PL

Conservative. Ved at alle låser tas før transaksjonen begynner — om noen er opptatt, venter T-en før den i det hele tatt har startet, uten å holde noe selv. Dermed kan ikke en sirkulær venting oppstå. Prisen er at samtidigheten lider og at det er vanskelig å vite hvilke låser som trengs på forhånd.

06 · Granularitet

Hva låser vi egentlig?

Et dataelement i 2PL-teori. I virkeligheten har vi et hierarki av muligheter:

Hierarki: hele DB → tabell → side → record. Lav granularitet = mindre overhead, høy granularitet = mindre kontensjon.

Trade-off:

Coarse (tabell-lås) — lite metadata å holde, men én skribent stenger ute alle.
Fine (record-lås) — høy samtidighet, men låsetabellen blir stor og dyr.

Intent locks (IS, IX, SIX) brukes for å varsle at en transaksjon vil ha finer-granular låser i underliggende noder, slik at konflikter kan oppdages tidlig på høyere nivå uten å sjekke alle barn.

07 · MVCC

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.

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.

MVCC: X eksisterer som en kjede av versjoner. En lese-transaksjon ser den versjonen som var committed da den startet — selv om andre committer nye versjoner i mellomtiden.

Reads låser ikke writes, og writes låser ikke reads. Bare write/write-konflikter krever låsing eller (i optimistic varianter) 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.

Snapshot ≠ serializable

Snapshot isolation hindrer dirty/non-repeatable/phantom reads, men har sin egen anomali — write skew: to transaksjoner leser overlappende sett, hver skriver inn i sitt eget delsett basert på det den leste, og resultatet er inkonsistent. PostgreSQL «Serializable Snapshot Isolation» (SSI) løser det med ekstra konflikt-deteksjon.

08 · SQL-standard

Fire isolation levels

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

Level	Dirty read	Non-repeatable	Phantom	Typisk implementasjon
READ UNCOMMITTED	Ja	Ja	Ja	Ingen leselåser
READ COMMITTED	Nei	Ja	Ja	X-låser, korte S-låser, eller snapshot
REPEATABLE READ	Nei	Nei	Avhenger	Strict 2PL på leste rader, eller snapshot
SERIALIZABLE	Nei	Nei	Nei	Strict 2PL m. range-låser, eller SSI

«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; SERIALIZABLE er SSI.
MySQL InnoDB sin REPEATABLE READ tillater phantoms i noen tilfeller.

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

Sjekk · Isolation

Du driver et nettbutikk-system og vil unngå at én kunde leser saldoen sin to ganger og får ulike svar (selv om andre kan sette inn nye rader). Hvilket isolation level er minimum?

AREAD UNCOMMITTED

BREAD COMMITTED

CREPEATABLE READ

DSERIALIZABLE

REPEATABLE READ. Spørsmålet beskriver presist non-repeatable read. REPEATABLE READ er det laveste nivået som hindrer det. Phantoms ble eksplisitt sagt at vi tolererer, så SERIALIZABLE ville vært overkill.

09 · Oppsummering

Kort oppsummert

Fire klassiske anomalier: dirty read, lost update, non-repeatable read, 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 →