Serialiserbarhet

Serialiserbarhet er et uttrykk som brukes i databasesystemer og transaksjonsprosessering. Serialiserbar betyr at en historie utføres på en slik måte at det finnes en seriell utførelse som ville gitt samme resultat. Serialiserbarhet er nært knyttet til kravet om isolasjon i databaser.
Hvis transaksjonen skjer serielt, hver operasjon starter og avsluttes før neste begynner, gir dette seg selv. Men i praksis går det raskere hvis mange transaksjoner skjer parallelt, og derfor støtter de fleste databasesystemer dette. Dette betyr ikke at resultatet av en seriell utføring er uavhengig av rekkefølgen den skjer i. Rekkefølgen kan ha stor betydning for resultatet, men parallell behandling skal ikke føre til at forskjellige operasjoner blandes sammen og gir uventede resultater. En serie av transaksjoner i en fastsatt rekkefølge kalles en eksekveringsplan. 
Noen strategier man kan bruke for å sikre at en eksekveringsplan er serialiserbare er tidsstempling, versjonering og bruk av låser. Man kan teste en eksekveringsplan i etterkant eller forkant ved hjelp av en presedensgraf.

Feilsituasjon

Et eksempel på en feilsituasjon kan være hvis en transaksjon Tₐ skal gjøre X * 2 og det samtidig går en transaksjon Tb som skal gjøre X + 2. Anta at begge leser X = 10. Så gjør Tₐ X = 10 * 2 = 20. Deretter gjør Tb X = 10 + 2 = 12, som blir stående. Riktig resultat var 22 hvis Tₐ kom først, eller 24 hvis Tb kom først. Begge de to riktige resultatene oppfyller kravet om serialiserbarhet.

Teori

Man opererer med to former for serialiserbarhet: viewserialiserbar og konfliktserialiserbar. 
Viewserialiserbarhet innebærer at alle transaksjoner leser og skriver samme data som i en seriell utførelse. Å håndheve viewserialiserbarhet er et NP-komplett problem, det vil si at for større datamengder er det ikke mulig med en eksisterende algoritme.
Man opererer derfor med konfliktserialiserbarhet. En eksekveringsplan (S₁) er konfliktserialiserbar hvis den er konfliktekvivalent med en seriell eksekveringsplan (S₂). Konfliktekvivalent betyr at S₁ kan omdannes til S₂  ved å bytte om plassene på operasjoner som ikke er i konflikt med hverandre. To operasjoner er i konflikt med hverandre hvis de behandler samme data og minst en av dem er en skriveoperasjon. 
En konfliktersialiserbar eksekveringsplan er alltid viewserialiserbar, men det finnes viewserialiserbare eksekveringplaner som ikke er konfliktserialiserbare. Ulikeheten på de to formene for serialiserbarhet kommer frem når en operasjon skriver i et attributt uten å lese det først. Hvis dette skjer spiller det ingen rolle om attributtet har blitt endret siden transaksjonen startet, dette tas ikke høyde for i konfliktserialiserbarhet. Hvis man legger inn et krav om at alle operasjoner skal lese enhver verdi som de skriver på, blir de to begrepene ekvivalente.

Tidsstempling

Hvis alle transaksjoner merkes med et tidspunkt eller et transaksjonsnummer når de begynner, kan man skape serialiserbarhet basert på starttidspunktet til transaksjonene. Databasesystemet må da, for alle verdier i databasen, følge med når siste lesing skjedde, når siste skriving skjedde og om den siste transaksjonen som skrev er ferdig utført. Hvis noen transaksjoner blir "forsinket", slik at operasjoner som skulle ha skjedd etterpå rekker dem i forkjøpet, må de oppheves og starte på nytt med et nytt tidsstempel.
En problemstilling knyttet til slike metoder er man kan få kaskadetilbakerullinger. Det vil si at det at en operasjon oppheves fører til at neste oppheves og så videre. En ACR-eksekveringsplan (Avoid Cascade Rollback) sikrer mot dette ved å sørge for at ingen transaksjoner kan lese data fra bekreftede (commit) transaksjoner.

Multiversjon tidsstempling (MVCC)

Versjonering vil si at for hver skriveoperasjon lagres den gamle verdien av attributtet med et tidsstempel. Da kan transaksjoner alltid lese den verdien som er riktig i forhold til sitt eget tidsstempel. Transaksjonene kan imidlertid ikke skrive hvis noen annen transaksjon har lest verdien av attributtet på et "senere" tidsstempel. Da må hele transaksjonen starte på nytt.
Implementeringen av dette kalles Snapshot Isolation (SI) og er allment brukt i kommersielle databasesystemer. Snapshot Isolation gir høy ytelse, men kan ikke garantere 100% serialiserbarhet. Vanligvis vil imidlertid SI være tilstrekkelig serialiserbart.

Validering

Validering er en form for tidsstempling, men istedenfor at det lagres tidsstempel for alle attributter lagrer man det som leses og skrives av alle aktive transaksjoner. Transaksjoner deles da opp i tre faser – lesefasen, valideringsfasen og skrivefasen.

Låser

Låser er en mekanisme som gjør at en transaksjon kan sperre de data den arbeider med slik at andre transaksjoner ikke kan forstyrre. Leselåser (Shared locks) tillater andre transaksjoner å lese elementet, men ikke å endre det. Skrivelåser (exclusive lock) sperrer all annen tilgang til elementet – en transaksjon kan ikke få eksklusiv lås så lenge det finnes andre transaksjoner som har noe lås på elementet. En inkrementlås kan brukes når to skriveoperasjoner ikke er i konflikt, for eksempel hvis man har to addisjoner til samme element. 
Man har en strikt låseregel hvis transaksjoner ikke kan slippe skrivelåser før den er ferdig og validert. En strikt eksekveringsplan er serialiserbar fordi den er ekvivalent med den serielle planen vi får hvis vi tenker oss at alle transaksjoner skjer i det øyeblikket de er bekreftet.
2PL (two phase locking) er en metode som sikrer serialiserbarhet. I 2PL gjelder at en transaksjon som har låst opp et element ikke får utføre flere låsinger. Alle transaksjoner får da to faser – voksefasen, der de setter alle nødvendige låser, og krympefasen, der de fjerner låsene. 2PL er egnet når man arbeider med data på tabellform.
Treprotokollen er egnet til å sikre serialiserbarhet i trær. Treprotokollen begynner med å låse elementet øverst i treet, og så går den nedover. For hvert trinn låser den opp elementet den forlater, helt til den kommer til elementer som den skal endre.

Isolasjonsnivå

Det koster kapasitet å sikre serialiserbarhet, og i mange situasjoner er det ikke så viktig at alle transaksjoner er 100% serialiserbare. Derfor opererer man med ulike isolasjonsnivåer. 
I SQL opererer man med fire ulike nivåer av serialiserbarhetskrav: serializable, repeatable read, read committed og read uncommitted.
Mange av de mest utbredte databasesystemene har ikke noe funksjon for total serialiserbarhet. Det finnes med andre ord situasjoner der systemet ikke greier å ivareta dette kravet selv om operasjonen er satt til "serializable".