Elosztott rendszerek: Alapelvek és paradigmák Distributed Systems: Principles and Paradigms. 5. rész: Elnevezési rendszerek

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

5. rész: Elnevezési rendszerek 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 / 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

Elosztott rendszerek: Alapelvek és paradigmák Distributed Systems: Principles and Paradigms. 5. rész: Elnevezési rendszerek

Recommend Documents