Redigerer Serialiserbarhet

'''Serialiserbarhet''' er et uttrykk som brukes i [[database]]systemer og transaksjonsprosessering. ''Serialiserbar'' betyr at en [[historie (databaser)|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 [[database#ACID-prinsippet|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 [[database]]systemer 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<sub>a</sub> skal gjøre X * 2 og det samtidig går en transaksjon T<sub>b</sub> som skal gjøre X + 2. Anta at begge leser X = 10. Så gjør T<sub>a</sub> X = 10 * 2 = 20. Deretter gjør T<sub>b</sub> X = 10 + 2 = 12, som blir stående. Riktig resultat var 22 hvis T<sub>a</sub> kom først, eller 24 hvis T<sub>b</sub> 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<sub>1</sub>) er konfliktserialiserbar hvis den er konfliktekvivalent med en seriell eksekveringsplan (S<sub>2</sub>). Konfliktekvivalent betyr at S<sub>1</sub> kan omdannes til S<sub>2 </sub> 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.<ref>Rusinkiewicz, Marek: [http://www2.cs.uh.edu/~marek/notes/lecture13/index.htm ''Lecture 13: Transaction Management''] {{Wayback|url=http://www2.cs.uh.edu/~marek/notes/lecture13/index.htm |date=20090214032513 }} 27.10.1997</ref>

==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.<ref name="postgresdoc">PostgreSQL 8.2.11 Documentation [http://www.postgresql.org/docs/8.2/interactive/mvcc.html  Chapter 12. Concurrency Control] 2006</ref>

==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.<ref>Normann, Ragnar: [http://www.uio.no/studier/emner/matnat/ifi/INF3100/v08/undervisningsmateriale/lysark/kap18.7-19.1.pdf Transaksjonshåndtering del 2 (Lysark)] INF3100, Universitetet i Oslo, mars 2008</ref>

==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 [[tre (datastruktur)|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==
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==
[[Fil:Precedence graph.svg|thumb|200px|right|Presedensgraf]]
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 T<sub>i</sub> til T<sub>j</sub> hvis noe av det T<sub>i</sub> gjør skjer før og er i konflikt med noe av det T<sub>j</sub> gjør.

Sistnevnte gjelder hvis en av transaksjonene inneholder en skriveoperasjon.

:<math>S = \begin{bmatrix}
T1   & T2   & T3  \\
R(A) &      &     \\
     & W(A) &     \\
     & Com. &     \\
W(A) &      &     \\
Com. &      &     \\
     &      & W(A)\\
     &      & Com.\\
\end{bmatrix}</math>

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å==
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.<ref name="asktom">Kyte, Tom:
[http://www.oracle.com/technetwork/issue-archive/2010/10-jan/o65asktom-082389.html Ask Tom – On Transaction Isolation Levels]
</ref>

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 ==
<references/>

{{Databaser}}

{{Autoritetsdata}}

[[Kategori:Databaser]]

[[el:Σειριοποιησιμότητα Συγκρούσεων]]