Controlul concurenței DBMS: Protocoale bazate pe blocare și timestamp

Ce este controlul concurenței?

Controlul concurenței Într-un sistem de gestionare a bazelor de date, o procedură pentru gestionarea operațiunilor simultane fără a intra în conflict unele cu altele este asigurată de efectuarea concomitentă și precisă a tranzacțiilor în baza de date pentru a produce rezultate corecte, fără a încălca integritatea datelor din baza de date respectivă.

Accesul concurent este destul de ușor dacă toți utilizatorii doar citesc date, deoarece nu există nicio modalitate prin care aceștia să interfereze unii cu alții. Cu toate acestea, orice bază de date practică are un amestec de operațiuni de READ și WRITE, așadar concurența devine o provocare.

Controlul concurenței în DBMS este utilizat pentru a aborda astfel de conflicte, care apar mai ales într-un sistem multi-utilizator. Prin urmare, controlul concurenței este unul dintre cele mai importante elemente pentru funcționarea corectă a unei baze de date în care două sau mai multe tranzacții se execută simultan și necesită acces la aceleași date. Acesta funcționează mână în mână cu managementul tranzacțiilor, care definește unitățile de lucru pe care controlul concurenței trebuie să le intercaleze în siguranță.

Probleme potențiale de concurență

Iată câteva probleme cu care este posibil să te confrunți fără un control adecvat al concurenței în DBMS:

• Actualizări pierdute apar atunci când mai multe tranzacții selectează același rând și îl actualizează pe baza valorii selectate.
• Dependență necommisă (citire murdară) apare atunci când o a doua tranzacție selectează un rând care a fost actualizat de o altă tranzacție care nu a fost încă validată.
• Citire nerepetabilă apare atunci când o a doua tranzacție accesează același rând de mai multe ori și citește date diferite de fiecare dată.
• Rezumat incorect apare atunci când o tranzacție realizează un sumar asupra valorii tuturor instanțelor unui element de date repetat, în timp ce o a doua tranzacție actualizează câteva dintre acele instanțe. Sumarul rezultat nu reflectă un rezultat corect.

De ce să folosiți o metodă de concurență?

Motive pentru utilizarea unei metode de control al concurenței în SGBD:

• Pentru a aplica izolarea prin excludere reciprocă între tranzacțiile conflictuale.
• Pentru a rezolva problemele de conflict citire-scriere și scriere-scriere.
• Pentru a păstra consistența bazei de date prin aplicarea constantă a constrângerilor de execuție.
• Pentru a controla interacțiunea dintre tranzacțiile concurente, realizat folosind scheme de control al concurenței.
• Pentru a ajuta la asigurarea serializabilității.

Exemplu

Să presupunem că două persoane merg simultan la chioșcuri electronice pentru a cumpăra un bilet la același film și la aceeași oră de difuzare.

Totuși, a mai rămas un singur loc pentru acel spectacol în sală. Fără controlul concurenței, este posibil ca ambii spectatori să ajungă să cumpere câte un bilet. Controlul concurenței nu permite acest lucru. Ambii spectatori pot accesa în continuare informațiile din baza de date cu locuri la film, dar controlul concurenței oferă un bilet doar cumpărătorului care finalizează primul procesul de tranzacție.

Protocoale de control al concurenței

Diferite protocoale de control al concurenței oferă compromisuri diferite între cantitatea de concurență pe care o permit și costurile suplimentare pe care le impun. Principalele tehnici de control al concurenței în SGBD-uri sunt:

• Protocoale bazate pe blocare
• Protocol de blocare în două faze
• Protocoale bazate pe marca temporală
• Protocoale bazate pe validare

Fiecare este examinat pe rând mai jos, începând cu cele mai utilizate protocoale, bazate pe încuietori.

Protocoale bazate pe blocare

Protocoale bazate pe blocare În SGBD-uri, există un mecanism prin care o tranzacție nu poate citi sau scrie un element de date până când nu dobândește o blocare corespunzătoare. Protocoalele bazate pe blocare ajută la eliminarea problemei de concurență prin blocarea sau izolarea unui anumit element de date la o singură tranzacție.

Un blocaj este o variabilă de date asociată cu un element de date care indică operațiunile care pot fi efectuate asupra acestuia. Blocajele ajută la sincronizarea accesului la elementele bazei de date prin tranzacții concurente. Toate solicitările de blocaj sunt adresate managerului de control al concurenței, iar tranzacțiile continuă numai după ce solicitarea de blocaj este aprobată.

Blocări binare: O blocare binară asupra unui element de date poate fi fie într-o stare blocată, fie într-o stare deblocată.

Partajat/Exclusiv: Acest mecanism de blocare separă blocările în funcție de utilizarea lor. Dacă se obține un blocaj pentru a efectua o operațiune de scriere, acesta se numește blocaj exclusiv.

1. Blocare comună (S): Un blocaj partajat este numit și blocaj doar pentru citire. Cu un blocaj partajat, elementul de date poate fi partajat între tranzacții, deoarece niciuna dintre ele nu are permisiunea de a actualiza elementul. De exemplu, dacă două tranzacții citesc soldul contului unei persoane, Baza de date le permite să citească prin plasarea unui lacăt partajat. Dacă o altă tranzacție dorește să actualizeze soldul respectiv, lacătul partajat împiedică acest lucru până la finalizarea citirii.

2. Blocare exclusivă (X): Cu o blocare exclusivă, un element de date poate fi citit, precum și scris. Este exclusivă și nu poate fi menținută concomitent pe același element de date. O blocare X este solicitată folosind instrucțiunea lock-x. De exemplu, atunci când o tranzacție trebuie să actualizeze soldul unui cont, acest lucru este permis prin plasarea unei blocări X; o a doua tranzacție care dorește să citească sau să scrie este apoi împiedicată.

3. Protocol de blocare simplistă: Acest lucru permite tranzacțiilor să obțină un blocaj pentru fiecare obiect înainte de a începe o operațiune. Tranzacțiile pot debloca elementul de date după finalizarea operațiunii de scriere.

4. Blocarea prealabilă revendicării: Acest protocol evaluează operațiunile și creează o listă cu elementele de date necesare pentru a începe execuția. Când toate blocajele sunt acordate, tranzacția se execută, iar toate blocajele sunt eliberate odată ce operațiunile sale se termină.

Foame: Înfometarea este situația în care o tranzacție așteaptă o perioadă nedeterminată pentru a dobândi un blocaj. Printre motive se numără o schemă de așteptare prost gestionată pentru elementele blocate, o scurgere de resurse sau selectarea repetată a aceleiași tranzacții ca victimă.

Impas: Interblocarea se referă la o situație în care două sau mai multe procese așteaptă reciproc să elibereze o resursă, formând un lanț circular.

Protocol de blocare în două faze (2PL)

Protocol de blocare în două faze, cunoscută și sub numele de 2PL, este o metodă de control al concurenței care asigură serializabilitatea prin aplicarea unui blocaj la datele tranzacțiilor, blocând accesul simultan al altor tranzacții la aceleași date.

Protocolul de blocare în două faze permite fiecărei tranzacții să efectueze o cerere de blocare sau deblocare în doi pași:

• Faza de creștere: În această fază, o tranzacție poate obține blocări, dar este posibil să nu elibereze nicio blocare.
• Faza de micșorare: În această fază, o tranzacție poate elibera blocări, dar este posibil să nu obțină nicio blocare nouă.

Este adevărat că 2PL oferă serializabilitate. Cu toate acestea, nu garantează că blocajele nu se produc. În diagrama de mai sus, detectoarele locale și globale de blocaje caută blocaje și le rezolvă prin reluarea tranzacțiilor la stările lor inițiale.

Metodă strictă de blocare în două faze

Strict 2PL este aproape la fel ca 2PL. Singura diferență este că Strict-2PL nu eliberează niciodată o blocare după utilizare. Menține toate blocările până la punctul de validare și le eliberează pe toate odată când procesul se termină.

Centralizat 2PL

În 2PL centralizat, un singur site este responsabil pentru procesul de gestionare a blocărilor. Acesta are un singur manager de blocări pentru întregul SGBD.

Copie principală 2PL

În mecanismul Primary Copy 2PL, mulți manageri de blocare sunt distribuiți către diferite locații, iar un anumit manager de blocare este responsabil pentru gestionarea blocării pentru un set de elemente de date. Când copia primară este actualizată, modificarea este propagată către serverele slave.

Distribuit 2PL

În acest mecanism, managerii de blocări sunt distribuiți către toate locațiile și sunt responsabili de gestionarea blocărilor pentru datele de la locația respectivă. Dacă nu se reproduc date, este echivalent cu Primary Copy 2PL. Costurile de comunicare ale Distributed 2PL sunt mult mai mari decât cele ale Primary Copy 2PL.

Protocoale bazate pe marca temporală

Protocol bazat pe marcaj temporal Într-un SGBD, un algoritm este un algoritm care folosește timpul sistemului sau un contor logic ca marcă temporală pentru a serializa execuția tranzacțiilor concurente. Acesta asigură că fiecare operațiune de citire și scriere conflictuală este executată în ordinea marcăi temporale.

Tranzacția mai veche are întotdeauna prioritate în această metodă. Folosește timpul sistemului pentru a determina marcajul temporal al tranzacției și este cel mai frecvent utilizat protocol de concurență. Protocoalele bazate pe blocare gestionează ordinea dintre tranzacțiile conflictuale atunci când acestea se execută; protocoalele bazate pe marcaj temporal gestionează conflictele imediat ce este creată o operațiune.

Exemplu:

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

avantaje:

• Programările sunt serializabile, la fel ca protocoalele 2PL.
• Fără așteptarea tranzacției, ceea ce elimină posibilitatea apariției blocajelor.

Dezavantaje: Înfometarea este posibilă dacă aceeași tranzacție este repornită și abandonată în mod continuu.

Protocol bazat pe validare

Protocol bazat pe validare În SGBD, cunoscută și sub denumirea de tehnica de control optimist al concurenței, este o metodă de evitare a conflictelor de concurență în tranzacții. În acest protocol, copiile locale ale datelor tranzacției sunt actualizate, nu datele în sine, ceea ce duce la mai puține interferențe în timpul execuției.

Protocolul bazat pe validare se desfășoară în trei faze:

1. Faza de citire
2. Faza de validare
3. Faza de scriere

Faza de citire

În faza de citire, valorile datelor pot fi citite de o tranzacție, dar operațiunile de scriere sau actualizările se aplică doar copiilor locale de date, nu bazei de date propriu-zise.

Faza de validare

În faza de validare, datele sunt verificate pentru a se asigura că aplicarea actualizărilor nu va încălca serializabilitatea.

Faza de scriere

În faza de scriere, actualizările sunt aplicate bazei de date dacă validarea are succes; în caz contrar, actualizările sunt eliminate, iar tranzacția este anulată.

Compararea protocoalelor de control al concurenței

Cele patru familii de protocoale fac pariuri diferite cu privire la frecvența cu care tranzacțiile intră în conflict. Tabelul de mai jos prezintă pe scurt locul în care se încadrează fiecare.

Pe scurt, protocoalele bazate pe blocări și 2PL presupun că conflictele sunt comune și le previn din timp, în timp ce protocoalele de timestamp și validare presupun că conflictele sunt rare și le rezolvă doar atunci când apar.

Caracteristicile unui protocol de concurență bun

Un mecanism ideal de control al concurenței are următoarele obiective:

• Trebuie să fie rezistent la defecțiunile site-ului și ale comunicațiilor.
• Permite executarea paralelă a tranzacțiilor pentru a obține concurență maximă.
• Mecanismele sale de stocare și metodele de calcul ar trebui să fie modeste pentru a minimiza cheltuielile generale.
• Trebuie să impună anumite constrângeri asupra structurii acțiunilor atomice ale tranzacțiilor.

Întrebări frecvente