Distributed Hash Tables

 Documents

 119 views
of 34
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Seminar: Information Management in the Web Vortrag: Distributed Hash Tables (DHTs) and Plaxton-Type Routing Vortragende: Désirée Zillmann Betreuer: Dr. Artur…
Share
Transcript
Seminar: Information Management in the Web Vortrag: Distributed Hash Tables (DHTs) and Plaxton-Type Routing Vortragende: Désirée Zillmann Betreuer: Dr. Artur Andrzejak, ZIB Vortragsdatum: 08.05.2003 Inhaltsverzeichnis  1. Distributed Hash Tables  2. Plaxton  3. Pastry  4. Tapestry  5. Übersicht  Literatur 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 2 Distributed Hash Tables  Dateien sind über einen eindeutigen Hash-Schlüssel (key) erreichbar  Knoten bekommen auch einen Schlüssel (z.B. IP-Adresse) aus demselben Namensraum  Die Hash-Funktionen sind jedem Teilnehmer bekannt  Jeder Knoten ist root-Knoten für mehrere Dateien  Jeder Knoten hält eine Tabelle mit (key, Id)- Paaren, wobei Id auf den Knoten zeigt, der die Datei zur Verfügung stellt  Anfragen werden an einen Knoten weitergeleitet, dessen KnotenId dem Schlüssel des Objekts “am nächsten” ist im Gegensatz zu Napster und Gnutella Suche nach Schlüsselworten setzen voraus, dass Dateien in erster Linie auf dem Knoten des Publishers gespeichert sind 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 3 Unterschiede bei DHT-Systemen  Aufbau des Overlay-Netzwerks  Aufrechterhaltung des Netzwerks  Suchalgorithmus lookup(key) Wichtig: Man kann die lookup-Anfrage an einen beliebigen Knoten schicken, und diese wird an den root-Knoten korrekt weitergeleitet. DHT-Systeme:  Plaxton  Pastry  Tapestry 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 4 P2P Overlay-Netzwerk P2P-Layer IP-Layer 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 5 Plaxton Jeder Knoten ist  Server für die bei ihm gespeicherten Objekte  Router, der Nachrichten weiterleitet  Client, von dem Suchanfragen ausgehen Besonderheiten:  Von jedem Objekt gibt es ggf. mehrere Kopien 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 6 Routing zu dem Knoten mit Schlüssel 5AC84B *****B  ****4B  ***84B  **C84B  *AC84B  5AC84B  Bei jedem Schritt wird von rechts nach links eine Stelle des Schlüssels angepasst. *: zufällige Werte 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 7 Neighbor table Für Knoten 1032 (b=4): b 1. Stelle 1200 3201 -- 0023 2. Stelle 2302 0112 1022 -- n 3. Stelle -- 3132 0232 1332 4. Stelle 0032 -- 2032 3032 -- Stellen, die direkt mit dem lokalen Knoten-Schlüssel übereinstimmen. Bei der Suche kann gleich in die nächste Zeile gesprungen werden. b: Basis des Schlüssels n: Anzahl der Stellen der Schlüssel 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 8 Beispiel: Routing-Schritt Knoten 1032 erhält eine Nachricht für den Knoten 1232 An welchen Knoten wird die Nachricht weitergeleitet? 1. Stelle 1200 3201 -- 0023 2. Stelle 2302 0112 1022 -- 3. Stelle -- 3132 0232 1332 4. Stelle 0032 -- 2032 3032 1032 <-> 1232 => 0232 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 9 Pointer list Ein Zeiger ist ein Tripel (Aid, y, c(x,y) ) aus  dem ID Aid des Objekt  dem Knoten y, welcher eine Kopie des Objektes besitzt  der „Entfernung“ c(x,y) von x nach y (=Kosten für das Senden einer Ein-Wort-Nachricht von x nach y) 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 10 Wichtige Prozeduren bei Plaxton  Suchen nach einem Objekt  Einfügen eines Objekts  Löschen eines Objekts 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 11 Suchen nach einem Objekt (Plaxton) root Knoten 197E sucht Objekt 4378 • routed in Richtung root • jeder Knoten überprüft auf Zeiger auf genügend nahe Kopien des Objekts 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 12 Einfügen eines Objekts (Plaxton) root Einfügen des Objekts 4378 durch Knoten 39AA (Server) • sendet Wunsch an root • hinterlässt einen Zeiger zu sich bei jedem Schritt (falls neue Kopie näher) 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 13 Zu guter Letzt (1)  Fehlerbehandlung Verbindungs- oder Knotenfehler:  ausweichen auf die secondary neighbors  zur Not zurückgreifen auf einen Knoten aus einer niedrigeren Ebene Ausfall des root-Knotens:  ein echtes Problem, da ohne ihn ein Routing zu einem existierenden Objekt nicht sichergestellt ist 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 14 Zu guter Letzt (2)  Lokalität Ausgangsvoraussetzung:  der erste Kontakt zum Netzwerk über e. Knoten in der Nähe  Ausnutzen der Entfernungsfunktion c Plaxton erreicht eine hohe Wahrscheinlichkeit, dass eine nahe Kopie des Objekts gefunden wird (falls diese existiert). 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 15 Zusammenfassung Plaxton + Die pointer list ist eindeutig + Versucht, die möglichst nahe Kopie eines Objektes zu finden + ortsunabhängiges Routing (jeder root ist die Wurzel eines spannenden Baumes im Graphen, der die Topologie des Netzwerks beschreibt) - Statische Menge von teilnehmenden Knoten - Viel Vorarbeit, um die Knotenmenge für den Routing-Prozess zu erzeugen - Plaxton geht von gefüllten neighbor tables aus - Fällt ein root-Knoten aus, dann können einige Objekte nicht mehr erreichbar sein 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 16 Pastry  ähnlich aufgebautes Overlay-Netzwerk wie Plaxton  selbst-organisierend  fehlertolerant 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 17 Pseudo-Code Pastry Routing-Prozedur (1) (1) if( L  L / 2   D  L L / 2  ){ (2) // D is within range of our leaf set (3) forward to Li , s.th. D  Li is minimal; (4) } else { (5) // use the routing table (6) Let l  shl ( D, A) ; (7) if ( Rl  null ) { Dl Dl (8) forward to Rl ; (9) } Rli: Eintrag in der routing table, i-te Spalte, l-te Zeile Li : i-te nächste KnotenId 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 18 Pseudo-Code Pastry Routing-Prozedur (2) (10) else { (11) // rare case (12) forward to T  L  R  M , s.th. (13) shl (T , D)  l (14) T  D  A D (14) } (16) } Dl : der Wert der l Zeichen im Schlüssel D shl(A,B): Anzahl d. Zeichen des gemeinsamen Präfixes von A u. B 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 19 Beispiel (Pastry) (1) KnotenId 1023 (b=4): routing table 1. Stelle 0221 -- 2230 3120 2. Stelle -- 1130 1223 1302 3. Stelle 1003 1013 -- 1032 4. Stelle 1020 1022 -- -- Stellen, die direkt mit dem lokalen Knoten-Schlüssel übereinstimmen. (es kann auch leere Einträge geben) 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 20 Beispiel (Pastry) (2) KnotenId 1023 (b=4): leaf set kleiner größer 1019 1021 1025 1031 1001 1014 1030 1029 neighborhood set 1302 1020 1130 3130 0221 2230 3120 3321 Die zugehörigen IP-Adressen sind hier nicht mit angegeben. 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 21 Selbstorganisation bei Pastry  Einfügen eines Knotens  Löschen eines Knotens 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 22 Zu guter Letzt (1)  Fehlerbehandlung Ausfall eines Knotens:  Selbstreparatur Knoten, die eine Nachricht nicht korrekt weiterleiten:  Pastry ist hier anfällig  Abhilfe: mehrmaliges Senden der Nachricht durch client, bis evtl. eine andere Route gefunden  Abhilfe: Erweitern der Selbstorganisation IP routing Anomalien im Internet:  eine Herausforderung, wenngleich Pastry hier relativ tolerant 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 23 Zu guter Letzt (2)  Lokalität ein Knoten sendet eine Nachricht an den (nicht ausgefallenen) Knoten mit einer KnotenID, die dem Schlüssel numerisch am nächsten liegt alle Einträge der routing table verweisen auf einen nahen Knoten mit geeignetem Präfix 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 24 Zusammenfassung Pastry  vollständig dezentralisiert  effizient, gut skalierbar  selbstorganisierend  fehlertolerant  anpassungsfähig an Knoten-Fehler  zuverlässig im Senden einer Nachricht an den live Knoten mit einer KnotenID, die dem Schlüssel numerisch am nächsten liegt  gute Lokalität 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 25 Tapestry  beruht im Wesentlichen auf dem Plaxton- Algorithmus  Zuordnung mehrerer root-Knoten für ein Objekt  Frage nach nahegelegenstem Nachbar bei ähnlichen Kosten  neues Konzept zur Integration neuer Knoten  Verschieben eines Objekts zwischen zwei Knoten 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 26 Tapestry Routing Mesh Jeder Knoten hat neighbor-Links zu anderen Knoten. Li: Eintrag in der Zeile i der neighbor table 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 27 Selbstorganisation bei Tapestry (1)  Erzeugung von Ersatz-root-Knoten Problem: das Netzwerk ist nicht konstant Ziel: ein Objekt bleibt erreichbar, auch wenn ein root- Knoten ausgefallen ist Idee: „Löcher“ umrunden, indem man zu dem nächsten Eintrag in derselben Zeile der neighbor table routed gibt es nur noch einen Eintrag in der Zeile (den aktuellen Knoten), dann ist dieser Knoten der root- Knoten. 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 28 Selbstorganisation bei Tapestry (2)  Integration mehrerer neuer Knoten gleichzeitig Problem: x hat ein Loch, wo y hingehört Lösung:  jeder neue Knoten versendet eine “wish list” (Bit-Vektor der Länge b) von nichterreichbaren Präfixen  jeder Rezipient überprüft, ob er einen der gewünschten Knoten erreichen kann, ggf. sendet er den multicast zurück, Präfix und Löcher können angepasst werden 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 29 Zusammenfassung Tapestry  Fokussierung auf proximity findet tatsächlich die ungefähr nächste Kopie eines Objekts und den nahegelegensten Nachbarn Nachteil: gestiegene Komplexität Die Frage, welche Bedeutung proximity in einem P2P- System haben sollte, bleibt offen  ermöglicht simultanes Einfügen von Knoten Berücksichtigung eines weitreichenden Netzwerks  Anpassungsfähigkeit an eine sich verändernde Menge von Knoten 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 30 Übersicht Algorithmus Modell Suche Speicher neighbor table, log N b log b N Plaxton pointer list b neighbor table, log N b log b N Tapestry pointer list b routing table, leaf set, b log b N  b Pastry log b N neighborhood set b: Basis des Schlüssels N: Anzahl der Schlüssel 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 31 Fazit Es gibt noch viele offene Fragen in P2P-Systemen. 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 32 Literatur(1) [1] H. Balakrishnan et al.: Looking Up Data in P2P Systems, Communications of the ACM, February 2003/Vo. 46, No. 2 [2] Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao: Distributed Data Location in a Dynamic Network, Proc. of ACM SPAA, 2002) [3] C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa: Accessing Nearby Copies of Replicated Objects in a Distributed Environment, ACM Symposium on Parallel Algorithms and Architectures 1997 [4] Antony Rowstron, Peter Druschel: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, Middleware, 2001 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 33 Literatur(2) [5] Julian Bart: Routing in Peer-to-Peer Systemen. Universität Stuttgart. Hauptseminar: Internettechnologien der nächsten Generation. Januar 2003 http://www.informatik.uni-stuttgart.de/ipvr/vs/de/teaching/ ws0203/seminars/NGI/folien/Routing_P2P-Folien.pdf [6] Marko Tomljenovic: Vergleich von Routing-Algorithmen in “Peer to Peer” – und “Mobile Ad Hoc” - Netzwerken. Universität Stuttgart. Hauptseminar: Internettechnologien der nächsten Generation. Januar 2003 http://www.informatik.uni-stuttgart.de/ipvr/vs/de/teaching/ ws0203/seminars/NGI/folien/Vergleich_P2P_Ad-Hoc- Routing.pdf 08.05.2003 Désirée Zillmann: DHTs and Plaxton-Type Routing 34
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks