Transakcije
Transakcija je niz operacija nad podacima koja ima početak i kraj
Transakcija je sekvencijalno izvođenje operacija čitanja i pisanja. Kraj transakcije može biti ili spremanje promjena (potvrda, commit) ili poništavanje promjena (rollback). U kontekstu baza podataka, transakcija je nekoliko upita koji se tretiraju kao jedinstveni upit.
Transakcije moraju zadovoljavati ACID svojstva
Atomarnost. Transakcija se izvede ili potpuno ili se ne izvrši uopće.
Dosljednost. Kada se transakcija završi, ograničenja nametnuta na podatke ne smiju biti narušena (na primjer, constraints u bazi podataka). Dosljednost podrazumijeva da će sustav biti prebačen iz jednog ispravnog stanja u drugo ispravno.
Izoliranost. Paralelno izvođene transakcije ne smiju utjecati jedna na drugu, na primjer, mijenjati podatke koje koristi druga transakcija. Rezultat izvršavanja paralelnih transakcija trebao bi biti kao da su transakcije izvršene sekvencijalno.
Trajnost. Nakon potvrde, promjene ne smiju biti izgubljene.
Zapisnik transakcija
Zapisnik pohranjuje promjene koje su izvršene transakcijama, osigurava atomarnost i trajnost podataka u slučaju kvara sustava
Zapisnik sadrži vrijednosti koje su podaci imali prije i nakon promjene transakcijom. Strategija Write-ahead log obvezuje dodavanje zapisa o prethodnim vrijednostima prije početka, a o konačnim nakon završetka transakcije. U slučaju iznenadne pauze sustava, baza podataka čita log obrnutim redoslijedom i poništava promjene napravljene transakcijama. U slučaju prekinute transakcije, baza podataka će je izvršiti i unijeti promjene u zapisnik. U stanju u kojem je bila u trenutku kvara, baza podataka čita log u pravom redoslijedu i vraća promjene napravljenih transakcijama. Tako se osigurava trajnost transakcija koje su već bile potvrđene i atomarnost prekinute transakcije.
Jednostavno ponavljanje neispravnih transakcija nije dovoljno za oporavak.
Primjer. Na računu korisnika je 500$ i korisnik odlučuje podići ih putem bankomata. Izvode se dvije transakcije. Prva čita stanje na računu, i ako ima dovoljno sredstava, isplaćuje novac korisniku. Druga oduzima potrebni iznos od stanja. Pretpostavimo da je došlo do kvara sustava i prva operacija se nije izvršila, dok se druga izvršila. U tom slučaju ne možemo ponovno isplatiti novac korisniku bez vraćanja sustava u izvorno stanje s pozitivnim saldom.
Razine izolacije
Čitanje potvrđenih podataka (Read Committed)
Problem prljavog čitanja (Dirty Read) se sastoji u tome da transakcija može pročitati međurezultate rada druge transakcije.
Primjer. Početna vrijednost salda 0$. T1 dodaje 50$ na saldo. T2 čita saldo (50$). T1 odbacuje promjene i završava. T2 nastavlja s izvršavanjem s pogrešnim podacima o saldu.
Rješenje je čitanje potvrđenih podataka (Read Committed) koje zabranjuje čitanje podataka koji su promijenjeni transakcijom. Ako je transakcija A promijenila određeni skup podataka, tada je transakcija B pri pokušaju pristupa tim podacima primorana čekati završetak transakcije A.
Ponovljivo čitanje (Repeatable Read)
Problem izgubljenih promjena (Lost Updates). T1 sprema promjene preko promjena T2.
Primjer. Početna vrijednost salda 0$ i dvije transakcije istovremeno dopunjuju saldo. T1 i T2 čitaju saldo koji iznosi 0$. Zatim T2 dodaje 200$ na 0$ i sprema rezultat. T1 dodaje 100$ na 0$ i sprema rezultat. Krajni rezultat je 100$ umjesto 300$.
Problem neopetljivog čitanja (Unrepeatable read). Ponovno čitanje istih podataka vraća različite vrijednosti.
Primjer. T1 čita vrijednost salda koja iznosi 0$. Zatim T2 dodaje 50$ na saldo i završava. T1 ponovno čita podatke i otkriva neslaganje s prethodnim rezultatom.
Ponovljivo čitanje (Repeatable Read) jamči da će ponovno čitanje dati isti rezultat. Podaci pročitani od strane jedne transakcije ne smiju se mijenjati u drugim sve do završetka transakcije. Ako je transakcija A pročitala određeni skup podataka, tada je transakcija B pri pokušaju pristupa tim podacima primorana čekati završetak transakcije A.
Poredano čitanje (Serializable)
Problem fantomskog čitanja (Phantom Reads). Dva upita koja odabiru podatke prema određenom uvjetu vraćaju različite vrijednosti.
Primjer. T1 traži broj svih korisnika čiji je saldo veći od 0$ ali manji od 100$. T2 oduzima 1$ od korisnika sa saldom od 101$. T1 ponovo izvršava upit.
Poredano čitanje (Serializable). Transakcije se izvode kao potpuno sekvencijalne. Zabranjeno je ažurirati i dodavati zapise koji podliježu uvjetima upita. Ako je transakcija A zatražila podatke iz cijele tablice, tada se tablica potpuno zamrzava za ostale transakcije do završetka transakcije A.
Planer (Scheduler)
Postavlja redoslijed u kojem se operacije trebaju izvršavati tijekom paralelnih transakcija.
Osigurava zadanu razinu izolacije. Ako rezultat izvršavanja operacija ne ovisi o njihovom redoslijedu, takve su operacije komutativne (Permutable). Komutativne su operacije čitanja i operacije nad različitim podacima. Operacije čitanja-upisa i upisa-upisa nisu komutativne. Zadatak planera je naizmjenično raspoređivati operacije koje izvode paralelne transakcije tako da je rezultat izvršavanja ekvivalentan sekvencijalnom izvršavanju transakcija.
Mehanizmi kontrole paralelnih zadataka (Concurrency Control)
Optimistički se temelji na otkrivanju i rješavanju sukoba, pesimistički na sprječavanju nastanka sukoba.
Kod optimističkog pristupa više korisnika dobiva kopije podataka. Prvi koji završi s uređivanjem sprema promjene, ostali moraju izvršiti spajanje promjena. Optimistički algoritam dopušta sukob, ali sustav se mora oporaviti nakon sukoba.
Kod pesimističkog pristupa prvi korisnik koji zauzme podatke sprječava pristup podacima ostalima. Ako su sukobi rijetki, razumno je odabrati optimističku strategiju jer ona omogućava višu razinu paralelizma.
Zaključavanje (Locking)
Ako jedna transakcija zaključava podatke, ostale transakcije prilikom pristupa podacima moraju čekati otključavanje.
Blok se može postaviti na bazu podataka, tablicu, red ili atribut. Zajedničko zaključavanje (Shared Lock) može se primijeniti na iste podatke od strane više transakcija, dozvoljavajući svim transakcijama (uključujući onu koja je postavila) čitanje, ali zabranjuje izmjenu i ekskluzivno zaključavanje. Ekskluzivno zaključavanje (Exclusive Lock) može se postaviti samo od strane jedne transakcije, dozvoljavajući sve radnje transakcije koja ga je postavila, a zabranjuje sve radnje ostalim.
Situacija u kojoj se transakcije nalaze u stanju čekanja koje traje beskonačno dugo smatra se međusobnim blokiranjem.
Primjer. Prva transakcija čeka oslobađanje podataka koje druga transakcija drži, dok druga čeka oslobađanje podataka koje prva drži.
Optimizirano rješenje za problem međusobnog blokiranja dopušta da do njega dođe, ali zatim obnavlja sustav poništavajući jednu od transakcija uključenih u međusobno blokiranje.
S određenom frekvencijom provodi se pretraživanje za međusobna blokiranja. Jedan od načina otkrivanja je vremenski, tj. smatra se da je došlo do međusobnog blokiranja ako transakcija traje predugo. Kada se otkrije međusobno blokiranje, jedna od transakcija se poništava, omogućavajući drugim transakcijama uključenim u blokiranje da završe. Odabir žrtve može se temeljiti na trošku transakcija ili njihovom starijem statusu (Wait-Die i Wound-wait sheme).
Svakoj transakciji T dodjeljuje se vremenska oznaka TS koja sadrži vrijeme početka izvršavanja transakcije.
Wait-Die.
Ako TS(Ti) < TS(Tj), tada Ti čeka, inače Ti se poništava i počinje iznova s istom vremenskom oznakom.
Ako mlađa transakcija drži resurs, a starija zahtijeva isti resurs, starijoj transakciji je dozvoljeno čekati. Ako starija transakcija drži resurs, mlađa transakcija koja zahtijeva taj resurs će biti poništena.
Wound-wait.
Ako TS(Ti) < TS(Tj), tada Tj se poništava i počinje iznova s istom vremenskom oznakom, inače Ti čeka.
Ako je mlađa transakcija zauzela resurs, a starija transakcija traži taj isti resurs, mladja transakcija će biti otkazana. Ako je starija transakcija zauzela resurs, mlađoj transakciji koja traži taj resurs je dopušteno čekati. Odabir žrtve na osnovu starosti sprečava pojavu međusobnih blokada, ali otkazuje transakcije koje nisu u stanju međusobnog blokiranja. Problem je u tome što se transakcije mogu otkazivati više puta, jer starija transakcija može dugo zadržavati resurs.
Pesimistično rešenje problema međusobnih blokada ne dopušta transakciji da započne izvršavanje ako postoji rizik od pojave međusobne blokade.
Za otkrivanje međusobne blokade gradi se graf (graf čekanja, wait-for-graph), čvorovi su transakcije, a grane su usmerene od transakcija koje čekaju oslobađanje podataka ka transakcijama koje su zauzele te podatke. Smatra se da je došlo do međusobne blokade ako graf ima cikličnost. Gradnja grafova čekanja, posebno u distribuiranim BDP-ima, je skupa procedura.
Dvostruka blokada - sprečavanje međusobnih blokada tako što se svi resursi koje koristi transakcija zauzimaju na početku transakcije i oslobađaju na kraju.
Sve blokirajuće operacije moraju prethoditi prvoj operaciji otpuštanja. Ima dve faze - Faza rasta u kojoj se akumuliraju zauzimanja i Faza smanjenja u kojoj se oslobađaju zauzimanja. U slučaju nemogućnosti zauzimanja jednog od resursa, transakcija počinje ispočetka. Može doći do situacije kada transakcija ne može zauzeti potrebne resurse, na primer, ako više transakcija konkuriše za iste resurse.
Dvostruko potvrđivanje osigurava izvršenje potvrde na svim replikama BDP-a.
Svaka BDP unosi informacije o podacima koji će biti promenjeni u log i odgovara koordinatorki sa OK (Faza glasanja). Nakon što svi odgovore sa OK, koordinator šalje signal koji obavezuje sve da izvrše potvrdu. Nakon potvrde poslužitelja odgovaraju sa OK, ako barem jedan ne odgovori sa OK, koordinator šalje signal za povlačenje svih promena svim serverima (Faza završetka).
Metod vremenskih oznaka
Starija transakcija se otkazuje prilikom pokušaja pristupanja podacima koji su uključeni mlađom transakcijom
Svakoj transakciji dodjeljuje se vremenska oznaka TS koja odgovara vremenu početka izvršavanja. Ako Ti je starija Tj, tada TS(Ti) < TS(Tj).
Kada se transakcija poništi, dodjeljuje joj se nova vremenska oznaka. Svaki objekt podataka Q uključen u transakciju označava se s dvije oznake. W-TS(Q) — vremenska oznaka najmlađe transakcije koja je uspješno izvršila zapis preko Q. R-TS(Q) — vremenska oznaka najmlađe transakcije koja je izvršila zapis čitanja preko Q.
Kada transakcija T traži čitanje podataka Q postoje dvije mogućnosti.
Ako TS(T) < W-TS(Q), tj. ako su podaci ažurirani od strane mladije transakcije, tada se transakcija T poništava.
Ako TS(T) >= W-TS(Q), tada se čitanje izvršava i R-TS(Q) postaje MAX(R-TS(Q), TS(T)).
Kada transakcija T traži promjenu podataka Q postoje dvije mogućnosti.
Ako TS(T) < R-TS(Q), tj. ako su podaci već bili pročitani od strane mladije transakcije, a ako se izvrši promjena, doći će do sukoba. Transakcija T poništava.
Ako TS(T) < W-TS(Q), tj. ako transakcija pokušava prepisati noviju vrijednost, transakcija T se poništava. U ostalim slučajevima promjena se izvršava i W-TS(Q) postaje jednako TS(T).
Nije potrebno skupo građenje grafa čekanja. Starije transakcije ovise o novijima, stoga u grafu čekanja nema ciklusa. Nema međusobnih blokada, budući da transakcije ne čekaju, već odmah poništavaju. Mogući su kaskadni poništaji. Ako Ti se poništi, a Tj je pročitala podatke koje je promijenila Ti, tada Tj ona također mora biti poništena. Ako je pritom Tj već bila potvrđena, doći će do kršenja načela stabilnosti.
Jedno od rješenja za kaskadne poništaje. Transakcija izvršava sve operacije zapisa na kraju, a druge transakcije moraju čekati završetak te operacije. Transakcije čekaju potvrdu prije čitanja.
Thomasova pravila za pisanje - varijacija metode vremenskih oznaka prema kojoj podaci ažurirani od strane mladije transakcije ne mogu se prepisivati starijom
Transakcija T traži promjenu podataka Q. Ako TS(T) < W-TS(Q), tj. ako transakcija pokušava prepisati noviju vrijednost, transakcija T se ne poništava kao u metodi vremenskih oznaka.
Izvor: habr.com
