BALLAST: Gdy bandyta uczy bazę danych jak długo czekać

Wyobraź sobie, że jesteś liderem zespołu. Wysyłasz wiadomość i czekasz na odpowiedź. Jak długo czekasz, zanim uznasz, że kolega “zniknął”? Za krótko — i panikujesz bez powodu. Za długo — i cały projekt stoi. BALLAST to system, który uczy bazy danych odpowiadać na to pytanie automatycznie, używając technik uczenia maszynowego.

Problem: Protokół Raft i jego achillesowa pięta

Raft to protokół konsensusu — sposób, w jaki rozproszone bazy danych (jak etcd, Consul, CockroachDB) uzgadniają, kto jest “liderem” i jakie dane są aktualne. Działa tak:

1. Jeden węzeł jest liderem — przyjmuje zapisy
2. Pozostałe węzły to followerzy — replikują dane
3. Jeśli follower nie słyszy od lidera przez pewien czas (election timeout), rozpoczyna nowe wybory

Problem? Ten “pewien czas” to zazwyczaj losowa wartość z przedziału, np. 150-300ms. I tu zaczynają się kłopoty.

Dlaczego losowe timeouty zawodzą?

W stabilnej sieci lokalnej (LAN) losowe timeouty działają świetnie. Ale w rzeczywistości:

• Sieci WAN mają zmienne opóźnienia (czasem 10ms, czasem 500ms)
• Pakiety giną — szczególnie przy przeciążeniu
• Opóźnienia są skorelowane — jak jest źle, to dla wszystkich naraz
• Węzły są różne — jeden na szybkim serwerze, drugi na przeciążonej maszynie

Rezultat? Split votes — sytuacja, gdy kilka węzłów jednocześnie startuje wybory i żaden nie wygrywa. System staje się niedostępny na sekundy, czasem minuty.

Rozwiązanie: Niech maszyna sama wybiera timeouty

BALLAST (Bandit-Assisted Learning for Latency-Aware Stable Timeouts) zamienia statyczne heurystyki na bandytów kontekstowych — algorytmy, które uczą się wybierać najlepszą opcję na podstawie kontekstu.

Bandyty kontekstowe w pigułce

Wyobraź sobie automat do gier z wieloma dźwigniami (ramionami). Każda daje różną nagrodę. Nie wiesz, która jest najlepsza — musisz eksplorować. Ale też chcesz zarabiać — więc musisz eksploatować to, co już wiesz.

Bandyta kontekstowy idzie dalej: przed każdym wyborem widzi “kontekst” — np. aktualny stan sieci. I uczy się, że w tym konkretnym kontekście najlepiej zadziała ta konkretna dźwignia.

Jak BALLAST używa bandytów?

1. Ramiona (arms): Dyskretne wartości timeoutu do wyboru (np. 100ms, 150ms, 200ms, 300ms)
2. Kontekst: Aktualne warunki sieci — opóźnienia, utrata pakietów, historia ostatnich wyborów
3. Nagroda: Szybkość powrotu do stabilności, minimalizacja czasu niedostępności
4. Algorytm: Wariant LinUCB — liniowy bandyta z górnym przedziałem ufności

$$ a_t = \arg\max_a \left( \theta_a^\top x_t + \alpha \sqrt{x_t^\top A_a^{-1} x_t} \right) $$

gdzie $x_t$ to wektor kontekstu, $\theta_a$ to nauczone wagi dla ramienia $a$, a drugi człon to “bonus eksploracyjny”.

Bezpieczna eksploracja

Tu jest haczyk: eksplorowanie w systemie produkcyjnym może być niebezpieczne. Co jeśli bandyta wybierze bardzo krótki timeout podczas chwilowego przeciążenia sieci? Kaskada niepotrzebnych wyborów.

BALLAST wprowadza risk-capping — ograniczenie ryzyka podczas niestabilnych okresów:

• Gdy system jest niestabilny, bandyta działa konserwatywnie
• Eksploracja odbywa się głównie w “spokojnych” momentach
• Górne i dolne limity na wybierane timeouty

Wyniki: Liczby mówią same za siebie

BALLAST testowano w symulacji dyskretno-zdarzeniowej z realistycznymi scenariuszami:

Scenariusze testowe

Główne wnioski

1. Drastyczna poprawa w trudnych warunkach WAN — znacznie krótszy czas niedostępności
2. Brak regresji w łatwych przypadkach — na stabilnym LAN działa tak dobrze jak standardowe podejście
3. Adaptacja w czasie rzeczywistym — system uczy się na bieżąco, nie wymaga ręcznego tuningu

Dla kogo to jest?

Dla inżynierów systemów rozproszonych

Jeśli budujesz lub utrzymujesz systemy oparte na Raft (etcd, Consul, TiKV, CockroachDB), BALLAST pokazuje, że:

• Domyślne timeouty to tylko punkt startu
• ML może znacząco poprawić dostępność w trudnych warunkach
• Warto monitorować częstotliwość split votes

Dla badaczy ML

Ciekawy przypadek użycia bandytów kontekstowych:

• Środowisko niestacjonarne (warunki sieciowe się zmieniają)
• Wymóg bezpieczeństwa (safe exploration)
• Dyskretna przestrzeń akcji z ciągłym kontekstem

Techniczne szczegóły

Dla zaawansowanych — kluczowe elementy:

Przestrzeń ramion jest dyskretyzowana — zamiast wybierać ciągłą wartość timeoutu, bandyta wybiera z ustalonego zbioru (np. 8-16 opcji). Upraszcza to uczenie i zapewnia stabilność.

Kontekst obejmuje:

• Średnie opóźnienie RTT z ostatnich N pomiarów
• Wariancję opóźnień
• Liczbę ostatnich nieudanych wyborów
• Czas od ostatniej stabilnej kadencji lidera

Aktualizacja modelu odbywa się online, po każdej obserwacji. Nie wymaga treningu offline ani zbierania danych historycznych.

Podsumowanie

BALLAST pokazuje eleganckie połączenie dwóch światów: teorii uczenia maszynowego (bandyty kontekstowe) i inżynierii systemów rozproszonych (protokół Raft). Zamiast ręcznie dobierać timeouty i mieć nadzieję, że zadziałają w każdych warunkach, system sam uczy się optymalnych wartości.

To ważny kierunek: coraz więcej “magicznych stałych” w systemach rozproszonych może być zastąpionych adaptacyjnymi algorytmami ML.

Własna implementacja: Symulator w Rust

Żeby lepiej zrozumieć działanie BALLAST, zaimplementowałem własny symulator dyskretno-zdarzeniowy w Rust. Projekt porównuje dwie strategie wyboru timeoutów:

• Random: Klasyczne losowe timeouty (150-300ms) jak w standardowym Raft
• BALLAST: LinUCB bandyta kontekstowy adaptujący timeouty do warunków

Wyniki symulacji

BALLAST redukuje całkowitą niedostępność klastra o 84%!

Co pokazuje symulacja?

Najciekawsze obserwacje:

1. WAN Bursty (+90.8%): W scenariuszu ze skorelowanymi burstami opóźnień, BALLAST uczy się używać długich timeoutów (300-1000ms), podczas gdy Random ciągle “panikuje” z krótkimi timeoutami.

2. Heterogeneous (+69.4%): Gdy węzły mają różną wydajność, BALLAST adaptuje się do wolniejszych węzłów.

3. Stable conditions (~12%): Nawet w stabilnych warunkach jest niewielka poprawa — BALLAST szybko znajduje optymalny timeout.

Struktura projektu

src/
├── bandit.rs      # Implementacja LinUCB
├── network.rs     # Symulacja sieci (6 scenariuszy)
├── raft.rs        # Uproszczone węzły Raft
├── strategy.rs    # Strategie (Random, BALLAST)
├── simulation.rs  # Silnik symulacji
└── main.rs        # CLI i porównanie

Uruchomienie

git clone https://github.com/mysma-9403/BALLAST-Simulator
cd raft-ballast-sim
cargo run --release

Kod źródłowy: GitHub

📎 Linki

• Na podstawie publikacji 📄 2512.21165
• Implementacja symulatora: GitHub