Harmonogramowanie i zarządzanie transakcjami

Plan

• Transakcje, odtwarzanie i kontrola współbieżności
• Transakcje i zarządzanie transakcjami
• Odtwarzanie
• Kontrola współbieżności
• Własności ACID transakcji

Transakcje, odtwarzanie i kontrola współbieżności

• Większość baz danych przeznaczonych dla wielu użytkowników (multi user databases)
• Równoczesny dostęp do tych samych danych może powodować anomalie
• Błędy mogą wystąpić w DBMS lub jego środowisku
• DBMS musi wspierać własności ACID (Atomicity, Consistency, Isolation, Durability)

Transakcje, odtwarzanie i kontrola współbieżności

• Transakcja to zbiór operacji bazy danych wywoływany przez użytkownika lub aplikację, traktowany jako jedna niepodzielna jednostka pracy (np. transfer między rachunkami bankowymi)
• Transakcja powinna zakończyć się sukcesem lub niepowodzeniem w całości
• Transakcja przenosi bazę danych ze stanu spójnego do innego stanu spójnego

Rodzaje błędów

• Awaria dysku twardego
• Awaria aplikacji/DBMS
• Dzielenie przez 0
• Inne błędy

Odtwarzanie

• działanie polegające na przywróceniu bazy danych do spójnego stanu po awarii bez utraty danych, niezależnie od źródła problemu
• Awaria transakcji z błędów logicznych
• Awaria systemu operacyjnego
• Awaria nośnika

Odtwarzanie systemu

• W przypadku awarii systemu występują dwa rodzaje transakcji: te, które osiągnęły zatwierdzenie i te, które są nadal aktywne.
• Plik dziennika jest niezbędny do uwzględnienia aktualizacji i śledzenia zmian, do odtworzenia stanu bazy danych przy użyciu operacji UNDO i REDO.
• Strategia opróżniania bufora bazy danych wpływa na operacje UNDO i REDO

Odtwarzanie systemu (graf)

• Punkt kontrolny (checkpoint) oznacza moment opróżnienia bufora przez menadżera bufora bazy danych na dysk.
• W przypadku awarii systemowej, operacje REDO i UNDO umożliwiają odtworzenie bazy danych do ostatniego punktu kontrolnego.

Odtwarzanie nośników

• Odzyskiwanie nośników opiera się na pewnym typie nadmiarowości danych
• Dwa rodzaje odzyskiwania nośników: mirroring dysku i archiwizacja
• Kompromis między kosztami utrzymania danych a czasem potrzebnym na przywrócenie systemu

Mirroring dysku

• podejście w czasie rzeczywistym, w którym dane są zapisywane na dwóch dyskach
• ograniczony czas przełączania awaryjnego, ale droższe niż archiwizacja
• negatywny wpływ na wydajność zapisu, ale możliwość równoległego dostępu do odczytu

Archiwizacja

• okresowe kopiowanie danych na inne nośniki (np. taśma, dysk twardy).
• kompromis między częstotliwością kopii zapasowych a kosztem utraty danych
• pełna lub przyrostowa kopia zapasowa

Kontrola współbieżności

• Typowe problemy z interferencją w współbieżności.
• Harmonogramy i harmonogramy seryjne
• Harmonogramy serializowalne
• Harmonogramy optymistyczne i pesymistyczne
• Blokowania i protokoły blokowania

Typowe problemy ze współbieżnością

• Scheduler odpowiada za planowanie wykonywania transakcji i ich operacji.
• Proste wykonanie seryjne byłoby bardzo nieefektywne.
• Scheduler zapewnia, że operacje transakcji mogą być wykonywane z przeplotem.
• Problem utraconej aktualizacji: udana aktualizacja danych przez transakcję jest nadpisywana przez inną transakcję, która nie była świadoma pierwszej aktualizacji.

Typowe problemy ze współbieżnością - kontynuacja

• Problem niezatwierdzonych zależności (uncommitted dependency problem/dirty read problem): Transakcja odczytuje dane, które są aktualizowane przez inną, wciąż niezatwierdzoną transakcję.
• Problem analizy niespójności (incosistent analysis problem): Transakcja odczytuje częściowe wyniki innej transakcji, która równolegle działa na tych samych danych.
• Niepowtarzalny odczyt (nonrepeatable read): Transakcja odczytuje ten sam wiersz wiele razy, ale uzyskuje różne wartości, ponieważ inna transakcja zaktualizowała ten wiersz w międzyczasie.
• Odczyt fantomów (phantom reads): Transakcja wykonuje operacje na wstawieniach lub usunięciach wierszy odczytanych przez inną transakcję.

Harmonogramy i harmonogramy szeregowe

• Definiowanie harmonogramu S jako zbioru n transakcji i sekwencyjne uporządkowanie instrukcji tych transakcji. Własność: instrukcja s₁ poprzedzająca s₂ w T musi nastąpić przed s₂ w S.

Harmonogramy szeregowalne

• Harmonogram S jest szeregowy, jeżeli wszystkie instrukcje samej transakcji T są zaplanowane kolejno bez przeplotu z instrukcjami z innej transakcji. Szeregowe harmonogramy uniemożliwiają równoległe wykonywanie transakcji. Potrzeba nieszeregowych poprawnych harmonogramów.

Harmonogramy szeregowalne (graf pierwszeństwa)

• Graf pierwszeństwa do testowania harmonogramu pod kątem szeregowalności: węzły dla transakcji, krawędzie (T1 → T2) jeśli T2 odczytuje/zapisuje po zapisaniu przez T1. Cykl w grafie oznacza nieszeregowalność.

Harmonogramy optymistyczne i pesymistyczne

• Scheduler wykorzystuje protokół harmonogramowania. Protokoły: optymistyczny i pesymistyczny.
• Protokuł optymistyczny: konflikty rzadkie, operacje transakcji planowane bez opóźnień, weryfikacja konfliktów po zakończeniu transakcji.
• Protokuł pesymistyczny: konflikty prawdopodobne, operacje opóźnione do czasu możliwej kompatybilności

Blokowanie i protokoły blokowania

• Cele blokowania, Two-Phase Locking Protocol (2PL), Kaskadowe wycofywania (Cascading Rollbacks), Radzenie sobie z zakleszczeniami (Deadlocks), Poziomy izolacji, Ziarnistość blokad
• Blokada na wyłączność (x-lock) i współdzielona (s-lock). Macierz kompatybilności

Protokół dwufazowego blokowania (2PL)

• Protokół 2PL: faza wzrostu (uzyskiwanie blokad), faza zmniejszania (zwalnianie blokad). Rygorystyczny i Statyczny 2PL

Protokół dwufazowego blokowania (2PL) - problemy

• Problem utraconej aktualizacji i niezatwierdzonych zależności z blokowaniem. Ilustracja z przykładami i tabelami przedstawiające problem.

Kaskadowe wycofywania

• Problemy z niezatwierdzonymi zależnościami.
• Algorytmy radzenia sobie z nimi w protokole 2PL

Radzenie sobie z zakleszczeniami

• Zapobieganie zakleszczeniom za pomocą statycznego 2PL.
• Wykrywanie i rozwiązywanie zakleszczeń (graf oczekiwań).

Poziomy izolacji

• Niezatwierdzony odczyt (Read uncommited)
• Odczyt zatwierdzonych danych (Read committed)
• Powtarzalne odczyty (Repeatable read)
• Serializowalny (Serializable)
• Tabela porównawcza poziomów izolacji

Ziarnistość blokad

• Wielkość blokowanych obiektów (krotka, kolumna, tabela), kompromis między kosztem blokowania a wydajnością transakcji w wielu DBMS. Protokół wielokrotnej ziarnistości (MGL)

Ziarnistość blokad (kontynuacja)

• Protokół MGL wprowadza dodatkowe blokady intencyjne (is-lock, ix-lock, itd) dla skoordynowanego dostępu do różnych poziomów ziarnistości. Tabela kompatybilności dla MGL.

Własności ACID transakcji

• Atomicity (atomowość), Consistency (spójność, utrzymanie spójnego stanu bazy danych), Isolation (izolacja, oddzielność transakcji), Durability (trwałość, wynik transakcji na stałe w bazie danych).