SWI035 přednáška

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

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

Tato stránka není kompletní a/nebo může obsahovat chyby!

Distribuovaný systém[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

(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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  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í[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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

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 Lx před změnou na Lx+1
    • buď m doručí všechny uzly z Lx před provedením změny na Lx+1
    • nebo žádný uzel z Lx, který provede změnu na Lx+1, 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í[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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ěť[editovat | editovat zdroj]

Konzistence bez SP[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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í[editovat | editovat zdroj]

  • 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é[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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 2b
    • 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ů[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

  • 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)[editovat | editovat zdroj]

  • ú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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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í)