Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid Middleware
Andreas Walter28. April 2006
Fakultät für InformatikInstitut für Programmstrukturen und Datenorganisation
BetreuerProf. Dr.-Ing. Klemens Böhm, Dipl.-Wirtsch.-Inform. Stephan Schosser
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
Prognose
Bis Ende 2006 250 Millionen Breitbandanschlüsse weltweit
Ermöglicht
Ausnutzen überschüssiger Bandbreite, Speicher und Rechenleistung
Ziel
Kooperativer Aufbau einer Datenbasis, hohe Abdeckung des Webs
Crawler
Laden von Webseiten, Verfolgen unbekannter Links
Peer-2-Peer Ansatz
Gleichberechtigte Knoten, kommunizieren untereinander
Grid - Ansatz
Rechner über Middleware zusammenschalten, Aufgaben teilen
Webseite bekannt?
Webseite bekannt?
Crawler
CrawlerCrawler
Crawler
Crawler
WebViele Milliarden Webseiten
SuchmaschinenbetreiberBetreiben aufwendige Rechenzentren
Steuerung
Hauptziele• Schlankes Steuersystem• Schnellstmögliche
Kommunikation• Hochperformante
Crawler
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungIntro
Verarbeitung
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
1 / 13
Inhalt• Grid-Middleware• Crawler• Dienste• Evaluation• Zusammenfassung
Virtuelle Organisationen, Globus-Toolkit, Dienste
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungIntroIntro
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
Arbeitsablauf, Komponenten,Anforderungen
Verzeichnis- und Steuerdienste, Speicherdienste, Crawler
Hochperformante Crawler durch kurze Wege der Kommunikation
2 / 13
Ziel: Aufbau eines Grids
Rechner über Internet verbinden, leistungsfähigere Anwendungen
Virtuelle Organisation• Sicherheitsanforderungen• Anpassungsfähigkeit• Leistungsanforderungen• Fairness• Heterogenität der Systeme
Globus Toolkit: Grid Middleware• SSL: Authorisierung• Verzeichnisdienste• Zugang auf Komponenten• Lastverteilung
Einheitliche Infrastruktur
Ressourcen als Dienste• Einheitliche Schnittstelle • Definition Dienstmerkmale• Eindeutige Namen
Anpassung auf System
Nutzung heterogener Systeme
Grid Services• Webservices + Zustände• Verwendung von XML-Standard
zur Kommunikation• Installation in einheitlicher
Infrastruktur
Grid-Services
Dienste auf einheitlicher Infrastruktur, Nutzung heterogener Systeme
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungGrid-Middleware
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
3 / 13
Komponenten
• Steuerung -> Filterung,
Verteilung• Speicherdienste ->
Webseiten speichern• Crawler -> Webseiten
laden, auswerten
Als Dienste in einem
Grid aufbauen
Anforderungen
Bandbreite, Speicherplatz, Rechenleistung
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungCrawler
Pro Webseite ca. 15 kByte neuer Daten, ca. 8 neue LinksReferenzarchitektur eines verteilten CrawlersystemsSteuerung, Verarbeitung und Speicherung getrennt
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
4 / 13
Gridaufbau mit Standarddiensten von Globus-Toolkit
Verzeichnis-,Steuer- und Speicherdienste und Crawler
Speicherdienst
Crawler
Crawler
Speicherdienst
SteuerdienstSteuerdienst
Verzeichnis- dienst
Lokale Nähe
Zuordnung
Steuerdienst
Steuer- / Verzeichnisdienst
Verzeichnis- dienst
Verteiltes Hauptsystem
Erweiterungen: Ziele
Performanz, Verteilung, Verfügbarkeit, Skalierbarkeit, Effizienz
Minimierte Kommunikation
CrawlerKurze Wege
Verwendung bewährter Verfahren
Fertig ?!?
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungCrawler
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
5 / 13
Optimierungen
Dienste des verteilten Hauptsystems | Steuerung | Verzeichnis
Weltweit
Nordamerika
Kanada
USA
Crawler
Crawler
= > Hierarchischer Verzeichnisdienst
Schicht 1: CoreNet-List• Kennt Verzeichnisdienste in Lokationen• Anfragen an Gesamtnetz
Schicht 2: Component-Router• Kennen Dienste einer Lokation• Zuordnung Crawler / Speicher zu Steuerdiensten
CoreNet
Steuer-dienst
Kurze Kommunikationswege
Ermöglichen schnelleren Datenaustausch bei gleicher Verbindung
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungVerzeichnisdienste
Lokale Nähe
Verteilung
Zuordnung
Lokale Nähe
Verteilung
Zuordnung
Lokale Nähe
Verteilung
Zuordnung
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
6 / 13
Minimierte Kommunikation
Zellen und Areas
Verteilstrategien für Domains
Dienste des verteilten Hauptsystems | Steuerung | Verzeichnis
Steuerung
Speicherdienst Speicherdienst
Crawler
Lokation: Deutschland
Filterung URLs
Neue URLs Neue URLs
Filterung URLs
Problem: Filterung aufwendig
Effiziente Filterung
URL := <Domain> + <Pfade> + <Dateiname>
Steuerdienste
Unbekannte Webadressen zur Bearbeitung an Crawler weitergeben
Speicherdienst Speicherdienst
Crawler
SteuerungStatistiken• Mehrere hundert Webseiten pro Präsenz• Etwa 8 Links pro Webseite• Mehr als 75 Prozent der Links auf interne Ziele
Filterung URLs
ZuordnungDomains
Menge an Domains
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungSteuerdienste
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
7 / 13
Trennung: Domain - URL
Speicherdienst• feste Zuteilung von Domains
• Filterung URLs dieser Domains
Steuerdienst• Zuordnung Domain -> Speicherdienst
=> Minimierte Kommunikation
Lokation: USA
Menge an Domains
Speicherdienst Speicherdienst
Steuerung
Crawler
Austausch von Domains
Austausch von URLs
Minimierte Kommunikation
Zellen und Areas
Verteilstrategien für Domains
Dienste des verteilten Hauptsystems | Steuerung | Verzeichnis
Zellen und Areas
Trennung von Vermittlung und Verarbeitung (vgl. Mobilfunk GSM)
Lokation
Zelle: Steuerdienst, Speicherdienste, Crawler | Menge an Domains
Area: Vermittlung der Zelle, in der eine Domain bearbeitet wird Area• kennt Domains in Zellen• dauerhafte Speicherung der Zuordnung Anfragen an Gesamtsystem Schlanker Steuerdienst in Zelle
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungSteuerdienste
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
8 / 13
USA
Europa
UK
Afrika
AsienSüdamerika
Kanada
Minimierte Kommunikation
Zellen und Areas
Verteilstrategien für Domains
Dienste des verteilten Hauptsystems | Steuerung | Verzeichnis
Hochperformante Crawler
Kürzeste Wege der Kommunikation zwischen Crawler und Web-Server
Messwerte• Antwortzeit• Ladezeit• Lokationen
Verteilstrategien für Domains
Ziele
• Minimierung von Antwort- und Ladezeiten
• Entlastung der Zwischensysteme im Internet
• Kurze Ressourcenbelegung auf Web-Server
=> Mehr Webseiten in gleicher Zeit bearbeiten
1. Standardstrategie
• Zelle, in der Domain zuerst auftritt, bearbeitet diese
• Messung von Antwort- und Ladezeiten
• Ermittlung der lokalen Verteilung von Domains
=> Sind umfangreichere Strategien sinnvoll ?
2. Bearbeitung lokal naher Domains
• Zellen prüfen, ob Domain aus eigener Lokation
• Bearbeitung lokal naher Domains
• Andere Domains an lokal nahe Zellen senden
=> Immer kürzeste Wege, aber „unfair“
3. Optimierung von Durchschnittswerten
• Zellen prüfen, ob Domain aus eigener Lokation
• Bearbeitung lokal naher Domains
• Sonst Austauschangebot mit lokal nahen Zellen
=> Faire Möglichkeiten der Optimierung
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungSteuerdienste
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
9 / 13
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungEvaluation
Nordamerika
UK
Deutschland
Europa Realwelttest Planet-Lab
Ziel: Vergleich der Verteilstrategienfür Domains
4 LokationenNordamerika, Europa, Deutschland, UK
150 RechnerAutomatisierte Installationvon Globus-Toolkit und Grid-Services
ProblemStändig reproduzierbare Nichterreichbarkeit benötigter Ports nach einigen Anfragen an Grid-Services.
VermutungPlanet-Lab Rechner waren mit Globus-Toolkit überfordertFehler trat in Labortest nicht auf
Evaluation
Verteilstrategien für Domains zur Erstellung hochperformanter Crawler
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
10 / 13
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungEvaluation
Nordamerika
UKDeutschland
Europa
Realwelttest Planet-LabAlternativer Aufbau• Grid-Services in Laborumgebung• Crawler in Planet-Lab
EvaluationVerteilstrategien für Domains zur Erstellung hochperformanter Crawler
Messung vonReaktions- und Ladezeit, lokale Verteilung der Domains
Ableitung: Verteilstrategien sinnvoll?
Reaktions- und Ladezeiten Lokale Verteilung Domains nach Ländern
Halbe Reaktions- und Ladezeit in nahen Gebieten
Etwa 40 Prozent der Webseiten austauschbar
Mehr als 50 Prozent der Domains aus Nordamerika
Strategie: Bearbeitung lokal naher DomainsSinnvoll, wenn mehr als 50 Prozent der Dienste / Crawler in Nordamerika
Strategie: Optimierung von Durchschnittswerten
Evtl. doppelte Verarbeitungsgeschwindigkeit für 40 Prozent der Webseiten
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
11 / 13
Grid-Middleware
Standards XML / SSL
Status Zusammenfassung
Globus ToolkitFoster; Kesselman; The Anatomy of the Grid: Enabling Scalable Virtual Organisations; Lecture Notes in Computer Science, Volume 2150; 2001
Grid-ServicesCzajkowski et al. ; From Open Grid Services Infrastructure to WS-Resource Framework: Refactoring & Evolution.. März 2004.
Crawler-ReferenzarchitekturShkapenyuk; Suel; Design and implementation of a high-performance distributed Web crawler; In Proceedings of the 18th International Conference on Data Engineering (ICDE'02), San Jose, CA Feb. 26--March 1; Seite 357-368; 2002
DNS-Server: Verteilter VerzeichnisdienstCheriton; Mann, Timothy P.; Decentralizing a Global Naming Service for Improved Performance and Fault Tolerance; ACM Transactions on Computer Systems, Volume 7, Number 2, Seite 147-183; 1989 .
Mobilfunk GSM: Trennung von Verarbeitung und VermittlungSchiller; Mobilkommunikation, 2., überarbeitete Auflage, ISBN: 3827370604, Mai 2003
Optimierungen
Umsetzung bewährter Verfahren
12 / 13
Quellen
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungZusammenfassung
Danke für Ihre AufmerksamkeitHaben Sie Fragen?
Globus Toolkit Grid, Einheitliche Infrastruktur
Grid-Services - Verwendung von XML-Standards
Crawler Dienste ausReferenzarchitektur
Verteilt arbeitender Verzeichnisdienst
Flexibler als Standardverzeichnis Hierarchisch
Unterstützt lokale Nähe
Zuteilung Dienste
Verteilt arbeitender Steuerdienst
Feste Zuteilung von Domains Trennung: Vermittlung und Verarbeitung
Schlanker Steuerdienst in Zellen
Hochperformante Crawler
Einsatz umfangreicherer Verteilstrategien für Domains
Minimierung von Reaktions- und Ladezeiten
Sicherheit, Nutzung heterogener Ressourcen mit Hilfe von Diensten
Kurze Übertragungswege, Hohe Ausfallsicherheit, Skalierbarkeit
Minimierte Kommunikation, Hohe Ausfallsicherheit, Skalierbarkeit
Effizienz
Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid MiddlewareAndreas Walter, 28. April 2006
13 / 13
Folie 3 - 5
Folie 6
Folie 7 - 8
Folie 9 - 11