Transakcije
Transakcija je niz operacij nad podacima koji ima početak i kraj.
Transakcija je sekvencijalno izvršavanje operacija čitanja i pisanja. Kraj transakcije može biti ili očuvanje promena (potvrda, commit) ili poništavanje promena (rollback). U kontekstu baza podataka, transakcija se sastoji od više zahteva koji se tretiraju kao jedinstven zahtev.
Transakcije moraju zadovoljiti ACID svojstva.
Aatomarnost. Transakcija se ili izvršava u potpunosti ili se ne izvršava uopšte.
Doslednost. Na kraju transakcije ne smiju biti narušena ograničenja koja se postavljaju na podatke (npr. constraints u bazi podataka). Doslednost podrazumeva da će sistem preći iz jednog ispravnog stanja u drugo ispravno.
Izolacija. Paralelno izvršavane transakcije ne smeju uticati jedna na drugu, na primer, menjajući podatke koje koristi druga transakcija. Rezultat izvršenja paralelnih transakcija mora biti takav kao da su se transakcije izvršavale sekvencijalno.
Postojanost. Nakon potvrde, promene ne smeju biti izgubljene.
Dnevnik transakcija.
Dnevnik čuva promene izvršene transakcijama, obezbeđuje atomarnost i postojanost podataka u slučaju kvara sistema.
Dnevnik sadrži vrednosti koje su podaci imali pre i posle svojih promena izvršenih transakcijom. Strategija Write-ahead log obavezuje na dodavanje u dnevnik zapisa o prethodnim vrednostima pre početka, a o konačnim nakon završetka transakcije. U slučaju iznenadnog zaustavljanja sistema, baza podataka čita dnevnik unazad i poništava promene koje su napravile transakcije. Kada se susretne prekinuta transakcija, baza podataka je izvršava i beleži njene promene u dnevnik. Nalazeći se u stanju u trenutku kvara, baza podataka čita dnevnik unapred i vraća promene koje su napravile transakcije. Na taj način se zadržava postojanost transakcija koje su već bile potvrđene i atomarnost prekinutih transakcija.
Jednostavno ponavljanje grešaka u transakcijama nije dovoljno za oporavak.
Primer. U uporabnikovem računu je 500$, uporabnik pa se odloči, da jih dvigne preko bankomata. Opravljeni sta dve transakciji. Prva preveri stanje na računu in, če je na računu dovolj sredstev, izda denar uporabniku. Druga odšteje potrebno vsoto od stanja. Predpostavimo, da je prišlo do okvare sistema in prva operacija ni bila izvedena, druga pa je. V tem primeru ne moremo znova izdati denarja uporabniku brez vrnitve sistema v prvotno stanje s pozitivnim stanjem.
Nivoji izolacije
Branje fiksnih podatkov (Read Committed)
Težava umazanega branja (Dirty Read) je v tem, da lahko transakcija prebere vmesni rezultat dela druge transakcije.
Primer. Začetna vrednost stanja računa je 0$. T1 doda 50$ k stanju. T2 prebere vrednost stanja (50$). T1 prekliče spremembe in se zaključi. T2 nadaljuje izvajanje z napačnimi podatki o stanju.
Rešitev je branje fiksnih podatkov (Read Committed), ki prepoveduje branje podatkov, spremenjenih s transakcijo. Če je transakcija A spremenila nek nabor podatkov, mora transakcija B pri dostopu do teh podatkov počakati na zaključek transakcije A.
Ponovljivo branje (Repeatable Read)
Težava izgubljenih sprememb (Lost Updates). T1 shranjuje spremembe preko sprememb T2.
Primer. Začetna vrednost stanja računa je 0$ in dve transakciji hkrati dopolnjujeta stanje. T1 in T2 prebereta stanje, ki je enako 0$. Nato T2 doda 200$ k 0$ in shrani rezultat. T1 doda 100$ k 0$ in shrani rezultat. Končni rezultat je 100$ namesto 300$.
Težava neponovljivega branja (Unrepeatable Read). Ponovno branje istih podatkov vrne različne vrednosti.
Primer. T1 prebere vrednost stanja, ki je enaka 0$. Nato T2 doda 50$ k stanju in se zaključi. T1 ponovno prebere podatke in odkrije neskladje s prejšnjim rezultatom.
Ponovljivo branje (Repeatable Read) zagotavlja, da bo ponovno branje vrnilo enak rezultat. Podatke, ki jih prebere ena transakcija, je prepovedano spreminjati v drugih do zaključka transakcije. Če je transakcija A prebrala nek nabor podatkov, mora transakcija B pri dostopu do teh podatkov počakati na zaključek transakcije A.
Urejeno branje (Serializable)
Problem fanomskega branja (Phantom Reads). Dve poizvedbi, ki izbirata podatke po nekem pogoju, vračata različne vrednosti.
Primer. T1 zahteva število vseh uporabnikov, katerih stanje je večje od 0$ in manjše od 100$. T2 odšteje 1$ uporabniku s stanjem 101$. T1 izvede poizvedbo znova.
Urejeno branje (Serializable). Transakcije se izvajajo kot popolnoma zaporedne. Prepovedano je posodabljati in dodajati zapise, ki ustrezajo pogojem poizvedbe. Če je transakcija A zahtevala podatke celotne tabele, se tabela v celoti zamrzne za druge transakcije do zaključka transakcije A.
Načrtovalnik (Scheduler)
Določa zaporedje, v katerem se izvajajo operacije pri hkratnih transakcijah
Zagotavlja določeno raven izolacije. Če rezultat izvajanja operacij ni odvisen od njihovega zaporedja, so takšne operacije komutativne (Permutable). Komutativne so bralne operacije in operacije nad različnimi podatki. Bralne-pisalne in pisalne-pisalne operacije niso komutativne. Naloga načrtovalnika je, da izmenjuje operacije, ki jih izvajajo hkratne transakcije, tako, da je rezultat izvajanja enak zaporednemu izvajanju transakcij.
Mehanizmi nadzora hkratnih nalog (Concurrency Control)
Optimizirani temelji na odkrivanju in reševanju konfliktov, pesimistični pa na preprečevanju nastanka konfliktov.
Pri optimističnem pristopu več uporabnikov dobi kopije podatkov. Prvi, ki dokonča urejanje, shrani spremembe, ostali pa morajo izvesti združitev sprememb. Optimiziran algoritem omogoča, da pride do konflikta, vendar se mora sistem okrevati po konfliktnem dogodku.
Pri pesimističnem pristopu prvi uporabnik, ki pridobi podatke, preprečuje dostop do podatkov drugim. Če so konflikti redki, je razumno izbrati optimistično strategijo, saj ta zagotavlja višjo raven paralelizma.
Zaklepanje (Locking)
Če ena transakcija zaklene podatke, morajo ostale transakcije ob interakciji s podatki počakati na odklepanje.
Blok lahko obremeni bazo podatkov, tabelo, vrstico ali atribut. Skupna zaklenitev (Shared Lock) lahko obstaja na istih podatkih z več transakcijami, kar omogoča vsem transakcijam (vključno s tisto, ki je nalagala) branje, onemogoča pa spreminjanje in monopolno zaklepanje. Monopolna zaklenitev (Exclusive Lock) je lahko nalagana le z eno transakcijo, dovoljuje vsa dejanja nalagajoče transakcije, drugim pa prepoveduje vse akcije.
Mehanska blokada se šteje za situacijo, ko so transakcije v stanju čakajočega, ki traja neskončno dolgo.
Primer. Prva transakcija čaka na sprostitev podatkov, ki jih je zasedla druga, medtem ko druga čaka na sprostitev podatkov, zasedenih s prvo.
Optimizacijska rešitev problema mehanske blokade omogoča, da do mehanske blokade pride, nato pa sistem obnovi z vračanjem ene od transakcij, vključenih v mehansko blokado.
Iskanje mehanskih blokad poteka ob določenih časovnih intervalih. Eden od načinov za odkrivanje je časovni, kar pomeni, da šteje, da je prišlo do mehanske blokade, če transakcija izvaja predolgo. Ko se mehanska blokada najde, se ena od transakcij vrne nazaj, kar omogoča drugim transakcijam, vključenim v mehansko blokado, da se končajo. Izbira žrtve je lahko temelji na stroških transakcij ali njihovem vrstnem redu (Wait-Die in Wound-wait sheme).
Vsaki transakciji T je dodeljena časovna oznaka TS ki vsebuje čas začetka izvajanja transakcije.
Wait-Die.
Если TS(Ti) < TS(Tj), potem Ti čaka, drugače Ti se vrne nazaj in začne znova s to isto časovno oznako.
Če mlajša transakcija zasede vir in starejša zahteva isti vir, je starejši transakciji dovoljeno čakati. Če starejša transakcija zasede vir, bo mlajša transakcija, ki zahteva ta vir, vrnjena nazaj.
Wound-wait.
Если TS(Ti) < TS(Tj), potem Tj se vrne nazaj in začne znova s to isto časovno oznako, drugače Ti čaka.
Če mlajša transakcija prevzame vir, medtem ko starejša transakcija zahteva isti vir, bo mlajša transakcija prekinjena. Če starejša transakcija prevzame vir, je mlajši transakciji, ki zahteva ta vir, dovoljena, da čaka. Izbira žrtve na podlagi starosti preprečuje nastanek mrtvih točk, vendar prekinja transakcije, ki niso v stanju mrtve točke. Težava je v tem, da se transakcije lahko prekinejo večkrat, saj starejša transakcija lahko dolgo obdrži vir.
Pesimistična rešitev težave z mrtvimi točkami ne dovoli, da transakcija začne izvajanje, če obstaja tveganje nastanka mrtve točke.
Za odkrivanje mrtvih točk se gradi graf (graf čakanja, wait-for-graph), kjer so vozlišča transakcije, robovi pa so usmerjeni od transakcij, ki čakajo na osvoboditev podatkov, do transakcij, ki so te podatke prevzele. Mrtva točka se štejemo, če graf vsebuje zanke. Izgradnja grafa čakanja je še posebej draga operacija v porazdeljenih podatkovnih bazah.
Dvojna blokada — preprečevanje mrtvih točk s tem, da transakcija na začetku prevzame vse vire, ki jih potrebuje, in jih sprosti na koncu.
Vse blokirne operacije morajo predhoditi prvi razburljivi operaciji. Ima dve fazi — fazo rasti (Growing Phase), kjer se kumulirajo prevzemi, in fazo krčenja (Shrinking Phase), kjer se sproščajo prevzemi. V primeru, da enega od virov ni mogoče prevzeti, se transakcija začne znova. Lahko se zgodi, da transakcija ne bo mogla prevzeti zahtevanih virov, na primer, če več transakcij tekmuje za iste vire.
Dvojni commit zagotavlja izvedbo commit-a na vseh replikah podatkovne baze.
Vsaka podatkovna baza vnese informacije o podatkih, ki bodo spremenjeni, v dnevnik in odgovori koordinatorju z OK (Voting Phase). Ko vsi odgovorijo z OK, koordinator pošlje signal, ki vse obvezuje k izvedbi commita. Po commitu strežnika odgovorijo z OK, če vsaj eden ne odgovori z OK, koordinator pošlje signal za preklic sprememb vsem strežnikom (Completion Phase).
Metoda časovnih žigov
Starejša transakcija se prekine, ko poskuša dostopati do podatkov, ki jih uporablja mlajša transakcija.
Vsaki transakciji je dodeljen časovni žig TS ki ustreza začetku njenega izvajanja. Če je Ti starejši Tj, potem TS(Ti) < TS(Tj).
Ko se transakcija vrne, ji je dodeljen nov časovni žig. Vsak podatek Q vključen v transakcijo je označen z dvema žigoma. W-TS(Q) — časovni žig najmlajše transakcije, ki je uspešno zapisala Q. R-TS(Q) — časovni žig najmlajše transakcije, ki je izvedla operacijo branja nad Q.
Ko transakcija T zahteva branje podatkov Q so na voljo dve možnosti.
Если TS(T) < W-TS(Q), to je, če so bili podatki posodobljeni s strani mlajše transakcije, se transakcija T vrne.
Если TS(T) >= W-TS(Q), branje pa se izvede in R-TS(Q) ustvarjanje storitev, ki bodo poenostavile delo z multioblakom. Ena od podjetij, ki se razvijajo na tem področju, je VMware. MAX(R-TS(Q), TS(T)).
Ko transakcija T zahteva spremembo podatkov Q so na voljo dve možnosti.
Если TS(T) < R-TS(Q), to je, če so bili podatki že prebrani s strani mlajše transakcije in če pride do spremembe, bo nastal konflikt. Transakcija T vrne.
Если TS(T) < W-TS(Q), to je, če transakcija poskuša prepisati novejšo vrednost, se transakcija T vrne. V ostalih primerih se sprememba izvede in W-TS(Q) postane enaka TS(T).
Ni potrebno drago graditi grafa čakanja. Starejše transakcije so odvisne od novejših, zato v grafu čakanja ni ciklov. Ni mrtvih blokad, saj transakcije ne čakajo, ampak se takoj vrnejo. Možni so kaskadni povratki. Če Ti se vrne, in Tj je prebrala podatke, ki jih je spremenila Ti, potem Tj prav tako mora vrniti. Če je pri tem Tj že bila potrjena, bo prišlo do kršitve načela trajnosti.
Ena od rešitev kaskadnih povratkov. Transakcija izvede vse operacije zapisa na koncu, pri čemer morajo druge transakcije čakati na zaključek te operacije. Transakcije čakajo na potrditev pred branjem.
Thomasova pravila pisanja — variacija metode časovnih žigov, pri kateri so podatki, ki jih je posodobil mlajša transakcija, prepovedani za prepis s staro
Transakcija T zahteva spremembo podatkov Q. Если TS(T) < W-TS(Q), to je, če transakcija poskuša prepisati novejšo vrednost, se transakcija T ne vrne, kot v metodi časovnih žigov.
Izvor: habr.com
