1 Algorytmy zarządzania współbieżnym wykonywaniem transakcji 1

2 Klasyfikacja algorytmów Algorytmy zarządzania współbieżnym wykonywaniem transakcji możemy sklasyfikować następująco: 1.algorytmy blokowania 1.algorytmy blokowania - uszeregowanie transakcji wynika z kolejności uzyskiwanych blokad (algorytm blokowania dwufazowego – 2PL) 2.algorytmy znaczników czasowych 2.algorytmy znaczników czasowych - uszeregowanie transakcji wynika z wartości etykiet czasowych związanych z transakcjami 3.algorytmy optymistyczne 3.algorytmy optymistyczne - walidacja poprawności uszeregowania 2

3 Algorytmy blokowania (1) Blokada jest zmienną skojarzoną z każdą daną w bazie danych, określającą dostępność danej ze względu na możliwość wykonania na niej określonych operacji Ogólnie, z każdą daną mamy skojarzoną jedną blokadę Ze względu na proces blokowania, dane w bazie danych mogą występować w jednym z trzech stanów: – dana nie zablokowana (0) – dana zablokowana dla odczytu R (współdzielona S) – dana zablokowana dla zapisu W (wyłączna X) 3

4 Algorytmy blokowania (2) Zarządca blokad musi realizować trzy dodatkowe operacje na bazie danych: – Blokowanie danej x do odczytu (LR(x)) – Blokowanie danej x do zapisu (LW(x)) – Odblokowanie danej x (UNL(x)) Operacje blokowania muszą poprzedzać wykonanie operacji odczytu oraz zapisu danej 4

5 Kompatybilność blokad Dwie blokady są kompatybilne jeżeli mogą być założone na tej samej danej przez dwie różne transakcje RW R  W  Blokada uzyskana Blokada żądana 5

6 Konwersja blokad Transakcja posiadająca blokadę określonego typu na danej może dokonać jej konwersji w blokadę innego typu RW R  W Blokada uzyskana Blokada żądana 6

7 Implementacja algorytmów blokowania (1) Zarządca blokad (lock manager) wykonuje następujące operacje: – Lock(trans-id, data-item-id, mode) LR – read lock LW – write lock – Unlock(trans-id, data-item-id) – Unlock(trans-id) Zarządca blokad zapamiętuje blokady w tzw. tablicy blokad. Operacja Lock wstawia do tablicy rekord [trans-id, mode]. Operacja Unlock usuwa rekord z tablicy 7

8 Implementacja algorytmów blokowania (2) danaLista blokadKolejka oczekujących x1[T1, w][T2, r] x2[T1, r] [T2,r][T3, w] x3[T2, w][T3, w] x4[T4, w][T5, w] [T6, r] 8

9 Implementacja algorytmów blokowania (3) Tablica blokad jest tablica haszową, której argumentem jest data-item-id (rid) Procedura zakładania blokad generuje data-item-id, np. wykorzystując funkcję haszową zdefiniowana na nazwie danej Operacje Lock i Unlock muszą być atomowe, stąd dostęp do tablicy blokad, jak do innych obiektów bazodanowych, również podlegać mechanizmom zarządzania współbieżnością, w tym, algorytmowi blokowania Operacje Lock i Unlock są często wykonywane, stąd muszą być bardzo szybkie 9

10 Implementacja algorytmów blokowania (4) Alternatywna implementacja tablicy blokad danatidblokada x1T1W x2T1R x2T2R x3T2W danatidblokadakolejka x1T2R1 x1T3W1 x2T4W2 Tablica blokad + kolejki transakcji do zasobów 10

11 Implementacja algorytmów blokowania (5) R_lock(X, Tid) begin if (LOCK(X, tid)=0 or LOCK(X, tid)=R) then LOCK(X, Tid)  R; else begin ; end R_lock; 11

12 Implementacja algorytmów blokowania (6) W_lock(X, Tid) begin if LOCK(X, tid)=0 then LOCK(X, Tid)  W; else begin ; end W_lock; 12

13 Implementacja algorytmów blokowania (7) Unlock(X, Tid) begin if LOCK(X, Tid) = W then begin LOCK(X, Tid)  0; ; end; else if LOCK(X, tid) = R then begin LOCK(X, tid)  0; if (number_of_read_locks_on_X=0)then begin ; end; end Unlock; 13

14 Blokowanie nie wystarcza Sam mechanizm blokowania nie gwarantuje uszeregowalności realizacji: LR 1 [x] r 1 [x] UNL 1 [x] LW 1 [y] w 1 [y] UNL 1 [y]c 1 LR 2 [y] r 2 [y] LW 2 [x] w 2 [x] UNL 2 [y] UNL 2 [x] c 2 Usuwając operacje zakładania i zdejmowania blokad otrzymamy następującą realizację: r 1 [x] r 2 [y] w 2 [x] c 2 w 1 [y] c 1 która nie jest realizacją uszeregowalną Podstawowym problemem jest kolejność zdejmowania blokad 14

15 Algorytm 2PL (1) Transakcja T jest well-formed jeżeli dla każdej operacji założenia blokady dla transakcji T istnieje operacja zdjęcia blokady Transakcja T jest two-phase locked jeżeli: – Przed odczytem danej x, T musi uzyskać blokadę dla odczytu danej x – Przed zapisem danej x, T musi uzyskać blokadę dla zapisu danej x – T trzyma każdą blokadę danej aż nie zakończy wykonywania odpowiedniej operacji – Po zdjęciu pierwszej blokady, transakcji T nie może żądać założenie nowych blokad Każda transakcja zakłada blokady w fazie ekspansji i zdejmuje blokady w fazie zwijania Przykład na poprzednim slajdzie - T 2 jest two-phase locked, natomiast transakcji T 1 nie, gdyż UNL 1 [x] < LW 1 [y] – Symbol “

16 Algorytm 2PL (2) Algorytm podstawowy: 1.Każda operacja read(X) transakcji T musi być poprzedzona operacją R_lock(X, T) lub W_lock(X, T) 2.Każda operacja write(X) transakcji T musi być poprzedzona operacją W_lock(X, T) 3.Operacje unlock(X,T) transakcji T są wykonywane po zakończeniu wszystkich operacji read i write tej transakcji 16

17 Algorytm 2PL (3) Twierdzenie 2PL: jeżeli w realizacji r wszystkie transakcje są well- formed i two-phase locked, to realizacja r jest konfliktowo uszeregowalna (r  CSR) 17

18 Algorytm 2PL (4) Algorytm 2PL nie gwarantuje odtwarzalności (recoverability) Przykład nieodtwarzalnej realizacji 2PL : r:LW 1 [x] w 1 [x] UNL 1 [x] LR 2 [x] r 2 [x] c 2 … UNL 1 [z] c 1 – realizacja r nie jest ścisła i nie unika kaskadowych wycofań Jak zagwarantować ścisłość realizacji? - blokady dla zapisu muszą być utrzymywane aż do zakończenia wykonywania operacji commit lub abort – gwarantuje to odtwarzalność i unikanie kaskadowych wycofań – dla realizacji r powyżej, T 1 musi zostać zaakceptowana zanim zostanie zwolniona pierwsza blokada dla zapisu (UNL 1 ): LW 1 [x] w 1 [x] c 1 UNL 1 [x] LR 2 [x] r 2 [x] c 2 18

19 Automatyczne zakładanie blokad Algorytm 2PL może być transparentny dla aplikacji użytkownika Data manager po otrzymaniu operacji Read lub Write od transakcji, inicjuje odpowiednie operacje założenia blokady dla odczytu lub zapisu Skąd Data manager wie, kiedy może bezpiecznie rozpocząć fazę zdejmowania blokad? Standardowo, Data manager utrzymuje blokady danej transakcji do momentu akceptacji lub wycofania transakcji. Data manager: – może zdjąć blokadę (blokady) dla odczytu po otrzymaniu operacji commit od transakcji – może zdjąć blokadę (blokady) dla zapisu po zakończeniu wykonywania operacji commit (co gwarantuje ścisłość realizacji) 19

20 Transaction Handshakes (1) Moduł CC kontroluje wyłącznie wykonywanie operacji dostępu do bazy danych (Read i Write) Założenie: transakcje są izolowane i komunikują się wyłącznie poprzez dane (własność izolacji) – gwarancja uszeregowalności Jeżeli transakcje komunikują się w inny sposób (bezpośrednio) – pojawia się problem zapewnienia uszeregowalności Jeżeli transakcje komunikują się poprzez przesyłanie komunikatów, wówczas, aby zapewnić poprawność (CSR), należy zaimplementować SendMsg jako Write, i ReceiveMsg jako Read W przeciwnym przypadku możemy otrzymać następującą realizację: w 1 [x] r 2 [x] sendMsg 2 [M] receiveMsg 1 [M] – Data manager nie jest świadom komunikacji, stąd, z jego punktu widzenia realizacja jest CSR Występuje jeszcze problem komunikacji nieformalnej (brain transport) 20

21 Transport nieformalny 21 T1: Start... Display output Commit T2: Start Get input from display... Commit User reads output … User enters input Brain transport

22 Transaction Handshakes (2) Jeżeli użytkownik, zanim rozpocznie transakcję T 2, zaczeka na zakończenie wykonywania i akceptację transakcji T 1 to możemy zignorować problem komunikacji nieformalnej Taka relację między transakcjami nazywamy transaction handshake (transakcja T 1 zostaje zaakceptowana (commit) przed inicjacją (rozpoczęciem) transakcji T 2 ) Algorytm blokowania 2PL zachowuje porządek relacji „transaction handshakes” – tzn., transakcja T 1 zostanie uszeregowana przed T 2 – nie każda realizacja SR posiada taką własność: r 1 [x] w 2 [x] c 2 r 3 [y] c 3 w 1 [y] c 1 22

23 Działanie algorytmu 2PL 23 T1T1 T2T2 R_lock(T 1, Y) read(Y) W_lock(T 1, X) R_lock(T 2, X) read(X)(wait) X := X + Y;(wait) write(X);(wait) unlock(Y)(wait) unlock(X)(wait) read(X) W_lock(T 2, Y) read(Y) Y := Y + X; write(Y); unlock(X) unlock(Y)

24 Zakleszczenie (1) 24 T1T1 T2T2 R_lock(T 1, Y) read(Y) R_lock(T 2, X) read(X) W_lock(T 2, Y) W_lock(T 1, X)(wait) deadlock

25 Zakleszczenie (2) Zastosowanie algorytmu 2PL może prowadzić do wystąpienia zjawiska zakleszczenia Zakleszczenie jest efektem działania algorytmu 2PL w przypadku, gdy realizacja na wejściu modułu CC jest nieuszeregowalna realizacja: – LR 1 [y] r 1 [y] LR 2 [x] r 2 [x] … nie można wykonać poprawnie sekwencji operacji w 2 [y] w 1 [x] i jednocześnie zagwarantować uszeregowalności realizacji Rozwiązanie zakleszczenia polega na wycofaniu jednej z zablokowanych transakcji – Zwolnienie blokady przez transakcję T bez wycofania tej transakcji prowadzi do naruszenia reguły 2PL 25

26 Zakleszczenie (3) Dwa podejścia do problemu zakleszczenia transakcji w systemach baz danych: Wykrywanie i rozwiązywanie zakleszczenia Zapobieganie wystąpieniu zakleszczenia Podejście wykorzystujące ideę unikania zakleszczenia nie jest wykorzystywane w praktyce, chociaż algorytm unikania zakleszczenia poprzez uporządkowanie zasobów (resource ordering) mógłby znaleźć zastosowanie w przypadku np. zakleszczeń na hot-spot’ach 26

27 Zapobieganie (1) Algorytm no waiting Algorytm no waiting: Transakcja T i próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję T j. Transakcja T i jest wycofywana i restartowana z pewnym opóźnieniem czasowym Algorytm cautious waiting Algorytm cautious waiting: Transakcja T i próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję T j. Jeżeli transakcja T j nie czeka na uzyskanie innej blokady, T i będzie czekać na zwolnienie blokady przez T j. W przeciwnym wypadku T i jest wycofywana i restartowana 27

28 Zapobieganie (2) etykiety czasowe transakcji Algorytmy wykorzystujące etykiety czasowe transakcji - TS(T), nadawane w momencie inicjacji transakcji: – wait-die – wait-die: Transakcja T i próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję T j. Jeżeli TS(T i ) < TS(T j ) (T i jest starsza T j ) wtedy transakcja T i będzie czekać na zwolnienie blokady. W przeciwnym wypadku T i będzie wycofana i restartowana z tym samym znacznikiem czasowym – wound-wait – wound-wait: Transakcja T i próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję T j. Jeżeli TS(T i ) < TS(T j ) (T i jest starsza T j ) wtedy transakcja T j będzie wycofana i restartowana z tym samym znacznikiem czasowym. W przeciwnym wypadku T i będzie czekać na zwolnienie blokady 28

29 Metoda wykrywania i rozwiązywania zakleszczenia (1) 29 Graf oczekiwania Graf oczekiwania (waits-for graph – WFG)) T1T1 T3T3 T2T2 Zakleszczenie jest zjawiskiem stosunkowo rzadkim i, najczęściej, obejmuje niewiele transakcji. Stąd, taniej jest wykrywać zakleszczenia i je rozwiązywać w momencie wystąpienia. x y z

30 Metoda wykrywania i rozwiązywania zakleszczenia (2) Graf WFG jest okresowo sprawdzany, czy wystąpił w nim cykl. Zakleszczenie jest rozwiązywane przez wycofanie jednej z transakcji należących do cyklu Mechanizm timeout-u: jeżeli transakcja czeka zbyt długo na założenie blokady (przekroczyła czas timeout-u), możemy założyć, że wystąpiło zakleszczenie (wersja 1) Mechanizm timeout-u: jeżeli transakcja czeka zbyt długo na założenie blokady (przekroczyła czas timeout-u), wycofujemy transakcję (wersja 2) – Proste i łatwe do implementacji – Niestety, czasami niepotrzebnie wycofujemy transakcję 30

31 Metoda wykrywania i rozwiązywania zakleszczenia (3) Do budowy grafu WFG wykorzystujemy tablicę blokad. Z każdą blokadą są związane dwie listy: lista transakcji, które uzyskały blokadę, oraz lista transakcji oczekujących na przydział blokady. Obie listy mają postać ((T i, m i ),...), gdzie T i oznacza transakcję, natomiast m i oznacza rodzaj blokady. Do grafu WFG dodajemy luk T i  T j, jeżeli zachodzi warunek: – transakcja T j należy do listy transakcji, które uzyskały blokadę, natomiast T i jest na liście transakcji oczekujących, lub – transakcja T j jest przed transakcją T i na liście transakcji oczekujących – blokady m i i m j są niekompatybilne 31

32 Metoda wykrywania i rozwiązywania zakleszczenia (4) 32 T1T1 T4T4 T2T2 T3T3 Transaction wait list Lock lists WFG T1 T2 T3 T2: W T1: R T4: R T2: W T3: W

33 Metoda wykrywania i rozwiązywania zakleszczenia (5) Twierdzenie: jeżeli w systemie wystąpiło zakleszczenie, to WFG reprezentujący relację wzajemnego oczekiwania transakcji w systemie zawiera cykl Podejście dominujące w systemach bd – Pozwala na lepsze wykorzystanie zasobów – Jest tanie i łatwe w implementacji – Zakleszczenie jest zjawiskiem rzadkim Po wykryciu zakleszczenia jest ono rozwiązywane przez wycofanie jednej z transakcji należących do cyklu (victim) Wybierz „ofiarę” której wycofanie będzie najtańsze – np., transakcję o najmniejszej liczbie założonych blokad 33

34 Cykliczny restart transakcji (1) Błędny wybór „ofiary” może prowadzić do cyklicznego restartu transakcji – np. zawsze usuwamy najstarszą transakcję w cyklu: – Rozpoczęcie transakcji T 1, następnie rozpoczyna się transakcja T 2 – Wystąpiło zakleszczenie obejmujące transakcje T 1 i T 2, wycofujemy transakcję T 1 (najstarsza) – Transakcja T 1 jest restartowana i ponowne zakleszcza się z transakcją T 2 – Transakcja T 2 (najstarsza) jest wycofywana... Restartuje ponownie …. 34

35 Cykliczny restart transakcji (2) Wybierając najmłodszą transakcję w cyklu WFG jako ofiarę unikamy cyklicznego restartu transakcji, gdyż najstarsza transakcja nie jest nigdy ofiarą rozwiązania cyklu (może to jednak prowadzić do stałego restartowania transakcji – infinite restarting) Wybór ofiary w oparciu o czas inicjacji można połączyć z innymi heurystykami, np. transakcja o najmniejszej liczbie założonych blokad 35

36 Rozwiązania komercyjne SQL Serwer: – Wykorzystuje WFG – Wybierana jest transakcja „najtańsza”, gdzie “taniość” transakcji jest określona wielkością wygenerowanego przez nią logu – SET DEADLOCK_PRIORITY LOW (vs. NORMAL) pozwala transakcjom na zdefiniowanie swojego priorytetu względem wyboru ofiary Oracle: – Wykorzystuje WFG w systemie scentralizowanym – Transakcja, która wykryje zakleszczenie automatycznie staje się ofiarą – Wykorzystuje mechanizm timeout-u aby rozwiązywać zakleszczenie w systemach rozproszonych 36

37 Efektywność mechanizmu blokowania Zakleszczenia występują relatywnie rzadko – W rzeczywistych systemach 1-2% transakcji wpada w zakleszczenie Problemem jest efektywność mechanizmu blokowania wynikająca ze zbyt dużej liczby blokad Rozwiązanie: redukcja liczby blokad w systemie Prosta heurystyka – jeżeli więcej niż 30% transakcji jest zablokowanych, zredukuj liczbę współbieżnie wykonywanych transakcji 37

38 Problem konwersji blokad – tj., T i = read(x) … write(x) Konwersja blokad może prowadzić do zakleszczenia: – Jeżeli dwie transakcje dokonują jednocześnie konwersji blokad na danej x, może wystąpić zakleszczenie T 1 :LR[x] T 1 :r[x] T 2 :LR[x] T 2 :r[x] T 1 :LW[x] T 2 :LW[x] – Aby uniknąć zakleszczenie, transakcja (data manager) może najpierw założyć blokadę dla zapisu danej x (w-lock) a następnie zrobić down-grade blokady dla zapisu na blokadę dla odczytu (r-lock) w przypadku, gdy transakcja nie wykonuje aktualizacji danej x 38

39 Blokada aktualizacyjna (1) Down-grade blokad jest sprzeczny z zasadą 2PL (zwalniamy blokadę) – ale część systemów stosuje takie rozwiązanie Wprowadzenie blokady Update (U) – celem jest zapobieganie wystąpieniu zakleszczeń wynikających z konwersji blokad – Blokada U pozwala na czytanie danej, ale nie pozwala na jej zapis – Tylko blokadę U można zamienić na blokadę W – tj. up-grade blokad można wykonać tylko dla blokady U – Blokada U jest w konflikcie z blokadami U i W, ale jest kompatybilna z blokadą R (częściowo) – Ponieważ co najwyżej jedna transakcja może posiadać blokadę U, to nie może wystąpić zakleszczenie na skutek konwersji blokad – Blokadę U można zakładać wyłącznie na stronach i rekordach (nie można blokować w tym trybie relacji) 39

40 Blokada aktualizacyjna (2) 40 Blokada uzyskana Blokada żądana RUW R - U -- W--- Blokada uzyskana Blokada żądana RUW R -- U -- W--- Wersja 1 Wersja 2

41 Blokada aktualizacyjna (3) Można uzyskać blokadę aktualizacyjną rekordu poprzez wstawienie podpowiedzi (hint) UPDLOCK w klauzuli FROM 41 Select Emp.A From Emp (UPDLOCK) Where Emp.B = 10

42 Lock thrashing (1) Problemem algorytmu 2PL jest problem występowania opóźnienia w dostępie do danych na skutek blokowania: –Niewielkie opóźnienia do momentu nasycenia się blokad –Po nasyceniu blokad wzrost opóźnień wynikający z dłuższego czasu oczekiwania na blokady –Thrashing – moment od którego przepustowość systemu spada wraz ze wzrostem liczby aktywnych transakcji w systemie 42 Przepustowość niska wysoka liczba aktywnych transakcji maładuża thrashing

43 Lock thrashing (2) Problem lock thrashing’u jest związany z mechanizmem blokowania – Zjawisko to występuje nawet wtedy, gdy liczba wycofań transakcji jest stosunkowo niewielka Wraz ze wzrostem liczby transakcji w systemie: – Rośnie prawdopodobieństwo zablokowania nowo inicjowanych transakcji – Zanim jednak nowo inicjowana transakcja zostanie zablokowana, często, zdąży założyć blokady niektórych danych zwiększając tym samym prawdopodobieństwo zablokowania innych transakcji will block (negatywne sprzężenie zwrotne). – Zjawisko konwoju – tworzą się długie kolejki zablokowanych transakcji 43

44 Unikanie lock thrashing’u (1) Rozwiązanie: – Jeżeli ponad 30% transakcji aktywnych jest zablokowanych, system jest bliski lock thrashing’u – należy zredukować liczbę aktywnych transakcji w systemie Metoda wykrywania i rozwiązywania zakleszczeni,a bazująca na mechanizmie timeout’u, może być powodem lock thrashing’u – Jeżeli współczynnik wykrywania zakleszczenia przekracza 2% należy zredukować liczbę aktywnych transakcji w systemie – Zbyt późne wykrywanie stanu zakleszczenia zwiększa czas zbędnego blokowania zasobów i powoduje tworze konwojów 44

45 Unikanie lock thrashing’u (2) Można zastosować algorytm statyczny 2PL: wszystkie blokady muszą być uzyskane przed rozpoczęciem transakcji (przez predeklarowanie zbioru odczytywanych i modyfikowanych danych) – Uzyskanie wszystkich blokad przed rozpoczęciem transakcji zwiększa przepustowość systemu w punkcie thrashing’u (thrashing point) ponieważ zablokowane transakcje nie posiadają blokad i nie blokują innych transakcji 45

46 Unikanie lock thrashing’u (3) Zastosowanie opcja no_waiting rozwiązania konfliktu – wycofanie transakcji w momencie wystąpienia konfliktu powoduje automatycznie zmniejszenie liczby współbieżnie wykonywanych transakcji – Jeżeli koszt wycofania transakcji jest niewielki i liczba konfliktów transakcji w dostępie do innych zasobów jest mała to opcja no_waiting zwiększa przepustowość systemu przed punktem thrashing’u w stosunku do opcji wait – Z reguły czas odpowiedzi systemu (MRT) jest większy aniżeli w przypadku zastosowania opcji wait 46

47 Model blokowania (1) Bardzo uproszczony model blokowania [Bernstein, Newcomer] Założenia do modelu – Każda transakcja zakłada K blokad – N transakcji aktywnych współbieżnie – Rozmiar bazy danych D – T – średni czas pomiędzy żądaniami założenia blokady Każda transakcja posiada w danej chwili średnio K/2 blokad N transakcji aktywnych posiada w danej chwili średnio KN/2 blokad Prawdopodobieństwo wystąpienia konfliktu blokad (z założoną blokadą) dla dowolnego żądania założenia blokady danej wynosi KN/2 * 1/D = KN/2D 47

48 Model blokowania (2) Ponieważ każda transakcja żąda założenia K blokad, to prawdopodobieństwo, że w trakcie wykonywania transakcji wystąpi konflikt blokad wynosi KN/2D * K = K 2 N/2D Prawdopodobieństwo, że dwie transakcje T1 i T2 wzajemnie się zakleszczą wynosi: iloczyn prawdopodobieństwa, że T1 jest zablokowana (K 2 N/2D) * prawdopodobieństwo, że transakcja T2 jest w konflikcie blokad z transakcją T1. Prawdopodobieństwo, że transakcja T2 jest w konflikcie blokad z transakcją T1 odpowiada prawdopodobieństwu, że transakcja jest w konflikcie blokad (K 2 N/2D) podzielone przez N-1 48

49 Model blokowania (3) Upraszczając i zakładając, że dla dużego N, N-1  N, prawdopodobieństwo wzajemnego zakleszczenia transakcji T1 i T2 wynosi K 2 N/2D * K 2 N/2ND = K 4 N/4D 2 Prawdopodobieństwo, że trzy lub więcej transakcji wzajemnie się zakleszczą jest jeszcze mniejsze i możemy je pominąć Podsumowując: – Prob(zakleszczenia) jest proporcjonalne do K 4 N/D 2 – Prob(konfliktu) jest proporcjonalne do K 2 N/D – Prob(zakleszczenia) / Prop(konfliktu) = K 2 /D – dla K=10 i D = 10 6, mamy K 2 /D =.0001 Z punktu widzenia efektywności i przepustowości systemu problemem nie jest zakleszczenie lecz konflikty blokad 49

50 Model blokowania (4) Przepustowość – jeżeli żadna transakcja nie jest blokowana w trakcie realizacji, wówczas czas wykonywania transakcji (TT – transaction time) wynosi TT = T * (K+1), a przepustowość systemu wynosi N/TT = N/(T * (K+1)) Przykład: N = 50, TT = 0,5 s, to przepustowość wynosi 100 transakcji na sekundę Jednakże, cześć transakcji jest zablokowana i nie wpływa na przepustowość – tą część transakcji możemy oszacować na podstawie prawdopodobieństwa wystąpienia konfliktu K 2 N/2D * (część czasu TT transakcji, kiedy transakcja znajduje się w stanie czekania ze względu na konflikt – oznaczony A) 50

51 Model blokowania (5) Przepustowość jest wprost proporcjonalna do (N/TT) * (1 - A K 2 N/2D) Średnio A waha się pomiędzy 1/3 i ½ Przepustowość rośnie, gdy maleje czas wykonywania transakcji TT (mniejsze transakcje) i gdy blokujemy małe jednostki (wzrost D) 51

52 52 Problem duchów (1) Zakładaliśmy dotychczas, że baza danych jest zbiorem stałych i niezależnych obiektów. Rodzi to pewien problem Zakładając, że blokowania jest realizowane na poziomie rekordów bazy danych, pojawia się niebezpieczeństwo nieuszeregowalności realizacji: Zauważmy, że transakcja T1 nie widzi rekordu wprowadzanego przez transakcję T2. W odniesieniu do innej relacji, kolejność operacji transakcji T1 i T2 może być odwrotne T1: select * from emp where eyes=”blue” and hair=”red”; T2: insert into emp where eyes=”blue” and hair=”red”;

53 53 Problem duchów (2) T1: select * from emp where eyes=”blue” and hair=”red”; T2: insert into emp where eyes=”blue” and hair=”red”; T2: select * from movies where producent=”Disney”; T1: insert into movies where producent=”Disney”; duchy Zauważmy, że współbieżne wykonanie transakcji T1 i T2 może być nieuszeregowalne Takie nowowprowadzane lub usuwane rekordy nazywamy duchami (phantoms) duchami (phantoms)

54 Problem duchów (3) W jaki sposób zapobiec, aby transakcja T2 nie wprowadzała nowych rekordów do relacji emp w trakcie realizacji transakcji T1? Nie istnieje żaden mechanizm blokowania, realizowany na poziomie blokad rekordów, który gwarantowałby rozwiązanie problemu „duchów” Rozwiązanie problemu „duchów” wymaga wprowadzenia blokad hierarchicznych lub blokad predykacyjnych (predicate locks) 54

55 Problem duchów – blokady predykacyjne (logiczne) Przypuśćmy, że zapytanie odczytuje wszystkie rekordy spełniające predykat P. Przykładowo, – Select * From emp Where nazwisko = “Morzy” – Mechanizm blokad haszuje „rekord id”  „integer lock id” – I zapamiętuje blokadę w tablicy blokad. Nie rozwiązuje to problemu duchów Idealnie byłoby założyć blokadę dla odczytu na predykacie P – który byłby w konflikcie z blokadą dla zapisu Q, jeżeli jakiś rekord spełniałby predykat (P and Q) Dla dowolnych predykatów mamy problem: – Weryfikacja konfliktu predykatów zbyt wolna – Nierozstrzygalność konfliktu predykatów 55

56 Jednostka blokowania Wybór jednostki blokowania jest kompromisem między stopniem współbieżności systemu, a narzutem systemowym – Współbieżność pracy systemu rośnie wraz ze zwiększaniem precyzji blokowania (zmniejszaniem liczby zablokowanych danych i zwiększaniem liczby blokad) – Precyzyjne blokowanie jest kosztowne dla złożonych transakcji, które wymagają długiego czasu utrzymywania dużej liczby blokad – Blokowanie dużych jednostek danych wspiera złożone transakcje o dużej liczbie operacji, kosztem prostych transakcji o niewielkiej liczbie operacji Konkluzja: Konkluzja: potrzebny jest protokół, który będzie wspierał obydwa rodzaje transakcji, to znaczy taki, który będzie umożliwiał równoczesne zakładanie blokad na różnych jednostkach danych 56

57 57 Ziarnistość blokad Hierarchia ziarnistości danych Hierarchia ziarnistości danych database Relation ARelation BRelation C

58 Blokowanie wieloziarniste (1) Idea blokowania wieloziarnistego: należy umożliwić transakcjom zakładanie blokad na różnych poziomach ziarnistości blokad: – Duże transakcje (szczególnie – zapytanie) powinny mieć możliwość blokowania dużych jednostek danych (np. relacji) – Krótkie transakcje powinny mieć możliwość blokowania małych jednostek danych (np. krotki) Zarządca blokad (Lock manager) nie potrafi wykrywać konfliktów na różnych poziomach ziarnistości danych – Każdy obiekt (tj., relacja lub krotka) posiada inne id 58

59 Blokowanie wieloziarniste (2) Idea blokowania wieloziarnistego: – Wykorzystać naturalna hierarchie ziarnistości danych – Wprowadzić blokady intencyjne – przed założeniem blokady fizycznej na danym obiekcie należy założyć blokadę intencyjną na obiekcie wyższego poziomu – np., przed założeniem blokady dla odczytu danej krotki, należy uzyskać blokadę intencyjną dla odczytu relacji zawierającej daną krotkę 59

60 Blokady intencyjne (1) Idea hierarchicznego protokołu blokowania: 60 Zablokowanie pośredniego węzła w hierarchii ziarnistości danych jest równoznaczne z pośrednim zablokowaniem wszystkich węzłów potomnych Wymaga ono jednak wcześniejszego uzyskanie blokad na wszystkich węzłach rodzicielskich Zdjęcie blokady danego obiektu wymaga wcześniejszego zdjęcia blokad ze wszystkich węzłów potomnych

61 Blokady intencyjne (2) 61 IR - transakcja zamierza uzyskiwać blokady typu R na poszczególnych obiektach składowych IW - transakcja zamierza uzyskiwać blokady typu W na poszczególnych obiektach składowych RIW - transakcja blokuje wszystkie obiekty składowe w blokadą typu R, a na niektórych zamierza uzyskiwać blokady typu W Blokada uzyskana Blokada żądana IRIWRRIWW IR - IW --- R - -- RIW ---- W-----

62 Reguły blokowania intencyjnego Żądanie uzyskania blokady W na danym obiekcie jest pośrednim żądaniem ustawienia blokad W na wszystkich obiektach składowych Żądanie uzyskania blokady R na danym obiekcie jest pośrednim żądaniem ustawienia blokad R na wszystkich obiektach składowych Zanim transakcja uzyska blokadę typu IR lub R na danym obiekcie, musi uzyskać blokadę typu IR na co najmniej jednym zawierającym go obiekcie wyższego poziomu Zanim transakcja uzyska blokadę typu IW, RIW lub W na danym obiekcie, musi uzyskać blokadę typu IW na wszystkich zawierających go obiektach wyższego poziomu 62

63 63 Przykład T1: IW, T2: IR database Relation ARelation BRelation C T3: R T1: IW T1: WT1: R, T2: R T1: W T2: R

64 Złożoność blokowania wieloziarnistego Relacyjne DBMS wykorzystują blokowanie wieloziarniste w przypadku realizacji zapytań SQL oraz instrukcji DML (insert, delete, update) Część wykorzystuje ideę eskalacji blokad (lock escalation) – rozpoczyna zakładanie blokad na poziomie krotek, a następnie, jeżeli liczba blokad przekracza zadany próg n eskaluje blokadę na wyższy poziom (relacja) Area File Record Index Index Entry Hierarchia ziarnistości blokad jest DAG, nie drzewem, w przypadku uwzględniania indeksów W przypadku DAG-u założenie blokady W lub IW obiektu x wymaga założenia blokady IW wszystkich poprzedników obiektu x 64

65 65 Blokada aktualizacji (1) Blokada aktualizacji (update mode) została wprowadzona w celu minimalizacji prawdopodobieństwa wystąpienia zakleszczeń na skutek konwersji blokad (Wersja 1) Aktualizacja jest wykonywana następująco: blokada dla odczytu jest zakładana na wszystkich rekordach odczytywanych przez zapytanie (rekordy relacji emp), a następnie, na wszystkich rekordach, które spełniają predykat aktualizacji, jest zakładana blokada dla zapisu update emp set salary = salary * 1.1 where name = ”Morzy”;

66 Blokada aktualizacji (2) hotspots Problem hotspots – obiektów (rekordów) często aktualizowanych hotspots Analiza systemu R pokazała, że większość zakleszczeń pojawia się w wyniku wykonywania aktualizacji na danych typu hotspots Wprowadzenie blokady aktualizacji minimalizuje liczbę zakleszczeń występujących na skutek konwersji blokad Blokada aktualizacji może być asymetryczna (Wersja 2) Aktualizacja jest wykonywana następująco: blokada update jest zakładana na wszystkich rekordach odczytywanych przez zapytanie (rekordy relacji emp), a następnie, na wszystkich rekordach, które spełniają predykat aktualizacji, jest zakładana blokada dla zapisu (konwersja U  W) 66

67 67 Macierz kompatybilności blokad Pełna macierz kompatybilności blokad ma następującą postać: Blokada uzyskana Blokada żądana IRIWRRIWUW IR -- IW ---- R - --- RIW ----- U-- --- W------

68 68 Algorytm znaczników czasowych Znacznik czasowy Znacznik czasowy (ang. timestamp) transakcji T - TS(T), jest jej unikalnym identyfikatorem. Znaczniki są przydzielone transakcjom w kolejności, w której transakcje pojawiają się w systemie zarządzania bazą danych Z każdą daną (x) w bazie danych związane są dwie wartości znaczników czasowych: – Read_TS(x) – Read_TS(x) - największy znacznik czasowy spośród wszystkich transakcji, które pomyślnie odczytały daną x – Write_TS(x) – Write_TS(x) - największy znacznik czasowy spośród wszystkich transakcji, które pomyślnie zapisały daną x

69 69 Read(Ti, x) begin if (TS(Ti) < Write_TS(x)) then ; else begin ; Read_TS(x)  max(Read_TS(x),TS(Ti)) ; end; end Read; Implementacja algorytmu znaczników czasowych (1)

70 70 Implementacja algorytmu znaczników czasowych (2) Write(Ti, x) begin if (TS(Ti) < Read_TS(x) or TS(Ti) < Write_TS(x)) then ; else begin ; Write_TS(x)  TS(Ti); Read_TS(x)  TS(Ti); end; end Write;

71 71 Własności algorytmu znaczników czasowych Algorytm T/O, w swojej podstawowej wersji, jest wolny od zakleszczeń Algorytm T/O, w swojej podstawowej wersji, nie zapewnia odtwarzalności realizacji!!! S: T1: w(x) T2: r(x) T2: w(x) T2: c T1: abort S: T1: r(x) T2: r(y) T1: w(y) T2: w(x) T1: c T2: c

72 72 Algorytm znaczników czasowych z buforowaniem operacji (1) Aby zapewnić odtwarzalność realizacji generowanych przez algorytm T/O konieczna jest modyfikacja algorytmu polegająca na buforowaniu operacji odczytu i zapisu danych, aż do momentu zatwierdzenia transakcji Transakcja T1 zapisuje daną x: aktualizowana jest wartość znacznika Write_TS(x), zmiana wartości danej x jest odsunięta w czasie do momentu zatwierdzenia transakcji T1

73 Algorytm znaczników czasowych z buforowaniem operacji (2) Transakcja T2 odczytuje daną x aktualizowaną przez transakcję T1: znacznik transakcji TS(T2) jest porównywany ze znacznikiem Write_TS(x), jeżeli warunek odczytu jest spełniony, to odczyt jest odsunięty w czasie do momentu akceptacji transakcji T1, w przeciwnym razie transakcja T2 jest wycofywana 73 Efekt buforowania jest podobny do efektu zakładania blokad dla zapisu na danych !!!

74 74 Algorytmy optymistyczne (1) Algorytmy optymistyczne Algorytmy optymistyczne zarządzania współbieżnością transakcji przeprowadzają transakcję przez trzy stany: – Faza odczytu – Faza odczytu: Transakcje czytają dane z bazy danych. Wprowadzane modyfikacje są przechowywane w lokalnych obszarach roboczych transakcji (cache transakcji) – Faza walidacji: – Faza walidacji: Wykonywana jest walidacja czy w trakcie wykonywania transakcji wystąpiły konflikty, które mogłyby naruszać uszeregowalność realizacji. Transakcje niespełniające kryterium uszeregowalności są wycofywane i restartowane – Faza zapisu: – Faza zapisu: Jeżeli faza walidacji zakończy się pomyślnie, modyfikacje transakcji przechowywane w cache’u są wprowadzane do bazy danych

75 75 Algorytmy optymistyczne (2) Z każdą transakcją T i związane są czasy rozpoczęcia poszczególnych faz transakcji oraz utrzymywane są zbiory danych odczytywanych R i i modyfikowanych W i W fazie walidacji transakcji T i, dla każdej transakcji T j, która została zatwierdzona lub znajduje się w fazie walidacji sprawdzane jest czy spełniony jest jeden z warunków: 1.Transakcja T j zakończyła swoją fazę zapisu zanim transakcja T i rozpoczęła swoją fazę odczytu 2.(R i  W i )  W j =  i T j zakończyła swoją fazę zapisu zanim T i zakończyła swoją fazę odczytu

76 Algorytmy optymistyczne (3) Inna wersja algorytmu optymistycznego Podstawowa idea: – Transakcja wykonuje wszystkie operacje na współdzielonych danych bez zakładania blokad – aktualizacje przechowywane w obszarze roboczym transakcji – W momencie akceptacji transakcji jest wykonywany test sprawdzający czy w trakcie wykonywania transakcji wystąpiły potencjalne konflikty blokad, które mogłyby naruszać poprawność realizacji (nie ma zakładania blokad). Algorytm popularny w systemach client/server – Transakcja wykonuje wszystkie aktualizacje w buforze po stronie klienta bez konieczności zakładania blokad na serwerze bd – W momencie akceptacji transakcji, klient próbuje uzyskać blokady i wykonać aktualizacje na serwerze bazy danych 76

77 77 Standard SQL – tryb dostępu (1) Z każdą transakcją związane są trzy parametry systemowe: diagnostics_size, access_mode, i isolation_level Diagnostics_size: Access_mode: Parametr “diagnostics_size” określa liczbę opisów błędów, które system zapamiętuje dla danej transakcji Transakcja może występować w dwóch trybach: READ ONLY i READ WRITE

78 78 Standard SQL – tryb dostępu (2) Jeżeli transakcja występuje w trybie READ ONLY oznacza to, że transakcja jest zapytaniem i nie może modyfikować bazy danych. Dla transakcji w trybie READ ONLY, system zakłada wyłącznie blokady dla odczytu - prowadzi to do zwiększenia stopnia współbieżności. Domyślnie, trybem wykonywania transakcji jest tryb READ WRITE, który pozwala na wykonywanie wszystkich typów operacji na bazie danych

79 79 Poziomy izolacji (1) Większość systemów zarządzania bazami danych nie zapewnia automatycznie uszeregowalności realizacji!! Celem wprowadzenia tak zwanych poziomów izolacji jest znalezienie kompromisu pomiędzy poprawnością wykonywania transakcji a zapewnieniem jak największego stopnia współbieżności wykonywanych transakcji. Standard SQL-92 definiuje cztery poziomy izolacji: READ UNCOMMITTED READ UNCOMMITTED READ COMMITTED READ COMMITTED REPEATABLE READ REPEATABLE READ SERIALIZABLE SERIALIZABLE

80 80 Poziomy izolacji (2) SERIALIZABLE ten poziom izolacji gwarantuje, że każda transakcja T odczytuje dane utworzone wyłącznie przez zatwierdzone transakcje i że wartość żadnej danej, odczytywanej lub zapisywanej przez T, nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Ten poziom izolacji gwarantuje uszeregowalność wszystkich realizacji, jeżeli poziom izolacji każdej transakcji zostanie ustalony na poziomie SERIALIZABLE

81 81 Poziomy izolacji (3) REPEATABLE READ ten poziom izolacji gwarantuje, że każda transakcja T odczytuje dane utworzone wyłącznie przez zatwierdzone transakcje i że wartość żadnej danej, odczytywanej lub zapisywanej przez T, nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Niestety, ten poziom izolacji nie gwarantuje rozwiązania problemu „duchów” i, stąd, nie gwarantuje uszeregowalności wszystkich realizacji

82 82 Poziomy izolacji (4) READ COMMITTED READ COMMITTED (ang. cursor stability) ten poziom izolacji gwarantuje, że każda transakcja T odczytuje dane utworzone wyłącznie przez zatwierdzone transakcje i że wartość żadnej danej, zapisywanej przez T, nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Jednakże, poziom ten nie gwarantuje, że wartość danej odczytywanej przez transakcję T nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Ten poziom izolacji nie gwarantuje również rozwiązania problemu „duchów” i, stąd, nie gwarantuje uszeregowalności wszystkich realizacji

83 Poziomy izolacji (5) Poziom izolacji 1 (a.k.a. cursor stability) – Data manager utrzymuje blokadę dla odczytu read-lock(x) tylko na czas odczytu danej x (po odczycie następuje zwolnienie blokady), natomiast utrzymuje blokady do zapisu aż do momentu akceptacji transakcji (jak w 2PL) – Cursor stability - przeglądając rekordy kursora (lub wykonując scan relacji), każda operacja get-next-record zwalnia blokadę bieżącego rekordu i zakłada blokadę następnego rekordu – Operacja read(x) jest “niepowtarzalna” w ramach transakcji: LR 1 [x] r 1 [x] UNL 1 [x] LW 2 [x] w 2 [x] UNL 2 [x] c 2 LR 1 [x] r 1 [x] UNL 1 [x] – Poziom izolacji 1 jest często poziomem domyślnym DBMS! Klienci akceptują takie rozwiązanie!!! 83

84 84 Poziomy izolacji (6) READ UNCOMMITTED ten poziom izolacji dopuszcza odczyt przez transakcję T zmian dokonywanych przez aktywne jeszcze transakcje. Ten poziom izolacji jest dostępny tylko dla transakcji wykonywanych w trybie READ ONLY

85 85 Poziomy izolacji (6) W standardzie SQL-92 poziom izolacji i tryb wykonywania transakcji definiuje się za pomocą komendy SET TRANSACTION. Przykładowa komenda deklaruje transakcje jako transakcję tylko do odczytu i realizacje uszeregowalną SET TRANSACTION ISOLATION LEVEL SERIALIZABLE READ ONLY

86 86 2/8/2012 86 MS SQL Server Lock hints w klauzuli SQL FROM – Wszystkie poziomy izolacji zdefiniowane w standardzie ANSI, plus … – UPDLOCK - zastosuj blokadę update zamiast blokady read – READPAST – ignoruj zablokowane rekordy (dostępny na poziomie izolacji „read committed”) – PAGLOCK – zastosuj blokadę strony (page lock) w przypadku, gdy system automatycznie zastosowałby blokadę relacji – TABLOCK – współdzielona blokada relacji aż do zakończenia polecenia lub zakończenia transakcji – TABLOCKX – wyłączna blokada relacji aż do zakończenia polecenia lub zakończenia transakcji