Transakce, soub eznost a uv aznut v distribuovan em prostred

Osnova p redna sky

2

Transakce, soube znost a uvaznut

X Transakce, na jejichz proveden se podl vce nez jeden server

v distribuovanem prost red

(uzel ste, uzel distribuovaneho systemu)

2

Dvoufazov y protokol dosazen shody o forme proveden (commit/abort) distribuovane transakce

2

Zamykan , synchronizace distribuovanych procesu

2

Uvaznut v distribuovanem systemu

PA 150 Principy operacn ch system u

Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ }

Distribuovane transakce

w A| y < 5 4 23 1 0 / -. , )+ ( %&' $ # !"

Æ

Verze : podzim 2016 Jan Staudek, FI MU Brno

Distribuovana transakce, koncept

2 2 2

Distribuovana transakce zahrnuje operace provad ene ve vce serverech (uzlech DS ) formou dlcch subtransakc Uzly DS mohou vzajemn e komunikovat, obecne { kazdy s kazdym Mus byt zachovan bazov y princip transakce { atomicita, A

2 2

2

s clem zajistit atomicitu transakce aktivovane klientem

(TPM)

PA150 { Transakce a soube znost v distribuovanem prost red

Server { systemov y proces bez c v nekterem uzlu DS X koordinator transakce T, je soucast TPM, middleware ' X zajist uje start a ukoncen distribuovane transakce

X pomoc koordinacnch procesu realizovanych na urovni middleware |

Pouzita technologie { model klient-server Klient { aplikacn proces bez c v nekterem uzlu DS koordinatora teto transakce T (server bez c v nekterem uzlu DS), X r es program de nujc transakci spocvajc ve volan posloupnost operac r escch transakci (subtransakc) vesmes rozmstenych v ruzn ych uzlech DS napr. podle jimi spravovanych objektu apod. X aktivuje krach nebo prohla sen hotove transakce T za provedenou z adost zaslanou na koordinatora jm spustene transakce T

Mus byt zachovany pochopitelne i ostatn vlastnosti transakc { CID Subtransakce realizovane v ruzn ych uzlech DS proto na ukoncovan sve transakce kooperuj

Jan Staudek, FI MU Brno

1

X aktivuje realizaci transakce T z adost zaslanou na

jednotkou r dic transakci nebo se neprovede z adn a z nich

2



X Bud'to se provedou vsechny operace urcene programovou 2

|

2


|


3

Transaction Processing Monitors, TPM

2

Transaction Processing Monitors, TPM

Puvodn idea vzniku TPM

2

X 70./80. XX.stol { teleprocessing monitor X podpora velkeho mnozstv terminal u jedne aplikace

2

(rezervace letenek, . . . )

2

X X X X

Soucasne pojet funkcionality TPM X X X X X

Transaction Processing Monitor

poskytovan API sluzeb pro distribuovane r esen transakc trvale frontovan pozadavku klientu a reakc serveru smerovan klienta na relevantn servery koordinace behu protokolu pro ustanoven naln ho stavu distribuovane transakce na { provedena, commited a nebo na { zkrachovala, aborted tzv. 2-phase Commit Protocol, 2PCP Jan Staudek, FI MU Brno

|


4

TPM, process-per-client model



|


5

X server je vcevlaknov y, prepnan mezi vlakny r es server (ULT)

klienta { terminal, libovolny uzel DS X kazdy server komunikuje s jednm terminalem { klientem, r es autentizaci klienta a provad akce volane metodami z klienta X vysoka pamet'ova naro cnost, c aste prepnan kontextu mezi procesy zvysuje rezii CPU/OS X servery bez na 1 poctaci, nevhodny model pro distribuovane transakce pracujc se vzdalen ymi objekty rozlozenymi ve vce uzlech |

process-per-client model single-server model many-server, single-router model many-server, many-router model

TPM, single-server model

X jeden serverovsky proces v databazov em uzlu pro kazdeho jednoho


Architektura TPM: klient-server Modely TPM

klienti nejsou blokovan, je mens rezie prepnan kontextu X autentizaci r es server nikoli OS X vsechny aplikace jsou r esene vlakny jednoho serveru, ochrana mezi nimi se na urovni serveru nezajist'uje X vlakna bez v 1 poctaci, nevhodny model pro distribuovane transakce pracujc se vzdalen ymi objekty rozlozenymi ve vce uzlech 6


|


7

TPM, many-server, many-router model

TPM, many-server, single-router model

X vce aplikacnch procesu pristupuje do spolecne (distribuovane) DB X klienti komunikuj s jednm smerovacm procesem (router),

ktery je smeruje na relevantn servery X nezavisl e aplikace r es nezavisl e servery X severovske procesy jsou vcevlaknov e, obsluhuj soubez ne vce klientu X model vhodny pro distribuovanem prostred, typicke r esen pro Web servery Jan Staudek, FI MU Brno

|


X soudobe univerzaln r esen TPM pro distribuovane transakce X soucast serverovskych prostred jsou spravci r zen soubez nost,

obnovy a r esen transakc { koordinato ri transakc (na urovni TPM) X komunikace klient-server { Remote Procedure Call (RPC)

8


Prub ehy operac subtransakc v jednotlivych uzlech DS r d spravci , funkcnosti na urovni TPM

2

X Subtransakce nale zejc transakci T jsou spoustene klientem,

v uzlech DS jsou aktivovane dynamicky volan m metod z klienta X spravci transakc { jsou procesy bez c v uzlech DS, jsou soucast TPM, middleware { r d validnost soubez nosti (sub)transakc { udrzuj denk pro u cel obnovy po vypadku { spolupracuj s koordinatorem transakce na rozhodnut zda se transakce prohlas za provedenou nebo zda krachuje X algoritmy obnovy i r zen soubez nosti se mus pochopitelne upravit pro distribuovane prostred


|



9



2

|

2

2

10

Klient zahajujc transakci zasla pozadavek openTransaction (n.b. t begin) koordinatorovi transakc r dcmu chod zahajovane transakce, Ci (sluzba v TPM v urcenem uzlu i) Koordinator transakc Ci klientovi vrac id transakce, T { jednoznacny identi kator transakce v DS (napr. IP adresa i + poradove c slo transakce v i) a prebra roli koordinatora transakce T, ktery openTransaction pro transakci T provede Proces klienta a procesy, r esc pozadavky klienta jako c asti distribuovane transakce, mus byt schopn s koordinatorem transakce komunikovat, obv. via RPC, aby mohly koordinovat svoje akce pri prechodu transakce do stavu provedena (commit) nebo zrusena (abort), Jan Staudek, FI MU Brno

|


11


2 2 2 2

2


Koordinator transakce T registruje existenci transakce T a posleze i koordinuje jej ukoncen (commit / abort) Uzly zu castnene na r esen transakce T tvor tzv. ,,kohortu T", nazyv ame je participujc uzly na transakci T c asti transakce realizovane v participujcch uzlech nazyv ame subtransakce, obvykle se aktivuj volan m metod klientem v participujcm uzlu transakce T se zrizuje objekt participant, ktery je odpovedny za sledovan stavu obnovitelnych objektu v danem serveru zprstupnovan ych transakc T a kooperuje s koordinatorem pri ukoncovan transakce T participanti se registruj u koordinator u svych transakc operac join Jan Staudek, FI MU Brno

|


12

Koordinator transakce { registruje spusten transakce, { registruje participanty, prp. sam del transakci na subtransakce a { r es, koordinuje akce pri ukoncovan transakce

2

Spravce transakce v uzlu kohorty, participant { udrzuje denk pro obnovu transakc { participuje na schematu r zen soubez nosti

2

Kazdy participant mu ze kdykoliv volat koordinatora pozadavkem abortTransaction, pokud z nejakeho duvodu nen schopny jeho uzel v r esen subtransakce pokracovat Jan Staudek, FI MU Brno

|


2

2

2 2

koordinator T si udrzuje seznam participantu transakce T participanti (subtransakce) si relevantn sluzbou svych TPM udrzuj referenci na sveho koordinatora a komunikuj s nm pri ukoncovan transakce, commit / abort u cast participanta na transakci: { registrace u koordinatora + { sprava objektu zprstupnovan ych subtransakc + { kooperace s koordinatorem pri ukoncovan transakce bud'to vsichni participanti sve subtransakce provedou (a potvrd) { transakce se stane provedenou, commit nebo vsichni participanti zrus akce provedene v ramci subtransakc { transakce zkrachuje (abort) Jan Staudek, FI MU Brno

|


13

Konceptualn schema funkcn ch komponent TPM


2

2

14


|


15

P r klad, distribuovana bankovn transakce


2

Klientova transakce zahrnuje praci s u cty A,B, C a D X X X X

2

u cet A spravuje server v pobocce X u cet B spravuje server v pobocce Y u cty C a D spravuje server v pobocce Z transakce { prena s 4 USD z u ctu A do do u ctu C a { prena s 3 USD z u ctu B do u ctu D

Koordinator transakce mu ze byt situovany v kteremkoliv serveru X napr. v severu pobocky X, ktera je napr. umstena v centrale banky


|


16



|



|


17


18


|


19

sen Re problemu ukoncen transakce { Commit protocols


2 2

2 2

2

klient otevre transakci a zska jej identi kator, T Posleze klient vyvolav a metody predepsane programem transakce realizovane v ramci otevrene transakce napr. b.withdraw (T,3) v serveru Y Invokovany objekt b v serveru Y informuje objekt participant v tomto serveru o tom, z e nale z transakci T pokud tak objekt participant v serveru Y dosud neucinil, informuje objekt participant koordinatora, z e nale z transakci T po aplikacnm dokoncen transakce, klient nakonec informuje koordinatora transakce o konci transakce pozadavkem closeTransaction Jan Staudek, FI MU Brno

|


2 2 2 2

X abort { napr. se mu nepodarilo se spojit s nekterym uzlem nebo

zjistil narusen konzistence DB, . . .

2 2

20

2

2

2

21

Pro r esen ukoncen distribuovane transakce je jednoduchy, 1-fazov y, commit protokol nedostatecny nedav a tm moznost z adn emu participantu c i koordinatorovi aby on jednostranne rozhodl o zkrachovan transakce X Napr. dky zamykan mu ze mezi servery vzniknout uvaznut , ktere vede ke zkrachovan transakce, ale o tom se klient nedozv, dokud nevyda dals pozadavek na server, dokud mu neuplyne time-out, . . . X Napr. pri r esen soubez nosti transakc odhalen nevalidnosti planu by melo vyvolat krach transakce bez zavislosti na rozhodnut klienta X Napr. koordinator nemus vedet, z e jisty server mel behem r esen transakce vypadek a obnovoval svoji c innost v prub ehu distribuovane transakce a koordinator by mel tudz transakci abortovat

X Duvody { viz dale



X Kdyz klient rozhodne ukoncit transakci r adn e, commit,

a to opakovane dokud mu kazdy participant nesdel, z e u sebe provedl commit nebo abort jm r esene subtransakce Pro r esen ukoncen distribuovane transakce je jednoduchy, 1-fazov y, commit protokol nedostatecny

|

|

Jednoduchy, 1-fazov y, commit protokol

O typu ukoncen (proveden / krach) transakce rozhoduje klient, ktery transakci vyvolal Koordinator postupne (opakovane) sdeluje participantum podle pozadavku klienta zda maj provest commit nebo abort,


Atomicke ukoncen distribuovane transakce se mus r dit jistymi pravidly, protokolem Jedna se o preveden hotove transakce na provedenou transakci { commit, proto commit protocol Jan Staudek, FI MU Brno

Jednoduchy, 1-fazov y, commit protokol

2

Problem { zajisten atomicity (distribuovane) transakce Klient pozadal koordinatora o otevren transakce Pote klient postupne vyzadal provad en operac na vce serverech Nakonec klient z ad a koordinatora o closeTransaction, ukoncen transakce formou commit nebo abort

22


|


23

2-fazov y commit protokol

2


Jedna se o zvla stn prpad problemu Byzantskych general u

2

X distribuovana dohoda subtransakc zda transakci koncit r adn e c i

krachovat v prostred s vypadky uzlu X v distribuovanych databazov ych systemech zajist'uje globaln atomicitu transakc v prostred vypadk u uzlu a komunikac za predpokladu, z e vypadky budou nakonec opravene a kazdy uzel (participant) zaruc atomicitu sve subtransakce na sve lokaln urovni. X Lokaln atomicita subtransakce nestac, clem je globaln atomicita, ta nemu ze byt zarucena implicitne. X Globaln synchronizace distribuovane transakce mu ze skoncit

X synchronizacn protokol, ktery r es problem atomickeho ukoncen X umoznuje kazdemu participantu jednostranne abortovat

svoji c ast transakce

X jestli jedna subtransakce krachuje, krachuje cela transakce X jestlize se r adn e ukonc vsechny subtransakce,

r adn e se ukoncuje cela transakce

2

v nekterych uzlech provedenm subtransakce a v jinych krachem

a preveden transakce do stavu provedna X abort { zrusen u cinku subtransakc ve vsech uzlech Si, pokud alespon jedna subtransakce zkrachovala, a zrusen transakce

synchronizacn protokol, ktery zajist jednoznacny konecny vysledek pro kazdou distribuovanou transakci bez ohledu na vypadky uzlu. |



24

2PCP zajist'uje, z e

2

X distribuovana transakce se bud' r adn e ukonc

a vsechny jej u cinky se stanou trvale ve vsech participujcch uzlech X nebo distribuovana transakce zkrachuje a vsechny jej u cinky ve vsech uzlech se zrus, jako by se transakce nikdy nevykonala. 2

2

operace, klient pozad a koordinatora o ukoncen transakce X koordinator spoust 2PCP. X detaily behu 2PCP viz dale


25

2PCP se sklad a ze dvou faz , jmenovite z hlasovac faze a z faze vydan rozhodnut. Hlasovac faze z e subtransakci r adn e ukonc, kdyz ve fazi vydan rozhodnut k tomu dostanou pokyn { hlasuj ano / ne pro ukoncen transakce X Jakmile participant obdrz vyzvu k hlasovan , over na nej navazanou subtransakci z pohledu konzistence dat. X Pokud lze subtransakci r adn e ukoncit (tj. prosla validace), hlasuje ano. X V opacnem prpade hlasuje ne, subtransakci nasledn e bez dalsho c ekan krachuje, rus subtransakc zpusoben e u cinky a uvoln se vsechny subtransakc drzene zdroje (zamky, . . . ).

X Kazda transakce ma v nekterem uzlu DS koordinatora. X Pote, co transakce z hlediska klienta dokonc vsechny aplikacn

|


X Koordinator z ad a vsechny participanty transakce o zavazek,

Spusten 2PCP


|

sen Re ukoncen transakce, Two-Phase Commit Protocol


2

Ukoncen transakce pomoc 2PCP koordinuje koordinator, vysledkem rozhodnut koordinatora mu ze byt X commit { potvrzen proveden subtransakc ve vsech uzlech Si

X To ohrozuje globaln atomicitu a tudz konzistenci DBS X Dosazen atomicity na globaln urovni vyzaduje pouzt


Two-Phase Commit Protocol, (2PCP nebo take 2PCP)

26


|


27


2


Ve faz vydan rozhodnut koordinator transakce rozhoduje

2

X zda r adn e ukoncit transakci, pokud jsou

vsichni participanti pripraveni r adn e ukoncit transakci (hlasovali ano) X nebo zda zkrachovat, pokud se kterykoliv participant rozhodl transakci zkrachovat (hlasoval ne). 2

2

V prpade vydan rozhodnut r adn e ukoncit transakci, koordinator vysla vsem participantum zpravy commit (radn e ukoncit), transakce se stane provedenou V prpade vydan rozhodnut zkrachovat transakci koordinator odesla zpravy abort (zkrachovat), a to pouze tem participantum, kter jsou pripraveni r adn e ukoncit transakci (hlasovali ano), transakce se stane zkrachovalou Jan Staudek, FI MU Brno

|


2

2

2

2 2

|


|


29


Jakmile koordinator obdrz potvrzen od vsech participantu, pak v prpade, z e hlasovali ano, zapomene na transakci, vymaze veskere informace tykaj c se transakce z protokolove tabulky udrzovane v hlavn pameti. Odolnost 2PCP vu ci vypadk um se dosahuje zaznamenav an m prub ehu protokolu do denku udrzovanych jak koordinatorem, tak i participanty. Denky se udrzuj ve stabilnch, energeticky nezavisl ych pametech, vypadky je neznic. Koordinator zapisuje zaznam decision do denku prmo (bez vyrovnav an toku dat na urovni OS), jeste pred odeslan m sveho rozhodnut participantum. Jan Staudek, FI MU Brno


28


2

2

Jestlize participant hlasoval ano, nemu ze subtransakci jednostranne ani r adn e ukoncit ani zkrachovat, mus c ekat, dokud od koordinatora neobdrz konecne rozhodnut. Participant je tudz po neurcitou dobu blokovany (okno nejistoty), c eka na rozhodnut koordinatora. Jakmile participant obdrz naln rozhodnut koordinatora, rozhodnut respektuje a vykona odpovdajc akce a uvoln vsechny zdroje, ktere subtransakce drz, a obvykle odesle zpet koordinatorovi potvrzen (ACK ) Zamky vyzadan e transakc si transakce mus drzet az do sveho ukoncen

30

2

2 2

2

Stejne tak kazdy participant zapisuje do sveho denku zaznam prepared pred zaslan m hlasu ano a zaznam decision pred zaslan m potvrzen rozhodnut. Kdyz koordinator protokol ukoncuje, zapisuje uz bez nym (vyrovnavan ym) zapisem do denku zaznam end Tento zaznam indikuje, z e vsichni participanti obdrzeli rozhodnut, a z e z adn y z nich se v budoucnosti nebude dotazovat na stav transakce. Po te koordinator mu ze na transakci z pohledu 2PCP (trvale) zapomenout


|


31

Two-Phase Commit Protocol (2PCP), dlc kroky


je hotova, klient pozadal koordinatora koordinatora Ci o naln uzavren Ti { zajisten stavu provedena / zkrachovala koordinator Ci spoust 2PCP Faze 1 , COMMIT-REQUEST phase, resp. voting phase

2

2 Ti

2 2

X pokud je subtransakce v si ve stavu hotova, { manazer transakce v si je pripraveny subtran. potvrdit (commit), { udela v denku zaznam a vse v denku o T

zaps e do stabiln pameti a odpov koordinatorovi na dotaz canCommit?(T) odpoved Yes { odpoved Yes uzel si kohorty slibuje koordinatorovi Ci , z e bude reagovat ukoncenm ve 2. fazi 2PCP, vse ma poznaceno v denku ve stabiln pameti X pokud nen subtransakce v si stavu hotova, zkrachovala { si do denku poznac <no T> a koordinatorovi odpov na dotaz canCommit?(T) odpoved No X Ci c eka na odpoved' od vsech participantu X odpoved' nemus byt okamzita, pri spusten 2PCP mohou v nekterych si subtransakce jeste bez et

X Koordinator Ci pripravuje kohortu na potvrzen proveden transakce tm, z e zasla vsem uzlum kohorty z adost o sdelen souhlasu s commit,

zpravu typu canCommit?(T), prp. prepare T apod. X Ci prida do logu (denku) ve stabiln pameti zaznam <prepare T> X Ci posle vsem uzlum kohorty plncm T zpravu canCommit?(T) X Spravce transakce participanta rozhoduje, zda je pripraveny na commit sve c asti transakce


|


Faze 1 , COMMIT-REQUEST phase, detaily, pokr.

32


Faze 1 , COMMIT-REQUEST phase, detaily, pokr.

2


Faze 2, COMMIT phase, ukoncen podle vysledku hlasovan X

likviduje u cinky transakce, uvolnuje zdroje, . . .

|

33

prijal odpovedi na dotaz canCommit?(T) od vsech participantu nebo uplynul predde novany c asovy limit po rozeslan canCommit?(T) X Ci potvrzuje nebo rus transakci ve vsech uzlech kohorty podle zjisten stavu ze zprav (reakc na canCommit?(T)) zskanych ve fazi 1 2PCP: { vsechny odpovedi r kaj Yes: rozhodnut je T je provedena (commit) { alespon jedna odpoved' r ka No, nebo alespon jeden uzel kohorty neodpovedel: rozhodnut je T zkrachovala (abort) X koordinator prida do den´ıku nebo podle vysledku rozhodnut a denk zaps e do stabiln pameti X zaznam ve stabiln pameti je i v prpade poruchy nerevokovatelny, osud transakce je zpeceten

X vyslan canCommit?(T) mlccm participantum lze zopakovat X pokud participant hlasuje No, sam krachuje okamzite





2

|

34

Ci


|


35


2

Stavovy diagram 2PCP

Faze 2, COMMIT phase, ukoncen podle vysledku hlasovan , pokr. X koordinator posle kazdemu uzlu kohorty zpravu

s informac o naln m rozhodnut (doCommit (T) / doAbort (T)) X kazdy uzel kohorty zaznamena zpravu (rozhodnut) do sveho logu a koordinatorovi sdel potvrzujc zpravu haveCommited(T) (ACK) a zpracovan transakce u sebe ukonc


|



36

Prvn faze { hlasovac faze

2

X

X

zda transakci r adn e ukoncit nebo krachovat kazdy participant sdeluje zda transakci ukoncit nebo krachovat jakmile participant r ekne ukoncit, nesm posleze r ci krachovat tj. kdyz participant r ekne ukoncit, mus si byt jisty, z e bude schopny dokoncit svoji c ast commit protokolu, i kdyz mezi tm vypadne a obnov svoji c innost, denk mus mt zapsany na disku jakmile participant ma vsechny svoje objekty zmenene v prub ehu transakce uchovane v permanentn pameti, je pripraveny kdykoliv posleze potvrdit r adn e ukoncen transakce v permamentn pameti mus mt poznaceny i stav pripraveny


|


37

Druha faze { vydan rozhodnut o hlasovan X koordinator sdel participantum rozhodnut, vysledek hlasovan X kazdy participant realizuje rozhodnut X jestlize alespon jeden participant hlasoval abort, krachovat,

X koordinator transakce vyzve participanty ke sdelen X X X


Two-Phase Commit Protocol, rekapitulace

Two-Phase Commit Protocol, rekapitulace

2

|

rozhodnut zn zkrachovat transakci X jestlize vsichni participanti hlasovali commit, ukoncit, rozhodnut zn ukoncit transakci { commit 2

Problemy X X X X

38

mus se zajistit, aby hlasovali vsichni participanti mus se zajistit, aby vsichni realizovali spolecne naln rozhodnut trivialn r esen techto problemu je v prostred bez poruch 2PCP ale mus spravn e pracovat i v prpadech vypadk u serveru, ztrat zprav nebo docasnych vypadk u schopnosti komunikace mezi servery Jan Staudek, FI MU Brno

|


39

Model poruch pro Two-Phase Commit Protocol

2 2 2 2


Realn y distribuovany system = asynchronn distribuovany system Servery mohou vypadavat, zpravy se mohou ztracet Podpurn y komunikacn system odstranuje porusene a duplikovane zpravy Nejedna se o byzantinske chyby

2

X Obecne plat {

dosazen dohody nen v plne asynchronnch systemech mozne 2

procesu novymi procesy, jejichz stav je nastaveny podle informac uchovavan ych v permanentn pameti a informac drzenych jinymi procesy X proces mozna po jistou dobu nereaguje, ale kdyz reaguje, reaguje validne

Pripomenut { byzantinska chyba X proces mu ze nastavit chybny obsah zpravy nebo na z adost vracet

chybnou hodnotu, mu ze duplikovat odpoved', . . . X byzantinskou chybu nelze detekovat pozorovan m, zda proces odpovedel na invokaci, proces mu ze odpoved' vynechat Jan Staudek, FI MU Brno

|


40



2

v kazdem uzlu/participantu mus spravce transakc mus udrzovat denk, write-ahead log

2

zrusit (viz predna ska Transakce): { objekt se modi kuje pouze po zaznamenan undo info do logu { pred potvrzenm zmen ze zaznamenaj redo a undo logy do stabiln pameti

2 2

Prpomnka { protokol 2PCP je navrzeny

X s clem umoznit participantu zkrachovat, zrusit svoji c ast transakce

(z duvodu zachovan atomicity krachuje cela transakce) X pro praci v asynchronnm (distribuovanem) systemu, ve kterem mohou vypadavat uzly (servery) a ztracet se zpravy { se nejedna o byzantinske (libovolne) chyby, server bud' vypadne nebo se r d vyslanymi zpravami { od podpurn eho systemu request-reply se ocekav a, z e odstran vsechny porusene, prp. duplikovane zpravy Jan Staudek, FI MU Brno

|


|


41

Komunikace v 2PCP

X aby bylo mozne pri restartu uzlu po jeho vypadku u cinky subtransakce

2

Two-Phase Commit Protocol v asynchronnm prostred dohody dosahuje za omezujc podmnky: X vypadky procesu (serveru) jsou maskovane obnovou vypadlych

X Server bud'to vypadne nebo se r d zaslanymi zpravami 2

Two-Phase Commit Protocol je prklad protokolu pro dosazen dohody

2

Koordinator v prub ehu transakce, az na sdelen participanta o pripojen k transakci (join), s participanty nekomunikuje Pozadavek na commit nebo abort transakce predav a koordinatorovi klient Pokud klient z ad a pri ukoncovan transakce abortTransaction nebo kdyz nektery participant hlas abort, koordinator informuje participanty okamzite Vme jiz, z e 2PCP nastupuje do sve role v okamziku, kdy klient pozaduje commitTransaction (ukoncit transakci) X V 1. fazi koordinator z ad a vsechny participanty, aby r ekli, zda jsou pripraveni na commit X ve 2. fazi koordinator participantum r ka, at' udelaj akce odpovdajc commit nebo abort

42


|


43

Komunikace v 2PCP

Vypadky p ri r esen 2PCP

2

2

Komunikace mezi koordinatorem a participanty mu ze selhat, duvody { nektery server vypadne { nebo komunikacn system ztrat zpravu sitelnost dosazen dohody se podporuje sledovan Re c asovych vypadk u (time-outs) { system je pseudoasynchronn X Po c asovem vypadku mus proces c ekajc na udalost provest

2

relevantn akci X Kazdy krok, ve kterem se c eka na udalost, mus byt osetreny hldan m c asoveho limitu X V asynchronnm systemu uplynut c asoveho limitu nemus implikovat trvalou poruchu serveru

Slozitost pri N c lenech kohorty X 3N zprav, ve 3 c asovych rundach X haveCommited (ACK) se nepocta, 2PCP funguje i bez n

zprava slouz k indikaci moznosti odstranit zastarale informace

2

Stav neurcitosti v participantu = c ekan na naln rozhodnut Jan Staudek, FI MU Brno

|


44


2

2

X Vypadky uzlu a komunikac jsou detekovane timeouty,

hldan m uplynut c asovych limitu. X Kdyz c inny uzel detekuje vypadek evokuje Recovery Manager, jehoz ukolem je vypadek zvladnout. X V 2PCP mu ze selhat uzel s koordinatorem nebo uzel participanta. X V 2PCP jsou c tyri msta, kde mu ze dojt k selhan komunikace.

|


|


45

V 2PCP jsou cty ri msta, kde mu ze dojt k selhan komunikace

Zotaven ve 2PCP



46

Participant c eka na zpravu s vyzvou k hlasovan . Participant jeste nehlasoval. V tomto prpade participant mu ze rozhodnout o zkrachovan subtransakce jednostranne.


|


47


2

X Participant hlasoval ano, ale neobdrzel rozhodnut ukoncit/zkrachovat.

Koordinator c eka na hlasovan participantu. Vzhledem k tomu, z e koordinator dosud neucinil konecne rozhodnut, z adn y participant se nemohl r adn e ukoncit, kordinator mu ze rozhodnout zkrachovat.


|


V tomto prpade se participant nemu ze rozhodnout jednostranne, protoze nen jasne, jake rozhodnut koordinator vyda. Participant je v tomto prpade blokovan, dokud znovu nenava ze komunikaci s koordinatorem a pote, co ji znovu nava ze, participant pozad a od koordinatora o konecne rozhodnut, prosad pokracovan protokolu a potvrd koordinatorovi rozhodnut.

48


2


Koordinator c eka na potvrzovan od participantu. V tomto prpade koordinator po obnove komunikace znovu posla rozhodnut tem participantum, kter rozhodnut dosud nepotvrdili.


|



|


49


2

Pripomenut X Koordinator nemu ze jen tak jednoduse vymazat informace tykaj c se

transakce z protokolove tabulky nebo ze sveho stabilnho denku dokud neobdrz potvrzen od vsech participantu.

50


|


51

Obnova koordinatora po vypadku uzlu koordinatora

Obnova participanta po vypadku uzlu participanta

X koordinator po restartu c te denk ze stabiln pameti a znovu vytva r

X vyhledav a ve svem denku existenci transakc, ktere jsou ve stavu

protokolarn tabulku tak, aby zachycovala stav 2PCP pro vsechny probhajc transakce pred vypadkem. X Transakce, ktere byly aktivn podle koordinatora pred jeho vypadkem a nemaj v denku zaznam decision, koordinator krachuje. X Transakcm, ktere zacaly 2PCP a jeste ho nedokoncily pred vypadkem (tj. transakce, ktere maj v jeho denku zaznamy decision bez odpovdajcch zaznam u end ) koordinator dokonc protokol zaslan m rozhodnut a vycka na jejich potvrzen. Jelikoz nekter z participantu jiz mohli obdrzet rozhodnut pred vypadkem a prosadili ho, mohli tito u castnci jiz zapomenout, z e tato transakce kdy existovala. Takov u castnci jednoduse odpov slepym potvrzenm, kterym indikuj, z e jiz obdrzeli a prosadili rozhodnut pred vypadkem.


|


,,pripravena na ukoncen" (tj. maj v denku zaznam prepared bez zaznamu decision). X Pro vyhledanou transakci participant pozad a koordinatora o zaslan rozhodnut a pote co rozhodnut obdrz prosad rozhodnut a potvrd. X Koordinator bude vzdy schopny reagovat na tyto dotazy, protoze transakci nemu ze zapomenout drve, nez obdrz potvrzen vsech participantu. X Nicmen e, ex. prpad, kdy participant mu ze byt ve stavu pripraveny na r adn e ukoncen a koordinator si transakci nepamatuje: Koordinator selze pote, co poslal zpravu vyzadujc hlasovat a tesne pred tm, nez ucinil sve rozhodnut. V tomto prpade, koordinator po obnove o transakci nev. Participant pripraveny k ukoncen si vyzad a stav T od koordinatora, ten predpoklad a z e transakce zkrachovala, reaguje zpravou abort.

52



2

Participant hlasoval v 1. fazi 2PCP Yes a c eka na sdelen vysledku dohody { commit / abort

2

2

Vypadek koordinatora v tomto kroku protokolu zpravy o rozhodnut X po x zopakovan takovych z adost krachuje X prpadne se mu ze dotazovat ostatnch participantu jak znelo rozhodnut X pokud ale tito budou rovnez ve stavu neurcitosti, nedozv se ale nic PA150 { Transakce a soube znost v distribuovanem prost red

Participant nedostal po ukoncen svych operac dotaz canCommit?

Koordinator nedostal do uplynut c asoveho limitu hlas od nektereho participanta X Rozhoduje abort transakce X Toto rozhodnut rozesle vsem participantum X pokud nektery opozdeny participant bude pote hlasovat commit,

X participant mus c ekat na obnovu koordinatora X po uplynut c asoveho limitu mu ze pozadat o zopakovan

|

53

X Nezbyv a nic jineho po uplynut c asoveho limitu nez jednostranne udelat abort

netus jak bude znt rozhodnut, nemu ze rozhodnout jednostranne X Nemu ze uvolnit objekty drzene pro aktualn e r esenou transakci pro pouzit jinymi soubez nymi transakcemi




X Participant je ve stavu neurcitosti (uncertain)

2

|

zustane ve stavu neurcitosti (resen viz vy se)

54


|


55

Zvlad an poruch v 2PCP detailne { vypadek uzlu kohorty

Zvlad an poruch v 2PCP detailne { vypadek uzlu kohorty

Uzel kohorty obnovil c innost po svem vypadku a rozhoduje podle sveho logu (denku) o osudu transakc, ktere byly pri vypadku rozpracovane

2 Log

X uzel kohorty vypadl drve nez si pripravil reakci na canCommit?(T) { X Ci mus T zrusit, abort T X uzel kohorty provede undo(T)

obsahuje zaznam { uzel provede redo(T) Log obsahuje zaznam { uzel provede undo(T) Log obsahuje pouze zaznam a ne zaznamy /, { dotazuje se Ci a dela

2 Log 2 2

neobsahuje z adn y zaznam (abort, commit, ready) o T {

X redo(T), kdyz se dozv, z e rozhodnut bylo X undo(T) kdyz se dozv, z e rozhodnut bylo . X Pokud Ci neodpovda (vypadl), uzel periodicky vysla

ostatnm uzlum v systemu zpravu query-status (T)dokud od nektereho z nich nedostane informaci podle jeho logu zda T byla dokoncena nebo zrusena a dela podle zjisten redo(T) nebo undo(T) X dotazuje se periodicky dokud nedostane zpravu, zdroje drzene v uzlu pro T jsou po tuto dobu blokovane Jan Staudek, FI MU Brno

|


56


Zvlad an poruch v 2PCP detailne { vypadek koordinatora

2 2

Pokud aktivn uzel s koordinatorem ve svem logu obsahuje , T se potvrzuje Pokud aktivn uzel s koordinatorem ve svem logu obsahuje , T se rus Pokud aktivn uzel ve svem logu neobsahuje ani , nemohl takovy uzel poslat Ci zpravu ready (T) a vypadly Ci tudz nemohl T potvrdit.

|


2

2

2

{ Nez c ekat na obnovu Ci, je lepsm r esenm T zrusit



57

Hodnocen 2PCP

Kdyz uzel s koordinatorem vypadne v rozpracovanem 2PCP o osudu T rozhoduj uzly kohorty. Pokud to nezvladaj , c eka se na obnovu uzlu s koordinatorem. 2

|

58

2PCP je blokujc protokol, { drz si zamcene zdroje behem c ekan na zpravu, neuvolnuje je, { ostatn procesy, ktere tyto zdroje pozaduj, c ekaj kdyz vypadne uzel s koordinatorem, kohorta sama transakci neukonc, zdroje drzene v uzlech kohorty budou drzene do doby dokud uzel s koordinatorem neobnov svoji c innost 2PCP je konzervativn, pri nejistote dav a prednost zrusen (abort) pred dokoncenm (commit)


|


59

zen soube R znosti, synchronizace procesu

2 2 2 2 2

Zamykac protokoly

Modi kace centralizovanych synchronizacnch uloh na r esen umoznuj c pouzit distribuovanosti transakc Beh transakc (resp. subtransakc), ktere zprstupnuj data v lokale, koordinuje transakˇcn´ı manaˇzer lokaln transakce (subtransakce) bez pouze v jedinem uzlu globaln transakce bez v nekolika uzlech Typove ulohy { bazov e nastroje

2

dvoufazov y zamykac protokol lze pouzt i v DS X puvodn nedistribuovany 2PL protokol: { proces nejprve pouze zamyka´ objekty, pot´e pouze uvolnuje objekty ˇ

{ zamykan r es na z adost procesu spolecny spravce zamykan X pro distribuovane prostred se implementace spravce zamykan mus

zmenit tak, aby respektovala distribuovanost prostred

2

X zamykan X c asove raztkovan

Prklady r esen spravy zamykan v distribuovanem prostred { viz dals prusvitky: X zamykac spravci uzlu, data nejsou replikovana X jeden centraln zamykac spravce X majoritn zamykac protokol (majority protocol) {

zamykac spravci uzlu + moznost pouzvan replikovanych dat X asymetricky zamykac protokol (biased protocol ) Jan Staudek, FI MU Brno

|


60

Zamykac spravci uzlu, data nejsou replikovana

2 2

2

2


2

2

2 2 2

|



61

Zamykac protokol s jednm centraln m zamykacm spravcem

neexistuj replikovana data ve vce uzlech kazdy uzel provozuje sveho spravce zamykan , ktery zpracovav a pozadavky lock a unlock na data uchovavan a v danem uzlu jednoducha implementace vyvolav a vydan 2 zpravy na zpracovan pozadavku lock (zadost, povolen) 1 zprava na zpracovan pozadavku unlock Zvladnut uvaznut je dky distribuovanosti prostred slozitejs


|

62

V celem systemu v jedinem urcenem uzlu pusob jediny spravce zamykan , vsechny pozadavky na zamykan a uvolnov an jsou smerovany na tohoto spravce jednoducha implementace vyvolav a vydan 2 zpravy na zpracovan pozadavku lock (zadost, povolen) a 1 zpravy na zpracovan pozadavku unlock Zvladnut uvaznut je dky centralizovanosti jednoduche uzel s koordinatorem a komunikacn cesty k tomuto uzlu mohou byt uzk ym pro lem zranitelnost { vypadek uzlu s koordinatorem zpusobuje nefunkcnost celeho systemu


|


63

Majoritn zamykac protokol

2 2 2 2 2

Majoritn zamykac protokol, 2

s nedostatky centraln Re ho r zen, pracuje s replikovanymi daty, decentralizovane Modi kace schematu s uzlovymi koordinatory V kazdem uzlu bez spravce zamykan uzlu Spravce zamykan uzlu zamyka a uvolnuje data nebo repliky dat uchovavan ych ve svem uzlu Transakce zamykajc replikovany zdroj dat mus

2

2

X T1 a T2 zamykaj data Q replikovana v uzlech S1..4. X T1 pozad a o zamcen u S1..3 X T2 pozad a o zamcen u S2..4 X T1 uspeje u S1 a S2 a T2 uspeje u S3 a S4. X Aplikace generujc transakce T1 a T2 uvazla.

{ poslat pozadavek na zamcen vce nez polovine uzlu, ktere uchovavaj replikaci zamykanych dat a { zskat od techto uzlu povolen zamknut { informovat stejnou mnozinu uzlu o odemknut Jan Staudek, FI MU Brno

|


64


Asymetricky zamykac protokol (biased) )

2 2

2 2 2 2

|


|


65

Serializace p r stupu casov ym raztkovan m

V principu majoritn zamykac protokol Pouzva sdlene zamykan pro c tec operace a exkluzivn zamykan pro zapisy pro sdlene zamcen je dostatecne povolen od jedineho (kterehokoliv) spravce pro exklusivn zamcen je nutne povolen od vsech spravc u men e ztrat pro c tec operace, slozitejs je zamykan pro zapis r esen uvaznut je slozite


Slozitejs je implementace 2((n/2)+1) zprav na zpracovan pozadavku lock (zadost, povolen) a (n/2)+1 zprav na zpracovan pozadavku unlock Algoritmus pro zvladnut uvaznut mus byt modi kovan, uvaznut mu ze zpusobit i zamykan pouze jedne jedine, ale replikovane polozky dat

2

66

Razen na bazi TS zname r esen z predna sky Transakce


|


67

P ripomenut: Zamykac protokol s casov ymi raztky

2 2 2 2

2 2

P ripomenut: Zamykac protokol s casov ymi raztky, 2

Centralizovany scen a r, nedistribuovane prostred Predem se de nuje porad transakc { podle c asovych raztek Casov e raztko T Si se transakci Ti prideluje pred jejm spustenm T Si se mu ze odvozovat

2

X ze systemov ych hodin X z logickeho c tace inkrementovaneho kazdym spustenm transakce

2

Transakce Ti s T Si predchaz transakci Tj s T Sj pokud T Si < T Sj Casov a raztka urcuj porad serializovatelnosti

2

Datove polozce Q se pridel dve c asova raztka X WQ { nejvets c asove raztko z transakc, ktere usp es ne provedly write(Q) X RQ { nejvets c asove raztko z transakc, ktere usp es ne provedly read(Q)

Tato c asova raztka se koriguj pri kazdem read(Q) nebo write(Q) Protokol zajist'uje, z e kon iktn operace read a write se provedou v porad danem c asovymi raztky transakc

X pokud T Si < T Sj , protokol mus zajistit realizaci planu, ktery je ekvivalentn seriov emu planu, ve kterem Ti predchaz Tj Jan Staudek, FI MU Brno

|


68


P ripomenut: Zamykac protokol s casov ymi raztky, 2

2

X Jestlize T Si < WQ, Ti potrebuje c st hodnotu Q, ktera uz byla prepsana, operace read(Q) se odmta a Ti se vrac (roll-back) X Jestlize T Si ≥ WQ, pak se read(Q) provede a RQ se nastav na max(RQ, T Si) 2 Necht' Ti provad write(Q): X Jestlize T Si < RQ, hodnota Q vytva rena v Ti byla potrebna uz drve a Ti predpoklad a, z e tato hodnota uz nema byt vytva rena, operace write se odmta a Ti se vrac (roll back) X Jestlize T Si < WQ, pak Ti predpoklad a, z e zapisuje starou hodnotu Q, operace write se odmta a Ti se vrac (roll back) X V ostatnch prpadech se write provede a oprav se WQ 2 Vracen e Ti se pridel nove c asove raztko a spust se znovu 2 Pouzity algoritmus zarucuje kon iktovou serializaci a

nezpusobuje uvaznut (zadn a transakce neceka) |



69

Serializace p r stupu casov ym raztkovan m

Necht' Ti provad read(Q):


|

70

2 2

Problem { generovan jedinecneho TS v distribuovanem prostred globaln jedinecne TS: X kazdy uzel generuje jedinecne lokaln TS X globaln jedinecne TS se zska r etezenm

{ jedinecneho lokaln ho TS { s jedinecnym identi katorem uzlu X pro spravedlive generovan TS se pouzij logicke hodiny udrzovane v kazdem uzlu 2

Pripomenut problemu r azen na bazi TS X pokud se c tou hodnoty dat drve nez jsou potvrzeny (commit), ex. hrozba c asteho kaskadn ho vracen (roll-back) Jan Staudek, FI MU Brno

|


71

Uvaznut

Uvaznut

Prklad uvaznut zpusoben e exkluzivnm zamykan m (write locks)

Uvaznut zpusoben e exkluzivnm zamykan m (write locks) v distribuovanem systemu, kde u cty A a B spravuj servery X a Y, u cty C a D server Z


|


72


|


73

Principy r esen uvaznut

Uvaznut

Wait-for-Graph uvaznut zpusoben eho exkluzivnm zamykan m v distribuovanem systemu, kde u cty A a B spravuj servery X a Y, u cty C a D server Z

2

Razen m pouzitelnosti zdroju { prevence uvaznut X de nuje se globaln usporad an vsech systemov ych zdroju X kazdy zdroj obdrz jedinecne poradove c slo X proces sm pozadovat zdroj s c slem i

pouze kdyz nevlastn zdroj s c slem vetsm nez i

X snadna implementovatelnost, mozna neefektivita pouzvan zdroju 2

Banke ruv algoritmus { obchazen uvaznut X jeden z procesu mus hrat roli banke re { spravce prostredku X v distribuovanem prostred nesnadno implementovatelny, vets rezie

2

Detekce uvaznut X zkouman stavu interakc mezi procesy a zdroji,

vyhledav an cyklickeho c ekan

X efektivn prstup ke zvlad an uvaznut v distribuovanem prostred Jan Staudek, FI MU Brno

|


74


|


75

Problemy detekce uvaznut

2

Detekce uvaznut , kriteria spravnosti detekcn ho algoritmu

Jak udrzovat WFG ?

2

X vsechna existujc uvaznut mus algoritmus detekovat v konecnem c ase X jakmile se uvaznut vyskytne, spusteny algoritmus

X 2

Z ivost, progress, nezustne z adn e nedetekovane uvaznut

Jak vyhledat ve WFG cyklus ?

nesm c ekat na z adnou dals udalost aby uvaznut detekoval

X

2

2

Bezpecnost, safety, nedetekuj se falesna uvaznut X algoritmus nesm oznamovat neexistujc, falesna uvaznut X tj. uvaznut detekovane na zaklad e konstrukce nekonzistentnho WFG

X

vytvoreneho dky asynchronn komunikaci a neexist. spolecne pameti

2

sen detekovaneho Re uvaznut X jeden nebo vce z uvazl ych procesu se zrus (vrat na pocatek) a jejich

zdroje se pridel blokovanym procesu, ktere pak mohou dale bez et


|


76

Detekce uvaznut pomoc ,,wait-for"grafu, WFG

2

2


|

Predpoklad a dusledek X kazdy alokovatelny zdroj ex. v jedinem exempla ri X cyklus ve ,,wait-for"grafu reprezentuje uvaznut

Lokaln wait-for grafy neobsahuj cyklus

Lokaln ,,wait-for"graf, platny pro odpovdajc uzel ste

Jestlize Pi bez c v S2 z ad a zdroj drzeny Pj bez cm v S1, posle Pi zpravu do S1 a v lok. grafu v S1 se zaps e hrana Pi→Pj

pokud tyto procesy drz nebo pozaduj zdroje lokaln v danem uzlu ste

Globaln ,,wait-for"graf, platny pro celou st' X sjednocen lokaln ch lokaln ch ,,wait-for"grafu

2 2

77


X uzly v lok. WFG odpovdaj jako lokaln m tak i nelokaln m procesum, 2


Cyklus v lokaln m ,,wait-for"grafu ⇒ existuje uvaznut Acyklicnost lokaln ho ,,wait-for"grafu jeste neznamena neexistenci uvaznut X existenci uvaznut indikuje az globaln ,,wait-for"graf Jan Staudek, FI MU Brno

|


78


|


79







|



80



|



81

Detekce uvaznut { Centralizovane r esen

2

Globaln wait-for graf obsahuje cyklus, system je v uvaznut : P2 c eka na P3, P3 c eka na P4, P4 c eka na P2


|

2 2

Kazdy uzel ste si udrzuje lokaln wait-for graf Globaln wait-for graf udrzuje jeden koordinujc proces, tento graf je sjednocenm vsech lokaln ch wait-for grafu Existuj 3 mozne okamziky kdy lze globaln WFG konstruovat:

1. Kdykoliv se vloz nova hrana nebo se odstran existujc hrana v lokaln m wait-for grafu 2. periodicky, kdyz se vyskytne jisty pocet zmen, ktere se maj promtnout ve wait-for grafu 3. kdykoliv koordinator potrebuje vyvolat algoritmus detekce cyklu v grafu (viz dals prusvitky) 2 Falesne cykly (v 1. a 2.) mohou vyvolat nepotrebne navraty

82


|


83

Falesn e cykly

Detekce uvaznut { Centralizovane r esen podle volby 3

2 2

2


|


84

falesne cykly vznikaj pri korekci globaln ho wait-for grafu bez prsneho dodrzovan c asove posloupnosti jeho uprav volba 3 { aby se falesne cykly nedetekovaly, pripojuj se k z adostem z ruzn ych uzlu ste jedinecne identi katory (TS) { kdyz proces Pi z uzlu ste A pozaduje prostredek drzeny procesem Pj bez cm v uzlu ste B, odesle uzlu ste B zpravu request s c asovym raztkem TS a hrana Pi → Pj s ohodnocenm TS se vloz do lokaln ho wait-for grafu uzlu A a uzlu B pouze tehdy, kdyz uzel B prijal zpravu request a nemu ze pozadovany prostredek uvolnit ihned. pozadavek Pi na Pj v jednom uzlu se zpracuje standardne, hrana Pi → Pj se neohodnocuje Jan Staudek, FI MU Brno

Detekce uvaznut { Centralizovane r esen podle volby 3

|


85

Detekce uvaznut { plne distribuovane r esen

Algoritmus:

2

1. vsechny uzly v systemu dostanou od koordinatora iniciacn zpravu 2. pri prjmu iniciacn zpravy uzel posle koordinatorovi svuj lokaln wait-for graf 3. kdyz koordinator dostane odpoved' od vsech uzlu, zkonstruuje globaln wait-for graf nasleduj cm zpusobem:

2 2

a. graf obsahuje uzel pro kazdy proces v systemu b. graf obsahuje hranu Pi → Pj tehdy a jen tehdy, jestlize

Za detekci uvaznut sdlej odpovednost vsichni koordinato ri. V kazdem uzlu ste se konstruuje lokaln wait-for graf, ktery reprezentuje c ast globaln ho wait-for grafu Do kazdeho lokaln ho wait-for grafu se pridav a dodatecny uzel Pex X Hrana Pi → Pex reprezentuje stav,

ve kterem Pi c eka na data drzena procesem ve kteremkoliv jinem uzlu ste X Hrana Pex → Pi reprezentuje stav, ve kterem proces ve kteremkoliv jinem uzlu ste c eka na data drzena procesem Pi v lokaln m uzlu

i. v jednom z wait-for grafu existuje hrana Pi → Pj nebo ii. ve vce nez jednom wait-for grafu se vyskytne hrana Pi → Pj s jistym ohodnocenm TS Jestlize zkonstruovany graf obsahuje cyklus, v systemu existuje uvaznut . Pokud ho neobsahuje, pak v okamziku zahajen testu uvaznut neexistovalo. Jan Staudek, FI MU Brno

|


86


|


87

Detekce uvaznut { doplnen e ,,wait-for"grafy o Pex

Detekce uvaznut { plne distribuovane r esen

2

Jestlize lokaln wait-for grafu obsahuje cyklus, ktery neobsahuje uzel Pex, pak system je ve stavu uvaznut

2

Cyklus obsahujc uzel Pex implikuje moznost uvaznut . Pro zjisten, zda system uvaznul c i ne, se mus spustit distribuovany algoritmus detekce uvaznut


|



88


2 2

|



89


2


|

90

Necht' S1 odhal cyklus P3-Pex-P2-P3 Protoze P3 z ad a zdroj z S2, posle S1 do S2 zpravu popisujc cyklus v S1 S2 koriguje svuj lokaln graf a odhal existenci uvaznut { cyklus, ktery neobsahuje Pex:


|


91

Transakce, soub eznost a uv aznut v distribuovan em prostred

Recommend Documents