Blokowanie dwufazowe

Blokowanie dwufazoweEdit

Zgodnie z protokołem blokowania dwufazowego transakcja obsługuje swoje blokady w dwóch odrębnych, następujących po sobie fazach podczas wykonywania transakcji:

1. Faza rozszerzania (vel faza wzrostu): blokady są nabywane i żadne blokady nie są zwalniane (liczba blokad może tylko rosnąć).
2. Shrinking phase (aka Contracting phase): zamki są zwalniane i żadne zamki nie są nabywane.

Dwufazowe zasady blokowania można podsumować jako: nigdy nie nabywaj blokady po zwolnieniu blokady. Właściwość serializowalności jest gwarantowana dla harmonogramu z transakcjami, które przestrzegają tej reguły.

Typowo, bez wyraźnej wiedzy w transakcji na temat końca fazy 1, jest bezpiecznie określona tylko wtedy, gdy transakcja zakończyła przetwarzanie i zażądała commit. W takim przypadku wszystkie zamki mogą zostać zwolnione jednocześnie (faza 2).

Konserwatywne blokowanie dwufazoweEdit

Różnica między 2PL a C2PL polega na tym, że transakcje C2PL uzyskują wszystkie zamki, których potrzebują, zanim transakcje się rozpoczną. Ma to na celu zapewnienie, że transakcja, która już posiada pewne zamki nie zablokuje się czekając na inne zamki. Konserwatywne 2PL zapobiega deadlockom.

Ścisłe blokowanie dwufazoweEdit

Aby zachować zgodność z protokołem S2PL, transakcja musi być zgodna z 2PL i zwalniać swoje blokady zapisu (wyłączne) dopiero po jej zakończeniu, tzn. po popełnieniu lub przerwaniu. Z drugiej strony, blokady odczytu (współdzielone) są zwalniane regularnie podczas fazy 2. Ten protokół nie jest odpowiedni w B-drzewach, ponieważ powoduje wąskie gardło (podczas gdy B-drzewa zawsze rozpoczynają wyszukiwanie od korzenia nadrzędnego).

Strong strict two-phase lockingEdit

lub Rigorousness, or Rigorous scheduling, or Rigorous two-phase locking

Aby spełnić wymagania strong strict two-phase locking (SS2PL) protokół blokowania zwalnia zarówno blokady zapisu (exclusive), jak i odczytu (shared) zastosowane przez transakcję tylko po jej zakończeniu, tj, tylko po zakończeniu wykonywania (gotowości) i zaangażowaniu lub przerwaniu. Protokół ten jest również zgodny z regułami S2PL. Transakcja zgodna z SS2PL może być postrzegana jako posiadająca fazę 1, która trwa przez cały czas wykonywania transakcji, oraz brak fazy 2 (lub zdegenerowaną fazę 2). Pozostaje więc właściwie tylko jedna faza, a „dwufazowość” w nazwie wydaje się być nadal wykorzystywana ze względu na historyczne rozwinięcie koncepcji z 2PL, oraz fakt, że 2PL jest superklasą. Właściwość SS2PL harmonogramu jest również nazywana Rygorystycznością. Jest to również nazwa klasy harmonogramów posiadających tę własność, a harmonogram SS2PL jest również nazywany „rygorystycznym harmonogramem”. Termin „Rygorystyczność” jest wolny od niepotrzebnego dziedzictwa „dwufazowości”, jak również jest niezależny od jakiegokolwiek mechanizmu (blokującego) (w zasadzie można wykorzystać inne mechanizmy blokujące). Odpowiedni mechanizm blokujący tej właściwości jest czasami określany jako Rigorous 2PL.

SS2PL jest szczególnym przypadkiem S2PL, tzn. klasa harmonogramów SS2PL jest właściwą podklasą S2PL (każdy harmonogram SS2PL jest również harmonogramem S2PL, ale istnieją harmonogramy S2PL, które nie są SS2PL).

SS2PL jest protokołem kontroli współbieżności z wyboru dla większości systemów baz danych i jest wykorzystywany od wczesnych lat 70-tych. Protokół ten okazał się skutecznym mechanizmem w wielu sytuacjach i zapewnia, oprócz Serializability, również Strictness (specjalny przypadek kaskadowej Recoverability), która jest kluczowa dla efektywnego odzyskiwania bazy danych, a także Commitment ordering (CO) dla uczestniczenia w środowiskach rozproszonych, w których stosowane są rozwiązania oparte na CO-based distributed serializability i global serializability. Będąc podzbiorem CO, wydajna implementacja rozproszonego SS2PL istnieje bez rozproszonego menedżera blokad (DLM), podczas gdy rozproszone deadlocki (patrz niżej) są rozwiązywane automatycznie. Fakt, że SS2PL zastosowany w systemach wielobazowych zapewnia globalną serializowalność był znany od lat przed odkryciem CO, ale dopiero wraz z CO zrozumiano rolę protokołu zobowiązań atomowych w utrzymaniu globalnej serializowalności, jak również zaobserwowano automatyczne rozwiązywanie rozproszonych deadlinów (zobacz szczegółowy przykład Distributed SS2PL). W gruncie rzeczy, dziedziczenie przez SS2PL właściwości Recoverability i CO jest bardziej znaczące niż bycie podzbiorem 2PL, który sam w swojej ogólnej postaci, poza tym, że zawiera prosty mechanizm serializowalności (serializowalność jest jednak również implikowana przez CO), nie jest w stanie zapewnić SS2PL żadnych innych znaczących właściwości. 2PL w swojej ogólnej postaci, jak również w połączeniu ze Strictness, czyli Strict 2PL (S2PL), nie są znane z praktycznego wykorzystania. Popularny SS2PL nie wymaga oznaczania „końca fazy 1” tak jak 2PL i S2PL, a więc jest prostszy w implementacji. Ponadto, w przeciwieństwie do ogólnego 2PL, SS2PL zapewnia, jak wspomniano powyżej, przydatne właściwości Strictness i Commitment ordering.

Istnieje wiele wariantów SS2PL, które wykorzystują różne typy blokad z różnymi semantykami w różnych sytuacjach, w tym w przypadkach zmiany typu blokady podczas transakcji. Godne uwagi są warianty, które używają blokowania o wielorakiej granulacji.

1. SS2PL vs. S2PL: Oba zapewniają Serializability i Strictness. Ponieważ S2PL jest nadklasą SS2PL, może, w zasadzie, zapewnić większą współbieżność. Jednakże, żadna przewaga współbieżności nie jest praktycznie zauważalna (dokładnie takie same blokady istnieją dla obu, z praktycznie niewiele wcześniejszym zwolnieniem blokady dla S2PL), a narzut na zajmowanie się mechanizmem końca fazy-1 w S2PL, oddzielnym od końca transakcji, nie jest uzasadniony. Ponadto, podczas gdy SS2PL zapewnia porządkowanie zobowiązań, S2PL tego nie robi. To wyjaśnia preferencje SS2PL w stosunku do S2PL.
2. Szczególnie przed rokiem 1990, ale także po, w wielu artykułach i książkach, np. (Bernstein et al. 1987, s. 59), termin „Strict 2PL” (S2PL) był często definiowany przez protokół blokowania „Release all locks only after transaction end”, który jest protokołem SS2PL. Tak więc „Strict 2PL” nie mogło być tam nazwą przecięcia Strictness i 2PL, które jest większe niż klasa generowana przez protokół SS2PL. To spowodowało zamieszanie. Dzięki wyraźnej definicji S2PL jako przecięcia Strictness i 2PL, nowej nazwie dla SS2PL oraz wyraźnemu rozróżnieniu pomiędzy klasami S2PL i SS2PL, artykuły (Breitbart et al. 1991) oraz (Raz 1992) miały na celu wyjaśnienie zamieszania: pierwszy używając nazwy „rigorousness”, a drugi „SS2PL”.”
3. Istnieje bardziej ogólna właściwość niż SS2PL (superklasa harmonogramu), Strict commitment ordering (Strict CO, lub SCO), która również zapewnia zarówno serializowalność, ścisłość, jak i CO, i ma podobny narzut blokady. W przeciwieństwie do SS2PL, SCO nie blokuje się przy konflikcie odczytu z zapisem (blokada odczytu nie blokuje nabycia blokady zapisu; zarówno SCO jak i SS2PL mają takie samo zachowanie dla konfliktów zapisu-odczytu i zapisu-zapisu) kosztem ewentualnego opóźnionego commitu, a przy takim konflikcie SCO ma krótszy średni czas zakończenia transakcji i lepszą wydajność niż SS2PL. Podczas gdy SS2PL stosuje się do powyższej tabeli zgodności blokad, SCO ma następującą tabelę:

Należy zauważyć, że chociaż SCO zwalnia wszystkie blokady na końcu transakcji i jest zgodne z zasadami blokowania 2PL, SCO nie jest podzbiorem 2PL z powodu innej tabeli kompatybilności blokad. SCO pozwala na zmaterializowane konflikty odczytu i zapisu pomiędzy dwoma transakcjami w ich fazie 1, na co 2PL nie pozwala w fazie 1 (zobacz o zmaterializowanych konfliktach w Serializability). Z drugiej strony 2PL pozwala na inne zmaterializowane typy konfliktów w fazie 2, na które SCO w ogóle nie pozwala. Razem implikuje to, że klasy harmonogramów 2PL i SCO są nieporównywalne (tzn. żadna klasa nie zawiera drugiej klasy).

Podsumowanie – Relacje między klasamiEdit

Zawieranie klas harmonogramu: Strzałka od klasy A do klasy B wskazuje, że klasa A ściśle zawiera B; brak skierowanej ścieżki między klasami oznacza, że klasy są nieporównywalne. Właściwość jest z natury blokująca, jeśli może być egzekwowana tylko przez blokowanie operacji dostępu do danych transakcji do czasu wystąpienia pewnych zdarzeń w innych transakcjach. (Raz 1992)

Pomiędzy dwoma dowolnymi klasami harmonogramów (zdefiniowanymi przez ich właściwości), które mają wspólne harmonogramy, albo jedna zawiera drugą (ściśle zawiera, jeśli nie są równe), albo są one nieporównywalne. Relacje zawierania pomiędzy klasami 2PL i innymi głównymi klasami harmonogramów są podsumowane na poniższym diagramie. 2PL i jego podklasy są z natury blokujące, co oznacza, że nie istnieją dla nich optymistyczne implementacje (i ilekroć jest mowa o „Optymistycznym 2PL” odnosi się to do innego mechanizmu z klasą, która zawiera również harmonogramy nie należące do klasy 2PL).