FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Suche in P2P-Netzen: FASD
Fault-tolerant, Adaptive, Scalable, Distributed
search engine
Stefan Haun
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Gliederung
•
•
•
•
•
•
•
Einleitung & Motivation
Suchverfahren kurz angerissen
Freenet
FASD – Protokoll und Architektur
Simulation der FASD
Zusammenfassung
Diskussion
14.01.2004
2/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Einleitung & Motivation
• Bisher: Strukturen und Datentransfer
• Jetzt: Suchverfahren in P2P-Netzen
• Warum?
– Notwendig zur Informationsbeschaffung
– Schlechte Suchverfahren erzeugen viel Traffic
14.01.2004
3/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Zentralisierte Suche (Napster)
• Client/Server
• Zentraler Server verwaltet Speicherorte der Dokumente
• Clients stellen direkte Suchanfragen an den Server
• Nachteile:
– Suchverfahren nicht P2P-Verteilt -> Skaliert nicht
– Gezielter Angriff auf Server macht Netz unbrauchbar
– Keine Client-Anonymität, Identität bei Anfrage bekannt
– Keine Dokumenten-Anonymität
– Statt dessen: Liste mit Nutzern und ihren Dokumenten!
14.01.2004
4/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Hash-Based Index Distribution (Chord)
• Grundlage ist Hash-Basierter Index (z.B. SHA-1)
• LOOKUP-Funktion liefert Knoten zur GUID
• Chord sucht bei N Knoten mit O(log N) Schritten
• Nachteile:
– m UND/ODER-Verknüpfungen erzeugen m Suchen
– Keine effizienten Insert/Remove-Operationen
14.01.2004
5/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Broadcast (Gnutella)
• Suchanfrage wird an alle Nachbarn weitergeleitet
• Suchtiefe durch HTL (Hops To Live) begrenzt
• Nachteile:
– Sehr hoher Traffic im Netzwerk
– Dokument wird nicht gefunden, wenn „zu weit entfernt“
14.01.2004
6/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Freenet
• Netz von Knoten mit lokalem Informationsspeicher
• Jedes Dokument durch GUID gekennzeichnet
• Kein semantischer Zusammenhang zwischen Inhalt und
GUID
• Knoten auf GUID spezialisiert
• Bildung von Nachbarschaften ähnlicher GUIDs
• Suchanfrage an Nachbarknoten, die am nächsten an der
GUID sind
• Suchaufwand ist O(log N), N = Knotenzahl
14.01.2004
7/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
FASD
• Fault-Tolerant, Adaptive, Scalable Distributed search engine
• Als Such-Maschine für Freenet entwickelt
• Technisch sehr stark an Freenet angelehnt
• Kann aber auch stand-alone oder in anderen Netzen
verwendet werden
14.01.2004
8/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
FASD – Protokoll und Architektur
• Metadata Keys
• Schlüssel-Abstand (Closeness)
• Darstellung der Queries
• Suche nach Schlüsseln
• Erzeugen und Einfügen von Schlüsseln
• Speichern von Schlüsseln
• Mögliche Inkonsistenzen zwischen P2P-Netz und FASD
14.01.2004
9/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Metadata Keys
• Vektor-Repräsentation des Dokuments
• Enthalten die Häufigkeiten von Schlüsselwörtern des
Dokuments
• Berechnet nach „TFIDF“
(term frequency x inverse document frequency)
• Aus Performancegründen als Lexikon bereitgestellt
• Metadata Key besteht aus Vektor, GUID und Decryption Key
14.01.2004
10/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Schlüssel-Abstand (Closeness)
• Maß für die Ähnlichkeit zweier Metadata Keys
• Vorteile:
– Ermöglicht effizientere Suche
– Macht FASD kompatibel zum Freenet RoutingAlgorithmus
• Cosinus-Abstand (cosine correlation value) verwendet
• Größerer Cosinus-Wert -> größere Ähnlichkeit
• Wert von 1 bedeutet Gleichheit
• Nur indirekte Aussage über Gleichheit der Dokumente!
14.01.2004
11/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Darstellung der Queries
• Query = Vektor
• Gesuchte Schlüsselwörter werden auf 1 gesetzt
• Abstandsfunktion der Metadata Keys verwendet
• UND-Verknüpfungen in einem Vektor darstellbar
• ODER-Verknüpfungen in Einzelanfragen zerlegt
• Komplexe Queries in Disjunktive Normalform umgewandelt
• Beispiel: t1 ODER (t2 UND t3) ODER (t4 UND t5 UND t6)
14.01.2004
12/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Suche nach Schlüsseln
• Erweitert Freenets Routing-Algorithmus
• Begrenzungen:
– HTL (hops to live)
– Anzahl der Treffer (Top n-Liste)
– Schwellwert für die Ähnlichkeit
• Jeder Knoten erstellt eigene Top n-Liste
• Anschließend Top n der Nachbarknoten
• Ergebnisse werden zu neuer Top n-Liste zusammengeführt
und zurückgegeben
• Ergebnisse entlang des Suchpfades gespeichert
14.01.2004
13/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Einfügen von Schlüsseln
•
•
•
•
Metadata Keys vom Knoten berechnet
FASD liefert Lexikon mit Gewicht für Schlüsselwort
Berechnung vom Benutzer nicht beeinflussbar
-> Schlüssel im FASD-Layer konsistent
• Suche nach ähnlichstem Knoten
• Schlüssel wird dort eingefügt
• Inseln ähnlicher Metadata Keys
14.01.2004
14/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Speichern von Schlüsseln
• Schlüssel werden in LRU-Cache gespeichert
• Läuft der Cache über, werden überflüssige Schlüssel
gelöscht
• -> unpopuläre Schlüssel gehen verloren
• Effiziente Suche mit invertierten Indizes
• Effiziente Insert/Remove-Operationen benötigt
• Aggressives Caching: Alle Metadata Keys, die den Knoten
passieren, werden zwischengespeichert
14.01.2004
15/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Inkonsistenzen zwischen P2P/FASD
• Schlüssel wird gelöscht, Dokument existiert noch
– Wird vermieden, indem Schlüssel bei Direktzugriff aufs
Dokument neu eingefügt wird
• Dokument wird gelöscht, Schlüssel existiert noch
– Schlüssel über „cull request“ gelöscht
– Knoten entlang des Suchpfades müssen bestätigen
– Bestätigung bringt zusätzliche Sicherheit
– Unerlaubter Cull-Request hat Verbreitung zur Folge
14.01.2004
16/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Sicherheit
• FASD nutzt keine Verschlüsselung
• Bewertungsalgorithmen nicht ausgereift
• -> Weitere Forschungsarbeit notwendig!
• Lösungsansätze zu folgenden Aspekten:
– Vermeidung von Zensur
– Qualität der Dokumente
14.01.2004
17/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Sicherheit: Vermeidung von Zensur
• Knoten können Suchabfragen nicht abfangen, da nur Teil
des Suchbaums
• Bei Zensurverdacht kann Knoten umgangen werden
• Ansatz: Verschlüsselte Suchalgorithmen
• Problem: Knoten brauchen Schlüssel
• Network-Of-Trust kann Abhilfe schaffen
14.01.2004
18/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Sicherheit: Ähnlichkeit vs Qualität
• Ähnlichkeit objektiv definiert, Qualität subjektiv
• Objektiv ähnliches Dokument kann für Nutzer unbrauchbar
sein
• Mögliche Erweiterung um:
– Reputation der Dokumentenquelle
– Update-Frequenz
– Popularität
– Erwähnung in anderen Dokumenten
14.01.2004
19/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Anwendungen neben Freenet
• FASD auch ohne Freenet als Such-Layer verwendbar
• Verwendung mit Chord:
– hat sehr effiziente Methode zur Lokalisierung von
Dokumenten
– jedoch keine Suchfunktion
– Zusammen mit FASD sehr effektiv
• Stand-Alone:
– Als eigenständige Such-Applikation einsetzbar
– Datentransfer über andere Standards
14.01.2004
20/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Simulation des FASD
• FASD-Netz wurde durch Simulation geprüft
• Bedingungen:
– Initial: 20 Knoten, 2500 Dokumente
– Netz wird schrittweise auf 1000 Knoten erweitert
– Alle 200 Zeiteinheiten 300 neue Requests
– Bei Verfügbarkeitstests: HTL = 500
• Im Folgenden werden einige Ergebnisse vorgestellt
14.01.2004
21/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Durchschnittliche Suchtiefe
14.01.2004
22/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Entwicklung der Suchdauer
14.01.2004
23/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Entwicklung der Suchtiefe
14.01.2004
24/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Verhalten bei Angriff auf Knoten
14.01.2004
25/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Zukünftige Forschung
• Erweiterung der Funktion für die Schlüsselnähe
• Nutzung von verschlüsselter Suche
• Implementierung eines Trust-Networks
• Weitere Simulationen und Verbesserung der Parameter
• FASD soll in Freenet v0.6 integriert werden
14.01.2004
26/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Zusammenfassung
• Grundlegendes Problem: Auffinden von Daten ohne
zentrale Suchinstanz
• FASD löst das Problem, indem P2P-Netz als Suchmaschine
genutzt wird
• Simulationen zeigen: Ansatz von FASD kann mit den
bekannten Problemen umgehen
• Aber: Weitere Forschungsarbeiten sind noch notwendig!
14.01.2004
27/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Geschafft!
Vielen Dank für Eure Aufmerksamkeit! :)
14.01.2004
28/29
FASD – A Fault-Tolerant, Adaptive, Scalable, Distributed search engine
Diskussion
• FASD gefährdet die Verfügbarkeit eines P2P-Netzes, weil
semantisch ähnliche Dokumente konzentriert werden. Ist
es trotzdem sinnvoll, das Verfahren in Freenet zu
integrieren? Sollte es besser standalone laufen?
• Eine anderweitige Anwendung kann den Austausch des
Lexikons notwendig machen. Wie lässt sich eine Migration
der Metadata Keys realisieren?
• Eignet sich FASD auch, um nach Binärdaten zu suchen?
14.01.2004
29/29

Suche in P2P