Programmieraufgabe 5 (Peer-to-Peer Suchmaschine) - optional
|
|
|
Informationssysteme
Sommersemester 2005
From: Di, 28.06.2005
Upload deadline: Di, 12.07.2005 09:15 MEZ (optional)
|
Ziel dieser optionalen Programmieraufgabe ist es, die verteilte Web-Suche im Rahmen eines dezentralisierten Peer-to-Peer (P2P) Netzwerks, gebildet
aus den Teilnehmern des ISSearch Projektes, zu implementieren.
Allgemeine Problemstellung
In einem P2P Netz sind alle Computer gleichberechtigt und können sowohl Dienste in Anspruch nehmen (in unserem Fall, die Suche auf
den Daten von mehreren Peers durchführen) als auch Dienste zur Verfügung stellen (in unserem Fall, die Suche auf dem lokalen
Datenbestand
für andere Benutzer anbieten). Die wichtigsten allgemeinen Vorteile der P2P Systeme sind:
- Ressourcen: die immense Zahl der potentiell verfügbaren Rechner im Internet ermöglicht die Lösung von anspruchsvollen
rechnerischen Aufgaben bzw. die verteilte Suche auf immensen Datenbeständen der konventionellen Desktop-Rechner, die ans
Internet angeschlossen sind und durch den Benutzer teilweise für P2P-Aktivitäten freigegeben sind (z.B. im Leerlauf).
- Geringe Kosten: da die Aufgaben des Netzes auf mehrere Rechner verteilt sind, wird keine zusätzliche Hardware benötigt.
- Robustheit: es gibt keine zentralen Server, deren Überlastung bzw. Ausfall zum Stillstand des Netzes führen könnte.
Die P2P Technologie wurde bekannt hauptsächlich durch File-Tauschbörsen, bei denen die Teilnehmer untereinander Dateien kopieren
(Napster, Kazaa, Gnutella, etc.). Es gibt allerdings viele weitere Anwendungen, die
von den Vorteilen der P2P-Architektur profitieren können. Dazu gehört auch die dezentralisierte Web-Suche, bei der mehrere Benutzer
ihre lokalen Datenbestände des Crawls für alle anderen verfügbar maachen und gleichzeitig die Crawl-Daten aller anderen Teilnehmer für die
eigene Suche in Anspruch nehmen können.
Im Gegensatz zu den zentralisierten Systemen (z.B. die Web-Suchmaschine google),
ist die Information über den gecrawlten Datenbestand verteilt über mehrere Peers. Jeder Peer kennt die Statistiken seines eigenen Datenbestandes
und verfügt über geeignete Indexstrukturen für die schnelle lokale Suche, hat jedoch keine globale Sicht auf alle verfügbaren Knoten und deren Treffer im Netzwerk.
Die fehlenden globalen Indexstrukturen (in unserem Fall, die Zuordnung zwischen den Suchbegriffen und den Peers, die passende Ergebnisse liefern können) können
auf verschiedene Arten realisiert werden. Dieses Problem wird in existierenden P2P Arhitekturen unterschiedlich gelöst:
- P2P Netzwerke ohne Indexstrukturen (z.B. Gnutella) geben die Anfrage einfach an alle benkannten Nachbarn weiter.
Die Ergebnisse werden von jedem angefragten Peer direkt zum Initiator der Suche zurückgeschickt. Um die dabei entstehende Netzlast in Grenzen zu halten,
ist die Tiefe
der Weiterletung solcher Anfragen typischerweise strikt beschränkt.
- P2P Netzwerke mit partiellen Indexstrukturen (z.B. Kazaa) verwenden sogenannte Super-Peers. Alle Knoten im P2P
Netz sind entweder selbst Super-Peers (stärkere Server mit schneller Netzverbindung), oder sind einem Super-Peer zugeordnet. Die Super-Peers
beinhalten u.a. partielle Indexstrukturen (für einen Bereich, der alle Knoten des P2P-Netzes unter dem zuständigen Super-Peer zusammenfasst).
Die Anfrage des Initiators wird zuerst von seinem Super-Peer bearbeitet. Nur wenn dieser keine passenden Ergebnisse in seinem Zuständigkeitsbereich
finden kann, wird die Anfrage an andere Super-Peers weitergereicht.
- P2P Netzwerke mit einem verteilten Index (z.B. Chord-basierte Anwendungen) verwenden einen globalen Suchindex, dessen Elemente nach einem
bestimmten Prinzip zwischen allen Knoten des Netzes verteilt sind. Solche Netzwerke benutzen spezielle Routing-Mechanismen, um die Elemente
der Anfrage (z.B. einzelne Suchbegriffe) an die Knoten weiterzureichen, die für entsprechende Indexlisten zuständig sind.
Die Indexknoten übermitteln ihre
Indexlisten an den Initiator der Suche, der daraufhin die besten Ziel-Peers auswählt und an diese seine Anfrage nun direkt weiterleitet.
- P2P Netzwerke mit einem Indexserver (z.B. Napster) benutzen eine zentrale Stelle, die zu jedem Suchbegriff eine Liste der Peers bereitstellt,
die passende Ergebnisse liefern können. Der Server agiert dabei als Vermittler zwischen dem Initiator der Suche und den Anbietern mit passenden Inhalten.
Die eigentlichen Treffer bekommt der Initiator direkt von den angefragten Peers.
Die letztere Variante soll im Rahmen des Projektes ISSearch realisiert werden. Die Rolle des zentralen Indexservers übernimmt bei uns eine spezielle Datenbank-Instanz,
die von allen Peers gemeinsam genutzt wird.
Hinter jedem Peer verbirgt sich eine laufende Instanz des Projektes ISSearch mit ihrem gecrawltem Datenbestand.
Jeder aktive Peer speichert in der Datenbank seine Verbindungsdaten und die Liste der verfügbaren Features (Terms zusammen
mit einigen Statistiken des lokalen Datenbestandes),
zu den er passende Ergebnisse liefern kann. Nun kann jeder Peer, der als Initiator der Suche agiert, die besten Partner für seine Anfrage
bestimmen und an diese die Query weiterleiten. Anschliessend werden die zurückgegebenen Trefferlisten zusammengelegt, um die gemeinsame Rangliste
der verteilten Suche zu erzeugen.
Implementierung der Datenbank-Schnittstelle
Die Schnittstelle für die Kommunikation zwischen den Peers bildet eine
Datenbank-Instanz, deren Zugangsdaten ab sofort auf Ihrer persönlichen Teilnehmerkarte erscheinen. Die aktiven Peers haben gemeinsamen Zugriff
auf folgende Datenstrukuren:
- Relation 'peers'. Diese Relation enthält Systeminformationen zu jedem aktiven Peer (ID des Peers, Port und Service-Name des Suchdienstes),
damit andere Peers mit ihm eine Verbindung
herstellen und die Suche auf seinem Datenbestand durchführen können.
- Relation 'features'. Diese Relation enthält alle Features (Wortstämme), zu den der Peer die Ergebnisse liefern kann. Zu jedem
Wortstamm werden zusätzlich die Gewichte DF (Document Frequency) und IDF (Inverse Document Frequency) gespeichert.
Für die Dokumentsammlung der Größe N, in der n Dokumente mit dem gegebenen Wortstamm enthalten sind, werden diese
Statistiken wie folgt definiert: DF = n und IDF = N/n.
- Relation 'properties', die für die Speicherung der zusätzlichen Meta-Informationen durch den Peer in Form von generischen [key:value] Paaren
vorgesehen ist. Die Meta-Informationen sind optional und können bei Bedarf für die Erweiterung und Optimierung der Suche innerhalb Ihrer Implementierung
genutzt werden. Hier können u.a. die besten Features des Datenbestandes, Top-Treffer für bestimmte Queries, die charakteristischen Dokumente der Sammlung,
etc. gespeichert werden. Ihre Implementierung sollte in der Lage sein, sowohl Peers mit speziellen optimierten Meta-Informationen
(z.B. ihre eigene Implementierung) als
auch die sonstigen Peers ohne Meta-Information (die Suchmaschinen anderer Kursteilnehmer) bei der Suche zu berücksichtigen.
Das Datenbank-Schema ist definiert wie folgt:
view peers
(
id number primary key, -- id of the peer
port number default 1099, -- port of the search service
service varchar2(100) not null, -- name of the search service
numDocs number not null -- total number of available documents on ths peer
)
table features
(
id number not null, -- id of the peer
term varchar2(500) not null, -- term (word stem) of the feature
df number default 0, -- DF (document frequency) weight of the feature
idf number default 0, -- IDF (inverse document frequency) of the feature
FOREIGN KEY (id) REFERENCES peers(id) ON DELETE CASCADE
)
table properties
(
id number not null, -- id of the peer
name varchar2(1000) not null, -- name of the meta property
value varchar2(1000) not null, -- value of the meta property
description varchar2(1000) default 'No description',
FOREIGN KEY (id) REFERENCES peersTable(id) ON DELETE CASCADE
)
Die IDs der Peers dienen zur eindeutigen Identifikation der Knoten in unserem P2P Netzerk. Diese numerischen Werte
werden umkehrbar aus den 4 bytes der IP-Adresse des Rechners wie folgt gebildet:
byte[] ipAddress;
long id = (long)(ipAddress[0] & 0xff ) << 24 +
(long)(ipAddessr[1] & 0xff ) << 16 +
(long)(ipAddress[2] & 0xff ) << 8 +
(long)(ipAddress[3] & 0xff ) << 0;
Die Kommunikation zwischen den Peers und der Datenbank erfolgt durch SQL-Befehle mit Hilfe der JDBC-Schnittstelle.
Implementierung eines Peers der ISSearch Suchmaschine
Die Implementierung eines Peers besteht aus zwei Komponenten: dem Server und dem Client. Der Server stellt die Peer-Suchmaschine dar,
die die Anfragen anderer Peers auf dem lokalen Datenbestand ausführt und die Ergebnisse an diese Peers zurückgibt. In diesem Sinne ist die Funktionsweise
des Servers sehr ähnlich zu dem Query-Processor des Projektes und basiert auf der Implementierung aus der Programmieraufgabe 4.
Der Client ist für die Verarbeitung
der eigenen Abfragen des Peers
(Auswahl der Peers für die Weiterleitung der Query mit Hilfe der zentralen Datenbank-Instanz,
Weiterleitung der Query, Aggregation der erhaltenen Ergebnisse und
Erstellung der gemeinsamen Rangliste der Top-Treffer) zuständig.
Der Funktionsumfang beider Komponenten lässt sich wie folgt zusammenfassen:
Server:
- Beim Start: Systeminformationen des Peers und die Feature-Liste in die zentrale Datenbank-Instanz eintragen.
- Im Betrieb: auf Anfragen anderer Peers warten. Bei Erhalt einer Anfrage diese auf dem lokalen Datenbestand ausführen und die
vorgegebene Zahl der besten Treffer im normierten Format zurückgeben.
- Beim herunterfahren: Systeminformationen des Peers aus der zentralen Datenbank entfernen.
Client:
- Die Anfrage des Benutzers im spezifizierten Format (Aufgabe 4) entgegennehmen, parsen und analysieren.
- Mit Hilfe der zentralen Datenbank einen (oder mehrere) am besten geeignete Peers für die Anfrage auswählen, die geeignete Treffer liefern können.
- Die Anfrage an alle ausgewählten Peers im normierten Format weiterleiten; von jedem angefragten Peer eine Rangliste der besten Treffer im normierten Format
entgegennehmen. Die Ranglisten einzelner Peers zu einer gemeinsamen Trefferliste zusammenführen.
- Die besten Treffer der Rangliste (z.B. top 10) dem Benutzer als Endergebnis der Suche präsentieren.
Die Kommunikation zwischen dem Initiator der Suche (Client) und dem Ziel-Peer, auf dessen Datenbestand die Suche stattfinden soll (Server) erfolgt im Projekt
ISSearch mit Hilfe von Java RMI (Remote Method Invocation). Die Schnittstellen der Kommunikation
sind aus den Kompatibilitätsgründen durch Vorgabe der Interfaces normiert und sollten auf keinen Fall modifiziert werden:
- Interface 'ISPeerServerInterface' gibt die via RMI aufrufbaren Metoden des Peer-Servers vor
- Interface 'ISPeerResultInterface' gibt die Struktur der Suchtreffer vor, die der Server dem Client zurückgeben soll.
- Interface 'ISPeerFeatureInterface' gibt die Struktur der Features vor, die zur Konstruktion von dokumentspezifischen
Feature-Vektoren der Treffer benutzt werden.
Das Package ISSearch enthält funktionsfähige Beispielklassen (ISPeerServer.java, ISPeerClient.java) für diese Interfaces.
Die Beispielklassen ermöglichen eine einfache Client-Server Testsuche via RMI. Ausserdem enthält das Paket die Klasse ISPeerTools.java,
die eine Bibliothek von technischen Hilfsfunktionen des Projektes enthält (Auslesen der lokalen IP-Adresse, Konvertierung der IP-Adresse in eine Peer-ID, Konvertierung der Peer-ID
in die entsprechende IP-Adresse, Generierung von RMI-Verbindungsdeskriptoren, Herstellung der Verbindung zu einem RMI-Server,
Ausführen der ISSearch-Abfragen via RMI).
Die inhaltliche Realisierung der folgenden Aspekte des verteilten Suchsystems bleibt Ihnen komplett überlassen:
- Auswahl der besten Peers für die Weiterleitung der Anfrage.
- Ergänzug der o.a. Peer-Statistiken durch zusätzliche Peer-Metainformationen für die optimierte Auswahl der geeeigneten Peers.
- Integration der partiellen Trefferlisten von mehreren Peers in eine gemeinsame Rangliste.
Vorgehensweise
Wir empfehlen bei der Bearbeitung dieser Programmieraufgabe folgende Vorgehensweise:
- Downloaden und analysieren Sie die Inhalte des erweiterten Packages ISSearch.
- Konfigurieren Sie die Pfade in der Security-Policy ISPeerSecurity und dem Server-Startup-Script StartRMIServer.bat.
Starten Sie in einem separaten Fenster den RMI-Repositorydienst rmiregistry.
Versuchen Sie, den Beispiel-Server ((ISPeerServer.java) zu starten. Versuchen Sie, den Beispiel-Client (ISPeerClient.java) im zweiten
separaten Fenster zu starten und die Test-Abfrage auf dem lokalen RMI-Server auszuführen.
- Erweitern Sie die Beispielklasse des Servers, so dass er die externen Anfragen auf Ihrem Datenbestand auswerten und die Ergebnislisten zurückgeben kann.
- Erweitern sie die Beispielklasse des Servers, so dass er in der zentralen Datenbank eine Eintragung vornimmt (und somit Ihre Daten nun für andere Peers
verfügbar macht).
- Erweitern Sie die Beispielklasse des Clients, damit er mit Hilfe der zentralen Datenbank-Instanz den besten Peer für die Anfrage aussucht und an ihn die Anfrage
weiterleitet (der beste Peer muss nicht zwangsweise Ihr eigenes System sein!).
- Erweitern Sie die Beispielklasse des Clients, damit er mehrere geeignete Peers für die Auswertung der Query aussucht, an alle diese Peers die Anfrage weiterleitet,
die erhaltenen Ergebnisse zu einer Rangliste zusammenführt, und die Top-10 der Trefferliste dem Benutzer zurückgibt.
Typische Probleme
Die Anfangsprobleme liegen überwiegend im Bereich der RMI-Programmierung.
Um den Testbeispiel aus dem Paket ISSearch zu starten,
sind folgende Schritte erforderlich:
1. Starten Sie den Java RMI-Repositorydienst rmiregistry in einem separaten Fenster:
rmiregistry
2. Starten sie den Peer-Server in einem zweiten separaten Fenster:
java -classpath mein_classpath ISSearch.ISPeerServer
3. Starten sie den Such-Client in einem dritten separaten Fenster:
java -classpath mein_classpath ISSearch.ISPeerClient
Nach den Änderungen im Client oder Server müssen diese neu kompiliert werden. Der Client ist ein 'normales' Java-Programm,
dass mit dem Compiler javac direkt kompiliert werden kann:
javac -classpath mein_classpath ISSearch.ISPeerClient.java
Die Server-Klasse wird zuerst auch mit dem Compiler javac in den Bytecode übersetzt. Anschliessend muss sie mit dem
RMI-Compiler rmic (im JDK-Lieferumfang enthalten) kompiliert werden. Dabei werden Hilfsklassen
ISPeerServer_Skel.class und ISPeerServer_Stub.class erzeugt, die für die Kommunikation via RMI benötigt werden.
javac -classpath mein_classpath ISSearch.ISPeerServer.java
rmic -classpath mein_classpath ISSearch.ISPeerServer
Am häufigsten kommt beim ersten Start des Peer-Servers die folgende Fehlermeldung vor:
java.rmi.ServerException: RemoteException occurred in server thread; nested exception is:
java.rmi.UnmarshalException: error unmarshalling arguments; nested exception is:
java.lang.ClassNotFoundException: examples.callback.ISPeerServer_Stub
java.rmi.UnmarshalException: error unmarshalling arguments; nested exception is:
java.lang.ClassNotFoundException: examples.callback.MessageReceiverImpl_Stub
java.lang.ClassNotFoundException: examples.callback.MessageReceiverImpl_Stub
at sun.rmi.transport.StreamRemoteCall.exceptionReceivedFromServer(Compiled Code)
at sun.rmi.transport.StreamRemoteCall.executeCall(Compiled Code)
at sun.rmi.server.UnicastRef.invoke(Compiled Code)
at sun.rmi.registry.RegistryImpl_Stub.rebind(Compiled Code)
at java.rmi.Naming.rebind(Compiled Code)
.............................
Diese Fehlermeldung deutet darauf hin, dass die zuvor erzeugten RMI-Hilfsklassen
(ISPeerServer_Skel.class und ISPeerServer_Stub.class) vom System nicht gefunden werden.
In diesem Fall muss Java beim Start des Peer-Servers
in der Komandozeile den Pfad zu den Klassen des Packages ISSearch explizit enthalten, zum Beispiel:
java -Djava.rmi.server.codebase="file:c:/ISSearch/" ISPeerServer
Ein weiteres Problem kündigt sich typischerweise durch folgende Fehlermeldung an:
java.security.AccessControlException: access denied (java.net.SocketPermission 127.0.0.1:1099 connect,resolve)
at java.security.AccessControlContext.checkPermission(AccessControlContext.java:269)
at java.security.AccessController.checkPermission(AccessController.java:401)
at java.lang.SecurityManager.checkPermission(SecurityManager.java:524)
at java.lang.SecurityManager.checkConnect(SecurityManager.java:1026)
at java.net.Socket.connect(Socket.java:446)
at java.net.Socket.connect(Socket.java:402)
at java.net.Socket.(Socket.java:309)
at java.net.Socket.(Socket.java:124)
Diese Fehlermeldung deutet darauf hin, dass die aktuelle Sicherheits-Richtlinie der JVM die Anmeldung
des Peer-Servers beim RMI System verhindert hat.
Durch die Definition einer ergänzung zur Sicherheits-Richtlinie kann diese Sperre für Ihre Klassen aufgehoben werden.
Die Sicherheits-Richtlinie von Java wird mit Hilfe einer kleinen Textdatei
ergänzt, die wie folgt aussehen könnte (beliebigen Text-Editor oder Java-Tool policytool aus dem JDK verwenden):
grant codeBase "file:C:/ISSearch"
{
permission java.security.AllPermission;
};
In diesem Fall muss Java beim Start des Peer-Servers
in der Komandozeile den Pfad zu der Policy-Textdatei explizit enthalten, zum Beispiel:
java -Djava.security.policy=ISPeerSecurity.dat ISPeerServer
Insgesamt könnte der Aufruf des Peer-Servers so aussehen:
java -Djava.security.policy=ISPeerSecurity.dat -Djava.rmi.server.codebase="file:c:/ISSearch/" -classpath mein_classpath ISPeerServer
Es ist sicherlich bequemer, eine kleine Batch-Datei mit dem erweiterten Java-Aufruf zu benutzen.
Im Paket ISSearch sind ein Policy-File und ein Batch-File
für den Start des Peer-Servers bereits enthalten. Nach der Anpassung der Pfade
sollten sie sofort funktionieren.
Die folgende Fehlermeldung deutet darauf hin, dass die Netzverbindung zwischen dem Client und dem Server
nicht hergestellt weden konnte.
java.rmi.ConnectException: Connection refused to host: 123.45.67.89; nested exception is:
java.net.ConnectException: Connection refused: connect
at sun.rmi.transport.tcp.TCPEndpoint.newSocket(TCPEndpoint.java:567)
at sun.rmi.transport.tcp.TCPChannel.createConnection(TCPChannel.java:185)
at sun.rmi.transport.tcp.TCPChannel.newConnection(TCPChannel.java:171)
at sun.rmi.server.UnicastRef.newCall(UnicastRef.java:313)
at sun.rmi.registry.RegistryImpl_Stub.lookup(Unknown Source)
at java.rmi.Naming.lookup(Naming.java:84)
at ISPeerTools.getServer(ISPeerTools.java:24)
at ISPeerClient.main(ISPeerClient.java:36)
.................
In diesem Fall sollten die Einstellungen der lokalen Firewall ueberprueft werden. Die RMI-Kommunikation
wird normalerweise über den Port 1099 abgewickelt. Auf dem Server-Rechner sollten eingehende, auf dem Client-Rechner ausgehende
Verbindungen für diesen Port freigeschaltet sein. Es ist aber auch möglich, dass der Server inzwischen die Arbeit
beendet hat (die explizite Abmeldung ist in unserem P2P-Netzwerk optional). Ihr System sollte in der Lage sein,
solche Timeouts abzufangen und die Abfrage ggf. auf andere verfügbaren Peers umzuleiten.