Transakcije
Transakcija je niz operacija nad podacima koji ima početak i kraj.
Transakcija je sekvencijalno izvršavanje operacija čitanja i pisanja. Završetak transakcije može biti ili spremanje promjena (urezivanje) ili otkazivanje promjena (povratak). U odnosu na bazu podataka, transakcija se sastoji od nekoliko zahtjeva koji se tretiraju kao jedan zahtjev.
Transakcije moraju zadovoljiti svojstva ACID
Atomicity. Transakcija je ili u potpunosti dovršena ili uopće nije završena.
Dosljednost. Prilikom dovršavanja transakcije ne smiju se kršiti ograničenja nametnuta podacima (na primjer, ograničenja u bazi podataka). Konzistentnost podrazumijeva da će sistem biti prebačen iz jednog ispravnog stanja u drugo ispravno stanje.
Izolacija. Transakcije koje se izvršavaju paralelno ne bi trebale uticati jedna na drugu, na primjer, promijeniti podatke koje koristi druga transakcija. Rezultat izvršavanja paralelnih transakcija trebao bi biti isti kao da se transakcije izvršavaju sekvencijalno.
Održivost. Jednom predate, promjene ne bi trebale biti izgubljene.
Dnevnik transakcija
Dnevnik pohranjuje promjene izvršene transakcijama, osigurava atomičnost i stabilnost podataka u slučaju kvara sistema
Dnevnik sadrži vrijednosti koje su podaci imali prije i nakon što ih je transakcija promijenila. Strategija dnevnika upisivanja unaprijed zahtijeva dodavanje zapisnika o prethodnim vrijednostima prije početka i o konačnim vrijednostima nakon što je transakcija završena. U slučaju iznenadnog zaustavljanja sistema, baza podataka čita log obrnutim redosledom i poništava promene izvršene transakcijama. Nakon što je naišla na prekinutu transakciju, baza podataka je izvršava i unosi promjene u dnevnik. Budući da je u stanju u trenutku neuspjeha, baza podataka čita log u naprijed redoslijedu i vraća promjene izvršene transakcijama. Na ovaj način se čuva stabilnost transakcija koje su već izvršene i atomičnost prekinute transakcije.
Jednostavno ponovno izvršavanje neuspjelih transakcija nije dovoljno za oporavak.
Primjer. Korisnik ima 500$ na svom računu i korisnik odlučuje da ih podigne sa bankomata. Dvije transakcije su u toku. Prvi očitava vrijednost bilansa i ako ima dovoljno sredstava na saldu, izdaje novac korisniku. Drugi oduzima potreban iznos od stanja. Recimo da se sistem srušio i prva operacija nije uspjela, ali druga jeste. U ovom slučaju, ne možemo ponovo izdati novac korisniku bez vraćanja sistema u prvobitno stanje sa pozitivnim stanjem.
Nivoi izolacije
Read Committed
Problem prljavog čitanja je da transakcija može pročitati međurezultat druge transakcije.
Primjer. Početna vrijednost bilansa je 0 USD. T1 dodaje $50 na vaš saldo. T2 očitava vrijednost bilansa ($50). T1 odbacuje promjene i izlazi. T2 nastavlja izvršavanje sa netačnim podacima o stanju.
Rješenje je čitanje fiksnih podataka (Read Committed), što zabranjuje čitanje podataka izmijenjenih transakcijom. Ako je transakcija A promijenila određeni skup podataka, onda je transakcija B, kada pristupa ovim podacima, prisiljena čekati da se transakcija A završi.
Ponovljivo čitanje
Problem izgubljenih ažuriranja. T1 sprema promjene na T2 promjene.
Primjer. Početna vrijednost bilansa je 0 USD i dvije transakcije istovremeno dopunjuju stanje. T1 i T2 očitavaju stanje od 0 dolara. T2 zatim dodaje $200 na $0 i pohranjuje rezultat. T1 dodaje $100 na $0 i pohranjuje rezultat. Konačni rezultat je 100 dolara umjesto 300 dolara.
Neponovljiv problem čitanja. Čitanje istih podataka više puta vraća različite vrijednosti.
Primjer. T1 čita vrijednost bilansa od $0. T2 zatim dodaje $50 na saldo i završava. T1 ponovo čita podatke i nalazi neslaganje sa prethodnim rezultatom.
Ponovljivo čitanje osigurava da će drugo čitanje vratiti isti rezultat. Podaci koje čita jedna transakcija ne mogu se mijenjati u drugim dok se transakcija ne završi. Ako je transakcija A pročitala određeni skup podataka, onda je transakcija B, kada pristupa ovim podacima, prisiljena čekati da se transakcija A završi.
Naručeno čitanje (serializable)
Problem sa fantomskim čitanjem. Dva upita koja biraju podatke na osnovu određenog uslova vraćaju različite vrijednosti.
Primjer. T1 traži broj svih korisnika čiji je stanje veći od 0 USD, ali manji od 100 USD. T2 oduzima 1 USD od korisnika sa stanjem od 101 USD. T1 ponovo izdaje zahtjev.
Naručeno čitanje (serializable). Transakcije se izvršavaju potpuno sekvencijalno. Zabranjeno je ažuriranje ili dodavanje zapisa koji potpadaju pod uslove zahtjeva. Ako je transakcija A zatražila podatke iz cijele tablice, tada se cijela tablica zamrzava za druge transakcije dok se transakcija A ne završi.
Planer
Postavlja redosled kojim bi se operacije trebale izvoditi tokom paralelnih transakcija.
Pruža određeni nivo izolacije. Ako rezultat operacija ne zavisi od njihovog redosleda, tada su takve operacije komutativne (permutativne). Operacije čitanja i operacije na različitim podacima su komutativne. Operacije čitanja-pisanja i pisanja-pisanja nisu komutativne. Zadatak planera je da isprepliće operacije koje izvode paralelne transakcije tako da rezultat izvršenja bude ekvivalentan sekvencijalnom izvršavanju transakcija.
Mehanizmi za kontrolu paralelnih poslova (Concurrency Control)
Optimističan se zasniva na otkrivanju i rješavanju konflikata, pesimističan na sprečavanju nastajanja sukoba.
U optimističkom pristupu, više korisnika ima na raspolaganju kopije podataka. Prva osoba koja završi uređivanje sprema promjene, dok ostali moraju spojiti promjene. Optimistički algoritam dozvoljava da dođe do sukoba, ali sistem se mora oporaviti od konflikta.
Sa pesimističkim pristupom, prvi korisnik koji uhvati podatke sprječava druge da ih prime. Ako su konflikti rijetki, mudro je izabrati optimističku strategiju, jer ona pruža viši nivo konkurentnosti.
Zaključavanje
Ako jedna transakcija ima zaključane podatke, onda druge transakcije moraju čekati dok se ne otključaju prilikom pristupa podacima.
Blok se može preklopiti na bazu podataka, tablicu, red ili atribut. Zajedničko zaključavanje može biti nametnuto istim podacima sa više transakcija, omogućava čitanje svih transakcija (uključujući i onu koja ga je nametnula), zabranjuje modifikaciju i ekskluzivno hvatanje. Ekskluzivno zaključavanje može biti nametnuto samo jednom transakcijom, dozvoljava bilo koje radnje nametnute transakcije, zabranjuje bilo kakve radnje drugih.
Mrtvo zaključavanje je situacija u kojoj transakcije završe u stanju čekanja koje traje neograničeno.
Primjer. Prva transakcija čeka da podaci koje je uhvatila druga budu pušteni, dok druga čeka da podaci koje je uhvatila prva budu pušteni.
Optimistično rješenje problema zastoja omogućava da dođe do zastoja, ali zatim oporavlja sistem vraćanjem jedne od transakcija uključenih u zastoj.
Zastoji se traže u određenim intervalima. Jedna od metoda detekcije je vremenski, odnosno smatrati da je došlo do zastoja ako transakcija traje predugo da se završi. Kada se pronađe zastoj, jedna od transakcija se poništava, omogućavajući drugim transakcijama uključenim u zastoj da se završe. Izbor žrtve može se zasnivati na vrijednosti transakcija ili njihovom stažu (šeme čekaj-umri i rane-čekaj).
Svaka transakcija T dodjeljuje se vremenska oznaka TS koji sadrži vrijeme početka transakcije.
Čekaj-Umri.
ako TS(Ti) < TS(Tj), onda Ti ceka, u suprotnom Ti vraća se i počinje ponovo sa istom vremenskom oznakom.
Ako je mlada transakcija stekla resurs, a starija transakcija zahtijeva isti resurs, tada je starijoj transakciji dopušteno da čeka. Ako je starija transakcija nabavila resurs, tada će se mlađa transakcija koja zahtijeva taj resurs biti vraćena.
Rana-čekaj.
ako TS(Ti) < TS(Tj), onda Tj vraća se unazad i počinje ponovo sa istom vremenskom oznakom, inače Ti čekanje.
Ako je mlađa transakcija nabavila resurs, a starija transakcija zahtijeva isti resurs, tada će se mlađa transakcija vratiti. Ako je starija transakcija stekla resurs, tada je mlađoj transakciji koja traži taj resurs dozvoljeno da čeka. Odabir žrtava zasnovan na prioritetu sprječava zastoje, ali vraća transakcije koje nisu u zastoju. Problem je u tome što se transakcije mogu vratiti mnogo puta jer... starija transakcija može zadržati resurs dugo vremena.
Pesimističko rješenje problema zastoja ne dozvoljava da se transakcija počne izvršavati ako postoji rizik od zastoja.
Da bi se otkrio zastoj, konstruiše se graf (graf čekanja, graf čekanja), čiji su vrhovi transakcije, a ivice su usmerene od transakcija koje čekaju objavljivanje podataka na transakciju koja je uhvatila ove podatke. Smatra se da je došlo do zastoja ako graf ima petlju. Izrada grafa čekanja, posebno u distribuiranim bazama podataka, je skupa procedura.
Dvofazno zaključavanje - sprječava zastoje tako što zaplijeni sve resurse koje koristi transakcija na početku transakcije i otpusti ih na kraju
Sve operacije blokiranja moraju prethoditi prvom otključavanju. Ima dvije faze - Fazu rasta, tokom koje se hvataljke akumuliraju, i Fazu smanjivanja, tokom koje se zahvati oslobađaju. Ako je nemoguće uhvatiti jedan od resursa, transakcija počinje ispočetka. Moguće je da transakcija neće moći steći potrebne resurse, na primjer, ako se više transakcija nadmeće za iste resurse.
Dvofazno urezivanje osigurava da se urezivanje izvršava na svim replikama baze podataka
Svaka baza podataka unosi informacije o podacima koji će biti promijenjeni u dnevnik i odgovara koordinatoru OK (Faza glasanja). Nakon što su svi odgovorili OK, koordinator šalje signal kojim obavezuje sve da se obavežu. Nakon urezivanja, serveri odgovaraju OK, ako barem jedan ne odgovori OK, tada koordinator šalje signal za otkazivanje promjena svim serverima (faza završetka).
Metoda vremenske oznake
Starija transakcija se poništava kada se pokuša pristupiti podacima uključenim u mlađu transakciju
Svakoj transakciji je dodijeljena vremenska oznaka TS koji odgovara vremenu početka izvršenja. Ako Ti stariji Tj, onda TS(Ti) < TS(Tj).
Kada se transakcija vrati, dodjeljuje joj se nova vremenska oznaka. Svaki objekt podataka Q uključen u transakciju označen je sa dvije oznake. W-TS(Q) — vremenska oznaka najmlađe transakcije koja je uspješno završila zapis Q. R-TS(Q) — vremenska oznaka najmlađe transakcije koja je izvršila zapis čitanja Q.
Kada transakcija T zahtjeva za čitanje podataka Q Postoje dvije opcije.
ako TS(T) < W-TS(Q), odnosno podaci su ažurirani mlađom transakcijom, zatim transakcijom T kotrlja nazad.
ako TS(T) >= W-TS(Q), zatim se vrši očitavanje i R-TS(Q) postaje MAX(R-TS(Q), TS(T)).
Kada transakcija T zahtijeva promjene podataka Q Postoje dvije opcije.
ako TS(T) < R-TS(Q), odnosno, podatke je već pročitala mlađa transakcija i ako se napravi promjena, doći će do sukoba. Transakcija T kotrlja nazad.
ako TS(T) < W-TS(Q), to jest, transakcija pokušava prepisati noviju vrijednost, transakcija T se vraća nazad. U ostalim slučajevima, promjena se vrši i W-TS(Q) postaje jednak TS(T).
Nije potrebna skupa konstrukcija grafa čekanja. Starije transakcije zavise od novijih, tako da u grafu čekanja nema ciklusa. Nema zastoja jer se transakcije ne čekaju već se odmah vraćaju. Moguća su kaskadna vraćanja. Ako Ti otkotrljao i Tj Pročitao sam podatke koje sam promijenio Ti, onda Tj takođe treba da se vrati. Ako u isto vreme Tj već počinjeno, onda će doći do kršenja principa stabilnosti.
Jedno od rješenja za kaskadno vraćanje. Transakcija završava sve operacije pisanja na kraju, a druge transakcije moraju čekati da se ta operacija završi. Transakcije čekaju da se potvrde prije nego što se pročitaju.
Thomasovo pravilo pisanja - varijacija metode vremenske oznake u kojoj je zabranjeno prepisivanje podataka ažuriranih mlađom transakcijom od strane starije
Transakcija T zahtijeva promjene podataka Q. Ako TS(T) < W-TS(Q), odnosno, transakcija pokušava prepisati noviju vrijednost, transakcija T se ne vraća nazad kao u metodi vremenske oznake.
izvor: www.habr.com