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ć zapisanie zmian (zatwierdzenie) lub anulowanie zmian (wycofanie). W przypadku bazy danych transakcja składa się z kilku żądań, które są traktowane jako jedno żądanie.
Transakcje muszą spełniać właściwości ACID
Atomowość. Transakcja zostaje albo zrealizowana całkowicie, albo wcale.
Konsystencja. Podczas realizacji transakcji nie wolno naruszać ograniczeń nałożonych na dane (na przykład ograniczeń w bazie danych). Spójność oznacza, że system zostanie przeniesiony z jednego prawidłowego stanu do innego prawidłowego stanu.
Izolacja. Transakcje przebiegające równolegle nie powinny na siebie wpływać, np. zmieniać danych wykorzystywanych przez inną transakcję. Wynik realizacji transakcji równoległych powinien być taki sam jak w przypadku realizacji transakcji sekwencyjnie.
Zrównoważony rozwój. Raz zatwierdzone zmiany nie powinny zostać utracone.
Dziennik transakcji
Dziennik przechowuje zmiany dokonane w transakcjach, zapewnia niepodzielność i stabilność danych w przypadku awarii systemu
Log zawiera wartości jakie miały dane przed i po zmianie w wyniku transakcji. Strategia zapisu z wyprzedzeniem polega na dodaniu wpisu do dziennika o wartościach poprzednich przed rozpoczęciem oraz o wartościach końcowych po zakończeniu transakcji. W przypadku nagłego zatrzymania systemu baza danych odczytuje logi w odwrotnej kolejności i anuluje zmiany dokonane transakcjami. Baza danych po napotkaniu przerwanej transakcji wykonuje ją i wprowadza zmiany do protokołu. Będąc w stanie z chwili wystąpienia awarii, baza danych odczytuje log w kolejności forwardowania i zwraca zmiany dokonane przez transakcje. W ten sposób zachowana jest stabilność transakcji, które zostały już zatwierdzone, oraz atomowość przerwanej transakcji.
Samo ponowne wykonanie nieudanych transakcji nie wystarczy do odzyskania danych.
Przykład. Użytkownik ma na swoim koncie 500 dolarów i decyduje się wypłacić je z bankomatu. Dwie transakcje są w toku. Pierwszy odczytuje wartość salda i jeśli na saldzie jest wystarczająca ilość środków, wydaje pieniądze użytkownikowi. Drugi odejmuje wymaganą kwotę od salda. Załóżmy, że system się zawiesił i pierwsza operacja nie powiodła się, ale druga tak. W takim przypadku nie możemy ponownie wydać pieniędzy użytkownikowi bez przywrócenia systemu do pierwotnego stanu z dodatnim saldem.
Poziomy izolacji
Przeczytaj Zaangażowany
Problem Dirty Read polega na tym, że transakcja może odczytać pośredni wynik innej transakcji.
Przykład. Początkowa wartość salda wynosi 0 USD. T1 dodaje 50 $ do Twojego salda. T2 odczytuje wartość salda (50 USD). T1 odrzuca zmiany i wychodzi. T2 kontynuuje wykonywanie z nieprawidłowymi danymi salda.
Rozwiązaniem jest odczyt danych stałych (Read Committed), co uniemożliwia odczyt danych zmienionych transakcją. Jeżeli transakcja A zmieniła określony zestaw danych, wówczas transakcja B uzyskując dostęp do tych danych zmuszona jest czekać na zakończenie transakcji A.
Powtarzalny odczyt
Problem z utraconymi aktualizacjami. T1 zapisuje zmiany oprócz zmian T2.
Przykład. Początkowa wartość salda wynosi 0 USD, a dwie transakcje jednocześnie uzupełniają saldo. T1 i T2 odczytują saldo 0 USD. Następnie T2 dodaje 200 USD do 0 USD i zapisuje wynik. T1 dodaje 100 $ do 0 $ i zapisuje wynik. Ostateczny wynik to 100 dolarów zamiast 300 dolarów.
Niepowtarzalny problem z odczytem. Wielokrotne czytanie tych samych danych zwraca różne wartości.
Przykład. T1 odczytuje wartość salda wynoszącą 0 USD. Następnie T2 dodaje 50 dolarów do salda i kończy się. T1 ponownie odczytuje dane i stwierdza rozbieżność z poprzednim wynikiem.
Odczyt powtarzalny gwarantuje, że drugi odczyt zwróci ten sam wynik. Dane odczytane przez jedną transakcję nie mogą zostać zmienione w innych do czasu zakończenia transakcji. Jeśli transakcja A odczytała określony zestaw danych, wówczas transakcja B uzyskując dostęp do tych danych zmuszona jest czekać na zakończenie transakcji A.
Uporządkowany odczyt (możliwość serializacji)
Problem z odczytem Phantom. Dwa zapytania, które wybierają dane na podstawie określonego warunku, zwracają różne wartości.
Przykład. T1 żąda liczby wszystkich użytkowników, których saldo jest większe niż 0 USD, ale mniejsze niż 100 USD. T2 odejmuje 1 dolara od użytkownika, którego saldo wynosi 101 dolarów. T1 ponownie wysyła żądanie.
Uporządkowany odczyt (możliwość serializacji). Transakcje realizowane są w sposób całkowicie sekwencyjny. Zabrania się aktualizacji lub dodawania rekordów objętych warunkami żądania. Jeśli transakcja A zażądała danych z całej tabeli, wówczas cała tabela zostanie zablokowana dla innych transakcji do czasu zakończenia transakcji A.
Planista
Ustawia kolejność wykonywania operacji podczas transakcji równoległych.
Zapewnia określony poziom izolacji. Jeśli wynik operacji nie zależy od ich kolejności, to są to operacje przemienne (Permutable). Operacje odczytu i operacje na różnych danych są przemienne. Operacje odczyt-zapis i zapis-zapis nie są przemienne. Zadaniem planisty jest przeplatanie operacji wykonywanych przez transakcje równoległe tak, aby wynik wykonania był równoważny z sekwencyjną realizacją transakcji.
Mechanizmy kontroli zadań równoległych (Kontrola współbieżności)
Optymizm opiera się na wykrywaniu i rozwiązywaniu konfliktów, pesymizm opiera się na zapobieganiu powstawaniu konfliktów.
W podejściu optymistycznym kopie danych ma do dyspozycji wielu użytkowników. Pierwsza osoba, która zakończy edycję, zapisuje zmiany, pozostali muszą scalić zmiany. Algorytm optymistyczny pozwala na wystąpienie konfliktu, ale system musi wyjść z konfliktu.
W podejściu pesymistycznym pierwszy użytkownik, który przechwyci dane, uniemożliwia innym otrzymanie danych. Jeśli konflikty są rzadkie, mądrze jest wybrać strategię optymistyczną, ponieważ zapewnia ona wyższy poziom współbieżności.
Zamykający
Jeśli jedna transakcja ma zablokowane dane, inne transakcje muszą poczekać, aż zostaną odblokowane podczas uzyskiwania dostępu do danych.
Blok można nałożyć na bazę danych, tabelę, wiersz lub atrybut. Shared Lock może zostać nałożony na te same dane przez kilka transakcji, umożliwia odczyt wszystkich transakcji (w tym tej, która je nałożyła), zabrania modyfikacji i wyłącznego przechwytywania. Ekskluzywna Blokada może zostać nałożona tylko przez jedną transakcję, pozwala na dowolne działania transakcji nakładającej, zabrania jakichkolwiek działań innym.
Zakleszczenie to sytuacja, w której transakcje znajdują się w stanie oczekującym, który trwa przez czas nieokreślony.
Przykład. Pierwsza transakcja czeka na uwolnienie danych przechwyconych przez drugą, druga zaś na uwolnienie danych przechwyconych przez pierwszą.
Optymistyczne rozwiązanie problemu zakleszczenia pozwala na wystąpienie zakleszczenia, ale następnie przywraca system poprzez wycofywanie jednej z transakcji objętych zakleszczeniem.
Zakleszczenia są wyszukiwane w określonych odstępach czasu. Jedną z metod wykrywania jest badanie czasowe, co oznacza uwzględnienie zakleszczenia, jeśli realizacja transakcji trwa zbyt długo. W przypadku wykrycia zakleszczenia jedna z transakcji jest wycofywana, umożliwiając zakończenie innych transakcji objętych zakleszczeniem. Wybór ofiary może opierać się na wartości transakcji lub ich stażu pracy (schematy Czekaj-Die i Rana-czekaj).
Każda transakcja T przypisany jest znacznik czasu TS zawierający godzinę rozpoczęcia transakcji.
Poczekaj-umrzyj.
jeśli TS(Ti) < TS(Tj)następnie Ti czeka, inaczej Ti cofa się i zaczyna od nowa z tym samym znacznikiem czasu.
Jeśli młoda transakcja pozyskała zasób, a starsza transakcja żąda tego samego zasobu, wówczas starsza transakcja może poczekać. Jeśli starsza transakcja nabyła zasób, wówczas młodsza transakcja żądająca tego zasobu zostanie wycofana.
Rany-poczekaj.
jeśli TS(Ti) < TS(Tj)następnie Tj w przeciwnym razie cofa się i zaczyna od nowa z tym samym znacznikiem czasu Ti Czekanie.
Jeśli młodsza transakcja nabyła zasób, a starsza transakcja zażąda tego samego zasobu, wówczas młodsza transakcja zostanie wycofana. Jeśli starsza transakcja pozyskała zasób, wówczas młodsza transakcja żądająca tego zasobu może poczekać. Wybór ofiar na podstawie pierwszeństwa zapobiega zakleszczeniom, ale wycofuje transakcje, które nie są zablokowane. Problem polega na tym, że transakcje można wycofywać wiele razy, ponieważ... starsza transakcja może przechowywać zasób przez długi czas.
Pesymistyczne rozwiązanie problemu zakleszczenia nie pozwala na rozpoczęcie wykonywania transakcji, jeśli istnieje ryzyko zakleszczenia.
W celu wykrycia zakleszczenia tworzony jest graf (wykres oczekiwania, wykres oczekiwania na), którego wierzchołkami są transakcje, a krawędzie kierują od transakcji oczekujących na uwolnienie danych do transakcji, która te dane przechwyciła. Uważa się, że zakleszczenie wystąpiło, jeśli na wykresie znajduje się pętla. Konstruowanie grafu oczekiwania, szczególnie w rozproszonych bazach danych, jest kosztowną procedurą.
Blokowanie dwufazowe - zapobiega zakleszczeniom poprzez przejęcie wszystkich zasobów wykorzystywanych przez transakcję na początku transakcji i zwolnienie ich na końcu
Wszystkie operacje blokujące muszą poprzedzać pierwszą operację odblokowania. Ma dwie fazy – fazę wzrostu, podczas której gromadzą się uchwyty, i fazę kurczenia się, podczas której uchwyty są uwalniane. Jeśli przejęcie jednego z zasobów nie jest możliwe, transakcja rozpoczyna się od nowa. Może się zdarzyć, że w ramach transakcji nie uda się pozyskać wymaganych zasobów, np. jeśli kilka transakcji konkuruje o te same zasoby.
Zatwierdzenie dwufazowe gwarantuje, że zatwierdzenie zostanie wykonane na wszystkich replikach bazy danych
Każda baza danych wprowadza do logu informację o danych, które zostaną zmienione i odpowiada koordynatorowi OK (Faza Głosowania). Gdy wszyscy odpowiedzą OK, koordynator wysyła sygnał zobowiązujący wszystkich do zaangażowania się. Po zatwierdzeniu serwery odpowiadają OK; jeśli przynajmniej jeden nie odpowie OK, koordynator wysyła sygnał o anulowaniu zmian do wszystkich serwerów (faza zakończenia).
Metoda znacznika czasu
Starsza transakcja jest wycofywana przy próbie dostępu do danych związanych z młodszą transakcją
Każdej transakcji przypisany jest znacznik czasu TS odpowiadający godzinie rozpoczęcia realizacji. Jeśli Ti ponad Tjnastępnie TS(Ti) < TS(Tj).
Wycofywanie transakcji powoduje przypisanie jej nowego znacznika czasu. Każdy obiekt danych Q zaangażowani w transakcję są oznaczeni dwiema etykietami. W-TS(Q) — znacznik czasu najmłodszej transakcji, która pomyślnie zakończyła zapis Q. R-TS(Q) — znacznik czasu najmłodszej transakcji, dla której dokonano odczytu zapisu Q.
Kiedy transakcja T żądania odczytu danych Q możliwe są dwie opcje.
jeśli TS(T) < W-TS(Q), czyli dane zostały zaktualizowane przez młodszą transakcję, a następnie transakcję T odwraca się.
jeśli TS(T) >= W-TS(Q), następnie następuje odczyt i R-TS(Q) staje się MAX(R-TS(Q), TS(T)).
Kiedy transakcja T żąda zmiany danych Q możliwe są dwie opcje.
jeśli TS(T) < R-TS(Q), czyli dane zostały już odczytane przez młodszą transakcję i w przypadku wprowadzenia zmiany powstanie konflikt. Transakcja T odwraca się.
jeśli TS(T) < W-TS(Q), czyli transakcja próbuje nadpisać nowszą wartość, transakcja T jest wycofywana. W pozostałych przypadkach zmiana jest przeprowadzana i W-TS(Q) staje się równy TS(T).
Nie jest wymagana kosztowna konstrukcja wykresu oczekiwania. Starsze transakcje zależą od nowszych, więc na wykresie oczekiwania nie ma cykli. Nie ma zakleszczeń, ponieważ transakcje nie są czekane, lecz natychmiastowo wycofywane. Możliwe jest kaskadowe wycofywanie zmian. Jeśli Ti przetoczył się i Tj Odczytałem dane, które zmieniłem Tinastępnie Tj powinien również się wycofać. Jeśli jednocześnie Tj zostało już popełnione, wówczas nastąpi naruszenie zasady stabilności.
Jedno z rozwiązań kaskadowego wycofywania zmian. Transakcja kończy wszystkie operacje zapisu na końcu, a inne transakcje muszą poczekać na zakończenie tej operacji. Transakcje czekają na zatwierdzenie przed odczytaniem.
Reguła zapisu Thomasa - odmiana metody znacznika czasu, w której dane aktualizowane przez młodszą transakcję nie mogą zostać nadpisane przez starszą
transakcja T żąda zmiany danych Q. Jeśli TS(T) < W-TS(Q), czyli transakcja próbuje nadpisać nowszą wartość, transakcja T nie jest cofana jak w metodzie znacznika czasu.
Źródło: www.habr.com