Transaksjonen
En transaksjon er en sekvens av operasjoner på data som har en begynnelse og en slutt.
En transaksjon er sekvensiell utførelse av lese- og skriveoperasjoner. Slutten på en transaksjon kan enten være å lagre endringene (commit) eller kansellere endringene (rollback). I forhold til en database består en transaksjon av flere forespørsler som behandles som en enkelt forespørsel.
Transaksjoner må tilfredsstille ACID-egenskaper
Atomitet. Transaksjonen er enten fullført eller ikke i det hele tatt.
Konsistens. Ved gjennomføring av en transaksjon må ikke restriksjonene som er pålagt dataene (for eksempel begrensninger i databasen) brytes. Konsistens innebærer at systemet vil bli overført fra en korrekt tilstand til en annen korrekt tilstand.
Isolering. Transaksjoner som kjører parallelt skal ikke påvirke hverandre, for eksempel endre data brukt av en annen transaksjon. Resultatet av å utføre parallelle transaksjoner bør være det samme som om transaksjonene ble utført sekvensielt.
Bærekraft. Når de er forpliktet, bør ikke endringer gå tapt.
Transaksjonslogg
Loggen lagrer endringer gjort av transaksjoner, sikrer atomitet og stabilitet av data i tilfelle systemfeil
Loggen inneholder verdiene som dataene hadde før og etter at de ble endret av transaksjonen. Fremskrivningsloggstrategi krever å legge til en loggoppføring om tidligere verdier før starten, og om endelige verdier etter at transaksjonen er fullført. Ved en plutselig stopp av systemet, leser databasen loggen i omvendt rekkefølge og kansellerer endringene som er gjort av transaksjoner. Etter å ha støtt på en avbrutt transaksjon, kjører databasen den og gjør endringer om den i loggen. Siden den er i tilstanden på tidspunktet for feilen, leser databasen loggen i videresendingsrekkefølgen og returnerer endringene som er gjort av transaksjoner. På denne måten bevares stabiliteten til transaksjoner som allerede er begått og atomiteten til den avbrutte transaksjonen.
Det er ikke tilstrekkelig å gjenopprette mislykkede transaksjoner på nytt.
Eksempel. Brukeren har $500 på kontoen sin, og brukeren bestemmer seg for å ta den fra en minibank. To transaksjoner pågår. Den første leser saldoverdien, og hvis det er nok midler på saldoen, utsteder den penger til brukeren. Den andre trekker det nødvendige beløpet fra saldoen. La oss si at systemet krasjet og den første operasjonen mislyktes, men den andre gjorde det. I dette tilfellet kan vi ikke utstede penger til brukeren på nytt uten å returnere systemet til sin opprinnelige tilstand med en positiv saldo.
Isolasjonsnivåer
Les Engasjert
Dirty Read-problemet er at en transaksjon kan lese mellomresultatet av en annen transaksjon.
Eksempel. Den opprinnelige saldoverdien er $0. T1 legger til $50 til saldoen din. T2 leser balanseverdien ($50). T1 forkaster endringene og avslutter. T2 fortsetter kjøringen med feil balansedata.
Løsningen er å lese faste data (Read Committed), som forbyr lesing av data endret av transaksjonen. Hvis transaksjon A har endret et bestemt sett med data, blir transaksjon B, når den får tilgang til disse dataene, tvunget til å vente på at transaksjon A skal fullføres.
Repeterbar lesing
Problem med tapte oppdateringer. T1 lagrer endringer på toppen av T2s endringer.
Eksempel. Den opprinnelige saldoverdien er $0 og to transaksjoner fyller opp saldoen samtidig. T1 og T2 leser en saldo på $0. T2 legger så til $200 til $0 og lagrer resultatet. T1 legger til $100 til $0 og lagrer resultatet. Det endelige resultatet er $100 i stedet for $300.
Ugjentakelig leseproblem. Å lese de samme dataene gjentatte ganger returnerer forskjellige verdier.
Eksempel. T1 viser en balanseverdi på $0. T2 legger deretter til $50 til saldoen og avslutter. T1 leser dataene på nytt og finner et avvik med det forrige resultatet.
Repeterbar lesing sikrer at en ny lesing vil returnere det samme resultatet. Data som leses av én transaksjon kan ikke endres i andre før transaksjonen er fullført. Hvis transaksjon A har lest et bestemt sett med data, blir transaksjon B, når den får tilgang til disse dataene, tvunget til å vente på at transaksjon A skal fullføres.
Bestilt lesing (kan serialiseres)
Phantom Reads-problem. To spørringer som velger data basert på en bestemt betingelse returnerer forskjellige verdier.
Eksempel. T1 ber om antall brukere hvis saldo er større enn $0, men mindre enn $100. T2 trekker $1 fra en bruker med en saldo på $101. T1 sender forespørselen på nytt.
Bestilt lesing (Serialiserbar). Transaksjoner utføres som fullstendig sekvensielle. Det er forbudt å oppdatere eller legge til poster som faller innenfor vilkårene for forespørselen. Hvis transaksjon A har bedt om data fra hele tabellen, fryses hele tabellen for andre transaksjoner til transaksjon A fullføres.
Planlegger
Angir rekkefølgen som operasjoner skal utføres i under parallelle transaksjoner.
Gir et spesifisert nivå av isolasjon. Hvis resultatet av operasjoner ikke avhenger av rekkefølgen deres, er slike operasjoner kommutative (Permutable). Leseoperasjoner og operasjoner på forskjellige data er kommutative. Lese-skrive og skrive-skrive operasjoner er ikke kommutative. Planleggerens oppgave er å sammenflette operasjoner utført av parallelle transaksjoner slik at utførelsesresultatet er ekvivalent med sekvensiell utførelse av transaksjoner.
Mekanismer for å kontrollere parallelle jobber (Concurrency Control)
Optimistisk er basert på å oppdage og løse konflikter, pessimistisk er basert på å forhindre at konflikter oppstår.
I den optimistiske tilnærmingen har flere brukere kopier av dataene til disposisjon. Den første personen som fullfører redigeringen lagrer endringene, mens de andre må slå sammen endringene. En optimistisk algoritme lar konflikt oppstå, men systemet må komme seg fra konflikten.
Med en pessimistisk tilnærming hindrer den første brukeren som fanger dataene andre fra å motta dataene. Hvis konflikter er sjeldne, er det lurt å velge den optimistiske strategien, siden den gir en høyere grad av samtidighet.
Låse
Hvis en transaksjon har låste data, må andre transaksjoner vente til den låses opp når de får tilgang til dataene.
En blokk kan legges over en database, tabell, rad eller attributt. Delt lås kan pålegges samme data ved flere transaksjoner, lar alle transaksjoner (inkludert den som påtvunget den) leses, forbyr modifikasjon og eksklusiv fangst. Eksklusiv lås kan pålegges av bare én transaksjon, tillater alle handlinger av den påleggende transaksjonen, forbyr handlinger fra andre.
En deadlock er en situasjon der transaksjoner havner i en ventende tilstand som varer på ubestemt tid.
Eksempel. Den første transaksjonen venter på at dataene fanget av den andre skal frigis, mens den andre venter på at dataene som er fanget opp av den første blir frigitt.
En optimistisk løsning på vranglåsproblemet lar vranglåsen oppstå, men gjenoppretter deretter systemet ved å rulle tilbake en av transaksjonene som er involvert i vranglåsen.
Vranglås søkes etter med visse intervaller. En av deteksjonsmetodene er etter tid, det vil si å vurdere at en deadlock har oppstått hvis transaksjonen tar for lang tid å fullføre. Når en deadlock er funnet, rulles en av transaksjonene tilbake, slik at andre transaksjoner involvert i deadlock kan fullføres. Valget av offer kan være basert på verdien av transaksjoner eller deres ansiennitet (Wait-Die og Wound-wait-ordninger).
Hver transaksjon T et tidsstempel er tildelt TS som inneholder starttidspunktet for transaksjonen.
Vent-Dø.
Hvis TS(Ti) < TS(Tj)deretter Ti venter, ellers Ti ruller tilbake og starter på nytt med samme tidsstempel.
Hvis en ung transaksjon har anskaffet en ressurs og en eldre transaksjon ber om den samme ressursen, får den eldre transaksjonen vente. Hvis en eldre transaksjon har anskaffet en ressurs, vil den yngre transaksjonen som ber om den ressursen bli rullet tilbake.
Sår-vent.
Hvis TS(Ti) < TS(Tj)deretter Tj ruller tilbake og starter på nytt med samme tidsstempel, ellers Ti venter.
Hvis en yngre transaksjon har anskaffet en ressurs og en eldre transaksjon ber om den samme ressursen, vil den yngre transaksjonen bli rullet tilbake. Hvis en eldre transaksjon har anskaffet en ressurs, får den yngre transaksjonen som ber om den ressursen vente. Forrangsbasert offerseleksjon forhindrer vranglås, men ruller tilbake transaksjoner som ikke er sperret. Problemet er at transaksjoner kan rulles tilbake mange ganger fordi... en eldre transaksjon kan holde ressursen i lang tid.
En pessimistisk løsning på vranglåsproblemet tillater ikke at en transaksjon begynner å utføres hvis det er fare for en stopp.
For å oppdage en vranglås, konstrueres en graf (ventegraf, vente-på-graf), hvis toppunkter er transaksjoner, og kantene er rettet fra transaksjoner som venter på frigjøring av data til transaksjonen som har fanget disse dataene. En vranglås anses å ha oppstått hvis grafen har en løkke. Å lage en ventegraf, spesielt i distribuerte databaser, er en kostbar prosedyre.
To-fase låsing - forhindrer vranglås ved å beslaglegge alle ressurser som brukes av en transaksjon i begynnelsen av transaksjonen og frigjøre dem på slutten
Alle blokkeringsoperasjoner må gå før den første opplåsingen. Den har to faser - Growing Phase, hvor grepene samler seg, og Shrinking Phase, hvor grepene frigjøres. Hvis det er umulig å fange en av ressursene, starter transaksjonen på nytt. Det er mulig at en transaksjon ikke vil kunne skaffe de nødvendige ressursene, for eksempel hvis flere transaksjoner konkurrerer om de samme ressursene.
En to-fase commit sikrer at commit utføres på alle databasereplikaer
Hver database legger inn informasjon om dataene som skal endres i loggen og svarer koordinatoren OK (Voting Phase). Etter at alle har svart OK, sender koordinatoren et signal som forplikter alle til å forplikte seg. Etter å ha forpliktet seg, svarer serverne OK; hvis minst én ikke svarer OK, sender koordinatoren et signal om å avbryte endringene til alle servere (Fullføringsfase).
Tidsstempelmetode
En eldre transaksjon rulles tilbake når man forsøker å få tilgang til data involvert i en yngre transaksjon
Hver transaksjon er tildelt et tidsstempel TS tilsvarende starttidspunktet for utførelsen. Hvis Ti eldre Tjderetter TS(Ti) < TS(Tj).
Når en transaksjon rulles tilbake, tildeles den et nytt tidsstempel. Hvert dataobjekt Q involvert i transaksjonen er merket med to etiketter. W-TS(Q) — tidsstempel for den yngste transaksjonen som fullførte en rekordovergang Q. R-TS(Q) — tidsstempel for den yngste transaksjonen som utførte en lesepost på Q.
Når transaksjonen T forespørsler om å lese data Q Det er to alternativer.
Hvis TS(T) < W-TS(Q), det vil si at dataene ble oppdatert av en yngre transaksjon, deretter transaksjonen T ruller tilbake.
Hvis TS(T) >= W-TS(Q), så utføres avlesningen og R-TS(Q) blir MAKS(R-TS(Q); TS(T)).
Når transaksjonen T ber om dataendringer Q Det er to alternativer.
Hvis TS(T) < R-TS(Q), det vil si at dataene allerede er lest av en yngre transaksjon og hvis det gjøres en endring vil det oppstå en konflikt. Transaksjon T ruller tilbake.
Hvis TS(T) < W-TS(Q), det vil si at transaksjonen prøver å overskrive en nyere verdi, transaksjon T rulles tilbake. I andre tilfeller gjennomføres endringen og W-TS(Q) blir lik TS(T).
Ingen dyr ventegrafkonstruksjon er nødvendig. Eldre transaksjoner avhenger av nyere, så det er ingen sykluser i ventegrafen. Det er ingen vranglås fordi transaksjoner ikke ventes, men rulles tilbake umiddelbart. Cascading rollbacks er mulig. Hvis Ti rullet bort og Tj Jeg leste dataene jeg endret Tideretter Tj skal også rulle tilbake. Hvis samtidig Tj allerede er begått, vil det være et brudd på stabilitetsprinsippet.
En av løsningene på cascading rollbacks. En transaksjon fullfører alle skriveoperasjoner på slutten, og andre transaksjoner må vente på at operasjonen skal fullføres. Transaksjoner venter på å bli begått før de blir lest.
Thomas skriveregel - en variant av tidsstempelmetoden der data som er oppdatert av en yngre transaksjon ikke kan overskrives av en eldre transaksjon
Transaksjon T ber om dataendringer Q. om TS(T) < W-TS(Q), det vil si at transaksjonen prøver å overskrive en nyere verdi, transaksjon T blir ikke rullet tilbake som i tidsstempelmetoden.
Kilde: www.habr.com