Skupinov e zasl an zpr av, Multicasting PA 150 Principy operacnch syst em u Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Verze: podzim 2020 Model skupinov e komunikace (Multicast Communication) 2 Resen problemu sdelen zpravy vsem procesum nalezejcch do skupiny procesu, slozen skupiny je zname 2 Procesy mezi sebou komunikuj spolehlivymi 1:1 kanaly 2 Procesy mohou krachovat (krach = vypadek = fail-stop, proces bud' bez spravne nebo je necinny) 2 Vyslajc proces vysla zpravu m skupine procesu g jedinou operac, multicast(g, m) ta je implementovana v middleware nasobnymi operacemi na urovni sluzeb OS, send(p, m), kde p jsou id procesu ze skupiny g, p ∈ g 2 Zprava m je unikatne identi kovatelna, nese sebou jedinecny id odeslatele a jednoznacny id skupiny clovych procesu, g=group(m) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 1 Probl em skupinov e komunikace (Multicast Communication) 2 Uzel procesu v adresovane skupine zpravu prijme (operac receive) na urovni sluzeb OS, middleware ji doruc (operac deliver) aplikacnmu procesu 2 Procesu ve skupine g prijatou zpravu m doruc operace deliver(m), komplementarn operace k operaci multicast, s vlastnostmi: Zprava m mus byt dorucena vsem procesum aktivnm ve skupine g Pokud zpravu m zska jeden ze skupiny procesu g, mus ji zskat vsechny procesy aktivn ve skupine g Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 2 Probl em skupinov e komunikace (Multicast Communication) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 3 B azov e resen skupinov e komunikace 2 B-multicast(g, m) Basic-multicast { se (na urovni middleware) implementuje nasobnym provedenm spolehlivych operac send(p, m) z urovne OS ke vsem procesum p ze skupiny g Proveden spolehlivych operac send(p, m) lze zparalelnit pomoc vlaken odpovdajcch ve vyslajcm procesu procesum ve skupine g Pak ale potvrzen prijmut zpravy maj tendenci se kumulovat, vyslac zpravy je nemus stacit zpracovavat, opakuje proto vyslan, zprav, coz zpusobuje prchod dalsch potvrzen { ack-implosion 2 B-delivered(m), komplementarn operace k B-multicast, zpravu m pro proces p prijma v uzlu procesu p OS operac receive (m) a middleware ji dorucuje procesu p Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 4 B azov e resen skupinov e komunikace 2 Bazove resen skupinove komunikace nezarucuje splnen pozadavku dorucen zpravy vsem procesum ve skupine pokud vyslajc uzel vypadne behem vyslan operacemi send(p, m) implementujcmi B-multicast(g, m), nektere procesy zpravu dostanou, jine ne a procesy ve skupine g nemaj sanci tuto skutecnost (kdo zpravu dostal a kdo ne) zjistit 2 Spolehlive resen skupinove komunikace pozaduje: zprava je dorucena vsem procesum ve skupine, pokud ji zska jeden ze skupiny procesu, mus ji zskat vsechny procesy ve skupine Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 5 Spolehliv e (Reliable) resen skupinov e komunikace 2 Pozadovane vlastnosti operac R-multicast(g, m) a R-deliver(m) integrita { spolehliva 1:1 komunikace procesu korektne se chovajcmu procesu se dorucuje zprava m nejvyse jednou (zpravy lze jednoznacne identi kovat: napr. id zdroje + porad zpravy ve zdroji) validita { jestlize korektn proces skupinove rozesle zpravu m, zprava m nakonec bude dorucena dosazen shody { jestlize je zprava m dorucena jednomu korektnmu procesu skupiny, je dorucena vsem korektnm procesum ve skupine spolecne s validitou se jedna o zarukou zivosti algoritmu { pokud send odvozeny z multicast vysle alespon jednou zpravu k procesu skupiny, nesm vypadek originalnho vyslace ohrozit dorucen zpravy ke vsem procesum Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 6 Spolehliv e (Reliable) resen skupinov e komunikace 2 Spolehlivost se dosahuje nadstavbou bazoveho resen Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 7 Spolehliv e (Reliable) resen skupinov e komunikace 2 Je zajistena validita a shoda zpravu by nektery z procesu ve skupine neobdrzel pouze kdyby zadny proces skupiny neudelal B-multicast, tj. kdyby zadny nefungoval 2 integritu podporuje podpurny komunikacn system resc B-multicast 2 Spolehlive rozeslan je zaruceno i v asynchronnm systemu, o case se nic nepredpoklada 2 Kazda zprava je kazdemu procesu skupiny g zaslana |g|-krat, :-(( Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 8 Skupinov a komunikace se zachov anm porad zpr av 2 Jestlize je dulezite aby se dorucovan zprav se odehravalo v de novanem porad, existuj 3 typy razen multicastu: FIFO razen { provede-li korektn proces multicast(g, a) pred multicast(g, b), pak kazdy korektn proces v g, ktery zskava zpravu b, zska zpravu a pred zskanm zpravy b kauzaln razen { jestlize multicast(a) predchaz multicast(b) v g z hlediska zaslan zprav mezi procesy ve skupine g, pak kazdy korektn proces v g, ktery zskava zpravu b, zska zpravu a pred zskanm zpravy b totaln razen { jestlize nektery korektn proces v g zskava zpravu a pred zskanm zpravy b, pak kazdy korektn proces v g, ktery zskava zpravu b, zska zpravu a pred zskanm zpravy b Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 9 Skupinov a komunikace se zachov anm porad zpr av 2 Kauzaln razen prirozene implikuje FIFO razen 2 Kauzaln razen a FIFO razen jsou castecna usporadan 2 De nice razen nepredpoklada ani neimplikuje spolehlivost dorucen Napr. pri totalnm razen jestlize je korektnmu procesu p dorucena zprava a po n zprava b, procesu q muze byt dorucena a bez dorucen b nebo jinych zprav razenych za a Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 10 Paradigmata dorucov an zpr av v asychr. DS Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 11 Skupinov a komunikace se zachov anm FIFO porad zpr av Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 12 Implementace FIFO razen 2 Pro kazdy proces p ze skupiny g middleware (MW) udrzuje promenne Sp g { ctac zprav vyslanych procesem p do skupiny g Rq g { pro kazdy proces q ze skupiny g cslo posledn zpravy ze zprav zaslanych do g procesem q a dorucenych procesu p 2 Pri vyslan operac multicast pridava MW ke zprave S = Sp g a pote Sp g inkrementuje o 1, zpravy z p poradove csluje 2 Pri prijet zpravy od q pro p MW kontroluje Rq g a S ze zpravy jestlize S = Rq g + 1, MW zpravu doruc p a nastav Rq g = S jestlize S > Rq g + 1, MW zpravu zapamatuje ve vyrovnavac fronte a doruc ji procesu p az bude platit Rq g + 1 = S 2 Jestlize se pouzije spolehlive rozeslan, R-multicast, zskame spolehlive FIFO rozeslan Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 13 Skupinov a komunikace se zachov anm kauz alnho porad Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 14 Skupinov a komunikace se zachov anm kauz alnho porad Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 15 Implementace kauz alnho razen 2 Bazova idea Respektovan relace stalo-se-pˇred na bazi logickeho casu hnaneho rozeslanm a dorucovanm (multicast) zprav Msto prosteho casoveho raztka TS, ve zpravach pouzijeme vektorove casove raztko V Vektorove casove raztko V ma tolik prvku kolik je procesu ve skupine, inicialne jsou vsechny prvky V nulove Kazdy proces pi udrzuje sve vlastn vektorove casove raztko Vi Kdyz proces rozesla zpravu procesum ve skupine, nejprve inkrementuje svuj cas ve svem V a pote zpravu s V rozesle Kdyz se prijme zprava m pro proces q od procesu p, muze mu byt dorucena az kdyz se mu doruc zpravy, ktere ji kauzalne predchazej tj. az se q doruc vsechny predchoz zpravy vyslane procesem p a az se q doruc vsechny zpravy, ktere byly doruceny procesu p do doby, kdy p rozeslal m Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 16 Implementace kauz alnho razen vektorov ymi cas. raztky Jestlize se pouzije spolehlive rozeslan, R-multicast, zskame spolehlive kauzaln rozeslan Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 17 Kauz alnho razen vektorov ymi cas. raztky Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 18 Skupinov a komunikace se zachov anm tot alnho porad Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 19 Ilustrace dopadu nedodrzen tot alnho porad 2 Obe replikace databaze se ocitnou v nekonzistentnm stavu Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 20 Implementace tot alnho razen, 2 Analogicke resen jako FIFO razen, ctac rozeslanych zprav ale mus byt ve skupine procesu jedinecny 2 centralizovane resen DS podporuje pouze FIFO kanaly Zpravy rozesla vsem procesum ve skupine jeden centraln proces CP Proces P rozeslajc zpravu M posle tuto zpravu CP CP rozesle vsem procesum ve skupine zpravu {P, M} Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 21 Implementace tot alnho razen, sequencerem 2 Resen totalnho razen pomoc sequenceru Ctac rozeslanych zprav udrzuje jeden proces ve skupine - sequencer Kazdy proces, ktery chce rozeslat zpravu ji s jedinecnym indexem rozesle procesum ve skupine a sequenceru jedinecny index { napr. id procesu + poradove cslo zpravy v procesu prijatou zpravu middleware umst do vyrovnavac fronty sequencer urc jemu dorucene zprave jej poradove cslo a toto cslo s indexem zpravy rozesle procesum ve skupine Middleware pro kazdy proces ve skupine dorucuje prijate zpravy z vyrovnavac fronty v porad poradovych csel Sequencer z hlediska komunikacn zateze a spolehlivosti je uzkym pro lem resen Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 22 Implementace tot alnho razen, sequencerem Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 23 Implementace tot alnho razen, dohodou 2 Trfazovy distribuovany algoritmus 2 Princip algoritmu: Kazdy proces q si pamatuje v promenne Aq g nejvyss jemu zname dohodnute poradove cslo zpravy nekterym procesem rozeslane do g kazdy proces q vytvar a udrzuje v promenne P q g jm navrhovane poradove cslo zpravy proces p rozesle zakladnm rozeslanm (B-multicast) vsem procesum ve skupine jedinecne indexovanou (i) rozeslanou zpravu < m, i >, procesy si ji zapamatuj na urovni receive Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 24 Implementace tot alnho razen, dohodou proces q, ktery prijal zpravu < m, i > vrat procesu p jm navrhovane poradove cslo zpravy < m, i > jako hodnotu P q g = max(Aq g, P q g ) + 1 proces p vybere nejvets navrhovane cslo zpravy < m, i >, oznacme je a, a toto zakladnm rozeslanm rozesle vsem procesum skupiny jako dohodnute poradove cslo zpravy < m, i > kazdy proces q ve skupine si nastav Aq g = max(Aq g, a) zprava < m, i > je pak dorucena kazdemu procesu ve skupine v takto dohodnutem porad Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 25 Implementace tot alnho razen, dohodou Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 26 Implementace tot alnho razen, dohodou Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 27 Implementace tot alnho razen, dohodou Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 28 Implementace tot alnho razen, dohodou Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 29