Transaktioner
En transaktion er en sekvens af operationer på data, der har en start og en slutning.
En transaktion er en sekventiel udførelse af læse- og skriveoperationer. Afslutningen af en transaktion kan være enten bevaring af ændringer (commit) eller annullering af ændringer (rollback). I forhold til databaser er en transaktion flere forespørgsler, der betragtes som en enkelt forespørgsel.
Transaktioner skal opfylde ACID-egenskaberne.
Atomicitet. En transaktion udføres enten fuldstændigt eller slet ikke.
Konsistens. Ved afslutningen af en transaktion må de begrænsninger, der er pålagt dataene (f.eks. constraints i databasen), ikke blive overtrådt. Konsistens indebærer, at systemet skal overgå fra en korrekt tilstand til en anden korrekt.
Isolation. Parallelt udførte transaktioner må ikke påvirke hinanden, fx ændre data, som en anden transaktion bruger. Resultatet af parallelle transaktioner skal være det samme, som hvis transaktionerne blev udført sekventielt.
Holdbarhed. Efter commit må ændringer ikke gå tabt.
Transaktionslog
Loggen opbevarer ændringer foretaget af transaktioner, sikrer atomicitet og holdbarhed af dataene i tilfælde af systemfejl.
Loggen indeholder værdierne, som dataene havde før og efter ændringerne blev foretaget af transaktionen. Write-ahead log-strategien kræver, at der tilføjes en post til loggen om de tidligere værdier før starten, og om de endelige værdier efter afslutningen af transaktionen. Ved en pludselig systemstop læser databasen loggen bagfra og annullerer ændringer foretaget af transaktioner. Hvis den støder på en afbrudt transaktion, udfører databasen den og opdaterer loggen om den. I den tilstand, databasen var i på tidspunktet for fejlen, læser databasen loggen i fremadrettet rækkefølge og genfører ændringerne foretaget af transaktioner. Dette sikrer holdbarheden af transaktioner, der allerede er blevet bekræftet, og atomiciteten af de afbrudte transaktioner.
En simpel gentagelse af fejlede transaktioner er ikke tilstrækkelig til at genoprette.
Eksempel. Brugeren har 500$ på sin konto, og brugeren beslutter at hæve dem via en pengeautomat. Der udføres to transaktioner. Den første læser saldoen, og hvis der er tilstrækkelige midler på kontoen, udbetales pengene til brugeren. Den anden fratrækker det nødvendige beløb fra saldoen. Antag, at systemet fejler, og den første operation ikke blev udført, men den anden blev udført. I dette tilfælde kan vi ikke udbetale penge til brugeren igen uden at bringe systemet tilbage til sin oprindelige tilstand med en positiv saldo.
Isoleringsniveauer
Læse fast data (Read Committed)
Problemet med beskidt læsning (Dirty Read) er, at en transaktion kan læse et mellemresultat fra en anden transaktion.
Eksempel. Startsaldoen er 0$. T1 tilføjer 50$ til saldoen. T2 læser saldoen (50$). T1 annullerer ændringerne og afsluttes. T2 fortsætter med at udføre og har falske oplysninger om saldoen.
Løsningen er at anvende læse fast data (Read Committed), som forhindrer læsning af data ændret af en transaktion. Hvis transaktion A ændrer en bestemt datamængde, må transaktion B vente på, at transaktion A afsluttes, før den kan få adgang til disse data.
Gentagen læsning (Repeatable Read)
Problemet med tabte ændringer (Lost Updates). T1 gemmer ændringer oven på ændringer fra T2.
Eksempel. Startsaldoen er 0$, og to transaktioner forsøger samtidigt at tilføje til saldoen. T1 og T2 læser saldoen som 0$. T2 tilføjer 200$ til 0$ og gemmer resultatet. T1 tilføjer 100$ til 0$ og gemmer resultatet. Det endelige resultat er 100$ i stedet for 300$.
Problemet med ikke-repetabel læsning (Unrepeatable read). Gentagen læsning af de samme data giver forskellige værdier.
Eksempel. T1 læser saldoen som 0$. Derefter tilføjer T2 50$ til saldoen og afsluttes. T1 læser dataene igen og opdager en uoverensstemmelse med det tidligere resultat.
Gentagen læsning (Repeatable Read) garanterer, at gentagen læsning returnerer det samme resultat. Data læst af én transaktion må ikke ændres af andre, indtil transaktionen er afsluttet. Hvis transaktion A har læst en bestemt datamængde, må transaktion B vente på, at transaktion A afsluttes, før den kan få adgang til disse data.
Ordnet læsning (Serializable)
Problemet med phantomlæsning (Phantom Reads). To forespørgsler, der vælger data baseret på et bestemt kriterium, returnerer forskellige værdier.
Eksempel. T1 forespørger antal brugere, hvis balance er over 0$ men under 100$. T2 trækker 1$ fra en bruger med en balance på 101$. T1 udfører forespørgslen igen.
Ordnet læsning (Serializable). Transaktioner udføres som fuldstændig sekventielle. Det er forbudt at opdatere og tilføje poster, der falder ind under forespørgselsbetingelserne. Hvis transaktion A har forespurgt data fra hele tabellen, så fryses tabellen helt for andre transaktioner, indtil transaktion A er afsluttet.
Planlægger (Scheduler)
Fastlægger rækkefølgen af operationer, der skal udføres ved parallelt kørende transaktioner
Sikrer det angivne niveau af isolering. Hvis resultatet af operationer ikke afhænger af deres rækkefølge, er sådanne operationer kommutative (Permutable). Læseoperationer og operationer på forskellige data er kommutative. Læse-skriv og skrive-skriv operationer er ikke kommutative. Planlæggerens opgave er at vekselere operationer udført af parallelle transaktioner, så resultatet er ækvivalent med sekventiel udførelse af transaktionerne.
Kontrolmekanismer for parallelle opgaver (Concurrency Control)
Optimistisk baseret på opdagelse og løsning af konflikter, pessimistisk på at forhindre opståen af konflikter
Ved den optimistiske tilgang får flere brugere adgang til kopier af dataene. Den første, der afslutter redigeringen, gemmer ændringerne, mens de andre skal fusionere ændringerne. Den optimistiske algoritme tillader en konflikt at opstå, men systemet skal kunne genoprette sig efter konflikten.
Ved den pessimistiske tilgang hindrer den første bruger, der får fat i dataene, de andre i at få adgang til dem. Hvis konflikter er sjældne, kan det være fornuftigt at vælge en optimistisk strategi, da den muliggør et højere niveau af parallelisme.
Låsning (Locking)
Hvis én transaktion har låst dataene, skal de øvrige transaktioner vente på, at aft låsningen bliver ophævet.
En blok kan pålægges en database, tabel, række eller attribut. En delt lås (Shared Lock) kan pålægges de samme data af flere transaktioner, hvilket tillader alle transaktioner (herunder den pålagte) at læse, men forbyder ændringer og eksklusive låsninger. En eksklusiv lås (Exclusive Lock) kan kun pålægges af én transaktion, hvilket tillader alle handlinger af den pålagte transaktion og forbyder alle handlinger af de resterende.
En situation, hvor transaktioner befinder sig i en ventetilstand, der varer uendeligt, kaldes en deadlock.
Eksempel. Den første transaktion venter på frigivelse af data, der er låst af den anden, mens den anden venter på frigivelse af data låst af den første.
Den optimistiske løsning på deadlock-problemet tillader, at deadlock opstår, men genopretter derefter systemet ved at tilbageføre en af transaktionerne, der er involveret i deadlocken.
Med jævne mellemrum foretages der søgning efter deadlocks. En af metoderne til opdagelse er tidsbaseret, hvilket vil sige, at man betragter det som en deadlock, hvis en transaktion kører for længe. Når en deadlock findes, tilbageføres en af transaktionerne, hvilket giver mulighed for, at andre transaktioner involveret i deadlocken kan afsluttes. Valget af offer kan baseres på transaktionernes omkostninger eller deres anciennitet (Wait-Die og Wound-Wait skemaer).
Hver transaktion T tildeles et tidsstempel TS som indeholder tidspunktet for, hvornår transaktionen blev påbegyndt.
Wait-Die.
Hvis TS(Ti) < TS(Tj), så Ti venter, ellers Ti tilbageføres og starter forfra med det samme tidsstempel.
Hvis en yngre transaktion har låst en ressource, og en ældre anmoder om den samme ressource, så må den ældre transaktion vente. Hvis en ældre transaktion har låst ressourcen, så vil den yngre transaktion, der anmoder om denne ressource, blive tilbageført.
Wound-Wait.
Hvis TS(Ti) < TS(Tj), så Tj bliver tilbageført og starter forfra med det samme tidsstempel, ellers Ti venter.
Hvis en yngre transaktion har taget kontrol over en ressource, og en ældre transaktion anmoder om den samme ressource, vil den yngre transaktion blive tilbagekaldt. Hvis en ældre transaktion har taget kontrol over ressourcen, skal den yngre transaktion, der anmoder om den pågældende ressource, vente. Valget af offer baseret på alder forhindrer optræden af deadlocks, men tilbagekalder transaktioner, der ikke er i en tilstand af deadlock. Problemet er, at transaktioner kan blive tilbagekaldt flere gange, da en ældre transaktion kan holde ressourcen i lang tid.
En pessimistisk løsning på deadlock-problemet tillader ikke transaktionen at begynde udførelsen, hvis der er risiko for at opnå en deadlock.
For at opdage deadlocks opbygges en graf (ventningsgraf, wait-for-graph), hvor noderne repræsenterer transaktioner, og kanterne er rettet fra transaktioner, der venter på frigivelse af data, til transaktioner, der har taget kontrol over disse data. Det antages, at der har været en deadlock, hvis grafen har en cyklus. Opbygning af ventningsgrafen, især i distribuerede databaser, er en kostbar procedure.
To-fase låsning - forhindring af deadlocks ved at tage kontrol over alle ressourcer, der bruges af transaktionen i starten af transaktionen og frigive dem i slutningen.
Alle låseoperationer skal finde sted før den første frigivelsesoperation. Det har to faser - vækstfasen, hvor låseakkumuleres, og krympningsfasen, hvor låse frigives. Hvis det ikke er muligt at tage kontrol over en af ressourcerne, starter transaktionen forfra. Det er muligt, at en transaktion ikke kan tage kontrol over de nødvendige ressourcer, hvis flere transaktioner konkurrerer om de samme ressourcer.
To-fase commit sikrer udførelsen af commit på alle replikaer af databasen.
Hver database indfører oplysninger om de data, der vil blive ændret i en log og svarer til koordinatoren med OK (Voting Phase). Efter at alle har svaret OK, sender koordinatoren et signal, der forpligter alle til at gennemføre commit. Efter commit server svarer de med OK; hvis blot én ikke svarer med OK, sender koordinatoren et signal om at annullere ændringerne til alle servere (Completion Phase).
Metoden med tidsstempler.
En ældre transaktion bliver tilbagekaldt, når den forsøger at få adgang til data, der er involveret i en yngre transaktion.
Hver transaktion tildeles et tidsstempel TS som svarer til det tidspunkt, hvor den bliver udført. Hvis Ti ældre Tj, så TS(Ti) < TS(Tj).
Når en transaktion rulles tilbage, tildeles den et nyt tidsstempel. Hvert datablob Q involveret i transaktionen markeres med to timestamps. W-TS(Q) — tidsstemplet for den yngste transaktion, der har fuldført en skrivning til Q. R-TS(Q) — tidsstemplet for den yngste transaktion, der har udført en læseskrivning til Q.
Når transaktionen T anmoder om at læse data Q er der to muligheder.
Hvis TS(T) < W-TS(Q), det vil sige at dataene er blevet opdateret af en yngre transaktion, så transaktionen T rulles tilbage.
Hvis TS(T) ≥ W-TS(Q), så udføres læsningen og R-TS(Q) bliver MAX(R-TS(Q), TS(T)).
Når transaktionen T anmoder om at ændre data Q er der to muligheder.
Hvis TS(T) < R-TS(Q), det vil sige at dataene allerede er blevet læst af en yngre transaktion, og hvis der foretages en ændring, vil det skabe en konfliktsituation. Transaktionen T rulles tilbage.
Hvis TS(T) < W-TS(Q), det vil sige at transaktionen forsøger at overskrive en nyere værdi, transaktionen T rulles tilbage. I alle andre tilfælde gennemføres ændringen og W-TS(Q) bliver lig med TS(T).
Der er ikke behov for dyre ventegrafer. Ældre transaktioner er afhængige af nyere, så der er ingen cyklusser i ventegrafen. Der er ingen deadlocks, da transaktionerne ikke venter, men rulles tilbage med det samme. Kaskade tilbageslag er mulige. Hvis Ti er blevet rullet tilbage, og Tj har læst de data, som den ændrede Ti, så Tj skal også rulles tilbage. Hvis dette samtidig Tj allerede er blevet bekræftet, vil det krænke princippet om konsistens.
En løsning på kaskade tilbageslag. Transaktionen udfører alle skriveoperationer til sidst, og de øvrige transaktioner skal vente på, at denne operation er afsluttet. Transaktionerne venter på en bekræftelse før læsning.
Thomas write rule — en variation af metoden med tidsstempler, hvor data opdateret af en yngre transaktion ikke må overskrives af en ældre
Transaktion T anmoder om at ændre data Q. Hvis TS(T) < W-TS(Q), det vil sige at transaktionen forsøger at overskrive en nyere værdi, transaktionen T rulles ikke tilbage som i metoden med tidsstempler.
Kilde: habr.com
