Algoritmii de control al concurentei prin blocare previn executia unei secvente incorecte de operatii prin punerea in asteptare a tranzactiilor care vor sa execute operatii conflictuale
=> sincronizare asupra datelor partajate
Prevenire & Asteptare
Tipuri de blocari (general):
Tipuri de blocari (general):
Partajat
Exclusiv
Matricea compatibilitatilor:
In utilizarea blocarilor partajate si exclusive, trebuie respectate urmatoarele reguli:
In utilizarea blocarilor partajate si exclusive, trebuie respectate urmatoarele reguli:
Orice unitate de acces care este blocata de o tranzactie, trebuie ulterior deblocata de catre aceeasi tranzactie inainte de terminarea acesteia;
O tranzactie T’ nu incearca sa deblocheze o unitate de acces blocata de o tranzactie T;
O tranzactie nu incearca sa blocheze (si) pentru citire o unitate de acces pentru care are asociata deja o blocare partajata sau exclusiva (vezi observatia de mai jos);
O tranzactie nu incearca sa blocheze (iarasi) pentru citire-scriere o unitate de acces pentru care are asociata deja o blocare exclusiva.
Operatii de blocare / deblocare:
Operatii de blocare / deblocare:
RL(x)
WL(x)
RU(x)
WU(x)
Doua blocari pLi(x) si qLj(x), i<>j, sunt conflictuale daca cel putin una dintre ele este de tip exclusiv (altfel spus – daca operatiile p si q sunt conflictuale).
TM trimite o cerere de blocare pi(x) planificatorului:
TM trimite o cerere de blocare pi(x) planificatorului:
Daca pLi(x) este in conflict cu vreo blocare qLj(x) (acordata sau deja solicitata si in asteptare) atunci operatia pi(x) este amanata => forteaza Ti sa astepte pana cand poate impune blocarea dorita pe x (pLi(x)).
Altfel seteaza pLi(x) si trimite operatia pi(x) catre DM.
=> operatiile conflictuale sunt executate in ordinea in care sunt obtinute blocarile corespunzatoare conflictuale =>
ordonarea operatiilor
o unitate de acces este deblocata cel mai devreme dupa primirea confirmarii efectuarii operatiei (de catre DM)
Blocari / durata blocarilor / nivel de izolare:
Blocari / durata blocarilor / nivel de izolare:
Op – pe durata efectuarii operatiei
Tr – de la inceputul efectuarii operatiei pana la terminarea tranzactiei
2PL = protocol de blocare care asigura serializabilitatea istoriei unui un set de tranzactii.
2PL: Odata ce planificatorul a eliberat o blocare pentru o tranzactie Ti, nu poate sa obtina o alta blocare pentru Ti, indiferent de unitatea de acces.
Exemplu 2PL, {T1, T2} / no deadlock / SR
Exemplu 2PL, {T1, T2} / no deadlock / SR
2PL si serializabilitatea
O istorie produsa de un planificator 2PL este serializabila.
2PL conservativ => SR + no deadlock
Fiecare tranzactie obtine toate blocarile inainte de a trimite prima operatie catre DM.
Lock Manager (LM) – gestioneaza un tabel al blocarilor, cu inregistrari de forma (tr_id, data_item, lock_mode).
Lock Manager (LM) – gestioneaza un tabel al blocarilor, cu inregistrari de forma (tr_id, data_item, lock_mode).
LM incearca sa blocheze un data_item prin adaugarea intrarii corespunzatoare in tabel.
Daca exista deja o blocare care intra in conflict cu blocarea solicitata, cererea de blocare este adaugata intr-o coada de asteptare pentru acel data_item.
Deblocarea consta in stergerea intrarii corespunzatoare din tabelul de blocari.
Prevenire
Prevenire
Metoda cererilor anticipate (2PL conservativ)
Metoda ordonarii
Evitare
Wait-die
Wound-wait
Detectie si iesire
Timeout
Waits-for graph
Extern
=> anularea unor tranzatii victima
Exemplu WFG, {T1, T2, T3, T4}
Exemplu WFG, {T1, T2, T3, T4}
Marca de timp (timestamp) – este o valoare care asigura unicitatea si ordonarea cronologica a unui set de resurse.
Marca de timp poate sa fie o valoare care se incrementeaza automat la asocierea unei marci de timp unei noi tranzactii (gen autonumber) sau poate fi generata din timpul curent al sistemului.
Fie Ti – tranzactie, ts(Ti) – marca de timp a lui Ti
Exemplu:
Exemplu:
Algoritmul de ordonare partiala
Fiecare unitate de acces x are doua marci de timp: de citire si de scriere
Ordoneaza operatiile conflictuale folosind marcile de timp
Regula dupa care functioneaza:
Daca pi(x) si qj(x) sunt doua operatii conflictuale, atunci se executa pi(x) inainte de qj(x) ddaca ts(Ti)
Ex:
create table dbo.concerte
(idc int, titlu varchar(50), rv rowversion)
insert into dbo.concerte (idc, titlu)
values (1, 'Spargatorul de nuci')
=>
1 Spargatorul de nuci 0x00000000000007D5
Protocol validation-based
Protocol validation-based
Ideea de la care se pleaca este faptul ca (daca…) sunt mici sansele ca o tranzactie sa intre in conflict cu alte tranzactii concurente => acest algoritm de control al concurentei este cat de permisiv cu putinta (optimist).
se folosesc blocari (strict necesare) indeosebi la scriere, pentru a asigura consistenta fizica a datelor.
Observatie: Nu se folosesc blocari pentru asigurarea controlului concurentei => nu se produc interblocari.
OCC prevede ca executia unei tranzactii sa se desfasoare in trei faze:
OCC prevede ca executia unei tranzactii sa se desfasoare in trei faze:
Citire (Read) – operatiile tranzactiei se executa citind date din baza de date si scriind modificari intr-un spatiu privat (propriu tranzactiei).
Validare (Validation) – in momentul in care tranzactia urmeaza sa trimita spre executie operatia de comitere, sistemul verifica daca tranzactia ar putea sa fie in conflict cu vreo alta tranzactie concurenta (mai veche decat tranzactia curenta). Daca se detecteaza un posibil conflict, tranzactia este anulata, spatiul privat este eliberat, iar tranzactia este reluata.
Scriere (Write) – daca in faza de validare nu se determina conflicte, modificarile efectuate in spatiul privat sunt copiate in baza de date.
Fiecare tranzactie Ti primeste o marca de timp ts(Ti) la inceput (pentru mai mult optimism, la sfarsitul fazei de citire)
Fiecare tranzactie Ti primeste o marca de timp ts(Ti) la inceput (pentru mai mult optimism, la sfarsitul fazei de citire)
Criteriul de validare verifica daca ordinea marcilor de timp a tranzactiilor are ca echivalent o ordine seriala a tranzactiilor
Nu se valideaza doua tranzactii in acelasi timp
Conditii de validare:
(1) asigura executie seriala
(2) asigura ca Tj nu citeste ceva modificat de Ti, dar care inca nu a fost scris in bd; nu se permit conflicte WiRj sau RjWi; WjRi si WjWi nu se permit din configuratie; se permit RiWj si WiWj, dar sunt ordonate conform marcilor de timp a tranzactiilor
(3) nu se permit conflicte WiRj, RjWi, WiWj, WjWi; WjRi nu se permite din configuratie; se permite RiWj, dar aceste operatii conflictuale sunt ordonate conform marcilor de timp a tranzactiilor.
Posibile situari a doua tranzactii, {T1, T2}, validare
Posibile situari a doua tranzactii, {T1, T2}, validare
Observatii:
Observatii:
(1) Prima conditie permite ca Tj sa vada modificari efectuate de Ti, in timp ce aceste operatii se executa in ordine seriala (sunt citite doar date comise) => tranzactiile se executa in ordine seriala
(2) A doua conditie permite ca Tj sa citeasca unitati de acces in timp ce Ti inca modifica obiecte, dar fara sa apara conflicte – deoarece Tj nu are voie sa citeasca unitati de acces modificate de Ti. Desi Tj ar putea supra-scrie unele unitati de acces scrise de Ti, toate scrierile lui Ti preced toate scrierile lui Tj (Tj sa nu citeasca ce Ti a modificat, dar care inca nu a fost scris in BD)
(3) A treia conditie permite ca Ti si Tj sa scrie unitati de acces in acelasi timp, permitandu-se astfel un nivel de concurenta in scriere mai ridicat, insa cu conditia ca seturile de scriere a celor doua tranzactii sa nu se suprapuna
Pentru validarea tranzactiei Tj, trebuie verificat daca una din aceste conditii este indeplinita in functie de fiecare tranzactie comisa Ti a.i. ts(Ti)
Fiecare din aceste conditii (vezi slide anterior) asigura ca modificarile efectuate de Tj nu sunt vizibile in Ti
Anomaliile de tip Dirty Read, Lost Update, Non-repeatable Read nu sunt posibile (acestea rezulta din executia incorecta a operatiilor conflictuale RW, WR, WW)
Resurse implicate:
In intretinerea listelor de citire / scriere pentru fiecare din setul de tranzactii concurente
In verificarea conflictelor
In copierea modificarilor din spatiu privat in cel „public” (in BD)
Daca modificarile efectuate de o tranzactie nu pot fi validate, tranzactia este anulata
Sunt memorate versiuni ale unitatilor de acces modificate de tranzactiile comise
fiecare operatie de scriere W(x) are ca efect crearea unei noi versiuni a lui x;
la fiecare citire R(x), se primeste una din versiunile (scrise de tranzactiile – posibil comise – ale) lui x, a.i. sa se asigure serializabilitatea.
Avantajul major – tranzactiile care executa doar operatii de citire nu vor fi blocate si citesc doar date comise.
Dezavantajul major – costurile impuse de gestiunea versiunilor.
Se folosesc una sau doua versiuni pentru o unitate de acces x.
Daca pentru x sunt doua versiuni, atunci una singura este scrisa de o tranzactie comisa, iar a doua versiune este scrisa de o tranzactie inca activa. In momentul in care si aceasta se comite, a doua versiune ramane singura versiune comisa a lui x (se poate renunta la cea veche).
Se folosesc trei tipuri de blocari:
Ti vrea sa citeasca x:
Solicita RLi(x).
Daca exista un CLj(x), atunci Ti asteapta. Daca nu exista nicio blocare asupra lui x, sau exista RL sau WL, atunci Ti citeste versiunea comisa a lui x (sau versiunea scrisa de insasi Ti).
Ti vrea sa scrie x:
Solicita WLi(x).
Daca exista WLj(x) sau CLj(x), atunci Ti asteapta. Altfel, scrie o noua versiune Wi(xi).
Ti vrea sa se comita:
Incearca sa converteasca toate blocarile de scriere in blocari de certificare.
Daca exista cel putin o blocare de citire pe oricare din unitatile de acces solicitate, atunci se intra in asteptare.
Observatie: Toate blocarile sunt mentinute pana la sfarsitul tranzactiei.
Se stocheaza versiuni ale fiecarei inregistrari care este modificata (precum versiunile unei aplicatii software, indica numarul reviziei”” la care s-a ajuns)
La modificarea unei inregistrari de catre o tranzactie, imaginea inregistrarii inaintea modificarii este copiata in „version store”
„Version store” este o colectie de pagini in tempDB
Daca sunt mai multe tranzactii care modifica o inregistrare, versiunile sale sunt pastrate intr-o lista inlantuita de versiuni
TempDB trebuie sa aiba la dispozitie suficient spatiu pentru „version store”; daca tempDB se umple (este setat sa ramana la dimensiune fixa sau nu mai este spatiu pe disc), comenzile de modificare nu mai genereaza versiuni si se executa cu succes, iar interogarile ar putea sa esueze din lipsa unei versiuni necesare
Citirile nu solicita blocari asupra inregistrarilor => alti cititori sau scriitori pot sa-si efectueze operatiile asupra datelor
Scriitorii nu blocheaza cititorii
Scriitorii se blocheaza intre ei; nu pot exista doua tranzactii care sa modifice aceeasi inregistrare in acelasi timp
activat la setarea optiunii bazei de date READ_COMMITTED_SNAPSHOT pe ON:
ALTER DATABASE MyDatabase
SET READ_COMMITTED_SNAPSHOT ON
toate operatiile vad versiuni ale inregistrarilor care au fost comise in momentul in care a inceput executia comenzii SQL => snapshot al datelor la nivel de comanda
consistenta citirii la nivel de comanda
Nivele de izolare MVCC
Nivele de izolare MVCC
Snapshot Isolation
activat la setarea optiunii bazei de date ALLOW_SNAPSHOT_ISOLATION pe ON:
ALTER DATABASE MyDatabase
SET ALLOW_SNAPSHOT_ISOLATION ON
toate operatiile vad versiuni ale inregistrarilor care au fost comise in momentul in care a inceput executia tranzactiei => snapshot al datelor la nivel de tranzactie
consistenta citirii la nivel de tranzactie
Utilizarea multiversionarii
Utilizarea multiversionarii
Pas 1: setarea uneia dintre optiunile READ_COMMITTED_SNAPSHOT sau ALLOW_SNAPSHOT_ISOLATION pe ON:
alter database MyDb
set READ_COMMITTED_SNAPSHOT on | off
alter database MyDb
set ALLOW_SNAPSHOT_ISOLATION on | off
Pas 2:
daca e setata optiunea READ_COMMITTED_SNAPSHOT, atunci tranzactiile care ruleaza sub nivelul de izolare Read Committed folosesc versionarea inregistrarilor
daca e setata optiunea ALLOW_SNAPSHOT_ISOLATION, atunci pentru o tranzactie se poate seta nivelul de izolare Snapshot
Citirea datelor
Citirea datelor
O tranzactie care citeste date nu solicita blocari pentru inregistrarile citite.
Sub nivelul de izolare Read Committed cu versionare
se ia ultima versiune generata pentru acea inregistrare – care da starea comisa a inregistrarii in momentul inceperii executiei interogarii.
este obtinuta versiunea curenta a inregistrarii in momentul in care a inceput tranzactia => snapshot al datelor consistent tranzactional, relativ la momentul in care a inceput tranzactia.
la inceperea unei tranzactii, se inregistreaza toate tranzactiile care sunt active in sistem. Cand aceasta vrea sa citeasca o inregistrare pentru care exista o lista inlantuita de versiuni, se cauta versiunea al carei XSN este cel mai mare XSN (cel mai apropiat) mai mic decat al tranzactiei care citeste (a.i. sa nu fie al unei tranzactii care era activa in momentul in care a inceput cea in cauza).
Scrierea datelor
Scrierea datelor
In cazul unei tranzactii sub Read Committed cu versionare
se solicita o blocare pentru scriere. Daca reuseste sa obtina blocarea, atunci se creeaza o noua versiune si blocarea e mentinuta pana la sfarsitul tranzactiei. Acest comportament este similar celui de Read Committed fara versionare.
In cazul nivelului de izolare Snapshot
se solicita blocare – e obtinuta, sau se asteapta. Insa – la iesirea din asteptare (cand ar obtine blocarea X), scrierea esueaza (tranzactia curenta este anulata) daca se determina ca o alta tranzactie a comis modificarea inregistrarii respective dupa ce tranzactia curenta si-a inceput executia (conflict la actualizare).
