Tranzacție
O tranzacție este o secvență de operațiuni pe date care are un început și un sfârșit.
O tranzacție este execuția 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 legătură cu o bază de date, o tranzacție constă din mai multe cereri care sunt tratate ca o singură cerere.
Tranzacțiile trebuie să îndeplinească proprietățile ACID
Atomicitatea. Tranzacția este fie finalizată complet, fie deloc.
Consecvență. La finalizarea unei tranzacții, restricțiile impuse datelor (de exemplu, constrângerile din baza de date) nu trebuie încălcate. Consecvența implică faptul că sistemul va fi transferat de la o stare corectă la alta.
Izolare. Tranzacțiile care rulează în paralel nu ar trebui să se influențeze reciproc, de exemplu, să modifice datele utilizate de o altă tranzacție. Rezultatul executării tranzacțiilor paralele ar trebui să fie același ca și cum tranzacțiile ar fi executate secvenţial.
Durabilitate. Odată efectuate, modificările nu trebuie pierdute.
Jurnal de tranzacții
Jurnalul stochează modificările efectuate prin tranzacții, asigură atomicitatea și stabilitatea datelor în cazul unei defecțiuni a sistemului
Jurnalul conține valorile pe care datele le-au avut înainte și după ce au fost modificate de tranzacție. Strategia de jurnal de scriere anticipată necesită adăugarea unei intrări de jurnal despre valorile anterioare înainte de începere și despre valorile finale după finalizarea tranzacției. În cazul unei opriri bruște a sistemului, baza de date citește jurnalul în ordine inversă și anulează modificările efectuate prin tranzacții. După ce a întâlnit o tranzacție întreruptă, baza de date o execută și face modificări despre aceasta în jurnal. Fiind în starea la momentul defecțiunii, baza de date citește jurnalul în ordine de avans și returnează modificările efectuate prin tranzacții. În acest fel, se păstrează stabilitatea tranzacțiilor care au fost deja comise și atomicitatea tranzacției întrerupte.
Simpla reexecuție a tranzacțiilor eșuate nu este suficientă pentru recuperare.
Exemplu. Utilizatorul are 500 USD în cont și utilizatorul decide să-i retragă de la un bancomat. Două tranzacții sunt în curs. Primul citește valoarea soldului și dacă există suficiente fonduri pe sold, emite bani utilizatorului. Al doilea scade suma necesară din sold. Să presupunem că sistemul s-a prăbușit și prima operațiune a eșuat, dar a doua a făcut-o. În acest caz, nu putem reemite bani utilizatorului fără a readuce sistemul la starea inițială cu un sold pozitiv.
Niveluri de izolare
Citiți Angajat
Problema Dirty Read este că o tranzacție poate citi rezultatul intermediar al unei alte tranzacții.
Exemplu. Valoarea soldului inițial este de 0 USD. T1 adaugă 50 USD la soldul dvs. T2 citește valoarea soldului (50 USD). T1 renunță la modificări și iese. T2 continuă execuția cu date de sold incorecte.
Soluția este citirea datelor fixe (Read Committed), care interzice citirea datelor modificate de tranzacție. Dacă tranzacția A a schimbat un anumit set de date, atunci tranzacția B, atunci când accesează aceste date, este forțată să aștepte finalizarea tranzacției A.
Citire repetabilă
Problemă cu actualizările pierdute. T1 salvează modificările pe lângă modificările T2.
Exemplu. Valoarea soldului inițial este de 0 USD și două tranzacții simultan reîncarcă soldul. T1 și T2 citesc un sold de 0 USD. T2 adaugă apoi $200 la $0 și salvează rezultatul. T1 adaugă 100 USD la 0 USD și salvează rezultatul. Rezultatul final este de 100 USD în loc de 300 USD.
Problemă de citire irepetabilă. Citirea acelorași date în mod repetat returnează valori diferite.
Exemplu. T1 citește o valoare a soldului de 0 USD. T2 adaugă apoi 50 USD la sold și se termină. T1 citește din nou datele și găsește o discrepanță cu rezultatul anterior.
Citirea repetabilă asigură că o a doua citire va returna același rezultat. Datele citite de o tranzacție nu pot fi modificate în altele până când tranzacția este finalizată. Dacă tranzacția A a citit un anumit set de date, atunci tranzacția B, atunci când accesează aceste date, este forțată să aștepte finalizarea tranzacției A.
Citire ordonată (serializată)
Problemă Phantom Reads. Două interogări care selectează date pe baza unei anumite condiții returnează valori diferite.
Exemplu. T1 solicită numărul tuturor utilizatorilor al căror sold este mai mare de 0 USD, dar mai mic de 100 USD. T2 deduce 1 USD de la un utilizator cu un sold de 101 USD. T1 reemite cererea.
Lectură ordonată (serializată). Tranzacțiile sunt executate complet secvenţial. Este interzisă actualizarea sau adăugarea înregistrărilor care se încadrează în termenii solicitării. Dacă tranzacția A a solicitat date din întregul tabel, atunci întregul tabel este înghețat pentru alte tranzacții până la finalizarea tranzacției A.
Programator
Stabilește ordinea în care operațiunile trebuie efectuate în timpul tranzacțiilor paralele.
Oferă un anumit nivel de izolare. Dacă rezultatul operațiilor nu depinde de ordinea lor, atunci astfel de operații sunt comutative (permutabile). Operațiile de citire și operațiile pe diferite date sunt comutative. Operațiile de citire-scriere și scriere-scriere nu sunt comutative. Sarcina planificatorului este să intercaleze operațiunile efectuate prin tranzacții paralele, astfel încât rezultatul execuției să fie echivalent cu execuția secvențială a tranzacțiilor.
Mecanisme pentru controlul joburilor paralele (Concurrency Control)
Optimistul se bazează pe detectarea și rezolvarea conflictelor, pesimismul se bazează pe prevenirea apariției conflictelor.
În abordarea optimistă, mai mulți utilizatori au la dispoziție copii ale datelor. Prima persoană care finalizează editarea salvează modificările, în timp ce ceilalți trebuie să îmbine modificările. Un algoritm optimist permite să apară conflicte, dar sistemul trebuie să-și revină din conflict.
Cu o abordare pesimistă, primul utilizator care captează datele îi împiedică pe alții să primească datele. Dacă conflictele sunt rare, este înțelept să alegeți strategia optimistă, deoarece oferă un nivel mai ridicat de concurență.
Blocare
Dacă o tranzacție are date blocate, alte tranzacții trebuie să aștepte până când sunt deblocate atunci când accesează datele.
Un bloc poate fi suprapus pe o bază de date, tabel, rând sau atribut. Blocarea partajată poate fi impusă acelorași date prin mai multe tranzacții, permite citirea tuturor tranzacțiilor (inclusiv celei care a impus-o), interzice modificarea și capturarea exclusivă. Blocarea exclusivă poate fi impusă printr-o singură tranzacție, permite orice acțiuni ale tranzacției impunătoare, interzice orice acțiuni ale altora.
Un impas este o situație în care tranzacțiile ajung într-o stare în așteptare care durează la infinit.
Exemplu. Prima tranzacție așteaptă ca datele capturate de al doilea să fie eliberate, în timp ce a doua așteaptă ca datele capturate de primul să fie eliberate.
O soluție optimistă la problema blocajului permite blocarea să apară, dar apoi recuperează sistemul prin derularea înapoi a uneia dintre tranzacțiile implicate în blocaj.
Blocajele sunt căutate la anumite intervale. Una dintre metodele de detectare este în timp, adică să luați în considerare că a apărut un impas dacă tranzacția durează prea mult pentru a se finaliza. Când este găsit un blocaj, una dintre tranzacții este anulată, permițând finalizarea altor tranzacții implicate în blocaj. Alegerea victimei se poate baza pe valoarea tranzacțiilor sau pe vechimea acestora (scheme Wait-Die și Wound-wait).
Fiecare tranzacție T este atribuit un marcaj de timp TS care conțin ora de începere a tranzacției.
Așteaptă-Moară.
Dacă TS(Ti) < TS(Tj), Apoi, Ti asteapta, altfel Ti se derulează înapoi și începe din nou cu același marcaj temporal.
Dacă o tranzacție tânără a achiziționat o resursă și o tranzacție mai veche solicită aceeași resursă, atunci tranzacția mai veche are voie să aștepte. Dacă o tranzacție mai veche a achiziționat o resursă, atunci tranzacția mai tânără care solicită acea resursă va fi anulată.
Rană-așteaptă.
Dacă TS(Ti) < TS(Tj), Apoi, Tj se derulează înapoi și începe din nou cu același marcaj temporal, în caz contrar Ti aşteptare.
Dacă o tranzacție mai tânără a achiziționat o resursă și o tranzacție mai veche solicită aceeași resursă, atunci tranzacția mai tânără va fi anulată. Dacă o tranzacție mai veche a achiziționat o resursă, atunci tranzacția mai tânără care solicită acea resursă are voie să aștepte. Selectarea victimelor pe bază de precedență previne blocajele, dar derulează înapoi tranzacțiile care nu sunt blocate. Problema este că tranzacțiile pot fi anulate de multe ori, deoarece... o tranzacție mai veche poate deține resursa pentru o perioadă lungă de timp.
O soluție pesimistă la problema blocajului nu permite ca o tranzacție să înceapă executarea dacă există riscul unui blocaj.
Pentru a detecta un blocaj, se construiește un grafic (grafic de așteptare, grafic de așteptare), ale cărui vârfuri sunt tranzacții, iar marginile sunt direcționate de la tranzacțiile care așteaptă eliberarea datelor către tranzacția care a capturat aceste date. Se consideră că a avut loc un blocaj dacă graficul are o buclă. Construirea unui grafic de așteptare, în special în bazele de date distribuite, este o procedură costisitoare.
Blocare în două faze - previne blocajele prin sechestrarea tuturor resurselor utilizate de o tranzacție la începutul tranzacției și eliberarea acestora la sfârșit
Toate operațiunile de blocare trebuie să precedă prima deblocare. Are două faze - Faza de creștere, în timpul căreia mânerele se acumulează, și Faza de micșorare, în timpul căreia mânerele sunt eliberate. Dacă este imposibil să captați una dintre resurse, tranzacția începe de la capăt. Este posibil ca o tranzacție să nu poată achiziționa resursele necesare, de exemplu, dacă mai multe tranzacții concurează pentru aceleași resurse.
O comitere în două faze asigură că comiterea este executată pe toate replicile bazei de date
Fiecare bază de date introduce informații despre datele care vor fi modificate în jurnal și răspunde coordonatorului OK (faza de vot). După ce toată lumea a răspuns OK, coordonatorul trimite un semnal prin care îi obligă pe toți să se angajeze. După comitere, serverele răspund OK dacă cel puțin unul nu răspunde OK, atunci coordonatorul trimite un semnal pentru a anula modificările la toate serverele (Faza de finalizare).
Metoda marcajului de timp
O tranzacție mai veche este anulată atunci când se încearcă accesarea datelor implicate de o tranzacție mai tânără
Fiecărei tranzacții i se atribuie un marcaj de timp TS corespunzătoare orei de începere a execuţiei. Dacă Ti mai batran Tj, Apoi, TS(Ti) < TS(Tj).
Când o tranzacție este anulată, i se atribuie un nou marcaj temporal. Fiecare obiect de date Q implicat în tranzacție este marcat cu două etichete. W-TS(Q) — marcaj de timp al celei mai tinere tranzacții care a finalizat cu succes o înregistrare Q. R-TS(Q) — marcaj temporal al celei mai tinere tranzacții care a efectuat o înregistrare citită Q.
Când tranzacția T solicită citirea datelor Q Există două opțiuni.
Dacă TS(T) < W-TS(Q), adică datele au fost actualizate de o tranzacție mai tânără, apoi tranzacția T se rostogolește înapoi.
Dacă TS(T) >= W-TS(Q), apoi se efectuează citirea și R-TS(Q) devine MAX(R-TS(Q), TS(T)).
Când tranzacția T solicită modificări ale datelor Q Există două opțiuni.
Dacă TS(T) < R-TS(Q), adică datele au fost deja citite de o tranzacție mai tânără și dacă se face o modificare, va apărea un conflict. Tranzacţie T se rostogolește înapoi.
Dacă TS(T) < W-TS(Q), adică tranzacția încearcă să suprascrie o valoare mai nouă, tranzacția T este anulată. În alte cazuri, modificarea se realizează și W-TS(Q) devine egal TS(T).
Nu este necesară construcția costisitoare a graficului de așteptare. Tranzacțiile mai vechi depind de cele mai noi, așa că nu există cicluri în graficul de așteptare. Nu există blocaje, deoarece tranzacțiile nu sunt așteptate, ci sunt anulate imediat. Sunt posibile derulări în cascadă. Dacă Ti rostogolit departe și Tj Am citit datele pe care le-am schimbat Ti, Apoi, Tj ar trebui, de asemenea, să se rotească înapoi. Dacă în acelaşi timp Tj a fost deja comisă, atunci va exista o încălcare a principiului stabilității.
Una dintre soluțiile pentru derularea în cascadă. O tranzacție finalizează toate operațiunile de scriere la sfârșit, iar alte tranzacții trebuie să aștepte ca acea operațiune să fie finalizată. Tranzacțiile așteaptă să fie comise înainte de a fi citite.
Regula de scriere Thomas - o variație a metodei marcajului de timp în care datele actualizate de o tranzacție mai tânără sunt interzise să fie suprascrise de una mai veche
Tranzacţie T solicită modificări ale datelor Q. dacă TS(T) < W-TS(Q), adică tranzacția încearcă să suprascrie o valoare mai nouă, tranzacția T nu este anulată ca în metoda marcajului de timp.
Sursa: www.habr.com