Zaimplementowałem w Pythonie algorytm konsensusu Raft (sztandarowy przykład algorytmu rozproszonego). To dość kiepska implementacja! Ale też (do pewnego stopnia) poprawna.
Oto kilka uwag, którymi podzieliłbym się z każdym, kto chciałby podjąć podobne wyzwanie.
Z perspektywy czasu te materiały okazały się najbardziej przydatne do poznania Rafta i poprawnego zaimplementowania go.
- Artykuł opisujący Rafta (przeczytaj do sekcji 5 i często zaglądaj do rysunku 2)
- Przewodnik po Rafcie dla studentów
- jedna z najczęściej używanych implementacji Rafta
- sklonuj repozytorium, przejrzyj pobieżnie
raft.goi prowadź dialog z LLM-em, żeby zrozumieć kod i decyzje projektowe
- sklonuj repozytorium, przejrzyj pobieżnie
- Seria wpisów na blogu Eliego Bendersky’ego
Proponuję najpierw poświęcić mniej więcej godzinę na przeczytanie artykułu, a potem napisać szkielet kodu serwera UDP lub TCP, który odczytuje przychodzące bajty i dodaje je do tablicy. Następnie podążałem za implementacją Eliego, dodając funkcje do swojej implementacji Rafta w tej samej kolejności.
Gdy zaczęło działać coś przypominającego wybory lidera, zacząłem szukać błędów w kodzie i w swoim rozumieniu algorytmu. Wracałem na przemian do przewodnika dla studentów, rysunku 2 w artykule o Rafcie i swojej implementacji, dokładnie zastanawiając się, w których miejscach moja implementacja była zgodna z opisem (a w których się różniła). Intensywnie korzystałem też z LLM-a do przeglądu tego kodu, dodając do kontekstu materiały z powyższych źródeł.
Powtórz ten proces dla replikacji dziennika, trwałego zapisu danych itd.
w kwestii implementacji
W swojej implementacji podjąłem kilka decyzji upraszczających projekt. W przypadkowej kolejności:
- każdy węzeł działa i przetwarza komunikaty w jednym wątku
- użycie „zegara logicznego” do śledzenia lokalnego „czasu” w systemie (np. wywoływanie
tick()i zwiększanie licznika lokalnego dla każdego węzła zamiast korzystania z czasu systemowego) - „zagmatwanie” implementacji przez umieszczenie wszystkiego w jednym pliku, np. parsowania danych sieciowych, przechowywania/trwałego zapisu danych, głównego algorytmu Raft oraz narzędzi/poleceń do sterowania samym węzłem
Rozwiązanie z punktu 2 wydaje się rozsądną i poprawną decyzją projektową (zegary logiczne są wykorzystywane w implementacji etcd). Rozwiązanie z punktu 3 można uznać za lepsze do nauki/nauczania. Dobrze mieć wszystko w jednym pliku, żeby móc zobaczyć całość naraz; daje to też wygodną implementację, którą można rozłożyć na części i sprawdzić, jakie abstrakcje najlepiej pasują do algorytmu.
Wybór z punktu 1 uważam za dość rażący. Znacznie upraszcza implementację (mniej musisz się martwić o zakleszczenia i atomowe aktualizacje stanu wewnętrznego węzła), ale w rezultacie otrzymujesz coś, co nie do końca jest Raftem. Na potrzeby pierwszej implementacji wydaje się to w porządku. Algorytm jest wystarczająco skomplikowany i myślę, że wolisz poświęcić czas na debugowanie błędów logicznych w samym algorytmie Raft niż na zmagania z muteksami.
Traktowałbym implementację Rafta w ten sposób jako projekt na ~30 godzin. Wstępna lektura artykułu o Rafcie i przejrzenie powiązanych materiałów powinny zająć kilka godzin. Większość kodu napisałem w ~3 dni w czasie świąt, programując po około 6-8 godzin dziennie. W obecnej implementacji nadal mam kilka rzeczy do dopracowania i poprawienia (np. usunięcie kilku subtelnych błędów), co może zająć jeszcze pół dnia pracy.
W sumie całkiem nieźle jak na zrozumienie jednego z podstawowych algorytmów, na którym opiera się tak duża część infrastruktury.