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 rediger
Et eksempel på en feilsituasjon kan være hvis en transaksjon Ta 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 Ta X = 10 * 2 = 20. Deretter gjør Tb X = 10 + 2 = 12, som blir stående. Riktig resultat var 22 hvis Ta kom først, eller 24 hvis Tb kom først. Begge de to riktige resultatene oppfyller kravet om serialiserbarhet.
Teori rediger
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 (S1) er konfliktserialiserbar hvis den er konfliktekvivalent med en seriell eksekveringsplan (S2). Konfliktekvivalent betyr at S1 kan omdannes til S2 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 rediger
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.[1]
Multiversjon tidsstempling (MVCC) rediger
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.[2]
Validering rediger
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.[3]
Låser rediger
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.
Vranglås rediger
En vranglås oppstår hvis to ulike transaksjoner venter på hverandre på grunn av låser som blokkerer. En vranglås må løses ved at en av transaksjonene må begynne på nytt. En strategi for å hindre vranglåser er at hver transaksjon har et vranglåstidsstempel (ikke samme som annet tidsstempel).
Vent-dø-strategien er slik at hvis en transaksjon T må vente på en lås som tilhører transaksjon U, så:
- Hvis T er eldre enn U må T vente til U har låst opp.
- Hvis T er yngre enn U dør T og må starte helt på nytt.
Skad-dø-strategien:
- Hvis T er eldre enn U skades U og må starte på nytt hvis den ikke er i krympefasen.
- Hvis T er yngre enn U må T vente til U har låst opp
Hvis man tegner en vranglås-presedensgraf kan man enkelt se vranglåser som sykler på grafen.
Presedensgraf rediger
En presedensgraf er et verktøy for å undersøke serialiserbarheten til en eksekveringsplan. Hvis en presedensgraf ikke har "løkker", eller sykler, er den konfliktserialiserbar. Hvis to eksekveringsplaner er konfliktekvivalente har de like presedensgrafer, men to eksekveringsplaner kan ha like presedensgrafer uten å være konfliktekvivalente.
Presedensgrafen har:
- En node for hver utførte transaksjon i eksekveringsplanen.
- En pil fra Ti til Tj hvis noe av det Ti gjør skjer før og er i konflikt med noe av det Tj gjør.
Sistnevnte gjelder hvis en av transaksjonene inneholder en skriveoperasjon.
R står for leseoperasjon, W står for skriveoperasjon. Her vises tre transaksjoner (T1 både leser og skriver). Siden det dannes en "løkke", eller en sykel, er denne eksekveringsplanen ikke konfliktserialiserbar. Årsaken til dette er at T2 skriver A etter at T1 har lest den, og deretter skriver T1 til A. Dette kan gi et annet resultat enn en seriell eksekvering.
Isolasjonsnivå rediger
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.[4]
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".
Referanser rediger
- ^ Rusinkiewicz, Marek: Lecture 13: Transaction Management Arkivert 14. februar 2009 hos Wayback Machine. 27.10.1997
- ^ PostgreSQL 8.2.11 Documentation Chapter 12. Concurrency Control 2006
- ^ Normann, Ragnar: Transaksjonshåndtering del 2 (Lysark) INF3100, Universitetet i Oslo, mars 2008
- ^ Kyte, Tom: Ask Tom – On Transaction Isolation Levels