Protokół zatwierdzania dwufazowego — Two-phase commit protocol

„2PC” przekierowuje tutaj. Aby zapoznać się z grą w futbol amerykański i kanadyjski, zobacz Konwersja dwupunktowa . Aby zapoznać się z protokołem kryptograficznym, zobacz Schemat zobowiązań .

W przetwarzaniu transakcji , baz danych i sieci komputerowych , dwufazowe protokół ( 2PC ) jest typem atomowym protokołu zobowiązań (ACP). Jest to algorytm rozproszony, który koordynuje wszystkie procesy uczestniczące w rozproszonej transakcji atomowej w kwestii zatwierdzenia lub przerwania (wycofania) transakcji (jest to wyspecjalizowany rodzaj protokołu konsensusu ). Protokół osiąga swój cel nawet w wielu przypadkach tymczasowej awarii systemu (obejmującej awarie procesów, węzła sieci, komunikacji itp.) i dlatego jest szeroko stosowany. Jednak nie jest odporny na wszystkie możliwe konfiguracje awarii, aw rzadkich przypadkach konieczna jest ręczna interwencja, aby naprawić wynik. Aby uwzględnić odzyskiwanie po awarii (w większości przypadków automatyczne) uczestnicy protokołu używają rejestrowania stanów protokołu. Rekordy dzienników, których generowanie jest zazwyczaj powolne, ale przetrwają awarie, są wykorzystywane przez procedury odzyskiwania protokołu . Istnieje wiele wariantów protokołu, które różnią się przede wszystkim strategiami rejestrowania i mechanizmami odzyskiwania. Chociaż zwykle mają być używane rzadko, procedury odzyskiwania stanowią znaczną część protokołu, ze względu na wiele możliwych scenariuszy awarii, które należy uwzględnić i wspierać.

W „normalnym wykonaniu” dowolnej pojedynczej transakcji rozproszonej (tj. gdy nie występuje awaria, co jest zazwyczaj najczęstszą sytuacją), protokół składa się z dwóch faz:

  1. Faza żądania zatwierdzenia (lub faza głosowania), w której proces koordynatora próbuje przygotować wszystkie procesy uczestniczące w transakcji (nazwani uczestnicy, kohorty lub pracownicy) do podjęcia kroków niezbędnych do zatwierdzenia lub przerwania transakcji i do głosowania, albo "Tak": zatwierdź (jeśli wykonanie części lokalnej uczestnika transakcji zakończyło się prawidłowo) lub "Nie": przerwij (jeśli wykryto problem z częścią lokalną), oraz
  2. Faza zatwierdzenia, w której na podstawie głosowania uczestników, koordynator decyduje, czy zatwierdzić (tylko jeśli wszyscy zagłosowali na „Tak”), czy przerwać transakcję (w przeciwnym razie) i powiadamia wszystkich uczestników o wyniku. Następnie uczestnicy wykonują niezbędne czynności (zatwierdzenie lub przerwanie) ze swoimi lokalnymi zasobami transakcyjnymi (zwanymi również zasobami możliwymi do odzyskania; np. dane bazy danych) i ich odpowiednimi częściami w innych danych wyjściowych transakcji (jeśli dotyczy).

Protokół dwufazowego zatwierdzania (2PC) nie powinien być mylony z protokołem dwufazowego blokowania (2PL), protokołem kontroli współbieżności .

Założenia

Protokół działa w następujący sposób: jeden węzeł jest wyznaczonym koordynatorem, który jest miejscem nadrzędnym, a pozostałe węzły w sieci są wyznaczonymi uczestnikami. Protokół zakłada, że w każdym węźle znajduje się stabilna pamięć masowa z dziennikiem zapisu z wyprzedzeniem , że żaden węzeł nie ulega awarii na zawsze, że dane w dzienniku zapisu z wyprzedzeniem nigdy nie zostają utracone ani uszkodzone w wyniku awarii oraz że dowolne dwa węzły mogą komunikować się z wzajemnie. To ostatnie założenie nie jest zbyt restrykcyjne, ponieważ komunikacja sieciowa może być zwykle przekierowywana. Pierwsze dwa założenia są znacznie silniejsze; jeśli węzeł zostanie całkowicie zniszczony, dane mogą zostać utracone.

Protokół jest inicjowany przez koordynatora po osiągnięciu ostatniego kroku transakcji. Następnie uczestnicy odpowiadają komunikatem o zgodzie lub komunikatem o przerwaniu, w zależności od tego, czy transakcja została pomyślnie przetworzona u uczestnika.

Podstawowy algorytm

Zatwierdź fazę żądania (lub głosowania)

  1. Koordynator wysyła zapytanie o zatwierdzenie wiadomości do wszystkich uczestników i czeka na otrzymanie odpowiedzi od wszystkich uczestników.
  2. Uczestnicy realizują transakcję do momentu, w którym zostaną poproszeni o zatwierdzenie. Każdy z nich zapisuje wpis do swojego dziennika cofania i wpis do swojego dziennika ponawiania .
  3. Każdy uczestnik odpowiada komunikatem o zgodzie (uczestnik głosuje tak, aby zatwierdzić), jeśli działania uczestnika powiodły się, lub komunikatem o przerwaniu (uczestnik głosuje nie, nie zatwierdza), jeśli uczestnik doświadczy niepowodzenia uniemożliwiającego zatwierdzenie.

Faza zatwierdzenia (lub zakończenia)

Powodzenie

Jeśli koordynator otrzymał wiadomość o zgodzie od wszystkich uczestników w fazie zatwierdzenia-wniosku:

  1. Koordynator wysyła wiadomość do wszystkich uczestników.
  2. Każdy uczestnik kończy operację i zwalnia wszystkie blokady i zasoby przechowywane podczas transakcji.
  3. Każdy uczestnik przesyła potwierdzenie do koordynatora.
  4. Koordynator kończy transakcję po otrzymaniu wszystkich potwierdzeń.

Niepowodzenie

Jeśli któryś z uczestników zagłosuje na „Nie” w fazie prośby o zatwierdzenie (lub wygaśnie limit czasu koordynatora):

  1. Koordynator wysyła wiadomość o wycofaniu do wszystkich uczestników.
  2. Każdy uczestnik cofa transakcję za pomocą dziennika cofania oraz zwalnia zasoby i blokady utrzymywane podczas transakcji.
  3. Każdy uczestnik przesyła potwierdzenie do koordynatora.
  4. Koordynator cofa transakcję po otrzymaniu wszystkich potwierdzeń.

Przepływ wiadomości

Coordinator                                          Participant
                             QUERY TO COMMIT
                 -------------------------------->
                             VOTE YES/NO             prepare*/abort*
                 <-------------------------------
commit*/abort*               COMMIT/ROLLBACK
                 -------------------------------->
                             ACKNOWLEDGMENT          commit*/abort*
                 <--------------------------------  
end

Znak * obok typu rekordu oznacza, że ​​rekord jest przechowywany w stabilnym miejscu.

Niedogodności

Największą wadą protokołu zatwierdzania dwufazowego jest to, że jest to protokół blokujący. Jeśli koordynator ulegnie trwałej awarii, niektórzy uczestnicy nigdy nie rozwiążą swoich transakcji: po wysłaniu przez uczestnika komunikatu o umowie do koordynatora, zostanie on zablokowany do czasu otrzymania zatwierdzenia lub wycofania.

Implementacja protokołu zatwierdzania dwufazowego

Wspólna architektura

W wielu przypadkach protokół 2PC jest rozprowadzany w sieci komputerowej. Jest łatwo dystrybuowany poprzez implementację wielu dedykowanych komponentów 2PC podobnych do siebie, zwykle nazywanych menedżerami transakcji (TM; określani również jako agenty 2PC lub monitory przetwarzania transakcji), które wykonują wykonanie protokołu dla każdej transakcji (np. The Open Group ' s X/Otwórz XA ). Bazy danych zaangażowane w transakcję rozproszoną, uczestnicy, zarówno koordynator, jak i uczestnicy, rejestrują się w zamkniętych bazach TM (zwykle rezydujących w tych samych węzłach sieci co uczestnicy) w celu zakończenia transakcji za pomocą 2PC. Każda transakcja rozproszona posiada zestaw baz TM ad hoc, w których rejestrują się uczestnicy transakcji. Lider, koordynator TM, istnieje dla każdej transakcji, aby koordynować dla niej 2PC, zazwyczaj TM bazy danych koordynatora. Rolę koordynatora można jednak przenieść do innej bazy TM ze względu na wydajność lub niezawodność. Zamiast wymieniać między sobą wiadomości 2PC, uczestnicy wymieniają się wiadomościami z odpowiednimi bazami TM. Odpowiednie bazy TM komunikują się między sobą w celu wykonania powyższego schematu protokołu 2PC, „reprezentując” odpowiednich uczestników w celu zakończenia tej transakcji. Dzięki tej architekturze protokół jest w pełni rozproszony (nie wymaga żadnego centralnego elementu przetwarzającego ani struktury danych) i skutecznie skaluje się wraz z liczbą węzłów sieci (rozmiarem sieci).

Ta wspólna architektura jest również skuteczna w przypadku dystrybucji innych protokołów zaangażowania atomowego oprócz 2PC, ponieważ wszystkie takie protokoły wykorzystują ten sam mechanizm głosowania i propagacji wyników wśród uczestników protokołu.

Optymalizacje protokołów

Przeprowadzono badania bazy danych dotyczące sposobów uzyskania większości korzyści z protokołu dwufazowego zatwierdzania przy jednoczesnym obniżeniu kosztów poprzez optymalizację protokołu i oszczędzanie operacji protokołu przy określonych założeniach dotyczących zachowania systemu.

Domniemane przerwanie i domniemane popełnienie

Domniemane przerwanie lub domniemane zatwierdzenie są powszechnymi takimi optymalizacjami. Założenie o wyniku transakcji, czy to zatwierdzeniu, czy przerwaniu, może zapisywać zarówno komunikaty, jak i operacje rejestrowania przez uczestników podczas wykonywania protokołu 2PC. Na przykład, w przypadku domniemanego przerwania, jeśli podczas odzyskiwania systemu po awarii procedura odzyskiwania nie wykryje zarejestrowanych dowodów na zatwierdzenie jakiejś transakcji, zakłada, że ​​transakcja została przerwana i działa zgodnie z tym. Oznacza to, że nie ma znaczenia, czy aborcje są w ogóle rejestrowane, a takie rejestrowanie można zapisać przy tym założeniu. Zazwyczaj podczas odzyskiwania po awarii płaci się karę za dodatkowe operacje, w zależności od typu optymalizacji. Zatem najlepszy wariant optymalizacji, jeśli w ogóle, jest wybierany na podstawie statystyk niepowodzeń i wyników transakcji.

Protokół zatwierdzania dwufazowego drzewa

Protokół Tree 2PC (zwany także Nested 2PC lub Recursive 2PC) jest powszechnym wariantem 2PC w sieci komputerowej , który lepiej wykorzystuje podstawową infrastrukturę komunikacyjną. Uczestnicy transakcji rozproszonej są zazwyczaj wywoływani w kolejności, która definiuje strukturę drzewa, drzewo wywołań, gdzie uczestnikami są węzły, a krawędziami wywołania (łącza komunikacyjne). To samo drzewo jest powszechnie wykorzystywane do realizacji transakcji za pomocą protokołu 2PC, ale w zasadzie można do tego wykorzystać również inne drzewo komunikacji. W drzewie 2PC koordynator jest uważany za główny („górny”) drzewa komunikacyjnego (drzewo odwrócone), podczas gdy uczestnikami są inne węzły. Koordynatorem może być węzeł, który zainicjował transakcję (wywoływany rekursywnie (przechodnie) przez innych uczestników), ale również inny węzeł w tym samym drzewie może zamiast tego przyjąć rolę koordynatora. Wiadomości 2PC od koordynatora są propagowane „w dół” drzewa, natomiast wiadomości do koordynatora są „zbierane” przez uczestnika od wszystkich uczestników znajdujących się poniżej, zanim wyśle ​​odpowiednią wiadomość „w górę” drzewa (z wyjątkiem wiadomości o przerwaniu, która jest propagowana „w górę” natychmiast po jej otrzymaniu lub jeśli obecny uczestnik zainicjuje przerwanie).

Protokół dynamicznego zatwierdzania dwufazowego (Dynamiczne zatwierdzanie dwufazowe, D2PC) jest wariantem Tree 2PC bez z góry określonego koordynatora. Obejmuje kilka optymalizacji, które zostały zaproponowane wcześniej. Komunikaty o zgodzie (głosy Tak) zaczynają się rozchodzić ze wszystkich liści, z każdego liścia podczas wykonywania swoich zadań w imieniu transakcji (stając się gotowym). Węzeł pośredni (nie będący liściem) wysyła komunikat gotowości, gdy komunikat zgody do ostatniego (pojedynczego) sąsiedniego węzła, z którego komunikat zgody nie został jeszcze odebrany. Koordynator jest określany dynamicznie przez komunikaty umów wyścigowych nad drzewem transakcji, w miejscu ich kolizji. Zderzają się one albo w węźle drzewa transakcji, jako koordynator, albo na krawędzi drzewa. W tym drugim przypadku jeden z dwóch węzłów krawędziowych zostaje wybrany jako koordynator (dowolny węzeł). D2PC jest optymalny czasowo (pomiędzy wszystkimi instancjami określonego drzewa transakcji i dowolną konkretną implementacją protokołu Tree 2PC; wszystkie instancje mają to samo drzewo; każda instancja ma inny węzeł jako koordynator): Wybierając optymalnego koordynatora, D2PC zobowiązuje zarówno koordynatora i każdego uczestnika w możliwie najkrótszym czasie, umożliwiając jak najwcześniejsze zwolnienie zablokowanych zasobów u każdego uczestnika transakcji (węzeł drzewa).

Zobacz też

Bibliografia