Tranzacții

Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/

9 Martie 1998

Subiect:
Tranzacțiile atomice: proprietăți, implementări, utilizare
Cunoștințe necesare:
programare, concurență
Cuvinte cheie:
atomicitate, durabilitate, independență, consistență, log (înregistrare), lock (încuietoare), timestamp


Contents




Unelte

La o adică un calculator nu este altceva decît o unealtă. O unealtă care este folosită cu foarte mult succes în rezolvarea a fel de fel de probleme. Hai să luăm totuși calculatorul ca pe un scop în sine, și să aruncăm o scurtă privire asupra naturii muncii din domeniu, fie ea scriere de software sau proiectare de hardware (permiteți-mi să contrag totul la aceste două categorii). Aș vrea să observ că poate mai pregnant decît în alte domenii tehnice, munca din calculatoare constă tot din creația unor unelte.

Ce sunt sistemele de operare? Niște unelte care măresc productivitatea utilizării unui calculator. Ce sunt limbajele de programare? Unelte care înlesnesc exprimarea unor operații complexe. Ce sunt rețelele de calculatoare? Unelte care mijlocesc schimbul de informații. Procedurile sunt unelte care rezolvă subprobleme, etc. Și tot așa, la scară macro sau micro, peste tot numai unelte. Un bun specialist în proiectarea aplicațiilor sau sistemelor are la dispoziție o paletă amplă de unelte din care le alege pe cele mai potrivite scopurilor sale.

Unele probleme sunt de nerezolvat fără unelte potrivite; e ca și cum ai încerca să înțelegi teoria relativității cunoscînd numai aritmetica de clasa a doua. Uneltele nu numai că dau chei pentru soluționarea dificultăților, ci crează și un cadru ordonat în care să ne exprimăm gîndurile. Este de neconceput scrierea de software la ora actuală fără suportul conceptului de ``proces'': un program care se execută în izolare. Ori procesul nu este altceva decît o altă unealtă construită de către sistemul de operare; o abstracție, dar una extrem de utilă.

În acest articol voi prezenta tot o unealtă. Una mai puțin cunoscută, și care a fost aplicată în relativ puține contexte, deși este extrem de expresivă și utilă. Dar lucrurile se vor schimba cu siguranță în ceea ce o privește, pentru că domeniul ei de aplicații se lărgește permanent, de la bazele de date, în care a fost (și este) folosită inițial pînă la sistemele de operare sau aplicațiile distribuite. Este vorba de tranzacții, numite și ``tranzacții atomice''.

Ce sunt tranzacțiile

Dintru început trebuie spus că subiectul este extrem de generos. Există cărți întregi scrise despre tranzacții, există varietăți extrem de exotice de tranzacții, dar evident, în spațiul unui astfel de articol nu putem să ne aventurăm prea departe. Vom fi deci relativ ``tradiționali'', discutînd despre unul dintre cele mai simple modele de tranzacții, cam așa cum este el întîlnit în majoritatea cărților de baze de date.

Ce e o tranzacție? O tranzacție este o unealtă pusă la îndemînă unui programator prin care acesta poate exprima anumite proprietăți ale părților unor programe. Principala proprietate pe care tranzacțiile o pun la dispoziție este atomicitatea. Cuvîntul atom, spuneau manualele de fizică de liceu pe vremea mea, însemna în greaca veche ``indivizibil'', ``care nu poate fi spart în bucăți''. O tranzacție îi permite unui programator să grupeze mai multe operații elementare într-un tot indivizibil, să construiască deci noi operații, dar într-un fel care să nu ne permită să discernem structura lor interioară (adică faptul că sunt compuse din mai multe bucățele). Vom vedea imediat că acest lucru poate fi interpretat în mai multe feluri, depinzînd de contextul la care ne gîndim.

Proprietăți ale tranzacțiilor

Înainte de a vedea cum arată sau cum se implementează tranzacțiile o să le trecem în vedere proprietățile. În literatură sunt evidențiate patru proprietăți esențiale, ale căror inițiale sunt ACID.

Să reținem însă că anumite implementări ale tranzacțiilor nu oferă toate aceste proprietăți, probabil pentru că domeniul de utilizare al nu are neapărată nevoie de unele din proprietăți. Vom vedea de asemenea că proprietățile acestea nu sunt complet independente, și că anume mecanisme de implementare pot oferi simultan mai multe proprietăți; o oarecare independență există între proprietăți.

Atomicitate

O tranzacție grupează mai multe instrucțiuni laolaltă într-o ``macro-instrucțiune'' care se comportă ca o unitate indivizibilă. Putem vedea această proprietate în două feluri, care se numesc respectiv atomicitate și independență. Primul punct de vedere este discutat în această secțiune, iar al doilea ceva mai tîrziu.

Un grup de instrucțiuni dintr-o tranzacție se comportă ca o singură entitate atunci cînd se întîmplă o catastrofă. Chiar dacă am grupat 10 instrucțiuni și curentul cade după ce am executat numai primele 5, sistemul de tranzacții trebuie să ne asigure că după reluarea execuției efectul celor cinci instrucțiuni nu este vizibil. O întrerupere catastrofală trebuie să lase sistemul într-o stare corectă, care ar fi putut surveni în urma unei execuții normale. Cu alte cuvinte dacă am grupat niște instrucțiuni într-o tranzacție atunci se execută ori toate ori niciuna: ``totul sau nimic''.

Să luăm un exemplu ipotetic: un program de contabilitate care calculează plățile făcute angajaților. Programul trebuie ca pentru fiecare angajat să marcheze salariul de plătit și să scadă aceeași sumă din budgetul întreprinderii (îmi cer scuze dacă o dau în bară cu terminologia contabilă; ideea contează). Programul ar putea arăta așa:

platit := 0;
for i:=1 to angajati do begin 
        dePlata[i] := dePlata[i] + salariu[i];
        platit := platit + salariu[i]
end;
budget := budget - platit;

Dacă presupunem că valorile modificate sunt înregistrări pe disc, într-o bază de date, atunci dacă curentul cade undeva la mijlocul buclei anumite salarii vor fi fost plătite, dar suma nu a fost scăzută din budget. Programul nu poate fi reluat de la început, pentru că anumite salarii au fost plătite, dar altele nu.

Soluția este să executăm toate aceste instrucțiuni într-o singură tranzacție, care atunci cînd este întreruptă inainte de terminare va face ca modificările făcute să dispară. Cum, vom vedea mai tîrziu.

Independența

Independența se referă la un context în care mai multe programe acționează simultan asupra aceluiași set de date (activitate concurentă). Un program nu trebuie să vadă rezultatele parțiale ale altui program, pentru că acestea nu ar fi corecte.

Ca exemplu să considerăm un program care implementează o mărire de salariu (ura!), ceva de genul:

for i:=1 to angajati do
        salariu[i] := salariu[i] * 110/100; { marire 10 la suta :( }

Ce se poate întîmpla dacă acest program se execută ``simultan'' cu cel anterior? O posibilitate este ca acest program să pornească în execuție după cel precedent, să ajungă la același indice undeva și apoi să o ia înainte. În acest fel unora dintre angajați le vor fi plătite salarii indexate (celor din urmă), iar altora nu. Total necinstit, și nu numai necinstit, ci arbitrar, pentru că rezultatul depinde de momentul la care se execută programele și de viteza lor relativă.

Dacă fiecare din aceste fragmente de program ar fi fost o tranzacție așa ceva nu s-ar fi putut întîmpla: toate măririle ar fi fost executate ori înainte ori după toate plățile.

Consistența; programarea cu invarianți

Să aruncăm o privire la totalitatea variabilelor unui program. La un anumit moment de timp ele vor avea fiecare o valoare. Dar nu orice combinație de valori este posibilă. De exemplu, pentru un program care sortează un vector de numere, în vector se vor afla tot timpul aceleași numere, poate în altă ordine. Această regulă (mai precis acest predicat) se numește un invariant, pentru că trebuie să fie tot timpul adevărată, indiferent de faza de execuție a programului. Pentru primul program de mai sus un invariant este că (*) ``suma de plătit și budgetul curent trebuie să aibă aceeași sumă'' (balanța de plăți este zero).

Tehnica invarianților este extrem de importantă pentru ingineria programării. Un tip de date abstract nu este altceva decît o serie de proceduri care mențin niște invarianți foarte preciși despre anumite structuri de date.

Dacă atunci cînd scriem un program scriem procedurile în așa fel încît atunci cînd datele de intrare respectă un invariant să avem garanția că și datele de ieșire respectă același invariant, atunci putem obține demonstrații de corectitudine pentru programe. Prin inducție matematică. (Schiță de demonstrație: să presupunem că datele de intrare respectă un invariant. Dacă toate procedurile chemate păstrează acest invariant, atunci prin inducție după numărul de proceduri chemate demonstrăm imediat că invariantul este întotdeauna adevărat. Deci este adevărat și atunci cînd programul se termină.) De altfel tehnica invarianților este cheia demonstrațiilor de corectitudine din metoda post-condițiilor a lui Hoare. Dar asta este o cu totul altă mîncare de pește; am vrut doar să arăt că paradigma este extrem de puternică.

Ei bine, tranzacțiile sunt una din metodele pentru a programa ușor cu invarianți. Luînd din nou programul din primul exemplu, care plătea salariile, este evident că invariantul (*) nu este adevărat în interiorul buclei, unde variabilă dePlatit are o valoare nenulă, dar budgetul a rămas încă neschimbat. Invariantul (*) este adevărat înainte și după textul prezentat. De aceea dacă ``îmbrăcăm'' programul într-o tranzacție obținem invariantul adevărat întotdeauna, pentru că pentru universul exterior nu mai există de fapt o buclă for cu mii de instrucțiuni, ci o singură operație atomică.

Durabilitatea

Ultima proprietate a tranzacțiilor este legată de programarea cu structuri de date persistente (lucru adevărat și pentru atomicitate, descrisă mai sus). Un program Pascal simplu se execută de fiecare dată la fel, plecînd de la aceleași valori inițiale. Dar un program care operează cu un fișier, sau o bază de date, are structuri de date care se află pe disc și care supraviețuiesc ``morții'' programului. Operația de creștere a salariului va avea, dacă este executată de două ori, rezultate diferite, pentru că a doua creștere se aplică peste prima, pentru că rezultatele primeia au fost salvate pe disc. Noțiunea de persistență este prezentă explicit în puține limbaje de programare, dar este crucială în baze de date, unde în mod implicit orice operație se efectuează asupra unor date ``permanente''.

Durabilitatea tocmai la asta se referă: atunci cînd o tranzacție se termină rezultatele ei trebuie să fie permanente, chiar în cazul unor catastrofe (ex. căderea curentului). Atunci cînd cumpărați un bilet de avion, se execută o tranzacție care se termină cu tipărirea biletului. Cum ar fi dacă biletul ar fi tipărit, dar datele despre vînzare nu ar fi încă pe disc și curentul ar cădea? La reluarea execuției pentru baza de date biletul ar fi ca ne-vîndut, deci s-ar putea să vă treziți doi pe un loc. Așa ceva este intolerabil (iar într-un sistem cu mii de terminale și o rețea globală, cum au companiile de aviație, malfuncțiile hardware sunt statistic frecvente și normale), așa că tranzacțiile trebuie să ofere și durabilitate.

Pe scurt iată proprietățile tranzacțiilor:

Nume Proprietate
Atomicitate Catastrofele nu pot întrerupe o tranzacție ``la mijloc''
Consistență Tranzacțiile păstrează structurile de date corecte
Independență Programe executate în paralel nu interferă
Durabilitate Rezultatul unei tranzacții este permanent

Operațiile tranzacțiilor

Să vedem cum se manifestă tranzacțiile pentru un programator. Operațiile esențiale elementare (atomice) pe care programatorul le are la dispoziție atunci cînd operează asupra unei baze de date sunt citirile și scrierile unei valori din baza de date, precum și felurite operații aritmetice. Tranzacțiile se manifestă prin 3 noi instrucțiuni la dispoziția programatorului:

Operație Semnificație
Begin Indică începutul unei tranzacții
End Indică sfîrșitul tranzacției
Abort Sfîrșit nereușit de tranzacție; modificările dispar
Read Citește valoarea unei variabile persistente
Write Scrie valoarea unei variabile persistente

Vom folosi în mod explicit Write și Read pentru a indica operațiile asupra valorilor persistente; pe lîngă valori persistente (din baza de date) mai avem de-a face în exemple și cu valori locale fiecărui proces (ca variabilele locale unei funcții din limbajele de programare).

Unul din exemplele de mai sus va fi scris deci astfel într-un sistem care oferă tranzacții:

Begin Transaction
for i:=1 to angajati do begin
        x := Read(salariu[i]); { x e o variabila locala, nepersistenta }
        x := x * 110/100; { marire 10 la suta }
        Write(x, salariu[i]);
End Transaction

Tot ceea ce se află între Begin Transaction și End Transaction se va comporta ca o singură instrucțiune (lungă). Modificările tuturor salariilor vor deveni în mod normal (dacă nu se produce vreo eroare) vizibile instantaneu la execuția comenzii End Transaction. Sfîrșitul cu succes al unei tranzacții se numește Commit.

Instrucțiunea Abort este utilă atunci cînd ceva neplăcut s-a întîmplat și tranzacția nu se poate termina cu succes. Toate modificările făcute asupra datelor persistente, de la execuția lui Begin sunt pierdute pentru eternitate atunci cînd se execută Abort. Tranzacția se consideră terminată.

Iată un exemplu de utilizare a tranzacțiilor în cadrul sistemelor de operare în care instrucțiunea Abort este utilizată: codul ipotetic al operației move, care mută un fișier dintr-un director într-altul și eventual îi schimbă numele:

procedure move(numeVechi, numeNou)
begin
        Begin Transaction;
        directorNou := extrageDirector(numeNou);
        fisierNou := extrageNumeFisier(numeNou);
        este := cauta(directorNou, fisierNou);
        if (este) then Abort;  { fisierul nou exista deja }

        directorVechi := extrageDirector(numeVechi);
        fisierVechi := extrageNumeFisier(numeVechi);
        este := cauta(directorVechi, fisierVechi);
        if (not este) then Abort; { fisierul vechi nu exista }

        continutFisier := fisier(numeVechi);
        eroare := sterge(directorVechi, fisierVechi);
        if (eroare) then Abort;
        
        eroare := creaza(directorNou, fisierNou);
        if (eroare) then Abort;
        fisier(numeNou) := continutFisier;
        End Transaction;
end;

(Funcțiile cauta, sterge, etc. operează tot cu structuri persistente, deci sunt asemănătoare cu Read și Write de mai sus, numai că sunt puțin mai complicate; ele pot fi sintetizate din mai multe operații de acest fel.)

Ideea este că pe disc operațiile atomice sunt foarte simple: ștergerea unui nume dintr-un director, crearea unui nume într-un alt director, asocierea unui nume cu un conținut. Ca procedura move să aibă succes toate operațiile componente trebuie să se efectueze cu succes; dacă nu nici una nu trebuie să se efectueze: cum ar fi ca fișierul să fie șters din directorul vechi dar să nu apară în cel nou pentru că utilizatorul, de pildă, nu are drept de scriere în directorul cel nou?

Este însă foarte greu să ne asigurăm că toate condițiile sunt adevărate simultan, mai ales în prezența activității concurente. Dacă mai multe procese încearcă simultan să facă move la un același rezultat, atunci degeaba unul din ele verifică înainte de mutare dacă rezultatul există, pentru că rezultatul ar putea să apară în timp ce el șterge numele vechi.

Cu tranzacțiile problema se rezolvă automat: dacă toate condițiile au fost îndeplinite End face modificările dintr-odată; altfel nici o modificare nu este vizibilă, și Abort este executat. Este o diferență între End Transaction și Commit: instrucțiunea End anunță sfîrșitul tranzacției și încercarea de a face modificările permanente. Faptul că rezultatele operațiilor devin permanente se numește Commit. Un End însă poate să nu reușească să facă Commit, și atunci se va transforma în Abort.

Deci End nu înseamnă ``succes'', ci ``aș vrea să termin cu succes''. Dacă este posibil End rezultă în Commit (care înseamnă într-adevăr ``succes''), altfel End devine un Abort.

Sinucidere și crimă

Trebuie spus că există două feluri în care o tranzacție se poate termina cu eșec:

Vom vedea mai jos exemple de contexte în care sistemul ar avea nevoie să ``ucidă'' tranzacții. Ideea este că promisiunile făcute sunt mai importante decît execuția codului; codul poate fi eventual re-executat, dar promisiunile nu pot fi în nici un caz încălcate. În general atunci cînd o tranzacție este ucisă programul care a invocat-o (sau utilizatorul) este informat de acest lucru și poate decide dacă să încerce din nou execuția sau nu, în funcție de motive.

La ce sunt utile tranzacțiile?

Deja ne-am făcut o idee despre utilitatea tranzacțiilor. Să recapitulăm:

Serializabilitate

Chiar dacă intuitiv noțiunea de independență poate părea clară, trebuie să înțelegem foarte bine ce înseamnă. Această secțiune este consacrată numai acestui scop. Pentru că independența nu are sens în absența paralelismului, discutăm despre un sistem în care se pot executa simultan mai multe procese cu tranzacții.

Vom defini o proprietate mai tare decît cea de independență, numită serializabilitate (serializability). Serializabilitatea este o proprietate e executării tranzacțiilor care implică independență. Vom vedea deci că dacă sistemul run-time care implementează tranzacțiile garantează că orice execuție a unui set de tranzacții este serializabilă, atunci tranzacțiile sunt independente.

Schedule

Cum am văzut, fiecare tranzacție este în realitate compusă din mai multe instrucțiuni, pe care le putem considera atomice. Atunci cînd două tranzacții se execută ``simultan'', de fapt avem de-a face cu o execuție întrețesută a instrucțiunilor care le compun. O ordine de execuție a instrucțiunilor din mai multe tranzacții se numește schedule (nu am nici o traducere rezonabilă pentru acest termen; numele românesc cel mai apropiat ar fi ``planificare'').

Să vedem un exemplu foarte simplu; să notăm tranzacțiile cu T1, T2, etc. Iată două posibile tranzacții care citesc variabila persistentă salariu într-o variabilă locală, o modifică și apoi o pun la loc:

Begin T1;
1)  x := Read(salariu);
2)  x := x * 110/100;
3)  Write(salariu, x);
End T1;

Begin T2;
1)  y := Read(salariu);
2)  y := y + 200;
3)  Write(salariu, y);
End T2;

Aceste tranzacții conțin fiecare cîte 3 instrucțiuni; există foarte multe ``schedules'' posibile pentru executarea lor. Iată unul dintre ele:

Begin T1; tt 
1) x := Read(salariu); tt 
  ttBegin T2;
  tt1) y := Read(salariu);
2) x := x * 110/100; tt 
3) Write(salariu, x); tt 
  tt2) y := y + 200;
  tt3) Write(salariu, y);
End T1; tt 
  ttEnd T2;

Există două ``schedules'' speciale: cel în care toate operațiile lui T1 se execută înainte de începutul lui T2, și cel în care toate se execută după sfîrșitul lui T2. Aceste două ``schedules'' se numesc seriale, pentru că sunt formate din executarea ``în serie'' a unei tranzacții și apoi a celeilalte.

Toate celelalte ``schedules'' constau din amestecări ale instrucțiunilor lui T1 cu T2, ca în exemplul de mai sus. Un ``schedule'' se numește serializabil dacă produce exact aceleași rezultate finale ca unul dintre ``schedule''-le seriale. Citiți cu atenție definiția asta. Rezultat final înseamnă exact aceleași valori ale variabilelor persistente.

Ce putem spune despre ``schedule''-ul din exemplul de mai sus? Este sau nu serializabil? Nu este! Să vedem un exemplu de date pentru care asta e evident: dacă inițial salariu avea valoarea 100, atunci schedule-ul de mai sus va da valoarea finală 300 (verificați). Pe de altă parte execuția T1 urmat de T2 dă valoarea 310, iar T2 urmat de T1 dă valoarea 330.

Sistemul care implementează tranzacții trebuie să excludă posibilitatea executării instrucțiunilor unor tranzacții într-o ordine (schedule) care nu este serializabilă.

Graful dependențelor

Să încercăm să ne dăm seama pentru care motive ``schedule''-ul de mai sus nu este serializabil. Putem să ne gîndim la serializabilitate și în următorul fel: pentru anumite operații ordinea de executare nu contează. De exemplu dacă citim o valoare în două tranzacții nu contează în ce ordine citim, pentru că vom obține același rezultat. Pe de altă dacă scriem două valori într-o singură variabilă persistentă (cum se întîmplă mai sus, cu tranzacțiile T1 și T2), atunci ordinea scrierilor este extrem de importantă pentru rezultatul final, pentru că ultima scriere dă valoarea rezultatului.

Operațiile care se pot schimba între ele fără a afecta valoarea rezultatului se spune că comută. Toate citirile comută între ele, așa cum comută operații de orice fel asupra variabilelor locale și operații care se efectuează asupra unor variabile persistente diferite. Cu alte cuvinte dacă eu scriu în variabila a iar tu citești b nu contează prea tare în ce ordine facem asta, pentru că rezultatul va fi același.

Un criteriu de serializabilitate este următorul: dacă putem schimba într-un ``schedule'' între ele instrucțiuni care comută și obținem un ``schedule'' serial, atunci avem de-a face cu un ``schedule'' serializabil. Altfel nu.

Hai să vedem care instrucțiuni din T1 și T2 nu comută în schedule-ul dat ca exemplu. ``T1 3)'' nu comută cu ``T2 1)'', pentru că ``T1 3)'' scrie în salariu iar ``T2 1)'' citește din salariu. De asemenea, ``T1 3)'' nu comută cu ``T2 3)'', pentru că amîndouă scriu în aceeași valoare. Păi atunci e clar de ce acest schedule nu e serializabil: instrucțiunea ``T1 3)'' nu poate fi nici ``împinsă'' înainte de T2 nici după, din cauza acestor dependențe.

Formal putem exprima acest lucru printr-un graf de dependențe care caracterizează un schedule. În graful (orientat) al dependențelor nodurile sunt tranzacții. Între două tranzacții avem un arc dacă prima execută o operație care nu comută cu o operație executată ulterior de a doua. Testul de serializabilitate atunci devine foarte simplu:

Un ``schedule'' este serializabil dacă în graful dependențelor asociat lui nu există cicluri.

Verificarea prezenței ciclurilor într-un graf se poate face în timp linear în numărul de noduri. Mai mult, o sortare topologică a grafului ne indică ordinea serială echivalentă cu cea dată.

Graful dependențelor pentru ``schedule''-ul de mai sus este următorul:

        T2 scrie salariu dupa ce T1 scrie
     /---->---\
     |        |
     |        V
     T1       T2
     ^        |
     |        |
     \---<----/
        T1 scrie salariu dupa ce T2 citeste

Avem deci un algoritm posibil pentru a implementa tranzacții izolate: le lăsăm să se execute pînă cînd una vrea să se termine; atunci verificăm dacă graful asociat execuției are cicluri, și dacă are atunci executăm Abort pentru (cel puțin) una din tranzacții.

În secțiunea următoare intrăm în zona implementării tranzacțiilor. Vom vedea cum se implementează partea care oferă proprietatea de ``Independență''. Cum se implementează celelalte proprietăți (durabilitate, etc.) mai tîrziu.

Controlul accesului concurent

Există două tipuri mari de implementări de sisteme tranzacționale din punct de vedere al serializabilității:

Secțiunile următoare dau exemple din fiecare tip.

Încuietori

Încuietorile (locks) sunt o metodă pentru controlul pesimist al accesului. Ideea este că atunci cînd faci operații asupra unei valori interzici accesele altor tranzacții la acea valoare; știm că accesele la valori diferite sunt serializabile.

Tipuri de încuietori

Pentru a nu limita excesiv activitatea concurentă în sistem de obicei se folosesc mai multe tipuri de încuietori. Există variante extrem de sofisticate, dar noi vom discuta doar una, în care există încuietori separate pentru citire și scriere. O încuietoare pentru scriere este mai ``exclusivă'' decît una pentru citire, pentru că putem executa mai multe citiri simultan, dar o scriere nu poate fi simultană cu o altă operație din altă tranzacție.

Manipularea încuietorilor se poate face fie explicit de către programator (cînd e nevoie de control fin) fie în ascuns de către sistemul tranzacțional. În orice caz, încuietorile sunt asociate valorilor persistente și se manipulează cu următoarele operații (primele două sunt fundamentale, iar următoarele auxiliare):

Operație Semnificație
lock(date, operație) ``încuie'' aceste date pentru ``operație''
unlock(date) eliberează restricțiile asupra acestor date
upgrade(date) întărește o încuietoare
degrade(date) slăbește o încuietoare

Cum funcționează încuietorile? De obicei există o entitate (proces) specială numit ``lock manager'' care ține minte care din date sunt încuiate, de cine și în ce fel. Atunci cînd o tranzacție vrea să încuie o valoare se petrec următoarele lucruri:

Există două acțiuni posibile cînd încuierea este refuzată; alegerea uneia dintre ele poate fi o politică a celui care a implementat baza de date, sau poate fi la alegerea utilizatorului:

Terminarea unei tranzacții (cu Commit sau Abort) eliberează întotdeauna toate încuietorile.

O tranzacție este obligată să încuie datele înainte de a le accesa. Un exemplu ar fi:

Begin T2;
    lock(salariu, readLock);  { incuie pentru citire }
    y := Read(salariu);
    y := y + 200;
    upgrade(salariu);         { transforma incuietoarea pentru scriere }
    Write(salariu, y);
    unlock(salariu);
End T2;

Protocolul în două faze

E interesant că doar punînd încuietori în jurul acceselor la date nu e suficient. Ca să ne convingem, considerați tranzacțiile T1 și T2 în forma în care exact fiecare acces este protejat, ca în exemplul următor pentru T2:

Begin T2;
    lock(salariu, readLock);
    y := Read(salariu);
    unlock(salariu);
    y := y + 200;
    lock(salariu, writeLock);
    Write(salariu, y);
    unlock(salariu);
End T2;

E ușor de observat că o astfel de încuiere permite execuții neserializabile (chiar execuția indicată mai sus este posibilă). Nu ajunge deci să încuiem, trebuie să respectăm un protocol de încuiere. Adică un set de reguli pentru toată lumea.

Cel mai simplu și mai des folosit protocol este cel în două faze (two-phase locking; 2PL). Acest protocol se poate enunța astfel:

În prima fază se pot numai obține încuietori (adică se execută instrucțiuni lock și upgrade).

În a doua fază se pot numai dealoca încuietori (unlock sau degrade).

Dacă facem un grafic al numărului de încuietori posedate de o tranzacție, el trebuie să arate cam ca în figura următoare: să aibă o fază de creștere (growing phase) și una de descreștere (shrinking phase).

                  growing  shrinking
                ^       ____
                |      /    \
numar de        |     /      \____
incuietori      |  __/            |
                | /                \
                0----------------------->
                                timp

Acest protocol garantează serializabilitatea. Este un exercițiu interesant să demonstrăm acest lucru. Iată o schiță a demonstrației.

Să presupunem (prin absurd) că o serie de tranzacții T1, T2, ... Tn, care respectă protocolul 2PL, au avut o execuție ne-serializabilă. Asta înseamnă că în graful lor de dependențe există un ciclu, T1 $\rightarrow$ T2 $\rightarrow$ ...Tn $\rightarrow$ T1. Ce înseamnă că avem un arc de la T1 la T2? Înseamnă că T1 a operat asupra unei valori înainte de T2, cu o operație care nu comută cu cea a lui T2. Dar noi știm că T1 nu are voie să opereze asupra unei valori ne-încuiate. Asta înseamnă că T2 a încuiat acea valoare după ce T1 a descuiat-o. Arcul T2 $\rightarrow$ T3 indică un lucru asemănător, și anume că T3 a încuiat o valoare (nu necesar aceeași) după ce T2 a descuiat-o. Din aproape în aproape obținem că, în fine, T1 a încuiat o valoare după ce T1 a descuiat o altă valoare, ceea ce este absurd. Concluzia inițială era deci greșită. În concluzie 2PL garantează serializabilitate.

Să observăm ca 2PL nu este același lucru cu serializabilitatea, ci că 2PL doar o implică.

2PL strict

Există un dezavantaj al lui 2PL și o implementare care îl evită. Să considerăm următorul scenariu: o tranzacție T1 încuie o valoare $x$, o modifică și apoi o descuie. T2 vine la rînd, încuie și citește $x$. Dacă acum T1 vrea să execute Abort, valoarea lui $x$ trebuie pusă cum era înainte ca T1 să o fi modificat. Dar T2 a citit-o deja! Asta înseamnă nimic altceva decît că dacă T1 execută Abort, T2 trebuie să fie ``ucisă'' de sistem, pentru a respecta proprietatea de izolare! E clar că lanțul poate fi mai lung: T3 poate a citit la rîndul ei $x$, și atunci trebuie ucisă și ea.

O astfel de situație foarte neplăcută (pentru că o mulțime de operații trebuie ``șterse'') se numește cascaded abort (abort în cascadă). (O altă consecință neplăcută este că T2 nu se poate termina înainte de T1, pentru că dacă T2 face Commit iar T1 Abort am încurcat-o, căci T2 a promis că valoarea lui $x$ este permanentă, dar nu avea voie s-o citească! Deci T2 trebuie să aștepte ca T1 să se termine.)

Soluția este simplă: restrîngi concurența, dar nu lași pe nimeni să vadă ce-ai modificat. Nu descui nimic pînă la sfîrșit, cînd descui totul dintr-o mișcare (de exemplu folosind End Transaction, care eliberează încuietorile). Graficul ar arăta atunci cam așa:

                  growing       shrinking
                ^       _________
                |      /         |
numar de        |     /          |
incuietori      |  __/           |
                | /              |terminare
                0----------------------->
                                timp

Blocarea (deadlock)

Încuietorile sunt foarte bune și frumoase pentru a obține serializabilitate, dar au un foarte, foarte mare dezavantaj.... Pot duce la situații de blocare totală, din care nu există ieșire. Aceasta se cheamă deadlock. Iată un exemplu foarte simplu de ``schedule'' în care două tranzacții încuie niște valori, după care nici una nu mai poate progresa nicicum, pentru că vrea valoarea încuiată de cealaltă:

T1 T2
lock(x, writeLock)  
  lock(y, writeLock)
lock(y, writeLock)  
refuz: blocat lock(x, writeLock)
  refuz: blocat

Problema deadlock-ului este foarte interesantă și complicată; prea complicată pentru articolul ăsta. Să menționăm că există tehnici standard pentru a o trata:

Algoritmii pentru detectarea deadlock-ului sunt extrem de sofisticați în sisteme distribuite, și de aceea de obicei evitarea este tehnica folosită.

O metodă nu prea precisă constă în a omorîorice tranzacție care a așteptat mai mult de un anumit timp eliberarea unei încuietori; e clar atunci că nu se pot petrece deadlock-uri, dar s-ar putea ca nevinovați să piară, doar pentru că stăteau la o coadă prea lungă.

Granularitatea încuietorilor

O problemă foarte importantă, pe care am eludat-o (și o vom eluda și mai departe) este granularitatea unei încuietori: cît de mare este o ``valoare'' pe care o încui? Încuietori mai mari restrîng paralelismul posibil, dar reduc costul: o tranzacție ca cea din primul exemplu, care procesează toate salariile ar prefera să pună o singură încuietoare mare decît un milion mici. Astfel putem încuia:

Încuietori de mărimi diferite ridică și alte probleme: de exemplu trebuie să fim grijulii să nu avem o tranzacție care încuie o valoare pentru scriere și o alta care încuie tot fișierul care conține valoarea, pentru că atunci avem un conflict.

Timestamps

O altă metodă de control al activității concurente este de a impune tranzacțiilor de la început o anumită ordine de acces la date. De pildă tranzacțiile sunt etichetate cu ora la care au fost lansate, și o tranzacție mai ``bătrînă'' nu este lăsată cu nici un chip să facă o operație asupra unei valori atinse de o tranzacție mai ``tînără''. Cu alte cuvinte se alege de la început unul dintre ``schedule''-urile seriale cu care va fi echivalent cel al execuției curente.

Metoda folosește cîte două ``etichete temporale'' (timestamps) pentru fiecare valoare persistentă. O etichetă (RT: read time) indică ultima tranzacție care a citit valoarea, iar o alta (WT: write time) indică ultima tranzacție care a scris valoarea. Notînd eticheta unei tranzacții T1 cu T(T1), protocoalele de acces la date ale unei tranzacții vor fi:

procedure read(date, tranzactie)
begin
   if T(tranzactie) >= RT(date) then begin
        RT(date) := T(tranzactie);
        return date;
   else
        Abort;
end;


procedure write(date, valoare, tranzactie)
begin
   if (T(tranzactie) >= max(RT(date), WT(date))) then begin
        date := valoare;
        WT(date) := T(tranzactie)
   end 
   else if RT(date) > T(tranzactie) then Abort
   else if RT(date) <= T(tranzactie) and
           T(tranzactie) < WT(date) then
   ;     { nu face absolut nimic; ignora scrierea } 
end;

Aceste proceduri vor lăsa o tranzacție mai veche să facă operații asupra unei valori numai dacă tranzacții mai noi nu au făcut operații care nu comută. Cazul scrierii este interesant: dacă o tranzacție veche scrie peste o valoare pe care a scris între timp o tranzacție mai nouă (dar între cele două timpuri nimeni nu a citit valoarea), atunci valoarea scrisă de tranzacția veche este pur și simplu ignorată. Asta pentru că dacă tranzacția veche ar fi scris înainte valoarea, nimeni nu ar fi apucat să o citească pînă cînd cea nouă ar fi supra-scris-o.

``Timestamps'' și ``locks''

Putem combina laolaltă încuietorile cu ``timestamps'' pentru a evita deadlock-ul. Există două mari soluții care folosesc ``timestamps'' pentru a arbitra accesul la un lock:

wait-die:

wound-wait:

Amîndouă schemele dau prioritate tranzacțiilor care au trăit mai mult, în ideea că au făcut mai multă treabă și e păcat să le omorîm. Wait-die poate produce livelock, sau ``starvation'' (cînd tranzacții tinere sunt mereu repornite și nu apucă niciodată un lock). Nu se pot produce deadlock-uri, pentru că în orice ciclu tranzacția cea mai tînără trebuie să moară.

O metodă optimistă: algoritmul validării

O metodă care nu restrînge deloc accesul concurent este următoarea: cine are de făcut modificări strînge toate valorile de modificat în variabile locale, iar cînd a terminat verifică dacă poate să salveze modificările. Asta se poate dacă nimeni nu s-a atins între timp de valorile inițiale. Dacă această fază (de validare) se termină cu succes toate valorile sunt salvate (printr-o operație atomică) în baza de date. Altfel tranzacția face Abort.

Ca să verifice dacă nimeni nu s-a atins de valori între timp, fiecare valoare este etichetată cu un număr de versiune, care este incrementat la fiecare scriere. Dacă observi atunci cînd vrei să-ți salvezi rezultatele că versiunea s-a schimbat față de atunci cînd ai citit datele, renunți să le mai scrii.

Un astfel de protocol este folosit de sistemul de fișiere NFS (network file system): fiecare fișier pe server are o versiune. Cînd cineva șterge un fișier și crează altul folosind aceleași porțiuni de pe disc (mai precis același inod -- pentru detalii citiți articolele mele mai vechi despre sistemul de fișiere din Unix, disponibile și din pagina mea de web), versiunea se incrementează. Dacă un alt client vrea să facă operații pe un fișier care nu mai există, server-ul se prinde, pentru că clientul oferă versiunea veche a inod-ului. Astfel accese ilegale sunt interzise.

Izolare: recapitulare

Am văzut multe tehnici alternative pentru a implementa proprietatea de izolare a tranzacțiilor. Un anume sistem va implementa probabil una singură dintre ele.

Protocol Calități
2PL deadlock și cascaded-abort posibile
2PL strict deadlock posibil; concurență redusă față de 2PL
Timestamp restrînge ``schedule''-le posibile; necesită spațiu suplimentar pentru etichete; concurență mare
Validare poate cauza abort-uri tardive; cere spațiu suplimentar
Timestamp + lock pot cauza ``starvation''; nu au deadlock

Implementarea lui Abort și Commit

Dom'le, am tot vorbit de cum se implementează sincronizarea, și am folosit mereu operațiile Abort și Commit, dar nu avem încă nici cea mai mică idee despre cum se pot implementa. Le-a venit timpul.

Există două metode mari pentru a modifica valorile persistente (baza de date):

  1. Toate modificările se fac pe copii ale valorilor din baza de date (acestea se numesc ``date umbră'' (shadow-data)). Tranzacția citește toate valorile interesante din baza de date (poate folosi fie încuietori, fie validare), după care modifică toate valorile local. Cînd a terminat cu succes, (Commit) trimite toate valorile la server-ul care ține baza de date, unde ele trebuie efectuate în mod atomic, toate deodată (redo). Dacă tranzacția decide să facă Abort nu trimite nici o valoare, ci doar eliberează încuietorile.

  2. Tranzacția poate alege să modifice valorile direct în baza de date. În cazul ăsta Commit e foarte simplă: eliberezi încuietorile. Abort însă are nevoie de un mecanism special, prin care variabilele trebuie readuse la valorile inițiale (undo).

În fiecare caz una dintre operațiile de terminare este mai grea decît cealaltă. Amuzant este că ambele probleme pot fi rezolvate folosind aceeași unealtă, în moduri ușor diferite. Această unealtă este setul de înregistrări, mai precis numit log, sau audit.

Log-ul

Un ``log'' este o secvență lineară, teoretic nesfîrșită, de înregistrări care descriu operații. Există două feluri de ``log'':

  1. ``log''-ul de intenții, sau ``redo-log'': atunci cînd modificările se fac pe o copie personală a datelor, toate noile valori ale datelor sunt marcate în log. Pentru Commit, log-ul tranzacției este trimis la baza de date care re-execută (de aici numele de ``redo'') toate operațiile descrise în log, de data asta direct în baza de date, într-o manieră atomică.

  2. ``log''-ul ``undo'' ține minte în schimb toate valorile inițiale ale datelor, înainte de modificare. Dacă faci modificări marchezi în log cum erau valorile, iar dacă-ți vine pofta să faci Abort atunci o iei de-a-ndoaselea în log și refaci valorile cum erau inițial. Această tehnică de parcurgere inversă cu des-facerea modificărilor se numește Rollback.

Vom vedea că, în mod surprinzător, log-ul se poate folosi nu numai pentru a implementa operațiile de Abort și Commit, ci și pentru a obține proprietățile de atomicitate și durabilitate în fața catastrofelor!

Desigur că putem avea un log combinat, care ține ambele feluri de valori, și care permite atît ``undo'' cît și ``redo''. Iată un exemplu posibil de înregistrare dintr-un astfel de log:

Tranzacție T232
Ora 12:01:22 EST
Valoare modificată salariu
Valoare inițială 100
Valoare finală 200

În log trebuie marcate nu numai operațiile asupra valorilor persistente, ci și fiecare acțiune de început și terminare de tranzacție.

Puncte de control (checkpoints)

Problema principală cu log-ul este că acesta crește permanent cu noi înregistrări. Niciodată nu se eliberează spațiu. E clar, asta nu poate merge la infinit. O metodă care recuperează spațiul inutil din log (de exemplu înregistrările tranzacțiilor care au făcut Commit) se bazează pe ceea ce se numește ``puncte de control'' (checkpoints). Aceasta este o formă specială de ``garbage collecting''.

Să facem următoarea observație: dacă știm starea inițială a unui sistem și toate modificările făcute asupra lui (în ordine) atunci putem deduce starea curentă. Exact asta este și un log: lista tuturor modificărilor făcute asupra unui sistem. Dar de la un anumit rang încolo, descrierea modificărilor poate fi mai mare decît descrierea stării întregului sistem. Putem atunci ``compacta'' lista modificărilor ținînd minte starea curentă a sistemului și uitînd toate modificările făcute pînă atunci. Această ``stare înghețată'' a sistemului se numește ``checkpoint''.

Problema este mai grea decît pare: de fapt sistemul nu este niciodată într-o stare stabilă; tot timpul sunt în execuție tranzacții despre care nu știm încă dacă se vor termina cu succes sau nu, deci nu putem vorbi de ``o stare''. Soluția (cu variante din ce în ce mai sofisticate și performante) este grosso-modo următoarea: se oprește toată activitatea din sistem, după care log-ul este parcurs în ordine inversă. Toate informațiile despre tranzacții care au fost terminate pot fi șterse din ``log'', pentru că efectele acestora sunt deja în baza de date (proprietatea de durabilitate garantează acest lucru). În log se mai păstrează doar informații despre tranzacțiile curente neterminate. De obicei toate aceste lucruri se fac tot folosind log-ul: se scrie o înregistrare specială ``checkpoint'', după care log-ul este scanat și sunt copiate toate înregistrările încă ``vii''. Tot spațiul află înainte de checkpoint poate fi apoi reutilizat.

Tehnica aceasta este folosită și în sisteme de operare, unde proceselor care rulează pentru foarte mult timp li se fac periodic astfel de puncte de control, pentru ca în cazul unei catastrofe să se reia calculele numai de la ultimul punct.

Catastrofe (crash)

Am văzut pînă acum cum se pot obține proprietățile de izolare (prin controlul accesului concurent) și consistență (printr-un stil de programare care menține invarianții adevărați înafara tranzacțiilor).

În această secțiune vom introduce ultimul element suplimentar care complică viața celor ce implementează tranzacții: catastrofele și vom vedea cum tranzacțiile reușesc să ofere proprietățile de atomicitate și durabilitate în fața unor condiții atît de adverse.

Scula esențială este din nou ``log''-ul (undo-redo).

Vrem să asigurăm deci două proprietăți:

Durabilitate:
o tranzacție care a făcut Commit trebuie să aibă efectele permanente orice s-ar întîmpla.
Atomicitate:
după un ``crash'' baza de date va executa un protocol special de refacere (recovery protocol) care-i va permite să reia operațiunile într-un mod corect (adică tranzacțiile neterminate la ora crash-ului vor fi Abort-ate). Mai mult, un crash în timpul acțiunii de refacere trebuie să nu cauzeze daune de nici un fel!

Prima regulă pe care trebuie s-o respectăm este următoarea:

Raportăm succesul unei tranzacții numai după ce toate valorile modificate de ea au ajuns pe un mediu stabil (stable medium), care supraviețuiește catastrofelor.

(În funcție de importanța sistemului, mediul stabil se poate defini ca memorie RAM, memorie NVRAM, disc, disc cu redundanță, disc dublu (mirrored disk), bandă magnetică, bunker anti-atomic, etc. Depinde de ce fel de catastrofe vrem să ne ferim.)

Această regulă este adevărată pentru că nu există nici un undo pentru ceea ce i-am spus utilizatorului. Dacă am tipărit un bilet de avion atunci nu mai putem să-l luăm înapoi (cel puțin pînă învățăm să dezvoltăm roboți suficient de puternici...).

Astfel garantăm durabilitatea.

``Write-ahead log''

Pentru a garanta atomicitatea trebuie să avem o metodă de a identifica toate tranzacțiile care erau neterminate la momentul crash-ului și de a face Abort cu ele. Pentru că un crash distruge absolut toate valorile variabilelor ne-persistente, toată informația necesară pentru identificare și Abort trebuie să fie pe un mediu stabil. Regula de aur este:

O operație poate fi efectuată în baza da date numai dacă înregistrarea din log care o descrie a ajuns pe un mediu stabil.

E ușor de înțeles de ce: dacă facem o modificare în baza de date și aparatul crapă înainte să apucăm să scriem în log, nu avem nici o metodă după repornire să ne dăm seama că am scris într-adevăr ceva în baza de date sau nu.

Protocolul de refacere (recovery)

Dacă respectăm regula de aur atunci avem destulă informație ca să refacem baza de date după o catastrofă. Algoritmul are trei pași mari:

  1. Scanăm log-ul și identificăm toate tranzacțiile care corespund clientului care a răposat (dacă a decedat chiar serverul considerăm toate tranzacțiile).

  2. Pentru toate tranzacțiile care au o înregistrare Commit în log re-executăm acțiunile din log în ordinea în care au fost făcute.

  3. Pentru toate tranzacțiile neterminate din log executăm acțiunile în ordine inversă, ștergînd modificările lor.

Ca treaba să meargă cum trebuie, este necesar ca înregistrările din log să satisfacă o proprietate suplimentară: acțiunile lor trebuie să fie idempotente. Asta înseamnă că executarea unei acțiuni din log de mai multe ori trebuie să dea exact același rezultat ca executarea o singură dată. În acest fel nu ne doare dacă cumva re-executăm acțiuni care au mai fost făcute. De asemenea, nu avem probleme dacă pică din nou curentul în timpul acțiunii de refacere: o a doua refacere va da aceleași rezultate.

O înregistrare de log de genul ``A este incrementat cu 2'' nu este idempotentă, pentru că fiecare nouă execuție schimbă valoarea lui A. Exemplul de mai sus însă este.

Să observăm că ``regula de aur'' ne oferă și cheia creșterii performanței în implementarea tranzacțiilor: nu trebuie să scriem în log de fiecare dată cînd facem ceva: trebuie să scriem în log numai înainte de a modifica baza de date. Putem astfel strînge serii întregi de modificări în log, pe care le scriem dintr-un singur foc. Se știe că pentru accesul la disc mai mult costă să începi decît să faci treaba, deci costul este practic același pentru una sau mai multe înregistrări. Singurul moment cînd trebuie neapărat să salvăm pe disc este exact înainte de terminarea tranzacției; toate celelalte modificări pot fi amînate.

Încheiere

Ar mai fi foarte multe lucruri de spus despre tranzacții; foarte interesant este protocolul pentru tranzacții în medii distribuite, numit ``Two-phase commit protocol'', 2PC. Tranzacțiile ierarhice (nested) sunt o altă paradigmă aplicată cu succes. Sisteme de fișiere bazate pe log-uri sunt folosite cu succes în sisteme Unix pentru refaceri extrem de rapide după căderi.

Tranzacțiile sunt o sculă foarte utilă pentru programator, care cu prețul unei oarecare scăderi în performanță oferă o serie de proprietăți foarte utile ale datelor. Este de așteptat să devină o paradigmă din ce în ce mai întîlnită în arsenalul sculelor programatorilor.