Kontrola współbieżności DBMS: protokoły oparte na blokadach i znacznikach czasu

Co to jest kontrola współbieżności?

Nadzór konkurencji W systemie zarządzania bazą danych procedura zarządzania operacjami równoległymi bez powodowania konfliktów między nimi. Zapewnia ona, że ​​transakcje w bazie danych są wykonywane współbieżnie i dokładnie, generując poprawne wyniki bez naruszania integralności danych w danej bazie danych.

Dostęp współbieżny jest dość łatwy, jeśli wszyscy użytkownicy tylko odczytują dane, ponieważ nie ma możliwości, aby mogli sobie nawzajem przeszkadzać. Jednak każda praktyczna baza danych zawiera kombinację operacji ODCZYTU i ZAPISU, co sprawia, że ​​współbieżność staje się wyzwaniem.

Kontrola współbieżności w systemie DBMS służy do rozwiązywania takich konfliktów, które najczęściej występują w systemach wielodostępnych. Kontrola współbieżności jest zatem jednym z najważniejszych elementów prawidłowego funkcjonowania bazy danych, w której dwie lub więcej transakcji jest wykonywanych jednocześnie i wymaga dostępu do tych samych danych. Działa ona ściśle z zarządzanie transakcjami, który definiuje jednostki pracy, które kontrola współbieżności musi bezpiecznie przeplatać.

Potencjalne problemy współbieżności

Oto kilka problemów, z którymi możesz się spotkać, jeśli nie będziesz mieć odpowiedniej kontroli współbieżności DBMS:

• Utracone aktualizacje występuje, gdy wiele transakcji wybiera ten sam wiersz i aktualizuje go na podstawie wybranej wartości.
• Niezatwierdzona zależność (brudny odczyt) występuje, gdy druga transakcja wybiera wiersz, który został zaktualizowany przez inną transakcję, która nie została jeszcze zatwierdzona.
• Odczyt niepowtarzalny występuje, gdy druga transakcja uzyskuje dostęp do tego samego wiersza kilkakrotnie i za każdym razem odczytuje inne dane.
• Nieprawidłowe podsumowanie Występuje, gdy jedna transakcja podsumowuje wartość wszystkich wystąpień powtarzającego się elementu danych, podczas gdy druga transakcja aktualizuje kilka z tych wystąpień. Otrzymane podsumowanie nie odzwierciedla prawidłowego wyniku.

Dlaczego warto stosować metodę współbieżności?

Powody stosowania metody kontroli współbieżności w systemach DBMS:

• Zastosowanie izolacji poprzez wzajemne wykluczanie pomiędzy sprzecznymi transakcjami.
• Aby rozwiązać problemy związane z konfliktami odczytu i zapisu oraz zapisu i zapisu.
• Aby zachować spójność bazy danych poprzez ciągłe egzekwowanie ograniczeń wykonywania.
• Kontrolowanie interakcji pomiędzy współbieżnymi transakcjami, realizowane przy użyciu schematów kontroli współbieżności.
• Aby pomóc zapewnić możliwość serializacji.

Przykład

Załóżmy, że dwie osoby w tym samym czasie udają się do kiosku elektronicznego, aby kupić bilet do kina na ten sam film i ten sam seans.

Jednak na ten seans w kinie pozostało tylko jedno miejsce. Bez kontroli współbieżności istnieje możliwość, że obaj widzowie kupią bilet. Kontrola współbieżności na to nie pozwala. Obaj widzowie nadal mają dostęp do informacji w bazie danych miejsc w kinie, ale kontrola współbieżności zapewnia bilet tylko temu, kto jako pierwszy sfinalizuje transakcję.

Protokoły kontroli współbieżności

Różne protokoły kontroli współbieżności oferują różne kompromisy między dopuszczalnym poziomem współbieżności a nakładanym narzutem. Główne techniki kontroli współbieżności w systemach DBMS to:

• Protokoły oparte na blokadach
• Protokół blokowania dwufazowego
• Protokoły oparte na znacznikach czasu
• Protokoły oparte na walidacji

Każdy z nich omówimy poniżej po kolei, zaczynając od najszerzej stosowanych protokołów opartych na blokadach.

Protokoły oparte na blokadach

Protokoły oparte na blokadach W systemach DBMS to mechanizm, w którym transakcja nie może odczytać ani zapisać elementu danych, dopóki nie uzyska odpowiedniej blokady. Protokoły oparte na blokadach pomagają wyeliminować problem współbieżności poprzez zablokowanie lub odizolowanie określonego elementu danych w ramach jednej transakcji.

Blokada to zmienna danych powiązana z elementem danych, która wskazuje, jakie operacje można na nim wykonać. Blokady pomagają synchronizować dostęp do elementów bazy danych poprzez transakcje współbieżne. Wszystkie żądania blokady są kierowane do menedżera kontroli współbieżności, a transakcje są kontynuowane dopiero po zatwierdzeniu żądania blokady.

Zamki binarne: Blokada binarna elementu danych może być zablokowana lub odblokowana.

Współdzielone/Ekskluzywne: Ten mechanizm blokowania rozdziela blokady w zależności od ich przeznaczenia. Jeśli blokada jest uzyskiwana w celu wykonania operacji zapisu, nazywa się ją blokadą wyłączną.

1. Wspólny zamek (S): Blokada współdzielona jest również nazywana blokadą tylko do odczytu. W przypadku blokady współdzielonej element danych może być współdzielony między transakcjami, ponieważ żadna z nich nie ma uprawnień do jego aktualizacji. Na przykład, jeśli dwie transakcje odczytują saldo konta danej osoby, baza danych Umożliwia im odczyt poprzez nałożenie wspólnej blokady. Jeśli inna transakcja chce zaktualizować to saldo, wspólna blokada uniemożliwia to do momentu zakończenia odczytu.

2. Ekskluzywny zamek (X): W przypadku blokady wyłącznej element danych może być zarówno odczytany, jak i zapisany. Blokada ma charakter wyłączny i nie może być jednocześnie utrzymywana na tym samym elemencie danych. Blokada X jest żądana za pomocą instrukcji lock-x. Na przykład, gdy transakcja wymaga aktualizacji salda konta, jest to dozwolone poprzez nałożenie blokady X; wówczas druga transakcja, która chce odczytać lub zapisać dane, jest blokowana.

3. Prosty protokół blokady: Umożliwia to transakcjom uzyskanie blokady na każdym obiekcie przed rozpoczęciem operacji. Transakcje mogą odblokować element danych po zakończeniu operacji zapisu.

4. Blokada przed złożeniem roszczenia: Ten protokół ocenia operacje i tworzy listę danych potrzebnych do rozpoczęcia wykonywania. Po przyznaniu wszystkich blokad transakcja zostaje wykonana, a wszystkie blokady zostają zwolnione po zakończeniu operacji.

Głód: Głodowanie to sytuacja, w której transakcja oczekuje przez nieokreślony czas na uzyskanie blokady. Przyczynami mogą być źle zarządzany schemat oczekiwania na zablokowane elementy, wyciek zasobów lub wielokrotne wybieranie tej samej transakcji jako ofiary.

Impas: Blokada odnosi się do sytuacji, w której dwa lub więcej procesów czeka, aż inny proces zwolni zasób, tworząc łańcuch cykliczny.

Protokół blokowania dwufazowego (2PL)

Protokół blokowania dwufazowego, znana również jako 2PL, to metoda kontroli współbieżności zapewniająca serializację poprzez zastosowanie blokady danych transakcji, która uniemożliwia innym transakcjom jednoczesny dostęp do tych samych danych.

Protokół blokowania dwufazowego pozwala każdej transakcji na wysłanie żądania zablokowania lub odblokowania w dwóch krokach:

• Faza wzrostu: na tym etapie transakcja może uzyskać blokady, ale nie może żadnej blokady zwolnić.
• Faza kurczenia: w tej fazie transakcja może zwalniać blokady, ale nie może uzyskać żadnej nowej blokady.

Prawdą jest, że 2PL oferuje serializację. Nie gwarantuje to jednak braku zakleszczeń. Na powyższym diagramie lokalne i globalne detektory zakleszczeń wyszukują zakleszczenia i rozwiązują je, wznawiając transakcje do ich stanów początkowych.

Ścisła metoda blokowania dwufazowego

Strict 2PL jest prawie taki sam jak 2PL. Jedyną różnicą jest to, że Strict-2PL nigdy nie zwalnia blokady po jej użyciu. Utrzymuje wszystkie blokady do momentu zatwierdzenia i zwalnia je wszystkie jednocześnie po zakończeniu procesu.

Scentralizowany 2PL

W systemie Centralized 2PL za proces zarządzania blokadami odpowiada jedna lokalizacja. Posiada ona tylko jednego menedżera blokad dla całego systemu DBMS.

Kopia podstawowa 2PL

W mechanizmie Primary Copy 2PL wiele menedżerów blokad jest rozproszonych w różnych lokalizacjach, a konkretny menedżer blokad odpowiada za zarządzanie blokadą dla zestawu danych. Po aktualizacji kopii głównej zmiana jest propagowana do serwerów podrzędnych.

Dystrybuowane 2PL

W tym mechanizmie menedżerowie blokad są rozproszeni po wszystkich lokalizacjach i odpowiadają za zarządzanie blokadami danych w danej lokalizacji. Jeśli dane nie są replikowane, jest to odpowiednik kopii podstawowej 2PL. Koszty komunikacji w rozproszonej kopii 2PL są znacznie wyższe niż w przypadku kopii podstawowej 2PL.

Protokoły oparte na znacznikach czasu

Protokół oparty na znaczniku czasu W systemie DBMS algorytm ten wykorzystuje czas systemowy lub licznik logiczny jako znacznik czasu do serializacji wykonywania współbieżnych transakcji. Zapewnia on, że każda kolidująca operacja odczytu i zapisu jest wykonywana w kolejności określonej przez znacznik czasu.

W tej metodzie priorytet ma zawsze starsza transakcja. Wykorzystuje ona czas systemowy do określenia znacznika czasu transakcji i jest najczęściej używanym protokołem współbieżności. Protokoły oparte na blokadach zarządzają kolejnością wykonywania kolidujących transakcji; protokoły oparte na znacznikach czasu zarządzają konfliktami od razu po utworzeniu operacji.

Przykład:

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

Zalety:

• Harmonogramy można serializować, podobnie jak protokoły 2PL.
• Nie ma konieczności czekania na transakcję, co eliminuje ryzyko wystąpienia blokad.

Niedogodności: Do zagłodzenia może dojść, jeśli ta sama transakcja jest ciągle uruchamiana od nowa i przerywana.

Protokół oparty na walidacji

Protokół oparty na walidacji W systemach DBMS, znana również jako technika optymistycznej kontroli współbieżności, jest metodą unikania konfliktów współbieżności w transakcjach. W tym protokole aktualizowane są lokalne kopie danych transakcji, a nie same dane, co skutkuje mniejszymi zakłóceniami podczas wykonywania.

Protokół oparty na walidacji wykonywany jest w trzech fazach:

1. Przeczytaj Fazę
2. Faza walidacji
3. Napisz fazę

Przeczytaj Fazę

W fazie odczytu wartości danych mogą zostać odczytane przez transakcję, ale operacje zapisu lub aktualizacji są stosowane tylko do lokalnych kopii danych, a nie do rzeczywistej bazy danych.

Faza walidacji

W fazie walidacji dane są sprawdzane w celu zapewnienia, że ​​zastosowanie aktualizacji nie naruszy możliwości serializacji.

Napisz fazę

W fazie zapisu aktualizacje są stosowane w bazie danych, jeśli walidacja zakończy się pomyślnie; w przeciwnym razie aktualizacje są odrzucane, a transakcja wycofywana.

Porównanie protokołów kontroli współbieżności

Cztery rodziny protokołów stawiają różne hipotezy dotyczące tego, jak często transakcje faktycznie kolidują. Poniższa tabela podsumowuje, gdzie każda z nich pasuje.

Krótko mówiąc, protokoły oparte na blokadach i 2PL zakładają, że konflikty występują często i zapobiegają im z góry, podczas gdy protokoły oparte na znacznikach czasu i walidacji zakładają, że konflikty występują rzadko i rozwiązują je tylko wtedy, gdy się pojawią.

Cechy dobrego protokołu współbieżności

Idealny mechanizm kontroli współbieżności ma następujące cele:

• Musi być odporny na awarie witryny i problemy z komunikacją.
• Umożliwia równoległą realizację transakcji w celu osiągnięcia maksymalnej współbieżności.
• Mechanizmy przechowywania i metody obliczeniowe powinny być skromne, aby zminimalizować obciążenie.
• Musi narzucić pewne ograniczenia na strukturę atomowych działań transakcji.

FAQ