Elosztott adatbázisok és peerto-peer. Simon Csaba

Elosztott adatbázisok és peerto-Peer (P2P) Simon Csaba [email protected]

Miről lesz szó? Mi a P2P?  Kell-e nekünk és miért?  Struktúrálatlan P2P ---------- DHT ---------- Elosztott P2P adatbázisok 

2

2014. október 27.

P2P

Legal Download in EU 

http://index.hu/kultur/2013/10/30/uhd/

4

2014. október 27.

CAP tétel 

CAP = Consistency, Availability, Partition Tolerance  



Elosztott rendszerekben Egyszerre nem lehet mind a három célt elérni

http://www.julianbrowne.com/article/vie wer/brewers-cap-theorem 5

2014. október 27.

DHT

6

P2P Keresés 

Strukturálatlan P2P rendszerek Gnutella, KaZaa, stb... Véletlenszerű keresés

 



Nincs információ a fájl lehetséges tárolási helyéről

Példa: koncentrikusan szélesedő keresés





Expanding Ring Search (ERS)

Nagy terhelés a rendszeren Minél több helyen tárolva, annál kisebb a keresés által generált terhelés





7

2014. október 27.

P2P Keresés (II) 

Strukturált P2P rendszerek 

Irányított keresés 

Kijelölt peer-ek kijelölt fájlokat (vagy azok fele mutató pointereket) kell tároljanak 





Mint egy információs pult

Ha valaki keresi a fájlt, tudja kit kérdezzen

Elvárt tulajdonságok 

Elosztottság 



Felelősség elosztása a résztvevők között

Alkalmazkodás    8

A peer-ek ki és bekapcsolódnak a rendszerbe Az új peer-eknek feladatokat osztani A kilépő peer-ek feladatai újraosztani 2014. október 27.

Elosztott hash táblák - DHT  

Distributed Hash Tables – DHT Egy hash függvény a keresett fájlhoz egy egyéni azonosítót társít 





Példa: h(„P2P_előadás”) -> 123

A hash függvény értékkészletét elosztja a peer-ek között Egy peer-nek tudnia kell minden olyan fájlról, melynek a hash-elt értéke a saját értékkészletébe tartozik  

Vagy saját maga tárolja a fájlt.... Vagy tudja ki tárolja a fájlt.

9

2014. október 27.

DHT példa 211-399 200-210

484-799

400-483 100-199

123 10

0-99

h(x) → [0..799]

2014. október 27.

DHT példa 211-399 200-210

484-799

400-483 100-199

123 11

0-99

h(x) → [0..799]

2014. október 27.

DHT útválasztás 

Minden peer mely információt tartalmaz egy fájlról elérhető kell legyen egy „rövid” úton 

 



A kereső peer által A fájlt tároló peer-ek által

Korlátozott számú szomszéd 



Korlátozott számú lépésen belül

Skálázható a rendszer méretétől függetlenül

A különböző DHT megoldások lényégében az útválasztásban térnek el 

12

CAN, Chord, Pastry, Tapestry

2014. október 27.

CAN

13

CAN Sylvia

Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, “A Scalable Content-Addressable Network”, Proceedings of the ACM SIGCOMM'01 Conference, San Diego, CA (August 2001). 

http://citeseerx.ist.psu.edu/viewdoc/sum mary?doi=10.1.1.140.3129

Ratnasamy, „A Scalable Content-Addressable Network”, Ph.D. Thesis, October 2002 Sylvia



http://berkeley.intel-research.net/sylvia/thesis.pdf

5

2014. október 27.

Content Addressable Network 

CAN = egy elosztott, Internet szinten skálázható hash tábla 



Tároló (Insert), kereső (Lookup) és adattörlő (Delete) műveleteket biztosít egy (Kulcs, Érték) paraméter párra

CAN tulajdonságok  



Teljesen elosztott rendszer Skálázható: minden résztvevő csak korlátozott számú állapotot tárol, a résztvevők számától függetlenül Hibatűrő: akkor is működőképes ha a rendszer egy része meghibásodott 6

2014. október 27.

CAN architektúra hash-tábla egy d-dimenziós ortogonális (Descartes) koordináta rendszerben kialakított D-tóruszon működik A

 

Ciklikus d-dimenziós tér hash(K)=(x1, …, xd) 1-dimenziós ciklikus tér 0.5 + 0.7 = 0.2

2014. október 27.

CAN architektúra A hash-tábla egy d-dimenziós ortogonális (Descartes) koordináta rendszerben kialakított D-tóruszon működik  Ciklikus d-dimenziós tér  hash(K)=(x1, …, xd)

Ortogonális (Descartes) távolság

2014. október 27.


Ortogonális (Descartes) távolság  p1 = 0.2; p2 = 0.8  CartDist (p1, p2) = 0.4

2014. október 27.


Ortogonális (Descartes) távolság  p1 = 0.2; p2 = 0.8  CartDist (p1, p2) = 0.4

1-dimenziós ciklikus tér 0.5 + 0.7 = 0.2

Koordináta zóna  Egy „szelet” a Descartes térből

2014. október 27.

CAN architektúra (II) 

CAN csomópontok  





Egy CAN csomópont = egy gép a rendszerben Egy CAN csomópont ≠ peer  A peer-nek itt más jelentése van, lásd „Zónák túlterhelése” később Minden CAN csomópont a tér egy külön zónájáért (szeletéjért) felel  A csomópont információt tárol az összes olyan állományról mely a saját zónájába hash-elődik A csomópontok egymás között lefedik a teljes teret

2014. október 27.

CAN szomszédok 2

CAN csomópont szomszéd ha a zónáik átfedik egymást d-1 dimenzió mentén és szomszédosak 1 dimenzió mentén 





Egy csomópont ismeri az összes szomszédja IP címét Egy csomópont ismeri az összes szomszédos zóna koordinátáit A csomópontok csak a szomszédaikkal tudnak kommunikálni 2014. október 27.

CAN csatlakozás 

Egy CAN-nek van egy DNS domain neve 



Egy vagy több „Bootstrap Node” IP címére képződik le

A Bootstrap Node tárolja néhány résztvevő csomópont IP címét 

Gateway csomópontok



Az új csomópont véletlenszerűen kiválaszt egyet, és rajta keresztül



próbál csatlakozni 

A hash tábla egy szeletét (zónát) az új csomópontnak kell adni 



A kapcsolódó állományokat, illetve az azokra vonatkozó adatokat tárolni kell az új csomóponton

Az új csomópont be kell kapcsolódjon az útválasztásba

2014. október 27.

CAN csatlakozás (II) Zóna keresése az új csomópont részére 1. Véletlenszerűen választ egy P pontot

2. A JOIN üzenetet a P pontért felelős csomóponthoz küldi 3. A kérést a CAN útválasztást használva továbbítja

2014. október 27.

CAN routing 1. Elindul egy tetszőleges pontból 2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding Az aktuális csomópont: 1. Leellenőrzi hogy a saját vagy a szomszédai zónája tartalmazza-e a P pontot 2. HA NEM a. Rangsorolja a szomszédait a P ponttal szembeni Descartes távolságuk alapján b. Az üzenetet a P ponthoz legközelebb álló szomszédhoz küldi c. Megismétli az 1. lépést 3. HA IGEN A pozitív választ (a keresett állományt) visszaküldi a keresőhöz 2014. október 27.

CAN routing 1. Elindul egy tetszőleges pontból 2. P = a K kulcs hash-elt értéke

3. Greedy (mohó) forwarding Az aktuális csomópont: 1. Leellenőrzi hogy a saját vagy a szomszédai zónája tartalmazza-e a P pontot 2. HA NEM a. Rangsorolja a szomszédait a P ponttal szembeni Descartes távolságuk alapján b. Az üzenetet a P ponthoz legközelebb álló szomszédhoz küldi c. Megismétli az 1. lépést 3. HA IGEN A pozitív választ (a keresett állományt) visszaküldi a keresőhöz 2014. október 27.

CAN routing 1. Elindul egy tetszőleges pontból 2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding Az aktuális csomópont: 1. Leellenőrzi hogy a saját vagy a szomszédai zónája tartalmazza-e a P pontot 2. HA NEM a. Rangsorolja a szomszédait a P ponttal szembeni Descartes távolságuk alapján b. Az üzenetet a P ponthoz legközelebb álló szomszédhoz küldi c. Megismétli az 1. lépést 3. HA IGEN A pozitív választ (a keresett állományt) visszaküldi a keresőhöz

2014. október 27.




CAN routing 1. Elindul egy tetszőleges pontból 2. P = a K kulcs hash-elt értéke

3. Greedy (mohó) forwarding Az aktuális csomópont: 1. Leellenőrzi hogy a saját vagy a szomszédai zónája tartalmazza-e a P pontot 2. HA NEM a. Rangsorolja a szomszédait a P ponttal szembeni Descartes távolságuk alapján b. Az üzenetet a P ponthoz legközelebb álló szomszédhoz küldi c. Megismétli az 1. lépést 3. HA IGEN A pozitív választ (a keresett állományt) visszaküldi a keresőhöz 2014. október 27.


CAN routing

Hibatűrő útválasztás

1. Elindul egy tetszőleges pontból 2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding a. Mielőtt továbbküldené az üzenetet, ellenőrzi a szomszéd készenléti állapotát b. Az üzenetet a rendelkezésre álló legjobb szomszédhoz küldi el

2014. október 27.

CAN routing Hibatűrő útválasztás 1. Elindul egy tetszőleges pontból

2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding a. Mielőtt továbbküldené az üzenetet, ellenőrzi a szomszéd készenléti állapotát b. Az üzenetet a rendelkezésre álló legjobb szomszédhoz küldi el

2014. október 27.


2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding a. Mielőtt továbbküldené az üzenetet, ellenőrzi a szomszéd készenléti állapotát b. Az üzenetet a rendelkezésre álló legjobb szomszédhoz küldi el

2014. október 27.

CAN routing Hibatűrő útválasztás 1. Elindul egy tetszőleges pontból 2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding a. Mielőtt továbbküldené az üzenetet, ellenőrzi a szomszéd készenléti állapotát b. Az üzenetet a rendelkezésre álló legjobb szomszédhoz küldi el

2014. október 27.


2. P = a K kulcs hash-elt értéke 3. Greedy (mohó) forwarding a. Mielőtt továbbküldené az üzenetet, ellenőrzi a szomszéd készenléti állapotát b. Az üzenetet a rendelkezésre álló legjobb szomszédhoz küldi el A célcsomópontot elérjük ha létezik legalább egy út 2014. október 27.

CAN csatlakozás (II) Zóna keresése az új csomópont részére 1. Véletlenszerűen választ egy P pontot 2. A JOIN üzenetet a P pontért felelős csomóponthoz küldi 3. A kérést a CAN útválasztást használva továbbítja 4. A P pontért felelős csomópont kettévágja zónáját • Az egyik fele az új csomóponté lesz • A másik fele megmarad a régi csomópontnál 5. Az elosztás a zóna legnagyobb oldalának megfelelő dimenzió mentén történik • Ha két oldal egyenlő, a kisebbik rangú dimenzió mentén osztódik 6. A hash tábla alapján az új csomópont zónájába eső állományokra vonatkozó adatokat átküldi 2014. október 27.



2. A JOIN üzenetet a P pontért felelős csomóponthoz küldi 3. A kérést a CAN útválasztást használva továbbítja 4. A P pontért felelős csomópont kettévágja zónáját • Az egyik fele az új csomóponté lesz • A másik fele megmarad a régi csomópontnál 5. Az elosztás a zóna legnagyobb oldalának megfelelő dimenzió mentén történik • Ha két oldal egyenlő, a kisebbik rangú dimenzió mentén osztódik 6. A hash tábla alapján az új csomópont zónájába eső állományokra vonatkozó adatokat átküldi

2014. október 27.


2. A JOIN üzenetet a P pontért felelős csomóponthoz küldi 3. A kérést a CAN útválasztást használva továbbítja 4. A P pontért felelős csomópont kettévágja zónáját • Az egyik fele az új csomóponté lesz • A másik fele megmarad a régi csomópontnál 5. Az elosztás a zóna legnagyobb oldalának megfelelő dimenzió mentén történik • Ha két oldal egyenlő, a kisebbik rangú dimenzió mentén osztódik 6. A hash tábla alapján az új csomópont zónájába eső állományokra vonatkozó adatokat átküldi 2014. október 27.


CAN csatlakozás (III) Bekapcsolódás az útválasztásba 1. Az új csomópont megkapja a régi csomópont (kinek a zónáját osztottuk) szomszédainak listáját 2. A régi csomópont frissíti a szomszédait • Törli az „elvesztett” szomszédokat • Bejegyzi az új csomópontot

3. Minden szomszéd kap egy frissítő üzenetet, a saját szomszéd-táblája frissítéséhez •Törli a régi csomópontot •Bejegyzi az új csomópontot 2014. október 27.

CAN csatlakozás (III) Bekapcsolódás az útválasztásba 1. Az új csomópont megkapja a régi csomópont (kinek a zónáját osztottuk) szomszédainak listáját 2. A régi csomópont frissíti a szomszédait • Törli az „elvesztett” szomszédokat • Bejegyzi az új csomópontot 3. Minden szomszéd kap egy frissítő üzenetet, a saját szomszéd-táblája frissítéséhez •Törli a régi csomópontot •Bejegyzi az új csomópontot

2014. október 27.

CAN csatlakozás (III) Bekapcsolódás az útválasztásba 1. Az új csomópont megkapja a régi csomópont (kinek a zónáját osztottuk) szomszédainak listáját 2. A régi csomópont frissíti a szomszédait • Törli az „elvesztett” szomszédokat • Bejegyzi az új csomópontot

3. Minden szomszéd kap egy frissítő üzenetet, a saját szomszéd-táblája frissítéséhez •Törli a régi csomópontot •Bejegyzi az új csomópontot

2014. október 27.

CAN csatlakozás (III) Bekapcsolódás az útválasztásba 1. Az új csomópont megkapja a régi csomópont (kinek a zónáját osztottuk) szomszédainak listáját 2. A régi csomópont frissíti a szomszédait • Törli az „elvesztett” szomszédokat • Bejegyzi az új csomópontot 3. Minden szomszéd kap egy frissítő üzenetet, a saját szomszéd-táblája frissítéséhez •Törli a régi csomópontot •Bejegyzi az új csomópontot

2014. október 27.

Csomópont távozása Csomópont kilép a rendszerből a. Ha az egyik szomszéd zónája egyesíthető a kilépő csomópont zónájával, akkor ez a szomszéd veszi át az egyesített zóna kezelését egyesíthető = „szabályos” konvex zóna keletkezik b. Ha nem, akkor az egyik szomszéd két külön zónát kezel majd

2014. október 27.

Csomópont távozása Csomópont kilép a rendszerből a. Ha az egyik szomszéd zónája egyesíthető a kilépő csomópont zónájával, akkor ez a szomszéd veszi át az egyesített zóna kezelését egyesíthető = „szabályos” konvex zóna keletkezik b. Ha nem, akkor az egyik szomszéd két külön zónát kezel majd

2014. október 27.

Csomópont távozása Csomópont kilép a rendszerből a. Ha az egyik szomszéd zónája egyesíthető a kilépő csomópont zónájával, akkor ez a szomszéd veszi át az egyesített zóna kezelését egyesíthető = „szabályos” konvex zóna keletkezik b. Ha nem, akkor az egyik szomszéd két külön zónát kezel majd Mindkét esetben (a és b): 1. A kilépő csomópont adatai átkerülnek a zónát átvevő csomóponthoz 2. A zónát átvevő csomópont frissíti a szomszédainak listáját 3. Az összes szomszédot értesíti a cseréről, azok pedig frissítik a saját szomszéd-listájukat 2014. október 27.

Csomópont távozása (II) 

Ha egy csomópont „angolosan” távozik (ungraceful departure)... 

Szabályos időközönként a csomópontok frissítő üzeneteket küldenek a szomszédaiknak 



Ha egy csomópont egy adott t időn belül nem kapott üzenetet az egyik szomszédjától, elindítja a TAKEOVER procedúrát  



 

Megpróbálja átvenni a „halottnak” hitt csomópont zónáját Egy TAKEOVER üzenetet küld a halott csomópont minden szomszédjának

Ha egy csomópont kap egy TAKEOVER üzenetet, összehasonlítja a saját zónáját a küldő zónájával 



A saját zonájuk koordinátái, a szomszédaik listája, illetve azok zónáinak koordinátái

Ha optimálisabb, hogy ő vegye át a zónát, saját maga küld egy új TAKEOVER üzenetet a halott csomópont szomszédainak

Az a szomszéd veszi át a zónát, aki nem kap választ a TAKEOVER üzenetére t időn belül

A halott csomóponton tárolt adatok nem elérhetőek mindaddig ameddig a forrás nem publikálja újból őket (elküldi az új csomópontnak) 2014. október 27.

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan  

presentation is based on slides by Robert Morris (SIGCOMM’01) presentation is based on slides by Daniel Figueiredo, for Peer-to-Peer and Application-Level Networking Seminar, at the University of Massachusetts at Amherst

50

Motiváció Hogyan találjuk meg az adatot egy elosztott fájl megosztó rendszerben? Publisher Key=“LetItBe” Value=MP3 data

N2

N1

Internet

N4 

N3

N5

Client ? Lookup(“LetItBe”)

Hatékony keresés a fő probléma! 51

2014. október 27.

Központosított megoldás 

Központi szerver (pl.: Napster)

Publisher Key=“LetItBe” Value=MP3 data

N2

N1

N3

Internet

DB N4  

N5

Client Lookup(“LetItBe”)

Követelmények: O(M) állapot Központi elem kiesése 52

2014. október 27.

Elosztott megoldások - I 

Elárasztás (pl.: Gnutella, Morpheus)


N2

N1

Internet

N4 

N3

N5


Legrosszabb esetben O(N) üzenet per keresés 53

2014. október 27.

Elosztott megoldások - II 

Irányított (Routed) üzenetek (Freenet, Tapestry, Chord, CAN, stb…)


N2

N1

Internet

N4 

N3

N5


Kizárólag teljes egyezés 54

2014. október 27.

Keresés kihívásai   

Hasznos kulcs egyezőség („távolság”) Alacsony üzenet továbbítási szám Mérsékelt üzenet továbbítási táblázat méret 



Robosztus működés 



mérsékelt == „pont megfelelő” gyorsan változó résztvevők

Chord: 

Fókuszban: hatékonyság és egyszerűség 55

2014. október 27.

Chord áttekintés 

P2P hash keresési szolgálat  



Lookup(key)  IP address Figyelem: a tárolt adatok különválasztva!!!

Kérdések:  



Hogyan talál meg egy csomópontot? Hogyan tartja fenn az üzenet továbbítási táblázatot? Hogyan adaptálódik a résztvevők változásához? 56

2014. október 27.

Chord jellegzetességei 

Hatékony: O(Log N) üzenet kersésenként 







ahol N a kiszolgálók (csomópontok) száma

Skálázódik: O(Log N) állapot csomópontonként Robosztus: megbirkózik jelentős résztvevő változással

Állítások bizonyításai [tech_report] 

Feltételezés: nincs rosszakaratú résztvevő

57

2014. október 27.

Chord Azonosítók (IDs)  

m bites azonosító tér a kulcsoknak és a csomópontoknak Kulcs azo. = SHA-1(key) 



Csomópont azo. = SHA-1(IP address) 





KEY=“LetItBe” !SHA-1 ID=60 IP=“198.10.10.1” !SHA-1 ID=123

Egyenletes eloszlással Hogyan lehet a kulcs azo.-at a csomóponti azo.-khoz rendelni? 58

2014. október 27.

Konzisztens Hash 

Konzisztens HASH függvény 

mind csomóponthoz és kulcshoz egy m bites azonosító 



   

SHA 1 algoritmussal (Secure Hash Standard)

m tetszőleges szám, elég nagy, hogy az ütközés valószínűsége kicsi legyen

KEY ID = SHA-1(key) NODE ID = SHA-1(IP cím) Egyenletes eloszlást követve Értékkészlet: egyazon tartomány 59

2014. október 27.

Konzisztens Hash-elés [Karger 97] 0 K5

IP=“198.10.10.1”

N123

K101

N90 

K20 Circular 7-bit ID space

N32

Key=“LetItBe”

K60

Minden kulcs az őt követő legközelebbi csomópontnál kerül tárolásra 60

2014. október 27.

Chord: Gyűrű - I 



Azonosítók egy azonosító gyűrű mentén elhelyezve modulo 2m Chord ring

61

2014. október 27.

The Chord algorithm – Construction of the Chord ring 



a key k is assigned to the node whose identifier is equal to or greater than the key‘s identifier this node is called successor(k) and is the first node clockwise from k. 62

2014. október 27.

Konzisztens Hash-elés 

Minden csomópont ismeri az összes többi csomópontot  



globális információ tárolási kényszer üzenet továbbítási táblák nagyok O(N)

Gyors keresés O(1) 0 N10

Where is “LetItBe”? Hash(“LetItBe”) = K60

N123

N32 “N90 has K60”

K60

N90

N55

63

2014. október 27.

Chord: alap keresés - I 

Minden csomópont ismeri az őt követőt a gyűrűn 0 N10 N123

Where is “LetItBe”? Hash(“LetItBe”) = K60

N32 “N90 has K60”

K60 N90 

N55

Keresési idő: O(N) 64

2014. október 27.

Chord: alap keresés - II // ask node n to find the successor of id n.find_successor(id) if (id 2 (n; successor]) return successor; else // forward the query around the circle return successor.find_successor(id);



Keresési idő ~ üzenetek száma: O(N) 65

2014. október 27.

„Mutató táblák” - I (finger tables) 



Minden egyes csomópont m számú további csomópontot tart nyilván Az előre mutató távolság exponenciálisan növekszik N112 80 + 25

N16 80 + 26

N96 80 + 24 80 + 23 80 + 22 80 + 21 80 + 20

N80 66

2014. október 27.

„Mutató táblák” - II 

Az i. bejegyzése a mutató táblának az n+2i. kulcsot követő csomópont címe N120 N16 N112 80 + 25

80 + 26

N96 80 + 24 80 + 23 80 + 22 80 + 21 80 + 20

N80 67

2014. október 27.

Chord: gyors/skálázódó keresés - I 

A mutató táblák segítségével a keresésnek O(log N) csomópontot kell bejárnia N5 N10

N110

N20 K19 N99

N32 Lookup(K19)

N80 N60 68

2014. október 27.

Chord: gyors/skálázódó keresés - II 





Minden csomópont m további bejegyzést tartalmaz Minél közelebbi a kulcs annál részletesebb információval rendelkezik róla a csomópont Általában nem biztosítja az azonnali célba jutást

69

2014. október 27.

Új érkezők 

Három lépésben (alap működés)   



Újonnan érkező mutató táblájának feltöltése Gyűrű csomópontok mutató táblájának frissítése Kulcsok cseréje

„Lusta” vagy kevésbé agresszív működés  



Csak a követő csomópont beállítása Periodikus követősuccessor, megelőzőpredecessor ellenőrzés Periodikus mutató tábla frissítés 70

2014. október 27.

Új érkező: mutató táblák Kiindulás: bármely p ismert csomópontból







Kérjük meg p-t, hogy építse fel a mutató táblánkat Táblázat visszaadása N5 N20

N36

N99

1. Lookup(37,38,40,…,100,164)

N40

N80 N60 71

2014. október 27.

Új érkező: gyűrű mutató táblák 

A gyűrű csomópontok mutató tábláinak frissítése 



új érkező a frissítés funkciót kelti életre a szomszédos csomópontokban csomópontok rekurzívan frissíttetik a további csomópontok mutató tábláit N5

1. 2.

N20

N40  successor(N36) N36 értesíti N40-et 

N99

N36.predecessor  N40.predecessor

N40.predecessor N36 N20 frissít (stabilizál)  N20.successor  N40.prececessor 

N36

3.

N40 N80 N60 72

2014. október 27.

Új érkező: kulcsok kicserélése 

A követő csomóponttól az megfelelő kulcsok átvétele 

csak a hozzárendelt tartományhoz tartozó kulcsok átadása N5

N20 N99

N36

K30

N40 K38 K30

N80

Copy keys 21..36 from N40 to N36

K38

N60 73

2014. október 27.

Új érkezők: keresés 





Korrekt mutató táblák esetén O(log N) Ha csak a követő lánc helyes, akkor is korrekt, de lassabb működés Hibás követő lánc, szünet majd újra próbálkozni 74

2014. október 27.

Hibák kezelése - I 

Csomópontok kiesése (hiba) helytelen keresést eredményezhet N120

N113

N10

N102

N85

Lookup(90)

N80  

N80 nem ismeri az őt követőt, így a keresés eredménytelen A követő lánc elégséges a keresés sikeréhez 75

2014. október 27.

Hibák kezelése - II 

Követő lista  

Az egyetlen követő helyett r soron követő csomópont regisztrációja Hiba esetén ismeri a soron következő (élő) csomópontot 



helyes keresés

Valószínűségi garancia 

r megválasztása, hogy a keresési hiba valószínűsége megfelelően alacsony legyen 

r ~ O(log N)

76

2014. október 27.

Teljesítmény elemzés 

 



Gyors keresés nagy rendszerekben Alacsony szórással a keresési időben Robosztus, még gyakori csomóponti hibák esetén is

Teoretikus eredmények összhangban a numerikus vizsgálatokkal 77

2014. október 27.

Keresés Költség: O(log N) 

összhangban a teoretikus eredményekkel Average Messages per Lookup



Number of Nodes

78

2014. október 27.

Robosztusság - I 

Statikus eset 



hiba = csomóponti hiba, nincs többszörözve a kulcs

Kulcsok egyenletesen elosztva (SHA-1) 79

2014. október 27.

Robosztusság - II 

Dinamikus eset: 

mutató tábla hibás csomópontra mutat 

hibás útvonal  

 

500 csomópont kezdetben stabilize( ) hívás átlag 30sec 1 keresés/sec (Poisson) x {join|fail}/sec (Poisson)

80

2014. október 27.

Chord implementáció 

  

3000 soros C++ kód Library amely tetszőleges alkalmazáshoz linkelhető Kis Internet teszthálón kipóbálva Funkciók 



lookup(key): azon csomópont IP címe amely a kulcsért felelős kulcs-felelősség változások terjesztése 81

2014. október 27.

Alkalmazás: Chord-DNS 

DNS keresési szolgálat 



host name  IP cím

Chord-based DNS: 

  

nincsenek root serverek nincs manuális routing information menedzsment nincs naming structure olyan objektumokat is megtalálhat amelyek nincsenek adott géphez kötve

82

2014. október 27.

Erősségek 



Teoretikus eredményeken alapul (konzisztens hash) Bizonyított teljesítmény 



analízis  „nagy valószínűséggel”

Robosztusság

83

2014. október 27.

Gyengeségek és felvetések  

Korántsem olyan egyszerű mint amilyennek látszik Új érkezők  





Legrosszabb esetben a keresés lassú lehet Kulcsok  



túl sok üzenet és frissítés (pl. kulcsok cseréje, mutató táblák) konvergencia kérdése ha a „lusta” frissítést használjuk

teljes egyezőség kulcsszó vagy regexp keresés

Biztonság  

rosszindulatú adatok (key) rosszindulatú Chord tábla

84

2014. október 27.

Irodalom 

I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, "Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications," AC Sigcomm2001, http://www.acm.org/sigcomm/sigcomm2001/p12.html

85

2014. október 27.

Elosztott adatbázisok és peerto-peer. Simon Csaba

Recommend Documents