Distribuované systémy

Z ωικι.matfyz.cz
Verze z 28. 5. 2008, 03:40, kterou vytvořil Che (diskuse | příspěvky) (RPC: typo)

Přejít na: navigace, hledání

zdroje

Obsah

Komunikace

Zasílání zpráv

nespolehlivý unicast – to co nám dává hardware, počítáme s best effort

  • v IPv4 se pakety mohou na routerech fragmentovat

Spolehlivý unicast

chceme aby nám přišel každý paket a přišel nám jen jednou (exactly once sémantika)

  • ochrana proti poškození (duplikace, checksums, parita, křížová parita, CRC)
    • forward error correction – když zjistím poškození, doplňuji další opravné informace
  • ochrana proti ztrátě – potvrzování
  • ochrana proti duplikaci – unikátní ID paketů
  • jiné problémy – když jedna strana spadne, zapomene jaká čísla paketů poslala atd

TCP – emuluje stream, pakety jsou číslované, mají dvoubajtový kontrolní součet

flow/congestion/etc

flow control 
ochrana proti ucpání příjemce; řeší se posíláním "flow control window" počet/velikost zpráv, které příjemce může dál sezvýkat, posílaný v ACK zprávách
congestion control 
ochrana proti ucpání sítě; "congestion control windows" si upravuje příjemce podle toho jak se mu ztrácí zprávy

Požadavky na real time/propustnost (soft – většinou splněny, hard – splněny vždy) musí být garantovány hardwarem, nad tím se pak dá zajistit rezervace

  • throughput – propustnost
  • latency – jak dlouho to trvá
  • jitter – rozptyl latence

Protokol RSVP (reservation protokol)

  • odesílatel posílá Path zprávy, aby dal najevo uzlům po cestě že je tam nějaká session co něco chce
  • příjemce posíla opačným směrem Resv zprávy, aby vyznačil cestu dalším směrem a dal najevo co se má rezervovat
RTP (Real Time Protocol) 
přenáší real-time data, k němu je RTCP (Real Time Control Protocol) se zprávami o tom jak to jde
RTSP (Real Time Streaming Protocol) 
používá se k dohadování streamingu, ovládá třeba RTP

Multicast

Zpráva jde k více příjemcům, ale posílá se jen jednou. (Broadcast – ke všem uzlům v síti).

V TCP/IP se k ohlašování příslušnosti k multicast skupinám používá IGMP (Internet Group Management Protocol). Další protokoly řídí routování multicast zpráv.

spolehlivost:

  • sender initiated protocols – odesílatel ví o všech příjemcích, ti mu posílají co přišlo; když je příjemnců moc máme ACK implosion problem
  • receiver initiated protocols – příjemce ví, co má přijít, jinak posílá NAK; když má hodně příjemců problémy, máme NAK implosion problem
    • dá se řešit pomocí posílání NAK multicastem a čekáním náhodný interval, jestli už někdo neposlal NAK dřív
  • stromově, pak node posílá lokální ACK (pro flow control) a agregované ACK (když už přide ACK od všech pod ním, kvůli zapomínání poslaných paketů)
  • kruh s tokenem – uzel s tokenem posílá ACK odesílateli, uzly bez tokenu posílají NAK uzlu s tokenem

interfacy:

  • blokující × neblokující (s callbackem nebo pollováním)
  • synchronní (dokončení operace znamená že příjemce zprávu přijal) × asynchronní (operace se vrátí hned po odeslání)

RPC

  • marshalling / unmarshalling – balení a rozbalování parametrů funkcí do zpráv
  • rozhraní může být i ze signatury v "normálním" jazyce, jen s nějakými doplňujícími informacemi
    • IDL – popisuje rozhraní funkcí, z něj se pak generují skeletony a stuby; pak mapování do jazyků
  • varianta s objekty – máme proxy objekty u klienta a servanty na serveru

paralelizace serverů

  • single threaded
  • thread per connection
  • per request
  • thread pool

Skupinová komunikace

Virtuální synchronie

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.

doručovací protokoly

záplavový algoritmus 
při každém přijetí zprávy, kterou uzel ještě neviděl, ji pošle všem ostatním – spolehlivé a neefektivní

algoritmus s potvrzováním

  • ps odesílatel, pr (z L) je příjemce, px uzel co havaroval
  • ps odešle zprávu všem v L, schová ji dokud nedostal ACK od všech, nebo než nazná že zhavarovali
  • pr po příjmu odešle ACK ps, zprávu si schová než zjistí že všichni ostatní přijali
  • jestliže pr zjistí, že ps havaroval, odešle zprávu všem z L, o nichž neví, že ji dostali

Jak pr zjistí které uzly zprávu přijaly?

  • Třeba tím že se ACK posílají taky všem – neefektivní, pokud se to stejně nedělá broadcastem nebo multicastem
  • Ack se dají nalepovat na jiné zprávy, a využitím kauzality – při korektním kauzálním doručování jsou potvrzení tranzitivní
    • D může z příjmu a, b+ACK(a), c+ACK(b) odvodit, že B přijal a, a C přijal a i b
    • z příjmu b+ACK(a), c+ACK(b) může D odvodit, že B přijal a, C přijal a i b, a taky že A poslal a (a vyžádat si jeho resend)
Trans algoritmus
uzel si udržuje kauzální graf zpráv které přijal a ještě je nemají všichni, z došlých potvrzení si vypočítává další, přeposílá zprávy od kterých dostal NAK, detekuje stabilní zprávy.
Transis algoritmus

spolehlivý kauzální multicast + členství ve skupinách. Při pomalé odpovědi vyhodí uzel ze skupiny, ten se pak musí vrátit explicitně.

Založeno na konzistentních změnách pohledů a doručování v rámci pohledů.

  • Při detekci havárie zpráva FAULT
  • kauzální hranice pohledu – vynutí doručení kauzální předcházejících zpráv, pozdrží zprávy následující
  • dvě havárie zároveň – společná hranice
  • kauzální doručení zpráv havarovaného procesu vzhledem ke změně pohledu
ISIS protokol

Maticové hodiny – každý proces si udržuje vektor s odeslanými zprávami, a zároveň vektory co mu došly od všech ostatních. Z toho zjistí které zprávy už mají všichni (a jsou stabilní).

Zaručení synchronie: když se proces dozví o novém pohledu, rozešle všechny nestabilní zprávy a potom potvrzení instalace (flush message), když pak dostane flush od každého procesu, může nový pohled nainstalovat. Každý proces si udržuje seznam "havarovaných" procesů dle aktuálního pohledu, ten se posílá se zprávami a sjednocuje při příjmu. Zprávy od havarovaných se zahazují.

řazení zpráv

  • source ordering – zprávy jednoho odesílatele dorazí v takovém pořadí v jakém je poslal
    • stačí sekvenční číslování lokálně odesílatelem
  • causal ordering – zprávy o události dorazí před zprávami o jejích následcích
  • total ordering – všem příjemcům přijdou všechny zprávy ve stejném pořadí
    • sériová čísla zpráv vydává centrální autorita

Middleware

Klasifikace

převzato z VŠE, berte s rezervou :-)
  • communication middleware – zajišťuje přenos zpráv a tam podobně
    • synchronní – RPC, RMI (Remote Method Invocation) – SunRPC, DCOM, CORBA, Java RMI, SOAP
    • asynchronni – Message-Oriented Middleware
  • data management middleware – přístup k datům
    • Remote Database Access – ODBC, JDBC, ADO.NET
    • Remote File Access
  • platform middleware – běhové prostředí
    • Transaction (Processing) Monitor (TPM) – zajišťuje transakce – EJB - Java Transaction Service
    • Object Request Proker (ORB) – RPC v objektovém prostředí (+ life cycle services, naming services, ...)
    • Message Broker – zajišťuje doručení zpráv a tak (JMS – Java Message Service)
    • Application Server – kontejnery, které zajišťují standardizované služby pro aplikace (CORBA, .NET, J2EE EJB – perzistence, transakce, kontrola souběžných přístupů)


jiná struktura, podle lokiho
  • messaging
  • RPC
  • data access
  • kontejnery

Protokoly

  • SOAP – založené na XML, určené pro web services
  • MPI – C/C++/Fortran knihovna pro přenositelné zasílání zpráv, umí p2p, ale i skupinové metody broadcast, scatter, gather, reduce volitelnou funkcí, ...)
  • .NET Remoting – volání přes SOAP, lifecycle řešený pomocí leases (jak dlouho instance minimálně žije) a sponsors (když vyrší lease, ptáme se sponzorů jestli to ještě chtějí – stačí kladná odpověď od jednoho, takže je to lepší než pingování)

RMI – Remote Method Invocation

see also RMI tutorial

Objekty implementují Remote interface (kde navíc mohou házet RemoteException), implementace dědí z RemoteObject.

  • Třída UnicastRemoteObject pro dočasné objekty
  • Třída Activatable pro perzistentní objekty

Lifecycle se vzdáleně řeší pomocí počítání referencí a keepalive zpráv – klient si při rozbalování příchozí reference na objekt vyžádá lease, ten pak obnovuje.

CORBA

  • IDL, pak mapování do různých jazyků.
  • Protokol GIOP (definuje Common Data Representation – CDR a formáty zpráv), nadstavba IIOP
    • GIOP umí i location forward – zprávu, že požadavky mají teď jít na jiný server
  • Messaging
  • stub/skeleton – u RPC
  • proxy/servant – proxy objekt, servant okolo něj – pro RMI
  • POA – Portable Object Adapter – směruje volání buď do servantů (místních, nebo na jiné servery)
    • default servant – vyřizuje požadavky pro které není servant
    • servant activator – když není servant, vytvoří ho
    • thread pool – připravené thready k obsluze požadavků
    • servant retention policy – dá se úplně vypnout vedení info o servantech, všechny požadavky pak jdou na default nebo activator
  • Naming Service – operace resolve a bind
  • Trading Service – operace export, query
  • operace se dají volat i neblokujícně, s callbackem nebo pollingem

DCOM

Microsoftí middleware pro RPC (s objekty). Místo IDL má MIDL (Microsoft Interface Definition Language), parametry jdou definovat jako in, out, několik typů pointerů, taky pipe.

Interface může být buď RPC nebo COM – COM musí dědit z IUnknown (metody QueryInterface, AddRef, Release) nebo IDispatch (GetTypeInfo, GetIDsOfNames, Invoke), a musí mít uuid atribut (unikátní id). Správa paměti pomocí počítání referencí, vzdáleně se to řeší před další IRemUnknown, které AddRef a Release před posláním serveru agreguje.

Reference na objekty se získávají buď přes factories, nebo nějakými metodami co vrací reference.

Servery mohou být buď in-process (linkované v DLL), nebo out-of-process (v samostatném procesu, mohou běžet i na jiném stroji.

Interfacy pro perzistenci, s metodami jako Load, Save a IsDirty.

JMS – Java Messaging Service

  • zprávy se vyměňují v rámci session se service providerem; session je vázáno na jeden thread a stará se o pořadí a tak
  • různé typy specifických obsahů zpráv (objekt, mapování, stream primitivních typů, text, stream bajtů)
  • rozhraní Producer a Consumer, vytvářené volání metod ze Session; odesílání je blokující asynchronní; příjem je synchronní nebo asynchronní, dá se filtrovat co přijmout
  • modely Point To Point (odesílatelé ukládají do fronty, příjemci vybírají; nejsou-li zůstavají zprávy ve frontě) a Publish Subscribe (kanál od odesílatelů příjemcům; když nejsou příjemci tak se zprávy zahazují – leda že by si někdo objednal durable subscription)

EJB

Prostředí pro komponentové aplikace. Beany obsahují logiku aplikace a bydlí v kontejnerech, které jim zajišťují přístup klientů, životní cyklus, perzistenci, transakce a tak. Volání všech beanů je serializované.

  • stateful session beans – objekt se vytváří když se na něj dodá reference, pak se stav inicializuje business metodou, další speciální metoda stav sundá; stav se v kontejneru uchovává jako serializace tranzitivního uzávěru polí objektu
  • stateless session beans – jako stateful, ale odpadá aktivování/deaktivování
  • message driven beans – požírají JMS zprávy, implementují JMS listener
  • entities – reprezentují entity v databázi; vlastnosti instancí jsou perzistentní, odpovídají primitivním/serializovatelným typům a kolekcím. proměnná Id je primární klíč. Entity manažer posytuje metody k vyhledávání

Beany můžou mít definovaný stav vůči transakcím (neumíme, požadujeme v transakci, může být, pak taky co se má dělat když transakce je/není). Stav session beanu není v transakci a není ovlivněn commitem/rollbackem.

  • business interface – samotné metody na beanu, dělají tu věc co se od beanu chce
  • remote interface – proxy k beanu, třeba hazí navíc výjimky typu "selhalo spojení"
  • home interface – metody nejsou vázané na konkrétní instanci (třeba vytvoření nové instance, nebo vyhledání existující) (jen v EJB 2.1, ne v EJB 3.0... asi)

Logické hodiny a jejich synchronizace

Fyzické hodiny se nedají dostatečně přesně synchronizovat, takže se používají logické.

Lamportovy hodiny

Je důležité pořadí, nikoli přesný čas; nekomunikující procesy nemusí být synchronizovány.

Integer u každého uzlu, a:

  1. Kdykoli proces zaznamená důležitou událost (generování zprávy), inkrementuje timestamp
  2. Ke každé poslané zprávě přidá timestamp
  3. Když proces p přijme zprávu m, aktualizuje si svůj timestamp: TS(p) = max(TS(p), TS(m)+1)

Pak platí, že když událost A kauzálně předchází B, tak TS(A) < TS(B). Opačná implikace ale neplatí. To řeší až vektorové hodiny.

Vektorové hodiny

Každý proces má svůj vektor hodin VT.

  1. odeslání zprávy m procesem ps
    • VT(ps)[i]++; VT(m) = VT(ps)
  2. přijetí zprávy procesem pr; proces pozdrží doručení, dokud
    • VT(m)[k] = VT(pr)[k] + 1 pro k=i (tj. ve slotu odesílatele je zpráva o jednu napřed)
    • VT(m)[k] ≤ VT(pr) jinak
  3. po doručení zprávy m si proces pr upraví VT
    • VT(pr)[k] = max(VT(pr)[k], VT(m)[k])

Pak je zaručeno kauzální uspořádání zpráv.

Distribuované synchronizační algoritmy

  • synchronizace fyzických hodin
  • logické hodiny - lamport, vektorové, maticové
  • vzájemné vyloučení
  • detekce globálního stavu
  • volba koordinátora
  • členství ve skupinách


Vzájemné vyloučení

Není společná paměť, nutno synchronizovat přes zprávy.

  • centralizované (s koordinátorem)
  • princip soutěže (Lamport, Ricard-Agrawalla)
  • volby (Maekawa)
  • token-passing (Suzuki-Kasami)
  • kruh, strom (Le Lann, Raymond)

Centralizovaný algoritmus

Jeden server s frontou, na žádost posílá potvrzení/zamítnutí/uvolnění

  • ideově nevhodné, ale nejjednodušší a nejefektivnější
  • výpadek serveru – ztráta informace
  • výpadek klienta – vyhladovění

U všech následujících algoritmů je problém s výpadkem skoro libovolného procesu – řešit centralizovaný problém distribuovaným algoritmem nemá moc smysl.

Lamportův algoritmus

Proces vyšle žádost, a čeká až dorazí odpovědi od všech ostatních, a všechny žádosti v jeho frontě mají vyšší časovou značku.

  • p posílá žádost Mp se svým timestampem
  • přijetí žádosti od i: zapamatuje si žádost, pošle ACK s vlastním timestampem
  • když dostane od někoho ACK, přidá si ho ke svému požadavku
  • do kritické sekce proces vstoupí, když
    1. od všech ostatních dostal ACK
    2. a zároveň neví o žádném starším požadavku
  • když skončí s kritickou sekcí, pošle ostatním release
  • po přijetí release si proces vymaže k němu patřící žádost (a někdo další pak na základě toho může vlézt do kritické sekce)

Ricart & Agrawala

Proces chce vstoupit do kritické sekce

  • zašle žádost ostatním a čeká na došlé odpovědi s potvrzením

Proces přijme žádost:

  • jestliže není v kritické sekci a ani nechce, pošle potvrzení
  • jestliže je v kritické sekci, neodpovídá a požadavek si zařadí do fronty
  • jestliže do kritické sekce chce, porovná čas příchozí žádosti se s časem své vlastní
    • pokud je vlastní dřív, neodpovídá a zařadí do fronty
    • pokud je příchozí dřív, pošle potvrzení
  • po opuštení kritické sekce pošle potvrzení všem procesům co má ve frontě

Princip voleb

Proces se snaží zíkat hlasy ostatních, kdo má nejvíc může do kritické sekce. Proces může v jeden okamžik hlasovat jen pro jednoho. Problém: jak počítat výsledky, kdy už proces ví že vyhrál. Při stejném počtu hlasů může nastat deadlock.

Maekawa – optimalizace komunikační složitosti pomocí volebních okrsků, pro vstup do kritické sekce je potřeba získat všechny hlasy z vlastního okrsku (podmínky: každé dva okrsky mají společného člena, velikost okrsků je konstatní, každý proces ve stejném počtu okrsků). Komunikační složitost odpovídá velikosti okrsků.

Prevence deadlocku – logické hodiny (proces ruší původní hlas, pokud ještě pak dostane žádost s nižším TS)

Token based

Kdo má peška může do kritické sekce. Problém se ztrátou peška.

Volba koordinátora

Bully algoritmus

Předpokládá se omezená doba přenosu a zpracování zprávy kvůli detekci havárií.

  • Když se proces rozhodne volit, zašle zprávu všem procesům s vyšší identifikací
    • Když přijde odpověď, proces končí
    • Když nepřijde nic, proces vyhrál, je novým koordinátorem a pošle o tom zprávu všem ostatním
  • Když proces přijme zprávu o volbě, vrátí svou odpověď a pošle žádosti všem vyšším procesům.

Volba se provede ve dvou kolech.

Invitation algoritmus

Procesor může zhučet, při selhání komunikace se může síť rozdělit na izolované segmenty, zprávy se můžou ztratit – nelze spolehlivě detekovat havárii.

Idea: koordinátor je vázán na skupinu (všichni členové skupiny vidí stejného koordinátora), skupiny lze štěpit.

pravidelná výzva AreYouCoordinator

  • příjem koordinátorem – sjednocení skupin pod vyššího koordinátora
  • pokud člen skupiny nějakou dobu neobdrží AYC svého koordinátora
    1. prohlásí se za koordinátora nové vlastní skupiny
    2. rozešle AYC ostatním

Konzistence je relativní vzhledem ke skupině. Procesy se shodují na členství ve skupině a na nějaké hodnotě. Separované uzly jsou konzistentní samy se sebou.

Kruhový algoritmus

  1. Proces se rozhodne volit, pošle zprávu následníkovi.
    • zpráva obsahuje čísla procesů (odesílatel a nejvyšší živý)
    • po návratu obsahuje zpráva nového koordinátora
  2. následuje fáze oznámení

Stačí znát následníky a mít možnost zjistit následníka nedostupného uzlu. Složitost je O(n2)

Distribuovaný konsensus

Byzanstký konsensus (1->1)
iniciátor zvolí hodnotu rozešle ji všem; všechny loajální uzly se musí shodnout na stejné hodnotě, je-li iniciátor loajální, musí se shoudnout na jeho
Konsensus (n->1)
každý uzel má iniciální hodnotu, všechny loajální uzly se musí shodnout na společné hodnotě, pokud je iniciální hodnota všech loajálních uzlů stejná, musí se shodnout na té
Interaktivní konzistence (n->n)
každý uzel má inicální hotnotu, všechny loajální uzly se musí shodnout na společném vektoru, hodnota položek vektoru odpovídající loajálním uzlům se musí shodovat s jejich init hodnotou

Problém dvou armád

  • Početnější armáda je rozdělena, uspěje jen při synchronizovaném útoku.
  • Obě části musí mít jistotu, že druhá část začne útok také.
  • Komunikace pouze nespolehlivým kurýrem.

Řešení neexistuje – pošlu-li "Útok v pět", nevím jestli to dostala druhá strana, když mi ona pošle ACK, tak neví jestli jsem ho dostal.

Problém Byzanstkých generálů

  • Někteří generálové jsou zrádci.
  • Všichni loajální generálové musí rozhodnout shodně.
  • Každý generál se rozhoduje na základě informací od ostatních generálů (mají spolehlivou komunikaci).

BÚNO: 1 generál, ostatní důstojníci. Generál vydá rozkaz, důstojníci předají dál dolů – rozkaz bude vydán na základě většiny. Cíle:

  1. všichni loajální důstojníci vydají stejný rozkaz
  2. nebo, je-li generál loajální, každý loajální důstojník vydá rozkaz generála.

Pro tři uzly s jedním zrádcem nejde.

Pro 4 uzly:

  • zrádce generál: alespoň 2 stejné rozkazy: důstojníci si vzájemně přepošlou většinový rozkaz (C1), pro tři různé se shodnou že je generál zrádce (C2)
  • zrádce důstojník: v nejhorším případě pošle všem ostatním falešný rozkaz, loajální ale dostanout většinu správných (C2)

Existuje řešení pro 4 uzly s jedním zrádcem, obecně pro m zrádců existuje řešení pro n≥3m+1 uzlů

Konsensus s nezfalšovatelnými zprávami

Pokud nelze předávanou zprávu zfalšovat, pak libovolný počet zrádců neznemožní konsensus.

Idea algoritmu:

  • každý přepošle vše, co dostal, v nezměněné podobě
  • každý uzel nakonec sám uvidí co kdo komu poslal
  • loajální uzly se shodnou buď na majoritní nebo default hodnotě

Distribuované sdílení paměti

Různé mechanismy, v HW/SW, od SMP s busem/switchem přes NUMA, distribuované stránkování po distribuované sdílené promenné a objekty.

Konzistenční modely

Modely bez synchronizační proměnné

implementace možná na úrovní virtuální paměti, procesy o tom nemusí vůbec vědět

striktní konzistence
jakékoli čtení z adresy x vrátí hodnotu uloženou při posledním zápisu do x – absolutní časové uspořádání, všechny zápisy okamžitě všude viditelné; musí existovat přesný globální čas
sekvenční kozistence
výsledek výpočtu je stejný, jako kdyby všechny operace všech CPU byly vykonávány v nějakém sekvenčním uspořádání, a operace každého CPU jsou v pořadí specifikovaném programem – snadno implementovatelné, povoleno libovolné prokládání instrukcí na různých CPU, všechny procesy vidí stejné pořadí změn; platí že čas čtení a zápisu dohromady musí trvat alespoň tak jako přenos jednoho paketu -> pomalé
kauzální konzistence
kauzálně vázané zápisy musí být viděny všemi procesy ve stejném pořadí; vyžaduje udržování grafu závislostí zápisu na čtení
PRAM (pipelined RAM) konzistence
zápisy prováděné jedním procesem jsou viděny ostatními procesy v tom pořadí, ve kterém byly prováděny; neexistuje jednotný pohled na rozvrh, snadná na implementaci
slow memory
zápisy jedním procesem do jednoho místa musí být viděny ve stejném pořadí; lokální zápis, pomalá nesynchronizovaná propagace, neposkytuje žádnou synchronizaci

Všechny modely vyžadují propagaci všech zápisů všem procesům, přitom ne všechny aplikace potřebují vidět všechny zápisy a jejich pořadí.

Modely se synchronizační proměnnou

Operace Synchronize, Acquire a Release určují kdy je proces v kritické sekci. (Po jejím skončení se data propagují ostatním). Procesy musí o SP vědět, ale výkonnost je vyšší.

slabá konzistence
  1. přístup k SP je sekvenčně konzistentní (všechny procesy ho vidí ve stejném pořadí)
  2. před přístupem k SP musí být dokončeny všechny předchozí zápisy
  3. před přistupem k obyčejným proměnným musí být dokončeny všechny předchozí přístupy k SP

Sáhnutím na SP před čtením se zajistí aktuální verze dat.

Výstupní konzistence
  1. Před přístupem ke datům musí být úspěšně dokončeny všechny předchozí Acq() procesu.
  2. Před provedením Rel() musí být dokončeny všechny předchozí zápisy a čtení prováděné procesem.
  3. Acq() a Rel() musí být PRAM konzistentní.
  • eager release consistency – změny se všem propaguí po Rel(); optimalizace přístupové doby
  • lazy release consistency – změny se propagují až po Acq() jiného procesu; menší nároky na síť
Vstupní konzistence
  1. Před Acq() k SP se aktualizují chráněná sdílená data procesu
  2. Exkluzivní přístup k SP je povolen jen když k ní nepřistupuje jiný proces (ani neexkluzivně)
  3. Pro exkluzivní přístup si musí proces vyžádat aktuální kopii dat od posledního vlastníka (kdo to měl exkluzivně)

Distribuované stránkování

obdoba virtuální paměti (problémy: replikace, nalezení stránky, správa kopií, uvolňování stránek, falešné sdílení)

  • sekvenčně konzistentní – stránky mají vlastníka co na ně může psát, ostatní mají kopie pro čtení
  • kauzálně konzistentní – vektorové hodiny u stránek i procesů, velká prostorová režie

Distribuované sdílené proměnné

  • implementováno v knihovnách (např. Munin – sdílení read-only; migratory s eager release konzistencí; write-shared – do lokální kopie se dá psát, po release se propagují změny; normální sdílená data se sekvenční konzistencí)
  • distribuované objekty – flexibilnější díky zapouzdření (CORBA, etc)

Souborové a adresářové služby

see #Identifikace objektů a přístup k nim


Distribuované souborové systémy

  • distribuovaný FS vs. jednotný přístup k síťovým FS
  • monolit vs. oddelené souborové a adresářové služby (které mapují uživatelská jména na systémová)
  • stavové vs. bezestavové servery
  • replikace, cache

sémantika přístupu k souborům

  • centralizovaná (každá změna hned vidět)
  • relační (změny jsou vidět až po zavření – AFS)
  • imutabilní soubory (GoogleFS)
  • transakce

NFS

wen: Network File System (protocol)
  • postaveno nad RPC
  • vyvinul v 80tých letech Sun
  • XDR - eXternal Data Representation – popis datových struktur které NFS používá
  • verze 3
    • bezstavová
    • některé podpůrné protokoly běží na různých portech
    • jedna akce nad NFS se typicky skládá z většího množství RPC callů
  • verze 4
    • stavová (!)
    • složené operace – umožňují omezit počet nutných RPC callů
      • odhaduje se až pětinásobná úspora potřebných client-server interakcí

AFS

wen: Andrew File System
  • vznikl v rámci projektů Andrew Project na Carnegie Mellon University (jméno podle Andrew Carnegie a Andrew Mellon)
  • poskytuje lepší možnosti scalability a security
  • pro security využíván Kerberos, implementována ACL adresářů
  • soubory jsou cacheované na klientovi => možnost omezeně fungovat i po pádu serveru/sítě
    • změny jdou do cache a jsou na server propagovány až při zavření souboru
    • pokud je soubor na serveru změněn, klienti kteří ho mají v cache jsou informování
  • svazek – strom souborů, adresářů a mountpointů. Sestavuje jej admin.
    • uživatel s ním může pracovat jakoby byl lokální
    • může mít nastaveny kvóty
    • admin ho může přesunou na úplně jiný server bez toho aby se to uživatel dozvěděl
    • může mít několik read-only kopií, AFS zajistí že budou obsahovat správná data, pokud mám jednu připojenou a server kde je spadne => nic se neděje, začnu seamlessly pracovat s jinou
  • hodně se jím inspirovalo NFS verze 4, z AFS 2 vychází CODA

CODA

wen:Coda (file system), základy přímo na CMU
  • začal vznikat na Carnegie Mellone University v 1987
  • vychází přímo z AFS 2
  • client-side caching souborů, adresářů a atributů
  • write-back cache
  • kerberos-like autentizace
  • ACLka
  • reintegrace dat na čas odpojených klientů
  • možnost replikace serverů (read/write)

Replikace

Udržování kopií na více fileserverech. Důvody: spolehlivost, dostupnost, výkon.

  • explicitní (uživatel se stará sám)
  • odložená (aktualizuje se primární replika, sekundární pak)
  • skupinová komunikace (zápisy se simlutánně posílají všem replikám)

Aktualizace kopií:

  • primární kopie vítězí
  • většinové hlasování
  • vážené hlasování (různý důraz na čtoucí a zapisující procesy)
  • hlasování s duchy (bezdatový server – ghost, obsahuje pouze verze, účastní se hlasování o zápisu)
  • dynamická kvóra

klientocentrické konzistenční modely

see also [1]

Replikovaná databáze (www+cache, zápisy málo časté), když se klient přesune jinam, musí vidět stejná data.

eventuální konzistence
po ukončení všech zápisů budou všechny repliky v konečném čase aktualizovány; problém je, že jeden proces může koukat na data jiných replik a vidět něco jiného
monotonní čtení
po přečtení hodnoty x všechna další čtení vrátí stejnou nebo novější hodnotu (při připojení k jiné replice uživatel vidí všechny zprávy co už si přečetl dřív – dá se řešit třeba logem updatů, co už klient viděl – pak si může zajistit že kouká na aktuální repliku
monotonní zápis
zápis do proměnné je proveden před každým následním zápisem do ní; než do repliky zapíšu, musí si aplikovat přijmout aktuální změny od ostatních
read your writes
procesy při následném čtení vidí svoje zápisy (po aktualizaci wiki nekoukám na kopie z cache)
writes follow reads
zápis se provede do kopie proměnné, která je alespoň tak aktuální jako ta, která se předtím přečetla

Implementace: klient si udržuje read-set a write-set (množiny čtení a zápisů co už viděl), posílá s požadavky, podle toho se vynucuje aktualizace replik, jde i vektorovými hodinami (podle replik?)

epidemické protokoly

Eventuální konzistence, optimalizuje pro hodně velké systémy, neřeší konflikty.

  • servery jsou: infected (rozšiřují "epidemii"), removed (data mají ale nerozšiřují), susceptible (data nemají)
  • antientropie: každý server jednou za čas zkontaktuje náhodný jiný, vymění si co ještě nemají (nebo jen push nebo pull)
  • gossiping: pokud byl P aktualizování, kontaktuje nějaký další server Q, aby šířil update; jestliže Q už update má, P se s pravděpodobností 1/k nastaví jako removed
    • nezaručuje že update budou mít všechny servery

Distribuovaná správa prostorů jmen

Identifikace objektů a přístup k nim

Adresářová služba poskytuje přístup k nějaké databázi sdílených prostředků.

  • identifiace a přístup k objektům (který, kde je, jak se k němu dostat)
  • struktura jmen, trvanlivost, distribuovaná správa jmen
  • kapability a jejich ochrana
  • přístup k objektům, distribuovaná správa prostředků
  • objekty: aktivní (kód) / pasivní (přes správce, nebo prostředky)
  • jména: uživatelská (human-readable) / systémová (interní čílesné kódy)
    • mapování jmen na replikované objekty
    • jména mohou být plochá, strukturovaná (hierarchická), nebo popisná (více atributů)

Prostory jmen mohou být separátní (file system, registry, URL) nebo může být jednodný (distribuovaný name server).

Kapabilita je datová struktura umožňující jednoznačnou identifikaci objektu, obsahuje i přístupová práva pro držitele – k jednomu objektu typicky patří víc různých kapabilit. Uživatelským procesům je znemožněno vlastní generování kapabilit i změny práv.

  • snadný test oprávněnosti, každý správce si může nadefinovat vlastní druhy práv
  • problematické kontrola propagace, potřeba definovat oprávněné uživatele, nebo revokovat
  • kapability mohou být buď podepsané, nebo je jejich část s přístupovými právy zašifrována

Adresáře jsou množina položek (jméno,hodnota), hodnota může být:

  • primitivní (čísl, řetězce, binární data)
  • perzistentní reference (trvalé odkazy na objekty, kapability)
  • tranzientní reference (na živé objekty, porty, kanály)
  • odkazy na jiné adresáře

Kapability se publikují na nameserveru, zároveň si server registruje u Reg serveru. Klient si najde kapability na NS, otevře si ji u Reg serveru, ten ověří a předá serveru, ke kterému si pak klient otevře kanál.

Služby

LDAP

see also wen:Lightweight Directory Access Protocol

"Odlehčená" verze X.500 DAP pro použití v TCP/IP sítích.

  • adresář je strom položek, každý má sadu atributů
  • atribut má jméno a jednu nebo více hodnot (podle definovaného schématu)
  • každý položka má DN (distringuished name) – skládá se z RDN (relative DN, vyrobeného z nějaké položky) a DN rodiče
    • DN se může v průběhu živata měnit, někdy se jim přidává i UUID

LDAP poskytuje autentizaci přístupu, služby čtení a vyhledávání v položkách, ověření jestli má položka nějakou hodnotu atributu, aktualizace dat a tak.

JNDI

see also wen:Java Naming and Directory Interface

Hledání objektů pro Java RMI a Java EE, poskytuje:

  • bind objektu ke jménu
  • hledání v adresáři
  • event interface, dovolující klientům zjistit když se položky změnily
  • hledá se v kontextu, root je initial context

CORBA Naming/Trading

Naming service:

  • naming context: sada vazeb jméno objekt (cosi jako adresář)
  • resolve: nalezení objektu podle jména v kontextu
  • bind: vytvoření vazby v kontextu
  • v kontextu může být pod jménem i jiný kontext – složené cesty (jako ve stromovém fs)

Trading Object Service:

  • Export: objekt dá traderovi kapabilitu (popis služby, a interface kde je)
  • Import: někdo se zeptá tradera na službu s danými vlastnostmi, trader dodá umístění
  • tradery se dají navzájem linkovat

Procesy v distribuovaném prostředí

  • sdílení výpočetní síly systému
  • vzájemná synchronizace
  • vzdálené spouštění, alokace procesorů, migrace, load balancing

Vzdálené spouštění by mělo být transparentní, a vytvořit prostředí odpovídající domácímu

  1. registr volných počítačů, tam se nějaký najde
  2. vytvoření prostředí pro proces, ten se pustí, po ukončení zpráva jeho domovskému systému

Pokud hostitel přestane být volný, tak se proces zabije, nechá doběhnout, dostane čas na uložení stavu, nebo přemigruje.

Alokace procesorů:

  • up-down alogoritmus (koordinátor má tabulku procesorů, ty mu hlásí co dělají; dostávají trestné body za proces jinde, odebírají se jim za neuspokojené požadavky, jinak jdou směrem k nule; při uvolnění procesoru ho dostane klient co má nejmíň trestných bodů)
  • deterministický grafový – minimalizuje komunikaci, nutno vědět jak co bude komunikovat
  • hierarchický – manažeři skupin, při neúspěchu žádost nahoru
  • distribuovaný heuristický – několik náhodných výběrů cíle
  • bidding – procesy kupují výpočetní sílu

Migrace procesů

  • vyvažovani zateze, shutdown, optimalizace
  • korektnost – ostatní procesy nejsou migrací ovlivněny, přenesený proces potom je ve stejném stavu
  • transparentnost – proces o migraci neví a nemusí spolupracovat

problémy:

  • přenesení stavu a adresového prostoru
  • komunikace mezi procesy (neztrácet zprávy a tak)
  • reziduálni dependence (nechat něco na původním místě)
  • vícenásobna migrace

Postup přenosu

  1. zmrazení
  2. oznameni příjemci, alokace místa tam
  3. přenos stavu (registry, zásobnik) a kódu / adresového prostoru
  4. přesmerování / doručení zpráv
  5. dealokace, vyčištění původního místa
  6. vazby na nové jadro, nastartování přeneseného procesu (přesunutí částí stavu spolu s procesem, jiné požadavky forwarovat – konzole, některé se používají z nového místa – alokace paměti)
  7. dokončení přenosu vazeb

jak kopírovat paměť

  • celou při migraci – eliminuje reziduální dependence, ale je pomalé
  • pre-copying – proces zmražen jen krátkou dobu, ale ty věci co změní od kopírování se přenášejí víckrát
  • copy on reference – stránka se přenese až když je vyžadována, na zdrojové stanici se smaže

zprávy:

  • dočasné nebo trvalé přesměrování
  • upozornit kamarády předem (ale které?)
  • neposílat ACK, on si je zdroj pošle znovu
  • migrace kanálu

Vyvažování zátěže

Rozhodnutí o okamžiku migrace – nutno porovnávat zatížení procesorů (nějak konzistentně), pak vybrat co bude migrovat a kam.

  • párový algoritmus – vytvoří se páry které se vzájemně vyvažují, zatíženější procesor vybere proces podle míry vylepšení stavu
  • vektorový algoritmus (MOSIX) – první vždy vlastní zátěž, pak pošle první půlku nahodnému uzlu, došlá se proloží s vlastní půlkou
  • bidding algoritmus: procesy pravidelně vyhodnocovány, pod určitý prah se migruje:
    1. broadcastem žádost o nabídku do vzdálenosti d
    2. adresát proces ohodnotí, případně vrátí nabídku
    3. odpověďi se zkorigují o cenu přenosu, bere se nejlepší; když nedorazí žádná zvýšíme d
  • centralizované/hierarchické vyvažovací algoritmy – koordinátor zná zátěže svých procesorů
  • lokální (prahová hodnota, když přelezu, ptám se po volných n počítačů, vyberu nejlepší odpověď)

Zablokování

  • oblíbené řešení – pštrosí algoritmus
  • detekce horší než lokálně: wait-for-graph
  • chceme: Každý existující deadlock je v konečném čase detekován, detekovaný deadlock musí existovat

modely deadlocků

Kdy už je deadlock?

  • single
  • AND model – všechny požadované prostředky musí být přiděleny, aby se proces odblokoval – na deadlock stačí cyklus
  • OR model – výpočet může pokračovat, pokud proces dostane alespoň jeden požadovaný prostředek – cyklus je nutná podmínka deadlocku, na postačující je nutný nějaký horší uzel
  • k of m
  • AND-OR

metody kontrukce wait-for grafu

  • centralizovaně (prenos informací po každé změně, v intervalech, nebo na požádání)
    • kauzální doručování proti falešnému uváznutí kvůli zpoždění zpráv
    • hierarchický (každý řeší deadlocky podřízených)
  • path-pushing (uzly sparvují lokální kusy WFG, sousedním uzlům zasílání externí žádosti, potřeba rozlišovat různé procesy uvnitř jiných uzlů)
  • edge-chasing (pošlu zprávu všem, na které čekám, pokud se mi vrátí, jsem v háji; mezitím se to ale mohlo doblokovat – řešením je aging; overkill – zpráva zároveň hledá kandidáta na zahubení)
  • diffusing computation – těm na které čekám se posílají pingy, oni je vrací pokud jsou taky zablokováni. pokud dostanu všechny své pingy zpět, mám deadlock
  • detekce globalniho stavu – existuje-li deadlock, pak existuje i v konzistentním řezu; při příjmu značku (okamžik řezu) uzel zaznamená lokální WFG, externí závislosti jsou zaslány iniciátorovi