P2P Searching

Suchen in P2P-Netzen - P2P Searching - Result Caching

Strukturfragen

Die Möglichkeiten der Suche, wie ein P2P-Netz durchsucht werden kann, sind abhängig von der zugrunde liegenden Struktur des P2P-Netzes. Die gebräuchlichsten Varianten sind dezentrale Netze (Gnutella,Mixmaster Remailer), zentrale Netze (Napster, Skype) und DHT-basierte Netze (Chord, edonkey, emule,.... Einige Netze bilden allerdings auch eine Mischung aus den oben genannten Formen.

Suchmöglichkeiten

dezentrale Netze
- Flooding
  Beim Flooding wird eine Anfrage parallel an alle bekannten Nachbarn gestellt. Diese leiten dann die Anfrage wiederum an ihre Nachbarn weiter, bis eine bestimmte Anzahl an Weiterleitungen (Hops) erreicht ist. Diese maximale Anzahl an Hops heisst Suchhorizont und ist eine Implentationsfrage des betreffenden Netzwerks. Diese Art der Anfrageverbreitung ist sehr ressourcenintensiv und war einer der Gründe, warum die erste Gnutella-Implementierung nicht gut skalierte. Das Flooding eines Netzwerks entspricht einer Breitensuche in einem Graphen. ;o)
- Random Walk
  Der Random Walk entspricht am ehesten einer Tiefensuche, bei der eine Anfrage zunächst immer nur an einen ausgewählten Nachbarn weitergeleitet wird. Dadurch ergibt sich zwar eine geringere Netzbelastung pro Zeiteinheit als beim Flooding, allerdings dauert das Durchsuchen des gesamten Netzes auch bedeutend länger.
zentrale Netze
- In Netzwerken mit zentralem Server ist dieser meist auch die Anlaufstelle für Suchanfragen. Die teilnehmenden Clients senden nach der Anmeldung ihr Datenangebot an Server. Dieser pflegt dann lange Listen über alle angebotenen Dateien der Clients. Vom Standpunkt der Sucheffizient aus betrachtet ist dieser Ansatz sicherlich einer der Besten.
DHT-basierte Netze
- Das genaue Vorgehen bei einer Suche ist in diesen Netzen abhängig von der zugrunde liegenden Struktur. Genauere Beschreibungen zweier ausgewählt Hashbasierter Strukturen sind hier Chord und hier Kademlia zu finden. Eine oft zu beobachtende Methode ist die Abbildung von Suchbegriffen und Daten auf Hashwerte und die Verwendung von geeigneten Metriken um Schlüsselverantwortliche schnell zu finden.

Result Caching

Das Suchen lässt sich im Allgemeinen durch Zwischenspeichern und Wiederverwenden von bereits erhaltenen Ergebnissen verbessern und beschleunigen. Dabei werden die bekannten Ergebnisse einfacher, früher gestellter Anfragen dazu verwendet, um neue komplexere Anfragen zu beantworten. Suchanfragen werden im folgenden auch Anfragen, Queries oder Suchen genannt. Suchergebnisse werden gelegentlich auch (materialisierte) Views genannt.

Die Komplexität einer Suchanfrage sei dabei in diesem Kontext über die Anzahl der abgefragten Attribute $a_{j}$ definiert, wobei $a_{j}$ beliebige Metadaten der Datenobjekte sind:

Datei- (name | typ | hash)
Bibliotheksdaten
Archivierungskennzeichen
...

Die Verwendung von lokalen Caches sollte eine Selbstverständlichkeit sein. Eine interessantere Variante sind daher verteilte Caches, welche allerdings wieder neue Probleme mit sich bringen.

verteilte Caches

Eines der Probleme, die bei der Verwendung von verteilten Caches auftritt, ist die grosse Menge an möglichen, nützlichen Teilanfragen. Die Anzahl dieser verwendbaren Caches für eine Anfrage $a_{1}\wedge ...\wedge a_{k}$ ist exponentiell in $k$ . Der Ansatz eine Liste aller verfügbaren Views an einer zentralen Stelle zu halten ist nicht praktikabel, da jede Veränderung der Views dort reflektiert werden müsste. Ausserdem geht es ja bei P2P-Netzen auch darum angreifbare, zentrale Stellen zu reduzieren. Ganz abgesehen davon, dass man an einer zentralen Stelle auch gleich die Suche durchführen könnte und somit auf (verteilte) Caches gänzlich verzichten könnte.

View Tree

Eine Möglichkeit zur Verwaltung und Pflege eines verteilten Caches ist der in Efficient Peer-To-Peer Searches Using Result-Caching beschriebene View Tree.

Dieser bedient sich des verwendeten P2P-System, um darin die Ergebnisse von Abfragen zu speichern. Dafür müssen allerdings einige Voraussetzungen geschaffen werden. Als erstes werden die Anfragen in eine disjunktive Normalform (Disjunktion von Konjunktionen) umgeformt. Für die weitere Betrachtung sind dann nur noch diese konjunktiven Klauseln interessant, da eine Disjunktion der erhaltenen Ergebnisse dieser Teilanfragen leicht lokal vorgenommen werden kann. Die Ergebnisse der konjunktiven Teilanfragen werden dann als Datenobjekte innerhalb des P2P-Netzes abgelegt. Dabei wird der notwendige Hashwert aus einer Konkatenation der abgefragten Attribute berechnet. So würde z.B. bei Chord die View $(a\wedge b)$ auf dem Knoten Successor( $H(a\wedge b)$ ) abgelegt werden. Dieses Verfahren kann und muss auch für "literale" Anfragen verwendet werden, sprich bei Anfragen die nur ein Attribut beinhalten. Ein Designkriterium für den View Tree war, dass bei jedem Suchschritt Informationen zu mindestens einem weiteren noch unbekannten Attribut geliefert werden soll. Dazu werden die bereits "materialisierten" Views in hierarchischer Form im P2P-System abgelegt und zwar so, dass jedes neue Ergebnis "unterhalb" seines längsten Prefixes gespeichert wird. Das bedeutet, dass ein neues Ergebnis einen Knoten als Vaterknoten erhält, dessen gespeicherte View bzw. die zugehörige Anfrage in ihrer kanonischen Darstellung die längste vollständig in der neuen Query enthaltene ist. Eine weitere wichtige Voraussetzung ist, dass alle Einzelattributanfragen "materialisiert" sind, also im System gespeichert sind.

Im folgenden Bild ist beispielhaft eine Suche nach den Attributen "cbagekhilo" angedeutet. Dort sind auch die "längsten Prefixe" zu erkennen.

Um ein Entarten des Baumes zu verhindern, werden die Attribute nicht immer in der selben Reihenfolge normalisiert (z.B. "alphabetisch" im theoretischen Beispiel), sondern es wird stattdessen eine deterministische Permutation der Attribute verwendet. Solch ein Entarten tritt immer dann auf, wenn ein Attribut besonders häufig zur Suche herangezogen wird (z.B. Dateiname in Filesharing-Systemen). Bei Bedarf werden Kindknoten auch umsortiert, z.B. wenn eine View eingefügt wird, die ein längster Prefix für eine bereits vorhandene View ist.

Der Pflegeaufwand für den ViewTree hält sich in Grenzen. Kinder und ihre Eltern tauschen in regelmässigen Abständen Nachrichten aus und reagieren entsprechend auf das Ausbleiben von Nachrichten. Sollte ein Kindknoten nicht erreichbar sein, wird dieser und der gesamte darunter hängende Teilbaum vom Elternknoten verworfen. Stellt hingegen ein Kind fest, dass sein Elternknoten nicht mehr erreichbar ist, fügt es sich selbst neu in den ViewTree ein.

Mit dem ViewTree-Ansatz lässt sich eine Menge Netzwerkverkehr einsparen. Studien haben gezeigt, dass eine Reduktion der versendeten Datenmengen um 90% möglich sind.

DiCAS

Ein weitere Ansatz zum Thema verteilte Caches beschreibt DiCAS. Dabei werden speziell unstrukturierte Netzwerke wie das Gnutella-Netz betrachtet.

Sollte hierzu eine Ausarbeitung gewünscht werden, bitte ein Mail an mich:o)