Nowych czytelników zapraszam do zapoznania się najpierw z wcześniejszymi wpisami, do których adresy zamieściłem w przypisach.
Protokół
Omawiana biblioteka umożliwia tworzenie transakcji hierarchicznych, czyli takich, gdzie uczestnicy mogą rozpoczynać swoje własne transakcje podrzędne powiązane z transakcją główną. Musi to być uwzględnione w protokole i tak jest w istocie. Zdecydowałem się na użycie pewnej modyfikacji protokołu 2PC o nazwie drzewiasty 2PC. Pozwala on na zmniejszenie obciążenia głównego koordynatora poprzez przeniesienie części zadań na koordynatorów podrzędnych. Wygląda to w ten sposób, że każdy koordynator zna tylko swoich bezpośrednich uczestników, przekazuje do nich informacje od koordynatora nadrzędnego i odsyła mu zbiorczą odpowiedź. Z punktu widzenia samej transakcji nie ma to znaczenia, czy decyzje wszystkich uczestników zbierze jeden koordynator, czy kilku i stopniowo będą oni składać to wszystko do kupy.
Wszyscy uczestnicy transakcji wymieniają się wiadomościami o ściśle ustalonym formacie opisanym przez następującą strukturę:
struct protocol_msg { uint16_t signature; uint32_t msg_type; /* master transaction information */ uint32_t master_trans_id; int32_t master_host; uint16_t master_port; /* sub-transaction information */ uint32_t parent_trans_id; int32_t parent_host; uint16_t parent_port; /* message data */ uint8_t data_length; char data[256]; };
Zaczyna się ona od 16-bitowej charakterystycznej sygnatury, następnie mamy typ wiadomości, pola kontrolne identyfikujące transakcję (dane głównego koordynatora oraz dane nadrzędnego koordynatora). Niektóre typy komunikatów pozwalają opcjonalnie załączyć dodatkowy blok danych o długości do 256 bajtów. Nakładki na funkcje systemowe recv() i send() automatycznie dobierają faktyczny rozmiar wiadomości do długości dodatkowych danych tak, by nie przesyłać niepotrzebnych śmieci i nie marnować łącza.
W protokole wyróżniamy kilka etapów:
- Tworzenie transakcji - transakcja rejestrowna jest w dzienniku
- Akcja - proces wykonuje tu jakieś operacje. Możliwe jest tutaj zapraszanie nowych uczestników do transakcji oraz wymiana danych z nimi.
- Faza głosowania - gdy główny koordynator zakończy swoją akcję, rozsyła do uczestników informację o rozpoczęciu głosowania. Każdy uczestnik przysyła swoje głosy.
- Faza decyzji - koordynator główny decyduje, czy zatwierdzić czy anulować transakcję i wysyła decyzję do uczestników. Uczestnicy stosują się do niej i odsyłają potwierdzenie odebrania.
Zapraszanie do transakcji
Każdy uczestnik transakcji może na etapie wykonywania akcji zaprosić inny proces do uczestnictwa w transakcji. Staje się on wtedy koordynatorem dla zapraszanego uczestnika. Od strony biblioteki takie połączenie jest równoznaczne z otwarciem kanału komunikacyjnego. Biblioteka na początku wysyła wiadomość PROTO_INVITATION, do której uczestnik może załączyć jakieś dane wejściowe. Zapraszany proces odbiera pakiet, odczytuje dane wejściowe i przyjmuje lub odrzuca zaproszenie. Przyjęcie realizowane jest poprzez odesłanie wiadomości PROTO_JOIN i poczekanie na potwierdzenie PROTO_JOINED. Od tego momentu oba procesy mogą się ze sobą komunikować.
Komunikacja
Na etapie wykonywania akcji procesy mogą dość intensywnie wymieniać się danymi. Protokół definiuje komunikat PROTO_DATA umożliwiający przesłanie danych od uczestnika A do B. Zauważmy, że procesy muszą same mieć ustalony kolejny, nadrzędny protokół, według którego rozmawiają ze sobą, co powoduje, że w pewien naturalny sposób się one synchronizują (A wysyła dane i czeka, aż B je przetworzy i odeśle odpowiedź itd.). Jednak nie zapominajmy, że na tym etapie uczestnicy mogą w każdej chwili zdecydować się na przerwanie akcji, np. z powodu błędu (jest to równoznaczne z późniejszym głosowaniem na anulowanie transakcji). Pozostaje pytanie, co zrobić, gdy A przerwał swoje wykonywanie, tymczasem B oczekuje na jakieś dane od niego. Rozwiązania są tu dwa:
- Biblioteka ma ustawiony limit oczekiwania na nadejście pakietu (u mnie: 30 sekund). Jeśli do tego czasu spodziewany pakiet nie nadejdzie, funkcja odbierająca zwraca -1 i uczestnik na podstawie tego może również u siebie przerwać akcję.
- Często mamy możliwość przewidzenia, że wszystko zmierza w złym kierunku. Aby inni uczestnicy nie czekali zbyt długo, a tym samym nie blokowali zasobów, delikwent zamierzający się nieoczekiwanie przerwać, może tuż przed zakończeniem wysłać komunikat PROTO_DATA_FAILURE informujący, że spodziewane przez drugiego uczestnika dane nigdy nie nadejdą.
Gdy jakiś uczestnik zakończył swoją akcję, zapamiętuje swój głos i rozpoczyna oczekiwanie na rozpoczęcie głosowania...
Głosowanie
Gdy główny koordynator zakończy swoją fazę akcji, przystępuje do rozpoczęcia głosowania, wysyłając do swoich bezpośrednich podwładnych komunikat PROTO_PLEASE_VOTE. Jeśli podwładny jest koordynatorem podrzędnym (innymi słowy, rozpoczął własną zagnieżdżoną transakcję), przekazuje on ten komunikat dalej, do swoich podwładnych i tak dalej. Zwykły uczestnik po odebraniu zaproszenia wysyła odpowiedź PROTO_VOTE_COMMIT lub PROTO_VOTE_ROLLBACK. Koordynatorzy podrzędni zbierają takie głosy, dokładają do tego swój i na podstawie tego konstruują głos dla koordynatora nadrzędnego. Jeśli wśród głosów pojawił się ROLLBACK, ostatecznym głosem też jest ROLLBACK, zaś w przeciwnym razie - COMMIT. Koordynator główny zbiera głosy, dodaje swój i na podstawie tego podejmuje ostateczną decyzję zgodnie z tymi samymi regułami.
Jeżeli w tej fazie wystąpi jakikolwiek problem (np. jakiś uczestnik nie otrzyma spodziewanego komunikatu itd.), cała transakcja jest anulowana. Uczestnicy, jeśli tylko mają możliwość, wysyłają wszędzie, gdzie się da, pakiet PROTO_ABORT nakazujący jak najszybsze zwinięcie transakcji (taki turbo-rollback :)). Nie jest istotne, czy faktycznie dotrze on do adresata - w takim wypadku wyłoży się on na przekroczeniu limitu czasu oczekiwania. PROTO_ABORT ma na celu jedynie jak najszybsze odblokowanie zajmowanych zasobów, gdy tylko jest ku temu sposobność.
Decyzja
Koordynator główny na podstawie zebranych głosów podejmuje decyzję, czy zatwierdzić transakcję. Wysyła ją jako komunikat PROTO_DECISION_COMMIT bądź PROTO_DECISION_ROLLBACK do swoich podwładnych. Analogicznie, jak w przypadku głosowania, koordynatorzy podrzędni posyłają taką decyzję dalej, do znanych sobie uczestników. Zwykły uczestnik odpowiada na taką decyzję, odsyłając potwierdzenie PROTO_DECISION_CONFIRM i przystępując do zatwierdzania bądź anulowania swojej części transakcji. Koordynatorzy podrzędni odsyłają swoje potwierdzenie, gdy dostaną wszystkie potwierdzenie z poziomu niżej.
W fazie drugiej sytuacja w obsługą błędów nie jest tak komfortowa, jak w fazie głosowania. Zakładamy, że każdy uczestnik musi w końcu odebrać decyzję i każdy koordynator musi w końcu dostać potwierdzenie. Można się tym zająć w następujący sposób:
- Uczestnik, który nie dostał decyzji, po prostu zostawia transakcję w spokoju w stanie nieokreślonym, wychodząc z założenia, że za chwilę koordynator będzie próbował połączyć się ponownie. Gdy wezwanie nadejdzie, transakcja zostanie wznowiona i dokończona.
- Koordynator, który nie dostał potwierdzenia, dopisuje transakcję do kolejki transakcji, w których należy powtórzyć wysyłanie decyzji. Co pewien ustalony czas osobny wątek przegląda kolejkę i dla znajdujących się w nich transakcji ponownie otwiera wszystkie kanały i wysyła do nich decyzję, dokładnie tak samo, jak przy normalnym zatwierdzaniu. Jeśli znów się nie uda, transakcja wraca do kolejki, w przeciwnym razie jest kończona.
Co się dzieje, gdy proces otrzymuje po raz drugi decyzję dotyczącą transakcji, którą już wykonał i zatwierdził? Nic, po prostu odsyła pro forma potwierdzenie. Zakładając niezawodność i niezniszczalność sprzętu, takie podejście gwarantuje nam, że wszyscy uczestnicy w końcu dostaną decyzję i zastosują się do niej.
Podsumowanie
Po otrzymaniu potwierdzenia i wykonaniu akcji zatwierdzającej/odrzucającej, transakcja oznaczana jest w dzienniku jako wykonana.
Interfejs programistyczny
Jak wspominałem na początku, API biblioteki uległo dość mocnym przeobrażeniom. To, co opisywałem w poprzednim wpisie, wciąż istnieje, ale w większości jako wewnętrzny interfejs, do którego programista nie ma dostępu. Na jego bazie zbudowana jest następująca konstrukcja.
Pierwsza rzecz to dziennik transakcji, który teraz przechowuje pełną strukturę transakcji. Dodatkowo, rejestrujemy w nim tzw. typy transakcji, czyli różne operacje, które chcemy realizować w środowisku transakcyjnym. Typ transakcji definiowany jest przez cztery funkcje oraz wskaźnik do argumentu dla nich:
- startup_func - funkcja wykonywana w trakcie inicjowania transakcji. Jej zadaniem jest wypełnienie rekordu danej transakcji danymi specyficznymi dla danego typu transakcji.
- action_func - funkcja wykonująca konkretną akcję. Musi zwrócić 0, jeśli głosujemy za zatwierdzeniem transakcji lub -1, jeśli za odrzuceniem.
- commit_func - funkcja zatwierdzająca zmiany wprowadzone przez action_func.
- rollback_func - funkcja wycofująca zmiany wprowadzone przez action_func.
Biblioteka samodzielnie dokonuje przełączania między podanymi funkcjami i na podstawie zwracanych przez nie wartości decyduje, co robić dalej. Znacznie zwiększa to idiotoodporność, gdyż teraz programista nie musi już pamiętać, jakie funkcje musi w jakiej kolejności wykonywać, aby protokół został zrealizowany.
My mamy do dyspozycji jedynie następujące funkcje:
- trans_start() - pozwala rozpocząć nową transakcję danego typu jako jej koordynator główny.
- trans_listen() - jako argument otrzymuje deskryptor gniazda, w którym oczekuje na nadejście pakietu. Rozszyfrowuje go i sprawdza, czy należy on do protokołu transakcyjnego, czy nie. Jeśli jest to zaproszenie do udziału, dodatkowa funkcja przekazywana jako argument decyduje, czy przyłączyć się, a jeśli tak, to jakiego typu transakcja będzie właśnie startować. W odpowiedzi na zwykły pakiet, funkcja startuje nową transakcję jako jej główny koordynator. Możliwe jest też odebranie decyzji o potwierdzeniu/odrzuceniu innej transakcji i należy wtedy zastosować się do niej, dokańczając daną transakcję.
I to właściwie tyle. My jako programiści, mamy napisać cztery funkcje i zarejestrować je jako typ transakcji. Do dyspozycji wciąż mamy API do otwierania i zamykania kanałów (nieco uproszczone - wypadły z niego funkcje do głosowania) oraz trans_send() i trans_recv() do wysyłania danych do koordynatora nadrzędnego.
Przykład
Zaczynamy od zainicjowania dziennika i zarejestrowania jakiegoś typu transakcji:
/* ustaw parametry polaczenia */ trans_engine_init(some_host, some_port); /* utworz dziennik i zarejestruj jakis typ transakcji */ struct trans_journal *journal = trans_journal_alloc(); struct trans_functionset fset; fset.startup_func = trans_startup; fset.action_func = trans_action; fset.commit_func = trans_commit; fset.rollback_func = trans_rollback; trans_journal_register_functionset(journal, 1, &fset, argument);
Potem albo startujemy nową transakcję, albo oczekujemy funkcją systemową accept() na nadchodzące połączenie i przekazujemy je do trans_listen(), by sobie radziła.
Na czym testowałem?
Do przetestowania biblioteki napisałem prosty program, który przy pomocy transakcji rozproszonych próbuje skonstruować botnet. Pojedyncza instancja zakłada nowy botnet, natomiast kolejne mogą próbować podłączyć się do już istniejącego. Każdy węzeł botnetu zna adresy wszystkich innych i w procesie nawiązywania połączenia nowy węzeł musi otrzymać listę wszystkich takich adresów, zaś pozostałe węzły muszą dodać do swoich list adres nowego węzła. Brzmi skomplikowanie, ale w rzeczywistości wygląda prosto i co najważniejsze, świetnie nadaje się do przetestowania całego mechanizmu. Oto, jak wygląda proces łączenia:
- Nowy węzeł startuje jako koordynator transakcji i przyłącza do niej dowolny węzeł, który już należy do botnetu. Wraz z zaproszeniem przesyła swoje namiary.
- Wywołany do odpowiedzi węzeł dołącza do transakcji, a następnie przyłącza do siebie wszystkie pozostałe węzły botnetu, stając się tym samym koordynatorem podrzędnym. Pozostałe węzły otrzymują informacje o pojawieniu się nowego agenta i namiary na nie, które zapisują w tymczasowej lokalizacji.
- Wywołany do odpowiedzi węzeł przesyła do nowego po kolei adresy kolejnych węzłów.
- Gdy nowy węzeł odbierze ostatni pakiet, głosuje za zatwierdzeniem i przystąpieniem do głosowania.
- Jeśli wszyscy głosowali za zatwierdzeniem, każdy węzeł aktualizuje swoją mapę botnetu i tym samym nowy węzeł jest przyłączony.
- Jeśli ktoś głosował za odrzuceniem, węzły kasują tymczasowe struktury i powracają do pierwotnego stanu.
Przy okazji widać, że transakcje nie są tylko domeną środowisk bazodanowych - można je wykorzystać również w takich sytuacjach, jak przyłączanie nowego węzła lub administrowanie jakąś zdecentralizowaną siecią.
Zakończenie
Był to ostatni wpis poświęcony transakcjom rozproszonym. Po pierwsze, projekt już zakończyłem i zdobyłem swoje upragnione 5,25/5 punktów, a po drugie jest to praca uczelniana i nie mogę ot tak udostępnić kodu źródłowego (młodsze roczniki pewnie będą innego zdania :)), bez którego właściwie temat został wyczerpany. Zamierzałem pokazać, jak zabrać się za implementowanie czegoś takiego, jak rozwiązać napotykane przeszkody i podsunąć sugestie dotyczące projektu interfejsu. Ten cel został zrealizowany, tymczasem nie wykluczam napisania w najbliższej przyszłości bardziej składnego i kompletnego artykułu na ten temat. Trzeba jedynie dokończyć sesję i kupę innych rzeczy, które się przez cały ten semestr nawarstwiły...
