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.

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.

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.

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
)

  byte[] ipAddress;
  long id = (long)(ipAddress[0] & 0xff ) << 24 +
            (long)(ipAddessr[1] & 0xff ) << 16 +
            (long)(ipAddress[2] & 0xff ) <<  8 +
            (long)(ipAddress[3] & 0xff ) <<  0;

Implementierung eines Peers der ISSearch Suchmaschine

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.

1. Interface 'ISPeerServerInterface' gibt die via RMI aufrufbaren Metoden des Peer-Servers vor
2. Interface 'ISPeerResultInterface' gibt die Struktur der Suchtreffer vor, die der Server dem Client zurückgeben soll.
3. Interface 'ISPeerFeatureInterface' gibt die Struktur der Features vor, die zur Konstruktion von dokumentspezifischen Feature-Vektoren der Treffer benutzt werden.

• 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

1. Downloaden und analysieren Sie die Inhalte des erweiterten Packages ISSearch.
2. 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.
3. Erweitern Sie die Beispielklasse des Servers, so dass er die externen Anfragen auf Ihrem Datenbestand auswerten und die Ergebnislisten zurückgeben kann.
4. 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).
5. 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!).
6. 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

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

  javac -classpath mein_classpath ISSearch.ISPeerServer.java
  rmic -classpath mein_classpath ISSearch.ISPeerServer

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)
      .............................

   java -Djava.rmi.server.codebase="file:c:/ISSearch/" ISPeerServer

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)

   grant codeBase "file:C:/ISSearch" 
   {
     permission java.security.AllPermission;
   };

   java -Djava.security.policy=ISPeerSecurity.dat ISPeerServer

   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)
        .................

• Ressourcen
  • Prototyp ISSearch (Interfaces und Pflichtklassen)
  • Spezifikationen des Projektes als JavaDoc: Online und Download
  • Allgemeine Problemstellung des Projektes
  • Upload der Implementierungen
  
  
  
• Dokumentation and Software, besonders hilfreich:
  • Java RMI Tutorial
  • Configuring Codebase for RMI
  • Oracle JDBC Reference
  • Oracle JDBC Developer's guide
  • Oracle SQL Reference