Elosztott rendszerek NGM_IN005_1 Bevezetés
A tárgy célja Az elosztott számítógép-rendszerek általános elméleti hátterének ismertetése algoritmusok implementációs megoldások, technikák tervezési elvek mérési kérdések 2
Tematika Bevezetés: Számítógép-hálózatok, elosztott rendszerek Átlátszóság, nyíltság, méretezhet"ség. Elosztott hardverrendszerek. Elosztott szoftverkoncepciók, architektúrák. A kliens-szerver modell: Az alap kliens-szerver modell. Több réteg! kliens-szerver architektúra. Szolgáltatás-felderítés. Kommunikációs paradigmák: Rétegzett protokollok. Távoli eljáráshívás. Távoli metódushívás. Üzenettovábbítás, socket absztrakció. Csoportkommunikáció, multicast. 3
Tematika (folyt.) Névterek: Egyedi nevek. A DNS rendszer. Mobil objektumok. Konkurrens folyamatok: Konkurrencia. Szinkronizálás. Alacsony szint! szinkronizáló algoritmusok. Szemaforok, számlálók, órák. Megbízhatóság és replikációs technikák: Redundancia. Konzisztencia modellek. Szétterítési protokollok. Replikációs sémák. Hibat!rés: Szoftver hibat!rés. Megbízhatósági modellek. Összeomlás-állóság. 4
Tematika (folyt.) Biztonság: Fenyegetettség, támadások. Titkosítási eljárások. Biztonsági mechanizmusok. Biztonsági protokollok. Middleware megoldások: A middleware paradigma. Java middleware. CORBA. COM, DCOM, .NET, IBM MQSeries. A World Wide Web: A HTTP protokoll. Dokumentum reprezentáció. Kliens és szerver oldali programok. Konkurrencia-kezelés. Méretezhet"ségi kérdések. Web middleware, SOAP. Aktuális fejlesztési kérdések: Grid rendszerek. Peer-to-peer rendszerek. Szoftver ágensek (ügynökök). 5
Ajánlott irodalom A. S. Tanenbaum, M. v. Steen: Elosztott rendszerek - Alapelvek és paradigmák, Panem 2004 J. M. Crichlow: Elosztott rendszerek, Kiskapu 2003 W. Jia, W. Zhou: Distributed Network Systems - From concepts to Implementations, Springer 2005 G. Coulouris, J. Dollimore, T. Kindberg: Distributed Systems - Concepts and design, Addison Wesley 2005 J. Bacon, T. Harris: Operating Systems - Concurrent and distributed software design, Addison Wesley 2003 M. Crovella, B. Krishnamurthy: Internet measurement - Infrastructure, traffic, and applications, John Whiley & Sons 2006 6
Oktatási anyagok
El"adás vázlatok: http://www.sze.hu/~heckenas/okt/
7
Követelmények El"tanulmányok Formálisan Webfejlesztés, Adatelemzés Ajánlatos emlékezni Operációsrendszerek, Hálózatok, Párhuzamos prog. El"adások heti 4 Számonkérés Írásbeli vizsga (90’, kb. 10 feladat) 8
Elosztott rendszerek Autonom feldolgozó egységek kommunikációs hálózattal összekötve egy integrált, konzisztens számítási környezet kialakítására er"forrás megosztás nyíltság konkurrens m!ködés méretezhet"ség hibat!rés 9
Network science Hálózatokkal (összekötött rendszerek) kapcsolatos jelenségek multi-diszciplináris tudományos vizsgálata szociológia biológia kommunikációs hálózatok Hálózatok szerkezete, dinamikai jelenségek speciális, kibontakozó tulajdonságok 10
Network science (folyt.) Gráf elmélet random gráfok (Erd"s, Rényi) Network-centric operations (katonai doktrina) földrajzilag szétszórt egységek, információs el"ny Dynamic Network Analysis multi-ágens hálózatok kapcsolat változásainak statisztikai elemzése Hálózati topológiák elemzése kis világok, skála független hálózatok (Barabási A. László)
11
Network science (folyt.) Hálózatok értéke Reed’s law szociális hálózatok értéke a csomópontok számától exponenciálisan függ “hatványhalmaz” Metcalfe’s law telekom hálózat értéke arányos a csomópontok számának négyzetével Odlyzko: n*log(n) -es arány 12
Skálafüggetlen hálózatok Hatvány függvény linkszám eloszlás P ( k ) ~ k "# Dinamikus növekedés “Népszer!ségi” kapcsolódás ! (web linkek) Beágyazódás rejtett metrikus terekbe (BGP hálózat) “Kis világok”, clusterek Valós, komplex hálózatoknál önhasonlóság 13
Skálafüggetlen hálózatok (folyt.) Skála független hálózatok jellemz"i robuszusság “rövid” utak
1
2
véletlen hálózat
3
4
1
2
3
4
5
6
7
skálafüggetlen hálózat 14
Alkalmazások Térben elosztott üzleti logika ERP rendszerek (elosztott, sok felhasználós) Kommunikációs infrastuktúra Internet (routing, services) Szuperszámítógépek Cluster computing, GRID (számítási kapacitás) 15
Alkalmazások (folyt.) Hagyományos elosztott rendszerek elosztott fájlrendszerek elosztott adatbázis rendszerek elosztott valós-idej! rendszerek elosztott multi-média rendszerek hálózati operációs rendszerek 16
Modellek - HW koncepciók Sok processzoros rendszerek A legegyszer!bb elosztott rendszerek Több folyamatból álló rendszer Nagy real-time rendszerek jellemz"je Processzorok és folyamatok összerendelése el"re vagy diszpécser által meghatározott 17
Multiprocesszor rendszerek Osztott memória M
M
M
Privát memória M
M
M Busz alapú
P
P
P
P
P
P
M
M
M
M
M
M
P
P
P
P
P
Kapcsoló alapú
P
18
Modellek - SW koncepciók Elosztott operációs rendszer szorosan csatolt multiprocesszoros rendszerek Hálózati operációs rendszer lazán csatolt többgépes (heterogén) hálózat Middleware hálózati oprendszer feletti átlátszóságot biztosító réteg 19
Modellek - SW koncepciók(folyt.) Mikrokernel OR Alkalmazás
Szolgáltatás modul 1
Szolgáltatás modul 2
Mikrokernel Hardver
20
Modellek - SW koncepciók(folyt.) Réteg-szerkezet! rendszerek platform (HW, OS), middleware, szolgáltatás réteg "A" gép
"B" gép
"C" gép
Elosztott alkalmazás
Middleware
Helyi op.r.
Helyi op.r.
Helyi op.r.
Hálózat 21
Modellek - SW koncepciók(folyt.) Kliens-szerver hálózatok
Client
invocation result
Client
invocation
Server
result
Server
Key: Process:
Computer:
22
Modellek - SW koncepciók(folyt.) Szolgáltatások
Service
Server Client
Server
Client Server 23
Modellek - SW koncepciók(folyt.) Peer-to-peer rendszerek Peer 2 Peer 1
Application
Application Peer 3
Sharable objects
Application
Peer 4 Application Peers 5 .... N
24
Modellek - SW koncepciók(folyt.) Kommunikáló folyamatok process p
process q
send m
receive
Communication channel Outgoing message buffer
Incoming message buffer
25
Elosztott rendszerek felj"dése Terminálok, processzor pool, egyéb szerverek (70-es évek) Diszk nélküli munkaállamások, szerverek Munkaállomások, szerverek (80-as, 90-es évek) Számítási gridek (e-science)
26
Elosztott rendszerek tervezési kérdései Modell épít"elemek, együttm!ködésük, viselkedésük leírása Architektúra komponensek azonosítása, elhelyezkedésük, rendszerszolgáltatások Technológia átlátszóság a felhasználók felé, API-k, nem funkcionális követelmények kielégítése 27
Elosztott rendszerek speciális jellemz"i Konkurrencia egyidej! m!ködés Független meghibásodás feldolgozó egységek és hálózati elemek hibái Nincs globális id" szinkronizálatlan helyi órák Kommunikációs késleltetés hatások terjedési ideje Inkonzisztens állapot nincs az egész rendszerre kiterjed" konzisztens állapot 28
Biztonsági kérdések Kölcsönös autentikáció Hozzáférés szabályozás Biztonságos kommunikáció Integritás biztosítás Letagadhatatlanság biztosítása Visszajátszás megakadályozása Szolgáltatás megbénítás megakadályozása 29
Biztonsági kérdések (folyt.) Támadások, fenyegetettség hamis megszemélyesítés lehallgatás átvitt adatok megváltoztatása visszajátszás jogosulatlan hozzáférés tárolt adatok megváltoztatása szolgáltatás megbénítás letagadás 30
Elemzési háttér Interakció modellezés kommunikációs teljesítmény késleltetés, sávszélesség, jitter szinkron vagy aszinkron m!ködés események sorrendisége Hiba modellezés Biztonsági (security) elemzés “ellenség” 31
Elemzési háttér (folyt.) Épít" elemek programok folyamatok (processzusok) üzenetek csomagok protokollok hálózati infrastruktúra komponensek 32
Elemzési háttér (folyt.) Hibakezelés HW és SW hibák Heisenbug “megfigyelési hatás” Bohrbug meghatározott körülmények között manifesztálódik Hiba típusok leállás leállás értesítéssel elhagyás hálózati hiba id"zítési hiba egyéb hibák
33
Elemzési háttér (folyt.) Leírás, jellemz"k Valószín!ségi leírás valószín!ségi változók eloszlás és valószín!ségi s!r!ség fv. várható érték, momentumok együttes valószín!ség kovariancia feltételes valószín!ség 34
Elemzési háttér (folyt.) Fontos eloszlások p(x) = "e# "x , x > 0 exponenciális kiszolgálási id"k 1 % x$ µ ( $ ' * 1 p(x) = e 2 & " ) ,$+ < x < + normális " 2# ! aggregált forgalom p(x) = "k x , x > k Pareto ! és “kis” méret! egységek “nagy” #x& Weibull bx b"1 "%$ a (' ! p(x) = b e ,x > 0 a megbízhatóság 2
"
#" #1
b
35
!
Elemzési háttér (folyt.) Sztohasztikus folyamatok val. változók indexelt halmaza
{ X t ,t " 0}
Xi -k közötti függések (kovariancia) stacionárius folyamat (id" ! eltolásra invariáns) kérések érkezése (intervallumok), 36
Elemzési háttér (folyt.) Rövid- és hosszú farok farok: nagy értékek valószín!sége 1" F(x) = P [ X > x ] 1" F(x) ~ e" #x
(1" F(x))e #x $ %, x $ %, # > 0
! !
!
37
Elemzési háttér (folyt.) Gráf elmélet irányítottság, súlyozott gráf, er"s csatolás csomópontok fokszáma átmér" karakterisztikus úthossz
d(i) =
cluster együttható
C(i) = !
!
#
v "V \{i}
d(i,v)
V $1
{e jk } k i (k i "1) /2 38
Elemzési háttér (folyt.) Gráf-modellek random gráfok (hosszú farok fokszám eloszláshoz) generalizált random gráf skála-független gráf (“kis világ”) hatvány fv. fokszám eloszlás 39
Elemzési háttér (folyt.) Metrikák mérési módszertan közvetlen mérés, konstrukció, becslés hibák mintavételezés reprezentativitás, torzítás random additive sampling 40
Tervezési elvek A leggyakoribb hibás feltételezések A hálózat megbízható (reliable) A késleltetés zéró A sávszélesség végtelen A hálózat biztonságos (secure) A topológia nem változik Egy adminisztrátor van Az átviteli költség zéró A hálózat homogén 41
Tervezési elvek (folyt.) Tetsz"leges számú komponens meghibásodhat Készítsünk hiba-scenáriókat Kliens és szerver oldalon is készüljünk fel a hibákra Minimalizáljuk a hálózati forgalmat Az adatok megváltozhatnak a hálózaton Kompromisszumos megoldások szükségesek késleltetés vs. kérések száma állapot mentesség vs. kommunikáció Az újraküldés költséges 42