SWI035 přednáška: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(spolehlive kauzalni dorucovani)
(cile)
Řádka 18: Řádka 18:
 
*transparentnost - pristupova, lokacni, migracni, replikacni, perzistentni, konkurencni, paralelismova
 
*transparentnost - pristupova, lokacni, migracni, replikacni, perzistentni, konkurencni, paralelismova
 
*prizpusobivost - autonomie, decentr. rozhodovani, otevrenost, migrace procesu
 
*prizpusobivost - autonomie, decentr. rozhodovani, otevrenost, migrace procesu
*spolehlivost - teorie: nespolehlivost jednoho serveru 1% => nespolehlivost čtyř serverů 0.014 = 0.00000001
+
*spolehlivost - teorie: nespolehlivost jednoho serveru 1% => nespolehlivost čtyř serverů 0.01^4 = 0.00000001
 
*vykonost - teorie: vice uzlu->vyssi vykon, praxe: výrazně nižší než lineární nárůst výkonu
 
*vykonost - teorie: vice uzlu->vyssi vykon, praxe: výrazně nižší než lineární nárůst výkonu
 
*rozsiritelnost - Princip: vyhnout se čemukoliv centralizovanému
 
*rozsiritelnost - Princip: vyhnout se čemukoliv centralizovanému
 +
 
==architektury==
 
==architektury==
 
*multiprocesory (sdili pamet) - bus,switched - crosspoint switch, omega
 
*multiprocesory (sdili pamet) - bus,switched - crosspoint switch, omega

Verze z 2. 2. 2009, 10:08

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!

distribuovany system

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

  • distribuovany OS
  • vrstva middleware nad OS

motivace

  • ekonomika
  • vykon
  • distribuovatelnost
  • spolehlivost
  • rozsiritelnost

cile

  • transparentnost - pristupova, lokacni, migracni, replikacni, perzistentni, konkurencni, paralelismova
  • prizpusobivost - autonomie, decentr. rozhodovani, otevrenost, migrace procesu
  • spolehlivost - teorie: nespolehlivost jednoho serveru 1% => nespolehlivost čtyř serverů 0.01^4 = 0.00000001
  • vykonost - teorie: vice uzlu->vyssi vykon, praxe: výrazně nižší než lineární nárůst výkonu
  • rozsiritelnost - Princip: vyhnout se čemukoliv centralizovanému

architektury

  • multiprocesory (sdili pamet) - bus,switched - crosspoint switch, omega
  • multicomputery (vlastni pamet) - bus, switched - mrizka, hyperkrychle
  • hybridni

komunikace

  • absence sdílené paměti -> zasílání zpráv
  • klient-server model
  • tcp vs t/tcp
  • ztráta zprávy -> typické řešení: potvrzování, timeout, opakování; ACK, NAK, AYA, IAA, CON, ...
  • dlouhe zpravy -> burty - potvrzuje se davka paketu
    • pevne davky - při vyšší zátěži sítě velká chybovost, při volné síti nízká výtěžnost
    • dynamicke davky - velikost na zaklade uspesnosti predchozich prenosu
  • idempotentni sluzba - nevadí opakované provedení služby, secti 1+1
  • semantiky zpracovani
    • exactly once
    • 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
  • havarie klienta
    • exterminace
    • reinkarnace
    • expirace

RPC

  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 zviditelni na directory serveru
  • pouziti IDL
  • problemy:
    • reprezentace dat - endiany, kodovani, floaty
    • globalni promenne
    • ukazatele a dynamicke struktury
    • predavani poli
    • variabilni parametry

skupinova komunikace

  • jeden odesilatel vic prijemcu
  • atomicita - vsichni nebo nikdo
  • synchronizace (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)
  • adresovani - adresa skupiny, seznam, predikatova adresace (pouzita jeden z predchozich + pridan predikat, pokud splnen tak je prijata)
  • technicky - unicasty, multicast, broadcast
  • uzavrena(koop. alg.) x otevrena skupina(replikovane sluzby)
  • flat x hierarchicka (pres koordinatora)
  • dorucovaci protokol: 1. prijem, 2. doruceni

fyzicke hodiny

  • UTC
  • požadovaná odchylka δ -> intervaly max. δ/2ρ ; ρ = mira presnosti
  • cristianuv alg-pasivni timeserver
  • berkeley alg-aktivni timeserver
  • distribuovany alg-resynchronizacni intervaly pevne delky, broadcast, zahozeni extremu, spocitani prumeru
  • intervalovy cas-cas je interval, nekdy nelze porovnat


logické hodiny

  • důležité pořadí, nikoliv přesný čas, nekomunikující procesy nemusí být sesynchronizovány
  • relace predchazi
  1. a a b udalosti v jednom procesu a a se udela pred b, pak a->b
  2. send(m)->recv(m)
  3. tranzitivita
  • jestliže a -> b pak C(a) < C(b) (zuplneni pro C(a)=C(b) - byrokraticke usporadani podle PID)
  • průběžně si zvyšuji čas, když mi přijde zpráva, s časem >=, než mám, tak si svůj zvětším abych mel vetsi

Kauzální závislost

  1. jestliže ex.p: e1 ->p e2 potom e1 -> e2
  2. send(m)->recv(m)
  3. tranzitivita
  • konkurentni udalosti - e1 neni kauzalne zavisla na e2 a e2 neni na e1
  • jestliže a -> b pak C(a) < C(b), opacne ne

Vzajemne vylouceni

  • centralizovany alg - centralizovany server s frontou, žádost / potvrzení / zamítnutí / uvolnění, problem s vypadkem serveru, klienta (starvation)
  • Lamportuv alg. - Proces vyšle žádost a čeká až dorazí potvrzeni s vetsi casovou znackou od všech procesů a všechny žádosti v jeho frontě mají větší časovou značku, po uvolneni KS se posila release zprava
  • Ricart & Agrawala
    • kdyz chce proces vstoupit, posle vsem zadost se svou TM a ceka na vsechny potvrzeni
    • proces ktery prijme zadost
      • nechce vstoupit ani neni v KS - posle potvrzeni
      • je v KS - zaradi zadost do fronty a potvrzeni posle az po vystupu z KS
      • neni v KS ale chce taky - pokud jeho zadost nizsi znacku, zaradi do fronty a neodpovida, jinak posle potvrzeni
  • naivni volby - potreba nadpolovicni vetsina hlasu, deadlocku pokud 2 procesy stejne hlasu, posila se zadost o hlasy, ostatni odpovidaji pokud jejich hlas je Available, po vystupu z KS se posila release zprava
  • Maekawa
    • volebni okrsky - pro vstup do KS je potreba ziskat vsechny hlasy z okrsku
      • kazde 2 volebni okrsky museji mit spolecny aspon jednoho kandidata
      • vsechny okrsky stejne velke
      • kazdy proces ve stejnem poctu okrsku
    • 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 vlastnici peska muze vstoupit do KS

volba koordinátora

  • bully - posílám větším, vetsi posilaji zase vetsim, kdyz prijde odpoved vzdavam se, kdyz ne jsem koordinator - informuju ostatni, predpoklady omezeny doby prenosu a zpracovani zpravy, spolehlivy prenos, pri prekroceni timeoutu moznost vice koordinatoru :(
  • invitation alg
    • nejsou pozadavky na spolehlivost a dobu odezvy
    • koordinator pravidelne posila AYC
    • pokud dele neprijde AYC od meho koordinatora prohlasim se za koordinatora sve skupiny
    • kdyz koordinatorovi prijde AYC jineho, spoji se do jedne skupiny toho vyssiho, koordinatori poslou zpravu clenum sve puvodni skupiny at se pripoji do nove
  • kruhový
    • rozhodnu se volit poslu zpravu naslednikovi
    • zprava obsahuje cisla procesu - odesilatel a dalsi ktere zprava obesla, prip. jen nejvyssi zivy
    • kdyz mi zprava prijde zpet koordinatorem urcim proces s nejvyssim id a rozeslu zpravu

dorucovaci protokoly

  • globalni usporadani - zprávy jsou doručovány v pořadí odeslání
  • Sekvenční uspořádání - všechny uzly doručí zprávu ve stejném pořadí
  • Kauzální uspořádání - kauzálně vázané zprávy ve správném pořadí
    • 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 kazde p z pruniku dest(m1) a dest(m2) plati deliverp(m1) ->p deliverp(m2)

vektorové hodiny

  • kauzalni dorucovani
  • vektor s kusy podle uzlů
  • kdyz 2 vektory nejsou porovnatelne jedna se o konkurentni zpravy
  • před odesláním zvýším svoje počítadlo
  • před přijetím čekám, než muj vektor bude větší nebo roven než vektor 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 sveho vektoru a vektoru zpravy) po složkách
  • pro prekryvajici se skupiny: u zprávy posílám vektory všech skupin, kde jsem; při příjmu kontroluju 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)

total-order protokol

  • sekvencni dorucovani

virtualni synchronie

  • Algoritmus spolehlivého doručování je virtuálně synchronní když
    • všechny uzly ve skupině udržují stejný L
    • pokud zpráva m je 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čí

Pozorovani: Nemusí platit, že přijetí zprávy členem L implikuje doručení všem členům L

spolehlive kauzalni dorucovani

  • flooding alg - Při příjmu každé doposud nepřijaté zprávy ji každý uzel přepošle všem ostatním -> neefektivni
  • trans alg
    • p rozesílá Ack(m) když přijal m a všechny kauzálně předcházející zprávy
    • graf kauzality G cele skupiny, graf prijatych zprav ale jeste nestabilnich 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 zmenu clenstvi ve skupinach
  • transis alg
    • rozsireni trans o clenstvi ve skupinach
    • při detekci havárie zpráva FAULT(q), při přijetí její přeposlání
    • zpravy kauzalne zavisle na nejake FAULT zprave pozdrzet do dalsiho pohledu, pokud vic FAULT zprav a zprava zavisla jen na jedne z nich, tak dorucit
    • zpravy od odesilatele, ktery spadnul a ktere jsou kauzalne vazane na nejakou FAULT zpravu nebo jsou k ni konkurentni zahodit, dorucit jen ty co byly odeslany pred detekci havarie
  • isis protokol
    • maticove hodiny
    • kazdy proces zna vektor vsech ostatnich procesu: VTpi[j] - co vi proces i o procesu j
    • pri prijmu zpravy od pi k pj: VTpj[j][i]=VTm[i], VTpj[i][*]=VTm[*]
    • clenstvi ve skupinach - kazdy proces udrzuje vsechny nestabilni zpravy, pri prijmu view change zpravy posle vsechny nestabilni a pak flush, po prijmu flush od kazdeho procesu instaluje novy pohled (kazdy proces udrzuje seznam havarovanych procesu, s kazdou zpravou se odesila, zpravy od havarovanych procesu se zahazuji)

ukonceni distr procesu

  • dijkstra-scholten alg
    • strom
      • kazdy listovy proces po ukonceni posle zpravu otci, ten propraguje vis, po zjisteni ukonceni vsech synu
    • dag
      • na kazde hrane deficit (#doslych zprav-#signalu)
      • koncici proces vysle kazdym signalnim tolik signalu aby deficit vsude byl 0
    • obecny graf
      • problem - nejsou listy
      • pri vypoctu kostra grafu - otec = uzel od ktereho prvni zprava
      • 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

konzistentni stav

  • Množina událostí v systému E = {e}
  • Řez c je rozdělení E na Pc a Fc : Pc u Fc = E & Pc prunik Fc = 0
  • Konzistentní řez c : a -> b & a lezi v Fc pak b lezi 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

detekce globálního stavu

  • Distributed snapshot alg - při příchodu značky ji rozešlu na výstupy a označím svoje I/O jako svůj stav, pak u příchozích kanálů počítám zprávy a čekám na značku. až přijde, zprávy mezi první a příchozí značkou kanálem jsou stav toho kanálu

distribuovany konsensus

  • problem 2 armad - pocetnejsi armada musi zautocit synchronizovane aby mohla vyhrat

problem byzantskych generalu

  • uzly mohou havarovat a chovat se zakerne
  • C1: vsichni loajalni dustojnici vydaji stejny rozkaz
  • C2: Je-li generál loajální, pak každý loajální důstojník vydá rozkaz generála
  • 3 uzly, 1 zradce - reseni neexistuje
  • 4 uzly
    • zradce general
      • 2 stejne rozkazy - dustojnici se rozhodnou pro vetsinovy rozkaz (C2)
      • 3 ruzne rozkazy - dustojnici se dohodnou ze general zradce (C1)
    • zradce dustojnik - loajalni dustojnici dostanou vetsinu spravnych rozkazu (C2)
  • Pro m zrádců exsituje řešení pro n ≥ 3m+1 uzlů
  • Konsensus s nezfalšovatelnými zprávami - vsichni preposilaji zpravu tak jak ji dostali, teda obsahuje i predchoziho odesilatele -> loajalni uzly se shodnou na majoritni nebo defaultni hodnote

Klasifikace problémů distribuovaného konsensu

  • byzantsky konsensus - iniciatorem rozesilana hodnota
  • konsensus - kazdy ma svou inicialni hodnotu
  • interaktivni konzistence - loajalni se museji shodnout na vektoru loajalnich

konzistence

  • strict (všechny zápisy okamžitě všude viditelné) - podmínka: musí existovat přesný globální čas -> v DS temer nemozne
  • 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 vsechny odpovidaji sekvencni konzistenci
    • dokazano r+w>=t, cili pokud optimalizujeme pro cteni, zapis bude pomaly
    • snadno implementovatelna
  • kauzální
    • kauzalne vazane zapisy(P1:W(x), P2:R(x),W(y)) musi byt videt ve stejnem poradi
    • implementace vyzaduje graf zavislosti
  • PRAM
    • zapisy jednoho procesu viděny v pořadí v jakem byly provedeny, zapisy ruznych procesu konkurencni
    • priklad se zabitim obou procesu
    • snadna 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

  • predchozi modely prilis restriktivni, 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
  • 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
  • release
    1. před přístupem k datům musí být uspesne dokončeny predchozi 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í
    • pri spravnem parovani Acq a Rel je vysledek ekvivalentni sekvenci konzistenci
    • eager (vše se propaguje po Rel())
    • lazy (vše se sosá před Acq())
  • entry
    1. Acq() až po aktualizacích všech chráněných dat
    2. exkluzivní (RW) přístup k SP jen kdyz nikdo jiny nepristupuji ani neexkluzivne
    3. po exkl pristupu si příští přístup musí vyžádat kopii od vlastníka
    • kazda SP ma vlastnika

distribuované stránkování

  • přístup k nenamapované stránce - přerušení, obsluha, načtení
  • problemy:
    • replikace x konzistence
    • nalezeni stranky
    • sprava kopii
    • uvolnovani stranek - ktere
    • falešné sdílení (nezávislá data na stejné stránce)
  • sekvenčně konzistetní (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á (signle writer, many readers -- jako distrib. stránkování, sekvenční konzistence)
  • distribuované objekty (základní distribuovaný předek, pak potomci, class deifinition language -- automatické generování kódu, middleware: CORBA, Java RMI)

identifikace

  • ktery objekt(identifikace), kde je(adresa), jak se dostat(cesta)
  • uzivatelska jmena x systemova
  • nestrukturovana jmena x strukturovana jmena(absolutni x relativni) x popisna (atribut=hodnota)
  • dynamicka jmena (deskriptory objektu) x staticka (jmena souboru)
  • capability x ACL

kapabilita

  • jednoznační identifikace objektu a přístupu (user nemůže měnit ani generovat)
  • k jednomu objektu typicky vic kapabilit (vlastnik, pisar, ctenar)
  • +: snadný test oprávěnosti přístupu, každý správce prostředků může nadefinovat vlastní druhy práv
  • -: seznam oprávněných uživatelů, ... ...
  • kapabilita s podpisem - podpis identifikace objektu a prav, potom jeste zasifrovano tajnym klicem
  • kapabilita s redundanci - server port, id objektu, prava + nahodne vygenerovana hodnota, zasifrovana prava a generovana hodnota
  • ns - publikace kapabilit, reg - zádosti o otevření kanálu

deadlocky

  • pštrosí algoritmus
  • detekce horší než lokálně: wait-for-graph (Každý existující deadlock je v konečném čase detekován, detekovaný deadlock musí existovat)
  • modely deadlocku
    • single
    • and
    • or
    • k of m
  • centralizovaný alg
    • prenos informaci:
      • po kazde zmene
      • v intervalech
      • na pozadani
    • kauzální doručování proti falešnému uváznutí
    • 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
    • phantom deadlock s cyklem mezi uzly?
  • edge-chasing
    • pošlu zprávu všem, na které čekám, pokud se vrátí, jsem v háji
    • ale mezitím se to ale mohlo doblokovat (řešení - aging, overkill - zpráva zároveň hledá kandidáta))
  • diffusing computation
  • detekce globalniho stavu - pri prijmu znacky proces zaznamena lokalni WFG

vzdalene spousteni procesu

  • nalezeni volneho pocitace
  • znalost vlastni zateze
  • spusteni vzdaleneho procesu - transparentnost, vytvoreni prostredi odpovidajiciho domacimu (kontexty, systemova volani - presmerovat x vzdalena)
  1. volny pocitac se zaregistruje do registru
  2. domovsky pocitac zada o nejaky volny registr
  3. alokace procesoru na volnem poc
  4. odregistrovani volneho z registru
  5. nastaveni prostredi
  6. nastartovani procesu
  7. beh procesu
  8. ukonceni procesu
  9. zprava o ukonceni domovskemu
  • pokud hostitel prestane byt volny (uzivatel se vratil z hospody)
    • zabit proces
    • nechat dobehnout
    • cas na ulozeni
    • premigrovat

alokace

  • up-down
    • koordinator ma tabulku s body pro kazdy procesor
    • pri kazde vyznamne udalosti (vytvoreni procesu, ukonceni) se posle zprava koordinatorovi
    • trestné body: + za proces jinde, - za neuspokojený požadavek, jinak směrem k nule
    • pri uvolneni procesoru se vybere proces jehoz procesor ma nejmin trestnych bodu
  • hierarchicky - manazer skupin
  • bidding alg - procesy kupuji vypocetni silu

migrace

  • vyvazovani zateze, shutdown, optimalizace
  • korektnost - ostatni procesy nejsou migraci ovlivneny
  • transparentnost - proces o migraci nevi - nemusi spolupracovat
  • problemy:
    • preneseni stavu a adres prostoru
    • komunikace mezi procesy
    • rezidualni dependence
    • vicenasobna migrace
  • prenos procesu:
    • zmrazeni
    • oznameni prijemci, alokace
    • prenos stavu - registry, zasobnik
    • prenos kodu / adres prostoru
    • presmerovani / doruceni zprav
    • dealokace, vycisteni
    • vazby na nove jadro, nastartovani
    • dokonceni prenosu vazeb, docisteni
  • virtualni pamet
    • preneseni cele
    • pre-copying
    • copy on reference - stranka se prenese az kdyz je vyzadovana, na zdrojove stanici se smaze
  • zpravy:
    • presmerovani - docasne/trvale
    • dat vedet predem
    • opakovani (no ACK)
    • migrace kanalu

systémy

  • DEMOS/MP (83, migrace - cíl si proces tahá k sobě, nepřijaté zprávy přeneseny při migraci)
  • Charlotte (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)
  • MOSIX (Izrael) - rozsireni struktury procesu o cas od posledni migrace, cas na procesoru, pricinu migrace ,...
  • 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 mechanizmus migrace entit)

load-balancing

  • uskali
    • jak porovnavat zatez
    • volba migrujiciho procesu
    • volba prijemce
  • párovy alg - vytvori se pary ktere se vzajemne vyvazuji, zatizenejsi procesor vybere proces podle miry vylepseni
  • vektorvy alg - první vždy vlastní zatez, pak pošle prvni půlku nahodnemu vektoru, došlá se proloží s vlastní pulkou
  • centralizované/hierarchické vyvažovací algoritmy - koordinator zna zateze svych procesoru
  • lokální (prahová hodnota, když přelezu, ptám se po volných n pocitacu, vyberu nejlepsi odpoved)
  • bidding alg
  • problémy - aktuálnost udaju, samotná zátěž algoritmu

distribuovane FS

  • monoliticky x oddelene adresarove a souborove sluzby
  • stavovy x bezestavovy
  • cache - v pameti serveru, pameti klienta - v adresovem prostoru procesu, jadre, cache manageru
  • posloupnost bytu x zaznamy x typovany
  • capability x ACL
  • upload model (stahnu a nahraju) x remote access model(otevre vzdalene)

replikace

  • spolehlivost
  • dostupnost
  • vykon
  • explicitni replika x odlozena replika x skupinova komunikace
  • aktualizacni protokoly
    • primarni replika - zmeny se provadi na jedne replice, ta se stara o aktualizaci ostatnich
    • vetsinove hlasovani - pro cteni/zapis potreba ziskat vetsinu hlasu, pri zadosti o cteni repliky posilaji cislo sve verze
    • vazene hlasovani - read a write quorum, r+w>N
      • hlasovani s duchy - server ktery se ucastni hlasovani pro write pri vypadku nejakeho serveru

klientocentricke konzistencni modely

  • eventualni konzistence
    • po skonceni vsech zapisu budou v konecnem case vsechny repliky aktualizovany
    • 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 precteni x, vsechna dalsi cteni vrati stejnou nebo novejsi hodnotu
    • při připojení k jiné replice uživatel vidí všechny dosud přečtené zprávy
  • monotonic write
    • zapis promenne proveden pred jakymkoliv dalsim zapisem te promenne
    • CVS commit na různých replikách
  • read your writes
    • zapis promenne proveden pred jakymkoliv jejim naslednym ctenim
    • po aktualizaci webové stránky si neprohlížím kopie z cache
  • 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

epidemicke protokoly

  • implementace eventualni konzistence
  • ve VELMI rozsahlych systemech
  • gossiping - s pravdepodobnosti 1/k prestane infikovat
    • push,pull,kombinace
    • problem s mazanim dat - casove omezeny certifikat smrti