Rozproszony DBMS - kontrolowanie współbieżności
Techniki kontroli współbieżności zapewniają, że wiele transakcji jest wykonywanych jednocześnie, zachowując właściwości ACID transakcji i możliwość serializacji w harmonogramach.
W tym rozdziale przeanalizujemy różne podejścia do kontroli współbieżności.
Protokoły kontroli współbieżności oparte na blokowaniu
Protokoły kontroli współbieżności oparte na blokowaniu używają koncepcji blokowania elementów danych. ZAlockto zmienna powiązana z elementem danych, która określa, czy operacje odczytu / zapisu mogą być wykonywane na tym elemencie danych. Ogólnie używana jest macierz zgodności blokad, która określa, czy element danych może być zablokowany przez dwie transakcje w tym samym czasie.
Systemy kontroli współbieżności oparte na blokowaniu mogą używać protokołów blokowania jednofazowego lub dwufazowego.
Jednofazowy protokół blokowania
W tej metodzie każda transakcja blokuje przedmiot przed użyciem i zwalnia blokadę, gdy zakończy się jej używanie. Ta metoda blokowania zapewnia maksymalną współbieżność, ale nie zawsze wymusza możliwość serializacji.
Dwufazowy protokół blokowania
W tej metodzie wszystkie operacje blokowania poprzedzają pierwszą operację zwolnienia lub odblokowania blokady. Transakcja składa się z dwóch faz. W pierwszej fazie transakcja uzyskuje tylko wszystkie potrzebne blokady i nie zwalnia żadnej blokady. Nazywa się to rozszerzaniem lubgrowing phase. W drugiej fazie transakcja zwalnia blokady i nie może zażądać żadnych nowych blokad. Nazywa się toshrinking phase.
Gwarantuje się, że każda transakcja następująca po protokole blokowania dwufazowego będzie możliwa do serializacji. Jednak takie podejście zapewnia niski paralelizm między dwiema sprzecznymi transakcjami.
Algorytmy kontroli współbieżności znacznika czasu
Algorytmy kontroli współbieżności oparte na sygnaturach czasowych używają sygnatury czasowej transakcji do koordynowania równoczesnego dostępu do elementu danych w celu zapewnienia serializacji. Znacznik czasu to unikalny identyfikator nadawany przez DBMS transakcji, który reprezentuje czas rozpoczęcia transakcji.
Algorytmy te zapewniają, że transakcje są zatwierdzane w kolejności określonej przez ich znaczniki czasu. Starsza transakcja powinna zostać zatwierdzona przed młodszą transakcją, ponieważ starsza transakcja wchodzi do systemu przed młodszą.
Techniki kontroli współbieżności oparte na znacznikach czasowych generują harmonogramy z możliwością serializacji, tak że równoważny harmonogram szeregowy jest uporządkowany według wieku transakcji uczestniczących.
Niektóre z algorytmów kontroli współbieżności opartych na sygnaturach czasowych to:
- Podstawowy algorytm porządkowania znaczników czasu.
- Konserwatywny algorytm porządkowania znaczników czasu.
- Algorytm wielu wersji na podstawie kolejności sygnatur czasowych.
Porządkowanie oparte na sygnaturach czasowych jest zgodne z trzema regułami wymuszania serializacji -
Access Rule- Gdy dwie transakcje próbują uzyskać dostęp do tego samego elementu danych jednocześnie, w przypadku operacji powodujących konflikt priorytet ma starsza transakcja. Powoduje to, że młodsza transakcja czeka, aż starsza transakcja zostanie zatwierdzona jako pierwsza.
Late Transaction Rule- Jeśli młodsza transakcja zapisała pozycję danych, to starsza transakcja nie może odczytać ani zapisać tej pozycji danych. Ta reguła zapobiega zatwierdzeniu starszej transakcji po zatwierdzeniu młodszej transakcji.
Younger Transaction Rule - Młodsza transakcja może odczytywać lub zapisywać dane, które zostały już zapisane przez starszą transakcję.
Algorytm optymistycznej kontroli współbieżności
W systemach o niskim współczynniku konfliktów zadanie sprawdzania poprawności każdej transakcji pod kątem możliwości serializacji może obniżyć wydajność. W takich przypadkach test możliwości serializacji jest odkładany tuż przed zatwierdzeniem. Ponieważ współczynnik konfliktów jest niski, prawdopodobieństwo przerwania transakcji, których nie można serializować, jest również niskie. Takie podejście nazywa się optymistyczną techniką kontroli współbieżności.
W tym podejściu cykl życia transakcji jest podzielony na następujące trzy fazy -
Execution Phase - Transakcja pobiera elementy danych do pamięci i wykonuje na nich operacje.
Validation Phase - Transakcja sprawdza, czy zatwierdzanie zmian w bazie danych przechodzi test serializacji.
Commit Phase - Transakcja zapisuje z powrotem zmodyfikowane dane w pamięci na dysk.
Ten algorytm używa trzech reguł do wymuszania serializacji w fazie walidacji -
Rule 1- Biorąc pod uwagę dwie transakcje T i i T j , jeśli T i czyta element danych, który zapisuje T j , to faza wykonania T i nie może pokrywać się z fazą zatwierdzania T j . T j może zatwierdzić dopiero po zakończeniu wykonywania T i .
Rule 2- Biorąc pod uwagę dwie transakcje T i i T j , jeśli T i zapisuje element danych odczytywany przez T j , to faza zatwierdzania T i nie może pokrywać się z fazą wykonywania T j . T j może rozpocząć wykonywanie dopiero po zatwierdzeniu T i .
Rule 3- Biorąc pod uwagę dwie transakcje T i i T j , jeśli T i zapisuje element danych, który zapisuje również T j , to faza zatwierdzania T i nie może pokrywać się z fazą zatwierdzania T j . T j może rozpocząć zatwierdzanie dopiero po zatwierdzeniu przez T i .
Kontrola współbieżności w systemach rozproszonych
W tej sekcji zobaczymy, jak powyższe techniki są implementowane w systemie rozproszonych baz danych.
Rozproszony dwufazowy algorytm blokowania
Podstawowa zasada rozproszonego blokowania dwufazowego jest taka sama, jak podstawowy protokół blokowania dwufazowego. Jednak w systemie rozproszonym istnieją witryny wyznaczone jako menedżery blokad. Menedżer blokad kontroluje żądania przejęcia blokady z monitorów transakcji. Aby wymusić koordynację między menedżerami zamków w różnych lokalizacjach, przynajmniej jedna witryna ma uprawnienia do przeglądania wszystkich transakcji i wykrywania konfliktów blokad.
W zależności od liczby witryn, które mogą wykryć konflikty blokad, można podzielić rozproszone dwufazowe podejścia do blokowania:
Centralized two-phase locking- W tym podejściu jedna lokalizacja jest wyznaczona jako zarządca centralnej śluzy. Wszystkie lokalizacje w środowisku znają lokalizację zarządcy centralnego zamka i uzyskują od niego blokadę podczas transakcji.
Primary copy two-phase locking- W tym podejściu wiele miejsc wyznaczono jako centra kontroli śluz. Każda z tych witryn jest odpowiedzialna za zarządzanie określonym zestawem blokad. Wszystkie strony wiedzą, które centrum kontroli zamków jest odpowiedzialne za zarządzanie blokadą, której tabeli danych / elementu fragmentu.
Distributed two-phase locking- W tym podejściu istnieje kilka menedżerów blokad, w których każdy menedżer blokad kontroluje blokady elementów danych przechowywanych w jego lokalnej lokalizacji. Lokalizacja menedżera blokad zależy od dystrybucji i replikacji danych.
Rozproszona kontrola współbieżności znacznika czasu
W systemie scentralizowanym znacznik czasu dowolnej transakcji jest określany na podstawie fizycznego odczytu zegara. Jednak w systemie rozproszonym odczyty lokalnego zegara fizycznego / logicznego dowolnej witryny nie mogą być używane jako globalne znaczniki czasu, ponieważ nie są one globalnie unikalne. Tak więc sygnatura czasowa składa się z kombinacji identyfikatora witryny i odczytu zegara tej witryny.
W celu implementacji algorytmów porządkowania znaczników czasu każda witryna ma program planujący, który utrzymuje oddzielną kolejkę dla każdego menedżera transakcji. Podczas transakcji menedżer transakcji wysyła żądanie blokady do harmonogramu witryny. Program planujący umieszcza żądanie w odpowiedniej kolejce w rosnącej kolejności znaczników czasu. Żądania są przetwarzane od początku kolejek w kolejności ich znaczników czasu, tj. Od najstarszych do najstarszych.
Wykresy konfliktów
Inną metodą jest tworzenie wykresów konfliktów. Dla tej transakcji definiowane są klasy. Klasa transakcji zawiera dwa zestawy elementów danych zwane zestawem do odczytu i zestawem do zapisu. Transakcja należy do określonej klasy, jeśli zbiór odczytów transakcji jest podzbiorem zbioru odczytu klasy, a zbiór zapisu transakcji jest podzbiorem zbioru zapisu klasy. W fazie odczytu każda transakcja wysyła swoje żądania odczytu dla elementów danych w swoim zestawie do odczytu. W fazie zapisu każda transakcja wysyła swoje żądania zapisu.
Dla klas, do których należą aktywne transakcje, tworzony jest wykres konfliktu. Zawiera zestaw krawędzi pionowych, poziomych i ukośnych. Pionowa krawędź łączy dwa węzły w klasie i oznacza konflikty w klasie. Pozioma krawędź łączy dwa węzły w dwóch klasach i oznacza konflikt zapisu i zapisu między różnymi klasami. Ukośna krawędź łączy dwa węzły w dwóch klasach i oznacza konflikt zapisu i odczytu lub odczytu i zapisu między dwiema klasami.
Wykresy konfliktu są analizowane w celu ustalenia, czy dwie transakcje w tej samej klasie lub w dwóch różnych klasach mogą przebiegać równolegle.
Algorytm rozproszonej optymistycznej kontroli współbieżności
Rozproszony optymistyczny algorytm sterowania współbieżnością rozszerza optymistyczny algorytm sterowania współbieżnością. W przypadku tego rozszerzenia obowiązują dwie zasady -
Rule 1- Zgodnie z tą zasadą transakcja musi zostać zweryfikowana lokalnie we wszystkich witrynach podczas jej wykonywania. Jeśli okaże się, że transakcja jest nieprawidłowa w dowolnej witrynie, jest przerywana. Lokalna walidacja gwarantuje, że transakcja zachowuje możliwość serializacji w lokacjach, w których została wykonana. Po przejściu lokalnego testu walidacji transakcja jest weryfikowana globalnie.
Rule 2- Zgodnie z tą zasadą, gdy transakcja przejdzie lokalny test walidacji, powinna zostać zweryfikowana globalnie. Globalna walidacja zapewnia, że jeśli dwie sprzeczne transakcje są uruchamiane razem w więcej niż jednej lokalizacji, powinny one zatwierdzać w tej samej względnej kolejności we wszystkich witrynach, które razem obsługują. Może to wymagać, aby transakcja czekała na inną konfliktową transakcję, po sprawdzeniu poprawności przed zatwierdzeniem. To wymaganie sprawia, że algorytm jest mniej optymistyczny, ponieważ transakcja może nie być w stanie zatwierdzić, gdy tylko zostanie zweryfikowana w witrynie.