PARALELNÍ A DISTRIBUOVANÉ SYSTÉMY Flashcards
Algoritmy pro kritickou sekci
Kritická sekce - část kódu, kde více procesů společně přistupuje ke zdrojům. Je potřeba tuto sekci synchronizovat, aby nedošlo k nekonzistenci v datech.
Korektnost KS: - vzájemné vyloučení - KS nesmí být prokládána jiným procesem
- absence deadlocku - pokud 2 procesy chtějí současně vstoupit do KS, může vstoupit pouze jeden z nich
- absence vyhladovění - pokud chce 1 proces vstoupit do KS, musí se mu to časem podařit - nesmí ho ostatní procesy předbíhat.. korektnost silně závisí na férovosti.
Atomické operace - operace, která nelze nijak rozdělit na jiné podoperace - př. inkrementace vyžaduje načtení aktuální hodnoty, přičtení o 1, uložení nové hodnoty.
KS - vstupní protokol, kritická sekce, výstupní protokol
Dekkerův algoritmus
- wantA, wantB, turn
- pokud proces chce přejít do KS, musí počkat, až přijde jeho “kolo”
- vzájemné vyloučení splněno, problém nastává, pokud spolu procesy nesoutěží, může dojít k vyhladovění
- složitě se implementuje a je neefektivní
Složení atomických operací
- dosud byly atomické pouze čtení a zápis zvlášť, pokud však HW a SW umožňuje, může být čtení se zápisem 1 atomická operace
- výrazné usnadnění, ale nutná podpora HW i SW
- dostáváme test&set, fetch&add, exchange, compare&swap
- slouží k vytvoření vyšších synchronizačních operací, př. semaforů nebo zámků
Petersonův algoritmus - tie breaker
- vychází z Dekkerova algoritmu, cyklus a await složeny do jednnoho await
- await wantB = false and or last = 2
- proměnná last - kdo poslední nastavil proměnnou last, musí počkat
- korektní i když je await rozděleno na neatomické operace
- zobecnění na n procesů komplikované
Bakery algoritmus - přiřazování pořadových lístků
- před vstupem do KS se procesu nastaví pořadové číslo (nejvyšší + 1)
- await dokud pořadové číslo druhého procesu nebude nula, nebo pokud nemáme nižší číslo. po KS se nastaví na 0.
- lze zobecnit na n procesů pomocí pole pořadových lístků
- elegantní, ale hledání nejvyššího pořadového čísla je pomalé
Realita, praxe - je za potřebí vyšších synchronizačních nástrojů, atomické operace jsou nedostatečné
Semafory
- Synchronizační nástroj, který slouží k řízení sdílených prostředků
- Jednoduše: obsahuje hodnotu, znázorňující dostupnost prostředků a operace ke
zvyšování a snižování této hodnoty - typy semaforů:
- obecný (hodnota semaforu N čísla, řídí přístup k více instancím prostředku)
- binární {0;1} (chová se jako zámek, mutex)
- implementace:
- aktivní - aktivní čekání
- pasivní - uvažuje stav procesů (záležitost OS), může dojít k vyhladovění, nutná
férovost plánování, používá oproti aktivní impl. frontu procesů
Proměnná S, S.V - hodnota semaforu
Operace: Signal(S), Wait(S)
Algoritmus pro KS pak vypadá následně:
NS
wait(S)
KS
signal(S)
Aktivní implementace:
Wait(S):
await S.V > 0
S.V ← S.V - 1
Signal(S): (obecný)
S.V ← S.V + 1
Signal(S): (binární)
if S.V = 0:
S.V ← 1
Pasivní implementace (použ. frontu procesů S.L a nastavuje jejich stav)
Wait(S): (proces A)
if S.V > 0:
S.V ← S.V - 1
else:
S.L ← S.L U A
A.state ← blocked
Signal(S): (obecný)
if S.L = empty:
S.V ← S.V + 1
else:
B ← libovolný proces z S.L
S.L ← S.L - B
B.state ← ready
Signal(S): (binární)
if S.V = 0:
if S.L = empty:
S.V ← 1
else:
B = lib. ze SL
SL -= B
B.state = ready
Monitory
- Monitor je synchronizační nástroj vyšší úrovně abstrakce než semafor
- automaticky zajišťuje vzájemné vyloučení při přístupu ke všem svým metodám
- uvnitř monitoru může být definovaná kritická sekce, přístupná pouze jednomu vláknu v daný okamžik
- velmi podobné třídám v OOP - zapouzdření se zámkem zajišťujícím synchronizovaný přístup
- v OOP jsou chráněné objekty, které rozšiřují monitory. V některých jazycích jako JAVA jsou chráněné objekty realizovány klíčovým slovem synchronized
Monitor obsahuje:
- sdílené proměnné - stav monitoru
- operace (metody) - definují přístup k proměnným
- synchronizační mechanismus (zajišťuje vzáj.vylouč a správu čekajících procesů)
Implementace:
- pasivní čekání - monitor má uvnitř frontu blokovaných procesů čekajících na splnění podmínky
- synchronizace s použitím podmíněné proměnné mimo monitor - přináší problémy a nutná další synchronizace
Příklad pasivní implementace:
monitor Counter:
int count = 0
procedure Increment():
count = count + 1
procedure Get():
return count
Tento příklad ukazuje pasivní implementaci monitoru, protože:
-Monitor uchovává stav (hodnotu proměnné count) a poskytuje metody pro bezpečný přístup ke sdíleným datům.
-Fronta blokovaných procesů (pokud by byla potřebná) je implicitně spravována monitorem, což je typické pro pasivní implementaci.
Podmíněná proměnná:
- wait, signal, empty
- Význam funkcí:
Wait
Používá se, když proces potřebuje čekat na splnění určité podmínky.
Proces je přesunut do fronty čekajících procesů na podmíněné proměnné a je zablokován, dokud jiný proces nezavolá Signal.
Signal
Informuje jeden proces čekající na podmíněné proměnné, že podmínka byla splněna, a odblokuje jej.
Pokud žádný proces nečeká, signál se “ztratí”.
Empty
Kontroluje, zda je fronta čekajících procesů na podmíněné proměnné prázdná.
Pomáhá při rozhodování, zda je potřeba poslat Signal.
Rozdíl mezi semaforem a monitorem:
wait signal
semafor nemusí blokovat vždy má efekt
monitor vždy blokuje nemusí dělat nic při prázdné frontě
Bariéry
Synchronizační mechanismus, který v paralelních či distribuovaných systémech zajišťuje, že vlákna, či procesy budou moci pokračovat, dokud všechny nedokončí svoji část, neboli nedorazí k bariéře
- nejedná se o primitivum, ale o princip řešení
Implemenace:
- sdílený čítač - centralizovaná bariéra - jakmile vlákno skončí, čítač se inkrementuje a
vlákna aktivně čekají, dokud čítač nenabyde zvolené hodnoty
- čekání zatěžuje paměť, nevhodné pro distribuované systémy
- koordinátor a vlajky - procesům se nastavuje vlajka, flag arrive / continue podle toho,
zda může či nemůže pokračovat- když proces dorazí do bariéry, nastaví se vlajka na arrive (připraven)
- po dosažení všech, koordinátor nastaví vlajky procesům na continue
- řešení lze hierarchicky implementovat na různé úrovně pro
distribuované systémy
Druhy bariér:
Stromově kombinovaná bariéra
- procesy uspořádány do stromové struktury
- synchronizace probíhá hierarchicky podle stromové struktury, nejdříve se synchronizují listy, pak vnitřní uzly a nakonec kořenové
- kořenové procesy nejvíce čekají, vnitřní uzly odvádějí nejvíce práce, listové procesy - 3 druhy procesů
- doba synchronizace je díky stromové struktuře logaritmická
- vylepšení - střídání arrive a continue bez resetování
(+) škálovatelnost
Symetrická bariéra
- procesy se synchronizují přímo mezi sebou bez hierarchie, důležitá komunikace mezi sebou pomocí vlajek a koordinátora nebo sdílené proměnné
- procesy mají stejný (symetrický) kód
Motýlí bariéra
- počet procesů mocnina dvojky
- synchronizace probíhá v úrovních
- počet synchronizačních kroků je logaritmický vůči počtu procesů
- př “proces 1 je synch s procesem 5 přes 2”
- nakreslit schéma
Diseminační bariéra
- rozšíření motýlí bariéry, pro počet procesů který není mocnina dvojky
- výhodou je, že nemusíme používat zbytečné procesy navíc oproti motýlí
- v každém kroku probíhá párové předávání informací o dosažení bariéry, dokud nejsou všechny procesy informovány
- vhodné pro distribuční systémy s omezenou komunikací
Datově paralelní algoritmy
- pro paralelní aplikace, kde jednotlivé procesy pracují na více částech stejného pole
- bariéra zajišťuje, že každý proces splní svou část, než se bude moct postoupit dále
- iterativní výpočty, nebo v počítačové grafice flood-fill, kde více procesů současně zaplňuje jeden prostor
SIMD - stejné instrukce, stejný takt
MIMD - různé instrukce, různý takt - potřeba synchronizace
Klasické paralelní problémy
Problémy, které simulují klasické synchronizační situace, ke kterým v paralelních, či distribuovaných systémech dochází během přístupu ke sdíleným zdrojům
- je potřeba zajistit koordinaci a synchronizovat přístup.
Producent-Konzument
P - produkují předměty, konkrétně naplňují pole
K - konzumují předměty, konkrétně odebírají prvky z pole
Pole je většinou velikostně omezeno.
Problémy:
- producent nesmí produkovat, pokud je pole plné
- konzument nesmí konzumovat, pokud je pole prázdné
Řešení tohoto problému lze provést přes semafory a to tak, že vytvoříme semafory coby ukazatele, zda je pole prázdné, či plné.
notEmpty, notFull
Producent před produkováním zavolá wait(notFull), přidá produkt, poté signal(notEmpty). Konzument využívá semafory naopak. Mimo konzumaci, či produkci se ještě aktualizuje index pole.
Příklad: Tisková fronta - tiskárna je konzument, uživatelé jsou producenti, přidávají požadavky do tiskové fronty. Pokud je fronta prázdná, tiskárna netiskne, pokud je fronta plná, uživatelé nemohou přidávat požadavky.
Čtenář-písař
Č - čte ze sdíleného zdroje, v jeden okamžik může číst více čtenářů, celá třída se však vzájemně vylučuje s písaři
P - zapisuje do pole, v jeden okamžik může pracovat pouze jeden písař, vzájemné vyloučení s ostatními písaři
Semafory - semafor pro čtenáře, písaře avšak navíc musíme udržovat počet čtenářů, což je proměnná a její inkrementace či dekrementace je kritická sekce, takže potřebujeme ideálně ještě semafor, který bude vzájemně vylučovat čtenáře
písař
wait W, wait R
write()
signal R, signal W
čtenář
čeká jestli jsou ostatní čtenáři manipulují s počítadlem
přičte +1, signalizuje, že přestal manipulovat
čte ze sdíleného zdroje
a jak skončí, tak opět wait, dekrementuje - a pokud je počet čtenářů nulový, tak signalizuje písaři, že může vstoupit. až poté signalizuje, že přestal manipulovat s proměnnou
Příklad: Systém rezervace hotelů - čtenáři jsou uživatelé prohlížející nabídky a do role písaře se dostává ten, kdo v daný moment provede změnu v databázi. Problém nastává, pokud by čtenář zobrazil volný pokoj, zatímco písař zároveň změnil jeho stav. Synchronizace zajišťuje konzistenci dat.
Večeřící filozofové
- simuluje případ, kde více procesů přistupuje ke společným omezeným zdrojům
- teoreticky zajímavý problém, v praxi však moc nepoužívaná, protože je to nehygienické (pauza pro smích)
- protože se jedná o pozičně závislé zdroje, v praxi většinou jsou zdroje na jedné hromadě
- 5 filozofů, 5 vidliček
- každý filozof buď EAT() - potřebuje obě vidličky vedle sebe
nebo THINK() - přemýšlí a má položené obě vidličky
Nabízí se více řešení:
- pravděpodobnostní - jíst bude ten, komu padne pozitivní hod mincí, může dojít k vyhladovění (doslova)
- implementace číšníka, proces, který bude určovat pořadí - když však číšník pracuje, tak filozofové nedělají nic, takže je to celkem neefektivní
- semafor(vidlička) - nefunguje
- semafor(místnost) - omezuje počet procesů, ale dostatečně efektivní řešení
pokud je filozofů 5, room se nastaví na 4
think()
wait(room)
wait(left)
wait(right)
eat()
signal(right) - opačné pořadí, protože umožní jíst někomu, kdo už levou vidličku drží
signal(left)
signal(room)
Příklad: Zpracovávání plateb mezi účty. Vidličky jsou v tomto případě účty a filozofové jsou transakce mezi nimi. Transakce musí zajistit korektnost dat při převodu, proto by měl k jednomu účtu přistupovat najednou pouze jeden filozof.
Vlastnosti a architektury distribuovaných systémů
DS jsou soustavy nezávislých uzlů (počítačů), které spolupracují jako celek
- sdílená paměť, navenek vypadají jako jeden systém
- z určitého pohledu jsou speciální případ paralelních systémů
Vlastnosti / problémy v DS, které je potřeba řešit:
Komunikace - jelikož uzly se nacházejí na různých fyzických místech, musí komunikovat přes síť, což přináší různé výzvy - latence, zpoždění zpráv, ztráta zpráv
Koordinace - potvrzování zpráv
- problém 2 generálů - chtějí se domluvit na čase spol. útoku, vyšlou posla - co když se posel nevrátil? - byl zajat na cestě tam? zpět? nebo druhý generál nemá zájem o spolupráci?
- v DS je absence úplné jistoty potvrzení pokud používáme pouze zprávy
Škálovatelnost - systém musí být schopen přidávat nové uzly, nárůst výkonu s přidáváním nových uzlů však není lineární
- zatímco přidání 2. uzlu může zdvojnásobit výkon, protože pro komunikaci potřeba nízké režie komunikace, 100 uzlů už nemusí představovat výkon 100x větší, protože může docházet k zahlcování sítě, potřeba synchronizovat přístup ke společným zdrojům, což zpomaluje celý systém
- uzly stejné API - přidání nového uzlu nemusí vyžadovat změnu systému
Přizpůsobivost - schopnost reakce na chyby, výpadky uzlů, výpadky sítě - systém musí být schopen dynamicky se přizpůsobovat
Architektury DS
Layer based - vrstvená architektura, uzly využívají služeb spodních vrstev a poskytují služby horním - př. MVC - oddělení logiky od uživ. rozhraní
Object based - uzly jsou objekty, které si posílají zprávy
Resource based - zaměřuje se na společné zdroje, které mají své specifické rozhraní, př. sem patří REST API
Event based - uzly reagují na události systému, koordinace oddělena od výpočtu
Typy organizace uzlů:
P2P - decentralizovaná organizace - uzly jsou rovnoprávné
- vysoká škálovatelnost a odolnost vůči selhání
- složitější správa a zabezpečení
př. torrent, blockchain
Klient-Server - centralizovaný systém - klienti odesílají požadavky, server na ně reaguje službami
- hůře škálovatelné - kapacita systému
- server je potenciální bod selhání
- jednoduchá správa a zabezpečení
- př. web, databáze
Komunikace:
Remote Procedure Call - klient posílá synchronně zprávy na vzdálený server
- efektivní, ale komplikované, nutná podpora infrastrukturou
Zasílání zpráv - uzly si vyměňují zprávy asynchronně pomocí komunikačních kanálů
- jednodušší a používané
Multicast - jeden uzel vyšle jednu zprávu, která se doručí více uzlům
- vhodné při live streamování, či videokonferencích
Chord Systém
- distribuovaná hash tabulka, používaná v P2P systémech k efektivní distribuci a vyhledávání dat
- má kruhovou topologii, aneb všechny uzly jsou uspořádány do pomyslného kruhu (propojeny, nikoliv fyzicky) - nakreslit na tabuli? porovnat s centralizovaným systémem
- každý uzel uchovává hashovou look up tabulku, které se říká finger table (FT).
- každý datový prvek má přiřazený jedinečný klíč a je spravován uzlem s nejbližším větším ID, tomuto uzlu, se říká successor (následník)
- toto rozložení dat mezi všechny uzly zajišťuje vyvážené rozložení dat mezi uzly
Výhody - škálovatelnost - snadné přidávání nových uzlů
- odolnost - díky redundantnímu ukládání dat
- jednoduchost - snadná impl. a správa
Princip
- Vyhledávání klíče - uzel dostane požadavek na klíč, zjistí, zda je daný klíč v jeho rozmezí, pokud ne, předává požadavek vedlejšímu sousedovi
- nakonec se buď odešle daný klíč, pokud nalezen, jinak se oznámí, že daný klíč není v systému obsažen
- Odebírání uzlu - uzel dostane požadavek na odebrání, informuje sousedy a své klíče pošle vyššímu sousedovi, který sjednotí přijatou množinu klíčů se svojí
- nižší soused tuto informaci využije k aktualizaci odkazu na následující sousední uzel
- Přidávání uzlu - uzel si vypočítá požadované místo v chord systému a informuje nové sousedy. Klíče s menším ID než daný nový uzel jsou odebrány vyššímu sousedovi.
Reálné využití - sdílená úložiště - torrentové systémy
- distribuovaná úložiště - rozložení a správa dat v cloudu
- blockchain - základní vrstva pro organizaci uzlů
Koordinace času v DS
- v DS je důležité zajistit synchronizaci času mezi uzly, protože z důvodu absence globálních hodin, neboli každý uzel má své vlastní lokální hodiny, které se můžou odchylovat (clock drift)
- to může způsobovat nekonzistence událostí, chyby časových razítek a nesoulad při zpracovávání dat
- synchronizace času znamená snížení rozdílu v hodinách dvou procesů
Cristianův algoritmus
- pro synchronizaci hodin mezi klientem a serverem
- klient pošle požadavek na server v čase T1, server mu odpoví Tserver a tuto zprávu obdrží v čase T2
- klient pak musí vypočítat čas s ohledem na kompenzaci trvání přenosu zpráv
RTT - round trip time - (T2 - T1)/2
- jednoduché a efektivní, ale problém nastává, když délka přenosu je asymetrická nekonzistentní a velká
NTP (Network time protokol)
- hierarchický protokol, obsahující úrovně pro různé uzly - Stratum
- lvl 1 atomické hodiny, velmi přesné referenční hodiny
- lvl 2 servery synchronizované s ref. hodinami
- lvl 3 - klienti a servery synchronizované s vyšší úrovní
- hodně podobný Cristianovu alg.
- k posílání dotazu na čas se připojí časové razítko odeslání zprávy klientem t1. server obdrží zprávu v čase t2 a odešle v čase t3. klient obdrží v čase t4.
- RTT se počítá následně: (T4-T1)-(T3-T2)
- celková odchylka se počítá RTT / 2
- velmi efektivní a přesné v globálních sítích
Berkleyho algoritmus
- pro synchronizaci v decentralizovaném systému mezi více uzly, které nemají přístup k referenčním hodinám
- zvolí se lídr/koordinátor, který periodicky zjišťuje čas všech uzlů, vynechá extrémní odchylky a spočítá jejich průměr
- poté spočítaný průměr posílá všem uzlům, které si podle toho upraví své hodiny
- proč to funguje - často nejde o přesný čas, nýbrž o posloupnost operací
Posloupností operací bez ohledu na čas se zabývají Logické (Lamportovy) hodiny.
- každý uzel má svůj čítač, na počátku nastaven na nulu
- při každé události se čítač inkrementuje
- s každou zprávou se posílá i hodnota čítače
- přijímací uzel pak svůj čítač nastaví na maximum svého čítače a přijatého čítače ve zprávě
- pokud má být událost A před B, tak L(a) < L(b) (hodnoty čítače uzlů)
- pokud jsou hodnoty stejné, tak se pořadí provede podle ID
- toto však nezaručuje úplnou kauzalitu
- úplnou kauzalitu řeší Vektorové hodiny, kde je čítač vektor velikosti počtu uzlů
- každý uzel přičítá svou hodnotu vektoru
- pokud jsou vektory reprezentující události neporovnatelné, tak jsou tyto události nezávislé - neexistuje mezi nimi kauzální vztah
—–A(1,0,0)—-B(2,0,0)—————————————-
——————————-C(2,1,0)————–D(2,2,2)—-
—————E(0,0,1)——————F(2,1,2)—————–
Volba lídra v DS
Volba lídra je klíčovým procesem v decentralizovaných distribuovaných systémech
Lídr - koordinátor/iniciátor, který plní specifické úkoly a řídí koordinaci systému
- má na starost synchronizaci, řízení operací a přidělování sdílených zdrojů
- uzly se mezi sebou musí domluvit, kdo bude lídr
- každý uzel musí vědět, kdo je aktuální lídr
- při selhání uzlu, který byl lídr, tak se musí zvolit nový
Při přístupu ke společným zdrojům musí být zajištěno vzájemné vyloučení, které může být bez lídra:
- token based - uzly si předávají token, který umožňuje přístup
- permition based - uzel musí požádat ostatní o povolení - ostatní uzly musí souhlasit
- pokud je však lídr zvolen, tak rozhodování bývá přímočaré
- nejznámější algoritmy pro volbu lídra jsou:
Bully alg
- uzel detekuje selhání aktuálního lídra
- zahájí volby tím, že všem ostatním uzlům (často pouze s větším ID) pošle svoje ID
– pokud nikdo neodpoví, aktuální uzel je nový lídr
– pokud odpoví uzel s vyšším ID, tak se chopí iniciativy a volby pokračují
- volba typu “starší má přednost”
(+) jednoduchá implementace
(–) u větších systémů může dojít k zahlcení sítě
Ring alg
- používá se k volbě lídra v kruhových topologiích¨
- uzel detekuje selhání, zahájí volby tím, že na tzv. volební lístek napíše své ID a pošle ho svému sousedovi
- ten buď pošle dál ve směru kruhu, nebo má možnost lístek přepsat svým ID
- takto to pokračuje dál, dokud se lístek nevrátí původnímu uzlu, který volby zahájil
- ten oznámí výsledek
- pokud se zahájí více voleb současně, výsledek by měl být vždy stejný
- pokud potenciální lídr odejde (uzel selže/odpojí), zahájí se nové volby
(+) dochází k méně zaslaným zprávám než u Bully alg
- může se používat stejný systém typu starší má přednost, ale často je vhodné zohlednit i vlastnosti uzlu, jako Polohu, výkon, latenci atd.
Volba lídra v ad hoc sítích
- ad hoc sítě nemají žádnou konkrétní topologii, každý uzel se může připojit či odpojit dynamicky
- uzel, který detekuje selhání lídra, zahájí volby zprávou ELECTION svým sousedům
- uzel, který přijme zprávu E poprvé, nastaví odesílatele jako svého rodiče a zprávu přepošle svým sousedům - přijetí zatím nepotvrzuje
- uzel, který obdrží zprávu ELECTION od jiného uzlu než svého rodiče, pouze potvrdí příjem
- pokud všechny sousedé mají nastaveny svoje rodiče, daný uzel se stává listovým a pošle svým rodičům informace o svých vlastnostech - výkon, polohu, stav baterie atd.
- takto sestaveným stromem se propaguje pouze informace nejlepší volby až ke zdrojovému kořenovému uzlu
- ten po obdržení vyhodnotí výsledek voleb a nominuje nového lídra
Shoda v DS
Důležitý problém v DS, týkající se dohody mezi uzly o společném rozhodování, přestože některé uzly můžou selhat a komunikace může být nespolehlivá.
- pokud by komunikace byla bez selhání, tak je shoda snadná, jenže problém nastává, když uzel selže a pak se obnoví bez informací, které systémem kolují
Problematika:
Rozdělení znalostí - žádný uzel nemá informace o stavu celkového systému
Asynchronní komunikace - zpoždění zpráv, ztráta, špatné pořadí
Selhání - uzly mohou selhat
Přístupy:
Flooding consensus - fail stop model - předpokládá, že uzly muhou selhat, ale pokud selžou, přestanou komunikovat - absence byzantských chyb - nereálné
- každý uzel může navrhnout nějakou hodnotu, odešle ji všem ostatním
- každý uzel přepošle hodnoty dál do sítě, dokud všechny uzly nemají všechny hodnoty
- poté každý uzel provede předdefinovanou rozhodovací funkci (deterministická volba) př. max value, max id
- všechny uzly které nezkolabovaly pošlou stejnou hodnotu
- pokud se nevrátí odpověď od všech uzlů, tak se přechází do druhého kola, dokud nedojde k úplné shodě
Paxos algoritmus
- rodina algoritmů pro řešení shody v DS typu, poprvé publikovaná Leslie Lamportem
- fail noisy model - stačí většinová shoda, povoluje až m selhání v 2m+1 uzelech
- funguje na nespolehlivých spojích
- uzly mohou mít 3 role - navrhovatel, akceptor a learner - více než jednu
- navrhovatel navrhne hodnotu, přijímací uzly hlasují, pokud více než polovina akceptuje, je dosaženo shody
(+) robustní
(–) velmi složité na implementaci
Raft alg. - o dost jednodušší než paxos, moderní, podobné reálným volbám
- volí se lídr a ostatní jsou následovníci
- vede se záznak operací, log, pokud se uzly dokážou shodnout na logu, tak se shodnou i na aktuálních hodnotách
- lídr o sobě dává pravidelně vědět signálem o tom, že je naživu tzv heartbeat
- př 100 ms, pokud uzel nedostane signál, že je leader naživu, tak začne volby a prohlásí se za kandidáta. aby kandidáti nebyli všichni, heartbeat je randomizovaný s malými odchylkami
- ostatní uzly volí mezi kandidáty podle velikosti logu - seznamu provedených operací
- při přidávání nového záznamu do logu pak lídr nejprve appenduje bez commitu a zeptá se ostatních na jejich stav logu.
- pokud většina odpoví, že zprávu obdržela, leader vyšle signál pro commit
- pokud však uzel odpojen a připojen s neaktuálním logem, lídr posílá ztracené záznamy, dokud nedojde ke shodě, vždy po dvou - poslední z předchozím, pokud uzel hází error, tak indexy záznamů dekrementuje
Tolerance chyb v DS
- obecně se může pokazit hodně - v DS více než v PS
- správně navržený DS by měl být schopen určité množství chyb zvládat, tolerovat a minimalizovat jejich dopad
Požadované vlastnosti DS:
- DOSTUPNOST - systém musí být dostupný v čase aspoň 90-99 % času (výpadky 36 - 3,6 dnů v roce)
- SPOLEHLIVOST - systém musí fungovat správně i v přítomnosti chyb (pokud uzel selže, jiný za něj musí převzít zodpovědnost)
- BEZPEČNOST - při chybách nesmí dojít ke katastrofám (ztráta dat, nalomení bezpečnosti)
- UDRŽITELNOST - systém musí být schopen chyby postupně opravovat (snadná oprava -> větší udržitelnost)
Klasifikace chyb:
fail-stop, stop chyba - uzel selže a přestane odpovídat - snadno detekovatelné
chyba času - uzel odpoví až po požadovaném termínu
chyba vynechání - selže odpověď, nebo příjem a uzel vynechá zaslání paketu př
chyba odpovědi - uzel pošle nesprávnou odpověď - chybná operace
byzantská (lib) chyba - těžko detekovatelná, uzel se chová nepředvídatelně, útočník s ním může manipulovat
Fail-stop - okamžité ukončení, spolehlivá detekce chyby
Fail-noisy - okamžité ukončení, detekce nespolehlivá
Redundance - základní nástroj / přístup při navrhování DS pro zvýšení tolerance chyb
- informační - kopie dat je uložena na více místech (uzlech)
- fyzická - kopie serveru, disků, záloha
- časová redundance - operace jsou opakovány v čase pro zvýšení pravděpodobnosti úspěchu
Tolerance byzantských chyb - nejhůře detekovatelné, uzel záměrně či nezáměrně může chybovat a nedojde k jeho selhání, útočník se takto může pokoušet manipulovat se systémem
- algoritmy pro toleranci byzantských chyb - za předpokladu, že chybuje méně než třetina, aby rozhodla většina a je potřeba exponenciální nárůst zpráv, což je velmi nákladné a zvyšuje to režii
- elektronické podpisy - uzly kontrolují věrohodnost zpráv
- replikační protokoly - požadavky jsou ověřovány více uzly
Replikace a konzistence v DS
Replikace dat v DS znamená, že jsou data uložena (replikována) na více uzlech
- hlavní důvody jsou:
– robustnost - odolnost vůči chybám
– rozložení zátěže systému - více uzlů zvládne obsloužit více požadavků
Chain replikace - řetězová replikace - změny dat probíhají zřetězením uzlů, kde každý uzel předá změny dalšímu
(+) zjednodušení replikace a správy konzistence
(+) změny se provádějí ve stejném pořadí
(–) zpomalení - změny musí projít postupně
(–) pokud jeden uzel selže, ohrozí to celou replikaci
Pokud však máme stejná data replikovaná na více uzlech - jak zajistíme jejich aktualizaci a shodnost? - tím se zabývá konzistence
Konzistence - neboli odpověď na otázku: “mají všechny uzly stejná data?”
Typy konzistencí:
**silná konzistence ** - model systému, kde každý uživatel při čtení dostane nejaktuálnější data. vhodný pro systémy, kde je požadovaná vysoká konzistence, ale při výpadku či zpomalení sítě je často obětovaná dostupnost a výkon
(+) máme jistotu, že máme shodná data
(–) nerozložená zátěž, neefektivní
(–) kvůli latenci lídr už nemusí být lídr, ověřování zpomaluje
**sekvenční konzistence **
- vhodné pro systémy, kde není nutná okamžitá konzistence dat
- uživatelé nemusí vidět stejná data, ale změny budou ve stejném pořadí
- změny se šíří postupně
- A 5 -> 10 -> 15, tak jiný uzel uvidí změnu z 5 na 10 a pak na 15 i když ne ihned
(+) vyšší výkon za cenu občasné nekonzistence
** eventuální konzistence** - zaručuje, že data budou časem konzistentní, jen ne ihned. oproti sekvenční konzistenci nezaručuje ani pořadí, pokud jsou aktualizace rychle po sobě.. slabší model, kde není potřeba aktuálnost ani sekvence - př. počet lajků na sociálních sítích
Replikace zvyšuje dostupnost a rychlost systému, ale přináší komplikace s konzistencí. Výběr strategie je vždy kompromis mezi rychlostí a přesností.
CAP teorém
Consistency - každé čtení vrátí výsledek posledního zápisu / chybu
Availability - na každý dotaz vrátí odpověď
Partition tolerance - systém bude pokračovat i při výpadku, zdržení, či ztrátě dat
Teorém říká, že každý DSystém může zajistit maximálně dvě záruky z těchto tří.
Jelikož odolnost proti výpadku je důležitá, systémy často volí mezi konzistencí a dostupností - CP a AP systémy. CP - Google spanner / AP - Cassandra - OpenSource správce DB
PACELC teorém - rozšíření CAPu
…Každý systém odolný proti výpadkům (P) volí mezi Dostupností (A) a konzistencí (C), ale jinak (E), pokud systém běží bez výpadků, stále volí mezi latencí (L) a ztrátě konzistence (C). (Nízká latence - rychlost odpovědí, nebo konzistence, ale synchronizace dat mezi uzly systém zpomaluje)
CALM teorém - Consistency and Logical Monotonicity
Říká, že logicky monotónní programy lze snadno implementovat s eventuální konzistencí, neboli nemonotónní programy nevyžadují koordinace a tím dosahují vyšší latence.
Monotónní program je program, kde přidání nových dat nezpůsobí změnu předchozích dat ani odstranění. Nově přidané informace ho pouze rozšiřují.
CALM teorém říká, že u takových programů není potřeba velké koordinace pro zachování konzistence.
Blockchain
- technologie, představující distribuovanou účetní knihu umožňující decentralizované ukládání a dat
- poprvé představena už v roce 1991, ale zpopularizována díky bitcoinu, který byl implementován a popsán v roce 2009 anonymním tvůrcem podepsaným jako Satoshi Nakamoto
- dnes je blockchain využívám nejen kryptoměnami, ale i v lékařských záznamech, účetnictví, volbách, DNS a dalších..
- blockchain představuje zřetězení bloků, kde každý blok musí být validován, aby mohl být do blockchainu přidán. Blockchain v bitcoinu obsahuje historii všech transakcí od počátku až do současnosti.
- blok obsahuje data, v podobě jejich hashe, časové razítko a hash předchozího bloku - ten zajišťuje bezpečnost tím, že pokud by někdo s blokem manipuloval, změnil by se tím hash a tím by neodpovídal hashi následujícího bloku, který se na něj odkazuje - útočník by tedy musel přepsat všechny následující bloky a přesvědčit všechny ostatní uzly, že ten jeho blok je ten správný - což stojí spoustu elektřiny a navíc je to vysoce nepravděpodobné díky složitosti šifrovací funkce SHA256
Problémy blockchainu
- kdo bude validovat?
- jak zabezpečit, aby nikdo nepodváděl?
- validace těchto bloků je v podstatě řešení složitého matematického úkolu - s adaptivní obtížností nastavující tak, aby validace jednoho bloku trvala v průměru 10 minut - proof of work
- úkol - přijít na hash, který bude mít určitý počet nul na jeho začátku - ověření snadné, ale není inverzní
- validátoři se nazývají mineři a dostávají odměnu v bitcoinu za každý validovaný blok. odměna se každé 4 roky snižuje na polovinu, nyní je to 3.125
- postupně snižovaná inflace
- v btc jsou transakce uspořádany do tzv - merkle tree - hashovací stromy - každý list je hashován, každý rodič obsahuje hash jeho potomků až po merkle root - opakované aplikování hashovacích funkcí - v btc merkle list představuje jednotlivé transakce
Shoda - každý uzel pak obdrží signál o novém řetězci - pokud uzel obdrží více verzí blockchainu, vybere ten delší - za kterým je více práce
- pokud obdrží dva různé, stačí chvíli počkat, ten správný řetězec poroste - nový blok nemusí být věrohodný, ale pokud je dostatečně vzdálen, můžeme si být jistí, že je legitimní
problémy bitcoinu:
- postupná centralizace
- 51% útok
- omezený počet transakcí v bloku
