Elosztott rendszerek NGM_IN005_1 Szinkronizáció
Magas szint! szinkronizáció
Órák szinkronizálása (állapot szinkronizáció) Koordinátor választás Elosztott tranzakció kezelés
2
Óraszinkronizálás Time stampekre épül" rendszerek tranzakciós rendszerek (helyfoglalás, bank, t"zsde) make adat tükröz" megoldások offline komponensek ind"nkénti szinkronizálása Óra szolgáltatások 3
Make példa
4
Fizikai órák Id"zít" áramkörök (timer) számláló (counter) tároló (hold register) clock tick (megszakítás) CMOS órák Órák jellemz"i offset drift (skew) 5
Események rendezettsége Processzen belüli események szekvenciálisak A kommunikáció részleges rendezést ad A helyi id"k nem biztosítják a teljes globális rendezést Logikai órák Node R Proc X
Node S Proc Y
Node T Proc Z
Proc X
Proc Y
X1 X2
Y1
send(m,tx)
Y2
receive(m,tx) at tY tx < tY tx ! tY Z1 Z2
6
UTC Universial Coordinated Time Bureau International de l’ Heure TAI (cézium-133) szök" másodperc rádió adók, GPS
7
Óraszinkronizáló algoritmusok Id"zít" áramkörök pontossága (relatív hiba) kb. ±10-5 dC 1" # $ $ 1+ # max. drift rate ! dt Max. megengedett eltérés " Újraszinkronizálás id"szerverekkel "/2! id"közönként !
8
Cristian algoritmusa Pontos id"t tartalmazó üzenet Óra beállítás fokozatosan (rendezés megtartása) hálózati késleltetés üzenet váltás idejének mérése helyi órával szerver válasz-generálási idejének ismerete több mérés
9
Berkeley algoritmus Id"démon (koordinátor) aktív lekérdezés átlagid" meghatározása óra állítási utasítás
10
NTP protokoll Network Time Protocol (1985) Óraszinkronizálás csomagkapcsolt, változó késleltetés! hálózati környezetben (Internet) Marzullo algoritmus Több szerver-réteg 64 bites time stampek 11
Marzullo algoritmus Optimális érték el"állítása konfidencia intervallummal adott becslésekb"l a legrövidebb, legtöbb forrással konzisztens intervallum
12
Lamport id"bélyegek Logikai órák szinkronizálása a#b (a happens before b) egy folyamaton belüli a,b a,b azonos üzenet küldése és fogadása különböz" folyamatokban C(a)
Alkalmazás példa Replikált adatbázison végzett m!veletek m!veletek azonos sorrendben totally ordered multicast
14
Id"bélyeg vektor Oksági viszonyok (kauzalitás) meg"rzése Vi[j]=k Pi folyamat számára ismert, hogy Pj-ben k esemény történt vt saját vektor csatolása az üzenetekhez Pj fogadó Vj[l]-t max{Vj[l],vt[l]}-ra állítja 15
Alkalmazás példa message thread elosztott üzen" rendszerben Pi “a” üzenetet küld: vt(a) Vi Pj válasza “r”: vt(r) Vj (vt(r)[j]>vt(a)[j]) Pk-hoz teszt. sorrendben megérkezek r megjelenítése vt(r)[j]=Vk[j]+1 és vt(r)[i]$Vk[i]
i#j 16
Elosztott r. globális állapota helyi állapotok + útonlév" üzenetek konzisztens állapot distributed snapshot
17
Snapshot készítése
18
Szavazó algoritmusok Kitüntetett, koordinátor folyamat választása legnagyobb, legkisebb azonosítójú folyamat megtalálása egyetértés biztosítása
19
Zsarnok algoritmus
20
Gy!r! algoritmus
21
Kölcsönös kizárás biztosítása Valamilyen er"forrás megszerzése kizárólagos használatra Megoldások centralizált koordinátor (master-slave) elosztott versenyhelyzet feloldás token továbbításos
22
Elosztott tranzakciók Védelem konkurrens hozzáférés esetén izoláció, szerializálás M!veletek oszthatatlan egységként konzisztencia biztosítása commit/rollback
23
Tranzakciók implementálása Saját munkaterület adatok másolata (shadow) copy on write Writeahead log naplózás régi és új értékekkel rollback 24
Konkurencia kezelés Rétegszerkezet használata ütemez" szerializálás olvasási és írási m!veletek conflicting operation pesszimista és optimista megközelítés 25
Kétfázisú lockolás Zárolások a növekedési fázisban ütközés esetén m!velet késleltetése, tranzakció felfüggesztése Feloldás a zsugorodási fázisban m!velet elvégzése után zárolás feloldás után a tranzakció nem zárolhat Két fázisú zárolással az ütemtervek szerializálhatók Holtpont kialakulhat azonos sorrendben lockolás 26
Kétfázisú lockolás (folyt.)
Szigorú kétfázisú lockolás 27
Pesszimista id"bélyeg rendezés
Írás
Olvasás 28
