Přehled látky probrané na přednášce Principy distribuovaných systémů.

{{Not_complete}}

Distribuovaný systém

Distribuovaný systém je takový systém propojení množiny nezávislých uzlů, který poskytuje uživateli dojem jednotného systému.

  • distribuovaný OS

  • vrstva middleware nad obyčejným OS

Motivace

  • ekonomika - lepší poměr výkon/cena

  • výkon - technologické limity

  • distribuovatelnost

  • spolehlivost - výpadek jednoho uzlu

  • rozšiřitelnost - snazší přidání uzlu

Cíle

  • transparentnost - přístupová, lokační, migrační, replikační, perzistentní, konkurenční, paralelismová

  • přizpůsobivost - autonomie, decentralizované rozhodování, otevřenost, migrace procesů a prostředků

  • spolehlivost - teorie: nespolehlivost jednoho serveru 1% => nespolehlivost čtyř serverů 0.01^4 = 0.00000001

  • výkonnost - teorie: více uzlů -> vyšší výkon, praxe: výrazně nižší než lineární nárůst výkonu

  • rozšiřitelnost - vyhnout se čemukoliv centralizovanému

Architektury

  • multiprocesory (sdílí paměť)

    • bus - synchronizace cache (max. 64 uzlů)

    • switched - crosspoint switch (kvadratický počet přepínačů), omega network (n log n)

  • multicomputery (vlastní paměť, výrazně nižší komunikace)

    • bus - propojeny obyčejnou sítí

    • switched - mřížka, hyperkrychle

  • hybridní - NUMA

Komunikace

  • absence sdílené paměti -> zasílání zpráv

  • potřeba jednotného mechanismu komunikace pro celý systém (lokální, rychlá síť, vzdálená síť, ...)

  • klient-server model, request/reply protokol - synchronní/asychronní čekání na požadavek/odpověď

  • přímé zasílání, zasílání zpráv přes schránku

  • přímé a nepřímé adresování (linky a porty)

  • T/TCP - odlehčené protokoly pro lokální sítě, vyšší výkon, složitější zotavování z chyb

  • ztráta zprávy -> typické řešení: potvrzování, timeout, opakování; ACK, NAK, AYA, IAA, CON, TRA, ...

  • dlouhé zprávy -> burst (buřty) - potvrzuje se dávka paketů

    • pevné dávky - při vyšší zátěži sítě velká chybovost, při volné síti nízká výtěžnost

    • dynamické dávky - velikost na základě úspěšnosti předchozích přenosů

  • idempotentní služba - nevadí opakované provedení služby, sečti 1+1

  • sémantiky zpracování

    • exactly once (ideální, obecně nelze zajistit)

    • at-least-once

    • at-most-once

  • spolehlivost serveru

    • ztratila se zpráva se žádostí

    • ztratila se zpráva s odpovědí

    • server je příliš pomalý nebo zahlcen

    • server nefunguje

  • havárie klienta

    • exterminace - klient po zrození sám zruší službu

    • reinkarnace - klient nastartuje novou epochu, předchozí epochy server zruší

    • expirace - kvantum času

RPC

(Remote Procedure Call)

  • volání vzdálené služby stejné jako zavolání podprogramu

  • síťová komunikace se před programátorem schová, zařídí ji překladač (u klienta i serveru)

  • stub - vygenerovaný kód pro zavolání vzdálené služby, přilinkuje se při kompilaci klienta

  • skeleton - vygenerovaný kód pro zpracování požadavku, přilinkuje se při kompilaci serveru

  1. Klientova funkce normálním způsobem zavolá klientský stub

  2. Stub vytvoří zprávu a zavolá jádro

  3. Jádro pošle zprávu jádru počítače, kde běží server

  4. Vzdálené jádro předá zprávu stubu serveru / skeletonu

  5. Stub rozbalí parametry a zavolá server

  6. Server zpracuje požadavky a normálním způsobem se vrátí do stubu

  7. Stub zabalí výstupní parametry do zprávy a zavolá jádro

  8. Jádro pošle zprávu klientovu jádru

  9. Klientovo jádro předá zprávu stubu

  10. Stub rozbalí výstupní parametry a vrátí se ke klientovi

  • server se zviditelní na directory serveru

  • použití IDL (Interface Description Language) - definice rozhraní, ze které se pak vygeneruje kód stubu a skeletonu

  • problémy:

    • reprezentace dat (marshalling) - endiany, kódování, floaty

    • globální proměnné

    • ukazatele a dynamické struktury

    • předávání polí

    • variabilní parametry

    • odlišná sémantika při vzniku chyb, bezpečnost

Skupinová komunikace

  • jeden odesílatel, více příjemců

  • atomicita - doručení všem nebo nikomu

  • synchronizace - doručování od různých odesílatelů

    • neexistence sdílené paměti - zprávy

    • rozprostřená informace mezi několika uzly

    • rozhodování na základě lokálních informací

    • vyloučení havarijních komponent

    • neexistence společných hodin

  • adresování - adresa skupiny, seznam příjemců, predikátová adresace (v kombinaci s předchozími)

  • technicky - unicasty, multicast, broadcast

  • uzavřené (koop. alg.) x otevřené skupiny (replikované služby)

  • flat x hierarchická (přes koordinátora)

  • doručovací protokol: 1. příjem, 2. doručení

  • jeden uzel může být ve více skupinách, překrývající se skupiny, změna členství

  • vnitřní uspořádání skupin - všechny procesy rovnocenné, hierarchické uspořádání, koordinátor skupiny

Fyzické hodiny

  • UTC

  • požadovaná odchylka δ -> intervaly max. δ/2ρ ; ρ = míra přesnosti

  • Cristianův algoritmus - jeden pasivní timeserver, periodické dotazy na aktuální čas, ošetření komunikační prodlevy

  • Berkeley algoritmus - aktivní timeserver, periodicky se ptá ostatních na rozdíl času, počítá průměr, vrátí rozdíl

  • distribuovaný algoritmus - resynchronizační intervaly pevné délky, broadcast, zahození extrémů, spočítání průměru

  • intervalový čas - čas není okamži, ale interval; někdy nelze porovnat

Logické hodiny

  • důležité pořadí, nikoliv přesný čas, nekomunikující procesy nemusí být sesynchronizovány

  • relace předchází

  1. a, b události v jednom procesu, a se udělá před b, pak a->b

  2. send(m)->recv(m)

  3. tranzitivita

  • jestliže a -> b, pak C(a) < C(b) (zúplnění pro C(a)=C(b) - byrokratické uspořádání podle PID)

  • synchronizace logických hodin

    • odesílatel - ke zprávě přiloží svou časovou značku

    • příjemce - zvýší si svou značku, pokud je < než značka zprávy: T = max (T, Tm + 1)

Kauzální závislost

  1. jestliže ex.p: e1 ->p e2, potom e1 -> e2

  2. send(m)->recv(m)

  3. tranzitivita

  • zpráva B je kauzálně závislá na A, jestliže A mohla ovlivit obsah B (jestliže byla na uzel doručena před odesláním B)

    • není důležité, zda byla zpráva ovlivněna, ale že mohla být ovlivněna

  • konkurentní události - e1 není kauzálně závislá na e2 a e2 není na e1

  • jestliže a -> b, pak C(a) < C(b), opačne ne

Vzájemné vyloučení

  • centralizovaný algoritmus - centralizovaný server s frontou, žádost / potvrzení / zamítnutí / uvolnění, problém s výpadkem serveru, klienta (starvation)

  • Lamportův algoritmus - proces vyšle žádost a čeká až dorazí potvrzení od všech procesů a všechny žádosti v jeho frontě mají větší časovou značku, po uvolnění KS se posílá release zpráva

  • Ricart & Agrawala

    • když chce proces vstoupit, pošle všem žádost se svou TM a čeká na všechna potvrzení

    • proces, který přijme žádost

      • nechce vstoupit ani není v KS -> pošle potvrzení

      • je v KS - zařadí žádost do fronty, po výstupu z KS pošle potvrzení všem ve frontě

      • není v KS, ale chce taky - pokud má jeho žádost nižší značku, zařadí do fronty a neodpovídá, jinak pošle potvrzení

  • naivní volby - potřeba nadpoloviční většina hlasů, deadlock pokud 2 procesy dostanou stejně hlasů, posílá se žádost o hlasy, ostatní odpovídají, pokud jejich hlas je Available, po výstupu z KS se posílá release zpráva

  • Maekawa

    • volební okrsky - pro vstup do KS je potřeba získat všechny hlasy z okrsku

      • každé 2 volební okrsky musí mít společného alespoň jednoho kandidáta

      • všechny okrsky stejně velké

      • každý proces ve stejném počtu okrsků

      • složitost O(K), K = velikost okrsku, cíl minimalizovat K

    • prevence deadlocku

      • p má volný hlas: potvrzení ACKr

      • p dal již hlas jinému procesu q s TSq < TSr: zařadit do fronty

      • p dal již hlas jinému procesu q s TSq > TSr: pošle zprávu REJECT procesu q

        • pokud již q je v kritické sekci (dostal všechny potřebné hlasy), odpoví až po opuštění kritické sekce

        • pokud q ještě nemá všechny hlasy, vrátí hlas procesu p a ten ho předá procesu r

  • token ring - proces vlastnící peška může vstoupit do KS, problémem ztráta peška a výpadek procesu

Volba koordinátora

  • bully algoritmus

    • koordinátorem se má stát proces s nejvyšším ID

    • nějaký proces zašle zprávu procesům s vyšším ID

    • pokud přijde odpověď, vzdává se

    • pokud nepřijde nic, stává se novým koordinátorem a zašle zprávu o výsledku všem

    • při příjmu zprávy o volbě každý proces zašle žádosti všem vyšším procesům (volba ve dvou kolech)

    • při překročení timeoutu možnost více koordinátorů

  • invitation algoritmus

    • nejsou požadavky na spolehlivost a dobu odezvy

    • koordinátor je vázán na skupinu, skupiny se mohou dle situace štěpit nebo spojovat

    • koordinátor pravidelně všem posílá AYC (AreYouCoordinator)

    • pokud déle nepřijde AYC od mého koordinátora, prohlásím se za koordinátora své skupiny

    • když koordinátorovi přijde AYC jiného koordinátora, spojí se do jedné skupiny toho vyššího, koordinátoři pošlou zprávu členům své původní skupiny ať se připojí do nové

  • kruhový algoritmus

    • rozhodnu se volit, pošlu zprávu následníkovi

    • zpráva obsahuje čísla procesů - odesílatel a nejvyšší živý

    • když mi zpráva přijde po kruhu zpět, koordinátorem určím proces s nejvyšším ID a rozešlu všem zprávu

    • stačí znát následníky a mít možnost zjistit následníka nedostupného uzlu

Doručovací protokoly

  • globální uspořádání - zprávy jsou doručovány v pořadí odeslání, nelze bez existence globálních hodin

  • sekvenční uspořádání - všechny uzly doručí zprávu ve stejném pořadí, nezávisí nutně na času odeslání

  • kauzální uspořádání

    • kauzálně vázané zprávy ve správném pořadí, konkurentní zprávy v libovolném

    • dest(m) množina procesů, kterým je zaslána zpráva m

    • deliverp(m) je událost doručení zprávy m procesu p

    • m1 -> m2, pak pro každé p z průniku dest(m1) a dest(m2) platí deliverp(m1) ->p deliverp(m2)

  • total-order protokol

    • všechny zprávy doručeny všem ve stejném pořadí

    • při příjmu zprávy potvrzení odesílateli TSAi

    • odesílatel po příjmu všech potvrzení odešle finalizační zprávu TSF = max(TSAi)

    • po příjmu finalizační zprávy příjemce doručí zprávy podle TSF

Vektorové hodiny

  • kauzální doručování

  • vektor délky N (= počet uzlů), v každé složce čas daného uzlu

  • když 2 vektory nejsou porovnatelné, jedná se o konkurentní zprávy

  • před odesláním zvýším svůj TS o 1, ke zprávě přiložím vektor

  • před přijetím čekám, než můj vektor bude větší nebo roven vektoru zprávy ve všech složkách kromě odesílatele (tam může být zpráva o jednu větši)

  • po přijetí svoje zvýším na maximum (ze svého vektoru a vektoru zprávy) po složkách

  • pro překrývající se skupiny: u zprávy posílám vektory všech skupin, kde jsem; při příjmu kontroluji kauzalitu i pro všechny skupiny, kde jsem (kromě té odesílatele, kde u něj může být větší o jedničku)

Virtuální synchronie

Group view – množina uzlů ve skupině (též group membership, delivery list, etc). Značí se L (globální), L<sub>i</sub> (lokální verze procesu i), L<sup>x</sup> (verze pohledu x), L<sub>i</sub><sup>x</sup>

Algoritmus spolehlivého doručování je virtuálně synchronní, když:

  1. všechny uzly ve skupině udržují stejný L

  2. pokud je zpráva m odeslána skupině s L<sup>x</sup> před změnou na L<sup>x+1</sup>

    • buď m doručí všechny uzly z L<sup>x</sup> před provedením změny na L<sup>x+1</sup>

    • nebo žádný uzel z L<sup>x</sup>, který provede změnu na L<sup>x+1</sup>, zprávu m nedoručí

Přitom nemusí platit, že přijetí zprávy členem L implikuje doručení všem členům L (nespolehlivost, havárie odesílatele).

Když se uzly B a C dozvědí, že uzel A přestal být členem jejich skupiny, už od něj pak nemůžou přijímat skupinové zprávy.

Spolehlivé kauzální doručování

  • flooding algoritmus

    • při příjmu každé doposud nepřijaté zprávy ji každý uzel přepošle všem ostatním, spolehlivý, neefektivní

  • trans algoritmus

    • p rozesílá Ack(m) když přijal m a všechny kauzálně předcházející zprávy

    • graf kauzality G celé skupiny, graf přijatých zpráv, ale ještě nestabilních Gp

    • ack_list, nack_list - seznam zpráv pro potvrzení / nepřijatých zpráv

    • undelivered_list – seznam přijatých, ale ještě nedoručených zpráv

    • implementace:

      • příjem potvrzení a výpočet vlastních potvrzení

      • detekce nepřijatých zpráv

      • ukládání zpráv a detekce stabilních zpráv

    • jestliže procesor havaruje, paměťová náročnost je neomezená :( -> potreba doplnit o změnu členství ve skupinách

  • transis algoritmus

    • rozšíření trans o členství ve skupinách

    • při detekci havárie zpráva FAULT(q), při přijetí její přeposlání

    • zprávy kauzálně závislé na nějaké FAULT zprávě pozdržet do dalšího pohledu, pokud víc FAULT zpráv a zpráva závislá jen na jedné z nich, tak doručit

    • zprávy od odesílatele, který spadnul a které jsou kauzálně vázané na nějakou FAULT zprávu nebo jsou k ní konkurentní zahodit, doručit jen ty co byly odeslány před detekcí havárie

  • ISIS protokol

    • maticové hodiny

    • každý proces zná vektor všech ostatních procesů: VTpi[j] - co ví proces i o procesu j (pokud i=j tak je to počet odeslaných zpráv)

    • při příjmu zprávy od pi k pj: VTpj[j][i]=VTm[i], VTpj[i][]=VTm[]

    • členství ve skupinách - každý proces udržuje všechny nestabilní zprávy, při příjmu view change zprávy pošle všechny nestabilní a pak flush, po příjmu flush od každého procesu instaluje nový pohled (každý proces udržuje seznam havarovaných procesů, s každou zprávou se odesíla, zprávy od havarovaných procesů se zahazují)

Ukončení distribuovaného procesu

  • Dijkstra-Scholten algoritmus

    • strom

      • každý listový proces po ukončení pošle zprávu otci, ten propaguje výš po zjištění ukončení všech synů

      • signál o ukončení dostane iniciační proces od všech synů -> konec

    • DAG

      • na každé hraně deficit (#došlých zpráv - #signálů)

      • končící proces vyšle každým signálním kanálem tolik signálů, aby deficit byl všude 0

    • obecný graf

      • problém - nejsou listy

      • při výpočtu vytvoření kostry grafu - otec = uzel od kterého přišla první zpráva

      • algoritmus ukončení pro jeden proces:

        1. Poslat signál podél všech vstupních hran kromě hrany k otci

        2. Čekat na signál od všech výstupních hran

        3. Poslat signál otci

Detekce globálního stavu

  • množina událostí v systému E = {e}

  • řez c je rozdělení E na Pc a Fc : Pc u Fc = E & Pc průnik Fc = 0

  • konzistentní řez c : a -> b & a leží v Fc, pak b leží v Fc

  • stav (distribuovaného) procesu je množina událostí, které se v procesu udály

  • konzistentní stav S = Pc, kde c je konzistentní řez

  • využití:

    • distribuovaná detekce deadlocků

    • distribuovaný garbage collection

    • detekce ukončení distribuovaných výpočtů

    • obecně detekce globálních vlastností

  • stav uzlu = množina přijatých a odeslaných zpráv

  • stav kanálu = množina zpráv, které byly kanálem odeslány, ale ještě nebyly doručeny

  • Distributed snapshot algoritmus

    • iniciátor vyšle všem výstupním uzlům značku

    • při příchodu první značky ji rozešlu na výstupy a zapamatuji si svůj stav (přijaté a odeslané zprávy do tohoto okamžiku)

    • u příchozích kanálů, od kterých mi ještě značka nepřišla, si pamatuji příchozí zprávy (až do okamžiku, než mi i tímto kanálem přijde další značka)

    • zprávy mezi první značnou a další značkou z příchozího kanálu jsou stav toho kanálu

    • algoritmus končí po příchodu všech značek

Distribuovaný konsensus

  • problém 2 armád - početnější armáda musí zaútočit synchronizovaně, aby mohla vyhrát - řešení neexistuje

Problém byzantských generálů

  • uzly mohou havarovat a chovat se zákeřně

  • C1: všichni loajální důstojníci vydají stejný rozkaz

  • C2: je-li generál loajální, pak každý loajální důstojník vydá rozkaz generála

  • 3 uzly, 1 zrádce - řešení neexistuje

  • 4 uzly

    • zrádce generál

      • 2 stejné rozkazy - důstojníci se rozhodnou pro většinový rozkaz (C2)

      • 3 různé rozkazy - důstojníci se dohodnou, že generál je zrádce (C1)

    • zrádce důstojník - loajální důstojníci dostanou vetšinu správných rozkazů (C2)

  • pro m zrádců existuje řešení pro n ≥ 3m+1 uzlů

  • konsensus s nezfalšovatelnými zprávami - všichni přeposílají zprávu tak jak ji dostali, obsahuje i předchozího odesílatele -> loajální uzly se shodnou na majoritní nebo defaultní hodnotě

Klasifikace problémů distribuovaného konsensu

  • byzantský konsensus - iniciátorem rozesílaná hodnota

  • konsensus - každý má svou iniciální hodnotu

  • interaktivní konzistence - loajální se musejí shodnout na vektoru loajálních

Distribuovaná sdílená paměť

Konzistence bez SP

  • striktní

    • všechny zápisy okamžitě všude viditelné

    • podmínka: musí existovat přesný globální čas -> v DS téměř nemožné

  • sekvenční

    • výsledek stejný, jako by procesory běžely v nějaké sekvenci a každý procesor běžel podle programu

    • může dát různé výsledky při spuštění stejného programu (není zaručeno zpoždění)

    • signatura = výstupy procesů v pevně daném pořadí, ne všechny odpovídají sekvenční konzistenci

    • dokázáno r+w>=t, čili pokud optimalizujeme pro čtení, zápis bude pomalý

    • snadno implementovatelné

  • kauzální

    • kauzálně vázané zápisy (P1:W(x), P2:R(x),W(y)) musí být vidět ve stejném pořadí

    • implementace vyžaduje graf závislostí zápisů na čtení

  • PRAM

    • zápisy jednoho procesu viděny v pořadí v jakém byly provedeny, zápisy různych procesů konkurenční

    • příklad se zabitím obou procesů

    • snadná implementace

  • slow memory

    • zápisy jedním procesem do jednoho místa musí být viděny ve stejném pořadí

Konzistence se synchronizační proměnnou

  • předchozí modely příliš restriktivní, ne všechny aplikace vyžadují sledování všech zápisů, natož pak jejich pořadí, typická situace: proces v kritické sekci ve smyčce čte a zapisuje data

  • řešení: nechat proces ukončit kritickou sekci a poté rozeslat změny ostatním

  • speciální druh proměnné - synchronizační proměnná (synchronizační operace)

  • slabá konzistence (weak)

    1. SP sekvenčně konzistentní

    2. na SP se sahá až skončí všechny předchozí zápisy

    3. na data se sahá až skončí všechny přístupy k SP

  • výstupní konzistence (release)

    1. před přístupem ke sdílené proměnné musí být úspešně dokončeny předchozí Acq()

    2. před Rel() musí být ukončeny všechny předchozí zápisy a čtení procesu

    3. Acq() a Rel() musí být PRAM konzistentní

    • při správném párování Acq a Rel je výsledek ekvivalentní sekvenční konzistenci

    • eager release consistency - vše se propaguje po Rel(), optimalizace přístupové doby

    • lazy release consistency - vše se sosá před Acq(), optimalizace síťového provozu

  • vstupní konzistence (entry)

    • přístup k datům a SP může být exkluzivní (RW) nebo neexkluzivní (RO)

    • každá SP má vlastníka (proces, který k ní naposledy přistupoval)

    • proces, který není vlastníkem, musí žádat o vlastnictví

    1. Acq() až po aktualizacích všech chráněných dat

    2. exkluzivní přístup k SP jen když nikdo jiný nepřistupuje ani neexkluzivně

    3. po exkluzivním přístupu si příští přístup musí vyžádat kopii od vlastníka

Distribuované stránkování

  • přístup k nenamapované stránce - přerušení, obsluha, načtení

  • problémy:

    • replikace x konzistence - namapování read-only, synchronizační akce při zápisu, invalidace, aktualizace

    • nalezení stránky - broadcast, centralizovaný manager, replikovaný manager

    • správa kopií - broadcast, copyset

    • uvolňování stránek - které

    • falešné sdílení (nezávislá data na stejné stránce)

  • sekvenčně konzistentní

    • pro zápis musím být jediný vlastník

  • kauzálně konzistentní

    • vektorové hodiny pro stránky a procesy

    • při zápisu se zvýší TS stránky i procesu, při přenosu stránky se přiřadí procesu max, při zvýšení TS procesu se zneplatní stránky s nižším TS ve svém políčku

Distribuované sdílené proměnné

  • knihovny (typicky se SP, eliminace falešného sdílení, nepodporováno OS, závislé na jazyku, nutnost rekompilace, Munin -- read only, migratory (eager release), write-shared (dirty copy on write, po release se propaguje, při konfliktu dirty/dirty porovnání a případný pád)... konvenční sdílená (single writer, many readers -- jako distrib. stránkování, sekvenční konzistence)

  • distribuované objekty (základní distribuovaný předek, pak potomci, class definition language -- automatické generování kódu, middleware: CORBA, Java RMI)

Identifikace

  • který objekt (identifikace), kde je (adresa), jak se k němu dostat (cesta)

  • aktivní (vlastní kod - agenti, procesy) x pasivní (obsluhovány cizím kódem - souboru, kanály, ...)

  • uživatelská jména (občas čitelné i pro člověka) x systémová (porty, desciptory, lidsky nečitelné)

  • nestrukturovaná jména x strukturovaná jména (absolutní x relativní) x popisná (atribut = hodnota)

  • dynamická jména (deskriptory otevřených objektů) x statická (jména souboru) + převody mezi nimi (freeze/melt)

  • capability x ACL

  • rozsah platnosti (local/global)

Kapability

  • jednoznačná identifikace objektu a přístupu (user nemůže měnit ani generovat)

  • k jednomu objektu typicky více kapabilit (vlastník, písař, čtenář)

  • +: snadný test oprávěnosti přístupu, každý správce prostředků může nadefinovat vlastní druhy práv

  • -: těžko zjistit seznam oprávněných uživatelů, problém odejmutí práva, kontrola propagace

  • kapabilita s podpisem - podpis vygenerován z identifikace objektu a práv, celé zašifrováno tajným klíčem (nutnost ochránit podpisovou funkci)

  • kapabilita s redundancí

    • server port (dostatečně náhodné číslo) a ID objektu volně přístupné

    • práva + náhodně vygenerovaná hodnota, zašifrovaná práva a generovaná hodnota

    • služba serveru - vygenerování kapability s menšími právy

Distribuovaná správa jmen

  • namesever - publikace kapabilit, reg - žádosti o otevření kanálu

  • spojení NS a FS - NS("a/b/c") -> FS("b/c") ...

  • oddělený NS a FS - NS("a/b/c")="cap 1234" -> FS("cap 1234")

  • adresáře - položky typu <jmeno,hodnota> (hodnota může být číslo, odkaz na trvalé objekty, na živé objekty, na adresáře)

Detekce deadlocků

  • detekce horší než lokálně

    • distribuovaný Wait-For-Graph (WFG)

    • každý existující deadlock je v konečném čase detekován, detekovaný deadlock musí existovat

  • modely deadlocku - single, and, or, and-or, m out of n model

  • pštrosí algoritmus

    • deadlock se neřeší, nechává se to na uživateli

  • centralizovaný algoritmus

    • přenos informací - po každé změně, v intervalech, na požádání

    • kauzální doručování proti falešnému uváznutí

    • hierarchický - podřízení si svoje deadlocky řeší sami, nadřízení řeší problémy, které podřízení nevidí

  • path-pushing

    • uzly spravují lokální kusy WFG

    • sousedním uzlům zasílání externí závislosti

    • phantom deadlock s cyklem mezi uzly?

  • edge-chasing

    • pošlu zprávu všem, na které čekám, pokud se vrátí, pak deadlock

    • ale mezitím se to ale mohlo odblokovat (řešení - aging, overkill - zpráva zároveň hledá kandidáta)

  • diffusing computation

    • nalezení cyklu v distribuovaném výpočtu = konec

  • detekce globálního stavu

    • při příjmu značky proces zaznamená lokální WFG

    • existuje-li deadlock, tak je v konzistentím řezu

    • při příjmu značky uzel zaznamenává lokální WFG, externí závislosti poslány iniciátorovi

Distribuované hashovací tabulky

  • hašovací tabulky (pole) rozprostřeno mezi více uzly, každý uzel spravuje svoji část, rozdělení množiny klíčů mezi účastnické uzly

  • uložení a vyhledání prvku znamená směrovat dotaz k uzlu, který spravuje danou oblast

  • Peer-to-Peer sítě

    • strukturované - založené na DHT, mají pevnou strukturu, která je využívána ke směrování, směrovací tabulky, problémem připojení a odpojení uzlu

    • nestrukturované - záplavové hledání nebo náhodná procházka, problémem vyhledávání a směrování

  • prvek S je přiřazen uzlu, jehož ID je nejblíže K(S) (funkce vzdálenosti)

  • příslušný uzel je buď vlastníkem klíče anebo zná uzel, který je ke klíči blíže (všichni nemusí vědět o všech)

  • odpojení uzlu - jeho oblast přejde na sousedy

  • připojení uzlu - sousední uzly mu předají část své oblasti

  • Content-Addressable Network

    • prostor klíčů je d-rozměrný kartézský souřadnicový systém

    • souřadnice bodů v prostoru představují klíče

    • prostor rozdělen na zóny, každá přísluší jednomu uzlu

    • každý uzel si drží ukazatele na sousední

    • připojení - uzel si zvolí bod v prostoru (vlastní ID), kontaktuje uzel dané oblasti, dohodne se s ním na rozdělení

    • odpojení - dohodne se s nějakým sousedem na spojení oblastí

  • Chord

    • klíče jsou m-bitová čísla uspořádaná do kružnice

    • měří se vzdálenost dvou klíčů na kružnici ve směru hodinových ručiček

    • funkce následník(K) - vrací identifikátor uzlu, který je rovný nebo větší K

    • klíč k je uložen na uzlu následník(k)

  • Pastry

    • klíče jsou m-bitová čísla rozdělená na sekvenci číslic o základu 2<sup>b</sup>

    • uzel směruje zprávu tomu uzlu, jehož id sdílí s klíčem prefix, který je nejméně o jednu číslici delší než prefix, který sdílí klíč s aktuálním uzlem

    • každý uzel má leaf set L = množina uzlů, které jsou numericky nejbližší jeho id

  • Kademlia

Vzdálené spouštění procesů

  • nalezení volného počítače

  • znalost vlastní zátěže

  • spuštění vzdáleného procesu - transparentnost, přenesení kód a dat, vytvoření prostředí odpovídající domovskému PC (kontexty, systémová volání - přesmerovat x vzdálená)

  1. volný počítač se zaregistruje do registru

  2. domovský počítač žádá o nějaký volný registr

  3. alokace procesoru na volném počítači

  4. odregistrování volného z registru

  5. nastavení prostředí

  6. nastartování procesu

  7. běh procesu

  8. ukončení procesu

  9. zpráva o ukončení domovskému

  • pokud hostitel přestane být volný (uživatel se vrátil z hospody)

    • zabít proces

    • nechat doběhnout

    • čas na uložení

    • přemigrovat

Alokace procesorů

  • up-down algoritmus

    • koordinátor má tabulku s body pro každý procesor

    • při každé významné události (vytvoření procesu, ukončení, tik hodin) se pošle zpráva koordinátorovi

    • trestné body: + za proces jinde, - za neuspokojený požadavek, jinak směrem k nule

    • při uvolnění procesoru se vybere proces z fronty neuspokojených požadavků procesoru, který má nejméně trestných bodů

  • deterministický grafový algoritmnus

    • minimalizace komunikace (toky v sítích)

    • nutnost znalosti komunikační složitosti

  • hierarchický algoritmus

    • manažer skupin, při neúspěchu žádost vyšším místům

  • distribuovaný heuristický

    • náhodné výběry cíle

  • bidding algoritmus

    • procesy kupují výpočetní sílu, procesory ji nabízejí

Migrace procesů

  • motivace: vyvažování zátěže, shutdown, optimalizace

  • korektnost - ostatní procesy nejsou migrací ovlivněny

  • transparentnost - proces o migraci neví, nemusí spolupracovat, zůstanou zachovány vazby, není narušena komunikace

  • problémy:

    • přenesení stavu a adres prostoru

    • komunikace mezi procesy

    • reziduální dependence

    • vícenásobná migrace

  • přenos procesu:

    1. zmražení

    2. oznámení příjemci, alokace

    3. přenos stavu - registry, zásobník

    4. přenos kódu / adres prostoru

    5. přesměrování / doručení zpráv

    6. dealokace, vyčištění

    7. vazby na nové jádro, nastartování

    8. dokončení přenosu vazeb, dočištění

  • přenos obsahu virtuální paměti

    • přenesení celé během zmražení procesu

    • pre-copying - přenos za běhu procesu, poté zmražení a přenos změněných stránek

    • copy on reference - stránka se přenese až když je vyžadována, na zdrojové stanici se smaže

  • zprávy:

    • přesměrování - dočasné/trvalé

    • oznámení migrace všem potencionálním odesílatelům (musím je znát)

    • opakování (no ACK)

    • migrace kanálu

Příklady systémů

  • DEMOS/MP (83, migrace - cíl si proces tahá k sobě, nepřijaté zprávy přeneseny při migraci)

  • Charlotte (nezustavaji residualni dependence, sběr statistiky, podle toho migrace, při migraci se kopírují jen hlavičky zpráv, zbytek se dotahává potom průběžně)

  • V (migruje se "logical host" -- víc procesů + adresový prostor), precopy, broadcast nove adresy, stare zpravy zahozeny)

  • MOSIX (Izrael) - rozsireni struktury procesu o cas od posledni migrace, cas na procesoru, pricinu migrace , statistiku IPC

  • Sprite (kazdy proces ma domaci stanici, chtěli všechna volání jádra formardovat na pův systém -- reziduální dependence doma, jednotny prostor jmen, filesystem, global PID | virtualni pamet - kombinace presunu vseho na jednou a copy-on-reference, zmenene stranky na fileserver a ztoho se to postupne taha, zarizuje jadro OS, pre-migratio routine, encapsulation routine, de-encapsulation routine, post-migration routine)

  • T4 - konvencni OS, IPC, vzdalena komunikace, prenos protokoly, name services, vyssi distribuovane sluzby (zdilena pamet, migrace procesu load balancing

Vyvažování zátěže (load balancing)

  • úskalí:

    • jak porovnávat zátěž

    • volba migrujícího procesu

    • volba příjemce

  • párový algoritmus

    • vytvoří se páry, které se vzájemně vyvažují

    • zatíženější procesor vybere proces podle míry vylepšení, zlepšení stavu = další přesouvání, jinak konec

  • vektorový algoritmus

    • pevný vektor zátěže, první vždy vlastní zátěž

    • pošle první půlku náhodnému příjemci, došlá se proloží (princip zipu) s vlastní půlkou + update vlastní zátěže

    • provádí se periodicky

  • centralizované/hierarchické vyvažovací algoritmy

    • koordinátor zná zátěže svých procesorů, velí

  • lokální algoritmus

    • prahová hodnota, když přelezu, ptám se volných N počítačů, vyberu nejlepší odpověď

  • bidding algoritmus

    • vyhodnocovací buňka - excitátory, inhibitory, procesy pravidelně vyhodnocovány (prahová hodnota)

    • výstup vyšší = OK, nižší = migrace, nula = nelze zmigrovat (inhibitor)

    • migrace - broadcast s žádosti o nabídku do vzdálenosti D, adresát proces ohodnotí, případně vrátí nabídku, při neúspěchu D++

  • problémy - aktuálnost údajů, samotná zátěž algoritmu

Distribuované souborové systémy

  • distribuovaný FS x jednotný přístup k síťovým FS

  • monolitický x oddělené adresářové a souborové služby

  • stavový x bezestavový

  • cache - v paměti serveru, v paměti klienta - v adresovém prostoru procesu, v jádře klienta, v cache manageru

  • posloupnost bytů x záznamy x typovaný

  • capability x ACL

  • upload model (stáhnu a nahraju) x remote access model (otevře vzdáleně)

  • kdy jsou vidět změny - ihned (centralizovaná sémantika) x po zavření souboru (relační sémantika)

  • imutabilní soubory - nelze je měnit

  • transakce

  • adresářové služby - mapování uživatelských jmen na systémová, hierarchický systém souborů, linky, graf adresářů - mazání linků

Replikace

  • motivace: spolehlivost, dostupnost, výkon

  • explicitní replika - uživatel sám udržuje konzistenci

  • odložená replika - primární, akutalizace sekundárních

  • skupinová komunikace - simultánní zasílání zpráv všem dostupným replikám

  • aktualizační protokoly

    • primární replika - změny se provádí na jedné replice, ta se stará o aktualizaci ostatních

    • většinové hlasování - pro čtení/zápis potřeba získat většinu hlasů, při žádosti o čtení repliky posílají číslo své verze

    • vážené hlasování - read a write quorum, r+w>N

      • hlasování s duchy - server, který se účastní hlasování pro write při výpadku nějakého serveru

Klientocentrické konzistenční modely

  • eventuální konzistence

    • po skončení všech zápisů budou v konečném čase všechny repliky aktualizovány

    • při připojení k jedné replice uživatel vidí zprávy, po připojení k jiné replice některé zprávy (které již viděl) ještě nevidí

  • monotonic read

    • po přečtení x všechna další čtení vrátí stejnou nebo novější hodnotu

    • při připojení k jiné replice uživatel vidí všechny dosud přečtené zprávy

    • při čtení serveru si server ověří podle read-setu aktuálnost údajů, klient si případně aktualizuje read-set

  • monotonic write

    • zápis proměnné proveden před jakýmkoliv dalším zápisem té proměnné

    • CVS commit na různých replikách

    • při zápisu si replika ověří aktuálnost svých zápisů, chybějící doplní, po zápisu replika aktualizuje write-set

  • read your writes

    • zápis proměnné proveden před jakýmkoliv jejím následným čtením

    • po aktualizaci webové stránky si neprohlížím kopie z cache

    • replika ověří aktuálnost svých zápisů

  • writes follow reads

    • zápis proměnné po předchozím čtení této proměnné je proveden na stejné nebo novější hodnotě

    • zápis odpovědi do newsgroups se provede tam, kde je i přečtená hodnota

    • aktualizace repliky podle read-set, aktualizace write i read-setu klienta

  • naivní implementace WID - globální identifikátor zápisu (kde, co), klient mé dvě množiny read-set, write-set

  • problém: read-set a write-set neomezene rostou, řešení: implementovat je vektorovými hodinami

Epidemické protokoly

  • implementace eventuální konzistence

  • ve VELMI rozsáhlých systémech (neřeší konflikty)

  • Antientropie - server náhodně vybere jiný server k výměně dat

  • gossiping - s pravděpodobností 1/k přestane infikovat

    • push (k sobe), pull (od sebe), kombinace (oba směry)

    • problém s mazáním dat - časově omezený certifikát smrti (záznam o smazání)