Wie entwickle ich meine eigene Suchmaschine: Crawler-Programmierung

Grundgerüst des Programms

Überlegen wir uns aber zunächst den Aufbau unserer Crawling-Architektur. Klar ist, dass wir eine Klasse Crawler benötigen. Da beim Aufrufen von Webseiten am meisten Zeit durch das Warten auf die Antwort (und das Auflösen des DNS-Namens, aber diese Optimierung wollen wir hier vernachlässigen) verloren geht, sollten wir zudem mehrere Instanzen unseres Crawlers laufen lassen. Deshalb muss Crawler als Thread implementiert werden. Zum Verwalten unserer Threads legen wir uns eine Klasse Manager an. Zwar könnten wir die Threads auch direkt starten, jedoch bietet uns die Klasse eine praktische Form der Kapselung an, die wir später auch zum gezielten Ansteuern durch die Konsole oder andere Programmteile verwenden können.

Dieses Threading auf mehrere parallele Crawler werden wir jedoch in einem späteren Entwurf ergänzen und uns zunächst auf einen einzelnen Crawler konzenzentrieren.

Natürlich müssen die Crawler auch wissen, welche Seiten sie besuchen sollen. Dafür brauchen wir eine Liste mit URLs, die zu bearbeiten sind. Da diese Liste jedoch schnell sehr großen werden würde und vermutlich unser Speicher zu klein ist, werden wir sie um eine Datenbank erweitern. Das heißt, ein Grundsatz an URLs wird in der Liste (bei Crawlern nennt man das den Frontier) verwaltet, der restliche Teil steckt in einer zentralen Datenbank. Sollte die Liste einmal leer sein, werden neue URLs von der Datenbank abgefragt.

Auch hier werden wir zunächst eine sehr einfache Version implementieren.

Jetzt bleibt nur noch die Frage, woher die URLs kommen sollen, die besucht werden. Hier gibt es zwei mögliche Ansätze:

• die Crawler extrahieren die Links selbst und besuchen sie (Online-Crawling)
• dir Crawler besuchen nur vorgegeben Links, speichern denn Quellcode und eine andere Instanz sucht die Links heraus (Offline-Crawling)

Umsetzung eines Crawlers in Python

Der Einfachheit halber implementieren wir zunächst einen Crawler, der die URLs selbst extrahiert. Wir verwenden eine externe Klasse Frontier, die wir später selbst noch implementieren werden, um die URLs zu speichern und zu laden. Unser Crawler selbst wird mehrere Methoden haben:

• crawl(): Startet den Crawlvorgang und läuft so lange in einer Schleife, bis keine URLs mehr gefunden werden. In unserer ersten Variante wird jedoch schnell der Speicher überlaufen, wenn man dies im globalen Web versucht, da es viel zu viele Seiten gibt, die in der noch zu besuchen-Liste landen. Einige Zeit lang kann man ihn aber so auch im Web laufen lassen.
• visit_url(): Hiermit besuchen wir tatsächlich eine Internetseite und rufen ihren Inhalt ab.
• collect_new_urls(): Sammelt die Links auf der aktuellen Seite ein und gibt sie an die URL-Klasse zum Speichern weiter, sodass wir sie später wieder von dort abrufen können.
• extract_urls(): Wird von collect_new_urls() verwendet und parst die Webseite, um die Links zu erhalten und als Liste zurückzugeben.

from BeautifulSoup import BeautifulSoup
import urllib2, httplib, urlparse
import time

import frontier

class Crawler(object):
   def __init__(self, init_url):
      init_domain = urlparse.urlparse(init_url).netloc
      
      # Manages our domains we want to visit or have visited
      self.frontier = frontier.Frontier()
      self.frontier.add(init_url, None)
   
   @property
   def polite_time(self):
      return self.frontier.polite_time
   
   @polite_time.setter
   def polite_time(self, seconds):
      if seconds >= 0:
         self.frontier.polite_time = seconds
   
   def crawl(self):
      while len(self.frontier) > 0:
         next_time, next_url = self.frontier.next()
         
         while time.time() < next_time:
            time.sleep(0.5)
         
         try:
            self.visit_url(next_url)
         except urllib2.URLError:
            continue
   
   def visit_url(self, url):
      print("Visiting URL: %s" % url)
      self.frontier.notify_visit(url)
      request = urllib2.Request(url)
      
      try:
         response = urllib2.urlopen(request, None, 10)
      except (urllib2.HTTPError, httplib.BadStatusLine):
         continue # Ignore this URL if we cannot open it
      
      if response != None:
         self.collect_new_urls(url, response.read())
   
   def collect_new_urls(self, url, html):
      print("Fetching new URLs from: %s" % url)
      
      try:
         for page in self.extract_urls(html):
            page = urlparse.urljoin(url, page)
            self.frontier.add(page, url)
      except UnicodeEncodeError:
         pass
   
   def extract_urls(self, page):
      soup = BeautifulSoup(page)
      return [link.get('href') for link in soup.findAll('a')]

Dies ist bereits ein sehr einfacher Webcrawler. Er folgt meinem Deadlink-Crawler.

Frontier

Da wir dem Crawler eine Liste mit Links geben wollen, müssen wir diese natürlich ebenfalls implementieren. Dazu müssen wir aber einige Vorüberlegungen anstellen.

Um später nicht alles neu machen zu müssen, überlegen wir uns, dass ein Crawler höflich (polite) sein soll. Das heißt, wir dürfen den gleichen Server nicht zu oft abfragen und wir sollten uns an Informationen zum Crawl-Delay der robots.txt halten. Die robots.txt werden wir jetzt noch nicht beachten, wohl aber einen eigenen Delay zwischen Anfragen an die gleiche Domain einbauen.

Neben dem eigentlich zu crawlenden Link müssen wir also ebenso einen Zeitstempel speichern, wann die URL wieder besucht werden darf. Zur Sortierung der Zeitstempel pro Domain können wir einen Heap verwenden. Python stellt dazu das Modul heapq bereit, welches mit nativen Python-Listen arbeitet.

Die Menge der noch zu crawlenden URLs wird als Frontier bezeichnet, deshalb nennen wir unsere Klasse auch Frontier. Der Frontier wird mehrere Methoden zum Setzen und Auslesen von URLs enthalten. Außerdem fügen wir eine Methode hinzu, um zu markieren, dass wir eine URL eben besucht haben.

Innerhalb unseres Frontier verwalten wir drei Datenstrukturen:

• Ein Dictionary, welches geordnet nach Domains speichert, welche URLs wir hiervon noch durchsuchen müssen
• Ein Set, welches uns angibt, ob wir eine URL schon besucht haben oder nicht
• Einen Heap (als Liste mit heapq), welches uns immer die als nächstes zu crawlende Domain liefert

import urlparse
import time
import heapq

class Frontier(object):
   def __init__(self):
      # A list of urls that still have to be searched sorted by
      # domains
      self.urls = {}
      
      # A list containing the next crawltimes on domain level, 
      # to achieve a optimal throughput maintaining a polite policy
      self.crawltimes = []
      
      # Urls we have already found and in our set
      self.found = set()
      
      self._polite_time = 1
   
   @property
   def polite_time(self):
      return self._polite_time
   
   @polite_time.setter
   def polite_time(self, seconds):
      if seconds >= 0:
         self._polite_time = seconds
   
   def add(self, url):
      if url in self.found:
         return False
      
      domain = urlparse.urlparse(url).netloc
      
      # means this is the first URL in our set
      if not domain in self.urls:
         self.urls[domain] = []
         heapq.heappush(self.crawltimes, (time.time(), domain))
      
      self.urls[domain].append(url)
      self.found.add(url)
      
      return True
   
   def next(self):
      next_time, next_domain = heapq.heappop(self.crawltimes)
      
      next_url = self.urls[next_domain].pop()
      
      if len(self.urls[next_domain]) == 0:
         del(self.urls[next_domain])
      
      return next_time, next_url
   
   def notify_visit(self, url):
      domain = urlparse.urlparse(url).netloc
            
      # If there are still other urls on this domain to crawl, add crawl time
      if domain in self.urls:
         heapq.heappush(self.crawltimes, (time.time() + self.polite_time, domain))
   
   def __len__(self):
      return sum([len(self.urls[domain]) for domain in self.urls])