Elosztott rendszerek: Alapelvek és paradigmák Distributed Systems: Principles and Paradigms. 1. rész: Bevezetés

Elosztott rendszerek: Alapelvek és paradigmák Distributed Systems: Principles and Paradigms Maarten van Steen1 1 VU

Kitlei Róbert 2

Amsterdam, Dept. Computer Science 2 ELTE Informatikai Kar

1. rész: Bevezetés 2015. május 24.

Tartalomjegyzék Fejezet 01: Bevezetés 02: Architektúrák 03: Folyamatok 04: Kommunikáció 05: Elnevezési rendszerek 06: Szinkronizáció 07: Konzisztencia & replikáció 08: Hibaturés ˝ 10: Objektumalapú elosztott rendszerek 11: Elosztott fájlrendszerek 12: Elosztott webalapú rendszerek

Maarten van Steen, Kitlei Róbert

Elosztott rendszerek

2 / 31

1.1 Definíció

1.2 Célok

1.3 Elosztott rendszerek fajtái

Definíció: Elosztott rendszer Az elosztott rendszer önálló számítógépek olyan összessége, amely ˝ számára egyetlen koherens rendszernek tunik. kezeloi ˝ Két szempont: (1) független számítógépek és (2) egyetlen rendszer ⇒ köztesréteg (middleware). Computer 1 Appl. A

Computer 2

Computer 3

Application B

Computer 4 Appl. C

Distributed system layer (middleware) Local OS 1

Local OS 2

Local OS 3

Local OS 4

Network



3 / 31

1.1 Definíció

1.2 Célok


Az elosztott rendszer céljai

˝ ˝ tétele Távoli eroforrások elérhetové Átlátszóság (distribution transparency) Nyitottság (openness) Skálázhatóság (scalability)



4 / 31

1.1 Definíció

1.2 Célok


Átlátszóság Fajta

Angolul

˝ Mit rejt el az eroforrással kapcsolatban?

Hozzáférési/elérési

Access

Adatábrázolás; elérés technikai részletei

Elhelyezési

Location

Fizikai elhelyezkedés

Áthelyezési

Migration

Elhelyezési + a hely meg is változhat

Mozgatási

Relocation

Többszörözési

Replication

Áthelyezési + használat közben is történhet az áthelyezés ˝ Az eroforrásnak több másolata is lehet a rendszerben

Egyidejuségi ˝

Concurrency

Több versenyhelyzetu˝ felhasználó is elérheti egyszerre

Meghibásodási

Failure

Meghibásodhat és újra üzembe állhat

Megjegyzés A fentiek lehetséges követelmények, amelyeket a rendszerrel kapcsolatban támaszthatunk. A félév során megvizsgáljuk, hogy melyik mennyire érheto˝ el. Maarten van Steen, Kitlei Róbert


5 / 31

1.1 Definíció

1.2 Célok


Az átlátszóság mértéke Mekkora átlátszóságot várhatunk el? ˝ A teljes átlátszóságra törekvés általában túl eros: A felhasználók különbözo˝ kontinenseken tartózkodhatnak A hálózatok és az egyes gépek meghibásodásának teljes elfedése elméletileg és gyakorlatilag is lehetetlen Nem lehet eldönteni, hogy a szerver csak lassan válaszol vagy meghibásodott Távolról nem megállapítható, hogy a szerver feldolgozta-e a ˝ összeomlott kérésünket, mielott A nagymértéku˝ átlátszóság a hatékonyság rovására megy, de a késleltetést is el szeretnénk rejteni Ilyen feladat lehet a webes gyorsítótárak (cache-ek) tökéletesen frissen tartása Másik példa: minden változás azonnal lemezre írása nagymértéku˝ hibaturéshez ˝ Maarten van Steen, Kitlei Róbert


6 / 31

1.1 Definíció

1.2 Célok


Elosztott rendszerek nyitottsága Nyitott elosztott rendszer A rendszer képes más nyitott rendszerek számára szolgáltatásokat nyújtani, és azok szolgáltatásait igénybe venni: A rendszerek jól definiált interfészekkel rendelkeznek Az alkalmazások hordozhatóságát (portability) minél inkább támogatják Könnyen elérheto˝ a rendszerek együttmuködése ˝ (interoperability) A nyitottság elérése A nyitott elosztott rendszer legyen könnyen alkalmazható heterogén környezetben, azaz különbözo˝ hardvereken, platformokon, programozási nyelveken. Maarten van Steen, Kitlei Róbert


7 / 31

1.1 Definíció

1.2 Célok


Nyitottság: követelményrendszerek, mechanizmusok

A nyitottság implementálása ˝ álljon Fontos, hogy a rendszer könnyen cserélheto˝ részekbol Belso˝ interfészek használata, nem egyetlen monolitikus rendszer ˝ A rendszernek minél jobban paraméterezhetonek kell lennie ˝ Egyetlen komponens megváltoztatása/cseréje lehetoleg minél kevésbé hasson a rendszer más részeire



8 / 31

1.1 Definíció

1.2 Célok


Nyitottság: követelményrendszerek, mechanizmusok Példák ˝ amelyekhez jó, ha A nyitott rendszer követelményeket (policy) ír elo, minél több megvalósító megvalósítás (mechanism) érheto˝ el a rendszerben. Néhány szóbajöheto˝ példa: ˝ konzisztenciát követeljünk meg a kliensoldalon Mennyire eros cache-elt adatokra? Legyen dinamikusan beállítható, hogyan ˝ döntse el a rendszer az adatról, milyen erosen legyen konzisztens. A letöltött kód milyen muveleteket ˝ hajthasson végre? A mobil kódhoz rendeljünk különbözo˝ megbízhatósági szinteket. Milyen QoS követelményeket támasszunk változó sávszéleségu˝ rendszerben? Minden folyamra külön lehessen QoS követelményeket beállítani. Milyen mértékben titkosítsuk a kommunikációs csatornánkat? A rendszer kínáljon többfajta titkosítási mechanizmust, amelyek közül választani lehet. Maarten van Steen, Kitlei Róbert


9 / 31

1.1 Definíció

1.2 Célok


˝ Átméretezhetoség (scalability) ˝ Átméretezhetoség ˝ az sokfajta kihívást jelenthet. Több különbözo˝ Ha egy „kis” rendszer megno, ˝ jellege is megnohet a rendszernek: ˝ méret szerinti átméretezhetoség: több felhasználó és/vagy folyamat van a rendszerben ˝ ˝ veszik földrajzi átméretezhetoség: a rendszert nagyobb területrol igénybe, pl. egyetemen belüli felhasználás→világméretu˝ felhasználóbázis ˝ adminisztrációs átméretezhetoség: biztonsági, karbantartási, együttmuködési ˝ kérdések merülnek fel, ha új adminisztrációs tartományok kerülnek a rendszerbe Megjegyzés ˝ A legtöbb rendszer a méret szerinti átméretezhetoséget kezeli. ˝ (Nem mindig) megoldás: erosebb szerverek használata. ˝ A másik két jellegu˝ átméretezhetoséget nagyobb kihívás kezelni. Maarten van Steen, Kitlei Róbert


10 / 31

1.1 Definíció

1.2 Célok


˝ Technikák az átméretezhetoség megvalósítására

A kommunikációs késleltetés elfedése A válaszra várás közben más tevékenység végzése: Aszinkron kommunikáció használata A beérkezo˝ választ külön kezelo˝ dolgozza fel Probléma: nem minden alkalmazás ültetheto˝ át ilyen megközelítésre



11 / 31

1.1 Definíció

1.2 Célok



Elosztás Az adatokat és a számításokat több számítógép tárolja/végzi: A számítások egy részét a kliensoldal végzi (Java appletek) Decentralizált elnevezési rendszerek (DNS) Decentralizált információs rendszerek (WWW)



12 / 31

1.1 Definíció

1.2 Célok



Replikáció/cache-elés Több számítógép tárolja egy adat másolatait: Replikált fájlszerverek és adatbázisok Tükrözött weboldalak ˝ Weboldalak cache-elése (böngészokben, proxy szervereken) Fájlok cache-elése (a szerver- és kliensoldalon)



13 / 31

1.1 Definíció

1.2 Célok


˝ Átméretezhetoség – a probléma Megjegyzés ˝ ˝ de ára van: Az átméretezhetoség könnyen elérheto, Több másolat fenntartása (cache vagy replika) inkonzisztenciához ˝ vezet: ha módosítunk egy másolatot, az eltér a többitol. A másolatok konzisztensen tartásához globális szinkronizációra van szükség minden egyes változtatás után. A globális szinkronizáció viszont rosszul skálázható nagy rendszerekre. Következmény Ha feladjuk a globális szinkronizációt, akkor kénytelenek vagyunk bizonyos fokú inkonzisztenciát elviselni a rendszerünkben. ˝ Az, hogy ez milyen mértékben elfogadható, rendszerfüggo. Maarten van Steen, Kitlei Róbert


14 / 31

1.1 Definíció

1.2 Célok


˝ Elosztott rendszerek fejlesztése: hibalehetoségek Megjegyzés ˝ kényelmes lehet feltételezni, hogy Az elosztott rendszer környezetérol megbízható. Ha ez tévesnek bizonyul, az a rendszer újratervezéséhez vezethet. Néhány ilyen feltételezés: a hálózat hibamentes a hálózat biztonságos a hálózat homogén a hálózati topológia nem változik ˝ a kommunikációnak nincsen idoigénye a sávszélesség korlátlan a kommunikációnak nincsen költsége csak egy adminisztrátor van



15 / 31

1.1 Definíció

1.2 Célok


Elosztott rendszerek fajtái

Elosztott számítási rendszerek grid cloud információs rendszerek

Elosztott információs rendszerek Elosztott átható (pervasive, ubiquitous) rendszerek



16 / 31

1.1 Definíció

1.2 Célok


Elosztott számítási rendszerek

Számítási rendszer Sok elosztott rendszer célja számítások végzése nagy teljesítménnyel. Cluster (fürt) Lokális hálózatra kapcsolt számítógépek összessége. Homogén: ugyanaz az operációs rendszer, hardveresen nem vagy csak alig térnek el A vezérlés központosítva van, általában egyetlen gépre



17 / 31

1.1 Definíció

1.2 Célok



Master node

Compute node

Compute node

Compute node

Management application Parallel libs

Component of parallel application



Local OS

Local OS

Local OS

Local OS

Remote access network

Standard network High-speed network



18 / 31

1.1 Definíció

1.2 Célok



Grid (rács) Több gép, kevésbé egységesek: Heterogén architektúra Átívelhet több szervezeti egységen Nagyméretu˝ hálózatokra terjedhet ki Megjegyzés Az együttmuködést ˝ sokszor virtuális szervezetek kialakításával segítik. Ez a felhasználókat csoportosítja, akiknek így egységesen lehet ˝ eroforrásokat kiutalni.



19 / 31

1.1 Definíció

1.2 Célok


Elosztott számítási rendszerek Felho˝ (cloud)

Infrastructure aa Svc

Platform aa Svc

Software aa Svc

Többrétegu˝ architektúra.


Web services, multimedia, business apps

Google Apps YouTube Flickr

Application Software framework (Java/Python/.Net) Storage (DB, File)

MS Azure Amazon S3

Platforms Computation (VM), storage (block)

Amazon EC2

Infrastructure CPU, memory, disk, bandwidth

Datacenters

Hardware


20 / 31

1.1 Definíció

1.2 Célok


Elosztott számítási rendszerek Felho˝ Négy különbözo˝ réteg: Hardver: Processzorok, útválasztók (routerek), áramforrások, ˝ hut ˝ oberendezések. A felhasználók közvetlenül nem látják. ˝ Infrastruktúra: Virtuális hardvert tesz elérhetové: szerver, adattároló, hálózati kapcsolat, számítási kapacitás lefoglalása és kezelése. Platform: Magasabb szintu˝ absztrakciókat biztosít. Pl. az Amazon S3 társzolgáltatás különbözo˝ fájlmuveleteket ˝ biztosít; a felhasználónak vödrei (bucket) vannak, ebbe feltölthet, letölthet stb. fájlokat egy API segítségével . ˝ Alkalmazás: A végfelhasználónak szánt, jellemzoen grafikus felületu˝ alkalmazások.



21 / 31

1.1 Definíció

1.2 Célok


Elosztott információs rendszerek

Elosztott információs rendszerek ˝ Sok elosztott rendszer elsodleges célja adatok kezelése, illetve meglevo˝ ilyen rendszerek elérése. Példa: tranzakciókezelo˝ rendszerek. BEGIN_TRANSACTION(server, transaction) READ(transaction, file-1, data) WRITE(transaction, file-2, data) newData := MODIFIED(data) IF WRONG(newData) THEN ABORT_TRANSACTION(transaction) ELSE WRITE(transaction, file-2, newData) END_TRANSACTION(transaction) END IF



22 / 31

1.1 Definíció

1.2 Célok


Elosztott információs rendszerek: tranzakciók Modell A tranzakció adatok összességén (adatbázis, objektumok vagy más adattár) végzett muvelet ˝ (lehetnek részmuveletei), ˝ melynek az alábbi tulajdonságai ˝ ˝ ACID-nek szokás nevezni a vannak. A kezdobet uk ˝ rövidítésébol követelményrendszert. Oszthatatlan, elemi (atomicity): Vagy a teljes tranzakció végbemegy minden részmuveletével, ˝ vagy pedig az adattár egyáltalán nem változik meg. Konzisztens (consistency): Az adattárra akkor mondjuk, hogy érvényes, ha ˝ feltételek teljesülnek rá. A tranzakció konzisztens, (az adattárra jellemzo) ˝ Ez a követelmény csak a tranzakció ha érvényes állapotot állít elo. ˝ végére vonatkozik: menet közben eloállhat érvénytelen állapot. ˝ sorosítható (isolation): Egyszerre zajló tranzakciók "nem Elkülönülo, zavarják" egymást: olyan eredményt adnak, mintha egymás után sorban futottak volna le. Tartósság (durability): Végrehajtás után az eredményt tartós adattárolóra mentjük, így a rendszer esetleges összeomlása után visszaállítható. Maarten van Steen, Kitlei Róbert


23 / 31

1.1 Definíció

1.2 Célok


Tranzakciófeldolgozó monitor (Transaction Processing Monitor) Megjegyzés A tranzakciókat sokszor több szerver hajtja végre. Ezeket egy TP monitor vezérli.

Server Reply Transaction

Request Requests Request

Client application

Server

TP monitor Reply Reply

Request Reply



Server

24 / 31

1.1 Definíció

1.2 Célok


Alkalmazásintegráció nagy rendszerekben Probléma A TP monitor nem választja el az alkalmazásokat az adatbázisoktól. Továbbá az alkalmazásoknak egymással is kommunikálniuk kell.

Client application

Client application

Communication middleware

Server-side application



Távoli eljáráshívás (Remote Procedure Call, RPC) Üzenetorientált köztesréteg (Message-Oriented Middleware, MOM) Maarten van Steen, Kitlei Róbert


25 / 31

1.1 Definíció

1.2 Célok


Elosztott átható rendszerek

Átható rendszer ˝ áll. Sok modern elosztott rendszer kicsi, mobil elemekbol Néhány jellemzo˝ A környezet megváltozhat: A rendszernek ezt követnie kell. ˝ Ad hoc szervezodés: A rendszer komponenseit nagyon különbözo˝ módokon használhatják a felhasználók. Ezért a rendszernek könnyen konfigurálhatónak kell lennie. Megosztott szolgáltatások: Mivel a rendszer nagyon változékony, az ˝ adatoknak könnyen kell áramlaniuk. Ennek elosegítésére a rendszer elemei általában nagyon egyszeru˝ szerkezetuek. ˝



26 / 31

1.1 Definíció

1.2 Célok


˝ Érzékelohálózatok

˝ Jellemzok ˝ Az érzékeloket tartalmazó csúcsok ˝ sok van belolük (nagyságrendileg 10-1000 darab) egyszeruek ˝ (kevés memória, számítási és kommunikációs kapacitás) ˝ muködnek, sokszor elemrol ˝ vagy áramforrás sem szükséges hozzájuk



27 / 31

1.1 Definíció

1.2 Célok


˝ Érzékelohálózatok mint elosztott rendszerek Sensor network Operator's site

Sensor data is sent directly to operator (a)

Each sensor can process and store data

Sensor network

Operator's site Query

Sensors send only answers Maarten van Steen, Kitlei Róbert


(b)

28 / 31

1.1 Definíció

1.2 Célok


Példák Tömegirányítás Helyzet: rendezvény fix útvonalakkal (kiállítás, fesztivál) Cél: az embereket a megfelelo˝ helyre irányítani ˝ a hasonló érdeklodés u˝ emberek egy helyre menjenek vészhelyzet esetén a fenti csoportokat ugyanahhoz a kijárathoz irányítani

Cél: összetartozó embereket (pl. családokat) egyben tartani



29 / 31

1.1 Definíció

1.2 Célok


Példák

Szociális játék ˝ különbözo˝ csoportokban Helyzet: Konferencia, a résztvevok érkeztek. ˝ Cél: A csoportok vegyítésének elosegítése. Megközelítés: A rendszer figyeli, hogy a csoportok hogyan viselkednek Ha külön csoportokból származó embereket észlel, bónuszpontokat kapnak az emberek és a csoportok egyaránt. A rendszer kiosztja a csoportszintu˝ pontokat a tagok között. ˝ mutatják (feedback and Az eredményeket elektronikus kituz ˝ ok social intervention).



30 / 31

1.1 Definíció

1.2 Célok


Példa: Szociális játék ˝ A szociális játék egy kituz ˝ oje.



31 / 31


Kitlei Róbert 2


2. rész: Architektúrák 2015. május 24.




2 / 26

2.1 Architektúrafajták

2.2 Rendszerarchitektúrák

2.3 Architektúrák és köztesréteg

2.4 Önszervezés

Architektúrák

Architektúrafajták Szoftverarchitektúrák Architektúrák és köztesréteg Az elosztott rendszerek önszervezése



3 / 26




2.4 Önszervezés

Architektúrafajták Alapötlet A rendszer elemeit szervezzük logikai szerepük szerint különbözo˝ komponensekbe, és ezeket osszuk el a rendszer gépein. Layer N

Object

Object

Layer N-1 Object

Request flow

Method call

Response flow Object

Layer 2 Object Layer 1 (a)

(b)

(a) A többrétegu˝ megközelítés kliens-szerver rendszerek esetén jól muködik ˝ (b) Itt a komponensek (objektumok) összetettebb struktúrában kommunikálnak, mindegyik közvetlenül küld üzeneteket a többieknek. Maarten van Steen, Kitlei Róbert


4 / 26




2.4 Önszervezés

Architektúrafajták További architektúrafajták A komponensek közötti kommunikáció történhet közvetlen kapcsolat nélkül („anonim”), illetve egyidejuség ˝ nélkül („aszinkron”).

Component

Component Event delivery

Component

Component Publish

Data delivery Event bus Publish

Shared (persistent) data space

Component (b)

(a)

(a) Publish/subscribe modell (térben független) ˝ (b) Megosztott, perzisztens adattár (térben és idoben független) Maarten van Steen, Kitlei Róbert


5 / 26



2.3 A

Központosított architektúrák Egyszeru˝ kliens–szerver modell ˝ Jellemzoi: egyes folyamatok szolgáltatásokat ajánlanak ki (ezek a szerverek) más folyamatok ezeket a szolgáltatásokat szeretnék használni (ezek a kliensek) a kliensek és a szerverek különbözo˝ gépeken lehetnek a kliens kérést küld (amire a szerver válaszol), így veszi igénybe a szolgáltatást Wait for result

Client Request

Reply

Server Provide service



Time

6 / 26



2.3 A

Többrétegu˝ architektúrák

Elosztott információs rendszerek rétegelése Az elosztott információs rendszerek gyakran három logikai rétegre („layer” vagy „tier”) vannak tagolva. Háromrétegu˝ architektúra Megjelenítés (user interface): az alkalmazás felhasználói felületét ˝ áll alkotó komponensekbol Üzleti logika (application): az alkalmazás muködését ˝ írja le (konkrét adatok nélkül) Perzisztencia (data layer): az adatok tartós tárolása



7 / 26



2.3 A


User-interface level

User interface

Keyword expression

HTML page containing list HTML generator

Query generator Database queries

Database with Web pages


Ranked list of page titles

Processing level

Ranking algorithm Web page titles with meta-information


Data level

8 / 26



2.3 A

Többrétegu˝ architektúrák ˝ néha több is egy gépen található meg. A három rétegbol Kétrétegu˝ architektúra: kliens/egyszeru˝ szerver Egyrétegu˝ architektúra: nagygépre (mainframe) kötött terminál A kétrétegu˝ architektúra többféleképpen bonthatja fel a három réteget: Client machine User interface

User interface

User interface

User interface

User interface

Application

Application

Application Database

User interface Application

Application

Application

Database

Database

Database

Database

Database

(d)

(e)

Server machine (a)


(b)

(c)


9 / 26



2.3 A

Decentralizált architektúrák Peer-to-peer architektúra Az utóbbi években a peer-to-peer (P2P) architektúra egyre népszerubbé ˝ válik. A „peer” szó arra utal, hogy a csúcsok között (többnyire) nincsenek kitüntetett szerepuek. ˝ strukturált P2P: a csúcsok által kiadott gráfszerkezet rögzített strukturálatlan P2P: a csúcsok szomszédai véletlenszeruek ˝ hibrid P2P: néhány csúcsnak speciális szerepe van, ezek a ˝ eltéro˝ szervezésuek többitol ˝ Overlay hálózat overlay: A gráfban szomszédos csúcsok a fizikai hálózaton lehetnek távol egymástól, a rendszer elfedi, hogy a köztük levo˝ kommunikáció több gépet érintve történik. A legtöbb P2P rendszer overlay hálózatra épül. Maarten van Steen, Kitlei Róbert


10 / 26



2.3 A

Strukturált P2P rendszerek Alapötlet A csúcsokat valamilyen struktúra szerint overlay hálózatba szervezzük (pl. logikai gyur ˝ u), ˝ és a csúcsoktól az azonosítójuk alapján lehet szolgáltatásokat igénybe venni. Actual node 15 14

0

1

{13,14,15}

{0,1}

2 3

13 12 {8,9,10,11,12}

{2,3,4}

Associated data keys

11 10

5

{5,6,7} 9

8


4

6

Példa: elosztott hasítótábla Ebben a rendszerben kulcs-érték párokat tárolunk. Az adott értéket tároló csúcsot hatékonyan meg lehet keresni a kulcsa alapján, akármelyik csúcsra is érkezik be a kérés.

7 Elosztott rendszerek

11 / 26



2.3 A

Strukturált P2P rendszerek Példa: d dimenziós particionált tér ˝ van, kulccsal nem rendelkeznek. Az adatoknak most d mezoje Az így adódó tér fel van osztva annyi tartományra, ahány csúcsunk ˝ van; minden csúcs valamelyik tartomány adataiért felelos. Ha egy új csúcs érkezik, kettébontunk egy tartományt. Keys associated with node at (0.6,0.7) (0,1)

(1,1) (0.9,0.9) (0.2,0.8)

(0.9,0.9) (0.2,0.8)

(0.6,0.7)

Actual node

(0.6,0.7) (0.9,0.6)

(0.9,0.6) (0.2,0.45)

(0.2,0.3) (0.7,0.2)

(0.7,0.2) (0.2,0.15)

(0,0)

(1,0) (a)


(b)


12 / 26



2.3 A

Strukturálatlan P2P rendszerek Strukturálatlan P2P rendszer A strukturálatlan P2P rendszerek igyekeznek véletlen gráfstruktúrát fenntartani. Mindegyik csúcsnak csak részleges nézete van a gráfról (a teljes hálózatnak csak egy kis részét látja). ˝ Minden P csúcs idoközönként kiválaszt egy szomszédos Q csúcsot P és Q információt cserél, valamint átküldik egymásnak az általuk ismert csúcsokat Megjegyzés A rendszer hibaturését ˝ és a gráf véletlenszeruségét ˝ nagyban befolyásolja az, hogy a harmadik lépésben pontosan milyen adatok kerülnek át.



13 / 26



2.3 A

Strukturálatlan P2P: pletykálás Aktív szál

Passzív szál

selectPeer(&B); selectToSend(&bufs); sendTo(B, bufs); receiveFrom(B, &bufr); selectToKeep(cache, bufr);

receiveFromAny(&A, &bufr); selectToSend(&bufs); sendTo(A, bufs); selectToKeep(cache, bufr);

˝ kiválaszt egy szomszédot. selectPeer: A részleges nézetbol selectToSend: Az általa ismert szomszédok közül kiválaszt n darabot. selectToKeep: (1) A megkapott csúcsokat eltárolja lokálisan. (2) Eltávolítja a többszörösen szereplo˝ csúcsokat. (3) A tárolt csúcsok számát m darabra csökkenti. Erre többfajta stratégia lehetséges.



14 / 26



2.3 A


Passzív szál






14 / 26



2.3 A


Passzív szál






14 / 26



2.3 A


Passzív szál






14 / 26



2.3 A


Passzív szál






14 / 26



2.3 A


Passzív szál






14 / 26



2.3 A


Passzív szál






14 / 26



2.3 A

Overlay hálózatok topológiájának kezelése Alapötlet Különböztessünk meg két réteget: (1) az alsó rétegben a csúcsoknak csak részleges nézete van; (2) a felso˝ rétegbe csak kevés csúcs kerülhet. Az alsó réteg véletlenszeru˝ csúcsokat ad át a felso˝ rétegnek; a felso˝ réteg ezek közül csak keveset tart meg.

Structured overlay

Protocol for specific overlay

Links to topologyspecific other nodes

Random peer

Random overlay


Protocol for randomized view


Links to randomly chosen other nodes

15 / 26



2.3 A

Overlay topológia: példa: tórusz Tórusz overlay topológia kialakítása ˝ Ha megfeleloen választjuk meg, milyen csúcsokat tartson meg a felso˝ réteg, akkor a kezdetben véletlenszeru˝ overlay kapcsolatok hamarosan szabályos ˝ alakba rendezodnek. Itt egy távolságfüggvény szerinti megtartó szabály hat (az overlay a közelieket veszi át), és már az elso˝ néhány lépés után jól látszik a kijövo˝ tórusz-alakzat.

Time Maarten van Steen, Kitlei Róbert


16 / 26



2.3 A

Overlay topológia: példa: clusterezés Most mindegyik i csúcshoz hozzárendelünk egy GID(i) ∈ N számot, és azt mondjuk, hogy i a GID(i) csoportba tartozik. Szintén távolságfüggvényt használunk: 1 ha GID(i) = GID(j) dist(i, j) = 0 ha GID(i) 6= GID(j) Itt is igen gyorsan kialakul a kívánt szerkezet: csak az azonos csoportbeli csúcsok között lesz kapcsolat, kialakulnak a clusterek.



17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A




17 / 26



2.3 A

Superpeer csúcsok

Superpeer superpeer: olyan kisszámú csúcs, amelyeknek külön feladata van Néhány jellemzo˝ feladat Regular peer Superpeer

kereséshez index fenntartása a hálózat állapotának felügyelete

Superpeer network


csúcsok közötti kapcsolatok létrehozása


18 / 26



2.3 A

Hibrid arch.: kliens-szerver + P2P: edge szerver Példa edge szerver: az adatokat tároló szerver, a kliensekhez minél közelebb ˝ van elhelyezve, jellemzoen ott, ahol egy nagyobb hálózat az Internetre csatlakozik ˝ a Content Delivery Network (CDN) rendszerekben jellemzo, tartalomszolgáltatás hatékonyságát növelik és költségét csökkentik. Client

Content provider ISP

ISP

Core Internet Edge server Enterprise network



19 / 26



2.3 A

Hibrid arch.: kliens-szerver + P2P: BitTorrent

Client node K out of N nodes Node 1

Lookup(F) A BitTorrent Web page Web server

Ref. to file server

.torrent file for F File server

Ref. to tracker

List of nodes storing F Tracker

Node 2

Node N

Alapötlet Miután a csúcs kiderítette, melyik másik csúcsok tartalmaznak részeket a kívánt fájlból, azokat párhuzamosan tölti le, és egyúttal önmaga is kiajánlja megosztásra.



20 / 26




2.4 Önszervezés

Architektúrák és köztesréteg

Probléma ˝ Elofordulhat, hogy az elosztott rendszer/alkalmazás szerkezete nem felel meg a megváltozott igényeknek. Ilyenkor legtöbbször nem kell újraírni a teljes rendszert: elegendo˝ lehet (dinamikusan) adaptálni a köztesréteg viselkedését. Interceptor interceptor: Távoli objektum elérése során a vezérlés szokásos menetébe avatkozik bele, pl. átalakíthatja más formátumra a kérést. ˝ ˝ Jellemzoen az architektúra rétegei közé illesztheto.



21 / 26




2.4 Önszervezés

Interceptors Client application

Intercepted call

B.do_something(value)

Application stub Request-level interceptor

Nonintercepted call invoke(B, &do_something, value)

Object middleware Message-level interceptor

send([B, "do_something", value])

Local OS To object B



22 / 26




2.4 Önszervezés

Adaptív middleware

Funkciók szétválasztása (separation of concerns): A szoftver különbözo˝ jellegu˝ funkciói váljanak minél jobban külön, így azokat könnyebb egymástól függetlenül módosítani. Önvizsgálat (reflection): A program legyen képes feltárni a saját szerkezetét, és futás közben módosítani azt. Komponensalapú szervezés: Az elosztott alkalmazás legyen ˝ moduláris, a komponensei legyenek könnyen cserélhetoek. A komponensek közötti függések legyenek egyértelmuek, ˝ és csak ˝ annyi legyen belolük, amennyi feltétlenül szükséges.



23 / 26




2.4 Önszervezés

Önszervezo˝ elosztott rendszerek

Adaptív rendszer képességei Az egyes szoftverelemek adaptivitása kihat a rendszerre, ezért megvizsgáljuk, hogyan lehet adaptív rendszereket készíteni. Különféle elvárásaink lehetnek: Önkonfiguráció Önkezelo˝ Öngyógyító Önoptimalizáló Ön*



24 / 26




2.4 Önszervezés

Adaptivitás visszacsatolással Visszacsatolásos modell Az ön* rendszerek sokszor az alábbi jellegu˝ visszacsatolásos vezérléssel rendelkeznek: mérik, hogy a rendszer mennyire tér el a kívánt tulajdonságoktól, és szükség szerint változtatnak a beállításokon. Uncontrollable parameters (disturbance / noise)

Initial configuration

Corrections

+/-

+/-

Core of distributed system

Observed output

+/Reference input

Adjustment measures

Metric estimation

Analysis Adjustment triggers Maarten van Steen, Kitlei Róbert


Measured output

25 / 26




2.4 Önszervezés

Példa: Globule Client Origin server

ISP

ISP

Core Internet Replica server Enterprise network Client

Client

Kollaboratív webes CDN, a tartalmakat költségmodell alapján helyezi el (minden szempontra: fontosság×költség). A központi szerver (origin server) elemzi, ami történt, és az alapján állítja be a fontossági paramétereket, hogy mi történt volna, ha P oldalt az S edge szerver tárolta volna. A számításokat különbözo˝ stratégiákra végzi el, végül a legjobbat választja ki. Maarten van Steen, Kitlei Róbert


26 / 26


Kitlei Róbert 2


3. rész: Folyamatok 2015. május 24.




2 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szálak: bevezetés Alapötlet ˝ A legtöbb hardvereszköznek létezik szoftveres megfeleloje. Processzor (CPU): Hardvereszköz, utasításokat képes sorban végrehajtani, ˝ származnak. amelyek egy megadott utasításkészletbol ˝ minimális Szál (thread): A processzor egyfajta szoftveres megfeleloje, kontextussal (környezettel). Ha a szálat megállítjuk, a kontextus ˝ elmentheto˝ és továbbfuttatáshoz visszatöltheto. Folyamat (process, task): Egy vagy több szálat összefogó nagyobb egység. Egy folyamat szálai közös memóriaterületen (címtartományon) dolgoznak, azonban különbözo˝ folyamatok nem látják egymás memóriaterületét. Hasonló elnevezések ˝ Fontos: nem összekeverendo! stream = folyam 6= folyamat = processz 6= processzor Maarten van Steen, Kitlei Róbert


3 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Kontextusváltás Kontextusváltás kontextusváltás: A másik folyamatnak/szálnak történo˝ vezérlésátadás, illetve a megfelelo˝ kontextusok cseréje. Így egy processzor több folyamatot/szálat is végre tud hajtani. Processzor kontextusa: Az utasítások végrehajtásában szerepet játszó kisszámú regiszter (elemi értéktároló) tartalma. ˝ ˝ Szál kontextusa: Jellemzoen nem sokkal bovebb a processzorkontextusnál. A szálak közötti váltáshoz nem kell igénybe venni az operációs rendszer szolgáltatásait. Folyamat kontextusa: Ahhoz, hogy a régi és az új folyamat memóriaterülete elkülönüljön, a memóriavezérlo˝ (memory management unit, MMU) tartalmának jórészét át kell írni, amire csak a kernel szintnek van joga. A folyamatok létrehozása, törlése és a kontextusváltás köztük sokkal költségesebb a szálakénál. Maarten van Steen, Kitlei Róbert


4 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szálak és operációs rendszerek Hol legyenek a szálak? ˝ független A szálakat kezelheti az operációs rendszer, vagy tole ˝ szálkönyvtárak. Mindkét megközelítésnek vannak elonyei és hátrányai. Szálak folyamaton belül: szálkönyvtárak ˝ elony: Minden muveletet ˝ egyetlen folyamaton belül kezelünk, ez hatékony. hátrány: Az operációs rendszer számára a szál minden muvelete ˝ a gazdafolyamattól érkezik ⇒ ha a kernel blokkolja a szálat (pl. lemezmuvelet ˝ során), a folyamat is blokkolódik. hátrány: Ha a kernel nem látja a szálakat közvetlenül, hogyan tud szignálokat közvetíteni nekik?



5 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szálak és operációs rendszerek Szálak folyamaton kívül: kernelszintu˝ szálak ˝ kernelszintre is. Ekkor minden szálmuvelet A szálkönyvtárak helyezhetoek ˝ rendszerhíváson keresztül érheto˝ el. ˝ elony: A szálak blokkolása nem okoz problémát: a kernel be tudja ütemezni a gazdafolyamat egy másik szálát. ˝ elony: A szignálokat a kernel a megfelelo˝ szálhoz tudja irányítani. hátrány: Mivel minden muvelet ˝ a kernelt érinti, ez a hatékonyság rovására megy. Köztes megoldás? ˝ Lehet-e olyan megoldást találni, ami ötvözi a fenti két megközelítés elonyeit?



6 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Solaris szálak Könnyusúlyú ˝ folyamatok könnyusúlyú ˝ folyamat (lightweight process, LWP): Kernelszintu˝ szálak, ˝ amelyek felhasználói szintu˝ szálkezeloket futtatnak. Thread state User space Thread

Lightweight process Kernel space LWP executing a thread

Támogatottsága ˝ o˝ két megközelítés valamelyikét támogatja. A legtöbb rendszer az eloz Maarten van Steen, Kitlei Róbert


7 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szálak a kliensoldalon Példa: többszálú webkliens A hálózat késleltetésének elfedése: A böngészo˝ letöltött egy oldalt, ami több másik tartalomra hivatkozik. Mindegyik tartalmat külön szálon tölti le, amíg a HTTP kéréseket kiszolgálják, ezek blokkolódnak. Amikor egy-egy fájl megérkezik, a blokkolás megszunik, ˝ és a böngészo˝ megjeleníti a tartalmat. Példa: több távoli eljáráshívás (RPC) egyszerre Egy kliens több távoli szolgáltatást szeretne igénybe venni. Mindegyik kérést külön szál kezeli. Megvárja, amíg mindegyik kérésre megérkezik a válasz. Ha különbözo˝ gépekre irányulnak a kérések, akár lineáris mértéku˝ gyorsulás is elérheto˝ így. Maarten van Steen, Kitlei Róbert


8 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szálak a szerveroldalon Cél: a hatékonyság növelése ˝ és tárigény Szálakat sokkal olcsóbb elindítani, mint folyamatokat (idoszempontjából egyaránt). Mivel egy processzor csak egy szálat tud végrehajtani, a többprocesszoros rendszerek kapacitását csak többszálú szerverek képesek kihasználni. A kliensekhez hasonlóan, a hálózat késleltetését lehet elfedni azzal, ha egyszerre több kérést dolgoz fel a szerver. Cél: a program szerkezetének javítása A program jobban kezelheto˝ lehet, ha sok egyszeru, ˝ blokkoló hívást alkalmaz, mint más szerkezet esetén. Ez némi teljesítményveszteséggel járhat. ˝ A többszálú programok sokszor kisebbek és könnyebben érthetoek, mert jobban átlátható, merre halad a vezérlés. Maarten van Steen, Kitlei Róbert


9 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Virtualizáció Fontossága A virtualizáció szerepe egyre no˝ több okból. ˝ A hardver gyorsabban fejlodik a szoftvernél ˝ Növeli a kód hordozhatóságát és költöztethetoségét A hibás vagy megtámadott rendszereket könnyu˝ így elkülöníteni

Program Interface A Program

Implementation of mimicking A on B

Interface A

Interface B

Hardware/software system A

Hardware/software system B

(a) Maarten van Steen, Kitlei Róbert

(b) Elosztott rendszerek

10 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

A virtuális gépek szerkezete Virtualizálható komponensek A rendszereknek sokfajta olyan rétege van, amely mentén virtualizálni ˝ milyen interfészeket kell lehet a komponenseket. Mindig eldöntendo, szolgáltatnia a virtuális gépnek (és milyeneket vehet igénybe).

Library functions System calls Privileged instructions

Application Library Operating system

General instructions

Hardware



11 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Process VM, VM monitor Applications Operating system Operating system Operating system

Application Runtime system Runtime system Runtime system Operating system

Virtual machine monitor

Hardware

Hardware (a)

(b)

Process VM: A virtuális gép (virtual machine, VM) közönséges ˝ programként fut, bájtkódot (elofordított programkódot) hajt végre. Pl. JVM, CLR, de vannak speciális célúak is, pl. ScummVM. VM Monitor (VMM), hypervisor: Hardver teljesköru˝ virtualizációja, bármilyen program és operációs rendszer futtatására képes. Pl. VMware, VirtualBox. Maarten van Steen, Kitlei Róbert


12 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

VM monitorok muködése ˝

VM monitorok muködése ˝ Sok esetben a VMM egy operációs rendszeren belül fut. A VMM a futtatott gépi kódú utasításokat átalakítja a gazdagép utasításaivá, és azokat hajtja végre. A rendszerhívásokat és egyéb privilegizált utasításokat, amelyek végrehajtásához az operációs rendszer közremuködésére ˝ lenne szükség, megkülönböztetett módon kezeli.



13 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Kliens: felhasználói felület Essence A kliensoldali szoftver egyik legfontosabb feladata a (grafikus) felhasználói interfész biztosítása. Application server

Application server

Window manager

Application

Xlib

Xlib

Local OS

Local OS

User's terminal Xlib interface

X protocol X kernel Device drivers Terminal (includes display keyboard, mouse, etc.)



14 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Kliens: átlátszóság ˝ A kliensekkel kapcsolatos fobb átlátszóságok hozzáférési: az RPC kliensoldali csonkja elhelyezési/áthelyezési: a kliensoldali szoftver tartja számon, hol ˝ helyezkedik el az eroforrás többszörözési: a klienscsonk kezeli a többszörözött hívásokat Client machine

Server 1

Server 2

Server 3

Client appl.

Server appl

Server appl

Server appl

Client side handles request replication

Replicated request

meghibásodási: sokszor csak a klienshez helyezheto˝ – csak ott jelezheto˝ a kommunikációs probléma



15 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szerver: általános szerkezet Általános modell szerver: Olyan folyamat, amely egy (vagy akár több) porton várja a kliensek kéréseit. Egy adott porton (ami egy 0 és 65535 közötti szám) a szerver egyfajta szolgáltatást nyújt. A 0-1023 portok közismert szolgáltatásokat nyújtanak, ezeket Unix alapú rendszereken csak rendszergazdai jogosultsággal lehet foglalni. ftp-data ftp ssh telnet smtp login


20 21 22 23 25 49

File Transfer [adatátvitel] File Transfer [vezérlés] Secure Shell Telnet Simple Mail Transfer Login Host Protocol


16 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szerver: általános szerkezet

Szerverfajták szuperszerver : Olyan szerver, amelyik több porton figyeli a bejövo˝ kapcsolatokat, és amikor új kérés érkezik, új folyamatot/szálat indít annak kezelésére. Pl. Unix rendszerekben: inetd. iteratív↔konkurens szerver : Az iteratív szerverek egyszerre csak egy kapcsolatot tudnak kezelni, a konkurensek párhuzamosan többet is.



17 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szerver: sávon kívüli kommunikáció ˝ üzenetek küldése Sürgos Meg lehet-e szakítani egy szerver muködését ˝ kiszolgálás közben? Külön port ˝ üzeneteknek van fenntartva: A szerver két portot használ, az egyik a sürgos Ezt külön szál/folyamat kezeli Amikor fontos üzenet érkezik, a normál üzenet fogadása szünetel A szálnak/folyamatnak nagyobb prioritást kell kapnia, ehhez az oprendszer támogatása szükséges Sávon kívüli kommunikáció Sávon kívüli kommunikáció használata, ha rendelkezésre áll: ˝ Pl. a TCP protokoll az eredeti kérés kapcsolatán keresztül képes sürgos üzenetek továbbítására Szignálok formájában kapható el a szerveren belül Maarten van Steen, Kitlei Róbert


18 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szerver: állapot Állapot nélküli szerver ˝ a kapcsolat bontása után. Nem tart fenn információkat a kliensrol Nem tartja számon, melyik kliens milyen fájlból kért adatokat Nem ígéri meg, hogy frissen tartja a kliens gyorsítótárát Nem tartja számon a bejelentkezett klienseket: nincsen munkamenet (session) Következmények A kliensek és a szerverek teljesen függetlenek egymástól Kevésbé valószínu, ˝ hogy inkonzisztencia lép fel azért, mert valamelyik oldal összeomlik A hatékonyság rovására mehet, hogy a szerver nem tud semmit a ˝ pl. nem tudja elore ˝ betölteni azokat az adatokat, amelyekre a kliensrol, kliensnek szüksége lehet Maarten van Steen, Kitlei Róbert


19 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szerver: állapot Állapotteljes szerverek ˝ Állapotot tart számon a kliensekrol: ˝ meg Megjegyzi, melyik fájlokat használta a kliens, és ezeket elore tudja nyitni legközelebb Megjegyzi, milyen adatokat töltött le a kliens, és frissítéseket küldhet neki ˝ Elonyök és hátrányok Az állapotteljes szerverek nagyon hatékonyak tudnak lenni, ha a kliensek lokálisan tárolhatnak adatokat. ˝ Az állapotteljes rendszereket megfeleloen megbízhatóvá is lehet tenni ˝ rontása nélkül. a hatékonyság jelentos



20 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Szerver: háromrétegu˝ clusterek Logical switch (possibly multiple)

Application/compute servers

Distributed file/database system

Dispatched request

Client requests

First tier

Second tier

Third tier

A diszpécserréteg Az elso˝ réteg feladata nagyon fontos: a beérkezo˝ kéréseket hatékonyan kell a megfelelo˝ szerverhez továbbítani. Maarten van Steen, Kitlei Róbert


21 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

A kérések kezelése Szuk ˝ keresztmetszet Ha minden kapcsolatot végig az elso˝ réteg kezel, könnyen szuk ˝ keresztmetszetté válhat. Egy lehetséges megoldás ˝ ha a kapcsolatot átadjuk (TCP handoff). A terhelés csökkentheto, Logically a single TCP connection

Client

Response

Request

Switch

Server

Request (handed off)

Server



22 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Elosztott rendszerek: mobil IPv6 Believes server has address HA

Client 1

Believes it is connected to X

APP

Believes location of X is CA1

Knows that Cient 1 believes it is X

Distributed server X Server 1

Access point with address CA1

TCP MIPv6 IP Internet

Believes server has address HA

Client 2

Believes it is connected to X

APP

Believes location of X is CA2

TCP MIPv6

Server 2

Access point with address CA2

IP Knows that Cient 2 believes it is X



23 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Elosztott rendszerek: mobil IPv6 Essence A mobil IPv6-ot támogató kliensek az elosztott szolgáltatás bármelyik peer-jéhez kapcsolódhatnak. A C kliens kapcsolódik a szerver otthonának (home address, HA) IPv6 címéhez A HA címen a szerver hazai ügynöke (home agent) fogadja a kérést, és a megfelelo˝ felügyeleti címre (care-of address, CA) továbbítja Ezután C és CA már közvetlenül tudnak kommunikálni (HA érintése nélkül) Példa: kollaboratív CDN-ek Az origin server tölti be HA szerepét, és átadja a beérkezo˝ kapcsolatot a megfelelo˝ peer szervernek. A kliensek számára az origin és a peer egy szervernek látszik. Maarten van Steen, Kitlei Róbert


24 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Kódmigráció: jellemzo˝ feladatok Kódmigráció kódmigráció: olyan kommunikáció, amely során nem csak adatokat küldünk át Jellemzo˝ feladatok Néhány jellemzo˝ feladat, amelyhez kódmigrációra van szükség.a Client-Server: a szokásos kliens-szerver kommunikáció, nincsen kódmigráció Remote Evaluation: a kliens feltölti a kódot, és a szerveren futtatja ˝ és helyben Code on Demand: a kliens letölti a kódot a szerverrol, futtatja Mobile Agent: a mobil ágens feltölti a kódját és az állapotát, és a szerveren folytatja a futását aA

következo˝ fólia ezeket a rövidítéseket tartalmazza.



25 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Kódmigráció: jellemzo˝ feladatok Client

Before execution Server

CS

Client

After execution Server

code

code

state

state*

resource

resource

code

code →

REV

→

state resource

code CoD

state

←

resource

code state*

resource

←

resource

code

code MA

state resource


state*

→

→ resource


resource

state* resource

26 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

˝ mobilitás Kódmigráció: gyenge és eros Objektumkomponensek Kódszegmens: a programkódot tartalmazza Adatszegmens: a futó program állapotát tartalmazza Végrehajtási szegmens: a futtató szál környezetét tartalmazza Gyenge mobilitás A kód- és adatszegmens mozgatása (a kód újraindul): Viszonylag egyszeru˝ megtenni, különösen, ha a kód hordozható Irány szerint: feltöltés (push, ship), letöltés (pull, fetch) ˝ mobilitás Eros A komponens a végrehajtási szegmenssel együtt költözik ˝ a másikra Migráció: az objektum átköltözik az egyik géprol Klónozás: a kód másolata kerül a másik gépre, és ugyanabból az állapotból indul el, mint az eredeti; az eredeti is fut tovább Maarten van Steen, Kitlei Róbert


27 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

˝ Kódmigráció: az eroforrások elérése ˝ Eroforrások elérése ˝ Az eredeti gépen található eroforrások költözés után a kód számára távoliakká válnak. ˝ ˝ Eroforrás–gép kötés erossége Mozdíthatatlan: nem költöztetheto˝ (pl. fizikai hardver) ˝ de csak drágán (pl. nagy adatbázis) Rögzített: költöztetheto, Csatolatlan: egyszeruen ˝ költöztetheto˝ (pl. gyorsítótár) ˝ Komponens–eroforrás kötés jellege ˝ Milyen jellegu˝ eroforrásra van szüksége a komponensnek? Azonosítókapcsolt: egy konkrét (pl. a cég adatbázisa) Tartalomkapcsolt: adott tartalmú (pl. bizonyos elemeket tartalmazó cache) Típuskapcsolt: adott jellegu˝ (pl. színes nyomtató) Maarten van Steen, Kitlei Róbert


28 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

˝ Kódmigráció: az eroforrások elérése ˝ Kapcsolat az eroforrással ˝ Hogyan tud a komponens kapcsolatban maradni az eroforrással? ˝ Típuskapcsolt eroforrás esetén a legkönnyebb újrakapcsolódni ˝ egy lokális, megfelelo˝ típusú eroforráshoz Azonosítókapcsolt vagy tartalomkapcsolt esetben: ˝ rendszerszintu˝ hivatkozást létesíthetünk az eredeti eroforrásra, ˝ ˝ mozdíthatatlan eroforrások esetén ez az egyetlen lehetoség minden más esetben is szóba jöhet, de általában van jobb megoldás

˝ azonosítókapcsolt eroforrást érdemes áthelyeznia ˝ tartalomkapcsolt eroforrást érdemes lemásolnia a ha

nem túl költséges



29 / 30

3.1 Szálak

3.2 Virtualizáció

3.3 Kliens

3.4 Szerver

3.5 Kódmigráció

Kódmigráció: heterogén rendszerben

Nehézségek A célgép nem biztos, hogy képes futtatni a migrált kódot A processzor-, szál- és/vagy folyamatkörnyezet nagyban függ a ˝ oprendszertol ˝ és futtatókörnyezettol ˝ lokális hardvertol, Megoldás problémás esetekben Virtuális gép használata: akár process VM, akár hypervisor. ˝ Természetesen a virtuális gépnek elérhetonek kell lennie mindkét környezetben.



30 / 30


Kitlei Róbert 2


4. rész: Kommunikáció 2015. május 24.




2 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Az ISO/OSI hálózatkezelési modell

Application Presentation Session Transport

Application protocol 7 Presentation protocol 6 Session protocol Transport protocol Network protocol

Network Data link protocol Data link Physical

Physical protocol

5 4 3 2 1

Network

Hátrányok Csak az üzenetküldésre koncentrál Az (5) és (6) rétegek legtöbbször nem jelennek meg ilyen tisztán Az elérési átlátszóság nem teljesül ebben a modellben Maarten van Steen, Kitlei Róbert


3 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Az alsó rétegek

A rétegek feladatai Fizikai réteg: a bitek átvitelének fizikai részleteit írja le Adatkapcsolati réteg: az üzeneteket keretekre tagolja, célja a hibajavítás és a hálózat terhelésének korlátozása Hálózati réteg: a hálózat távoli gépei között közvetít csomagokat útválasztás (routing) segítségével



4 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Szállítási réteg Absztrakciós alap A legtöbb elosztott rendszer a szállítási réteg szolgáltatásaira épít. ˝ A legfobb protokollok TCP: kapcsolatalapú, megbízható, sorrendhelyes átvitel UDP: nem (teljesen) megbízható, általában kis üzenetek (datagram) átvitele Csoportcímzés ˝ de IP-alapú többcímu˝ üzenetküldés (multicasting) sokszor elérheto, legfeljebb a lokális hálózaton belül használatos.



5 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Köztesréteg Szolgáltatásai A köztesrétegbe (middleware) olyan szolgáltatásokat és protokollokat szokás sorolni, amelyek sokfajta alkalmazáshoz lehetnek hasznosak. Sokfajta kommunikációs protokoll Sorosítás ((de)serialization, (un)marshalling), adatok reprezentációjának átalakítása (elküldésre vagy elmentésre) ˝ Elnevezési protokollok az eroforrások megosztásának megkönnyítésére Biztonsági protokollok a kommunikáció biztonságossá tételére Skálázási mechanizmusok adatok replikációjára és gyorsítótárazására Alkalmazási réteg ˝ Az alkalmazások készítoinek csak az alkalmazás-specifikus protokollokat kell önmaguknak implementálniuk. Maarten van Steen, Kitlei Róbert


6 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

A kommunikáció fajtái Synchronize at request submission

Synchronize at request delivery

Synchronize after processing by server

Client Request Transmission interrupt Storage facility Reply Server

Time

A kommunikáció lehet... ˝ idoleges (transient) vagy megtartó (persistent) aszinkron vagy szinkron Maarten van Steen, Kitlei Róbert


7 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting





Time

˝ Idoleges vs megtartó Megtartó kommunikáció: A kommunikációs rendszer hajlandó huzamosan tárolni az üzenetet. ˝ Idoleges kommunikáció: A kommunikációs rendszer elveti az üzenetet, ˝ ha az nem kézbesítheto. Maarten van Steen, Kitlei Róbert


8 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting





Time

A szinkronizáció lehetséges helyei Az üzenet elindításakor Az üzenet beérkezésekor A kérés feldolgozása után Maarten van Steen, Kitlei Róbert


9 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Kliens–szerver modell ˝ Általános jellemzok ˝ ˝ A kliens–szerver modell jellemzoen idoleges, szinkron kommunikációt használ. ˝ A kliensnek és a szervernek egyidoben kell aktívnak lennie. A kliens blokkolódik, amíg a válasz meg nem érkezik. A szerver csak a kliensek fogadásával foglalkozik, és a kérések kiszolgálásával. A szinkron kommunikáció hátrányai A kliens nem tud tovább dolgozni, amíg a válasz meg nem érkezik A hibákat rögtön kezelni kell, különben feltartjuk a klienst Bizonyos feladatokhoz (pl. levelezés) nem jól illeszkedik



10 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Üzenetküldés

Üzenetorientált köztesréteg (message-oriented middleware, MOM) Megtartó, aszinkron kommunikációs architektúra. Segítségével a folyamatok üzeneteket küldhetnek egymásnak A küldo˝ félnek nem kell válaszra várakoznia, foglalkozhat mással A köztesréteg gyakran hibaturést ˝ biztosít



11 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

RPC: alapok Az RPC alapötlete Az alprogramok használata természetes a fejlesztés során Az alprogramok a jó esetben egymástól függetlenül muködnek ˝ („fekete doboz”), ... így akár egy távoli gépen is végrehajthatóak Távoli eljáráshívás (remote procedure call, RPC) A távoli gépen futtatandó eljárása eléréséhez hálózati kommunikációra van szükség, ezt eljáráshívási mechanizmus fedi el. a tekintsük

Call remote procedure Request

Return from call Reply

Server

az alprogram szinonímájának


Wait for result

Client


Call local procedure and return results

Time

12 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

RPC: a hívás lépései Server machine

Client machine

Client process

k = add(i,j) proc: "add" int: val(i) int: val(j)

Client OS

Server process 1. Client call to procedure

Implementation of add

Server stub Client stub

k = add(i,j) proc: "add" int: val(i) int: val(j)

2. Stub builds message proc: "add" int: val(i) int: val(j)

6. Stub makes local call to "add"

Server OS

5. Stub unpacks message 4. Server OS hands message to server stub

3. Message is sent across the network

1 A kliensfolyamat lokálisan meghívja a klienscsonkot. 2 Az becsomagolja az eljárás azonosítóját és paramétereit, meghívja az OS-t. 3 Az átküldi az üzenetet a távoli OS-nek. 4 Az átadja az üzenetet a szervercsonknak. Maarten van Steen, Kitlei Róbert

5 Az kicsomagolja a paramétereket, átadja a szervernek. 6 A szerver lokálisan meghívja az eljárást, megkapja a visszatérési értéket. 7 Ennek visszaküldése a klienshez hasonlóan zajlik, fordított irányban.


13 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

RPC: paraméterátadás A paraméterek sorosítása A második lépésben a klienscsonk elkészíti az üzenetet, ami az egyszeru˝ bemásolásnál összetettebb lehet. A kliens- és a szervergépen eltérhet az adatábrázolás (eltéro˝ bájtsorrend) ˝ A sorosítás során bájtsorozat készül az értékbol Rögzíteni kell a paraméterek kódolását: A primitív típusok reprezentációját (egész, tört, karakteres) Az összetett típusok reprezentációját (tömbök, egyéb adatszerkezetek)

A két csonknak fordítania kell a közös formátumról a gépeik formátumára



14 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

RPC: paraméterátadás RPC paraméterátadás szemantikája Érték–eredmény szerinti paraméterátadási szemantika: pl. figyelembe kell venni, hogy ha (a kliensoldalon ugyanoda mutató) hivatkozásokat adunk át, azokról ez a hívott eljárásban nem látszik. Minden feldolgozandó adat paraméterként kerül az eljáráshoz; nincsen globális hivatkozás. Átlátszóság Nem értheto˝ el teljes mértéku˝ elérési átlátszóság. Távoli hivatkozás Távoli hivatkozás bevezetésével növelheto˝ az elérési átlátszóságot: A távoli adat egységesen érheto˝ el A távoli hivatkozásokat át lehet paraméterként adni Maarten van Steen, Kitlei Róbert


15 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Aszinkron RPC

Az RPC „javítása” A szerver nyugtázza az üzenet megérkezését. Választ nem vár. Wait for result

Client

Return from call

Call remote procedure Request Server

Client

Call remote procedure

Time

Server

(a)


Return from call

Request

Reply

Call local procedure and return results

Wait for acceptance

Accept request

Call local procedure

Time

(b)


16 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Késleltetett szinkronizált RPC Késleltetett szinkronizált RPC Ez két aszinkron RPC, egymással összehangolva. Interrupt client

Wait for acceptance

Client Call remote procedure

Request

Return from call

Return results

Acknowledge

Accept request

Server Call local procedure

Time Call client with one-way RPC

˝ További lehetoség ˝ ˝ A kliens elküldheti a kérését, majd idonként lekérdezheti a szervertol, kész-e már a válasz. Maarten van Steen, Kitlei Róbert


17 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

RPC: a használt fájlok Uuidgen Interface definition file IDL compiler

Client code

Client stub

Header

#include

Server stub

Server code

#include

C compiler

C compiler

C compiler

C compiler

Client object file

Client stub object file

Server stub object file

Server object file

Linker

Runtime library

Runtime library

Linker

Client binary Maarten van Steen, Kitlei Róbert

Server binary Elosztott rendszerek

18 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

RPC: a kliens csatlakozása a szerverhez A kliens 1 A szolgáltatások katalógusba jegyzik be (globálisan és lokálisan ˝ el. (1-2) is), melyik gépen érhetoek 2

A kliens kikeresi a szolgáltatást a katalógusból. (3)

3

A kliens végpontot igényel a démontól a kommunikációhoz. (4)

Directory machine Directory server 3. Look up server

2. Register service Server machine

Client machine 5. Do RPC Client 4. Ask for endpoint



Server

DCE daemon

1. Register endpoint

Endpoint table 19 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

˝ Idoleges kommunikáció: socket

Server socket

bind

listen

accept

read

Synchronization point socket

write

close

Communication connect

write

read

close

Client



20 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Socket: példa Python nyelven Szerver import socket HOST = ’’ PORT = SERVERPORT srvsock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) srvsock.bind((HOST, PORT)) srvsock.listen(N) # legfeljebb N kliens várakozhat clsock, addr = srvsock.accept() # lokális végpont + távoli végpont címe while True: # potenciálisan végtelen ciklus data = clsock.recv(1024) if not data: break clsock.send(data) clsock.close()

Kliens import socket HOST = ’distsys.cs.vu.nl’ PORT = SERVERPORT s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((HOST, PORT)) s.send(’Hello, world’) data = s.recv(1024) s.close() Maarten van Steen, Kitlei Róbert


21 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Üzenetorientált köztesréteg

Muködési ˝ elv A köztesréteg várakozási sorokat (queue) tart fenn a rendszer gépein. A kliensek az alábbi muveleteket ˝ használhatják a várakozási sorokra. PUT GET POLL NOTIFY

Üzenetet tesz egy várakozási sor végére Blokkol, amíg a sor üres, majd leveszi az elso˝ üzenetet Nem-blokkoló módon lekérdezi, van-e üzenet, ha igen, le˝ veszi az elsot ˝ Kezelorutint telepít a várakozási sorhoz, amely minden beérkezo˝ üzenetre meghívódik



22 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Üzenetközvetíto˝ Üzenetsorkezelo˝ rendszer homogenitása Az üzenetsorkezelo˝ rendszerek feltételezik, hogy a rendszer minden eleme közös protokollt használ, azaz az üzenetek szerkezete és ˝ adatábrázolása megegyezo. Üzenetközvetíto˝ üzenetközvetíto˝ (message broker): Olyan központi komponens, amely heterogén rendszerben gondoskodik a megfelelo˝ konverziókról. Átalakítja az üzeneteket a fogadó formátumára. Szerepe szerint igen gyakran átjáró (application-level gateway, proxy) is, azaz a közvetítés mellet további (pl. biztonsági) funkciókat is nyújt Az üzenetek tartalmát is megvizsgálhatják az útválasztáshoz (subject based vagy object based routing) ⇒ Enterprise Application Integration Maarten van Steen, Kitlei Róbert


23 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Üzenetközvetíto˝

Source client

Message broker

Repository with conversion rules and programs

Destination client

Broker program

OS

Queuing layer OS

OS

Network



24 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Példa: WebSphere MQ (IBM) Muködési ˝ elv ˝ neve itt sorkezelo˝ (queue manager); adott Az üzenetkezelok alkalmazásoknak címzett üzeneteket fogadnak ˝ össze lehet szerkeszteni a kliensprogrammal Az üzenetkezelot Az üzenetkezelo˝ RPC-n keresztül is elérheto˝

Az útválasztótáblák (routing table) megadják, melyik kimeno˝ csatornán kell továbbítani az üzenetet A csatornákat üzenetcsatorna-ügynökök (message channel agent, MCA) kezelik Kiépítik a hálózati kapcsolatokat (pl. TCP/IP) Ki- és becsomagolják az üzeneteket, és fogadják/küldik a csomagokat a hálózatról



25 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Példa: WebSphere MQ (IBM) Routing table

Sending client

Program

Client's receive queue

Send queue

Queue manager

Queue manager

Receiving client

Program

MQ Interface Server stub

Stub

RPC (synchronous)

MCA MCA

Local network

MCA MCA

Server stub

Stub

Enterprise network To other remote queue managers

Message passing (asynchronous)

A csatornák egyirányúak ˝ A sorkezelokhöz beérkezo˝ üzenetek automatikusan továbbítódnak a megfelelo˝ lokális MCA-hoz Az útválasztás paramétereit kézzel adják meg Maarten van Steen, Kitlei Róbert


26 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Példa: WebSphere MQ (IBM) Álnevek ˝ Távoli üzenetkezelohöz álnevet (alias) is lehet rendelni, ez csak a lokális ˝ belül érvényes. üzenetkezelon

Alias table LA1 LA2

QMC QMD

SQ2

Routing table QMB SQ1 QMC SQ1 QMD SQ2

Alias table LA1 LA2

SQ1

QMA SQ1 QMC SQ2 QMB SQ1

SQ2

Routing table QMA SQ1 QMC SQ1 QMD SQ1

SQ1

QMA

Routing table

QMA QMD

SQ1

QMB

QMC

Routing table QMA SQ1 QMB SQ1 QMD SQ1

Alias table QMD

LA1 LA2

QMA QMC


SQ1


27 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Folyamatos média Az ido˝ szerepe Az eddig tárgyalt kommunikációfajtákban közös, hogy diszkrét ˝ ábrázolásúak: az adategységek közötti idobeli kapcsolat nem befolyásolja azok jelentését. Folyamatos ábrázolású média ˝ ˝ A fentiekkel szemben itt a továbbított adatok idofügg oek. Néhány jellemzo˝ példa: audio videó animációk ˝ szenzorok adatai (homérséklet, nyomás stb.)



28 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Folyamatos média

Adatátviteli módok ˝ Többfajta megkötést tehetünk a kommunikáció idobeliségével kapcsolatban. aszinkron: nem ad megkötést arra, hogy mikor kell átvinni az adatot ˝ szinkron: az egyes adatcsomagoknak megadott idotartam alatt célba kell érniük izokron vagy izoszinkrona : felso˝ és alsó korlátot is ad a csomagok átvitelére; a remegés (jitter) így korlátozott mértéku˝ a α-=(fosztóképzo), ˝

˝ σύν=együtt, χρόνος=ido˝ ἴσος=egyenlo,



29 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Folyam Adatfolyam adatfolyam: Izokron adatátvitelt támogató kommunikációs forma. ˝ Fontosabb jellemzok Egyirányú Legtöbbször egy forrástól (source) folyik egy vagy több nyelo˝ (sink) felé A forrás és/vagy a nyelo˝ gyakran közvetlenül kapcsolódik ˝ hardverelemekhez (pl. kamera, képernyo) egyszeru˝ folyam: egyfajta adatot továbbít, pl. egy audiocsatornát vagy csak videót összetett folyam: többfajta adatot továbbít, pl. sztereo audiót vagy hangot+videót



30 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Folyam: QoS ˝ Szolgáltatás minosége ˝ ezeket A folyamokkal kapcsolatban sokfajta követelmény írható elo, ˝ összefoglaló néven a szolgáltatás minoségének (Quality of Service, ˝ a következok: ˝ QoS) nevezzük. Ilyen jellemzok A folyam átvitelének „sebessége”: bit rate. A folyam megindításának legnagyobb megengedett késleltetése. A folyam adategységeinek megadott ido˝ alatt el kell jutniuk a ˝ (end-to-end delay), illetve számíthat az forrástól a nyeloig oda-vissza út is (round trip delay). ˝ Az adategységek beérkezési idoközeinek egyenetlensége: remegés (jitter).



31 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Folyam: QoS biztosítása Differenciált szolgáltatási architektúra Több hálózati eszköz érheto˝ el, amelyekkel a QoS biztosítható. ˝ Egy lehetoség, ha a hálózat routerei kategorizálják az áthaladó forgalmat a beérkezo˝ adatcsomagok tartalma szerint, és egyes ˝ csomagfajtákat elsobbséggel továbbítanak (differentiated services). A remegés csökkentése A routerek pufferelhetik az adatokat a remegés csökkentésére. Packet departs source 1 2 3 4 5 6 7 8 Packet arrives at buffer

1

2

3 4 5

6

Time in buffer

Packet removed from buffer

7

8

1 2 3 4 5 6 7

8 Gap in playback

0


5

10 Time (sec)


15

20

32 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Folyam: QoS biztosítása A csomagok elveszhetnek útközben. Ennek hatását mérsékelheti, ha a csomagon belül az adatelemek sorrendjét kissé módosítjuk; ennek ára, hogy a lejátszás lassabban indul meg. Lost packet Sent

Delivered

1

2

1

2

3

3

4

4

5

6

7

5

6

7

8

9 10 11 12

8

9

13 14 15 16

10 11 12 13 14 15 16

Gap of lost frames (a)

Lost packet Sent

Delivered

1

5

1

2

9 13

3

4

2

6 10 14

5

6

7

3

8

9

7 11 15

4

8 12 16

10 11 12 13 14 15 16

Lost frames (b) Maarten van Steen, Kitlei Róbert


33 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Összetett folyam szinkronizációja ˝ Szinkronizáció a nyelonél ˝ Az összetett folyam alfolyamait szinkronizálni kell a nyelonél, különben ˝ idoben elcsúszhatnának egymáshoz képest. Receiver's machine Procedure that reads two audio data units for each video data unit

Application

Incoming stream OS

Network

Multiplexálás ˝ Másik lehetoség: a forrás már eleve egyetlen folyamot készít (multiplexálás). Ezek garantáltan szinkronban vannak egymással, a ˝ ˝ nyelonél csak szét kell oket bontani (demultiplexálás). Maarten van Steen, Kitlei Róbert


34 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Alkalmazásszintu˝ multicasting A hálózat minden csúcsának szeretnénk üzenetet tudjunk küldeni ˝ (multicast). Ehhez hierarchikus overlay hálózatba szervezzük oket. Chord struktúrában tárolt fa készítése A multicast hálózatunkhoz generálunk egy azonosítót, így egyszerre több multicast hálózatunk is lehet egy rendszerben. Tegyük fel, hogy az azonosító egyértelmuen ˝ kijelöl egy csúcsot a rendszerünkbena . Ez a csúcs lesz a fa gyökere. Terv: a küldendo˝ üzeneteket mindenki elküldi a gyökérhez, majd onnan a fán lefele terjednek. Ha a P csúcs csatlakozni szeretne a multicast hálózathoz, csatlakozási kérést küld a gyökér felé. A P csúcstól a gyökérig egyértelmu˝ az útvonalb ; ennek minden csúcsát a fa részévé ˝ válik a gyökértol. ˝ teszünk (ha még nem volt az). Így P elérhetové a Ez

˝ a technikai részletek késobb ˝ jönnek. az azonosító ún. rákövetkezoje; ˝ szintén késobb.

b Részletek



35 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Alkalmazásszintu˝ multicasting: költségek End host A

Router 1

1 30

Ra

C

20

Re

Rc 5

7 40 1 Rb

Rd 1

Internet

D

B Overlay network

Kapcsolatok terhelése: Mivel overlay hálózatot alkalmazunk, ˝ elofordulhat, hogy egy üzenetküldés többször is igénybe veszi ugyanazt a fizikai kapcsolatot. Példa: az A → D üzenetküldés kétszer halad át az Ra → Rb élen. Stretch: Az overlayt követo˝ és az alacsonyszintu˝ üzenetküldés költségének hányadosa. Példa: B → C overlay költsége 71, hálózati 47 ⇒ stretch = 71/47. Maarten van Steen, Kitlei Róbert


36 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járványalapú algoritmusok Alapötlet Valamelyik szerveren frissítési muveletet ˝ (update) hajtottak végre, azt szeretnénk, hogy ez elterjedjen a rendszerben minden szerverhez. Minden szerver elküldi a változást néhány szomszédjának (messze nem az összes csúcsnak) lusta módon (nem azonnal) Tegyük fel, hogy nincs olvasás-írás konfliktus a rendszerben. Két alkategória Anti-entrópia: Minden szerver rendszeresen kiválaszt egy másikat, és kicserélik egymás között a változásokat. ˝ Pletykálás (gossiping): Az újonnan frissült (megfertozött) szerver ˝ oket). ˝ elküldi a frissítést néhány szomszédjának (megfertozi



37 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járvány: anti-entrópia A frissítések cseréje P csúcs Q csúcsot választotta ki. Küldés (push): P elküldi a nála levo˝ frissítéseket Q-nak Rendelés (pull): P bekéri a Q-nál levo˝ frissítéseket Küldés–rendelés (push–pull): P és Q kicserélik az adataikat, így ugyanaz lesz mindketto˝ tartalma. Hatékonyság ˝ A küldo–rendel o˝ megközelítés esetében O(log(N)) nagyságrendu˝ forduló megtétele után az összes csúcshoz eljut a frissítés. Egy fordulónak az számít, ha mindegyik csúcs megtett egy lépést.



38 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Fraction ignorant

Járvány: anti-entrópia: hatékonyság

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

pull push

5


10

15 Cycle


20

25

39 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járvány: pletykálás

Muködési ˝ elv Ha az S szerver új frissítést észlelt, akkor felveszi a kapcsolatot más szerverekkel, és elküldi számukra a frissítést. Ha olyan szerverhez kapcsolódik, ahol már jelen van a frissítés, akkor 1 ˝ abbahagyja a frissítés terjesztését. k valószínuséggel



40 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járvány: pletykálás: hatékonyság Hatékonyság ˝ Kelloen sok szerver esetén a tudatlanságban maradó szerverek (akikhez nem jut el a frissítés) száma exponenciálisan csökken a k valószínuség ˝ növekedésével, de ezzel az algoritmussal nem garantálható, hogy minden szerverhez eljut a frissítés. k 1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

-2.5 -5.0 -7.5 -10.0 ln(s) -12.5

Consider 10,000 nodes k s Ns 1 0.203188 2032 2 0.059520 595 3 0.019827 198 4 0.006977 70 5 0.002516 25 6 0.000918 9 7 0.000336 3

-15.0



41 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járvány: értékek törlése

A törlési muvelet ˝ nem terjesztheto˝ ˝ oekhez ˝ Ha egy adat törlésének muveletét ˝ is az eloz hasonlóan terjesztenénk a szerverek között, akkor a még terjedo˝ frissítési muveletek ˝ újra létrehoznák az adatot ott, ahová a törlés eljutott. Megoldás A törlést speciális frissítésként: halotti bizonyítvány (death certificate) küldésével terjesztjük.



42 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járvány: értékek törlése

Halotti bizonyítvány törlése ˝ A halotti bizonyítványt nem akarjuk örökké tárolni. Mikor törölhetoek? Szemétgyujtés-jelleg ˝ u˝ megközelítés: Egy rendszerszintu˝ algoritmussal felismerjük, hogy mindenhová eljutott a bizonyítvány, és ekkor mindenhonnan eltávolítjuk. Ez a megoldás nem jól skálázódik. ˝ elavuló bizonyítvány: Kibocsátás után adott idovel a bizonyítvány ˝ így viszont nem garantálható, hogy elavul, és ekkor törölheto; mindenhová elér.



43 / 44

Rétegek

RPC

Üzenetek

Folyamok

Multicasting

Járvány: példák Példa: adatok elterjesztése ˝ alkalmazása a járványalapú Az egyik legfontosabb és legjellemzobb algoritmusoknak. Példa: adatok aggregálása Most a cél a csúcsokban tárolt adatokból új adatok kiszámítása. Kezdetben mindegyik csúcs egy értéket tárol: xi . Amikor két csúcs pletykál, mindketto˝ a tárolt értékét a korábbi értékek átlagára állítja: xi , xj ←

xi + xj 2

Mivel az értékek minden lépésben közelednek egymáshoz, de az összegük megmarad, mindegyik érték a teljes átlaghoz konvergál. x¯ = Maarten van Steen, Kitlei Róbert

∑i xi N


44 / 44


Kitlei Róbert 2


5. rész: Elnevezési rendszerek 2015. május 24.




2 / 30

5.1 Naming Entities

5.2 Strukturálatlan nevek

5.3 Strukturált nevek

5.4 Attribútumalapú nevek

Elnevezési rendszerek Elnevezési rendszerek Az elosztott rendszerek entitásai a kapcsolódási pontjaikon (access ˝ el. Ezeket távolról a címük azonosítja, amely point) keresztül érhetoek megnevezi az adott pontot. Célszeru˝ lehet az entitást a kapcsolódási pontjaitól függetlenül is elnevezni. Az ilyen nevek helyfüggetlenek (location independent). Az egyszeru˝ neveknek nincsen szerkezete, tartalmuk véletlen szöveg. Az egyszeru˝ nevek csak összehasonlításra használhatóak. Azonosító Egy név azonosító, ha egy-egy kapcsolatban áll a megnevezett egyeddel, és ez a hozzárendelés maradandó, azaz a név nem ˝ sem. hivatkozhat más egyedre késobb



3 / 30

5.1 Naming Entities




Strukturálatlan nevek

Strukturálatlan nevek feloldása ˝ Milyen lehetoségek vannak strukturálatlan nevek feloldására? (Azaz: hogyan találjuk meg a hozzárendelt kapcsolódási pontot?) egyszeru˝ megoldások (broadcasting) otthonalapú megoldások elosztott hasítótáblák (strukturált P2P) hierarchikus rendszerek



4 / 30

5.1 Naming Entities




Névfeloldás: egyszeru˝ megoldások Broadcasting Kihirdetjük az azonosítót a hálózaton; az egyed visszaküldi a jelenlegi címét. Lokális hálózatokon túl nem skálázódik A hálózaton minden gépnek figyelnie kell a beérkezo˝ kérésre Továbbítómutató Amikor az egyed elköltözik, egy mutató marad utána az új helyére. ˝ el van fedve, hogy a szoftver továbbítómutató-láncot old fel. A kliens elol A megtalált címet vissza lehet küldeni a klienshez, így a további feloldások gyorsabban mennek. Földrajzi skálázási problémák ˝ A hosszú láncok nem hibatur ˝ oek ˝ A feloldás hosszú idobe telik Külön mechanizmus szükséges a láncok rövidítésére Maarten van Steen, Kitlei Róbert


5 / 30

5.1 Naming Entities




Otthonalapú megközelítések Egyrétegu˝ rendszer Az egyedhez tartozik egy otthon, ez tartja számon az egyed jelenlegi címét. Az egyed otthoni címe (home address) be van jegyezve egy névszolgáltatásba Az otthon számon tartja az egyed jelenlegi címét (foreign address) A kliens az otthonhoz kapcsolódik, onnan kapja meg az aktuális címet Kétrétegu˝ rendszer Az egyes (pl. földrajzi alapon meghatározott) környékeken feljegyezzük, hogy melyik egyedek tartózkodnak éppen arrafelé. ˝ A névfeloldás eloször ezt a jegyzéket vizsgálja meg Ha az egyed nincsen a környéken, csak akkor kell az otthonhoz fordulni Maarten van Steen, Kitlei Róbert


6 / 30

5.1 Naming Entities




Otthonalapú megközelítések

Host's home location

1. Send packet to host at its home 2. Return address of current location Client's location 3. Tunnel packet to current location

4. Send successive packets to current location Host's present location



7 / 30

5.1 Naming Entities




Otthonalapú megközelítések

Problémák Legalább az egyed élettartamán át fenn kell tartani az otthont Az otthon helye rögzített ⇒ költséges lehet, ha az egyed messze költözik Rossz földrajzi skálázódás: az egyed sokkal közelebb lehet a klienshez az otthonnál



8 / 30

5.1 Naming Entities




Eloszott hasítótábla Chord eloszott hasítótábla Elosztott hasítótáblát (distributed hash table, DHT) készítünk (konkrétan Chord protokoll szerintit), ebben csúcsok tárolnak egyedeket. Az N csúcs gyur ˝ u˝ overlay szerkezetbe van szervezve. Mindegyik csúcshoz véletlenszeruen ˝ hozzárendelünk egy m bites azonosítót, és mindegyik entitáshoz egy m bites kulcsot. (Tehát N ≤ 2m .) ˝ az az id azonosítójú csúcs, amelyre A k kulcsú egyed felelose ˝ csúcsot a kulcs k ≤ id, és nincsen köztük másik csúcs. A felelos ˝ rákövetkezojének is szokás nevezni; jelölje succ(k ). ˝ o˝ megoldás Rosszul méretezod ˝ A csúcsok eltárolhatnák a gyur ˝ u˝ következo˝ csúcsának elérhetoségét, és így lineárisan végigkereshetnénk a gyur ˝ ut. ˝ Ez O(N) hatékonyságú, ˝ rosszul skálázódik, nem hibatur ˝ o... Maarten van Steen, Kitlei Róbert


9 / 30

5.1 Naming Entities




DHT: Finger table Chord alapú adattárolás Mindegyik p csúcs egy FTp „finger table”-t tárol m bejegyzéssel: FTp [i] = succ(p + 2i−1 ) Bináris (jellegu) ˝ keresést szeretnénk elérni, ezért minden lépés felezi a keresési tartományt: 2m−1 , 2m−2 , . . . , 20 . A k kulcsú egyed kikereséséhez (ha nem a jelenlegi csúcs tartalmazza) a kérést továbbítjuk a j indexu˝ csúcshoz, amelyre FTp [j] ≤ k < FTp [j + 1] illetve, ha p < k < FTp [1], akkor is FTp [1]-hez irányítjuk a kérést. ˝ o˝ megoldás Jól méretezod Ez a megoldás O(m), azaz O(log(N)) hatékonyságú. Maarten van Steen, Kitlei Róbert


10 / 30

5.1 Naming Entities




DHT: Finger table Actual node 30 1 2 3 4 5

31

0

1

1 2 3 4 5

4 Finger table 4 9 9 18

2

1 2 3 4 5

3

28 27

4

6

25

7 8

24 23

28 28 28 1 9


11 11 14 18 28

10 21

11 20

1 2 3 4 5

1 2 3 4 5

9

Resolve k = 26 from node 1

22 1 2 3 4 5

2

5

Resolve k = 12 from node 28

26

+

su 9 9 9 14 20

i

29

1 1 1 4 14

i-1 )

(p cc

21 28 28 28 4

12 13

19 18 1 2 3 4 5

17

16

15

1 2 3 4 5

14 14 18 20 28

14

20 20 28 28 4


1 2 3 4 5

18 18 18 28 1

11 / 30

5.1 Naming Entities




A hálózati közelség kihasználása Probléma Mivel overlay hálózatot használunk, az üzenetek sokat utazhatnak két csúcs között: a k és a succ(k + 1) csúcs messze lehetnek egymástól. Azonosító topológia szerinti megválasztása: A csúcsok azonosítóját megpróbálhatjuk topológiailag közeli csúcsokhoz közelinek választani. Ez nehéz feladat lehet. Közelség szerinti útválasztás: A p csúcs FTp táblája m elemet tartalmaz. Ha ennél több információt is eltárolunk p-ben, akkor egy lépés megtételével közelebb juthatunk a célcsúcshoz. Szomszéd közelség szerinti megválasztása: Ha a Chordtól eltéro˝ ábrázolást követünk, a csúcs szomszédainak megválasztásánál azok közelségét is figyelembe lehet venni.



12 / 30

5.1 Naming Entities




Hierarchikus módszerek Hierarchical Location Services (HLS) A hálózatot osszuk fel tartományokra, és mindegyik tartományhoz tartozzon egy katalógus. Építsünk hierarchiát a katalógusokból. The root directory node dir(T)

Top-level domain T Directory node dir(S) of domain S A subdomain S of top-level domain T (S is contained in T)

A leaf domain, contained in S



13 / 30

5.1 Naming Entities




HLS: Katalógus-csúcsok A csúcsokban tárolt adatok Az E egyed címe egy levélben található meg ˝ az E leveléig vezeto˝ úton minden belso˝ csúcsban van egy A gyökértol mutató a lefelé következo˝ csúcsra az úton ˝ van Mivel a gyökér minden út kiindulópontja, minden egyedrol információja Field with no data Field for domain dom(N) with pointer to N

Location record for E at node M M N

Location record with only one field, containing an address

Domain D1 Maarten van Steen, Kitlei Róbert


Domain D2 14 / 30

5.1 Naming Entities




HLS: Keresés a fában Keresés a fában A kliens valamelyik tartományba tartozik, innen indul a keresés Felmegyünk a fában addig, amíg olyan csúcshoz nem érünk, amelyik tud ˝ aztán követjük a mutatókat a levélig, ahol megvan E címe E-rol, Mivel a gyökér minden egyedet ismer, az algoritmus terminálása garantált Node has no record for E, so that request is forwarded to parent

Look-up request Maarten van Steen, Kitlei Róbert

Node knows about E, so request is forwarded to child M

Domain D Elosztott rendszerek

15 / 30

5.1 Naming Entities




HLS: Beszúrás Beszúrás a fában Ugyanaddig megyünk felfelé a fában, mint keresésnél Az érintett belso˝ csúcsokba mutatókat helyezünk Egy csúcsban egy egyedhez több mutató is tartozhat Node knows about E, so request is no longer forwarded

Node has no record for E, so request is forwarded to parent

Node creates record and stores pointer

M

M Node creates record and stores address

Insert request

Domain D (a)


(b)


16 / 30

5.1 Naming Entities




Névtér Névtér névtér: gyökeres, irányított, élcímkézett gráf, a levelek tartalmazzák a megnevezett egyedeket, a belso˝ csúcsokat katalógusnak vagy könyvtárnak (directory) nevezzük Az egyedhez vezeto˝ út címkéit összeolvasva kapjuk az egyed egy nevét. A ˝ indul, abszolút útvonalnév, ha máshonnan, relatív bejárt út, ha a gyökérbol útvonalnév. Mivel egy egyedhez több út is vezethet, több neve is lehet. Data stored in n1 n2: "elke" n3: "max" n4: "steen" elke n2

home

n0

keys n5

n1 max n3

"/keys" "/home/steen/keys"

steen keys

n4

Leaf node .twmrc

mbox

Directory node


"/home/steen/mbox"


17 / 30

5.1 Naming Entities




Névtér

Attribútumok A csúcsokban (akár a levelekben, akár a belso˝ csúcsokban) különféle attribútumokat is eltárolhatunk. Az egyed típusát Az egyed azonosítóját Az egyed helyét/címét Az egyed más neveit ...



18 / 30

5.1 Naming Entities




Névfeloldás

Gyökér szükséges Kiinduló csúcsra van szükségünk ahhoz, hogy megkezdhessük a névfeloldást. Gyökér megkeresése ˝ függo˝ környezet biztosítja a gyökér elérhetoségét. ˝ A név jellegétol Néhány példa név esetén a hozzá tartozó környezet: www.inf.elte.hu: egy DNS névszerver /home/steen/mbox: a lokális NFS fájlszerver 0031204447784: a telefonos hálózat 157.181.161.79: a www.inf.elte.hu webszerverhez vezeto˝ út



19 / 30

5.1 Naming Entities




Csatolás (linking) Soft link A gráf csúcsai valódi csatolások (hard link), ezek adják a névfeloldás alapját. soft link: a levelek más csúcsok álneveit is tartalmazhatják. Amikor a névfeloldás ilyen csúcshoz ér, az algoritmus az álnév feloldásával folytatódik. Data stored in n1 home

n2: "elke" n3: "max" n4: "steen"

n0

keys n5 "/keys"

n1

elke n2

max n3

steen n4

Data stored in n6

Leaf node .twmrc

mbox

keys

"/keys"

Directory node n6 "/home/steen/keys" Maarten van Steen, Kitlei Róbert


20 / 30

5.1 Naming Entities




A névtér implementációja Nagyméretu˝ névtér tagolása Ha nagy (világméretu) ˝ névterünk van, el kell osztanunk a gráfot a gépek között, hogy hatékonnyá tegyük a névfeloldást és a névtér kezelését. Ilyen nagy névteret alkot a DNS (Domain Name System). Globális szint: Gyökér és felso˝ csúcsok. A szervezetek közösen kezelik. Szervezeti szint: Egy-egy szervezet által kezelt csúcsok szintje. ˝ szint: Egy adott szervezeten belül kezelt csúcsok. Kezeloi Szempont Földrajzi méret Csúcsok száma Keresés ideje Frissítés terjedése Másolatok száma Kliens gyorsítótáraz? Maarten van Steen, Kitlei Róbert

Globális Világméretu˝ Kevés mp. ˝ Ráéros Sok Igen

Szervezeti Vállalati Sok ezredmp. Azonnal Nincs/kevés Igen


˝ Kezeloi Vállalati alegység Rendkívül sok Azonnal Azonnal Nincs Néha 21 / 30

5.1 Naming Entities




A névtér implementációja: DNS

Global layer

com

sun

Administrational layer

eng

edu

yale

cs

ai

eng

gov

mil

org

acm

jack

net

jp

ieee

jill

linda

ac

us

nl

oce

co

keio

nec

cs

csl

vu

cs ftp

www

pc24 robot

pub globe

Managerial layer


Zone


index.txt

22 / 30

5.1 Naming Entities




A névtér implementációja: DNS A DNS egy csúcsában tárolt adatok Legtöbbször az A rekord tartalmát kérdezzük le; a névfeloldáshoz feltétlenül szükséges az NS rekord. ˝ adminisztratív egységként kezelt Egy zóna a DNS-fa egy összefüggo, része, egy (ritkábban több) tartomány (domain) adatait tartalmazza. Rekord neve

Adat jellege

Leírás

A

Gazdagép

A csomópont gazdagépének IP címe

NS

Zóna

A zóna névszervere

SOA

Zóna

A zóna paraméterei

MX

Tartomány

˝ A csomópont levelezoszervere



23 / 30

5.1 Naming Entities




Iteratív névfeloldás ˝ indítjuk. A névfeloldást a gyökér névszerverek egyikétol Az iteratív névfeloldás során a névnek mindig csak egy komponensét oldjuk fel, a megszólított névszerver az ehhez tartozó névszerver címét küldi vissza. 1.

Root name server

2. #,

nl

3. Client's name resolver

4. #, 5. 6. #, 7. 8. #


Name server nl node

#

vu Name server vu node cs Name server cs node ftp Nodes are managed by the same server


24 / 30

5.1 Naming Entities




Rekurzív névfeloldás A rekurzív névfeloldás során a névszerverek egymás közt kommunikálva oldják fel a nevet, a kliensoldali névfeloldóhoz rögtön a válasz érkezik. 1.

Client's name resolver

8. #

Root name server

2.

7. #

Name server nl node

3.

6. #

5. #


Name server vu node

4.

Name server cs node

#


25 / 30

5.1 Naming Entities




Rekurzív névfeloldás: cache-elés

A névszerver ezt kezeli cs vu

Feloldandó cím

Feloldja # #

Átadja lefele —

Fogadja és cache-eli — #

nl

#

# #

(gyökér)

#

# # #



Visszaadja # # # # # # # # # #

26 / 30

5.1 Naming Entities




˝ Névfeloldás: átméretezhetoség ˝ Méret szerinti átméretezhetoség Sok kérést kell kezelni rövid ido˝ alatt ⇒ a globális szint szerverei nagy terhelést kapnának. Csúcsok adatai sok névszerveren A felso˝ két szinten, és sokszor még az alsó szinten is ritkán változik a gráf. Ezért megtehetjük, hogy a legtöbb csúcs adatairól sok névszerveren készítünk másolatot, így a keresést várhatóan sokkal ˝ indítjuk. közelebbrol A keresett adat: az entitás címe A legtöbbször a névfeloldással az entitás címét keressük. A névszerverek nem alkalmasak mozgó entitások címeinek kezelésére, mert azok költözésével gyakran változna a gráf. Maarten van Steen, Kitlei Róbert


27 / 30

5.1 Naming Entities




˝ Névfeloldás: átméretezhetoség ˝ Földrajzi átméretezhetoség A névfeloldásnál a földrajzi távolságokat is figyelembe kell venni. Recursive name resolution R1 I1 I2

Client

Name server nl node R2 Name server vu node

I3 Name server cs node

Iterative name resolution

R3

Long-distance communication

Helyfüggés Ha egy csúcsot egy adott névszerver szolgál ki, akkor földrajzilag oda kell kapcsolódnunk, ha el akarjuk érni a csúcsot. Maarten van Steen, Kitlei Róbert


28 / 30

5.1 Naming Entities




Attribútumalapú nevek Attribútumalapú keresés Az egyedeket sokszor kényelmes lehet a tulajdonságaik (attribútumaik) alapján keresni. Teljes általánosságban: nem hatékony Ha bármilyen kombinációban megadhatunk attribútumértékeket, a kereséshez az összes egyedet érintenünk kell, ami nem hatékony. X.500, LDAP A katalógusszolgáltatásokban (directory service) az attribútumokra megkötések érvényesek. A legismertebb ilyen szabvány az X.500, amelyet az LDAP protokollon keresztül szokás elérni. ˝ Az elnevezési rendszer fastruktúrájú, élei névalkotó jellemzokkel ˝ (attribútum-érték párokkal) címzettek. Az egyedekre az útjuk jellemzoi vonatkoznak, és további párokat is tartalmazhatnak. Maarten van Steen, Kitlei Róbert


29 / 30

5.1 Naming Entities




Példa: LDAP C = NL O = Vrije Universiteit OU = Comp. Sc. CN = Main server N Host_Name = star

Host_Name = zephyr

Attribute

Value

Attribute

Value

Country

NL

Country

NL

Locality

Amsterdam

Locality

Amsterdam

Organization

Vrije Universiteit

Organization

Vrije Universiteit

OrganizationalUnit

Comp. Sc.

OrganizationalUnit

Comp. Sc.

CommonName

Main server

CommonName

Main server

Host_Name

star

Host_Name

zephyr

Host_Address

192.31.231.42

Host_Address

137.37.20.10

answer = search("&(C = NL) (O = Vrije Universiteit) (OU = *) (CN = Main server)") Maarten van Steen, Kitlei Róbert


30 / 30


Kitlei Róbert 2


6. rész: Szinkronizáció 2015. május 24.




2 / 28

Órák szinkronizálása

Logikai órák

Kölcsönös kizárás

Csúcsok pozícionálása

˝ Vezetoválasztás

Fizikai órák ˝ Milyen módon van szükségünk az idore? ˝ szeretnénk tudni, néha elég, ha megállapítható két Néha a pontos idot ˝ ˝ idopont közül, melyik volt korábban. Foglalkozzunk eloször az elso˝ kérdéssel. Egyezményes koordinált világido˝ ˝ ˝ ol ˝ (TAI) származtatjuk. Az idoegységeket (pl. másodperc) az atomidob Az atomido˝ definíciója a gerjesztett céziumatom által kibocsátott sugárzás frekvenciáján alapul. A Föld forgásának sebessége kissé változékony, ezért a világido˝ (UTC) ˝ ˝ ol. ˝ néhány (szöko)másodperccel eltér az atomidot Az atomido˝

kb. 420 atomóra átlagából adódik.

Az atomórák pontosságának nagyságrendje kb. 1ns/nap. ˝ muholdak Az atomidot ˝ sugározzák, a vétel pontossága 0.5 ms ˝ nagyságrendu, ˝ pl. az idojárás befolyásolhatja. Maarten van Steen, Kitlei Róbert


3 / 28


Logikai órák




Fizikai órák Fizikai ido˝ elterjesztése ˝ az megkapja a pontos idot. ˝ Ezt a Ha a rendszerünkben van UTC-vevo, ˝ figyelembe vételével terjeszthetjük el a rendszeren belül. következok ˝ A p gép saját órája szerint az ido˝ t UTC-idopillanatban Cp (t). ˝ Ideális esetben mindig pontos az ido: Cp (t) = t, másképpen dC/dt = 1. ˝ Idoszinkronizáció üteme


ck lo ct c

clo ck

w

Slo

Ha csak megadott δ eltérést akarunk megengedni, δ /(2ρ) másodpercenként ˝ szinkronizálnunk kell az idot. Elosztott rendszerek

dC =1 dt dC <1 ck dt

fe

dC ≤ 1+ρ dt

Pe r

1−ρ ≤

dC >1 dt

Clock time, C Fa st

A valóságban p vagy túl gyors, vagy túl lassú, de viszonylag pontos:

clo

UTC, t 4 / 28


Logikai órák




Óraszinkronizálás Cristian-algoritmus ˝ ˝ kéri le a pontos idot ˝ Mindegyik gép egy központi idoszervert ol legfeljebb δ /(2ρ) másodpercenként (Network Time Protocol). ˝ kell állítani az órát: bele kell számítani, Nem a megkapott idore hogy a szerver kezelte a kérést és a válasznak vissza kellett érkeznie a hálózaton keresztül. Berkeley-algoritmus Itt nem feltétlenül a pontos ido˝ beállítása a cél, csak az, hogy minden gép ideje azonos legyen. ˝ ˝ átlagot von, Az idoszerver néha bekéri mindegyik gép idejét, ebbol majd mindenkit értesít, hogy a saját óráját mennyivel kell átállítania. Az ido˝ egyik gépnél sem folyhat visszafelé: ha vissza kellene állítani valamelyik órát, akkor ehelyett a számontartott ido˝ mérését lelassítja a gép mindaddig, amíg a kívánt ido˝ be nem áll. Maarten van Steen, Kitlei Róbert


5 / 28


Logikai órák




˝ Az elobb-történt reláció ˝ Az elobb-történt (happened-before) reláció ˝ Az elobb-történt reláció az alábbi tulajdonságokkal rendelkezo˝ reláció. ˝ Annak a jelölése, hogy az a esemény elobb-történt-mint b-t: a → b. Ha ugyanabban a folyamatban az a esemény korábban következett be b eseménynél, akkor a → b. Ha a esemény egy üzenet küldése, és b esemény annak fogadása, akkor a → b. A reláció tranzitív: ha a → b és b → c, akkor a → c Parcialitás ˝ A fenti reláció parciális rendezés: elofordulhat, hogy két esemény közül ˝ meg a másikat. egyik sem elozi



6 / 28


Logikai órák




Logikai órák

˝ Az ido˝ és az elobb-történt reláció ˝ Minden e eseményhez idobélyeget rendelünk, ami egy egész szám (jelölése: C(e)), és megköveteljük az alábbi tulajdonságokat. Ha a → b egy folyamat két eseményére, akkor C(a) < C(b). Ha a esemény egy üzenet küldése és b esemény annak fogadása, akkor C(a) < C(b). Globális óra nélkül? ˝ ˝ Ha a rendszerben van globális óra, azzal a fenti idobélyegek elkészíthetok. ˝ A továbbiakban azt vizsgáljuk, hogyan lehet az idobélyegeket globális óra nélkül elkészíteni.



7 / 28


Logikai órák




˝ Logikai órák: Lamport-féle idobélyegek Minden Pi folyamat saját Ci számlálót tart nyilván az alábbiak szerint: Pi minden eseménye eggyel növeli a számlálót. ˝ Az elküldött m üzenetre ráírjuk az idobélyeget: ts(m) = Ci . Ha az m üzenet beérkezik Pj folyamathoz, ott a számláló új értéke Cj = max{Cj , ts(m)} + 1 lesz; így az ido˝ „nem folyik visszafelé”. ˝ ˝ Pi és Pj egybeeso˝ idobélyegei közül tekintsük a Pi -belit elsonek, ha i < j. P1 0 6 12 18 24 30 36 42 48 54 60

m1

m4

P2 0 8 16 24 32 40 48 56 64 72 80

Maarten van Steen, Kitlei Róbert (a)

m2

m3

P3 0 10 20 30 40 50 60 70 80 90 100

P1 0 6 m1 12 18 24 30 P2 adjusts 36 its clock 42 48 m4 70 76 P1 adjusts its clock


P2 0 8 16 24 32 40 48 61 69 77 85 (b)

m2

m3

P3 0 10 20 30 40 50 60 70 80 90 100 8 / 28


Logikai órák




Logikai órák Beállítás: köztesréteg ˝ Az órák állítását és az üzenetek idobélyegeit a köztesréteg kezeli. Application layer

Application sends message

Message is delivered to application

Adjust local clock and timestamp message

Adjust local clock

Middleware sends message

Middleware layer

Message is received

Network layer



9 / 28


Logikai órák




Logikai órák: példa Pontosan sorbarendezett csoportcímzés Ha replikált adatbázison konkurens muveleteket ˝ kell végezni, sokszor követelmény, hogy mindegyik másolaton ugyanolyan sorrendben hajtódjanak végre a muveletek. ˝ Az alábbi példában két másolatunk van, a számlán kezdetben $1000 van. P1 befizet $100-t, P2 1% kamatot helyez el. Update 1

Update 1 is performed before update 2

Update 2

Replicated database

Update 2 is performed before update 1

Probléma ˝ érvénytelen eredményt Ha a muveletek ˝ szinkronizációja nem megfelelo, kapunk: másolat1 ← $1111, de másolat2 ← $1110. Maarten van Steen, Kitlei Róbert


10 / 28


Logikai órák




Példa: Pontosan sorbarendezett csoportcímzés Pontosan sorbarendezett csoportcímzés ˝ A Pi folyamat minden muveletet ˝ idobélyeggel ellátott üzenetben küld el. Pi egyúttal beteszi a küldött üzenetet a saját queuei prioritásos sorába. A Pj folyamat a beérkezo˝ üzeneteket az o˝ queuej sorába teszi be az ˝ ˝ mindegyik idobélyegnek megfelelo˝ prioritással. Az üzenet érkezésérol folyamatot értesíti. Pj akkor adja át a msgi üzenetet feldolgozásra, ha: ˝ (1) msgi a queuej elején található (azaz az o˝ idobélyege a legkisebb) (2) a queuej sorban minden Pk (k 6= i) folyamatnak megtalálható legalább ˝ ˝ egy üzenete, amelynek msgi -nél késobbi az idobélyege Feltételek Feltételezzük, hogy a kommunikáció a folyamatok között megbízható és FIFO sorrendu. ˝ Maarten van Steen, Kitlei Róbert


11 / 28


Logikai órák




˝ Idobélyeg-vektor Okság ˝ hogy az Arra is szükségünk lehet, hogy megállapíthassuk két eseményrol, egyik okoz(hat)ta-e a másikat – illetve fordítva, függetlenek-e egymástól. Az eddigi megközelítésünk erre nem alkalmas: abból, hogy C(a) < C(b), nem ˝ ab vonható le az a következtetés, hogy az a esemény okságilag megelozi eseményt. P1 0 6 12 18 24 30 36 42 48 70 76

m1

m5

P2 0 8 16 24 32 40 48 61 69 77 85


m2 m3

m4

P3 0 10 20 30 40 50 60 70 80 90 100

A példában szereplo˝ adatok a esemény: m1 beérkezett T = 16 ˝ idobélyeggel; b esemény: m2 elindult T = 20 ˝ idobélyeggel. Bár 16 < 20, a és b nem függenek össze okságilag.


12 / 28


Logikai órák




˝ Idobélyeg-vektor ˝ Idobélyeg-vektor A Pi most már az összes másik folyamat idejét is számon tartja egy VCi [1..n] tömbben, ahol VCi [j] azoknak a Pj folyamatban bekövetkezett ˝ Pi tud. eseményeknek a száma, amelyekrol Az m üzenet elküldése során Pi megnöveli eggyel VCi [i] értékét (vagyis az üzenetküldés egy eseménynek számít), és a teljes Vi ˝ idobélyeg-vektort ráírja az üzenetre. Amikor az m üzenet megérkezik a Pj folyamathoz, amelyre a ts(m) ˝ idobélyeg van írva, két dolog történik: (1) VCj [k ] := max{VCj [k ], ts(m)[k ]} (2) VCj [j] megno˝ eggyel, vagyis az üzenet fogadása is egy eseménynek számít



13 / 28


Logikai órák




Pontosan sorbarendezett csoportcímzés ˝ Idobélyeg-vektor alkalmazása ˝ Az idobélyeg-vektorokkal megvalósítható a pontosan sorbarendezett csoportcímzés: csak akkor kézbesítjük az üzeneteket, ha már ˝ mindegyik elozményüket kézbesítettük. ˝ leírt idobélyeg-vektorok ˝ Ehhez annyit változtatunk az elobb muködésén, ˝ hogy amikor Pj fogad egy üzenetet, akkor nem növeljük meg VCj [j] értékét. Pj csak akkor kézbesíti az m üzenetet, amikor: ts(m)[i] = VCj [i] + 1, azaz a Pj folyamatban Pi minden korábbi üzenetét kézbesítettük ˝ ol ˝ jött” ts(m)[k ] ≤ VCj [k ] for k 6= i, azaz az üzenet „nem a jövob



14 / 28


Logikai órák




Pontosan sorbarendezett csoportcímzés

Példa P0

VC0 = (1,0,0)

VC0 = (1,1,0)

m P1

m* VC1 = (1,1,0)

VC2 = (1,1,0)

P2 VC 2= (0,0,0)


VC2 = (1,0,0)


15 / 28


Logikai órák





Kölcsönös kizárás: a feladat ˝ Több folyamat egyszerre szeretne hozzáférni egy adott eroforráshoz. Ezt egyszerre csak egynek engedhetjük meg közülük, különben az ˝ eroforrás helytelen állapotba kerülhet. Megoldásfajták Központi szerver használata. Peer-to-peer rendszeren alapuló teljesen elosztott megoldás. Teljesen elosztott megoldás általános gráfszerkezetre. Teljesen elosztott megoldás (logikai) gyur ˝ uben. ˝



16 / 28


Logikai órák




Kölcsönös kizárás: központosított

0

1

2

0

2

Request

OK

Request

1

0

1

Release OK

No reply 3 Coordinator (a)


Queue is empty

3

2

2

(b)


3

(c)

17 / 28


Logikai órák




Kölcsönös kizárás: decentralizált Kölcsönös kizárás: decentralizált ˝ Tegyük fel, hogy az eroforrás n-szeresen többszörözött, és minden replikátumhoz tartozik egy azt kezelo˝ koordinátor. ˝ ˝ többségi szavazás dönt: legalább Az eroforráshoz való hozzáférésrol m koordinátor engedélye szükséges, ahol m > n/2. Feltesszük, hogy egy esetleges összeomlás után a koordinátor hamar felépül – azonban a kiadott engedélyeket elfelejti. Példa: hatékonyság Tegyük fel, hogy a koordinátorok rendelkezésre állásának valószínusége ˝ 99.9% („három kilences”), 32-szeresen replikált az ˝ eroforrásunk, és a koordinátorok háromnegyedének engedélyére van szükségünk (m = 0.75n). Ekkor annak a valószínusége, ˝ hogy túl sok koordinátor omlik össze, igen alacsony: kevesebb mint 10−40 . Maarten van Steen, Kitlei Róbert


18 / 28


Logikai órák




Kölcsönös kizárás: elosztott Muködési ˝ elv ˝ Ismét többszörözött az eroforrás, amikor a kliens hozzá szeretne férni, ˝ kérést küld mindegyik koordinátornak (idobélyeggel). Választ (hozzáférési engedélyt) akkor kap, ha ˝ a koordinátor nem igényli az eroforást, vagy ˝ ˝ a koordinátor is igényli az eroforrást, de kisebb az idobélyege. Különben a koordinátor (átmenetileg) nem válaszol. Accesses resource

8

0

0

0 8

12

OK

2

1

OK

OK

8 1

12 (a)

12


OK

2

(b)


1

2

Accesses resource

(c)

19 / 28


Logikai órák




Kölcsönös kizárás: zsetongyur ˝ u˝ Essence A folyamatokat logikai gyur ˝ ube ˝ szervezzük (fizikailag lehetnek pl. egy lokális hálózaton). A gyur ˝ uben ˝ egy zsetont küldünk körbe, amelyik folyamat birtokolja, az ˝ férhet hozzá az eroforráshoz. 2 3

1

0

2

4

3

7

1

6

5

0

4

5

7 6 (a)


(b)


20 / 28


Logikai órák




Kölcsönös kizárás: összehasonlítás

Algoritmus

Be+kilépési üzenetszám

˝ Belépés elotti késleltetés ˝ (üzenetidoben)

Problémák

Központosított

3

2

Ha összeomlik a koordinátor

Decentralizált

2mk + m

2mk

Kiéheztetés, rossz hatékonyság

Elosztott

2 (n – 1)

2 (n – 1)

Bármely folyamat összeomlása

Zsetongyur ˝ u˝

1 .. ∞

0 .. n – 1

A zseton elvész, a birtokló folyamat összeomlik



21 / 28


Logikai órák




Csúcsok globális pozícionálása Feladat Meg szeretnénk becsülni a csúcsok közötti kommunikációs költségeket. Erre többek között azért van szükség, hogy hatékonyan tudjuk megválasztani, melyik gépekre helyezzünk replikátumokat az adatainkból. Ábrázolás A csúcsokat egy többdimenziós geometriai térben ábrázoljuk, ahol a P és Q csúcsok közötti kommunikációs költséget a csúcsok távolsága jelöli. Így a feladatot visszavezettük távolságok becslésére. A tér dimenziószáma minél nagyobb, annál pontosabb lesz a becslésünk, de annál költségesebb is.



22 / 28


Logikai órák




A pozíció kiszámítása A becsléshez szükséges csúcsok száma Egy pont pozíciója meghatározható a tér dimenziószámánál eggyel ˝ nagyobb számú másik pontból a tolük vett távolságok alapján.

(x 2 ,y2 ) d2 d1 d3

P

(x 1 ,y1 )

(x 3 ,y3 )



23 / 28


Logikai órák




A pozíció kiszámítása Nehézségek 3.2

a késleltetések mért értékei ingadoznak nem egyszeruen ˝ összeadódnak a távolságok −→

1.0

1 P

2.0

2 Q

3

4 R

Megoldás Válasszunk L darab csúcsot, amelyek pozícióját tegyük fel, hogy nagyon pontosan meghatároztuk. ˝ Egy P csúcsot ezekhez viszonyítva helyezünk el: megmérjük az összestol mért késleltetését, majd úgy választjuk meg P pozícióját, hogy az össz-hiba (a mért késleltetések és a megválasztott pozícióból geometriailag adódó késleltetés eltérése) a legkisebb legyen.



24 / 28


Logikai órák




˝ Vezetoválasztás: zsarnok-algoritmus ˝ Vezetoválasztás: feladat Sok algoritmusnak szüksége van arra, hogy kijelöljön egy folyamatot, amely aztán a további lépéseket koordinálja. Ezt a folyamatot dinamikusan szeretnénk kiválasztani. Zsarnok-algoritmus A folyamatoknak sorszámot adunk. A legnagyobb sorszámú folyamatot ˝ szeretnénk vezetonek választani. ˝ Bármelyik folyamat kezdeményezhet vezetoválasztást. Mindegyik ˝ nem ismert, hogy kisebb lenne a küldonél ˝ folyamatnak (amelyrol a sorszáma) elküld egy választási üzenetet. ˝ visszaküld neki egy olyan Ha Pnagyobb üzenetet kap Pkisebb -tol, üzenetet, amellyel kiveszi Pkisebb -et a választásból. ˝ belül nem kap letiltó üzenetet, o˝ lesz a Ha P megadott idon ˝ Errol ˝ mindegyik másik folyamatot értesíti egy üzenettel. vezeto. Maarten van Steen, Kitlei Róbert


25 / 28


Logikai órák




Zsarnok-algoritmus 1

1 5

ion lect

5

2

OK

Election

6

Election

OK

4

6

Ele ctio n

E

4

1 5

2

4

n

El

ec t

tio ec El 0

6 io n

2

3

3

0

3

0

7

7

7

(a)

Previous coordinator has crashed (b)

(c)

1

1

5

2

5

2

OK 6

4

3

0


Coordinator

4

3

0

7

7

(d)

(e)


6

26 / 28


Logikai órák




˝ Vezetoválasztás gyur ˝ uben ˝ ˝ Vezetoválasztás gyur ˝ uben ˝ Ismét logikai gyur ˝ unk ˝ van, és a folyamatoknak vannak sorszámai. A ˝ legnagyobb sorszámú folyamatot szeretnénk vezetonek választani. ˝ Bármelyik folyamat kezdeményezhet vezetoválasztást: elindít egy üzenetet a gyur ˝ un ˝ körbe, amelyre mindenki ráírja a sorszámát. Ha egy ˝ folyamat összeomlott, az kimarad az üzenetküldés menetébol. ˝ Amikor az üzenet visszajut a kezdeményezohöz, minden aktív folyamat ˝ ezt sorszáma szerepel rajta. Ezek közül a legnagyobb lesz a vezeto; egy másik üzenet körbeküldése tudatja mindenkivel. Nem okozhat problémát, ha több folyamat is egyszerre kezdeményez választást, mert ugyanaz az eredmény adódik. Ha pedig az üzenetek ˝ valahol elvesznének (összeomlik az éppen oket tároló folyamat), akkor újrakezdheto˝ a választás. Maarten van Steen, Kitlei Róbert


27 / 28


Logikai órák




Superpeer-választás Szempontok A superpeer-eket úgy szeretnénk megválasztani, hogy teljesüljön rájuk: ˝ A többi csúcs alacsony késleltetéssel éri el oket Egyenletesen vannak elosztva a hálózaton A csúcsok megadott hányadát választjuk superpeer-nek Egy superpeer korlátozott számú peer-t szolgál ki Megvalósítás DHT használata esetén Az azonosítók terének egy részét fenntartjuk a superpeer-ek számára. Példa: ha m-bites azonosítókat használunk, és S superpeer-re van szükségünk, a k = dlog2 Se felso˝ bitet foglaljuk le a superpeer-ek számára. Így N csúcs esetén kb. 2k −m N darab superpeer lesz. ˝ az. A p kulcshoz tartozó superpeer: a p AND 11 · · 11} 00 · · 00} kulcs felelose | ·{z | ·{z k



m−k

28 / 28


Kitlei Róbert 2


7. rész: Konzisztencia & replikáció 2015. május 24.




2 / 27

7.2. Adatközpontú

7.3. Kliensközpontú

7.4 Replikátumok elhelyezése

7.5 Konzisztenciaprotokollok

˝ Hatékonyság és átméretezhetoség Konfliktusos muveletek ˝ A replikátumok konzisztensen tartásához garantálni kell, hogy az egymással konfliktusba kerül(het)o˝ muveletek ˝ minden replikátumon egyforma sorrendben futnak le. Ahogy a tranzakcióknál, írás–olvasás és írás–írás konfliktusok fordulhatnak ˝ elo. Terv: kevesebb szinkronizáció Az összes konfliktusos muvelet ˝ globális sorbarendezése általában túl költséges. Megvizsgáljuk, hogyan lehet a konzisztenciakövetelményeket gyengíteni. ˝ ˝ Jellemzoen minél megengedobbek a feltételek, annál kevesebb szinkronizáció szükséges a biztosításukhoz.



3 / 27

7.2. Adatközpontú




Adatközpontú konzisztencia Konzisztenciamodell A konzisztenciamodell megszabja, milyen módokon használhatják a ˝ folyamatok az adatbázist. Elosztott adattár (lásd az ábrát) esetén legfoképpen ˝ az egyideju˝ írási és olvasási muveletekre ˝ ad eloírásokat. Ha a feltételek teljesülnek, az adattárat érvényesnek tekintjük. Process

Process

Process

Local copy

Distributed data store



4 / 27

7.2. Adatközpontú




Folyamatos konzisztencia Konzisztencia mértéke A konzisztencia több módon is sérülhet: eltérhet a replikátumok számértéke eltérhet, hogy mennyire frissek az egyes replikátumok eltérhet, hogy hány frissítési muvelet ˝ nem történt még meg (illetve: sorrendben melyik muveletek ˝ hiányoznak) Conit Ha megtehetjük, a konzisztenciafeltéleket nem a teljes adatbázisra írjuk fel, hanem az adatoknak minél szukebb ˝ körére. Az olyan adategység, amelyre közös feltételrendszer vonatkozik, a conit (consistency unit).



5 / 27

7.2. Adatközpontú




Példa: Conit Replica A

Replica B

Conit

Conit

x = 6; y = 3 Operation

x = 2; y = 5 Result

Operation

Result

< 5, B> x := x + 2

[x=2]

< 5, B> x := x + 2

[x=2]

< 8, A> y := y + 2

[y=2]

<10, B> y := y + 5

[y=5]

<12, A> y := y + 1

[y=3]

<14, A> x := y * 2

[x=6]

Vector clock A = (15, 5) Order deviation =3 Numerical deviation = (1, 5)

Vector clock B = (0, 11) Order deviation =2 Numerical deviation = (3, 6)

Conit (most az x és y változó alkotja) ˝ B-beli ido) ˝ Mindkét replikátumnak van vektorórája: (A-beli ido, B elküldi A-nak a [h5, Bi: x := x + 2] muveletet ˝ A véglegesíti a kijött eredményt (nem vonható vissza) Maarten van Steen, Kitlei Róbert


6 / 27

7.2. Adatközpontú




Példa: Conit Replica A

Replica B

Conit

Conit

x = 6; y = 3 Operation

x = 2; y = 5 Result

Operation

Result

< 5, B> x := x + 2

[x=2]

< 5, B> x := x + 2

[x=2]

< 8, A> y := y + 2

[y=2]

<10, B> y := y + 5

[y=5]

<12, A> y := y + 1

[y=3]

<14, A> x := y * 2

[x=6]

Vector clock A = (15, 5) Order deviation =3 Numerical deviation = (1, 5)

Vector clock B = (0, 11) Order deviation =2 Numerical deviation = (3, 6)

Conit (most az x és y változó alkotja) A három muveletet ˝ nem végzett még el A-ban egy B-beli muvelet ˝ még nem hajtódott végre, a számérték legfeljebb 5-tel térhet el ⇒ (1, 5) Maarten van Steen, Kitlei Róbert


7 / 27

7.2. Adatközpontú




Soros konzisztencia Jelölések Sokszor a feltételeket nem a számértékekre alapozzuk, hanem csupán az írások/olvasások tényére. Jelölje W(x) azt, hogy az x változót írta egy megadott folyamat, R(x) azt, hogy olvasta, a mellettük levo˝ betuk ˝ pedig azt jelölik, hogy az olvasás melyik írással írt értéket látja. Soros konzisztencia Soros konzisztencia esetén azt várjuk el, hogy a végrehajtás eredménye olyan legyen, mintha az összes folyamat összes muvelete ˝ ˝ egy meghatározott sorrendben történt volna meg, megorizve bármely adott folyamat saját muveleteinek ˝ sorrendjét. (a) teljesíti, (b) nem P1: W(x)a P2: W(x)b P3: P4:

R(x)b

R(x)a R(x)b R(x)a

P1: W(x)a W(x)b P2: P3: R(x)a R(x)b R(x)a R(x)b P4:

(a) Maarten van Steen, Kitlei Róbert


8 / 27

7.2. Adatközpontú




Okozati konzisztencia Okozati konzisztencia A potenciálisan okozatilag összefüggo˝ muveleteket ˝ kell mindegyik folyamatnak azonos sorrendben látnia. A konkurens írásokat különbözo˝ folyamatok különbözo˝ sorrendben láthatják. (b) teljesíti; (a) nem, mert ott P1 és P2 írásait „összeköti” az olvasás P1: W(x)a P2: P3: P4:

R(x)a

W(x)b R(x)b R(x)a

R(x)a R(x)b

R(x)b R(x)a

R(x)a R(x)b

(a)

P1: W(x)a P2: P3: P4:

W(x)b

(b) Maarten van Steen, Kitlei Róbert


9 / 27

7.2. Adatközpontú




Muveletek ˝ csoportosítása Szinkronizáció Most szinkronizációs változókat használunk, ezek elérései sorosan konzisztensek. Háromfajta megközelítés: Egy rendszerszintu˝ S változó használata. S egy elérése után ˝ írások megtörténtek. garantált, hogy a korábbi elérései elotti Igényeljük (acquire) és aztán feloldjuk (release) a változókat, ezzel kritikus területeket (más néven: védett területeket) alakítunk ki. Több rendszerszintu˝ szinkronizációs változó használata. A védelem a területen írt/olvasott adatokra terjed ki. Minden adatelemhez külön változó használata. A védelem a változó adatelemére terjed ki.

Ha a fenti szinkronizációs határokon belül több írás is történik, a határon belül ezek nem definiált sorrendben látszanak, és a szinkronizáció után csak a végeredmény látszik, az nem, hogy milyen sorrendben történtek az írások. Maarten van Steen, Kitlei Róbert


10 / 27

7.2. Adatközpontú




Kliensközpontú konzisztencia Cél ˝ Azt helyezzük most elotérbe, hogy a szervereken tárolt adatok hogyan látszanak egy adott kliens számára. A kliens mozog: különbözo˝ szerverekhez csatlakozik, és írási/olvasási muveleteket ˝ hajt végre. Az A szerver után a B szerverhez csatlakozva különbözo˝ problémák léphetnek fel: az A-ra feltöltött frissítések lehet, hogy még nem jutottak el B-hez B-n lehet, hogy újabb adatok találhatóak meg, mint A-n a B-re feltöltött frissítések ütközhetnek az A-ra feltöltöttekkel Cél: a kliens azokat az adatokat, amelyeket az A szerveren kezelt, ugyanolyan állapotban lássa B-n. Ekkor az adatbázis konzisztensnek látszik a kliens számára. Négyfajta kombináció: a kliens A-n (olvasott/írt) adatokat (olvas/ír) B-n. Maarten van Steen, Kitlei Róbert


11 / 27

7.2. Adatközpontú




Kliensközpontú konzisztencia Client moves to other location and (transparently) connects to other replica

Replicas need to maintain client-centric consistency

Wide-area network

Distributed and replicated database Portable computer


Read and write operations


12 / 27

7.2. Adatközpontú




Kliensközpontú konzisztencia: olvasás után olvasás Jelölések WS(xi ): írási muveletek ˝ összessége (write set) az x változóra WS(xi ; xj ): olyan WS(xj ), amely tartalmazza WS(xi ) frissítéseit Monoton olvasás (olvasás után olvasás) ˝ minden ezután Ha egyszer a kliens kiolvasott egy értéket x-bol, következo˝ olvasás ezt adja, vagy ennél frissebb értéket. L1: WS( x 1) L2:

L2:

R( x 2)

WS( x 1;x 2)

L1: WS( x 1)

˝ Példa: határidonapló

R( x 1)

R( x 1)

WS( x 2)


R( x 2)

Minden korábbi bejegyzésünknek meg kell lennie az új szerveren is. ˝ Példa: levelezokliens Minden korábban letöltött levelünknek meg kell lennie az új szerveren is.


13 / 27

7.2. Adatközpontú




Kliensközpontú konzisztencia: írás után írás Monoton írás (írás után írás) A kliens csak akkor írhatja x-et, ha a kliens korábbi írásai x-re már ˝ befejezodtek.

L1: L2:

L1:

W( x 1) WS( x 1)

W(x 2 )

W( x 1)

L2:


W(x 2 )

Példa: forráskód A kliens egy programot szerkeszt több szerveren. Minden korábbi szerkesztésnek jelen kell lennie, mert ˝ az újonnan írt kód függ tolük. Példa: verziókezelés A kliens verziószámokkal ellátott fájlokat készít. Minden korábbi verziónak meg kell lennie ahhoz, hogy újat készíthessen.


14 / 27

7.2. Adatközpontú




Kliensközpontú konzisztencia: írás után olvasás

Olvasd az írásodat (írás után olvasás) Ha a kliens olvassa x-et, a saját legutolsó írásának eredményét kapja (vagy frissebbet). L1: L2:

L1: L2:

Példa: honlap szerkesztése

W( x 1) WS( x 1;x 2)

R( x 2)

W( x 1) WS( x 2)


R( x 2)

A kliens a honlapját szerkeszti, majd megnézi a szerkesztés eredményét. Ahelyett, hogy a böngészo˝ gyorsítótárából egy régebbi verzió ˝ a legfrissebb változatot kerülne elo, szeretné látni.


15 / 27

7.2. Adatközpontú




Kliensközpontú konzisztencia: olvasás után írás

Írás olvasás után (olvasás után írás) ˝ minden ezután kiadott frissítési Ha a kliens kiolvasott egy értéket x-bol, muvelete ˝ x legalább ennyire friss értékét módosítja. L1: WS( x 1) L2:

WS( x 1;x 2)

L1: WS( x 1) L2:

R( x 1) W( x 2)

R( x 1)

WS( x 2)


Példa: fórum A kliens csak olyan hírre tud választ beküldeni, amelyet már látott.

W( x 3)


16 / 27

7.2. Adatközpontú




Replikátumszerverek elhelyezése Tegyük fel, hogy N lehetséges helyre szeretnénk összesen K darab szervert telepíteni. Melyik helyeket válasszuk? Tegyük fel, hogy ismert a kliensek helye. Válasszuk meg úgy a ˝ minimális szervereket, hogy azok átlagtávolsága a kliensektol legyen. Egzakt kiszámítása költséges, heurisztika szükséges. ˝ Jellemzoen a kliensek több autonóm rendszerbena találhatóak meg. A K legnagyobb rendszerben helyezzünk el egy-egy szervert, mindig a rendszeren belül leginkább központi helyre. Szintén magas a számítási költsége. Mint korábban a csúcsok globális pozícionálásánál, ábrázoljuk a csúcsokat egy d-dimenziós térben, ahol a távolság mutatja a késleltetést. Keressük meg a K „legsur ˝ ubb” ˝ részt, és oda helyezzünk szervereket. Számítási költsége alacsonyabb. aA

teljes hálózat útválasztás szempontjából egységként adminisztrált része, gyakran egy Internet-szolgáltató (ISP) felügyeli. Maarten van Steen, Kitlei Róbert


17 / 27

7.2. Adatközpontú




Tartalom replikálása Különbözo˝ jellegu˝ folyamatok tárolhatják az adatokat: Tartós másolat: a folyamat mindig rendelkezik másolattal: eredetszerver (origin server) Szerver által kezdeményezett másolat: replikátum kihelyezése egy szerverre, amikor az igényli az adatot Kliens által kezdeményezett másolat: kliensoldali gyorsítótár

Server-initiated replication Client-initiated replication Permanent replicas Server-initiated replicas Client-initiated replicas Clients



18 / 27

7.2. Adatközpontú




Szerver által kezdeményezett másolatok C2 Server without copy of file F

P Client

Q

C1

Server with copy of F File F

Server Q counts access from C1 and C2 as if they would come from P

A rendszer figyeli, hányszor fértek hozzá a fájlhoz (A), úgy számolva, mintha a kérés a klienshez legközelebbi szerverhez (P) érkezett volna be. Adott két szám, D és R, melyekre D < R. Mit tegyünk a fájllal? Ha A < D ⇒ töröljük Q-ról (ha megvan máshol a rendszerben) Ha D < A < R ⇒ migráljuk Q-ról P-re Ha R < A ⇒ replikáljuk P-re Maarten van Steen, Kitlei Róbert


19 / 27

7.2. Adatközpontú




Frissítés terjesztése Modellek Megváltozott tartalmat több különbözo˝ módon lehet szerver-kliens architektúrában átadni: ˝ szóló értesítés/érvénytelenítés Kizárólag a frissítésrol ˝ elterjesztése (pl. gyorsítótáraknál ez egy egyszeru˝ lehetoség) Passzív replikáció: adatok átvitele egyik másolatról a másikra Aktív replikáció: frissítési muvelet ˝ átvitele Melyiket érdemes választani? A sávszélesség és az írási/olvasási muveletek ˝ aránya a replikátumon nagyban befolyásolja, melyik módszer a leghatékonyabb adott esetben.



20 / 27

7.2. Adatközpontú




Frissítés terjesztése

Küldésalapú: a szerver a kliens kérése nélkül küldi a frissítést Rendelésalapú: a kliens kérvényezi a frissítést Témakör

Küldésalapú

Rendelésalapú

Kezdeményezo˝

Szerver

Kliens

Szerverállapot

Klienscache-ek listája

Nincsen

Küldött üzenetek Válaszido˝ a kliensnél

Frissítés*

Lekérdezés és frissítés Letölto˝ frissítés ideje

Azonnali*

˝ még alkalmazhat letölto˝ frissítést (fetch update). *: A kliens késobb



21 / 27

7.2. Adatközpontú




Frissítés terjesztése Haszonbérlet Haszonbérlet (lease): a szerver ígéretet tesz a kliensnek, hogy át elküldi neki a frissítéseket, amíg a haszonbérlet aktív Rugalmas haszonbérlet Fix lejárat helyett rugalmasabb, ha a rendszer állapotától függhet a ˝ haszonbérlet idotartama: Kor szerinti: minél régebben változott egy objektum, annál valószínubb, ˝ hogy sokáig változatlan is marad, ezért hosszabb lejárat adható Igénylés gyakorisága szerinti: minél gyakrabban igényli a kliens az ˝ objektumot, annál hosszabb idotartamokra kap haszonbérletet rá Terhelés szerinti: minél nagyobb a szerver terhelése, annál rövidebb haszonbérleteket ad ki Maarten van Steen, Kitlei Róbert


22 / 27

7.2. Adatközpontú




Folyamatos konzisztencia: számszeru˝ eltérések Alapelv Az egyszeruség ˝ kedvéért most egyetlen adatelemet vizsgálunk. Az Si szerver a log(Si ) naplóba írja az általa végrehajtott muveleteket. ˝ ˝ A W írási muveletet ˝ elsoként végrehajtó szervert jelölje origin(W ), a muvelet ˝ hatására bekövetkezo˝ értékváltozást pedig weight(W ). Tegyük fel, hogy ez mindig pozitív szám. ˝ származnak, jelölje TW [i, j]: Si olyan írásait, amelyek Sj -rol TW [i, j] = ∑ weight(W ) origin(W ) = Sj & W ∈ log(Si ) Ekkor a változó összértéke (v) és értéke az i-edik másolaton (vi ): v = vkezdeti + ∑ TW [k , k ] k


vi = vkezdeti + ∑ TW [i, k ]


k

23 / 27

7.2. Adatközpontú




Folyamatos konzisztencia: számszeru˝ eltérések Cél: minden Si szerveren teljesüljön: v − vi < δi (rögzített δi értékre). Algoritmus TW [i, j] értékét minden Sk szerver becsülje egy TWk [i, j] értékkel. ˝ (Azaz: Sk „mit tud”, Si milyen frissítéseket kapott már meg Sj -tol.) Mivel a számértékeink nemnegatívak, fennáll: 0 ≤ TWk [i, j] ≤ TW [i, j] ≤ TW [j, j] = TWj [j, j] Amikor új frissítési muvelet ˝ érkezik be egy szerverre, pletykálással ˝ a többi szervert. értesíti errol ˝ a, Amikor Sj azt látja, hogy TWj [i, j] túl messzire kerül TW [j, j]-tol akkor küldje el Si -nek log(Sj ) muveleteit. ˝ a TW [j, j] − TW

j [i, j] > δi /(N − 1),


ahol N a replikátumok száma Elosztott rendszerek

24 / 27

7.2. Adatközpontú




˝ Elsodleges másolaton alapuló protokoll távoli írással Client

Client Primary server for item x

W1

Backup server

W5

R1 W4

W4

W3

W3

W2

R2

Data store W3

W4

W1. Write request W2. Forward request to primary W3. Tell backups to update W4. Acknowledge update W5. Acknowledge write completed

R1. Read request R2. Response to read

Példa: nagy hibaturést ˝ igénylo˝ elosztott adatbázisokban és fájlrendszerekben használatos. A másolatok gyakran egy lokális hálózatra kerülnek. Maarten van Steen, Kitlei Róbert


25 / 27

7.2. Adatközpontú




˝ Elsodleges másolaton alapuló protokoll helyi írással Client

Client Old primary for item x

R1

New primary for item x

R2

W1

Backup server W3

W5

W5

W4 W5

W4

W4

Data store

W2

W1. Write request W2. Move item x to new primary W3. Acknowledge write completed W4. Tell backups to update W5. Acknowledge update

R1. Read request R2. Response to read

˝ Példa: kapcsolat nélküli munka, idonként szinkronizálás a rendszerrel annak különbözo˝ pontjaihoz csatlakozva. Maarten van Steen, Kitlei Róbert


26 / 27

7.2. Adatközpontú




Többszörözöttírás-protokoll Testületalapú protokoll Többszörözött írás: az írási muveletet ˝ több szerveren hajtjuk végre. ˝ meghatározott Testület (quorum): egy muvelet ˝ végrehajtása elott ˝ kell engedélyt kérni. Jelölés: írási NW , olvasási NR . számú szervertol Egy írási muvelet ˝ ütközhetne egy olvasási muvelettel, ˝ vagy egy másik írásival; az elso˝ elkerüléséhez NR + NW > N, a másodikhoz NW + NW > N, azaz NW > N/2 szükséges a skatulya-elv alapján. Read quorum A

B

C

D

A

B

C

D

A

B

C

D

E

F

G

H

E

F

G

H

E

F

G

H

I

J

K

L

I

J

K

L

I

J

K

L

NR = 3,

N W = 10

NR = 7,

NW = 6

NR = 1,

N W = 12

W Maarten van Steen, Kitlei Róbert


27 / 27


Kitlei Róbert 2


8. rész: Hibaturés ˝ 2015. május 24.




2 / 34

Bevezetés

Hibaturés ˝

Kommunikáció

Csoportkommunikáció

Véglegesítés

Felépülés

Megbízhatóság Alapok A komponensek feladata, hogy a kliensek számára szolgáltatásokat ˝ tesz elérhetové. Ehhez sokszor maga is szolgáltatásokat vesz igénybe ˝ ⇒ függ tolük. ˝ más komponensektol ˝ A függéseket most foleg abból a szempontból vizsgáljuk, hogy a hivatkozott komponensek helyessége kihat a hivatkozó helyességére.

˝ Elérhetoség Megbízhatóság Biztonságosság Karbantarthatóság


A komponens reagál a megkeresésre A komponens biztosítja a szolgáltatást A komponens ritkán romlik el Az elromlott komponens könnyen javítható


3 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Terminológia Hasonló nevu, ˝ de különbözo˝ fogalmak ˝ elvártaknak megfeleloen ˝ Hibajelenség (failure): a komponens nem a tole üzemel Hiba (error): olyan rendszerállapot, amely hibajelenséghez vezethet Hibaok (fault): a hiba (feltételezett) oka Hibákkal kapcsolatos tennivalók ˝ Megelozés Hibaturés: ˝ a komponens legyen képes elfedni a hibákat Mérséklés: lehet mérsékelni a hibák kiterjedését, számát, súlyosságát ˝ ˝ becsülheto˝ lehet a hibák száma, jövobeli ˝ ˝ Elorejelzés: elore elofordulása, következményei



4 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Lehetséges hibaokok Lehetséges hibaokok A hibáknak sok oka lehet, többek között az alábbiak. ˝ Összeomlás (crash): a komponens leáll, de elotte helyesen muködik ˝ Kiesés (omission): a komponens nem válaszol ˝ ˝ Idozítési hiba (timing): a komponens helyes választ küld, de túl késon (ennek teljesítménnyel kapcsolatos oka lehet: a komponens túl lassú) Válaszhiba (response): a komponens hibás választ küld Értékhiba: a válaszként küldött érték rossz Állapotátmeneti hiba: a komponens helytelen állapotba kerül Váratlan hiba (arbitrary): véletlenszeru˝ válaszok, gyakran véletlenszeru˝ ˝ idozítéssel



5 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Összeomlás Probléma A kliens számára nem különböztetheto˝ meg, hogy a szerver összeomlott vagy csak lassú. ˝ adatot vár, de nem érkezik, annak oka lehet... Ha a kliens a szervertol ˝ idozítési vagy kieséses hiba a szerveren. a szerver és a kliens közötti kommunikációs csatorna meghibásodása. Lehetséges feltételezések Fail-silent: a komponens összeomlott vagy kiesett egy válasz; a kliensek ˝ nem tudják megkülönböztetni a kettot Fail-stop: a komponens hibajelenségeket produkál, de ezek ˝ (a komponens közzéteszi, vagy idotúllépésb ˝ ˝ szurjük felismerhetoek ol ˝ le) Fail-safe: a komponens csak olyan hibajelenségeket produkál, amelyek nem okoznak (nagy) kárt Maarten van Steen, Kitlei Róbert


6 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Folyamatok hibaturése ˝ Cél Próbáljuk meg a hibákat redundanciával elfedni. Egyenlo˝ csoport: Jó hibaturést ˝ biztosít, mert a csoport tagjai között közvetlen az információcsere. A nagymértéku˝ többszörözöttség azonban megnehezíti az implementálást (a vezérlés teljesen elosztott). Hierarchikus csoport: Két fél csak a koordinátoron keresztül képes kommunikálni egymással. Rossz a hibaturése ˝ és a skálázhatósága, de könnyu˝ implementálni. Flat group

Hierarchical group

Coordinator

Worker

(a)


(b)


7 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Csoporttagság kezelése

˝ Egy koordinátor kezeli a csoportot (vagy csoportokat). Csoportkezelo: Rosszul skálázódik. ˝ csoportja: A csoportkezelo˝ nem egyetlen szerver, Csoportkezelok hanem egy csoportjuk közösen. Ezt a csoportot is kezelni kell, de ezek a szerverek általában elég stabilak, így ez nem probléma: ˝ centralizált csoportkezelés elegendo. ˝ Csoportkezelo˝ nélkül: A belépo/kilép o˝ folyamat minden csoporttagnak üzenetet küld.



8 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Hibaelfedés csoportokban k-hibatur ˝ o˝ csoport k-hibatur ˝ o˝ csoport: olyan csoport, amely képes elfedni k tag egyszerre történo˝ meghibásodását. Mekkorának kell a csoportnak lennie? Ha a meghibásodottak összeomlanak, csak az szükséges, hogy legyen megmaradó tag ⇒ k + 1 tag Ha minden csoporttag egyformán muködik, ˝ de a meghibásodottak rossz eredményt adnak ⇒ 2k + 1 tag esetén többségi szavazással megkapjuk a helyes eredményt ˝ Ha a csoporttagok különbözoen muködnek, ˝ és mindegyikük kimenetét el kell juttatni mindenki másnak („bizánci generálisok”) ⇒ 3k + 1 tag esetén a „lojális” szerverek képesek megfelelo˝ adatokat továbbítani k „áruló” jelenlétében is Maarten van Steen, Kitlei Róbert


9 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Hibaelfedés csoportokban Az áruló folyamatok többféleképpen is tudnak helytelen adatokat továbbítani. Process 2 tells different things

Process 3 passes a different value

2 a 1

2 a

b b

3

˝ Eloször mindenki elküldi a saját értékét, majd minden beérkezett értéket ismét továbbítanak.

a

1

3

b

(a)

Az alábbi két ábra illusztrálja k = 1 esetben, hogy k áruló esetén ˝ de 3k 3k + 1 folyamat elegendo, még nem.

(b)

2 1

2 1

1 1

2 x 2

3

4

1

y

x

1

1

2

4

2

4

2 y

3

(a)

Faulty process

4 z

Faulty process

(a) 1 Got(1, 2, x ) 2 Got(1, 2, y ) 3 Got(1, 2, 3 )

1 Got (1, 2, y ) (a, b, c )

(b)


2 Got (1, 2, x ) (d, e, f )

1 2 3 4

(c)


Got(1, 2, x, 4 ) Got(1, 2, y, 4 ) Got(1, 2, 3, 4 ) Got(1, 2, z, 4 )

(b)

1 Got (1, 2, y, 4 ) (a, b, c, d ) (1, 2, z, 4 )

2 Got (1, 2, x, 4 ) (e, f, g, h ) (1, 2, z, 4 )

(c)

4 Got (1, 2, x, 4 ) (1, 2, y, 4 ) ( i, j, k, l )

10 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Hibaelfedés csoportokban Folyamatok: Késleltetések: Rendezettség: Átvitel:

Szinkron: a folyamatok azonos ütemben lépnek-e (lockstep)? A kommunikációs késleltetésekre van-e felso˝ korlát? Az üzeneteket a feladás sorrendjében kézbesítik-e? Az üzeneteket egyenként küldjük (unicast) vagy többcímuen ˝ (multicast)?

Egyezség elérése ˝ hogy kialakuljon Néhány feltételrendszer, amely fennállásával elérheto, a közös végeredmény: Ha a ütemezés szinkron és a késleltetés korlátozott. Ha az üzeneteket sorrendtartó módon, többcímuen ˝ továbbítjuk. Ha az ütemezés szinkron és a kommunikáció sorrendtartó. Maarten van Steen, Kitlei Róbert


11 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Hibák észlelése

˝ Idotúllépés ˝ Idotúllépés észlelése esetén feltételezhetjük, hogy hiba lépett fel. ˝ ˝ és nagyon nehéz Az idokorlátok megadása alkalmazásfüggo, A folyamatok hibázása nem megkülönböztetheto˝ a hálózati hibáktól A hibákról értesíteni kell a rendszer többi részét is Pletykálással elküldjük a hiba észlelésének tényét A hibajelenséget észlelo˝ komponens maga is hibaállapotba megy át



12 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható kommunikáció Csatornák A folyamatok megbízhatóságát azok csoportokba szervezésével tudtuk ˝ növelni. Mit lehet mondani az oket összeköto˝ kommunikációs csatornák biztonságosságáról? Hibajelenségek észlelése ˝ o˝ összegekkel látjuk el (felfedi a bithibákat) A csomagokat ellenorz A csomagokat sorszámmal látjuk el (felfedi a kieséseket) Hibajavítás A rendszer legyen annyira redundáns, hogy automatikusan meg lehessen javítani Kérhetjük a meghibásodott/elveszett utolsó N csomag újraküldését Maarten van Steen, Kitlei Róbert


13 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható RPC RPC: Fellépo˝ hibajelenségek és azok kezelése 1: A kliens nem találja a szervert. Ezt egyszeruen ˝ ki lehet jelezni a kliensnél. 2: A kliens kérése elveszett. A kliens újraküldi a kérést. 3: A szerver összeomlott. Ezt nehezebb kezelni, mert a kliens nem tudja, hogy a szerver mennyire dolgozta fel a kérést. REQ

REP

Server Receive Execute Reply (a)

REQ

No REP

Server Receive Execute Crash

REQ

No REP

(b)

Server Receive Crash

(c)

El kell dönteni, hogy milyen módon muködjön ˝ a szerver. „Legalább egyszer” szemantika szerint: A szerver az adott kérést legalább egyszer végrehajtja (de lehet, hogy többször is). „Legfeljebb egyszer” szemantika szerint: A szerver az adott kérést legfeljebb egyszer hajtja végre (de lehet, hogy egyszer sem). Maarten van Steen, Kitlei Róbert


14 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható RPC RPC: Fellépo˝ hibajelenségek és azok kezelése 4: Elveszett a szerver válasza. Nehéz felismerni, mert a szerver ˝ Nincsen általános összeomlása is hasonló a kliens szemszögébol. megoldás; ha idempotens muveleteink ˝ vannak (többszöri végrehajtás ugyanazt az eredményt adja), megpróbálhatjuk újra ˝ végrehajtani oket. 5: Összeomlik a kliens. Ilyenkor a szerver feleslegesen foglalja az ˝ eroforrásokat: árvaa feladatok keletkeznek. A kliens felépülése után az árva feladatokat szükség szerint leállítja/visszagörgeti a szerver. ˝ A kliens felépülése után új korszak kezdodik: a szerver leállítja az árva feladatokat. ˝ A feladatokra idokorlát adott. A túl sokáig futó feladatokat a szerver leállítja. a Más

fordításban: fattyú.



15 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható csoportcímzés Adott egy többcímu˝ átviteli csatorna; egyes folyamatok üzeneteket küldenek rá és/vagy fogadnak róla. Megbízhatóság: Ha m üzenet csatornára küldésekor egy folyamat a fogadók közé tartozik, és köztük is marad, akkor m üzenetet kézbesíteni kell a folyamathoz. Sokszor a sorrendtartás is követelmény. Atomi csoportcímzés: Cél: elérni azt, hogy csak akkor kézbesítsük az ˝ üzenetet, ha garantáltan mindegyik fogadónak kézbesítheto. Egyszeru˝ megoldás lokális hálózaton A küldo˝ számon tartja az elküldött üzeneteket. Minden fogadó nyugtázza (ACK) az üzenet fogadását, vagy kéri az üzenet újraküldését (NACK), ha észreveszi, hogy elveszett. Ha minden fogadótól megérkezett a nyugta, a ˝ küldo˝ törli az üzenetet a történetbol. Ez a megoldás nem jól skálázódik: ˝ Ha sok a fogadó, a küldohöz túl sok ACK és NACK érkezik. ˝ A küldonek minden fogadót ismernie kell. Maarten van Steen, Kitlei Róbert


16 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható csoportcímzés: visszajelzés-elfojtás Hagyjuk el az ACK üzeneteket, csak a kimaradó üzenetek esetén küldjenek a fogadók NACK üzeneteket. Tegyük fel, hogy a NACK ˝ üzenetek közös csatornán utaznak, és mindenki látja oket. A P fogadó ˝ véletlen ideig vár; ha közben egy másik a NACK küldése elott fogadótól NACK érkezik, akkor P nem küld NACK-t (elfojtás), ezzel csökkenti az üzenetek számát. A NACK hatására a küldo˝ mindegyik fogadóhoz újra eljuttatja az üzenetet, így P-hez is. Sender receives only one NACK Sender

Receivers suppress their feedback Receiver

Receiver

Receiver

Receiver

T=3 NACK

T=4 NACK

T=1 NACK

T=2 NACK

NACK Network



17 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható csoportcímzés: hierarchikus visszajelzés-vezérlés ˝ o˝ módszer lokális hálózatban muködik Az eloz ˝ hatékonyan. Az ˝ átméretezhetoség javításához a lokális hálózatokból építsünk fát; az üzenetek a fában felfelé, a NACK üzenetek felfelé utaznak. Probléma: a fát dinamikusan kell építeni, a meglévo˝ hálózatok átkonfigurálása nehéz lehet. Sender (Long-haul) connection Local-area network

S

Coordinator C

C

R Root

Receiver



18 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Megbízható csoportcímzés: elemi csoportcímzés A folyamatok számon tartják, hogy kik a csoport tagjai: nézet (view). Egy üzenetet csak akkor kézbesítenek, ha az eljutott az adott nézet ˝ minden tagjához. Mivel a nézetek idoben változhatnak, ez ún. látszólagos szinkronizáltságot (virtual synchrony) ad. Reliable multicast by multiple P1 joins the group point-to-point messages

P3 crashes

P3 rejoins

P1 P2 P3 P4 G = {P1,P2,P3,P4}

G = {P1,P2,P4} Partial multicast from P3 is discarded



G = {P1,P2,P3,P4} Time

19 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Elosztott véglegesítés: 2PC 2PC Egy elosztott számítás végén szeretnénk elérni, hogy vagy minden folyamat véglegesítse az eredményt, vagy egyik sem. (atomiság) Ezt általában kétfázisú véglegesítéssel (two-phase commit, 2PC) szokás elérni. A számítást az azt kezdeményezo˝ kliens koordinátorként vezérli. Az egyes fázisokban a koordinátor (K) és egy-egy résztvevo˝ (R) az alábbiak szerint cselekszik. 1/K: Megkérdez mindenkit, enged-e véglegesíteni: vote-request. 1/R: Dönt: igennel (vote-commit) vagy nem (vote-abort), utóbbi esetben rögtön el is veti a kiszámított értéket. 2/K: Ha minden válasz vote-commit, mindenkinek global-commit üzenetet küld, különben global-abort üzenetet. 2/R: Végrehajtja a kapott globális utasítást: elmenti a kiszámított ˝ adatokat (eddig csak átmenetileg tárolta oket lokálisan), illetve törli ˝ oket. Maarten van Steen, Kitlei Róbert


20 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Elosztott véglegesítés: 2PC

A vonalak fölött a kapott, alattuk a küldött üzenetek nevei láthatóak. Vote-request Vote-abort

INIT Commit Vote-request WAIT Vote-abort Global-abort

Vote-commit Global-commit

INIT Vote-request Vote-commit READY Global-abort ACK

COMMIT

ABORT

ABORT

(a)

COMMIT (b)

A 2PC koordinátor állapotgépe


Global-commit ACK

Egy 2PC résztvevo˝ állapotgépe


21 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Elosztott véglegesítés: 2PC, résztvevo˝ összeomlása Résztvevo˝ összeomlása Egy résztvevo˝ összeomlott, majd felépült. Mit tegyen adott állapotban? ˝ döntés: ABORT. INIT: A résztvevo˝ nem is tudott a véglegesítésrol, ˝ Az állapot marad ABORT. ABORT: Az eredmények törlendok. ˝ Az állapot marad COMMIT. COMMIT: Az eredmények elmentendok. READY: A résztvevo˝ a koordinátor 2/K döntésére vár, amit megkérdez ˝ vagy a koordinátor összeomlása esetén a többi résztvevot ˝ ol. ˝ Azok tole, vagy már tudnak róla (ABORT vagy COMMIT), vagy még INIT állapotban vannak (ekkor ABORT mellett dönthetnek). Ha mindegyik résztvevo˝ READY állapotban van, akkor megoldható a helyzet, azonban... A 2PC protokoll blokkolódhat Ha a koordinátor és legalább egy résztvevo˝ összeomlott, és a többi résztvevo˝ a READY állapotban van, akkor a protokoll beragad, ugyanis nem ismert, hogy ˝ valamilyen utasítást a a kiesett résztvevo˝ kapott-e az összeomlása elott koordinátortól. Ez szerencsére szinte sohasem fordul elo˝ a gyakorlatban. Maarten van Steen, Kitlei Róbert


22 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Elosztott véglegesítés: 3PC 3PC ˝ 1/K és 1/R: Mint korábban: megkezdodik a szavazás (vote-request), és a ˝ válaszolnak (vote-commit vagy vote-abort) résztvevok ˝ 2/K: Ha van vote-abort) szavazat, minden résztvevonek global-abort üzenetet küld, majd leáll. Ha minden szavazat vote-commit, prepare-commit üzenetet küld mindenkinek. 2/R: global-abort esetén leáll; prepare-commit üzenetre ready-commit üzenettel válaszol. 3/K: Összegyujti ˝ a prepare-commit üzeneteket; küldi: global-commit. 3/R: Fogadja a global-commit üzenetet, és elmenti az adatokat. A 3PC protokoll nem blokkolódhat ˝ mindig legfeljebb „egy távolságban Mivel a koordinátor és a résztvevok vannak” az állapotaikat tekintve, ha mindegyik aktív résztvevo˝ READY állapotban van, akkor a kiesett résztvevo˝ még nem járhat a COMMIT fázisban. Megjegyzés: a PRECOMMIT állapotból csak véglegesíteni lehet. Maarten van Steen, Kitlei Róbert


23 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Elosztott véglegesítés: 3PC

Vote-request Vote-abort

INIT Commit Vote-request WAIT Vote-abort Global-abort

Vote-commit Prepare-commit

ABORT

INIT Vote-request Vote-commit READY Global-abort ACK

PRECOMMIT

ABORT

PRECOMMIT

Ready-commit Global-commit

Global-commit ACK

COMMIT

COMMIT

(a)

(b)

A 3PC koordinátor állapotgépe


Prepare-commit Ready-commit

Egy 3PC résztvevo˝ állapotgépe


24 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Felépülés Alapok Ha hibajelenséget érzékelünk, minél hamarabb hibamentes állapotba szeretnénk hozni a rendszert. ˝ Elorehaladó felépülés: olyan új állapotba hozzuk a rendszert, ahonnan az folytathatja a muködését ˝ Visszatéro˝ felépülés: egy korábbi érvényes állapotba térünk vissza Jellemzo˝ választás ˝ opontokat ˝ Visszatéro˝ felépülést alkalmazunk, ehhez ellenorz (checkpoint) veszünk fel. Konzisztens állapot szükséges ˝ opontot ˝ Az elosztott rendszerek visszaállítását nehezíti, hogy ellenorz a rendszer egy konzisztens állapotára szeretnénk elhelyezni, ennek megtalálásához pedig a folyamatok együttmuködése ˝ szükséges. Maarten van Steen, Kitlei Róbert


25 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Stabil tárolás (stable storage) Sector has different value b

b

c

c

b

a

d

a

d

a

h

e

h

e

h

g

f

b

c

a h g

f

(a)

d

a

e

h

g

f

b

c

g

d

a

e

h

f

(b)

c d e

g

f

b

c

Bad checksum d e

g

f

(c)

˝ opontokat ˝ Az ellenorz minél megbízhatóbban kell tárolnunk. Tegyük fel, hogy fizikailag szinte elpusztíthatatlan tárunk van (stable storage), és két másolatot használunk; mit kell tenni összeomlás után? Ha mindkét lemez tartalma azonos, minden rendben. ˝ oösszegek ˝ Ha az ellenorz alapján kiderül, melyik a helyes, azt választjuk. Ha helyesek, de eltérnek, az elso˝ lemezt választjuk, mert oda írunk ˝ eloször. ˝ melyiket kell választani. Ha egyik sem helyes, nehezen eldöntheto, Maarten van Steen, Kitlei Róbert


26 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Konzisztens rendszerállapot A folyamatok pillanatfelvételeket készítenek az állapotukról. ˝ opont-gy ˝ konzisztens metszet: olyan ellenorz ujtemény, ˝ amelyben minden beérkezett üzenethez a küldési esemény is el van tárolva ˝ készült (legfrissebb) konzisztens metszet felépülési vonal: a leheto˝ legkésobb Recovery line

Initial state

Checkpoint

P1 Failure P2 Message sent from P2 to P1


Time Inconsistent collection of checkpoints


27 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Dominóeffektus Vissza kell keresnünk a legutolsó konzisztens metszetet. Ezért minden ˝ oponthoz, ˝ folyamatban vissza kell térni egy korábbi ellenorz ha „elküldetlen” fogadott üzenetet találunk. Így viszont további üzenetek válnak nem elküldötté, ami továbbgyur ˝ uz ˝ o˝ visszagörgetéshez (cascaded rollback) vezethet. Initial state

Checkpoint

P1

m

Failure

m

P2 Time



28 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

˝ opontok ˝ Független ellenorz készítése ˝ Egy lehetoség, ha mindegyik folyamat egymástól függetlenül készít ˝ opontokat ˝ ellenorz (independent checkpointing). ˝ opontját. ˝ Jelölje CP[i](m) a Pi folyamat m-edik ellenorz Jelölje INT[i](m) a CP[i](m − 1) és CP[i](m) közötti ˝ idointervallumot. Amikor Pi üzenetet küld a INT[i](m) intervallumban, hozzácsatolja i és m értékét. Amikor Pj fogadja az üzenetet a INT[j](n) intervallumban, rögzíti, függ

˝ hogy új függoség keletkezett: INT[i](m) −→ INT[j](n), és ezt CP[j](n) készítésekor a stabil tárba menti Ha Pi -nek vissza kell állítania CP[i](m − 1)-et, akkor Pj -t is vissza ˝ kell görgetni CP[i](m − 1)-ig. A függoségek egy gráfot adnak ki, ennek a vizsgálatával derül ki, melyik folyamatot pontosan melyik ˝ opontig ˝ ellenorz kell visszagörgetni, legrosszabb esetben akár a ˝ rendszer kezdoállapotáig. Maarten van Steen, Kitlei Róbert


29 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

˝ opontkészítés ˝ Koordinált ellenorz

A dominóeffektus elkerülése végett most egy koordinátor vezérli az ˝ opont ˝ ellenorz készítését. Kétfázisú protokollt használunk: Az elso˝ fázisban a koordinátor minden folyamatot pillanatfelvétel készítésére szólít fel. Amikor ezt megkapja egy folyamat, elmenti az állapotát, és ezt nyugtázza a koordinátor felé. A folyamat továbbá felfüggeszti az üzenetek küldését. Amikor a koordinátor minden nyugtát megkapott, minden folyamatnak engedélyezi az üzenetek küldését.



30 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Felépülés naplózással Ahelyett, hogy pillanatfelvételt készítenénk, most megpróbáljuk újra ˝ oponttól. ˝ lejátszani a kommunikációs lépéseket az utolsó ellenorz Ehhez mindegyik folyamat lokális naplót vezet. ˝ feltételezzük, hogy szakaszosan A végrehajtási modellrol determinisztikus (piecewise deterministic): Mindegyik folyamat végrehajtását egymás után következo˝ szakaszok sorozata Mindegyik szakasz egy nemdeterminisztikus eseménnyel ˝ kezdodik (pl. egy üzenet fogadása, szignál kezelése) A szakaszon belül a végrehajtás determinisztikus A naplóba elég a nemdeterminisztikus eseményeket felvenni, a többi ˝ lépés belolük meghatározható.



31 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Üzenetek konzisztens naplózása Q crashes and recovers P m1

m1

m2 is never replayed, so neither will m3

Q m3

m2

m2

m3

R Unlogged message Logged message

Time

Úgy szeretnénk naplózni, hogy elkerüljük árva folyamatok kialakulását. Q folyamat fogadta m1 -et és m2 -t, és elküldte m3 -at. Tegyük fel, hogy m2 üzenetet se R, se Q nem naplózta Q összeomlása után a visszajátszás során ekkor senkinek sem tunik ˝ fel, hogy m2 kimaradt ˝ (lehet, hogy) függo˝ m3 -at sem Mivel Q kihagyta m2 -t, ezért a tole küldi el Maarten van Steen, Kitlei Róbert


32 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Üzenetek konzisztens naplózása Jelölések HDR[m]: Az m üzenet fejléce, tartalmazza a küldo˝ és a folyamat azonosítóját és az üzenet sorszámát. Egy üzenet stabil, ha a fejléce már biztosan nem veszhet el (pl. mert stabil tárolóra írták). COPY[m]: Azok a folyamatok, amelyekhez HDR[m] már megérkezett, de még nem tárolták el. Ezek a folyamatok képesek HDR[m] reprodukálására. DEP[m]: Azok a folyamatok, amelyekhez megérkezett HDR[m’], ahol ˝ m0 okozatilag függ m-tol. Ha C összeomlott folyamatok halmaza, akkor Q 6∈ C árva, ha függ ˝ amelyet csak az összeomlottak tudnának eloállítani: ˝ olyan m üzenettol, Q ∈ DEP[m] és COPY[m] ⊆ C. Ha DEP[m] ⊆ COPY[m], akkor nem lehetnek árva folyamataink. Maarten van Steen, Kitlei Róbert


33 / 34

Bevezetés

Hibaturés ˝

Kommunikáció


Véglegesítés

Felépülés

Üzenetek konzisztens naplózása Pesszimista naplózóprotokoll Ha m nem stabil, akkor megköveteljük, hogy legfeljebb egy folyamat ˝ függjön tole: |DEP[m]| ≤ 1. Implementáció: minden nem-stabil üzenetet stabilizálni kell ˝ továbbküldés elott. Optimistista naplózóprotokoll Tegyük fel, hogy C a hibás folyamatok halmaza. A nem-stabil m üzenetekre, ha COPY[m] ⊆ C, akkor azt szeretnénk elérni, hogy egy ido˝ után DEP[m] ⊆ C is teljesüljön. Implementáció: minden árva folyamatot visszagörgetünk olyan ˝ opontig, ˝ ˝ ellenorz ahol a függoség már nem áll fenn. Maarten van Steen, Kitlei Róbert


34 / 34


Kitlei Róbert 2


10. rész: Objektumalapú elosztott rendszerek 2015. május 24.




2 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció

10.4 Elnevezési rendszerek

10.6 Replikáció

Távoli elosztott objektumok Objektum: muveleteket ˝ és adatokat zár egységbe (enkapszuláció) A muveleteket ˝ metódusok implementálják, ezeket interfészekbe csoportosítjuk Az objektumokat csak az interfészükön keresztül érhetik el a kliensek Az objektumokat objektumszerverek tárolják A kliensoldali helyettes (proxy) megvalósítja az interfészt A szerveroldalon a váz (skeleton) kezeli a beérkezo˝ kéréseket Client machine

Server machine Object Server

Client

State Same interface as object

Client invokes a method Proxy

Skeleton invokes same method at object

Method

Interface Skeleton

Client OS

Server OS

Network Marshalled invocation is passed across network



3 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Távoli elosztott objektumok Objektumok létrehozás ideje alapján ˝ Fordítási idoben létrejövo˝ objektumok: A helyettest és a vázat a fordítóprogram készíti el, összeszerkeszti a kliens és a szerver kódjával. Nem cserélheto˝ le, miután létrejött, és a klienssel/szerverrel azonos a programozási nyelve. ˝ ˝ Futási idoben létrejövo˝ objektumok: Tetszoleges nyelven valósítható meg, de objektumadapterre van szükség a szerveroldalon a használatához. Objektumok élettartamuk alapján Átmeneti (tranziens) objektum: Élettartama csak addig tart, amíg be van töltve a szerverbe. Ha a szerver kilép, az objektum is megsemmisül. Tartós (perzisztens) objektum: Az objektum állapotát és kódját lemezre írjuk, így a szerver kilépése után is megmarad. Ha a szerver nem fut, az objektum passzív; amikor a szerver elindul, betöltéssel aktivizálható. Maarten van Steen, Kitlei Róbert


4 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Példa: Enterprise Java Beans (EJB) Az objektumokat alkalmazásszerverek (pl. GlassFish) tárolják, amelyek ˝ teszik az objektumok különbözo˝ módokon való elérését. lehetové Container EJB EJBEJB Server RMI

JDBC

JNDI

JMS

Services

Server kernel Local OS Network



5 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Példa: Enterprise Java Beans (EJB) EJB-k fajtái Stateless session bean: Tranziens objektum, egyszer hívják meg, miután elvégezte a feladatát, megszunik. ˝ Példa: egy SQL lekérdezés végrehajtása, és az eredmény átadása a kliensnek. Stateful session bean: Tranziens objektum, de a klienssel egy munkameneten (session) keresztül tartja a kapcsolatot, ezalatt állapotot is tart fenn. Példa: bevásárlókosár. Entity bean: Perzisztens, állapottal rendelkezo˝ objektum, amely több munkamenetet is ki tud szolgálni. Példa: olyan objektum, ˝ tárol adatokat. amely az utolsó néhány kapcsolódó kliensrol Message-driven bean: Különbözo˝ fajta üzenetekre reagálni képes objektum. A publish/subscribe kommunikációs modell szerint muködik. ˝



6 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Globe elosztott objektumok Általában a távoli objektumok nem elosztottak: az állapotukat egy gép tárolja. A Globe rendszerben az objektumok fizikailag több gépen helyezkednek el: elosztott közös objektum (distributed shared object, DSO). Distributed shared object Local object

Process Network

Interface Maarten van Steen, Kitlei Róbert


7 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Globe elosztott objektumok Az elosztottság támogatásához belso˝ architektúra szükséges, és célszeru, ˝ ha ez független attól, hogy a DSO külso˝ felülete milyen szolgáltatásokat nyújt.

Same interface as implemented by semantics subobject Control subobject

Replication subobject

Semantics subobject

Communication subobject

A replikációkezelo˝ alobjektum vezérli, hogy hogyan és mikor kell a lokális szemantikus alobjektumot meghívni. Maarten van Steen, Kitlei Róbert

Communication with other local objects


8 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Folyamatok: Objektumszerverek A rendszer részei a kiszolgálók, a vázak és az adapterek. A kiszolgálót (servant), amely az objektum muködését ˝ biztosítja, több paradigma szerint lehet implementálni: Függvények gyujteménye, ˝ amelyek adatbázistáblákat, rekordokat stb. manipulálnak (pl. C vagy COBOL nyelven) Osztályok (pl. Java vagy C++ nyelven) A váz (skeleton) a szerveroldali hálózati kapcsolatokat kezeli: Kicsomagolja a beérkezo˝ kéréseket, lokálisan meghívja az objektumot, becsomagolja és visszaküldi a választ Az interfész specifikációja alapján hozzák létre Az objektumadapter feladata objektumok egy csoportjának kezelése: ˝ Elsoként fogadja a kéréseket, és azonosítja a releváns kiszolgálót Aktivációs házirend (policy) szerint aktiválja a megfelelo˝ vázat Az adapter generálja az objektumhivatkozásokat Maarten van Steen, Kitlei Róbert


9 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Folyamatok: Objektumszerverek Az objektumszerverek vezérlik a tartalmazott objektumok létrehozását. Server with three objects

Server machine

Object's stub (skeleton)

Object adapter

Object adapter

Request demultiplexer Local OS



10 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Példa: Ice Az Ice (Internet Communications Engine) objektumorientált ˝ a legnépszerubb köztesréteg, szolgáltatásai elérhetoek ˝ nyelveken. Az aktivációs házirend megjelenik a köztesréteg szintjén: az adapter properties adattagján át lehet módosítani. Ez segíti a rendszer ˝ egyszeru˝ kezelhetoségét. main(int argc, char* argv[]) { Ice::Communicator ic = Ice::initialize(argc, argv); Ice::ObjectAdapter adapter = ic->createObjectAdapterWithEndPoints("a","tcp -p 2000"); Ice::Object object = new MyObject; adapter->add(object, objectID); adapter->activate(); ic->waitForShutdown(); }



11 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Kliens csatlakoztatása objektumhoz Objektumhivatkozás Ha egy kliens birtokol egy referenciát egy objektumra, képes hozzá csatlakozni (bind): ˝ A hivatkozás eloírja, melyik szerveren, melyik objektumot, milyen kommunikációs protokoll szerint lehet rajta keresztül elérni A hivatkozáshoz kód tartozik, ezt a konkrét objektum eléréséhez felparaméterezve kapjuk a helyettest Kétfajta csatlakozás Implicit: Magán a hivatkozott objektumon hívjuk meg a muveleteket ˝ Explicit: A kliens kódjában a csatlakozás explicit megjelenik



12 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Kliens-objektum csatlakozás: implicit/explicit // implicit Distr_object* obj_ref; obj_ref = ...; obj_ref->do_something();

// explicit Distr_object* obj_ref; Local_object* obj_ptr; obj_ref = ...; obj_ptr = bind(obj_ref); obj_ptr->do_something();

A hivatkozás tartalmazhat egy URL-t, ahonnan az implementáció letöltheto˝ ˝ hogyan kell betölteni és példányosítani a letöltött Protokollban rögzítheto, kódot A szerver és az objektum ismerete elegendo˝ lehet a távoli metódushívás megkezdéséhez Objektumhivatkozások paraméterként is átadhatóak, amik RPC esetében bonyodalmakat okoznak



13 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Távoli metódushívás (Remote Method Invocation, RMI) Tegyük fel, hogy a helyettes és a váz rendelkezésre áll a kliensnél/szervernél. 1

A kliens meghívja a helyettest

2

A helyettes becsomagolja a hívás adatait, és elküldi a szervernek

3

A szerver biztosítja, hogy a hivatkozott objektum aktív: Külön folyamatot hozhat létre, amely tárolja az objektumot Betöltheti az objektumot a szerverfolyamatba ...

4

Az objektum váza kicsomagolja a kérést, és a metódus meghívódik

5

Ha paraméterként objektumhivatkozást kaptunk, ezt szintén távoli metódushívással éri el a szerver; ebben a szerver kliensként vesz részt

6

A választ hasonló úton küldjük vissza, a helyettes kicsomagolja, és visszatér vele a klienshez



14 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

RMI: Paraméterátadás Hivatkozás szerinti paraméterátadás: sokkal egyszerubb, ˝ mint RPC esetén. A szerver egyszeruen ˝ távoli metódushívással éri el az objektumot Ha már nincsen szüksége rá, megszünteti a csatolást (unbind) Érték szerinti paraméterátadás: RMI esetén ez kevésbé kényelmes. Szerializálni kell az objektumot Az állapotát A metódusait, vagy hivatkozást olyan helyre, ahol elérheto˝ az implementációjuk

Amikor a szerver kicsomagolja az objektumot, ezzel másolat ˝ készül az eredetirol Ez az automatikus másolódás többféle problémát okoz, pl. néha „túl átlátszó”: könnyen több objektumról készíthetünk másolatot, ˝ szeretnénk mint amennyirol Maarten van Steen, Kitlei Róbert


15 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

RMI: Paraméterátadás Machine A Local reference L1

Machine B

Local object O1

Client code with RMI to server at C (proxy)

Remote object O2

Remote reference R1

New local reference

Copy of O1

Remote invocation with L1 and R1 as parameters

Copy of R1 to O2 Machine C

Server code (method implementation)

A rendszerszintu˝ objektumhivatkozások általában a szerver címét, adapterének portját és az objektum lokális azonosítóját tartalmazzák. Néha ezekhez további információk is járulnak, pl. a kliens és szerver között használt protokoll (TCP, UDP, SOAP stb.) Maarten van Steen, Kitlei Róbert


16 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

RMI: Paraméterátadás Machine A Local reference L1

Machine B

Local object O1

Client code with RMI to server at C (proxy)

Remote object O2

Remote reference R1

New local reference

Copy of O1

Remote invocation with L1 and R1 as parameters

Copy of R1 to O2 Machine C

Server code (method implementation)

Mivel a helyettesnek mindenféleképpen ismernie kell a hivatkozáshoz szükséges adatokat (cím, port, lokális ID), felhasználhatjuk a helyettest ˝ magát mint távoli hivatkozást. Ez különösen elonyös, ha a helyettes letöltheto˝ (pl. a Java esetében igen). Maarten van Steen, Kitlei Róbert


17 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Objektumalapú üzenetküldés Client application 1. Call by the application Client proxy

Callback interface

4. Call by the RTS 3. Response from server

Client RTS

A kliens az üzenetekre várás közben lehet aktív vagy passzív.

2. Request to server

Client application 1. Call by the application

4. Call by the application Client proxy

Polling interface 3. Response from server

Client RTS 2. Request to server Maarten van Steen, Kitlei Róbert


18 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Objektumhivatkozások IIOP1 : távoli objektumhivatkozásokat kezelo˝ protokoll CORBA2 : Objektumalapú köztesréteg, IIOP-t használ Az alábbi ábrán a CORBA objektumhivatkozásának szerkezete látható. Tagged Profile Interoperable Object Reference (IOR) Repository identifier

Profile ID

IIOP version

Host

Adapter identifier

1 Internet

Profile

Port

Object key

Object identifier

Components

Other serverspecific information

Inter-ORB Protocol Object Request Broker Architecture

2 Common



19 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Objektumhivatkozások Különbözo˝ objektumkezelo˝ rendszerekben a hivatkozások szerkezete nagymértékben eltérhet. A rendszerek között átjárók (gateway) biztosíthatják a hivatkozások konvertálását. Object server

Interoperable references

Object system A


(Half) gateway

Object system B


20 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Replikáció és konzisztencia Az objektumok a belépo˝ konzisztencia megvalósításának természetesen adódó eszközei: Az adatok egységbe vannak zárva, és szinkronizációs változóval ˝ (zárral) védjük oket A szinkronizációs változókat soros konzisztencia szerint érjük el (az értékek beállítása atomi lépés) Az adatokat kezelo˝ muveletek ˝ összessége pont az objektum interfésze lesz Replikáció Mit tegyünk, ha az objektumot replikálni kell? A replikált objektumokon a muveletek ˝ végrehajtásának sorrendjének azonosnak kell lennie.



21 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Replikált objektumok Nemcsak a kéréseknek kell sorrendben beérkezniük a replikátumokhoz; a vonatkozó szálak ütemezésének determinisztikusnak kell lennie. Egyszeru˝ megoldás lehetne, ha teljesen sorosítva (egyetlen szálon) hajtanánk végre a kéréseket, de ez túl költséges. Computer 1

Computer 2

Object T11

Threads

Thread scheduler

T21

Deterministic thread scheduling

Threads

T22

Totally ordered requests

Middleware

Middleware

Local OS

Local OS Unordered requests


T12


Unordered requests

22 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Replikált hívások Aktív replikáció: ha a replikált objektum hívás során maga is meghív más objektumot, az a kérést többszörörözve kapná meg. Client replicates invocation request B1

A

All replicas see the same invocation

B2

Object receives the same invocation three times

C

B3

Replicated object



23 / 24

10.1 Architektúra

10.2 Folyamatok

10.3 Kommunikáció


10.6 Replikáció

Replikált hívások Megoldás: mind a szerver-, mind a kliensobjektumon válasszunk koordinátort, és csak a koordinátorok küldhessenek kéréseket és válaszokat. Coordinator of object C

Coordinator of object B Client replicates invocation request

Result B1

B1 C1

A

B2

C1

A

B2

C2 B3

C2 B3 Result

(a)


(b)


24 / 24


Kitlei Róbert 2


11. rész: Elosztott fájlrendszerek 2015. május 24.




2 / 15

11.1 Architektúra

11.3 Kommunikáció

11.5 Szinkronizáció

11.6 Konzisztencia és replikáció

11.7 Fault Tolerance

Elosztott fájlrendszerek

Cél: a fájlrendszer átlátszó elérését biztosítani távoli kliensek számára. 1. File moved to client Server

Client

Client

Server Old file New file

Requests from client to access remote file

File stays on server

Távoli hozzáférési modell


2. Accesses are done on client

3. When client is done, file is returned to

Feltöltés/letöltés modell


3 / 15

11.1 Architektúra

11.3 Kommunikáció




Példa: NFS architektúra Az NFS (Network File System) elosztott fájlok távoli elérését teszi ˝ lehetové. Az alkalmazások a helyi VFS (Virtual File System) réteget érik el, ez biztosítja a távoli elérés átlátszóságát. Client

Server

System call layer

System call layer

Virtual file system (VFS) layer

Virtual file system (VFS) layer

Local file system interface

NFS client

NFS server

RPC client stub

RPC server stub

Local file system interface

Network



4 / 15

11.1 Architektúra

11.3 Kommunikáció




NFS fájlmuveletek ˝ Muvelet ˝ Create Create Link Symlink Mkdir Mknod Rename Remove Rmdir Open Close Lookup Readdir Readlink Getattr Setattr Read Write

Verzió v3 v4 v3 és v4 v3 v3 v3 v3 és v4 v3 és v4 v3 v4 v4 v3 és v4 v3 és v4 v3 és v4 v3 és v4 v3 és v4 v3 és v4 v3 és v4


Leírás Hagyományos fájl létrehozása Nem-hagyományos fájl létrehozása (hagyományos: Open) Valódi csatolás (hard link) létrehozása fájlra Szimbolikus csatolás (soft link, symlink) létrehozása fájlra Alkönyvtár létrehozása Különleges fájl létrehozása Fájl átnevezése ˝ Fájl eltávolítása a fájlrendszerbol Üres könyvtár eltávolítása Fájl megnyitása Fájl bezárása Fájl megkeresése név szerint Könyvtár tartalmának lekérése Szimbolikus csatolás elérési útvonalának olvasása Fájl tulajdonságainak lekérdezése Egy vagy több tulajdonság írása Fájl tartalmának olvasása Fájl adatainak írása Elosztott rendszerek

5 / 15

11.1 Architektúra

11.3 Kommunikáció




Fürt (cluster) alapú fájlrendszerek Nagy fájlrendszerek esetén a kliens-szerver alapú megközelítés nem elég jó ⇒ a fájlokat csíkokra bontjuk (striping), így a részeiket párhuzamosan érjük el. Ennek célja a rendszer gyorsítása és biztonságosabbá tétele. File block of file a

a

b

a

b

a

c

e

d c

b

File block of file e

e

d

e

d

c

Whole-file distribution

a

b

c d

e

a c

a

b c

d e

b

d e

File-striped system Maarten van Steen, Kitlei Róbert


6 / 15

11.1 Architektúra

11.3 Kommunikáció




Példa: Google File System file name, chunk index GFS client

Master contact address Instructions

Chunk-server state

Chunk ID, range Chunk server

Chunk server

Chunk server

Linux file system

Linux file system

Linux file system

Chunk data

A fájlt 64 MB méretu˝ részekre (chunk) bontjuk, és több szerveren elosztva, replikálva tároljuk. A központ (master) csak azt tárolja, melyik szerver melyik részek ˝ ⇒ I/O terhelése alacsony felelose ˝ A szerverek elsodleges másolaton alapuló replikációs protokollt használnak; a központot ez nem terheli Maarten van Steen, Kitlei Róbert


7 / 15

11.1 Architektúra

11.3 Kommunikáció




RPC fájlrendszerekben ˝ Egy lehetoség távoli fájlrendszerek megvalósítására, ha távoli eljáráshívások segítségével végezzük a fájlmuveleteket. ˝ Ha a távoli gép elérése költséges, alternatív megoldásokra van szükség, pl. az NFSv4 támogatja több muvelet ˝ összekombinálását egy hívásba. Client

Server

Client

Server LOOKUP OPEN READ

LOOKUP

Lookup name

Lookup name

Open file READ

Read file data Read file data

Time

Time

(a)


(b)


8 / 15

11.1 Architektúra

11.3 Kommunikáció




Példa: RPC a Coda fájlrendszerben Ha replikált fájlokkal dolgozunk (pl. a Coda kliensei cache-elhetik a fájlokat), akkor a kérések sorrendjének kikényszerítése ((a) ábra) túlságosan költséges lehet, mert ha összeomlik egy kliens, akkor csak ˝ hosszú timeout után jöhet a következo. Client

Client Invalidate

Reply

Server

Invalidate

Invalidate

Reply

Server

Invalidate

Reply

Client

Reply

Client Time

Time

(a)


(b)


9 / 15

11.1 Architektúra

11.3 Kommunikáció




A fájlmegosztás szemantikája Ha egyszerre több kliens is hozzáférhet egy fájlhoz, a konkurens írási és olvasási muveletek ˝ lehetséges végrehajtási sorrendjeit és a kijöheto˝ eredményeket (összefoglalva: a rendszer szemantikáját) rögzíteni kell.

Client machine #1 a b Process A

a b c 1. Read "ab"

2. Write "c"

File server Original file a b

Single machine a b Process A

3. Read gets "ab"

a b c

Client machine #2 Process B

1. Write "c"

a b Process B

2. Read gets "abc" (a)



10 / 15

11.1 Architektúra

11.3 Kommunikáció




A fájlmegosztás szemantikája Sokfajta szemantika jöhet szóba. Megváltoztathatatlan fájlok: a fájlok tartalmát nem lehet módosítani létrehozás után; ez a modell csak ritkán használható UNIX szemantika: az olvasási muveletek ˝ mindig a legutolsó írási muvelet ˝ eredményét adják ⇒ a fájlból csak egy példányunk lehet ˝ o˝ (a) ábra) az elosztott rendszerben (az eloz Tranzakciós szemantika: a rendszer minden fájlra külön biztosít tranzakciókat Munkamenet szemantika: onnantól, hogy a kliens megnyitja a fájlt, odáig, amíg vissza nem írja, az írási és olvasási muveletei ˝ csak saját maga számára látszanak (gyakori választás a ˝ o˝ (b) ábra) rendszerekben; az eloz



11 / 15

11.1 Architektúra

11.3 Kommunikáció




Példa: fájlmegosztás Coda rendszerben A Coda fájlrendszer munkamenetei tranzakciós szemantikát valósítanak meg. A megnyitott fájl tartalma átmásolódik a kliensre; ha más módosítja a fájlt, arról a kliens értesítést kap. Ha a kliens csak olvas (pl. az ábrán SA ), akkor folytathatja a muködését ˝ – úgy tekintjük, hogy a tranzakció, amelyet végez, már korábban lezárult. Session S A Client Open(RD)

Invalidate

File f

Close Server Open(WR)

File f

Close

Client Session S B Maarten van Steen, Kitlei Róbert


Time

12 / 15

11.1 Architektúra

11.3 Kommunikáció




Konzisztencia és replikáció A modern elosztott fájlrendszerekben a kliensoldali gyorsítótárazás ˝ szerepe foleg a teljesítmény növelése, a szerveroldali replikáció célja a hibaturés ˝ biztosítása. ˝ A kliensek tárolhatják a fájlokat (vagy részeket belolük), és a szerver ˝ ˝ kiértesíti oket, ha ezt a jogot visszavonja tolük ⇒ a szerverek általában állapotteljesek. 1. Client asks for file Client

2. Server delegates file

Server Old file

Local copy

3. Server recalls delegation Updated file 4. Client sends returns file



13 / 15

11.1 Architektúra

11.3 Kommunikáció




Példa: kliensoldali gyorsítótárazás Coda rendszerben

Session S A

Session SA

Client A Open(RD)

File f

Server

Invalidate (callback break)

Close Open(RD)

File f

Close

File f OK (no file transfer)

Open(WR) Close

Open(WR)

Close

Client B Session S B

Session S B

Time

A tranzakciós szemantika segítségével a teljesítmény tovább ˝ növelheto.



14 / 15

11.1 Architektúra

11.3 Kommunikáció




Rendelkezésre állás növelése P2P rendszerekben Sok P2P alapú, decentralizált fájlrendszer létezik. Ezekben probléma lehet, ha túl gyorsan változik a tagság (churn), mert kiléphet akár egy fájlt tartalmazó összes csúcs. Ennek kivédéséhez replikálhatjuk a fájljainkat (arányát jelölje rrep ). Másik megközelítés: erasure coding: az F fájlt bontsuk m részre, és minden szerverre tegyünk n részt, ahol n > m. A replikációs arány ekkor rec = n/m. Ez az arány általában sokkal kisebb, mint rrep , ha a rendszerünk változékony. 2.2 rrep rec 2.0 1.8 1.6 1.4 0.2 Maarten van Steen, Kitlei Róbert

0.4

0.6


0.8 1 Node availability 15 / 15


Kitlei Róbert 2


12. rész: Elosztott webalapú rendszerek 2015. május 24.




2 / 17

12.1 Architektúra

12.2 Folyamatok


Elosztott webalapú rendszerek A WWW (világháló, World Wide Web) olyan szerverek összessége, amelyek HTTP protokollon keresztül különféle tartalmakat szolgálnak ki. A dokumentumokat hiperhivatkozások kapcsolják össze. Sok dokumentum szövegalapú: szövegfájl, HTML, XML Egyéb fajták: képek, audio, videó, dokumentum (PDF, PS) A tartalmak lehetnek a kliensoldalon végrehajthatóak (Javascript)

Jelenleg kb. 1 milliárd weboldal létezik, amelyek közül kevesebb mint 200 millió aktív; egy felmérés szerint a szerverek népszerusége: ˝ Apache (40%), IIS (29%), nginx (15%), egyéb (16%).


Client machine

Server machine

Browser

Web server

2. Server fetches document from local file

OS 3. Response 1. Get document request (HTTP)


3 / 17

12.1 Architektúra

12.2 Folyamatok



Már a kezdeti kiszolgálók is gyakran három rétegbe tagozódtak. 3. Start process to fetch document 1. Get request

6. Return result

HTTP request handler

CGI program

4. Database interaction

5. HTML document created Web server


CGI process


Database server

4 / 17

12.1 Architektúra

12.2 Folyamatok


Webszolgáltatások Felmerült az is, hogy a felhasználó ↔ weboldal interakció mellett az oldalak is igénybe vehetnek szolgáltatásokat más oldalakról ⇒ fontos, hogy a szolgáltatások szabványosak legyenek. Look up a service

Client machine

Server machine

Client application

Server application

Stub

Stub

Communication subsystem

SOAP

Publish service

Communication subsystem Generate stub from WSDL description

Generate stub from WSDL description Servicedescription description(WSDL) (WSDL) Service Service description (WSDL) Directory service (UDDI) Maarten van Steen, Kitlei Róbert


5 / 17

12.1 Architektúra

12.2 Folyamatok


Webszerverek A szerver szerkezetét a tartalmak kiszolgálásának menete szabja meg. ˝ amelyek a kiszolgálás A szerverekbe beépülo˝ modulok telepíthetok, egyes fázisaiban aktivizálódnak. Module

Module

...

Function

Module

...

... Link between function and hook

Hook

Hook

Hook

Hook

Apache core Functions called per hook Request Maarten van Steen, Kitlei Róbert

Response Elosztott rendszerek

6 / 17

12.1 Architektúra

12.2 Folyamatok


Szerverfürtök A teljesítmény és a rendelkezésre állás növelésének érdekében a szerverek sokszor (a felhasználó számára átlátszó módon) többszörözve vannak.

Web server

Web server

Web server

Web server

LAN Front end Request

Front end handles all incoming requests and outgoing responses Response

A kapcsolattartó (front end) szuk ˝ keresztmetszetté válhat, ennek ˝ elkerülésére több lehetoség van. TCP átadás: Valamilyen metrika alapján kiválasztunk egy szervert, és a kliens kiszolgálását az a szerver folytatja. Tartalomérzékeny kéréselosztás (content aware distribution): Lásd következo˝ oldal. Maarten van Steen, Kitlei Róbert


7 / 17

12.1 Architektúra

12.2 Folyamatok


Szerverfürtök Tartalomérzékeny kéréselosztás (content aware distribution): A HTTP kérés tartalmát is figyelembe vesszük a szerver kiválasztásánál. Ez ˝ megnöveli a kapcsolattartó terhelését, de sok elonye van: segítségével hatékonyabb lehet a szerveroldali cache-elés, és lehetnek bizonyos feladatokra dedikált szervereink. 6. Server responses Web server

5. Forward other messages Other messages Client

Switch Setup request

4. Inform switch

1. Pass setup request to a distributor

Distributor Web server


3. Hand of f TCP connection

Distributor


Dispatcher 2. Dispatcher selects server

8 / 17

12.1 Architektúra

12.2 Folyamatok


Webhelyettes A kimeno˝ kapcsolatok kezelésére webhelyetteseket (web proxy) telepíthetünk. Ezek cache-elik a kiszolgált tartalmakat; csak akkor fordulnak a szerverekhez, ha sem náluk, sem a többi helyettesnél nincsen meg a kért tartalom. Web server 3. Forward request to Web server 1. Look in local cache

Cache

Web proxy

2. Ask neighboring proxy caches

Client Client Client HTTP Get request

Web proxy

Cache

Client Client Client Web proxy

Cache

Client Client Client Maarten van Steen, Kitlei Róbert


9 / 17

12.1 Architektúra

12.2 Folyamatok


Replikáció webkiszolgálókban A replikáció célja a teljesítmény növelése. A rendszer paraméterei (hová célszeru˝ a replikátumokat elhelyezni, konzisztencia megkövetelt ˝ erossége, kérések útvonalválasztása) változóak lehetnek, ezeket célszeru˝ önszabályozással beállítani. Uncontrollable parameters (disturbance / noise)

Corrections

Initial configuration +/Replica placement

+/Consistency enforcement

Web hosting system

Observed output

+/Request routing

Reference input

Metric estimation

Analysis Adjustment triggers



Measured output

10 / 17

12.1 Architektúra

12.2 Folyamatok


Hirtelen terhelés A terhelés néha ugrásszeruen ˝ megemelkedik (flash crowd, flash mob), ˝ ezt még akkor sem könnyu˝ kezelni, ha az eroforráskezelés dinamikus.

2 days (a)

2 days (b)

6 days (c)

2.5 days (d)



11 / 17

12.1 Architektúra

12.2 Folyamatok


Szerveroldali replikáció A tartalomkézbesíto˝ hálózatok (Content Delivery Network, CDN) nagy teljesítményu˝ és rendelkezésre állású elosztott rendszerek, amelyeknek célja dokumentumok hatékony kiszolgálása. CDN server

Cache

6. Get embedded documents (if not already cached)

5. Get embedded documents Return IP address client-best server CDN DNS server

7. Embedded documents 1. Get base document 4

DNS lookups

Client

Origin server

2. Document with refs to embedded documents

3 Regular DNS system



12 / 17

12.1 Architektúra

12.2 Folyamatok


Replikáció webalkalmazásokban ˝ Ha a CDN tárolt adataiban változás következik be, ez eloször az eredetszerveren jelenik meg. A változásokat el kell juttatni a CDN ˝ függ. szerverekhez; ennek a célszeru˝ módja a rendszer jellegétol Teljes replikáció: sok olvasás, kevés írás, összetett lekérdezések Részleges replikáció: sok olv., kevés írás, egyszeru˝ lekérdezések Tartalom szerinti gyorsítótárazás: Az adatbázist az edge szerver módosított, a lekérdezésekhez illeszkedo˝ alakban tárolja helyben, és feliratkozik a szerveren a frissítésekre. Jól muködik ˝ intervallumokra vonatkozó, összetett lekérdezésekre. Eredmények gyorsítótárazása: Az edge szerver a korábbi lekérdezések eredményeit tárolja el. Jól muködik ˝ egyszeru˝ lekérdezésekre, amelyek egyedi adatokra (nem intervallumokra) vonatkoznak. ˝ akkor a replikáció akár ronthatja is a Ha az írások számaránya megno, rendszer teljesítményét. Maarten van Steen, Kitlei Róbert


13 / 17

12.1 Architektúra

12.2 Folyamatok


Replikáció webalkalmazásokban: nincsen replikáció Edge-server side

Client

Origin-server side

query

Web server

Web server

response

Appl logic

Appl logic

Content-blind cache

Database copy full/partial data replication

Content-aware cache


Schema

full schema replication/ query templates


Schema

Authoritative database

14 / 17

12.1 Architektúra

12.2 Folyamatok


Webalk. replikációja: részleges/teljes replikáció Edge-server side

Client

Origin-server side

query

Web server

Web server

response

Appl logic

Appl logic

Content-blind cache


Content-aware cache

Schema




Schema


15 / 17

12.1 Architektúra

12.2 Folyamatok


Webalk. replikációja: tartalom szerinti gyorsítótárazás Edge-server side

Client

Origin-server side

query

Web server

Web server

response

Appl logic

Appl logic

Content-blind cache


Content-aware cache

Schema




Schema


16 / 17

12.1 Architektúra

12.2 Folyamatok


Webalk. replikációja: eredmények gyorsítótárazása Edge-server side

Client

Origin-server side

query

Web server

Web server

response

Appl logic

Appl logic

Content-blind cache


Content-aware cache


Schema



Schema


17 / 17

Elosztott rendszerek: Alapelvek és paradigmák Distributed Systems: Principles and Paradigms. 1. rész: Bevezetés

Recommend Documents