Transakcje
Transakcja to sekwencja operacji na danych, która ma początek i koniec.
Transakcja to sekwencyjne wykonywanie operacji odczytu i zapisu. Zakończeniem transakcji może być albo zapisanie zmian (commit), albo ich anulowanie (rollback). W kontekście baz danych transakcja to kilka zapytań, które są traktowane jako jedno zapytanie.
Transakcje muszą spełniać właściwości ACID.
Atomowość. Transakcja jest albo w pełni realizowana, albo w ogóle nie jest realizowana.
Spójność. Po zakończeniu transakcji ograniczenia nakładane na dane (np. constraints w bazach danych) nie mogą być naruszone. Spójność oznacza, że system zostanie przeniesiony z jednego poprawnego stanu do drugiego.
Izolacja. Równolegle wykonywane transakcje nie powinny wpływać na siebie nawzajem, na przykład zmieniać danych, których używa inna transakcja. Wynik wykonania równoległych transakcji powinien być taki, jakby transakcje były wykonywane sekwencyjnie.
Trwałość. Po zatwierdzeniu zmiany nie mogą zostać utracone.
Dziennik transakcji.
Dziennik przechowuje zmiany dokonane przez transakcje, zapewniając atomowość i trwałość danych w przypadku awarii systemu.
Dziennik zawiera wartości, jakie dane miały przed i po ich zmianach dokonanych przez transakcje. Strategia write-ahead log wymaga dodania do dziennika zapisu o wcześniejszych wartościach przed rozpoczęciem a o końcowych po zakończeniu transakcji. W przypadku nagłego zatrzymania systemu, baza danych odczytuje log w odwrotnej kolejności i cofa zmiany dokonane przez transakcje. Spotykając przerwaną transakcję, baza danych wykonuje ją i wprowadza jej zmiany do dziennika. W momencie awarii, baza danych odczytuje log w prostej kolejności i przywraca zmiany dokonane przez transakcje. W ten sposób utrzymuje się trwałość transakcji, które już zostały zatwierdzone, oraz atomowość przerwanej transakcji.
Proste ponowne wykonanie błędnych transakcji nie jest wystarczające do przywrócenia stanu.
Przykład. Na koncie użytkownika jest 500$, a użytkownik postanawia je wypłacić przez bankomat. Wykonywane są dwie transakcje. Pierwsza odczytuje wartość salda, a jeśli na koncie jest wystarczająca ilość środków, wydaje pieniądze użytkownikowi. Druga odejmuje potrzebną kwotę z salda. Załóżmy, że wystąpił błąd systemu i pierwsza operacja się nie powiodła, a druga się powiodła. W takim przypadku nie możemy ponownie wydać pieniędzy użytkownikowi bez przywrócenia systemu do początkowego stanu z dodatnim saldem.
Poziomy izolacji
Odczyt zatwierdzonych danych (Read Committed)
Problem brudnego odczytu (Dirty Read) polega na tym, że transakcja może odczytać pośredni wynik działania innej transakcji.
Przykład. Początkowe saldo wynosi 0$. T1 dodaje 50$ do salda. T2 odczytuje wartość salda (50$). T1 odrzuca zmiany i kończy się. T2 kontynuuje wykonanie, dysponując nieprawidłowymi danymi o saldzie.
Rozwiązaniem jest odczyt zatwierdzonych danych (Read Committed), który zabrania odczytu danych zmienionych przez transakcję. Jeśli transakcja A zmieniła pewien zestaw danych, to transakcja B, przy próbie uzyskania tych danych, musi czekać na zakończenie transakcji A.
Powtarzalny odczyt (Repeatable Read)
Problem utraconych aktualizacji (Lost Updates). T1 zapisuje zmiany na wierzchu zmian T2.
Przykład. Początkowe saldo wynosi 0$ i dwie transakcje jednocześnie zwiększają saldo. T1 i T2 odczytują saldo równe 0$. Następnie T2 dodaje 200$ do 0$ i zapisuje wynik. T1 dodaje 100$ do 0$ i zapisuje wynik. Ostateczny wynik wynosi 100$ zamiast 300$.
Problem niepowtarzalnego odczytu (Unrepeatable read). Powtórny odczyt tych samych danych zwraca różne wartości.
Przykład. T1 odczytuje wartość salda równą 0$. Następnie T2 dodaje 50$ do salda i kończy się. T1 ponownie odczytuje dane i stwierdza niezgodność z poprzednim wynikiem.
Powtarzalny odczyt (Repeatable Read) gwarantuje, że powtórny odczyt zwróci ten sam wynik. Dane odczytane przez jedną transakcję nie mogą być zmieniane w innych do zakończenia transakcji. Jeśli transakcja A odczytała pewien zestaw danych, to transakcja B, przy próbie uzyskania tych danych, musi czekać na zakończenie transakcji A.
Uszeregowany odczyt (Serializable)
Problem fantomowego odczytu (Phantom Reads). Dwa zapytania wybierające dane na podstawie pewnego warunku zwracają różne wartości.
Przykład. T1 pyta o liczbę wszystkich użytkowników, których saldo jest większe niż 0$ lecz mniejsze niż 100$. T2 odejmuje 1$ od użytkownika z saldem 101$. T1 wykonuje zapytanie ponownie.
Uporządkowane odczyty (Serializable). Transakcje są wykonywane w pełni sekwencyjnie. Zabronione jest aktualizowanie lub dodawanie rekordów, które podlegają warunkom zapytania. Jeśli transakcja A pyta o dane całej tabeli, tabela jest w całości zamrażana dla pozostałych transakcji do momentu zakończenia transakcji A.
Planista (Scheduler)
Ustala kolejność, w jakiej powinny być wykonywane operacje w przypadku równolegle przebiegających transakcji.
Zapewnia zadany poziom izolacji. Jeśli wynik operacji nie zależy od ich kolejności, to takie operacje są przemienne (Permutable). Przemienne są operacje odczytu oraz operacje na różnych danych. Operacje odczytu-zapisu i zapisu-zapisu nie są przemienne. Zadaniem planisty jest naprzemiennie układać operacje wykonywane przez równoległe transakcje, tak aby wynik ich wykonania był równoważny sekwencyjnemu wykonaniu transakcji.
Mechanizmy kontroli równoległych zadań (Concurrency Control)
Optymistyczny, oparty na wykrywaniu i rozwiązywaniu konfliktów, pesymistyczny na zapobieganiu powstawaniu konfliktów.
W podejściu optymistycznym kilku użytkowników ma dostęp do kopii danych. Pierwszy, który zakończy edycję, zapisuje zmiany, pozostali muszą zrealizować scalanie zmian. Algorytm optymistyczny dopuszcza wystąpienie konfliktu, ale system musi się odbudować po konflikcie.
W podejściu pesymistycznym pierwszy użytkownik, który zablokował dane, uniemożliwia pozostałym dostęp do tych danych. Jeśli konflikty są rzadkie, rozsądniej jest wybrać strategię optymistyczną, ponieważ zapewnia ona wyższy poziom równoległości.
Blokada (Locking)
Jeśli jedna transakcja zablokowała dane, inne transakcje przy próbie dostępu do danych muszą czekać na odblokowanie.
Blok może być nałożony na bazę danych, tabelę, rząd lub atrybut. Wspólny zamek (Shared Lock) może być nałożony na te same dane przez kilka transakcji, pozwala wszystkim transakcjom (w tym nakładającej) na odczyt, zabrania modyfikacji i zablokowania wyłącznie. Zamek wyłączny (Exclusive Lock) może być nałożony tylko przez jedną transakcję, pozwala na wszystkie działania nakładającej transakcji, zabrania wszelkich działań innym.
Martwym blokowaniem nazywa się sytuację, w której transakcje znajdują się w trybie oczekiwania, który trwa w nieskończoność.
Przykład. Pierwsza transakcja czeka na zwolnienie danych zablokowanych przez drugą, podczas gdy druga czeka na zwolnienie danych zablokowanych przez pierwszą.
Optymistyczne rozwiązanie problemu deadlocków pozwala na wystąpienie deadlocku, ale następnie przywraca system, wycofując jedną z transakcji zaangażowanych w deadlock.
W określonych odstępach czasu przeprowadzana jest analiza deadlocków. Jednym ze sposobów wykrywania jest analiza czasu, tzn. uważa się, że wystąpił deadlock, jeśli transakcja trwa zbyt długo. Gdy deadlock zostanie znaleziony, jedna z transakcji jest wycofywana, co pozwala innym transakcjom zaangażowanym w deadlock na zakończenie. Wybór ofiary może być oparty na kosztach transakcji lub ich starszeństwie (schematy Wait-Die i Wound-wait).
Każdej transakcji T przypisywana jest znacznik czasowy TS zawierający czas rozpoczęcia wykonywania transakcji.
Wait-Die.
Jeśli TS(Ti) < TS(Tj), to Ti czeka, w przeciwnym razie Ti jest wycofywana i rozpoczyna się od nowa z tym samym znacznikiem czasowym.
Jeśli młodsza transakcja zdobyła zasób, a starsza prosi o ten sam zasób, to starszej transakcji zezwala się na czekanie. Jeśli starsza transakcja zdobyła zasób, młodsza transakcja, która prosi o ten zasób, zostanie wycofana.
Wound-wait.
Jeśli TS(Ti) < TS(Tj), to Tj jest wycofywana i rozpoczyna się od nowa z tym samym znacznikiem czasowym, w przeciwnym razie Ti czeka.
Jeśli młodsza transakcja zajmie zasób, a starsza transakcja spróbuje uzyskać ten sam zasób, młodsza transakcja zostanie wycofana. Jeśli starsza transakcja zajmie zasób, młodsza transakcja, która próbuje uzyskać dany zasób, może czekać. Wybór ofiary na podstawie starości zapobiega wystąpieniu zakleszczenia, ale wycofuje transakcje, które nie są w stanie zakleszczenia. Problem polega na tym, że transakcje mogą być wycofywane wiele razy, ponieważ starsza transakcja może długo utrzymywać zasób.
Pesymistyczne rozwiązanie problemu zakleszczeń nie pozwala na rozpoczęcie wykonania transakcji, jeśli istnieje ryzyko wystąpienia zakleszczenia.
Aby wykryć zakleszczenie, buduje się graf (graf oczekiwania, wait-for-graph), w którym węzły to transakcje, a krawędzie są skierowane od transakcji oczekujących na zwolnienie danych do transakcji, które te dane zajęły. Zakłada się, że zakleszczenie miało miejsce, jeśli graf zawiera cykl. Budowanie grafu oczekiwania, szczególnie w rozproszonych bazach danych, to kosztowna procedura.
Dwufazowe blokowanie — zapobieganie zakleszczeniom poprzez zajęcie wszystkich zasobów wykorzystywanych przez transakcję na początku transakcji i ich zwolnienie na końcu.
Wszystkie operacje blokujące muszą poprzedzać pierwszą operację zwalniającą. Ma dwie fazy — Faza Rosnąca, w której następuje kumulacja zajęć i Faza Kurcząca, w której dochodzi do zwolnienia zajęć. W przypadku niemożności zajęcia jednego z zasobów transakcja rozpoczyna się od nowa. Może wystąpić sytuacja, w której transakcja nie będzie mogła zająć wymaganych zasobów, na przykład jeśli kilka transakcji będzie konkurować o te same zasoby.
Dwufazowe potwierdzenie zapewnia wykonanie zatwierdzenia na wszystkich replikach bazy danych.
Każda baza danych wprowadza informacje o danych, które będą zmienione, do dziennika i odpowiada koordynatorowi OK (Faza Głosowania). Po tym, jak wszyscy odpowiedzą na OK, koordynator wysyła sygnał zobowiązujący wszystkich do dokonania zatwierdzenia. Po zatwierdzeniu serwera wszyscy odpowiadają OK, jeśli choć jeden nie odpowiada OK, to koordynator wysyła sygnał anulowania zmian do wszystkich serwerów (Faza Zakończenia).
Metoda znaczników czasowych
Starsza transakcja jest wycofywana w przypadku próby dostępu do danych zajętych przez młodszą transakcję.
Każdej transakcji przypisywany jest znacznik czasowy TS odpowiadający momentowi rozpoczęcia jej wykonania. Jeśli Ti jest starszy Tj, to TS(Ti) < TS(Tj).
Kiedy transakcja jest wycofywana, otrzymuje nowy znacznik czasowy. Każdy obiekt danych Q związany z transakcją oznaczany jest dwoma znacznikami. W-TS(Q) — znacznik czasowy najnowszej transakcji, która pomyślnie dokonała zapisu nad Q. R-TS(Q) — znacznik czasowy najnowszej transakcji, która dokonała zapisu odczytu nad Q.
Kiedy transakcja T żąda odczytu danych Q są dwa scenariusze.
Jeśli TS(T) < W-TS(Q), to znaczy, że dane zostały zaktualizowane przez młodsza transakcję, wówczas transakcja T jest wycofywana.
Jeśli TS(T) >= W-TS(Q), to odczyt jest wykonywany i R-TS(Q) staje się MAX(R-TS(Q), TS(T)).
Kiedy transakcja T żąda zmiany danych Q są dwa scenariusze.
Jeśli TS(T) < R-TS(Q), to znaczy, że dane zostały już odczytane przez młodszą transakcję i jeśli zostanie dokonana zmiana, to wystąpi konflikt. Transakcja T jest wycofywana.
Jeśli TS(T) < W-TS(Q), to znaczy, że transakcja próbuje nadpisać nowszą wartość, transakcja T jest wycofywana. W pozostałych przypadkach zmiana jest dokonywana i W-TS(Q) staje się równa TS(T).
Nie ma potrzeby kosztownego budowania grafu oczekiwania. Starsze transakcje zależą od nowszych, co oznacza, że w grafie oczekiwania nie ma cykli. Nie występują martwe blokady, ponieważ transakcje nie czekają, a od razu są wycofywane. Możliwe są kaskadowe wycofania. Jeżeli Ti została wycofana, a Tj odczytała dane, które zmieniła Ti, to Tj też musi zostać wycofana. Jeśli przy tym Tj już została zatwierdzona, to dojdzie do naruszenia zasady trwałości.
Jednym z rozwiązań kaskadowych wycofań. Transakcja wykonuje wszystkie operacje zapisu na końcu, a pozostałe transakcje muszą czekać na zakończenie tej operacji. Transakcje oczekują na zatwierdzenie przed odczytem.
Reguła pisania Thomasa — odmiana metody znaczników czasowych, w której dane zaktualizowane przez młodszą transakcję nie mogą być nadpisywane przez starszą
Transakcja T żąda zmiany danych Q. Jeśli TS(T) < W-TS(Q), to znaczy, że transakcja próbuje nadpisać nowszą wartość, transakcja T nie jest wycofywana jak w metodzie znaczników czasowych.
Źródło: habr.com
