Elosztott rendszerek NGM_IN005_1 Szoftver hibat!rés
Folyamat csoportok Folyamatok meghibásodása többszörözés -> folyamat csoportok Dinamikus folyamat csoportok transzparencia Egyszint! és hierarchikus csoportok
2
Hibaelfedés Passzív vagy aktív replikáció Többszörözés szintje k-hibat!rés leállás: k+1 bizánci hibák: 2k+1 3
Megegyezés Kommunikáció megbízhatatlansága két hadsereg probléma Hibázó folyamatok bizánci tábornokok problémája
4
Két hadsereg probléma
5
Bizánci tábornokok Tökéletes kommunikáció, de áruló tábornokok valótlan informácók közlése els" és másodkézb"l is Lamport megoldása
6
Bizánci tábornokok (folyt.) m meghibásodás 2m+1 helyes kimenet 3m+1 folyamat összesen
7
Megbízható kliens-szerver kommunikáció Pont-pont kommunikáció megbízható szállítási protokoll nyugták, timerek, ARQ összeköttetés megszünése problémás RPC rendszerek hibák kliens nem találja a szervert kliens üzenete elveszik szerver összeomlik a kérés megérkezte után szerver válasza elveszik kliens összeomlik a válasz megérkezte után 8
Nincs szerver Szerver üzemen kívül, vagy nem kompatibilis Kliens átlátszóság sérül kivétel (vagy signal) és kezelése
9
Elveszett kérések Nyugtázás + id"zít" Újraküldés Szerver nincs eset Szerver oldalon újraküldés esetleges detektálása
10
Szerver összeomlása Lehetséges forgatókönyvek
Kliens oldalon nem tudni melyik esettel állunk szemben pontosan egyszer legalább egyszer legfeljebb egyszer akárhányszor 11
Szerver összeomlása (pl.) Nyomtatás a távoli szerveren M: ack, P: nyomtatás, C: összeomlás Client
Server Strategy M -> P
Reissue strategy
Strategy P -> M
MPC
MC(P)
C(MP)
PMC
PC(M)
C(PM)
Always
DUP
OK
OK
DUP
DUP
OK
Never
OK
ZERO
ZERO
OK
OK
ZERO
DUP
OK
ZERO
DUP
OK
ZERO
OK
ZERO
OK
OK
DUP
OK
Only when ACKed Only when not ACKed
12
Elveszett válaszok Nem idempotens kérések kezelése kérések szekvencia számozása kliensek nyilvántartása újraküldés detektálása replay cache 13
Kliens összeomlása árva feladatok CPU pazarlás, er"források lekötése kezelés extermination - indítások logolása, árvák leölése reincarnation - újrainduláskor új korszak kezd"dik gentle reincarnation - ölés csak tulajdonos nélküli feladatokra expiration - id" korlát a feladatokra 14
Megbízható csoport kommunikáció Alacsony folyamatszám esetén megbízható pont-pont kommunikáció Hibás folyamatok jelenléte a csoportban helyesen m!köd" összes csomópontnak meg kell kapni egyetértés abban, kik m!ködnek helyesen Helyesen m!köd"nek feltételezett csoporttagok csoport minden tagjának meg kell kapni 15
Megbízható broadcast (pl.) Helyesen m!köd"nek feltételezett csoporttagok megbízhatatlan kommunikációs rendszer
16
Méretezhet"ség Sok nyugta kezelése Csak negatív nyugták meddig pufferelni? timeout? Nem hierarchikus visszajelzés vezérlés Hierarchikus visszajelzés vezérlés 17
Nem hierarchikus visszajelzés Visszajelzés elnyomás scalable reliable multicasting protocol nincs pozitív nyugta szervernek küldend" NACK késleltetése véletlen ideig NACK a csoport összes tagjának várakozás közben mástól érkezik NACK -> saját elfolytás
18
Hierarchikus visszajelzés Sok címzett - alcsoportok fa struktúra (létrehozása kihívás) helyi koordinátor továbbítás, újra küldési kérelmek kezelése
19
Atomi multicast Üzenet valamennyi csoporttaghoz vagy senkihez sem továbbítandó Mindenkihez ugyanabban a sorrendben teljesen rendezett látszólagos szinkronitás Alkalmazás pl. replika menedzserek csoportjában 20
Látszólagos szinkronitás Csoportkép (group view) view change üzenetek Ha az m üzenet küld"je összeomlik az átvitel közben, akkor az üzenetet vagy valamennyi megmaradt tagnak meg kell kapnia vagy mindnek figyelmen kívül kell hagynia
21
Üzenetek sorbarendezése Rendezetlen üzenetküldés FIFO rendezés
Process P1 sends m1
Process P2 receives m1
Process P3 receives m2
sends m2
receives m2
receives m1
Process P1
Process P2
Process P3
Process P4
sends m1
receives m1
receives m3
sends m3
sends m2
receives m3
receives m1
sends m4
receives m2
receives m2
receives m4
receives m4
Kauzálisan rendezett okok és következmények sorrendjének tartása Teljesen rendezett mindenkihez ugyan abban a sorrandben 22
Látszólagos szinkronitás implementálása Üzenet érkezése és kézbesítése
G csoport összes tagja tárolja az üzenetet, amíg mindenki meg nem kapja stabil üzenet ->kézbesíthet" view változás nem stabil üzenetek elküldése flush üzenet változás életbeléptetése Megbízható pont-pont kommunikáció 23
Látszólagos szinkronitás implementálása példa
24
Kétfázisú véglegesítés Koordinátor és résztvev"k
Blokkolt állapotok feloldása timerek, más résztvev"k állapotának megismerése 25
Kétfázisú véglegesítés - koordinátor actions by coordinator: while START _2PC to local log; multicast VOTE_REQUEST to all participants; while not all votes have been collected { wait for any incoming vote; if timeout { while GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; exit; } record vote; } if all participants sent VOTE_COMMIT and coordinator votes COMMIT{ write GLOBAL_COMMIT to local log; multicast GLOBAL_COMMIT to all participants; } else { write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; }
26
Kétfázisú véglegesítés - résztvev" actions by participant: write INIT to local log; wait for VOTE_REQUEST from coordinator; if timeout { write VOTE_ABORT to local log; exit; } if participant votes COMMIT { write VOTE_COMMIT to local log; send VOTE_COMMIT to coordinator; wait for DECISION from coordinator; if timeout { multicast DECISION_REQUEST to other participants; wait until DECISION is received; /* remain blocked */ write DECISION to local log; } if DECISION == GLOBAL_COMMIT write GLOBAL_COMMIT to local log; else if DECISION == GLOBAL_ABORT write GLOBAL_ABORT to local log; } else { write VOTE_ABORT to local log; send VOTE ABORT to coordinator; }
actions for handling decision requests: /* executed by separate thread */ while true { wait until any incoming DECISION_REQUEST is received; /* remain blocked */ read most recently recorded STATE from the local log; if STATE == GLOBAL_COMMIT send GLOBAL_COMMIT to requesting participant; else if STATE == INIT or STATE == GLOBAL_ABORT send GLOBAL_ABORT to requesting participant; else skip; /* participant remains blocked */
27
Háromfázisú véglegesítés Nem blokkoló véglegesítési protokoll koordinátor összeomlása
28
Felépülés Backward recovery korábbi helyes állapotba checkpointok pl. hibadetektáló kódolás + újraküldés Forward recovery új, m!köd" állapotba hibamodell pl. hibajavító kódolás 29
Felépülés (folyt.) Stabil tárolás felépülési információ túléli az összeomlást pl. lemez tükrözés
30
Felépülés (folyt.) Ellen"rz" pontok Felépülési vonal legutolsó konzisztens pillanat felvétel domino effektus
31
Megbízható pont-pont átvitel Hibakezelés FEC broadcast adattárolás rossz csatorna ARQ kisebb csatorna kapacitás nem kell konstans átviteli ráta Adatfolyam szabályozás ACK NACK time-out 32
Hibadetektáló kódolások redundáns információ inkonzisztencia detektálása az eredeti és a redundáns info között pl.: 32 bit extra info keretenként 1/232 részét nem detektálja a hibás kereteknek! Paritás bitek CRC 33
Hibadetektálás teljesítménye K=8, N=9 bin. kódolás (1 paritás bit),BER 1:104 8 bites hibás üzenet (paritás nélkül) valószín!sége 1-(1-10-4)8=0.000799 paritással nem detektált hibás üzenet valószín!sége detektálható 1 bites hibák (ez alsó becslés) 9*10-4(1-10-4)8 1-(1-10-4)9-9*10-4(1-10-4)8=0.000000359 34
Paritás bitek Paritás bitek q d ( c , v ) : = " # {c ! v } . Hamming távolság i =1 Érvényes kódszavak min. Hamming távolsága i
c3 001
u2 01
11
010
u1 00
10
011
111
c2
000
Két dimenziós paritás
c3
110
c1
111
c2
101
100
i
000
c1
Paritás bitek
Adatok
Paritás bájt
0101001
1
1101001
0
1011110
1
0001110
1
0110100
1
1011111
0
1111011
0
35
CRC üzenet polinom (M) és generátor polinom (G) osztásakor keletkez" maradék (R) mint redundancia => C=M+R maradék nélkül osztható G-vel vett üzenet (V), hiba (E) V=C+E válasszunk olyan G-t, hogy E-val ne 0 maradékot adjon Szoftver implementáció végrehajtása processzor intenzív 36
Internet checksum u_short cksum(u_short *buf, int count) { register u_long sum = 0; while (count--) { sum += *buf++; if (sum & 0xFFFF0000) { /* carry occurred, so wrap around */ sum &= 0xFFFF; sum++; } } return ~(sum & 0xFFFF); }
37
Hibajavító kódolások Hamming távolság
dmin > 2t # d "1& t corr = int% min ( $ 2 '
Lineáris szisztematikus kódolási sémák c = u ! G.
!
G ! H T = 0.
sT = H ! v T
c ! HT = 0
# 0 =$ T %H " e
e := v ! c !
38
Hamming kódolás (pl.) (7,4) Hamming kód –DDDPDPP "1 $ 0 G =$ $0 $ #0
k=bG
0 1 0 0
0 0 1 0
0 0 0 1
0 1 1 1
1 0 1 1
1% ' 1' 0' ' 1&
b = [b0 b1 b2 b3 ] "0 $ $0 $0 $ H T = $1 $1 $ $1 $#1
!
!
0 1 1 0 0 1 1
1% ' 0' 1' ' 0' 1' ' 0' 1'& 39
!
Adatfolyam szabályozás Stratégiák Stop + Wait Go-Back-n Szelektív újraküldés Csúszó ablak 40
Stop+wait közegkihasználása Tf keret átviteli id"
Tf 2 Tp
Tp késleltetési id" U=Tf/(Tf+2Tp) a=Tp/Tf
U
U=1/(1+2a) Tf
Tp
41
Csúszó ablak közegkihasználása
•
egy ciklusra: U=N.Tf/(Tf+2Tp)
• a=Tp/Tf • U=N/(1+2a), ha N<1+2a
N*Tf Tf +2*Tp
N
U
• 1,
ha N>=1+2a a 42
