Transaktion
En transaktion er en sekvens af operationer på data, der har en begyndelse og en slutning.
En transaktion er den sekventielle udførelse af læse- og skriveoperationer. Slutningen af en transaktion kan enten være at gemme ændringerne (commit) eller annullere ændringerne (rollback). I forhold til en database består en transaktion af flere anmodninger, der behandles som en enkelt anmodning.
Transaktioner skal opfylde ACID-egenskaber
Atomicitet. Transaktionen er enten gennemført helt eller slet ikke.
Konsistens. Når en transaktion gennemføres, må de begrænsninger, der er pålagt dataene (f.eks. begrænsninger i databasen), ikke overtrædes. Konsistens indebærer, at systemet vil blive overført fra en korrekt tilstand til en anden korrekt tilstand.
Isolation. Transaktioner, der kører parallelt, bør ikke påvirke hinanden, for eksempel ændre data, der bruges af en anden transaktion. Resultatet af at udføre parallelle transaktioner bør være det samme, som hvis transaktionerne blev udført sekventielt.
Bæredygtighed. Når først de er forpligtet, bør ændringer ikke gå tabt.
Transaktionslog
Loggen gemmer ændringer foretaget af transaktioner, sikrer atomicitet og stabilitet af data i tilfælde af systemfejl
Loggen indeholder de værdier, som dataene havde før og efter, de blev ændret af transaktionen. Fremskrivningslogstrategi kræver tilføjelse af en logpost om tidligere værdier før starten og om endelige værdier efter transaktionen er gennemført. I tilfælde af et pludseligt stop af systemet, læser databasen loggen i omvendt rækkefølge og annullerer ændringerne foretaget af transaktioner. Efter at have stødt på en afbrudt transaktion, udfører databasen den og foretager ændringer om den i loggen. Da databasen er i tilstanden på tidspunktet for fejlen, læser den log-in-forsendelsesrækkefølgen og returnerer ændringerne foretaget af transaktioner. På denne måde bevares stabiliteten af transaktioner, der allerede er begået, og atomiciteten af den afbrudte transaktion.
Blot at genudføre mislykkede transaktioner er ikke tilstrækkeligt til gendannelse.
Eksempel. Brugeren har $500 på sin konto, og brugeren beslutter sig for at hæve den fra en hæveautomat. To transaktioner er i gang. Den første læser saldoværdien, og hvis der er penge nok på saldoen, udsteder den penge til brugeren. Den anden trækker det nødvendige beløb fra saldoen. Lad os sige, at systemet styrtede ned, og den første operation mislykkedes, men den anden gjorde det. I dette tilfælde kan vi ikke genudstede penge til brugeren uden at returnere systemet til dets oprindelige tilstand med en positiv saldo.
Isoleringsniveauer
Læs Engageret
Dirty Read-problemet er, at en transaktion kan læse mellemresultatet af en anden transaktion.
Eksempel. Den oprindelige saldoværdi er $0. T1 tilføjer $50 til din saldo. T2 aflæser saldoværdien ($50). T1 kasserer ændringerne og afslutter. T2 fortsætter udførelse med forkerte balancedata.
Løsningen er at læse faste data (Read Committed), som forbyder læsning af data ændret ved transaktionen. Hvis transaktion A har ændret et bestemt sæt data, så er transaktion B, når den får adgang til disse data, tvunget til at vente på, at transaktion A er fuldført.
Gentagelig læsning
Problem med mistede opdateringer. T1 gemmer ændringer oven i T2s ændringer.
Eksempel. Den oprindelige saldoværdi er $0, og to transaktioner genopfylder saldoen samtidigt. T1 og T2 læser en saldo på $0. T2 tilføjer derefter $200 til $0 og gemmer resultatet. T1 tilføjer $100 til $0 og gemmer resultatet. Det endelige resultat er $100 i stedet for $300.
Ugentageligt læseproblem. Læsning af de samme data gentagne gange returnerer forskellige værdier.
Eksempel. T1 aflæser en saldoværdi på $0. T2 tilføjer derefter $50 til saldoen og slutter. T1 læser dataene igen og finder en uoverensstemmelse med det tidligere resultat.
Gentagelig læsning sikrer, at en anden læsning returnerer det samme resultat. Data læst af én transaktion kan ikke ændres i andre, før transaktionen er gennemført. Hvis transaktion A har læst et bestemt sæt data, er transaktion B, når den tilgår disse data, tvunget til at vente på, at transaktion A er fuldført.
Bestilt læsning (kan serialiseres)
Phantom Reads problem. To forespørgsler, der vælger data baseret på en bestemt betingelse, returnerer forskellige værdier.
Eksempel. T1 anmoder om antallet af alle brugere, hvis saldo er større end $0, men mindre end $100. T2 trækker $1 fra en bruger med en saldo på $101. T1 genudsender anmodningen.
Bestilt læsning (Serialiserbar). Transaktioner udføres som fuldstændig sekventielle. Det er forbudt at opdatere eller tilføje poster, der falder inden for betingelserne for anmodningen. Hvis transaktion A har anmodet om data fra hele tabellen, så fryses hele tabellen for andre transaktioner, indtil transaktion A er fuldført.
Planlægger
Indstiller den rækkefølge, som operationer skal udføres i under parallelle transaktioner.
Giver et specificeret niveau af isolation. Hvis resultatet af operationer ikke afhænger af deres rækkefølge, så er sådanne operationer kommutative (Permutable). Læseoperationer og operationer på forskellige data er kommutative. Læs-skrive- og skriv-skriv-operationer er ikke kommutative. Planlæggerens opgave er at sammenflette operationer udført af parallelle transaktioner, således at udførelsesresultatet svarer til sekventiel udførelse af transaktioner.
Mekanismer til styring af parallelle job (Concurrency Control)
Optimistisk er baseret på at opdage og løse konflikter, pessimistisk er baseret på at forhindre konflikter i at opstå.
I den optimistiske tilgang har flere brugere kopier af dataene til deres rådighed. Den første person, der fuldfører redigeringen, gemmer ændringerne, mens de andre skal flette ændringerne. En optimistisk algoritme tillader konflikt at opstå, men systemet skal komme sig over konflikten.
Med en pessimistisk tilgang forhindrer den første bruger, der fanger dataene, andre i at modtage dataene. Hvis konflikter er sjældne, er det klogt at vælge den optimistiske strategi, da den giver en højere grad af samtidighed.
Låsning
Hvis en transaktion har låst data, så skal andre transaktioner vente, indtil den er låst op, når de tilgår dataene.
En blok kan overlejres på en database, tabel, række eller attribut. Delt lås kan pålægges de samme data ved flere transaktioner, tillader alle transaktioner (inklusive den, der pålagde det) at læse, forbyder modifikation og eksklusiv indfangning. Eksklusiv lås kan kun pålægges af én transaktion, tillader enhver handling af den pålæggende transaktion, forbyder enhver handling fra andre.
Et dødvande er en situation, hvor transaktioner ender i en afventende tilstand, der varer på ubestemt tid.
Eksempel. Den første transaktion venter på, at de data, der er opsamlet af den anden, bliver frigivet, mens den anden venter på, at de data, der er fanget af den første, bliver frigivet.
En optimistisk løsning på dødvandsproblemet tillader dødvandet at opstå, men genopretter derefter systemet ved at rulle en af de transaktioner, der er involveret i dødvandet, tilbage.
Dødlåse søges efter med bestemte intervaller. En af detekteringsmetoderne er efter tid, det vil sige at overveje, at der er opstået et dødvande, hvis transaktionen tager for lang tid at gennemføre. Når en deadlock er fundet, rulles en af transaktionerne tilbage, så andre transaktioner involveret i deadlock kan gennemføres. Valget af offer kan være baseret på værdien af transaktioner eller deres anciennitet (Wait-Die og Wound-wait-ordninger).
Hver transaktion T et tidsstempel er tildelt TS indeholdende starttidspunktet for transaktionen.
Vent-Dø.
Hvis TS(Ti) < TS(Tj)derefter Ti venter ellers Ti ruller tilbage og starter igen med samme tidsstempel.
Hvis en ung transaktion har erhvervet en ressource, og en ældre transaktion anmoder om den samme ressource, får den ældre transaktion lov til at vente. Hvis en ældre transaktion har erhvervet en ressource, vil den yngre transaktion, der anmoder om denne ressource, blive rullet tilbage.
Sår-vent.
Hvis TS(Ti) < TS(Tj)derefter Tj ruller tilbage og starter igen med samme tidsstempel, ellers Ti venter.
Hvis en yngre transaktion har erhvervet en ressource, og en ældre transaktion anmoder om den samme ressource, vil den yngre transaktion blive rullet tilbage. Hvis en ældre transaktion har erhvervet en ressource, får den yngre transaktion, der anmoder om denne ressource, lov til at vente. Præcedensbaseret offerudvælgelse forhindrer deadlocks, men ruller transaktioner tilbage, der ikke er deadlocked. Problemet er, at transaktioner kan rulles tilbage mange gange, fordi... en ældre transaktion kan opbevare ressourcen i lang tid.
En pessimistisk løsning på deadlock-problemet tillader ikke en transaktion at begynde at udføre, hvis der er risiko for en deadlock.
For at detektere en dødvande konstrueres en graf (ventegraf, vente-på-graf), hvis toppunkter er transaktioner, og kanterne er rettet fra transaktioner, der venter på frigivelse af data, til transaktionen, der har fanget disse data. En dødvande anses for at være opstået, hvis grafen har en sløjfe. At konstruere en ventegraf, især i distribuerede databaser, er en dyr procedure.
To-faset låsning - forhindrer deadlocks ved at beslaglægge alle ressourcer brugt af en transaktion i begyndelsen af transaktionen og frigive dem i slutningen
Alle blokeringsoperationer skal gå forud for den første oplåsning. Den har to faser - Growing Phase, hvor grebene akkumuleres, og Shrinking Phase, hvor grebene slippes. Hvis det er umuligt at fange en af ressourcerne, starter transaktionen forfra. Det er muligt, at en transaktion ikke vil være i stand til at erhverve de nødvendige ressourcer, for eksempel hvis flere transaktioner konkurrerer om de samme ressourcer.
En to-fase commit sikrer, at commit udføres på alle databasereplikaer
Hver database indtaster information om de data, der vil blive ændret, i loggen og svarer koordinatoren OK (afstemningsfasen). Efter at alle har svaret OK, sender koordinatoren et signal, der forpligter alle til at forpligte sig. Efter committing svarer serverne OK; hvis mindst én ikke svarer OK, sender koordinatoren et signal om at annullere ændringerne til alle servere (fuldførelsesfasen).
Tidsstempel metode
En ældre transaktion rulles tilbage, når man forsøger at få adgang til data involveret i en yngre transaktion
Hver transaktion er tildelt et tidsstempel TS svarende til starttidspunktet for udførelsen. Hvis Ti senior Tjderefter TS(Ti) < TS(Tj).
Når en transaktion rulles tilbage, tildeles den et nyt tidsstempel. Hvert dataobjekt Q involveret i transaktionen er markeret med to etiketter. W-TS(Q) — tidsstempel for den yngste transaktion, der fuldførte en rekordoverførsel Q. R-TS(Q) — tidsstempel for den yngste transaktion, der udførte en læst post på Q.
Når transaktionen T anmodninger om at læse data Q Der er to muligheder.
Hvis TS(T) < W-TS(Q), det vil sige, at dataene blev opdateret af en yngre transaktion, derefter transaktionen T ruller tilbage.
Hvis TS(T) >= W-TS(Q), så udføres aflæsningen og R-TS(Q) bliver MAKS(R-TS(Q), TS(T)).
Når transaktionen T anmoder om dataændringer Q Der er 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 der opstå en konflikt. Transaktion T ruller tilbage.
Hvis TS(T) < W-TS(Q), dvs. transaktionen forsøger at overskrive en nyere værdi, transaktion T rulles tilbage. I andre tilfælde gennemføres ændringen og W-TS(Q) bliver lige TS(T).
Der kræves ingen dyr ventegrafkonstruktion. Ældre transaktioner afhænger af nyere, så der er ingen cyklusser i ventegrafen. Der er ingen deadlocks, fordi transaktioner ikke ventes, men rulles tilbage med det samme. Cascading rollbacks er mulige. Hvis Ti rullede væk og Tj Jeg læste de data, jeg ændrede Tiderefter Tj skal også rulle tilbage. Hvis på samme tid Tj allerede er begået, så vil der være tale om en krænkelse af stabilitetsprincippet.
En af løsningerne på cascading rollbacks. En transaktion fuldfører alle skriveoperationer i slutningen, og andre transaktioner skal vente på, at operationen er fuldført. Transaktioner venter på at blive begået, før de bliver læst.
Thomas skriveregel - en variation af tidsstempelmetoden, hvor data opdateret af en yngre transaktion er forbudt at blive overskrevet af en ældre
Transaktion T anmoder om dataændringer Q. hvis TS(T) < W-TS(Q), det vil sige, at transaktionen forsøger at overskrive en nyere værdi, bliver transaktion T ikke rullet tilbage som i tidsstempelmetoden.
Kilde: www.habr.com