V oblasti distribuovaných systémů je zásadní, aby se různé repliky dokázaly shodnout na jediném, konzistentním stavu událostí, a to i v případě selhání některých z nich. Pro tento účel se využívají konsensus algoritmy, které zajišťují, že systém nikdy nepřijme protichůdné hodnoty, a tedy se logy replik nikdy neodchýlí. Typické implementace konsensuálních systémů, jako jsou například distribuované úložiště klíč-hodnota, běžně spoléhají na zavedené algoritmy jako Raft, Paxos nebo Viewstamped Replication. Tyto algoritmy jsou dobře prozkoumané a v lokálních sítích fungují spolehlivě.
Nicméně, při nasazení v globálním měřítku, kde jsou systémy rozprostřeny přes kontinenty a propojeny sítěmi s vysokou a proměnlivou latencí, narážejí běžné konsensus algoritmy na zásadní problémy. Jejich závislost na jediném lídrovi, který je zodpovědný za pokrok systému, se stává Achillovou patou. Pokud lídr selže, zpomalí se nebo se odpojí, celý konsensus systém se buď zpomalí, nebo se stane nedostupným, dokud není zvolen nový lídr. Pro moderní distribuované systémy, které vyžadují nepřetržitou dostupnost, je tato situace nepřijatelná.
Jedním z klíčových problémů je tzv. destruktivní interference, která se projevuje, když se více procesů snaží současně dosáhnout konsensu. Vezměme si například algoritmus Paxos, který spočívá ve dvou fázích: navržení a přijetí. Pokud v průběhu těchto fází dva nebo více navrhovatelů souběžně odesílají své návrhy, mohou se navzájem blokovat, což vede k nekonečnému kolu soutěžení a ztěžuje pokrok systému. Aby se tomuto jevu předešlo, většina implementovaných konsensus algoritmů zavádí speciálního lídra, který je jediným oprávněným navrhovatelem. To sice urychlí rozhodování za stabilních podmínek, ale zároveň činí systém zranitelným vůči selhání lídra.
Když lídr selže, systém musí zvolit nového. Paradoxně, právě proces volby nového lídra často znovu zavádí destruktivní interferenci. Například v algoritmu Raft se kandidáti soutěží o většinu hlasů, a pokud se více kandidátů pokusí získat hlasy současně, mohou se vzájemně blokovat. To může vést k tzv. metastabilnímu selhání, kdy problém s volbou lídra přetrvává i poté, co původní příčina selhání (např. krátkodobý výpadek sítě) odezněla. Ideální konsensus algoritmus by se měl obejít bez složitých procesů obnovy, které jsou náchylné k interferenci a přispívají k výpadkům.
Dalším zásadním problémem je detekce chyb. V rozsáhlých, asynchronních sítích, jako je internet, kde zprávy nedorazí vždy v předvídatelném čase, je extrémně obtížné rozlišit mezi skutečným selháním serveru a pouhým zpožděním zprávy v síti. Detektory chyb tak musí „hádat“, zda je lídr v pořádku, nebo selhal. Chybný odhad spustí volbu nového lídra, což systém zastaví a zdrží pokrok. I když je detekce chyb přesná, je obvykle pomalá – časové limity pro detekci musí být nastaveny konzervativně vysoko, často na násobky latence sítě, což v globálních systémech znamená prodlevy v řádu sekund.
S ohledem na tyto výzvy byl vyvinut konsensus algoritmus QuePaxa, který byl publikován v roce 2023 výzkumníky Tennagem a Băsescem et al. QuePaxa je navržen tak, aby efektivně dosahoval konsensu v asynchronních prostředích, bez závislosti na přesném časování nebo bezchybné síti. Klíčovými principy QuePaxy jsou: volitelný lídr, úplné odstranění spoléhání na detekci chyb a návrh pro konstruktivní interferenci mezi navrhovateli, což znamená spíše spolupráci než soutěžení.
V QuePaxe existují navrhovatelé a zapisovatelé. Místo toho, aby si navrhovatelé konkurovali, kooperativně usilují o přijetí jediného návrhu. Každému návrhu je přidělena priorita (náhodné číslo), přičemž volitelný lídr má vždy nejvyšší prioritu. Když navrhovatel obdrží návrh s vyšší prioritou, přijme ho za svůj a začne ho sám šířit. Navrhovatelé tak společně konvergují k návrhu s nejvyšší prioritou, který je jim kolektivně znám. Tím se zabraňuje vzájemnému blokování a systém se může neustále posouvat vpřed, i když s náhodnou pravděpodobností v každém kole.
Lídr v QuePaxe je volitelný, avšak jeho přítomnost umožňuje rychlou cestu k rozhodnutí v jediném síťovém kole, pokud se jeho návrh rozšíří jako první. Klienti mohou posílat požadavky libovolnému navrhovateli, takže i když lídr selže, systém se nezastaví. Aby se využila tato rychlá cesta bez vytvoření jediného bodu selhání, klienti "zajišťují" své požadavky tím, že je posílají všem replikám. Ne-lídrovské repliky pak čekají na krátký "hedging" timeout, aby umožnily lídrovi rozhodnout. Pokud lídr v tomto čase nerozhodne, aktivují se ostatní navrhovatelé.

Potřebujete pomoc s webem nebo aplikací?
Ozvěte se mi — do 24 hodin se Vám ozvu zpět s návrhem dalšího postupu.
Tento "hedging" timeout se zásadně liší od časových limitů používaných pro detekci chyb v jiných algoritmech. Není svázán latencí sítě, ale je lokálně určen replikami a může být velmi krátký. Zatímco krátký časový limit v Raftu by systém zamrzl, v QuePaxe pouze zvyšuje počet aktivních navrhovatelů, což sice může zvýšit síťový provoz, ale umožní rychlejší reakci na změny stavu lídra. Díky tomuto přístupu QuePaxa proaktivně řeší selhání lídra zajišťováním (hedgingem), namísto reaktivní detekce chyb.
QuePaxa funguje ve fázích, které se opakují v kolech. Každé kolo se skládá ze čtyř fází. V první fázi (Propose and Adopt) navrhovatelé vybírají náhodné priority a šíří své návrhy. Pokud se návrh lídra (s nejvyšší prioritou) dostane k většině zapisovatelů jako první, lídr okamžitě rozhodne. Díky vlastnosti průniku většin je zaručeno, že žádný jiný návrh nemůže být přijat. Pokud rychlá cesta lídra selže, navrhovatelé v dalších fázích (Spread, Check and Decide, Carry Forward) spolupracují, aby konvergovali k nejlépe známému návrhu s nejvyšší prioritou. Toto postupné konvergování zajišťuje, že i při selhání prvního kola se práce neztrácí a systém se neustále posouvá k rozhodnutí.
V praxi bylo zjištěno, že systémy využívající QuePaxa průběžně zpracovávají požadavky, i když lídr selže, odpojí se nebo se zpomalí, aniž by se systém kdykoli úplně zastavil. Většina rozhodnutí, obvykle přes 95 %, je provedena lídrem v první fázi, což udržuje stabilní propustnost. V případech, kdy k rozhodnutí nedojde v první fázi, propustnost dočasně klesne, ale systém se pouze zpomalí, nikoli zastaví. QuePaxa také umožňuje dynamickou změnu lídra během provozu klastru bez výrazného dopadu na stabilitu systému. To potvrzuje, že QuePaxa je robustním a flexibilním řešením pro náročné globální distribuované prostředí.
