Począwszy od wykładu 8 zapoznawaliśmy 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 jednocześnie 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 powinien 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.
Istotne jest, że każde 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 to jak wyglądają transakcje w języku SQL zostało już omówione na wykładzie 3. Teraz zajmiemy się sprawą implementacji transakcji przez SZBD.
W pierwszej części wykładu 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 tzw. protokół ścisłego blokowania dwufazowego w skrócie Strict-2PL (ang. Strict Two-Phase Locking).
Druga część wykładu jest poświęcona zabezpieczeniom realizowanym przez SZBD na wypadek różnego rodzaju awarii: serwera, dysku, komputera. Są one realizowane na poziomie transakcji użytkowników, to znaczy w chwili awarii wszystkie nie zatwierdzone transakcje są anulowane a efekt wszystkich zatwierdzonych transakcji jest trwały niezależnie od rodzaju awarii.
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ć wiele programów.
Bywa i tak, że instrukcje SQL tworzące transakcję są przekazywane przez użytkownika w pewnych odstępach czasu i mogą 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 wykonywania 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. Przyjmuje się, że 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.
Podstawowe znaczenie ma poprawność danych w bazie danych. 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.
Transakcja jest poprawna, jeśli wykonywana w izolacji od innych transakcji, przekształca spójny stan bazy danych w spójny stan bazy danych.
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. Co to znaczy, że SZBD realizuje poprawnie przeplecione ze sobą akcje zbioru transakcji nie jest do końca sprawą oczywistą. Na pewno, powinniśmy wymagać, aby stan bazy danych po współbieżnym wykonaniu zbioru transakcji był spójny. Co prawda, SZBD zawsze ma możliwość wycofania transakcji, ale powinien z tej możliwości korzystać tylko w zupełnie wyjątkowych przypadkach, pozostawiając inicjowanie operacji ROLLBACK aplikacji użytkownika. Przyjmowane rozwiązanie tego problemu pokazuje poniższa definicja.
Za poprawny końcowy stan bazy danych dla danego zbioru transakcji przyjmuje się każdy stan, który można otrzymać przez szeregowe (sekwencyjne) wykonanie tych transakcji z zachowaniem więzów spójności - przy czym przyjmuje się, że różna kolejność wykonywania transakcji może prowadzić do innego poprawnego końcowego stanu. SZBD poprawnie realizuje zbiór transakcji jeśli rozpoczynając od spójnego stanu bazy danych dochodzi na koniec do poprawnego końcowego stanu bazy danych dla danego zbioru transakcji. |
Dochodzi do tego jeszcze wymaganie możliwości wycofania każdej transakcji ze zbioru (anulowania wszystkich wprowadzonych przez nią zmian) tak jakby jej nie było w danym zbiorze transakcji. Ewentualne wznowienie tej samej transakcji użytkownika, oznacza już nową transakcję z punktu widzenia systemu.
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ść).
SZBD stosuje następujące mechanizmy służące do zapewnienia aksjomatów ACID:
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ł 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 nie musi być jednoznacznie 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 pierwszy plan jest postaci:
T1: R(A), W(A), R(B), W(B) T2: R(A), W(A), R(B), W(B) |
a
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 jest to ustalenie kolejności wykonywania akcji odczytu i zapisu na obiektach bazy danych współbieżnie działających transakcji. 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 z definicji poprawny a więc również plan szeregowalny jako jemu równoważny jest też poprawny. Zauważmy, że:
Reasumując szeregowalność planu wykonania zbioru transakcji oznacza możliwość przestawienia akcji transakcji z zachowaniem wyników do postaci szeregowej - ustawiające wykonywanie transakcji w ciąg: akcje pierwszej transakcji; akcje drugiej transakcji; ....
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 nie szeregowalność wnioskuje się rozważając tzw. graf zależności akcji transakcji. Gdy zapis zmiennej A przez transakcję T1 występuje przed odczytem 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. 11.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ą.
Uwagi
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 pojawiają się w związku z dokonywaniem przez nie zapisów. Oto możliwe sytuacje konfliktowe dla dwóch transakcji.
Transakcja
T2 odczytuje i ewentualnie zmienia nie zatwierdzone 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!
Poniższy plan jest tego typu.
T1: R(A), W(A), R(B), W(B) T2: R(A), W(A) |
Powyższy plan jest szeregowalny jako równoważny planowi szeregowemu: najpierw T1, potem T2.
Z założenia transakcja jako całość przekształca spójny stan bazy danych w spójny. Natomiast w trakcie wykonywania transakcji stan może być niespójny (jak w trakcie przelewu z jednego konta na drugie). Odczytując nie zatwierdzoną, niepoprawną wartość i działając na jej podstawie, tak jakby była poprawna, druga transakcja może zakończyć się zatwierdzeniem w niespójnym stanie bazy danych.
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).
Transakcja T1 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.
Poniższy plan jest tego typu.
T1: R(A),
R(A), W(A) T2: R(A), W(A), Commit |
Powyższy plan jest szeregowalny jako równoważny planowi szeregowemu: najpierw T2, potem T1.
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ę.
Transakcja T1 zmieniła dane i nie zatwierdziła zmian. Za chwilę transakcja T2 zmieniła te same dane i zatwierdziła swoje zmiany. Poniższy plan jest tego typu i nie jest szeregowalny!
T1: W(A),
W(B) T2: W(A), W(B), Commit |
Nawet wtedy gdy transakcja tylko zapisuje wartość bez wcześniejszego jej odczytu, nadpisanie nie zatwierdzonych danych może spowodować niespójny stan bazy danych. Załóżmy, że poprawny 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 niepoprawnego stanu bazy danych, w którym A nie jest równe B.
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 nie zatwierdzonych danych, to żadna inna transakcja nie korzysta z nie zatwierdzonych 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.
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).
Dodatkowo, dopuszczana jest operacja podwyższenia blokady przez transakcję. Mianowicie, transakcja, która założyła blokadę S, może ją zmienić na X, pod warunkiem, że na obiekcie nie ma założonej innej blokady S.
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:
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. Kolejność zwalniania blokad determinuje kolejność ustawienia wykonywanych transakcji w równoważny plan szeregowy.
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:
Zakładanie blokad i ich zwalnianie są oddzielonymi w czasie fazami.
Zauważmy, że protokół Strict-2PL generuje wyłącznie plany wolne od poniższych zjawisk.
Podsumujmy wynik naszego rozumowania w postaci twierdzenia.
Twierdzenie
Protokół Strict-2PL nie dopuszcza do powstania zjawisk niezatwierdzonego odczytu, niepowtarzalnego odczytu i nadpisywania nie zatwierdzonych danych.
Uwaga
Rozważane są też dwie modyfikacje protokołu strict-2PL, które umożliwiają wcześniejsze zwalnianie blokad.
Protokół 2PL1: Transakcja nie może założyć żadnej nowej blokady po zwolnieniu jakiejkolwiek blokady;
gwarantuje szeregowalność transakcji, ale nie odtwarzalność.
Protokół 2PL2: Transakcja nie może wcześniej zwolnić żadnej blokady X, ale w każdej chwili może zwolnić założoną do odczytu blokadę S;
gwarantuje odtwarzalność transakcji, ale nie szeregowalność.
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:
Szczegóły algorytmów stosowanych w module zarządzania transakcjami pomijamy jako wykraczające poza zakres tego wykładu.
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:
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.
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) |
Rys. 11.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 automatycznie wycofana przez system.
Zjawisko "zagłodzenia" transakcji
Nawet jeśli nie będziemy dopuszczać do zakleszczenia, mogą wystąpić "pechowe" transakcje, które będą wielokrotnie wybierane do wycofania i w konsekwencji mogą nigdy nie doczekać się realizacji. Przypisanie transakcji priorytetu, związanego z momentem pierwszej próby jej realizacji, powoduje że z czasem transakcja uzyskuje coraz wyższy priorytet i w końcu "wygra" z innymi, później rozpoczętymi transakcjami.
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.
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.
E.Job='SALESMAN'
i wyznacza
zarabiającego najwięcej (powiedzmy E.Sal = 3000
).E.Job='SALESMAN'
,
E.Sal = 3500
.E.Job='MANAGER'
(zarabiającego
powiedzmy E.Sal = 5000
).E.Job='MANAGER'
i wyznacza najlepiej zarabiającego (powiedzmy E.Sal =
4500
).Wykonywania tych dwóch transakcji nie da się uszeregować!
Rozwiązanie problemu
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 trybie współdzielonym węzła indeksu z
E.Job='SALESMAN',
jeśli taki indeks istnieje albo trzeba zablokować
w trybie współdzielonym całą tabelę,
gdy indeksu nie ma. Dodajemy ten postulat do definicji protokołu Strict-2PL.
Rys. 11.3 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 realizacji szeregowalnego planu wykonywania transakcji!
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 (dopóki transakcja zawierająca tę operację nie zostanie zatwierdzona lub wycofana).
Przy samym wyszukiwaniu, węzły na ścieżce od korzenia do liścia nie muszą być blokowane (z wyjątkiem odczytywanego węzła, na którym zakładamy blokadę do 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.
Obiekty bazodanowe są zagnieżdżone. Blokada na pod-obiekcie implikuje pewną blokadę na nad-obiekcie (i na odwrót). Na przykład, założenie jakiejkolwiek blokady na rekord danych, powoduje konieczność założenia pewnego rodzaju współdzielonej blokady na całą tabelę jak i całą bazę danych.
Rys. 11.4 Struktura wielopoziomowa obiektów bazy danych
W praktyce jest możliwość wyboru poziomu zakładania blokady np. gdy trzeba zaaktualizować kilka wierszy tabeli blokadę X można założyć albo na całą bazę danych, albo na całą tabelę, albo na wybrane wiersze. Z punktu widzenia czasu realizacji pojedynczej transakcji lepiej założyć jedną blokadę (S lub X) na całą tabelę, niż milion blokad (S lub X) na jej wszystkie wiersze. Z punktu widzenia poziomu współbieżności lepiej pozwolić transakcjom zakładać blokady na najniższym poziomie, czyli wierszy. Omawiane dalej blokady intencyjne stanowią kompromis między czasem przetwarzania blokad a poziomem współbieżności.
W przypadku obiektowo-relacyjnej bazy danych obiekty mogą być złożone. Konieczne jest więc użycie blokad wielopoziomowych w odniesieniu do części obiektów.
Przy wykonywaniu instrukcji DDL (czyli typu CREATE/ALTER/DROP) też są zakładane blokady:
Podstawowe typy blokad współdzielona S i wyłączna X są wystarczające w przypadku zbioru niezależnych obiektów.
Natomiast, zarówno w przypadku blokowania węzłów na ścieżce w drzewie jak i blokowania obiektów składających się z podobiektów mamy do czynienia z sytuacją, w której tylko dwa rodzaje blokad S i X nie wystarczają ze względu na ograniczenia jakie nakładają na poziom współbieżności. Jedną z metod rozszerzenia rodzajów blokad jest wprowadzenie słabszych blokad intencyjnych - w celu wyrażenia intencji ewentualnego wykonania pewnych czynności na podobiektach - bez zakładania na obiekcie nadrzędnym lub węźle nadrzędnym pełnej dla tej czynności blokady.
Na przykład, przed właściwym zablokowaniem obiektu transakcja musi założyć blokadę intencyjną na wszystkich “przodkach” danego obiektu (z góry w dół). Przy odblokowywaniu idziemy w drugą stronę z dołu w górę.
W rozważanym modelu wprowadza się dwa nowe rodzaje blokad:
Blokady intencyjne mają one słabszą moc niż odpowiednio blokada współdzielona i wyłączna. Poniższa tabelka pokazuje jakie rodzaje blokad mogą być jednocześnie założone na obiekcie.
- |
IS |
IX |
S |
X |
|
- |
√ | √ | √ | √ | √ |
IS | √ | √ | √ | √ | |
IX | √ | √ | √ | ||
S | √ | √ | √ | ||
X | √ |
Tab. 11.1 Tabela możliwego współistnienia różnych rodzajów blokad na jednym obiekcie.
Dodatkowo wyróżnia się blokadę typu SIX: oznaczającą jednoczesne założenie na jednym obiekcie dwóch blokad: S i IX.
Przykłady
1. Transakcja T używa indeksu do odczytania części tabeli R (SELECT):
T uzyskuje blokadę IS na R, a następnie kolejno uzyskuje blokadę S na odczytywanych rekordach w R.
2. Transakcja T przebiega całą tabelę R i aktualizuje kilka rekordów (SELECT FOR UPDATE, INSERT, UPDATE, DELETE):
T uzyskuje blokadę SIX na R, następnie kolejno uzyskuje blokadę S na rekordach w R i czasami podwyższa blokadę rekordu do blokady X.
3. Transakcja T używa indeksu do odczytania części tabeli R a następnie aktualizuje wybrane wiersze (UPDATE, DELETE):
T uzyskuje blokadę IX na R, a następnie kolejno uzyskuje blokadę X na
zmienianych rekordach w R.
Rozszerzenie protokołu strict-2PL do blokad intencyjnych na tabelach
Przy wykonywaniu instrukcji SQL Oracle sam zakłada potrzebne blokady na obiekty i ich części. Programista może sam też sam założyć blokadę na tabelę za pomocą instrukcji LOCK TABLE. Użycie instrukcji LOCK TABLE w trybach S i X 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.
W Oracle występują odpowiedniki blokad intencyjnych na tabeli. Blokady typu ROW SHARE i ROW EXCLUSIVE dają najwyższy stopień współbieżności z pięciu trybów blokowania.
ROW SHARE – pozwala innym transakcjom na współbieżny dostęp do zablokowanej tabeli, ale uniemożliwia zablokowanie całej tabeli w trybie wyłącznym X. SZBD stosuje tryb ROW SHARE przy wykonywaniu instrukcji:
Tryb ROW SHARE jest najmniej restryktywnym rodzajem blokady na tabeli. Inne transakcje mogą współbieżnie wykonywać na tabeli zapytania, instrukcje INSERT, UPDATE, DELETE, zakładać blokady: ROW SHARE, ROW EXCLUSIVE, SHARE, SHARE ROW EXCLUSIVE. W tym trybie inne transakcje mogą zakłada blokady X na pojedyncze wiersze.
ROW EXCLUSIVE – SZBD stosuje go przy wykonywaniu instrukcji:
Inne transakcje mogą jednoczesnie wykonywać zapytania, instrukcje INSERT, UPDATE, DELETE, zakładać blokady: ROW SHARE, ROW EXCLUSIVE. Niedozwolone są natomiast operacje:
SHARE – SZBD stosuje go przy wykonywaniu instrukcji:
Inne transakcje jednocześnie mogą tylko wykonywać zapytania, zakładać blokady na wiersze przy użyciu SELECT ... FOR UPDATE lub LOCK TABLE ... IN [ROW] SHARE MODE. Aktualizacje wierszy przez daną transakcję są dozwolone tylko jeśli żadna inna transakcja nie ma założonej blokady SHARE na tabelę (nawet jeśli jej wiersze zostały zablokowane przy użyciu SELECT ... FOR UPDATE). Niedozwolone dla innych transakcji są aktualizacje wierszy oraz instrukcje:
SHARE ROW EXCLUSIVE – SZBD stosuje go przy wykonywaniu instrukcji:
Tylko jedna transakcja w jednej chwili może mieć założoną blokadę SHARE ROW EXCLUSIVE na danej tabeli. Inne transakcje mogą jednocześnie wykonywać zapytania lub blokować wiersze używając SELECT z klauzulą FOR UPDATE, ale nie mogą dokonywać zmian w tabeli. Niedozwolone są operacje:
EXCLUSIVE – SZBD stosuje go przy wykonywaniu instrukcji:
Tylko jedna transakcja może mieć taką blokadę na tabeli. Inne transakcje mogą
wykonywać tylko zapytania na tej tabeli – nie mogą ani jej zmieniać ani zakładać
blokady do końca transakcji.
W bazie danych mamy do czynienia z konfliktem interesów. Z jednej strony jest pożądana jak największa izolacja użytkowników między sobą. Uzyskuje się ją zakładając blokady na obiekty, których używa dany użytkownik. Powoduje to jednak, że w tym czasie inni użytkownicy są ograniczani w działaniu na tych samych obiektach, co powoduje spadek efektywności działania całego systemu.
Decyzję o stopniu izolacji swojej transakcji od innych podejmuje sam użytkownik.
Przypominamy z wykładu 3, że standard ANSI/ISO definiuje cztery poziomy izolacji realizacji transakcji w zależności od tego czy pozwalamy na nie zatwierdzony odczyt, niepowtarzalny odczyt i fantomy, zobacz Tab. 11.2.
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 |
Wyjaśnimy teraz dokładniej, co te poziomy izolacji oznaczają i jak są one implementowane przez SZBD.
1. SERIALIZABLE
Oto zasady obowiązujące na tym poziomie:
Realizacja tego poziomu przez SZBD jest następująca:
Poziom izolacji SERIALIZABLE gwarantuje szeregowalność i odtwarzalność. Jest więc zgodny z teoretycznym modelem współbieżnego wykonywania transakcji.
Wymienione poniżej poziomy izolacji gwarantują odtwarzalność natomiast nie gwarantują już szeregowalności wykonywania transakcji, a więc również pełnej izolacji użytkowników.
2. REPEATABLE READS
Oto zasady obowiązujące na tym poziomie:
Realizacja tego poziomu przez SZBD jest następująca:
Nie mamy do czynienia z blokadami zakładanymi na zbiory wierszy wynikowych instrukcji SELECT.
3. READ COMMITED
Oto zasady obowiązujące na tym poziomie:
Realizacja tego poziomu przez SZBD jest następująca:
Wariant metody READ COMMITED jest wykorzystywany w implementacji Oracle, gdzie do odczytu obiektu nie jest w ogóle zakładana blokada S. Zamiast zakładać blokadę S w celu odczytania zawartości obiektu, Oracle korzysta z cechy wielowersyjności danych (co jest omówione dalej). Zatem transakcja może odczytywać obiekty niezależnie od założonych na nich blokad - przy czym odczyt dotyczy ostatnio zatwierdzonej wersji tego obiektu w chwili rozpoczynania się danej instrukcji. Zastosowanie metody READ COMMITED w wersji Oracle prowadzi do znacznego podniesienia wydajności bazy danych, kosztem zmniejszenia izolacji użytkowników.
4. READ UNCOMMITED
Oto zasady obowiązujące na tym poziomie:
Realizacja tego poziomu przez SZBD jest następująca:
Wspomnimy jeszcze o jednym poziomie izolacji, który jest realizowany w Oracle.
5. SERIALIZABLE w wersji Oracle
Oto zasady obowiązujące na tym poziomie:
Alternatywą do omawianej do tej pory metody nazywanej blokowaniem pesymistycznym jest metoda blokowania optymistycznego polegająca na nie zakładaniu blokad na obiekty, wykonywaniu operacji przez transakcję najpierw w jej lokalnych buforach i dopiero na koniec przepisywaniu zmian do bazy danych.
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. Optymistyczne blokowanie zwiększa istotnie wydajność systemu, w przypadku małego współzawodnictwa o zasoby bazy 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. 11.5 Koegzystencja różnych wersji tego samego obiektu na stosie obiektów
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 S, w tym odczytywać poprzednie stany obiektów z założoną blokadą X. |
Wspomnieliśmy już o tym uprzednio, że w trybach READ COMMITED i SERIALIZABLE system Oracle korzystając z wielowersyjności obiektów pozwala zawsze odczytywać dane niezależnie od założonych blokad X (dane te mogą być w trakcie zmieniania przez inne transakcje). System Oracle używa wielowersyjności również przy wykonywaniu transakcji typu tylko-odczyt:
SET TRANSACTION READ ONLY;
i przy wykonywaniu zapytań retrospektywnych, o czym będzie mowa w następnym punkcie.
W dzienniku bazy danych są zapisywane informacje o operacjach wykonywanych na bazie danych przez transakcje oraz inne dodatkowe informacje o zachodzących w bazie danych zdarzeniach.
Każdy rekord dziennika ma przypisany sobie identyfikujący go
numer LSN (ang. log sequence number). Przykładowo, rekord dziennika opisujący zmianę w bazie danych
ma postać:
LSN:: <typ operacji, IDtransakcji, IDstrony, offset, długość, before-image, after-image, poprzedniLSN> |
Rys. 11.6 Rejestracja zmian na stronie
Zwracamy uwagę, że rejestracja zmian dokonywanych przez pojedynczą operację transakcji dotyczy strony, a nie pojedynczego rekordu!
Oprócz zmiany danych na stronie, rekordy dziennika są tworzone także dla innych akcji takich jak: zatwierdzenie transakcji, wycofanie transakcji.
Są dwa rodzaje dzienników: dzienniki wycofań i dzienniki powtórzeń. Dziennik wycofań jest związany z wycofywaniem transakcji oraz z wielowersyjnością.
Dziennik powtórzeń jest związany z odtwarzaniem bazy danych po awarii serwera lub nośnika danych. Ze względu na odmienne spełniane funkcje, oba dzienniki zwykle są zapisywane osobno: dziennik wycofań razem z danymi w bazie danych, a dziennik powtórzeń na innym nośniku danych niż pliki z danymi. W niektórych systemach używa się tylko dziennika powtórzeń, który, tak czy owak, zawiera w sobie informacje dziennika wycofań.
W celu umożliwienia wycofania transakcji SZBD zapisuje wszystkie zachodzące na stronach dyskowych zmiany w specjalnym dzienniku wycofań (ang. undo log) nazywanym w Oracle segmentami wycofań (ang. undo segments). Dziennik wycofań jest przechowywany razem z danymi w bazie danych i sprowadzany do buforów bazodanowych. Gdy trzeba wycofać transakcję, system odczytuje w tył zapisy o zmianach wprowadzonych przez transakcję i przywraca poprzednie wartości danych w bazie danych. Dziennik wycofań jest strukturą cykliczną - następuje ciągłe nadpisywanie jego części rejestrującej zmiany, które zaszły najdawniej.
Dziennik wycofań może być podstawą realizacji wielowersyjności. Zamiast explicite utrzymywać stare wersje obiektów, można je rekonstruować z aktualnego stanu bazy i informacji wpisanych do dziennika wycofań.
W przypadku wykonywania zapytania jego wyniki powinny być spójne i odpowiadać chwili rozpoczęcia jego wykonywania. W trakcie realizacji zapytania, inne transakcje mogą zmieniać zawartość stron, które są potrzebne do wykonania zapytania (jeśli nie stosujemy blokad współdzielonych S przy wykonywaniu zapytania). W takiej sytuacji, w oparciu o dziennik wycofań należy obliczyć zawartość potrzebnej strony w chwili rozpoczynania realizacji zapytania i użyć tę zawartość do wyznaczenia wyniku zapytania.
Mianowicie, system utrzymuje licznik SCN nazywany systemowym numerem zmiany. Każda zatwierdzona transakcja zwiększa ten licznik o jeden. Wartość SCN może być uważana za identyfikator zatwierdzanej transakcji. Identyfikuje też moment w czasie działania bazy danych. Na każdej stronie z danymi jest zapisany numer SCN ostatniej transakcji, która ją zmieniła, ewentualnie informacja o założonej blokadzie X do zapisu.
Algorytm wykonywania zapytania
Niech q_SCN będzie aktualnym numerem SCN w chwili rozpoczęcia wykonywania zapytania. W trakcie wykonywania zapytania są odczytywane strony z danymi. Dla każdej takiej strony z jej nagłówka jest odczytywana zapisana w niej wartość s_SCN będąca numerem transakcji, która ją ostatnio zmieniła.
W podobny sposób są wykonywane transakcje raportujące typu READ ONLY.
Korzystając z przedstawionego algorytmu wykonywania zapytania, możemy jako q_SCN wziąć dowolny SCN, o stanie danych którego informacja jest zapisana w dzienniku wycofań. Możemy zapisać sobie aktualny SCN przy wykonywaniu danej transakcji (:SCN_FLASH w przykładzie poniżej), a następnie użyć go jako parametru zapytania retrospektywnego, w celu wyznaczenia danych jakie były aktualne w czasie wykonywania transakcji. Oto przykład zastosowania odzyskania danych po tym jak je usunęliśmy:
….
COMMIT;
VARIABLE SCN_FLASH Number;
EXECUTE :SCN_FLASH := DBMS_FLASHBACK.GET_SYSTEM_CHANGE_NUMBER;
DELETE * FROM Emp;
COMMIT;
…..
SELECT * FROM Emp
AS OF SCN (:SCN_FLASH);
Przy wykonywaniu zapytań retrospektywnych Oracle używa numerów SCN, a nie
znaczników czasowych Timestamp, które występowały w zapytaniu retrospektywnym w
wykładzie 3. Oracle co 5 minut zapisuje aktualny numer SCN - utrzymując 1440
takich numerów z 5 ostatnich dni. Przy wykonywaniu zapytania retrospektywnego
system przybliża wartość Timestamp przez najbliższy numer SCN w przechowywanym
ciągu.
Dziennik rejestrujący wszystkie zmiany zachodzące w bazie danych jest nazywany dziennikiem powtórzeń (ang. redo log). Jest on z założenia trzymany na innym nośniku danych niż pliki z danymi w bazie danych. Na ogół, dokonuje się stale jego archiwizacji przepisując go na nośnik archiwizacyjny np. na taśmę.
Dane zmieniane przez transakcję nie muszą być zapisywane na dysk dokładnie w chwili kończenia transakcji (COMMIT) ale mogą zostać zapisane:
przed jej zakończeniem (mówi się wtedy o zjawisku kradzieży ramek - ang. frame stealing);
albo później, po jej zakończeniu (mówi się wtedy o strategii nie wymuszania - ang. no force).
Przy zastosowaniu poniżej opisanego protokołu najpierw-zapis-do-dziennika (WAL) nie ma to znaczenia dla operacji COMMIT, ROLLBACK i możliwości odtworzenia danych w przypadku awarii. Po zapisie do dziennika powtórzeń nawet awaria serwera lub dysku z danymi nie spowoduje trwałej utraty danych bo można je będzie odtworzyć.
Informacja o zatwierdzeniu transakcji razem z informacjami o dokonanych przez nią zmianach są najpierw zapisywane do dziennika powtórzeń przechowywanego na innym nośniku danych (dysku) niż pliki z danymi. Jest to częścią zasady nazywanej najpierw-zapis-do-dziennika w skrócie WAL – ang. write-ahead logging.
Zasada WAL składa się z dwóch punktów:
(1) Najpierw do dziennika powtórzeń na dysku jest zapisywany rekord opisujący zmianę zawartości strony, dopiero potem strona może być zapisana na dysku. Strategia ta zapewnia możliwość przywrócenia poprzedniej zawartości strony w przypadku awarii czyli zapewnia realizację własności atomowości transakcji.
(2) Transakcja kończy się wtedy, gdy wszystkie rekordy dziennika powtórzeń dotyczące jej akcji zostaną przepisane z pamięci wewnętrznej na dysk a nie wtedy gdy dane zmienione przez transakcję zostaną zapisane na dysku. Po zatwierdzeniu, nawet w przypadku awarii serwera, jest możliwość przywrócenia danych czyli ta strategia zapewnia realizację własności trwałości transakcji.
Gdy nastąpi awaria dysku, rekordy dziennika powtórzeń (z części on-line na osobnym dysku lub części archiwizacyjnej na taśmie) zastosowane do kopii zabezpieczającej bazy danych pozwalają odtworzyć stan bazy danych i struktur danych w pamięci RAM w chwili awarii. Jest to proces nazywany odtwarzaniem do przodu.
Podobnie, w przypadku awarii serwera bazy danych analiza stron bazy danych i dziennika powtórzeń pozwala na odtworzenie stanu bazy danych w chwili awarii.
Ponieważ w dzienniku powtórzeń zapisane są również rekordy dziennika wycofań, jest możliwość wycofania nie zatwierdzonych transakcji, których działanie zostało przerwane w chwili awarii:
Jest to proces nazywany odtwarzaniem do tyłu. W rezultacie tych dwóch odtwarzań jest możliwość doprowadzenia stanu bazy danych do spójnego stanu - obejmującego tylko zatwierdzone zmiany.
Odtwarzanie po awarii serwera musi mieć zdefiniowany punkt wyjściowy określający zawartość buforów pamięci RAM - sprowadzanych z bazy danych na dysku w chwili rozpoczynania odtwarzania.
W trakcie normalnej pracy systemu w celu przyśpieszenia ewentualnego odtwarzania bazy danych po awarii serwera, jest realizowana operacja nazywana punktem kontrolnym, ang. checkpoint, polegająca na przepisaniu zawartości bufora dziennika powtórzeń do plików dziennika powtórzeń na dysku oraz na przepisaniu wszystkich zmienionych stron w buforach bazodanowych na dysk, również tych, których zmiany nie zostały jeszcze zatwierdzone. Oznacza to synchronizację aktualnych zawartości buforów pamięci RAM i dysku.
Ponadto, do dziennika powtórzeń na dysku są zapisywane rekordy punktu kontrolnego zawierające informacje o wszystkich transakcjach i stronach, aktualnie przetwarzanych w buforach pamięci RAM. Dla każdej transakcji jest podawany identyfikator rekordu dziennika powtórzeń rejestrującego ostatnią zmianę, jaka zaszła dla tej transakcji.
W osobnym, bezpiecznym miejscu, są zapisywane identyfikatory LSN rekordów ostatniego punktu kontrolnego. Od ich odczytania rozpoczyna się odtwarzanie danych po awarii serwera. Dla każdej strony, która w tym momencie była w buforze w RAM, powtarzamy operacje zapisane w dzienniku powtórzeń. Operacja punktu kontrolnego powinna być wykonywana w regularnych odstępach czasu, a także w chwili robienia kopii zabezpieczającej bazy danych - aby mieć zapisany punkt startowy do odtwarzania bazy danych po awarii dysku z danymi.
W punkcie kontrolnym istotne jest zapisanie w dzienniku powtórzeń, jakie transakcje i jakie strony znajdują się aktualnie w pamięci RAM. Można przyśpieszyć wykonywanie punktu kontrolnego, a co za tym idzie i działanie całego serwera bazy danych, przez nie przepisywanie w tym momencie na dysk zmienionych zawartości buforów bazy danych. W przypadku konieczności odtworzenia po awarii serwera, system może odtworzyć stan każdej strony w oparciu o rekordy dziennika powtórzeń wychodząc od ostatnio zapisanej zawartości strony w bazie danych. Oznacza to, że wtedy odtwarzanie trwa dłużej, ale za to punkty kontrolne, trwają krócej. Punkt kontrolny tego rodzaju nosi nazwę niepełnego punktu kontrolnego (ang. fuzzy checkpoint).
Rezerwowa baza danych jest to dodatkowa instalacja bazy danych na osobnym komputerze utrzymywana stale w specjalnym trybie oczekiwania standby – z ciągle dokonywanym odtwarzaniem w oparciu o kopie zarchiwizowanego dziennika powtórzeń generowane przez główną, operacyjną bazę danych.
W przypadku awarii dysku lub katastrofy w rodzaju ataku terrorystycznego, trzęsienia ziemi, pożaru czy kradzieży, rezerwowa bazy danych przechodzi z trybu standby w tryb read write i przejmuje obowiązki głównej bazy danych.
Rezerwowa baza danych znajduje się zwykle w fizycznie oddalonym węźle, do którego stale są przesyłane kolejne części zarchiwizowanego dziennika powtórzeń.
Rezerwowej bazy danych można używać do raportowania – przechodząc w tryb read only – napływające pozycje zarchiwizowanego dziennika powtórzeń utrzymywane są w kolejce, dopóki nie wrócimy do trybu standby. Po przejściu bazy danych w tryb read write nie jest już możliwy jej powrót do trybu standby.
Zamiast rezerwowej bazy danych alternatywę stanowią:
Dla pełności obrazu trzeba jeszcze wspomnieć, że aksjomat ACID trwałości może być także realizowany w sposób sprzętowy przez użycie macierzy dysków RAID (skrót od Redundant Array of Independent Disks) umożliwiającej redundantny zapis danych; gdy jeden dysk ulegnie awarii - dane są pobierane z drugiego.
Wykład 11 przedstawił metody stosowane przez SZBD do współbieżnego wykonywania transakcji oraz do zabezpieczeń przed utratą danych w sytuacji zaistnienia awarii.
Został omówiony protokół ścisłego blokowania dwufazowego, który zapewnia własności szeregowalności i odtwarzalności dla niezmiennego zbioru obiektów w bazie danych. Następnie pokazano jak rozszerzyć ten protokół do zmiennego zbioru obiektów w bazie danych.
W drugiej części zostały omówione dzienniki bazy danych i ich zastosowanie przy odtwarzaniu po awarii, wielowersyjności i wycofywaniu transakcji w bazie danych.
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 odczytywać dane z 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.
dziennik wycofań - dziennik rejestrujący wszystkie zmiany zachodzące na stronach dyskowych umożliwiający wycofanie transakcji. Dziennik ten jest zapisywany razem z danymi. W Oracle dziennik ten nazywa się segmentami wycofań.
dziennik powtórzeń - dziennik rejestrujący wszystkie zmiany zachodzące na stronach dyskowych umożliwiający odtworzenie bazy danych po wystąpieniu awarii. Dziennik ten jest zapisywany w innym miejscu niż dane, np. na innym dysku. Na ogół jest on stale archiwizowany tworząc zarchiwizowany dziennik powtórzeń – przechowywany na nośniku pamięci masowej np. na taśmie magnetycznej. Umożliwia to cykliczne wykorzystywanie miejsca na zapis dziennika powtórzeń na dysku.
odtwarzanie - proces odtwarzania, odzyskiwania danych straconych w wyniku awarii serwera lub dysku z danymi.
punkt kontrolny - synchronizacja pamięci RAM i struktur bazy danych zapisanych na dyskach. Stanowi punkt startowy dla procesu odtwarzania po awarii serwera.
rezerwowa baza danych - dodatkowa instalacja bazy danych na osobnym komputerze utrzymywana stale w specjalnym trybie oczekiwania (standby) – z ciągle dokonywanym odtwarzaniem w oparciu o kopie zarchiwizowanego dziennika powtórzeń generowane przez główną, operacyjną bazę danych.
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?
T1: A=A+100,
B=A T2: B=1.06*B, A=B |
T1: A=A+100,
B=A T2: B=1.06*B, A=B |
T1:
A=A+100, B=A T2: B=1.06*B, A=B |
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?
T1: A=A+100,
C=A T2: B=1.06*B, C=B |
T1: A=A+100,
C=A T2: B=1.06*B, C=B |
T1:
A=A+100, C=A T2: B=1.06*B, C=B |
.... | T1 | .... | T2 | .... |
.... | W(A) | .... | R(A) | .... |
.... | R(A) | .... | W(A) | .... |
.... | W(A) | .... | W(A) | .... |
Plan jest szeregowalny konfliktowo jeśli jest równoważny konfliktowo pewnemu planowi szeregowemu. Czy następujące plany są szeregowalne konfliktowo?
i.
T1: R(A), W(A), R(B),
W(B) T2: R(A), W(A), R(B), W(B) |
ii.
T1: R(A), W(A), R(B),
W(B) T2: R(A), W(A), R(B), W(B) |
iii.
T1: R(A),
W(A) T2: W(A) T3: W(A) |
4. Plany S1 i S2 są równoważne widokowo (ang. view serializable) jeśli:
Plan jest szeregowalny widokowo jeśli jest równoważny widokowo pewnemu planowi szeregowemu. Czy plany i., ii., iii. są szeregowalne widokowo?
5. Uzasadnij, że:
6. Zaprogramuj algorytm tworzenia dziennika powtórzeń.
7. Zaprogramuj algorytm wycofania nie zatwierdzonej transakcji w oparciu o dziennik powtórzeń.
8. Zaprogramuj algorytm punktu kontrolnego.
9. Zaprogramuj algorytm obliczania wartości w wierszu tabeli przyjmując poziom izolacji READ COMMITED łącznie z wielowersyjnością.