SWI035 přednáška

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

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_i (lokální verze procesu i), L^x (verze pohledu x), L_i^x

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

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