Shoda v DS

Shoda se stává důležitá v DS, kde různé části systému mohou udržovat kopie dat a informací.
Shoda je proces, kdy se všechny uzly v systému dohodnou na společném rozhodnutí nebo hodnotě.
Je potřeba zajistit, aby všechny kopie byly v souladu.
Shoda v systémech bez selhání, je velmi jednoduchá zjistit.

Skupiny

Zavedení redundance.
Úlohu uzlu převezme skupina uzlů.

Protokol primární-záloha

Hierarchická skupina.

Pracuje primární (zápisy).

Výpadek primárního $\to$ záloha převezme roli.

Protokol replikovaného zápisu

Plochá skupina.

Všichni stejná role.

Nemají kritický bod.

Nutná koordinace.

Shoda v systémech s možností selhání

Flooding consensus

Algoritmus sloužící k dosažení shody v DS.
Jedná se o jednoduchý přístup, kde každý uzel systému periodicky rozesílá svůj stav nebo informace o změnách všem ostatním uzlům ve svém okolí.
Tento proces se nazývá “flooding” (případně “epidemic dissemination”).
Fail-stop (ví kdo vypadl a umí s tím pracovat)

Postup:

V každém kole si aktivní uzly vymění své návrhy.

Každý uzel z návrhu deterministicky zvolí volbu.

Pokud někdo nedostane některou odpověď, začne nové kolo.

Všichni dostanou všechny odpovědi $\to$ volba $\to$ konec.

Paxos

Algoritmus pro dosažení shody v DS, i když se jednotlivé uzly mohou chovat nespolehlivě (např. mohou selhat nebo se zpozdit).

Předpoklady:

Máme částečně synchronní či zcela asynchronní DS, který nemá libovolné (byzantské) chyby.

Spoje mohou být nespolehlivé.

Operace jsou deterministické.

Chybné zprávy lze detekovat (Fail-stop).

Shoda je rozhodnutí většiny.
Tolerance $m$ chyb v $2 m + 1$ uzlech.
Principy fungování algoritmu Paxos jsou komplexní, ale základní kroky mohou být popsány následovně:

Zjednodušený Paxos algoritmus:

Fáze přípravy (Prepare Phase):

Proposer vyšle požadavek na acceptory s návrhem čísla (proposal number).

Číslo přípravy se skládá z dvou čísel:

Číslo instance

Unikátní identifikátor uzlu

Uzly odpovídají s informace o nejvyšším čísle přípravy, které dosud viděly a s hodnotou, pokud již nějakou mají.

Fáze přijetí (Accept Phase):

Pokud uzel obdrží dostatek odpovědí ve fázi přípravy, pokračuje fází přijetí.

Uzel požádá ostatní uzly o přijetí navrhované hodnoty a informace o čísle přípravy.

Uzly odpovídají buď potvrzením, že hodnota byla přijata, nebo odmítnutím s informacemi o nejvyšším čísle přípravy, které dosud viděly.

Fáze rozhodnutí (Decision Phase):

Pokud uzel obdrží dostatek potvrzení ve fázi přijetí, může rozhodnout o hodnotě, kterou předložil.

Pokud uzel obdrží odmítnutí nebo nedostatek potvrzení, musí zahájit nový pokus o dosažení shody s novým číslem přípravy.

Možné chyby:

Pokud selže uzel přijímající návrh, nic se neděje, dokud funguje většina.

Pokud selže navrhující uzel před návrhem, jeho roli převezme jiný uzel.

Pokud selže navrhující uzel v průběhu fáze přijetí, jiný uzel převezme jeho roli a v případě, že existuje alespoň jedna informace o návrhu (zpráva accept()), převezme ji.

Funguje i v případě, že více uzlů zahájí návrh, můžu ale dojít k livelocku. To se řeší volbou lídra (např. Bully, Raft, …)