Wykład 12

Zarządzanie transakcjami

 

Wprowadzenie

Do tej pory czytelnik zapoznał się z podstawowymi strukturami danych na dysku i w pamięci wewnętrznej RAM, które umożliwiają przechowywanie danych na dysku i realizację instrukcji języka SQL. Nie braliśmy przy tym pod uwagę czy z bazy danych korzysta jeden czy wielu użytkowników. Teraz uwzględnimy możliwość równoczesnej pracy z bazą danych przez wielu użytkowników. System bazy danych musi zapewnić aby użytkownicy nie przeszkadzali sobie nawzajem w pracy z bazą danych np. gdy kilku z nich chce zarezerwować sobie miejsce w samolocie na ten sam lot.

Zlecenie użytkownika kierowane do SZBD ma postać transakcji – czyli ciągu instrukcji SQL, które są wykonywane jako całość: albo wszystkie albo żadna z nich. Przypominamy, że transakcje w języku SQL zostały już  omówione na wykładzie 3.

W tym wykładzie przedstawimy problemy jakie napotyka się, gdy akcje współbieżnie wykonywanych transakcji są przeplatane oraz w jaki sposób SZBD radzi sobie z pojawiającymi się problemami. Podstawą realizacji transakcji przez SZBD jest protokół ścisłego blokowania dwufazowego w skrócie Strict-2PL (ang. Strict Two-Phase Locking).

 


12.1 Transakcje

Współbieżność

Współbieżne wykonywanie programów użytkowników jest istotne dla szybkości działania aplikacji baz danych. Dostęp do danych na dysku jest częsty i względnie wolny, więc procesor może jednocześnie wykonywać kilka programów.

Instrukcje SQL tworzące transakcję mogą być podawane przez użytkownika w pewnych odstępach czasu i zależeć od wyniku poprzednich. Oczywiste jest więc, że również z tego powodu system nie może rezerwować czasu całego procesora do wykonania jednej transakcji.

Z punktu widzenia systemu SZBD transakcja stanowi reprezentację programu użytkownika i jest ciągiem odczytów i zapisów do bazy danych. Współbieżność uzyskuje się przez przeplecenie ze sobą odczytów i zapisów różnych transakcji. Efekt powinien być taki jakby transakcje były wykonywane niezależnie od siebie w czasie. Moduł zarządzania transakcjami zajmuje się organizacją współbieżnego wykonywania transakcji użytkowników.

Poprawność i spójność

Podstawowe znaczenie ma poprawność wykonywanych transakcji. Tę poprawność wspomagają więzy spójności definiowane przez administratora danych i projektanta bazy danych a sprawdzane przez system. Stan bazy danych jest spójny gdy są spełnione wszystkie więzy spójności. Nie wszystkie warunki poprawności mogą być sprawdzone przez system. System może sprawdzić w ramach więzów spójności, na przykład, czy format numeru telefonu jest prawidłowy; ale nie może sprawdzić czy jest to rzeczywiście numer telefonu osoby, o której informacje trzymamy w bazie danych. Należy więc do obowiązków użytkownika zadbanie, aby dane wprowadzane i aktualizowane przez transakcję wiernie odpowiadały rzeczywistym danym – zdefiniowane przez projektanta a sprawdzane przez system więzy spójności mogą tu tylko pomóc.

Oprócz sprawdzania więzów spójności, do zadań SZBD należy zadbanie aby poprawne transakcje zostały poprawnie zrealizowane w sytuacji współbieżnego wykonywania transakcji, czyli w sytuacji przeplatania ich akcji. Za poprawny stan bazy danych po współbieżnym wykonaniu zbioru transakcji przyjmuje się każdy stan, który można otrzymać przez szeregowe (sekwencyjne) wykonanie tych transakcji - przy czym różna kolejność wykonywania transakcji może prowadzić do innego poprawnego stanu. Dochodzi do tego jeszcze możliwość wycofania każdej transakcji ze zbioru (anulowania wszystkich wprowadzonych przez nią zmian). Ewentualne wznowienie tej samej transakcji użytkownika, oznacza już nową transakcję z punktu widzenia systemu.

Aksjomaty ACID

Są cztery ogólne wymagania, jakie stawia się przed SZBD co do współbieżnego wykonywania transakcji. Noszą one nazwę aksjomatów wykonywania transakcji ACID od czterech słów angielskich: A - Atomicity (atomowość), C - Consistency (spójność), I - Isolation (izolacja) oraz D - Durability (trwałość).

  1. Atomowość (niepodzielność) - każda transakcja jest niepodzielną operacją z punktu widzenia użytkownika: albo wszystkie akcje wchodzące w skład transakcji są wykonywane albo żadna z nich.
  2. Spójność - po wykonaniu zbioru transakcji stan bazy danych powinien być spójny (pod warunkiem, że przy rozpoczynaniu transakcji stan bazy danych był spójny oraz że każda z wykonywanych transakcji jest z osobna poprawna).
  3. Izolacja - transakcje powinny sobie wzajemnie nie  przeszkadzać w działaniu. Każdy użytkownik powinien mieć iluzję, że sam korzysta z bazy danych. Przy najwyższym (zalecanym) stopniu izolacji wymaga się aby transakcja działała na spójnym, nie zmienianym przez innych użytkowników fragmencie bazy danych.
  4. Trwałość - dane zatwierdzone przez transakcję powinny być dostępne nawet w sytuacji awarii programu, komputera lub nośnika danych.

Mechanizmy współdzielenia zasobów bazy danych

SZBD stosuje następujące mechanizmy służące do zapewnienia aksjomatów ACID:

Atomowość transakcji

Transakcja może zakończyć swoje działanie na cztery sposoby:

W każdej więc z tych sytuacji albo cała transakcja zostaje wykonana albo żadna jej część nie zostaje wykonana. Transakcję można traktować jak pojedynczą, atomową operację na bazie danych.

SZBD zapisuje wszystkie wykonywane akcje w dzienniku (logu) tak aby w razie potrzeby, gdy nie jest możliwe doprowadzenie transakcji do końca, móc ją wycofać czyli anulować wszystkie jej akcje.

Prześledźmy na prostym przykładzie problem przeplotu akcji przy współbieżnej realizacji dwóch transakcji.

Przykład
 
T1: BEGIN A=A+100, B=B-100 END
T2: BEGIN A=1.06*A, B=1.06*B END

Intuicyjnie transakcja T1 dokonuje transferu $100 z konta B na konto A. Transakcja T2 dopisuje do obu kont 6% odsetki.

Poprawna, współbieżna realizacja obu transakcji powinna być równoważna albo szeregowemu wykonaniu T1 potem T2 albo szeregowemu wykonaniu T2 potem T1. W przykładzie, w obu przypadkach efekt jest taki sam.

Rezultat współbieżnego wykonania kilku transakcji może być niejednoznacznie określony.

Oto możliwy, poprawny (z punktu widzenia otrzymywanego wyniku) przeplot akcji obu transakcji (czyli plan ich wykonania):
 
T1: A=A+100,                  B=B-100
T2:                 A=1.06*A,                B=1.06*B

A to niepoprawny plan (z powodu niepoprawnego wyniku):
 
T1: A=A+100,                                    B=B-100
T2:                 A=1.06*A, B=1.06*B

SZBD abstrahuje od znaczenia poszczególnych operacji na danych. Z punktu widzenia SZBD drugi plan jest postaci:
 
T1: R(A), W(A),                                     R(B), W(B)
T2:                  R(A), W(A), R(B), W(B)

gdzie R(A) oznacza operację odczytu obiektu A, a W(A) operację zapisu obiektu A. Z punktu widzenia zarządzania transakcjami jeszcze dwie operacje są istotne: Commit - zatwierdzenie transakcji oraz Rollback - anulowanie transakcji.

Na początku naszych rozważań przyjmiemy upraszczające założenia, że baza danych jest zbiorem niezależnych (niepodzielnych) obiektów oraz że zbiór ten nie zmienia się w trakcie realizacji transakcji. Potem pokażemy jak rozszerzyć otrzymane wyniki na ogólny przypadek.
 

Plan wykonania transakcji

Plan jest to ustalenie kolejności wykonywania akcji odczytu i zapisu na obiektach bazy danych przez współbieżnie działające transakcje. SZBD stosując pewne reguły, o których będzie mowa w dalszej części, na bieżąco podejmuje decyzje, akcja której transakcji ma być wykonana jako następna - dynamicznie tworząc pewien plan wykonywania akcji zbioru współbieżnych transakcji.

Plan szeregowy jest to plan, ustawiający wykonywanie transakcji w ciąg: najpierw akcje jednej transakcji, następnie akcje drugiej transakcji itd.

Dwa plany są równoważne jeśli efekt realizacji obu planów jest taki sam dla każdego stanu bazy danych tzn. po realizacji każdego z planów otrzymujemy ten sam stan bazy danych.

Plan szeregowalny jest to plan, który jest równoważny pewnemu planowi szeregowemu. Plan szeregowy jest poprawny a więc również plan szeregowalny jako jemu równoważny jest też poprawny. Zauważmy, że:

Przykład

Oto plan (rozważany już wcześniej), który nie jest szeregowalny:
 
T1: R(A), W(A),                                                  R(B), W(B)
T2:                   R(A), W(A), R(B), W(B)

Jego nieszeregowalność wnioskuje się rozważając tzw. graf zależności akcji transakcji. Gdy zapis zmiennej A przez transakcję T1 poprzedza odczyt zmiennej A przez transakcję T2, rysujemy krawędź od T1 do T2 i opatrujemy ją etykietą A i podobnie dla B. Zbudujmy graf zależności dla rozpatrywanego planu:

Rys. 12.1 Cykl w grafie zależności
 

Przyczyna nie szeregowalności tego planu leży w cyklu grafu zależności. Wynik T2 zależy od T1 i vice-versa. Nie istnieje równoważny plan, który by uszeregował kolejność wykonywania obu transakcji - przestawiając akcje jednej z nich przed drugą.

Zjawiska niepożądane przy przeplataniu akcji

Przy analizie współbieżnego wykonywania transakcji istotne są jeszcze inne, niezależne od pojęcia szeregowalności własności, które teraz rozważymy.

Analizując współbieżne wykonywanie transakcji bierzemy pod uwagę tylko operacje odczytu i zapisu. Konflikty między transakcjami i w szczególności niemożliwość uszeregowania ich akcji, pojawiają się w związku z dokonywaniem przez nie zapisów. Oto możliwe sytuacje konfliktowe dla dwóch transakcji.

Odczyt niezatwierdzonych danych "dirty read"

Transakcja T2 odczytuje i ewentualnie zmienia niezatwierdzone jeszcze przez transakcję T1 (a więc potencjalnie niepoprawne) dane. Transakcja T1 może nawet je chcieć następnie wycofać, po tym jak T2 je już zatwierdzi!

Chociaż nie są używane powszechnie, to czasami stosuje się transakcje "na niby", których celem jest przetestowanie pewnych hipotez ("co by było gdyby Kowalski został dyrektorem? czy nasza firma by upadła?") a następnie wycofanie całej transakcji. W trakcie takich transakcji stan obiektów bazy danych może być zupełnie niezgodny z rzeczywistością (użytkownik bazy danych mógłby na przykład z niej nagle odczytać, że firma znajduje się w stanie bankructwa).

Niepowtarzalny odczyt - odczyt zatwierdzonych danych

Transakcja odczytuje dwukrotnie ten sam obiekt i za każdym razem widzi inne dane - bo w międzyczasie zmieniła je i zatwierdziła inna transakcja.

Jednak, niepowtarzalny odczyt może prowadzić do nieprawidłowego działania aplikacji bazy danych, gdy jedna transakcja podejmuje decyzję w oparciu o odczyt danych. Na przykład, odczytuje, że jest miejsce w samolocie na lot, informuje o tym użytkownika, po czym chce zarezerwować to miejsce, a w tym momencie już zostało ono zarezerwowane przez inną transakcję.

Nadpisanie niezatwierdzonych danych

Transakcja T1 zmieniła dane i nie zatwierdziła zmian. Za chwilę transakcja T2 zmieniła te same dane i zatwierdziła swoje zmiany.

Nawet wtedy gdy transakcja tylko zapisuje wartość bez wcześniejszego jej odczytu, nadpisanie niezatwierdzonych danych może spowodować niespójny stan bazy danych. Załóżmy, że spójny stan bazy danych to taki, w którym zmienne A i B mają tę samą wartość. Transakcja T1 zapisuje na obu zmiennych wartość 0, a transakcja T2 zapisuje na obu zmiennych wartość 1. Przemieszanie akcji tych transakcji doprowadzi po ich zatwierdzeniu do niespójnego stanu bazy danych, w którym A nie jest równe B.

Plan odtwarzalny

Plan, który umożliwia wycofanie każdej transakcji nazywa się planem odtwarzalnym. Plan odtwarzalny jest istotny do zapewnienia własności atomowości i trwałości.

Zastanówmy się kiedy jesteśmy w stanie wycofać transakcję T. Jeśli w danym planie nie ma zjawisk nie zatwierdzonego odczytu ani nadpisania niezatwierdzonych danych, to żadna inna transakcja nie korzysta z niezatwierdzonych zmian transakcji T i dlatego transakcję T można wycofać. Jeśli jakaś transakcja skorzystała z wyników transakcji T, to tę transakcję też trzeba wycofać, co może być już niemożliwe, jeśli ta transakcja została wcześniej zatwierdzona.

Podamy teraz rozwiązanie problemu jak zagwarantować powstawanie i realizację planów wyłącznie szeregowalnych i odtwarzalnych.

 
 


12.2 Zarządzanie współbieżnością oparte na blokadach

Podstawowe rodzaje blokad

Podstawowym mechanizmem zapobiegającym konfliktom przy współbieżnie wykonywanych transakcjach są blokady (nazywane też zamkami) zakładane na obiekty. Są dwa rodzaje blokad:

Współdzielona, typu S (ang. shared lock) - daje transakcji współdzielony dostęp do zasobu, na przykład, kilka transakcji może jednocześnie odczytywać wiersze tej samej tabeli. Jeśli transakcja zakłada współdzieloną blokadę, inne transakcje też mogą założyć współdzieloną blokadę, ale nie mogą założyć blokady drugiego rodzaju, to jest wyłącznej blokady. Operację założenia blokady współdzielonej na obiekcie A oznaczamy przez S(A).

Wyłączna, typu X (ang. exclusive lock) - daje transakcji wyłączne prawo do wprowadzania zmian obiektu. Tylko jedna transakcja może mieć założoną wyłączną blokadę na obiekcie i w tym czasie nie może być na nim założonej żadnej innej blokady nawet współdzielonej. Operację założenia blokady wyłącznej na obiekcie A oznaczamy przez X(A).
 

Istnieje metoda zakładania blokad gwarantująca powstawanie i realizację planów wyłącznie szeregowalnych i odtwarzalnych. Jest ona powszechnie używana przez SZBD. Oto ona sformułowana w postaci ogólnego protokołu zakładania blokad na obiektach:

Protokół ścisłego blokowania dwufazowego (Strict 2PL):

  1. Każda transakcja musi uzyskać blokadę S (współdzieloną) na obiekcie zanim odczyta ten obiekt oraz blokadę X (wyłączną) na obiekcie przed zapisaniem go.
  2. Jeśli transakcja trzyma blokadę X na obiekcie, żadna inna transakcja nie ma prawa założyć żadnej blokady (ani typu S ani X) na tym obiekcie.
  3. Jeśli transakcja trzyma blokadę S na obiekcie, żadna inna transakcja nie ma prawa założyć blokady X na tym obiekcie.
  4. Gdy transakcja nie może założyć blokady na obiekcie, może ustawić się w kolejce oczekujących transakcji stowarzyszonej z tym obiektem albo może zostać wycofana.
  5. Wszystkie blokady trzymane przez transakcję są zwalniane jednocześnie, w chwili gdy transakcja kończy się (wycofaniem lub zatwierdzeniem).

Punkty 2 i 3 są powtórzeniami definicji blokad S i X - przytaczamy je dla pełności. Zwracamy uwagę na istotność ostatniego punktu protokołu.

Twierdzenie
Protokół Strict 2PL gwarantuje realizację wyłącznie planów szeregowalnych i odtwarzalnych.
 

Protokół Strict 2PL nazywa się dwufazowym, ponieważ determinuje dwie fazy działania każdej transakcji związane z blokadami:

  1. transakcja zakłada blokady i dokonuje wymaganych odczytów i zapisów na obiektach, na których założyła blokadę;
  2. transakcja wykonuje COMMIT/ROLLBACK jednocześnie zwalniając wszystkie blokady.

Zakładanie blokad i ich zwalnianie są oddzielonymi w czasie fazami.
 

Zastanówmy się czy protokół Strict-2PL generuje wyłącznie plany wolne od anomalii.

Podsumujmy wynik naszego rozumowania w postaci twierdzenia.

Twierdzenie
Protokół Strict-2PL nie dopuszcza do powstania anomalii niezatwierdzonego odczytu, niepowtarzalnego odczytu i nadpisywania nie zatwierdzonych danych.
 

Uwaga

Warunek 5 protokołu Strict 2PL można złagodzić zachowując jego dwufazowość i szeregowalność. Zamiast:

można przyjąć:

Otrzymujemy protokół blokowania dwufazowego oznaczany przez 2PL, który także prowadzi do planów szeregowalnych. Przy stosowaniu jego może się jednak pojawić problem z wycofaniem transakcji. Gdy transakcja T1 zwolni blokadę obiektu A, wtedy inna transakcja T2 może dokonać zmiany tego obiektu i zatwierdzić zmiany. Po czym transakcja T1 może chcieć wykonać ROLLBACK, co wymagałoby wycofania również transakcji T2, która jednak już została zatwierdzona! Zatem protokół 2PL nie gwarantuje planów odtwarzalnych!
 

Zarządzanie transakcjami

Moduł zarządzania transakcjami operuje na transakcjach, obiektach bazy danych i na rekordach dzienników. Buduje i wykorzystuje struktury danych przechowujące dane o powiązaniu między sobą obiektów bazy danych, transakcji i rekordów dziennika:

  1. transakcje (tablica transakcji w RAM) i obiekty (bazy danych) są powiązane związkiem: "transakcja trzyma określoną blokadę na obiekcie bazy danych" (na ogół blokowana jest strona, na której leży obiekt - nie tylko sam obiekt);
  2. transakcje (tablica transakcji w RAM) i rekordy dziennika są powiązane związkiem: "ostatnio wykonana przez transakcję operacja jest opisana w rekordzie dziennika" (informacja ta jest potrzebna do rozpoczęcia wycofywania transakcji i odtwarzania po awarii serwera).

Szczegóły algorytmów stosowanych w module zarządzania transakcjami pomijamy jako wykraczające poza zakres tego wykładu.
 

Zakleszczenia (deadlocks)

Protokół Strict-2PL nie zapewnia, że działanie transakcji dojdzie do końca (nie zostanie wstrzymane przez SZBD). Sytuacja taka może się pojawić w związku ze zjawiskiem zakleszczenia, kiedy dwie lub więcej transakcji wzajemnie blokują sobie - potrzebne do kontynuowania swojego działania - obiekty.

Na przykład, transakcja T1 dokonała blokady obiektu A, a transakcja T2 obiektu B. W kolejnym kroku T1 chce założyć blokadę na obiekt B, a T2 na obiekt A. Obie transakcje przestają działać oczekując, potencjalnie w nieskończoność, na zwolnienie blokady przez drugą transakcję.

Zakleszczenie (ang. deadlock) jest to cykl transakcji oczekujących wzajemnie na zwolnienie blokady przez inną transakcję w cyklu. Są trzy sposoby radzenia sobie z zakleszczeniami:

  1. zapobieganie,
  2. wykrywanie,
  3. ustalenie limitu oczekiwania na blokadę (timeout).

Zapobieganie polega na ustaleniu priorytetu między transakcjami np. transakcja, która rozpoczęła się wcześniej ma z definicji wyższy priorytet. Nie dopuszcza się do tego aby transakcja z wyższym priorytetem czekała na transakcję z niższym priorytetem. Aby do tego nie dopuścić, transakcja z niższym priorytetem zostaje wycofana przez system.

Wykrywanie zakleszczeń polega na analizie, która transakcja oczekuje na zwolnienie blokady przez którą transakcję i sprawdzaniu czy występuje cykl.

  1. Utwórz graf oczekiwań na zwolnienie blokady:
  2. Co jakiś czas sprawdzaj, czy w grafie jest cykl. Jeśli jest, wycofaj jedną z transakcji w cyklu.

Przykład rozpoznania zakleszczenia

Dla czterech transakcji:

 
T1: S(A), R(A),                       S(B)
T2:                  X(B),W(B)                               X(C)
T3:                                                 S(C), R(C)                   X(A)
T4:                                                                          X(B)
budujemy graf oczekiwań na zwolnienie blokady (rys. 12.2).

Rys. 12.2 Graf oczekiwań na zwolnienie blokady
 

Próba wykonania operacji X(A) przez transakcję T3 wprowadza cykl do rozważanego grafu (czerwona krawędź zamyka cykl). Aby nie dopuścić do zakleszczenia wycofujemy transakcję T3.

Zapobieganie zakleszczeniom - metoda timeout

Gdy transakcja czeka bezczynnie na zwolnienie blokady dłużej niż ustalony odcinek czasu timeout, transakcja zostaje wycofana przez system.
 

Zjawisko przeładowania

Im więcej transakcji jest równocześnie aktywne, tym większe jest  prawdopodobieństwo, że dana transakcja będzie czekać na zwolnienie blokady przez inną działającą transakcję. Od pewnej liczby aktywnych transakcji działanie systemu zaczyna się pogarszać – coraz mniejsza liczba akcji jest wykonywana. Dla określonej bazy danych i jej aplikacji administrator bazy danych powinien znaleźć ten punkt "przeładowania systemu" i powinien ograniczać liczbę równocześnie działających transakcji. Drugą metodą dawania sobie rady z przeciążeniem systemu jest identyfikacja najczęściej używanych (blokowanych) obiektów (ang. hot spots) i próba rozładowania zapotrzebowania na nie np. przez zastosowanie replikacji lub zmianę aplikacji.
 

Problem fantomów

Protokół Strict-2PL (w dotychczasowej postaci) jest poprawny pod warunkiem, że baza danych jest ustaloną, nie zmieniającą się kolekcją obiektów. Oto przykład dwóch transakcji, dla których realizacja za pomocą protokołu Strict-2PL daje plan nie szeregowalny.

  1. T1 blokuje wszystkie strony zawierające rekordy pracowników z E.Job='SALESMAN' i wyznacza zarabiającego najwięcej (E.Sal = 3000).
  2. Następnie T2 wstawia nowego pracownika: E.Job='SALESMAN', E.Sal = 3500.
  3. T2 usuwa najlepiej zarabiającego pracownika z E.Job='MANAGER' (zarabiającego powiedzmy E.Sal = 5000) i zatwierdza.
  4. T1 blokuje wszystkie strony zawierające rekordy pracowników z E.Job='MANAGER' i wyznacza najlepiej zarabiającego (powiedzmy E.Sal = 4500).

Wykonywania tych dwóch transakcji nie da się uszeregować!

Rozwiązanie

Nie wystarcza to, że transakcja T1 zakłada blokadę wszystkich istniejących rekordów pracowników z E.Job='SALESMAN'. Potrzebne są blokady na całe zbiory rekordów określone przez predykaty np. E.Job='SALESMAN'. Można to uzyskać przez zablokowanie węzła indeksu z E.Job='SALESMAN', jeśli taki indeks istnieje albo trzeba zablokować całą tabelę, gdy indeksu nie ma. Dodajemy ten postulat do definicji protokołu Strict-2PL.

Rys. 12.4 Blokada węzła indeksu
 

Zatem indeksy oprócz zastosowania do wyszukiwania i zapewnienia zachodzenia więzów klucza głównego i jednoznacznego, pełnią także istotną rolę przy zapewnieniu szeregowalnego planu wykonywania transakcji!
 

Blokady zakładane na węzłach B+ drzewa

Przy wykonywaniu operacji na wierszach tabeli należy również dokonać odpowiednich modyfikacji w każdym indeksie dla tej tabeli np. dodać nowe pozycje danych z kluczem wstawianego rekordu przy INSERT lub usunąć pozycje danych dla usuwanego rekordu przy DELETE. Rozważmy przypadek indeksu zbudowanego na B+ drzewie. Zmiany dotyczą liści drzewa, ale mogą również dotyczyć innych węzłów na ścieżce od korzenia do liścia. Jednocześnie na indeksie może być wykonywane kilka operacji pochodzących z różnych transakcji. Potrzebne są więc blokady zakładane na węzły drzewa, blokujące innym operacjom dostęp do węzła na którym pracuje dana operacja.

Przy samym wyszukiwaniu, węzły na ścieżce od korzenia do liścia nie muszą być blokowane (a dokładniej, węzeł jest blokowany tylko w czasie jego odczytu).

Przy wykonywaniu instrukcji INSERT, węzeł na ścieżce od korzenia do modyfikowanego liścia musi zostać zablokowany w trybie X tylko jeśli proces podziału węzłów może zostać propagowany do niego od modyfikowanego liścia (podobnie dla DELETE). Schodząc  w dół drzewa dokonujemy blokady aktualnego węzła i sprawdzamy, czy możemy zdjąć blokadę z węzłów, które leżą wyżej na ścieżce do korzenia. Zatem zawsze co najmniej jeden węzeł w drzewie pozostaje zablokowany w trybie wyłącznym.
 


12.3 Poziomy izolacji transakcji

Przypominamy z wykładu 3, że standard ANSI/ISO definiuje cztery poziomy izolacji określające, jakie zmiany dokonywane przez inne współbieżnie działające transakcje, widzi dana transakcja.

Poziom izolacji Niezatwierdzony odczyt Niepowtarzalny odczyt Fantomy
READ UNCOMMITED TAK TAK TAK
READ COMMITED NIE TAK TAK
REPEATABLE READS NIE NIE TAK
SERIALIZABLE   NIE NIE NIE
Tab. 12.1 Poziomy izolacji transakcji w SQL
 

Wyjaśnimy, jak są one implementowane przez SZBD.

1. SERIALIZABLE - transakcja T odczytuje tylko obiekty, których zmiany zostały zatwierdzone; żadna wartość odczytana lub zmieniona przez T nie może być zmieniona przez inną transakcję, dopóki T nie skończy się; wyniki instrukcji SELECT wyliczone przez transakcję T nie zmieniają się, dopóki T nie skończy działać.

Transakcja T uzyskuje blokady do odczytu i zapisu obiektów zgodnie z protokołem Strict-2PL plus blokady typu S na zbiory wierszy wynikowych instrukcji SELECT (realizowane albo poprzez zablokowanie węzła indeksu albo poprzez zablokowanie całej tabeli).

2. REPEATABLE READS - transakcja T może odczytywać tylko obiekty, których zmiany zostały zatwierdzone; żadna wartość odczytana lub zmieniona przez T nie może być zmieniona przez inną transakcję dopóki T nie skończy się.

Transakcja T uzyskuje blokady do odczytu i zapisu obiektów zgodnie z protokołem Strict-2PL. Nie mamy do czynienia z blokadami zakładanymi na zbiory wierszy wynikowych instrukcji SELECT.

3. READ COMMITED - transakcja T może odczytywać tylko obiekty, których zmiany zostały zatwierdzone; żadna wartość zmieniona przez T nie może być zmieniona przez inną transakcję, dopóki T nie skończy się.

Transakcja T uzyskuje blokady X aby wykonać zmiany i utrzymuje te blokady do końca swojego działania. Do wykonania odczytu uzyskuje blokadę S. Po zakończeniu odczytu blokada jest natychmiast zwalniana (nie czekając na koniec transakcji).

W implementacji Oracle uzyskanie blokady S do odczytu obiektu nie jest konieczne. Zamiast zakładać blokadę S do odczytu, Oracle korzysta z cechy wielowersyjności danych (co jest omówione dalej). Poziom READ COMMITTED w Oracle umożliwia większy poziom współbieżności niż w Standardzie, gdyż umożliwia odczytywanie obiektów nawet wtedy gdy inna transakcja założyła na tym obiekcie blokadę X (co jest niedozwolone w wersji opisanej przez Standard).

4. READ UNCOMMITEDT odczytuje obiekty w dowolnej chwili; T nie dokonuje żadnych zapisów.

Transakcja nie zakłada żadnych blokad ale też nie ma prawa wprowadzać żadnych zmian do bazy danych.
 

Optymistyczne blokowanie

Alternatywą do omawianej do tej pory metody nazywanej blokowaniem pesymistycznym jest metoda blokowania optymistycznego polegająca na nie blokowaniu obiektów i wykonywaniu operacji przez transakcję najpierw w jej lokalnych buforach.

Faza 1: Transakcja wczytuje potrzebne dane do swoich lokalnych buforów i na nich dokonuje zmian bez zakładania żadnych blokad.

Faza 2: Transakcja sprawdza czy dokonane przez nią odczyty i zapisy nie pozostają w konflikcie z odczytami i zapisami zatwierdzonych już transakcji. Jeśli nie, następuje przepisanie zmian z lokalnych buforów do globalnych i zatwierdzenie transakcji. Jeśli tak, następuje restartowanie jeszcze raz tej samej transakcji - nie jest potrzebne wycofywanie zmian w bazie danych, bo żadne nie zostały wprowadzone.

Tylko w czasie realizacji Fazy 2 jest konieczność założenia blokad X na zmieniane obiekty.
 

Wielowersyjność danych

Realizację wielowersyjności danych można sobie wyobrazić w ten sposób, że procesy zapisujące na obiekcie tworzą nową wersję obiektu, podczas gdy procesy odczytujące korzystają ciągle ze starej wersji.

 

Rys. 12.5 Koegzystencja różnych wersji tego samego obiektu
 

Zapytanie odwołuje się do stanu bazy danych z pewnej chwili w przeszłości - na przykład, z chwili kiedy nastąpiło rozpoczęcie wykonywania zapytania lub, z chwili kiedy nastąpiło rozpoczęcie wykonywania transakcji.
 
Przyjmując model wielowersyjności danych, transakcje tylko odczytujące mogą działać bez zakładania blokad, w tym odczytywać obiekty z założoną blokadą X.

W trybie READ COMMITED system Oracle pozwala zawsze odczytywać dane niezależnie od założonych blokad X (dane te mogą być w trakcie zmieniania przez inne transakcje). System używa wielowersyjności – podobnie jak przy wykonywaniu transakcji typu tylko-odczyt:

            SET TRANSACTION READ ONLY;

Blokady w Oracle

Przy wykonywaniu instrukcji SQL Oracle sam zakłada blokady na wiersze i tabele. Użycie instrukcji LOCK TABLE prowadzi do spowolnienia działania wykonywania transakcji, więc powinno być używane tylko w specjalnych przypadkach gdy chcemy zawczasu ograniczyć w odpowiedni sposób innym transakcjom dostęp do tabeli.
 


12.4 Podsumowanie

Wykład 12 przedstawił metody stosowane przez SZBD do współbieżnego wykonywania transakcji.

 


12.5 Słownik pojęć

transakcja - ciąg instrukcji SQL, które są wykonywane jako całość: albo wszystkie albo żadna z nich.

aksjomaty ACID - podstawowe właściwości jakie powinna spełniać implementacja transakcji przez SZBD: atomowość, spójność, izolacja, trwałość.

atomowość (niepodzielność) - aksjomat realizacji transakcji polegający na tym, że albo wszystkie akcje wchodzące w skład transakcji są wykonywane albo żadna.

spójność - aksjomat realizacji transakcji polegający na tym, że po wykonaniu transakcji stan bazy danych powinien być spójny (pod warunkiem, że przy rozpoczynaniu transakcji stan bazy danych był spójny).

izolacja - aksjomat realizacji transakcji polegający na tym, że wynik działania transakcji powinien być taki sam, jakby od chwili rozpoczęcia transakcji nie działała na wspólnych danych żadna inna transakcja. Każdy użytkownik powinien mieć iluzję, że sam korzysta z bazy danych.

trwałość - aksjomat realizacji transakcji polegający na tym, że  dane zatwierdzone przez transakcję powinny być dostępne (ewentualnie do odtworzenia) nawet w sytuacji awarii oprogramowania lub sprzętu.

plan - zaplanowanie w czasie wykonywania akcji odczytu i zapisu na obiektach bazy danych przez współbieżnie działające transakcje.

plan szeregowy - plan wykonania akcji transakcji, ustawiający wykonywanie transakcji w ciąg: najpierw akcje jednej transakcji, następnie akcje drugiej transakcji itd.

plan szeregowalny - plan wykonania akcji transakcji, który jest równoważny pewnemu planowi szeregowemu.

blokada obiektu - ograniczenie używania obiektu przez innych użytkowników.

blokada współdzielona, typu S - daje transakcji współdzielony dostęp do zasobu. Np. kilka transakcji może jednocześnie pracować na tej samej tabeli. Jeśli transakcja zakłada współdzieloną blokadę, inne transakcje też mogą założyć współdzieloną blokadę, ale nie mogą założyć wyłącznej blokady.

blokada wyłączna, typu X - daje transakcji wyłączny dostęp do obiektu. Tylko jedna transakcja może mieć założoną wyłączną blokadę na obiekcie i w tym czasie nie może być założonej żadnej innej blokady nawet współdzielonej.

protokół ścisłego blokowania dwufazowego (Strict 2PL) - zasady wykonywania transakcji przez system oparte na zakładaniu i zwalnianiu blokad gwarantujące realizację tylko planów szeregowalnych (co zapewnia zachodzenie aksjomatów izolacji i spójności).

zakleszczenie (deadlock) - cykl transakcji oczekujących wzajemnie na zwolnienie blokady.

fantom - wiersz, który zostaje wstawiony do tabeli po tym jak transakcja wykonała operację na tej tabeli a przed jej zatwierdzeniem (co potencjalnie oznacza, że gdyby ten wiersz był obecny przy wykonywaniu operacji, jej wynik byłby inny).

optymistyczne blokowanie - wykonywanie transakcji w jej lokalnych buforach i dopiero na koniec sprawdzenie, czy można dokonane zmiany wprowadzić do bazy danych. Zmniejsza się w ten sposób blokowanie zasobów ale nie daje gwarancji, że po wykonaniu wszystkich akcji będzie można przepisać rezultat transakcji do bazy danych (jeśli nie będzie można, trzeba będzie uzyskany rezultat porzucić i zacząć wykonywanie transakcji od nowa).

wielowersyjność - tworzenie kopii obiektów tak aby transakcja zapisująca na obiekcie mogła być wykonywana współbieżnie z transakcjami tylko odczytującymi stan obiektu. Co więcej, każda transakcja odczytująca powinna mieć swoją własną wersję, aktualną w chwili rozpoczynania się transakcji.

 


12.6 Zadania

1. Dane są dwie transakcje:
 

T1: BEGIN A=A+100, B=A END
T2: BEGIN B=1.06*B, A=B END

Czy następujące przeploty akcji obu transakcji są poprawne?

  1. T1: A=A+100,                  B=A
    T2:                 B=1.06*B,          A=B
  2. T1: A=A+100,                          B=A
    T2:                 B=1.06*B, A=B
  3. T1:                          A=A+100, B=A
    T2: B=1.06*B, A=B
 

2. Dane są dwie transakcje:
 

T1: BEGIN A=A+100, C=A END
T2: BEGIN B=1.06*B, C=B END

Czy następujące przeploty akcji obu transakcji są poprawne?

  1. T1: A=A+100,                  C=A
    T2:                 B=1.06*B,          C=B
  2. T1: A=A+100,                          C=A
    T2:                 B=1.06*B, C=B
  3. T1:                          A=A+100, C=A
    T2: B=1.06*B, C=B
 

Strona przygotowana przez Lecha Banachowskiego. Ostatnia aktualizacja - 12/04/05 .