tranzactii si paralelism

12

Click here to load reader

Upload: inaqx

Post on 28-Dec-2015

13 views

Category:

Documents


1 download

DESCRIPTION

Tranzactii Si Paralelism

TRANSCRIPT

Page 1: Tranzactii Si Paralelism

Conspect la MySQL 20

Tranzacţii şi paralelismV-om analiza posibilităţile executării tranzacţiilor în paralel de către mai mulţi utilizatori, - izolarea tranzacţiilor. SGBD sunt sisteme multiutilizatori, adică permit în paralel lucrul a mai multor utilizatori. Trebuie de ţinut cont că utilizatorii nu trebuie să încurce unul altuia. Fiindcă o unitate logică pentru utilizator este tranzacţia, lucrul SGBD trebuie organizat în aşa fel, ca utilizatorul să nu observe că tranzacţiile lor se îndeplinesc odată cu altele.. Cea mai simplă metodă este de a crea o coadă din tranzacţiile utilizatorilor şi de a le executa în ordinea apărută. Această metodă nu este convenabilă, fiindcă se pierde principiul lucrului în paralel. Rezultă că tranzacţiile trebuiesc executate odată, dar aşa, ca rezultatele să fie aşa – cum ar fi îndeplinite în rând. Complicat poate fi faptul, că dacă nu se iau careva măsuri atunci datele, modificate de un utilizator pot fi modificate de tranzacţia altui utilizator mai devreme ca să fie finisată tranzacţia primului utilizator. Una din metod este de a folosi blocările.

Pagina 1 din 8

Page 2: Tranzactii Si Paralelism

Conspect la MySQL 20

Tranzacţii în combinaţii

Atomicitatea tranzacţie presupune că trebuie să fie executată complet sau să nu fie executată deloc. SGBD garantează utilizatorului îndeplinirea următoarelor două condiţii:

1. trebuie să fie executată complet sau să nu fie executată deloc;2. În timpul executării aceste i operaţii nu se execută alte operaţii al altor tranzacţii.

Operaţiile elementare a diferitor tranzacţii pot fi executate în orice ordine (evident, în interiorul fiecărei tranzacţii operaţiile elementare sunt executate în ordinea indicată).

De exemplu, dacă sunt nişte tranzacţii, ce constau dintr-o serie de instrucţiuni elementare:

, , seria, creată de SGBD pentru a executa aceste tranzacţii poate fi de exemplu:

. Definiţie 1. O serie din mai multe tranzacţii, instrucţiunile elementare a cărora se intercalează, se numeşte combinaţie de tranzacţii. Definiţie 2. Seria, în care se execută instrucţiunile elementare a tranzacţiilor, se numeşte graficul de execuţie a tranzacţiilor. Notă. Evident, că pentru careva tranzacţii pot exista mai multe grafice de execuţie diferite. Determinarea izolării utilizatorilor, se reduce la alegerea graficului de execuţie a tranzacţiilor. Tot odată graficul de execuţie trebuie să fie optimal, de exemplu, să dea timp minim pentru executarea tranzacţiilor fiecărui utilizator. V-om analiza termenul grafic de execuţie ”corect”şi unele remarci despre optimalitate.

Pagina 2 din 8

Page 3: Tranzactii Si Paralelism

Conspect la MySQL 20

Problemele executării paralele a tranzacţiilor. Cum pot tranzacţiile unor utilizatori să încurce la alţi utilizatori? Se discută despre trei probleme de bază a paralelismului:

Problema pierderii rezultatelor modificării. Problema dependenţei nefixate (citirea datelor „murdare”, citirea incorectă). Problema analizei incompatibile.

Să analizăm aceste situaţii. Fie două tranzacţii, A şi B, sunt executate conform căruiva grafic. Fie că tranzacţiile lucrează cu careva obiecte a BD, de exemplu cu rândurile tăbliţei. Instrucţiunea de citire a

rândurilor v-om nota-o , unde - valoarea citită. Instrucţiunea de scriere a

valorii în rândul v-om nota-o . Problema pierderii rezultatelor modificăriiDouă tranzacţii pe rând înscriu careva date în acelaşi rând şi fixează modificări.

Tranzacţia A Timpul Tranzacţia B

De citire ---

---De citire

Scriere ---

---Scriere

Fixarea tranzacţiei ---

--- Fixarea tranzacţiei

Pierderea rezultatelor modificării    

Rezultat. La finisarea ambelor tranzacţii, rândul conţine valoarea , introdusă de tranzacţia mai târzie B. Tranzacţia A nu ştie nimic despre existenţa tranzacţiei B, şi

evident aşteaptă, ca rândul conţine valoarea . Astfel, tranzacţia A a pierdut rezultatele lucrului efectuat.

Pagina 3 din 8

Page 4: Tranzactii Si Paralelism

Conspect la MySQL 20

Problema dependenţei nefixate (citirea datelor „murdare”, citirea incorectă). Tranzacţia B modifică date în rând. După aceasta tranzacţia A citeşte datele modificate şi lucrează cu ele. Tranzacţia B refuză şi repune datele vechi.

Tranzacţia A Timpul Tranzacţia B

---De citire

---Scriere

De citire ---

Lucrul cu datele citite ---

---Refuzarea tranzacţiei

Fixarea tranzacţii ---

Lucrul cu datele “murdare”    

Cu ce a lucrat tranzacţia A? Rezultat. Tranzacţia A în lucrul său a folosit date, care nu sunt în BD şi nu au fost. Întradevăr, după refuzarea tranzacţiei B, trebuie să se restabilească situaţia, cum dacă tranzacţia B în genere nicicând nu s-a executat. Aşa dar, rezultatele lucrului tranzacţiile A sunt incorecte, fiindcă ea a lucrat cu datele, ce nu sunt în BD.

Problema analizei incompatibileAceastă problemă include mai multe variante:

Necitirea repetată. Elemente fictive (fantomă). Analiza incompatibilă.

Necitirea repetată. Tranzacţia A de două ori citeşte acelaşi rând. Între aceste citiri s-a inserat tranzacţia B, care modifică valori în acest rând.

Tranzacţia A Timpul Tranzacţia B

De citire ---

---De citire

---Scriere

--- Fixarea tranzacţii

Citirea repetată ---

Fixarea tranzacţii ---

Necitirea repetată    

Tranzacţia A nu ştie nimic despre existenţa tranzacţiile B, şi, fiindcă singură nu modifică valoarea în rând, aşteaptă ca la citirea repetată valoarea să fie aceeaşi.

Pagina 4 din 8

Page 5: Tranzactii Si Paralelism

Conspect la MySQL 20

Rezultat. Tranzacţia A lucrează cu date, care din punct de vedere a tranzacţiei A se modifică de sinestătător. Elemente fictive (fantomă) Efectul elementelor fictive diferă de tranzacţiile anterioare prin faptul, că la un pas se execută multe instrucţiuni - de citire odată a mai multor rânduri, ce satisfac careva condiţie. Tranzacţia A de două ori selectează rândurile cu aceeaşi condiţie. Între selectări s-a inserat tranzacţia B, care adaugă un rând nou, ce satisface condiţiei de selectare.

Tranzacţia A Timpul Tranzacţia B

Selectarea rândurilor ce satisfac condiţia . (S-au selectat n rânduri)

---

--- Inserarea rândului nou, ce satisface condiţia .

--- Fixarea tranzacţii

Selectarea rândurilor ce satisfac condiţia . (S-au selectat n+1 rânduri)

---

Fixarea tranzacţii ---

Au apărut rânduri, care mai devreme nu erau    

Tranzacţia A nu ştie nimic despre existenţa tranzacţiile B, şi, fiindcă singură nu modifică valoarea în rând, aşteaptă ca la a doua selectare să fie găsite aceleaşi rânduri. Rezultat. Tranzacţia A în două selectări egale a obţinut diferite rezultate.

Analiza incompatibilă. Efectul analizei incompatibile se deosebeşte de celelalte exemple prin faptul, că în combinaţie există două tranzacţii – una mare, alta mică. Tranzacţia mare execută careva analiză pentru tot tabelul, de exemplu, calculează suma totală a banilor din conturile clienţilor băncii pentru contabilul şef. Fie că pe toate conturile sunt aceleaşi sume, de exemplu, câte $100. Tranzacţia mică în acest moment execută transferul a $50 de pe un cont la altul, astfel, că suma totală pe conturi nu se modifică.

Tranzacţia A Timpul Tranzacţia B

De citire contul şi sumare. ---

---Extragerea banilor din contul .

---Adăugarea banilor la contul .

--- Fixarea tranzacţii

De citire contul şi sumare. ---

Pagina 5 din 8

Page 6: Tranzactii Si Paralelism

Conspect la MySQL 20

De citire contul şi sumare. ---

Fixarea tranzacţii ---

Suma $250 pe toate conturile nu este corectă – trebuie să fie $300    

Rezultat. Chiar dacă tranzacţia B a executat tot corect – banii au fost transferaţi fără pierderi, dar în rezultatul execuţiei tranzacţiei A a calculat suma incorectă. Fiindcă tranzacţiile de transferare se execută de obicei des, rezultă că contabilul şef nicicând nu va şti câţi bani sunt în bancă.

Conflicte între tranzacţii Am observat, că analiza problemei paralelismului ne arată, că dacă nu sunt primite măsuri speciale atunci în timpul lucrului în combinaţii se pierde cerinţa (I) a tranzacţiei - izolarea. Tranzacţiile real încurcă una alteia de a primi rezultate corecte. Nu toate tranzacţiile însă încurcă una alteia. Evident, că, tranzacţiile nu încurcă dacă ele se adresează la date diferite sau se execută în timp diferit. Definiţie 3. Tranzacţiile se numesc concurente, dacă ele se intersectează în timp şi se adresează la aceleaşi date. În rezultatul concurenţei cu datele între tranzacţii apar conflicte de acces la date. Se deosebesc următoarele forme de conflicte :

W-W (Scriere - Scriere ). Prima tranzacţie a modificat obiectul şi nu s-a finisat. A doua tranzacţie modifică acest obiect. Rezultatul - pierderea modificărilor.

R-W (De citire - Scriere ). Prima tranzacţie a citit obiectul şi nu s-a finisat. A doua tranzacţie efectuează modificarea acestui obiect. Rezultatul - analiză incompatibilă (necitire repetată).

W-R (Scriere - Citire). Prima tranzacţie a modificat obiectul şi nu s-a finisat. A doua tranzacţie încearcă să citească acest obiect. Rezultatul - de citire a datelor „murdare”. Conflictele de tipul R-R (De citire - Citire) lipsesc, fiindcă datele la citire nu se modifică. Celelalte probleme a paralelismului sunt mai complicate, fiindcă diferenţa principială a lor este, că ele nu pot apărea în timpul lucrului cu un obiect. Pentru apariţia acestor conflicte e necesar ca tranzacţiile să lucreze cu mai multe date. Definiţie 4. Graficul de execuţie a setului de tranzacţii se numeşte în serie, dacă tranzacţiile se execută strict una după alta. Definiţie 5. Două grafice se numesc echivalente, dacă la executarea lor se obţine acelaşi rezultat, indiferent de starea iniţială a BD. Definiţie 6. Graficul de execuţie a tranzacţiilor se numeşte corect, dacă este echivalent cu careva grafic în serie. Notă. La executarea a două grafice în serie (rezultă - corecte), ce conţine aceleaşi tranzacţii, pot fi obţinute diferite rezultate. Întradevăr, fie tranzacţia A are instrucţiunile “De adunat X cu 1”, dar tranzacţia B – “de dublat X”. Graficul în serie {A, B} v-a returna rezultatul 2(X+1), dar graficul în serie {B, A} v-a returna rezultatul 2X+1. Rezultă că pot exista mai multe grafice de executare a tranzacţiilor, ce obţin diferite rezultate cu aceeaşi situaţie iniţială a BD. Problema determinării lucrului izolat al utilizatorilor nu se reduce numai la determinarea graficelor corecte în serie de execuţie a tranzacţiilor. Dacă aceasta ar fi fost suficient,

Pagina 6 din 8

Page 7: Tranzactii Si Paralelism

Conspect la MySQL 20

atunci cea mai simplă soluţie era serializarea – aranjarea tranzacţiilor în rând comun, după timpul apariţiei a lor şi executarea lor strict în ordinea apariţiei. Problema este în faptul, că acest grafic nu va fi cel optimal din punct de vedere a eficienţei sistemei. Mai analizăm un exemplu – dorim să obţinem un grafic optim de executare a tranzacţiilor. Să definim noţiunea de optimal.

Fiecărui grafic posibil de execuţie a tranzacţiilor îi asociem valoarea căreiva funcţii de preţ. În calitate de funcţie de preţ putem considera, de exemplu, timpul sumar de executare a tuturor tranzacţiilor din set. Timpul executării unei tranzacţii se calculează de la momentul, când tranzacţia a apărut şi până când tranzacţia e executat ultima instrucţiune elementară a sa. Acest timp constă din următoarele componente:

1. Timpul de aşteptare a începutului tranzacţiei - timpul, care trece din momentul, când tranzacţia a apărut, şi când a început executarea reală a primei instrucţiuni elementare.

2. Suma timpurilor de executare a operaţiilor elementare a tranzacţiei.3. Suma timpurilor de executare a operaţiilor elementare a altor tranzacţii inserate

între operaţiile elementare a tranzacţiei. Optim va fi graficul, care va returna minimumul funcţiei de preţ. V-om analiza următoarea situaţie: Fie că cunoaştem care tranzacţii în care perioade de timp apar, adică, cunoaştem viitoarea combinaţie a tranzacţiilor şi momentele apariţiei fiecărei dintre tranzacţii :

Tranzacţia apare în momentul .

Tranzacţia apare în momentul . …

Tranzacţia apare în momentul . În acest caz, fiindcă setul tuturor tranzacţiilor este cunoscut din timp, teoretic putem analiza toate variantele posibile a graficelor de execuţie, şi de selectat din ele acele grafice care, în primul rând sunt corecte, şi în al doilea rând sunt optimale. În acest caz graficul optim de execuţie a tranzacţiilor este găsit. În situaţie reală, însă nu se cunosc nu numai care tranzacţii vor apare şi în ce timp, dar nu se cunoaşte nici timpul de execuţie a tranzacţiilor.

Real, sistemul poate funcţiona fără pauză mai multe zile sau chiar luni şi în acest caz setul de tranzacţii va fi setul tuturor tranzacţiilor din această perioadă. Pe de altă parte serverul poate să se deconecteze prin comanda administratorului sau în rezultatul căruiva caz excepţional. E necesar ca sistemul să funcţioneze aşa, ca în orice timp setul tranzacţiilor ce se execută să fie corect şi aproape de cel optimal.. Fiindcă tranzacţiile nu încurcă una alteia, dacă se adresează la date diferite sau se execută în timp diferit, există două metode de rezolvare a concurenţei între tranzacţii:

1. „De a stopa” unele tranzacţii pentru atât timp ca combinaţia de tranzacţii în fiecare moment de timp să fie corectă (adică, tranzacţiile concurente se execută în timp diferit).

2. De a oferi tranzacţiilor concurente „diferite” exemplare de date (adică tranzacţiile concurente să lucreze cu diferite versiuni de date).

Prima metodă „Stoparea” tranzacţiilor – se realizează prin folosirea blocărilor sau prin metoda etichetelor temporale.

Pagina 7 din 8

Page 8: Tranzactii Si Paralelism

Conspect la MySQL 20

A doua metodă - oferirea tranzacţiilor concurente „diferite” exemplare de date - se realizează prin folosirea datelor din jurnalul tranzacţiilor.

Întrebări:Combinaţii de tranzacţiiDefiniţie 2. Seria, în care se execută instrucţiunile elementare a tranzacţiilor, se numeşte graficul de execuţie a tranzacţiilor.

Problema pierderii rezultatelor modificării. Problema dependenţei nefixate (citirea datelor „murdare”, citirea incorectă). Problema analizei incompatibile.

Problema analizei incompatibileAceastă problemă include mai multe variante:

Necitirea repetată. Elemente fictive (fantomă). Analiza incompatibilă.

Definiţie 3. Tranzacţiile se numesc concurente, dacă ele se intersectează în timp şi se adresează la aceleaşi date. Definiţie 4. Graficul de execuţie a setului de tranzacţii se numeşte în serie, dacă tranzacţiile se execută strict una după alta. Definiţie 5. Două grafice se numesc echivalente, dacă la executarea lor se obţine acelaşi rezultat, indiferent de starea iniţială a BD. Definiţie 6. Graficul de execuţie a tranzacţiilor se numeşte corect, dacă este echivalent cu careva grafic în serie.

Pagina 8 din 8