Tranzacții
O tranzacție este o secvență de operații asupra datelor care are un început și un sfârșit.
O tranzacție este o execuție secvențială a operațiunilor de citire și scriere. Sfârșitul unei tranzacții poate fi fie salvarea modificărilor (commit), fie anularea modificărilor (rollback). În cazul bazelor de date, o tranzacție constă din mai multe cereri, care sunt interpretate ca o singură cerere.
Tranzacțiile trebuie să respecte proprietățile ACID.
Atomicitate. O tranzacție fie se execută complet, fie nu se execută deloc.
Consistență. La finalizarea unei tranzacții, constrângerile impuse asupra datelor (de exemplu, constraints în bazele de date) nu trebuie să fie încălcate. Consistența implică faptul că sistemul va fi transformat dintr-o stare corectă într-o altă stare corectă.
Izolare. Tranzacțiile care rulează în paralel nu trebuie să influențeze una asupra celeilalte, de exemplu, să schimbe datele utilizate de o altă tranzacție. Rezultatul execuției tranzacțiilor paralele trebuie să fie acela ca și cum tranzacțiile s-ar fi executat secvențial.
Persistență. După commit, modificările nu trebuie pierdute.
Jurnalul tranzacțiilor.
Jurnalul stochează modificările efectuate de tranzacții, asigurând atomicitatea și persistența datelor în caz de eșec al sistemului.
Jurnalul conține valorile pe care datele le aveau înainte și după modificarea acestora de către tranzacție. Strategia Write-ahead log obligă adăugarea în jurnal a înregistrărilor pentru valorile anterioare înainte de începutul tranzacției, iar pentru cele finale după finalizarea acesteia. În caz de oprire bruscă a sistemului, baza de date citește jurnalul în ordine inversă și anulează modificările efectuate de tranzacții. La întâlnirea unei tranzacții întrerupte, baza de date o finalizează și înregistrează modificările în jurnal. Fiind în starea de la momentul eșecului, baza de date citește jurnalul în ordine directă și returnează modificările efectuate de tranzacții. Astfel, se păstrează persistența tranzacțiilor care au fost deja confirmate și atomicitatea tranzacției întrerupte.
O simplă reluare a tranzacțiilor eronate nu este suficientă pentru recuperare.
Exemplu. Utilizatorul are un sold de 500$ și decide să îi retragă prin ATM. Se efectuează două tranzacții. Prima citește valoarea soldului și, dacă soldul este suficient, eliberează banii utilizatorului. A doua scade suma necesară din sold. Să presupunem că a avut loc o defecțiune a sistemului și prima operațiune nu s-a finalizat, dar a doua a fost efectuată. În acest caz, nu putem elibera din nou banii utilizatorului fără a readuce sistemul la starea inițială cu un sold pozitiv.
Niveluri de izolare
Citirea datelor fixe (Read Committed)
Problema citirii murdare (Dirty Read) constă în faptul că o tranzacție poate citi un rezultat intermediar al unei alte tranzacții.
Exemplu. Valoarea inițială a soldului este 0$. T1 adaugă 50$ la sold. T2 citește valoarea soldului (50$). T1 anulează modificările și se finalizează. T2 continuă executarea având date eronate despre sold.
Soluția constă în citirea datelor fixe (Read Committed) care interzice citirea datelor modificate de o tranzacție. Dacă tranzacția A a modificat un set de date, atunci tranzacția B, când solicită aceste date, este obligată să aștepte finalizarea tranzacției A.
Citirea repetabilă (Repeatable Read)
Problema actualizărilor pierdute (Lost Updates). T1 salvează modificările deasupra modificărilor T2.
Exemplu. Valoarea inițială a soldului este 0$ și două tranzacții umple simultan soldul. T1 și T2 citesc un sold egal cu 0$. Apoi T2 adaugă 200$ la 0$ și salvează rezultatul. T1 adaugă 100$ la 0$ și salvează rezultatul. Rezultatul final este 100$ în loc de 300$.
Problema citirii nerepetabile (Unrepeatable read). Citirea repetată a acelorași date returnează valori diferite.
Exemplu. T1 citește valoarea soldului egală cu 0$. Apoi T2 adaugă 50$ la sold și se finalizează. T1 citește din nou datele și descoperă o discrepanță față de rezultatul anterior.
Citirea repetabilă (Repeatable Read) garantează că citirea repetată va returna același rezultat. Datele citite de o tranzacție nu pot fi modificate de altele până la finalizarea tranzacției. Dacă tranzacția A a citit un anumit set de date, tranzacția B, când solicită aceste date, este obligată să aștepte finalizarea tranzacției A.
Citirea ordonată (Serializable)
Problema citirii fantomă (Phantom Reads). Două interogări care selectează date pe o anumită condiție returnează valori diferite.
Exemplu. T1 solicită numărul tuturor utilizatorilor ale căror solduri sunt mai mari de 0$ dar mai mici de 100$. T2 scade 1$ de la utilizatorul cu un sold de 101$. T1 efectuează din nou interogarea.
Citire ordonată (Serializable). Tranzacțiile sunt executate ca fiind complet secvențiale. Este interzisă actualizarea sau adăugarea de înregistrări care se încadrează în condițiile interogării. Dacă tranzacția A a solicitat datele întregii tabele, tabela este complet blocată pentru celelalte tranzacții până la finalizarea tranzacției A.
Programator (Scheduler)
Stabilește ordinea în care trebuie să fie efectuate operațiile în cazul tranzacțiilor care se desfășoară în paralel.
Asigură un nivel specific de izolare. Dacă rezultatul execuției operațiunilor nu depinde de ordinea acestora, atunci astfel de operații sunt comutabile (Permutable). Operațiile de citire și operațiile pe date diferite sunt comutabile. Operațiile de citire-scriere și cele de scriere-scriere nu sunt comutabile. Sarcina programatorului este de a alterna operațiile efectuate de tranzacțiile paralele astfel încât rezultatul final să fie echivalent cu execuția secvențială a tranzacțiilor.
Mecanisme de control al sarcinilor paralele (Concurrency Control)
Optimistul se bazează pe detectarea și rezolvarea conflictelor, pesimistul pe prevenirea apariției conflictelor.
În abordarea optimistă, mai mulți utilizatori primesc în gestionare copii ale datelor. Primul care finalizează editarea salvează modificările, ceilalți trebuie să realizeze o fuziune a modificărilor. Algoritmul optimist permite apariția conflictului, dar sistemul trebuie să se recupereze după acesta.
În abordarea pesimistă, primul utilizator care capturează datele împiedică obținerea datelor de către ceilalți. Dacă conflictele sunt rare, este rezonabil să alegi strategia optimistă, deoarece oferă un nivel mai înalt de paralelism.
Blocarea (Locking)
Dacă o tranzacție a blocat datele, atunci celelalte tranzacții care accesează aceste date trebuie să aștepte deblocarea.
Un bloc poate fi aplicat unei baze de date, unei tabele, unei linii sau unui atribut. Un blocare comună (Shared Lock) poate fi aplicată asupra unor date de mai multe tranzacții, permițând tuturor tranzacțiilor (inclusiv celei care a aplicat-o) să citească, dar interzicând modificarea și blocarea exclusivă. O blocare exclusivă (Exclusive Lock) poate fi aplicată doar unei singure tranzacții, permițând orice acțiuni tranzacției care a aplicat-o, dar interzicând orice acțiuni celorlalte.
O blocare de interblocare este o situație în care tranzacțiile se află într-o stare de așteptare, care durează la nesfârșit.
Exemplu. Prima tranzacție așteaptă eliberarea datelor blocate de a doua, în timp ce a doua așteaptă eliberarea datelor blocate de prima.
Soluția optimistă pentru problema interblocărilor permite interblocarea să aibă loc, dar apoi restaurează sistemul, făcând rollback uneia dintre tranzacțiile implicate în interblocare.
Cu o anumită frecvență, se realizează căutarea interblocărilor. Una dintre modalitățile de detectare este în funcție de timp, adică se consideră că a apărut o interblocare dacă o tranzacție durează prea mult. Atunci când se găsește o interblocare, una dintre tranzacții este anulată, ceea ce oferă posibilitatea altor tranzacții implicate în interblocare să finalizeze. Alegerea victimei poate fi bazată pe costul tranzacțiilor sau pe vechimea acestora (schemele Wait-Die și Wound-wait).
Fiecărei tranzacții T îi este atribuită un timestamp TS care conține timpul de început al execuției tranzacției.
Wait-Die.
Dacă TS(Ti) < TS(Tj), atunci Ti așteaptă, altfel Ti este anulată și începe din nou cu același timestamp.
Dacă o tranzacție tânără a blocat o resursă, iar o tranzacție mai veche cere aceeași resursă, tranzacției mai vechi i se permite să aștepte. Dacă tranzacția mai veche a blocat resursa, tranzacția tânără care solicită această resursă va fi anulată.
Wound-wait.
Dacă TS(Ti) < TS(Tj), atunci Tj este anulată și începe din nou cu același timestamp, altfel Ti așteaptă.
Dacă o tranzacție mai tânără a obținut un resurs, iar o tranzacție mai veche solicită aceleași resurse, tranzacția mai tânără va fi anulată. Dacă o tranzacție mai veche a obținut resursul, tranzacției mai tinere i se permite să aștepte pentru a solicita acel resurs. Alegerea victimei pe baza vechimii previne apariția blocajelor, dar anulează tranzacțiile care nu sunt blocate reciproc. Problema constă în faptul că tranzacțiile pot fi anulate de mai multe ori, deoarece o tranzacție mai veche poate menține resursa pentru mult timp.
O soluție pesimistă pentru problema blocajelor nu permite tranzacției să înceapă execuția dacă există riscul de a cauza un blocaj.
Pentru a detecta blocajele se construiește un grafic (graficul așteptării, wait-for-graph), vârfurile căruia sunt tranzacții, iar arcele sunt direcționate de la tranzacțiile care așteaptă eliberarea datelor către tranzacția care a obținut aceste date. Se consideră că s-a produs un blocaj dacă graficul este ciclic. Construirea graficului de așteptare, mai ales în baza de date distribuite, este o procedură costisitoare.
Blocarea în două faze previne blocajele prin obținerea tuturor resurselor folosite de tranzacție la începutul tranzacției și eliberarea lor la final.
Toate operațiunile de blocare trebuie să preceadă prima operațiune de deblocare. Are două faze — Faza de Creștere în care se acumulează obțineri și Faza de Scădere în care se eliberează obținerile. În cazul în care nu este posibil să se obțină o resursă, tranzacția începe de la capăt. Poate exista o situație în care tranzacția nu poate obține resursele necesare, de exemplu, dacă mai multe tranzacții concurează pentru aceleași resurse.
Comiterea în două faze garantează executarea comiterii pe toate replicile bazei de date.
Fiecare bază de date înregistrează informații despre datele care vor fi modificate în jurnal și răspunde coordonatorului cu OK (Faza de Votare). După ce toate răspund cu OK, coordonatorul trimite un semnal care obligă pe toți să efectueze comiterea. După comitere, server răspund cu OK; dacă măcar unul nu a răspuns cu OK, coordonatorul trimite un semnal care anulează modificările tuturor serverelor (Faza de Completare).
Metoda etichetelor temporale.
O tranzacție mai veche este anulată în momentul în care încearcă să acceseze datele implicate de o tranzacție mai tânără.
Fiecărei tranzacții i se atribuie un marcaj temporal TS corespunzător momentului de început al execuției. Dacă Ti este mai veche Tj, atunci TS(Ti) < TS(Tj).
Când o tranzacție este retrogradată, i se atribuie un nou marcaj temporal. Fiecare obiect de date Q implicat în tranzacție este marcat cu două mărci. W-TS(Q) — marcajul temporal al celei mai recente tranzacții care a efectuat cu succes scrierea asupra Q. R-TS(Q) — marcajul temporal al celei mai recente tranzacții care a efectuat scrierea pentru citire asupra Q.
Când tranzacția T solicită citirea datelor Q sunt posibile două opțiuni.
Dacă TS(T) < W-TS(Q), adică datele au fost actualizate de o tranzacție mai recentă, atunci tranzacția T se retrogradează.
Dacă TS(T) >= W-TS(Q), atunci citirea se efectuează și R-TS(Q) devine MAX(R-TS(Q), TS(T)).
Când tranzacția T solicită modificarea datelor Q sunt posibile două opțiuni.
Dacă TS(T) < R-TS(Q), adică datele au fost deja citite de o tranzacție mai recentă și dacă se efectuează modificarea, va apărea un conflict. Tranzacția T se retrogradează.
Dacă TS(T) < W-TS(Q), adică tranzacția încearcă să rescrie o valoare mai nouă, tranzacția T se retrogradează. În celelalte cazuri, modificarea se efectuează și W-TS(Q) devine egal cu TS(T).
Nu este necesară construcția costisitoare a unui grafic de așteptare. Tranzacțiile mai vechi depind de cele mai noi, prin urmare în graficul de așteptare nu există cicluri. Nu sunt blocaje reciproce, deoarece tranzacțiile nu așteaptă, ci se retrogradează imediat. Pot apărea retrogradări în cascadă. Dacă Ti s-a retrogradat, iar Tj a citit datele pe care le-a modificat Ti, atunci Tj de asemenea trebuie să se retrogradeze. Dacă în acest timp Tj a fost deja confirmată, va apărea încălcarea principiului de consistență.
Una dintre soluțiile pentru retrogradările în cascadă. Tranzacția efectuează toate operațiunile de scriere la sfârșit, iar celelalte tranzacții sunt obligate să aștepte finalizarea acestei operațiuni. Tranzacțiile așteaptă confirmarea înainte de a citi.
Regula de scriere Thomas — o variație a metodei marcajelor temporare prin care datele actualizate de o tranzacție mai recentă nu pot fi rescrise de o tranzacție mai veche
Transacție T solicită modificarea datelor Q. Dacă TS(T) < W-TS(Q), adică tranzacția încearcă să rescrie o valoare mai nouă, tranzacția T nu se retrogradează ca în metoda marcajelor temporare.
Sursa: habr.com
