Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid Middleware Andreas Walter 28. April 2006 Fakultät für Informatik

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


1 / 13

Inhalt• Grid-Middleware• Crawler• Dienste• Evaluation• Zusammenfassung

Virtuelle Organisationen, Globus-Toolkit, Dienste

Status Intro | Grid-Middleware | Crawler | Verzeichnisdienste | Steuerdienste | Evaluation | ZusammenfassungIntroIntro


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


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


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


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


6 / 13


Zellen und Areas

Verteilstrategien für Domains


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


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


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


Steuerung

Crawler

Austausch von Domains

Austausch von URLs


Zellen und Areas



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



8 / 13

USA

Europa

UK

Afrika

AsienSüdamerika

Kanada


Zellen und Areas



Hochperformante Crawler

Kürzeste Wege der Kommunikation zwischen Crawler und Web-Server

Messwerte• Antwortzeit• Ladezeit• Lokationen


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



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


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


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


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


13 / 13

Folie 3 - 5

Folie 6

Folie 7 - 8

Folie 9 - 11

Documents

Entwurf, Realisierung und Analyse eines hochgradig verteilten Web Crawlers mit Hilfe von Grid Middleware Andreas Walter 28. April 2006 Fakultät für Informatik