Domainen crawlen & Domainnamen listen -> LANGSAM!

GastMarkus · 27. Jun 2007

Hallo,

ich schreibe grade probeweise ein Programm, welches Domains innerhalb einer Domain erkennen soll, und diese dann wiederrum auch nach Domains durchsuchen soll. Leider ist die Performance miserabel.
Hab ich irgendwas grundlegend falsch gemacht?

Code:

import java.net.*;
import java.io.*;
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;


public class URLDemo
{
    private ArrayList namensListe = new ArrayList();
    private int zaehler = 0;
    public static void main(String args[]) throws Exception
    {
        if (args.length != 1)
            {
                 // Print message, pause, then exit
                 System.err.println ("Invalid command parameters");
                 System.in.read();
                 System.exit(0);
            }
            
        URLDemo myURLMaker = new URLDemo();
        myURLMaker.start(args[0]);
    }
    
    public void start(String url)
    {
          domaincrawler starter = new domaincrawler();
          starter.start();
          starter.filterDomain(url,zaehler);
    }
    
    // Alle Domainnamen in der newurl finden
    
    private class domaincrawler extends Thread
    {
    
      public void filterDomain(String newurl, int threadnummer)
      {
             Pattern pattern = Pattern.compile("www\\.([^\\.]*)\\.de");
             //Pattern pattern2 = Pattern.compile('#("|\=)http://([^/\s"]*)(\.+)([A-Za-z0-9]+[^/\s"]*)\.([a-zA-Z]+[^\."/\s]{2,3})(.*)("|\s)#');
          try
          {
        // Check to see that a command parameter was entered
              // Create an URL instance
              System.out.println ("Crawl #"+threadnummer+" von "+newurl+" gestartet!");
              URL url = new URL(newurl);

              // Get an input stream for reading
              InputStream in = url.openStream();

              // Create a buffered input stream for efficency
              BufferedInputStream bufIn = new BufferedInputStream(in);

              // Repeat until end of file

              String urldata = "";
              for (;;)
              {
                  int data = bufIn.read();

                  // Check for EOF
                  if (data == -1)
                      break;
                  else
                     urldata += ((char) data);
              }
              Matcher matcher = pattern.matcher(urldata);
               domaincrawler ocrawl;

               while (matcher.find()) {
                     if(!namensListe.contains(matcher.group()))
                     {
                     zaehler++;
                     System.out.println ("      Neue Domain ("+zaehler+")     "+matcher.group());
                     namensListe.add(matcher.group());
                     ocrawl = new domaincrawler();
                     ocrawl.start();
                     ocrawl.filterDomain("http://"+matcher.group(), zaehler);

                     }

              }
              System.out.println ("Crawl #"+threadnummer+" von "+newurl+" beendet!");
          }
          catch (MalformedURLException mue)
          {
              System.err.println ("Invalid URL");
          }
          catch (IOException ioe)
          {
              System.err.println ("I/O Error - " + ioe);
          }
      }
      }
}

Vielen Dank!

Murray · 27. Jun 2007

Das

Code:

                if (data == -1)
                      break;
                  else
                     urldata += ((char) data);

ist ziemlich ineffizient, da Strings immutable sind, so dass bei jeder Zuweisung der String kopiert und ein neues Objekt erstellt werden muss, was 1. sofort Zeit kostet und 2. irgendwann auch den GarbageCollector fordert, was dann noch mehr Zeit frisst. Zur String-Konkatenation daher lieber StringBuilder (oder bei Asbach-JDKs ersatzweise StringBuffer) verwenden.

Wichtiger ist aber wohl die Art und Weise, wie Du den Stream auswertest; ein BufferedInputStream bringt wenig (oder sogar nichts?), wenn man dann doch wieder jedes Byte einzeln liest.

GastMarkus · 27. Jun 2007

Ok. Vielen Dank !
Und wie kann ich dieses BufferedINputStream-Problem am effizientesten umgehen?
Danke!

GastMarkus · 27. Jun 2007

Und ist es möglich dass die Thread-Geschichte bei mir noch nicht richtig funktioniert? Das sieht immer sehr prozedural vom Verlauf her aus.

AlArenal · 27. Jun 2007

Mal ganz davon abgesehen, dass ne DNS Abfrage schneller wäre

Domain != Webserver

Murray · 27. Jun 2007

GastMarkus hat gesagt.:
Ok. Vielen Dank !
Und wie kann ich dieses BufferedINputStream-Problem am effizientesten umgehen?
Danke!

In etwa so (einfach nur hingeschrieben, daher keine Garantie)

Code:

StringBuilder content = new StringBuilder();
byte[] buffer = new byte[Math.max( 1000, bufIn.available())];
while ((bytesRead = in.read(buffer)) > 0)
   content.append( new String( buffer, 0, bytesRead));

Das funktioniert aber nur, wenn keine Unicode-Zeichen im Spiel sind, denn dann würde die Konvertierung vom byte-Array in einen String je nach verwendetem Encoding in die Hose gehen. Hier sollte das aber kein Problem sein, da in URLs besser kein Umlaute verwendet werden.

GastMarkus · 27. Jun 2007

@AlArenal
Könntest du konkretisieren wie du das meinst? Es geht hier ja mehr oder weniger darum mal eine Domainliste zu ercrawlen. Gehst das denn über DNS? Wenn ja wie?
@Murray
Vielen Dank! Werde ic hgleich mal ausprobieren!

Murray · 27. Jun 2007

GastMarkus hat gesagt.:
Und ist es möglich dass die Thread-Geschichte bei mir noch nicht richtig funktioniert? Das sieht immer sehr prozedural vom Verlauf her aus.

Das ist wahr; mit start wird ja nur die run-Methode des Threads aufgerufen, die Du aber nicht überschrieben hast. Du musst dafür sorgen, dass das, was jetzt in filterDomain passiert, in der run-Methode des DomainCrawlers passiert. Da man der run-Methode keine Parameter übergeben kann, sollten die Paramter, die Du jetzt bei filterDomain hast, in den Konstruktor des domainCrawlers wandern und dort in Member-Variablen gespeichert werden.
Den expliziten Aufruf von filterDomain außerhalb der run-Methode musst Du loswerden.

GastMarkus · 27. Jun 2007

Ahja bekomme jetzt folgenden Fehler:

Code:

URLDemo.java:59: cannot find symbol
symbol  : variable bytesRead
location: class URLDemo.domaincrawler
while ((bytesRead = in.read(buffer)) > 0)
        ^
URLDemo.java:60: cannot find symbol
symbol  : variable bytesRead
location: class URLDemo.domaincrawler
   urldata.append( new String( buffer, 0, bytesRead));

Murray · 27. Jun 2007

Sorry, da fehlte dei Deklaration

Code:

int bytesRead;
StringBuilder content = new StringBuilder();
byte[] buffer = new byte[Math.max( 1000, bufIn.available())];
while ((bytesRead = in.read(buffer)) > 0)
   content.append( new String( buffer, 0, bytesRead));

GastMarkus · 27. Jun 2007

Vielen Dank nochmal. Ist jetzt schon ca 100 mal schneller

Und wenn nun die run-Methode ausgeführt wurde, wird der Thread autoatmisch eliminiert?

Murray · 28. Jun 2007

Die run-Methode des Thread ist es, die asynchron ausgeführt wird; wenn man ein Thread-Objekt instanziiert, passiert erstmal noch nichts bzgl. irgendwelcher Nebenläufigkeiten. Erst wenn man Thread#start aufruft, dann wird intern die run-Methode aufgerufen, und nur die läuft dann (quasi-)parallel zum aufrufenden Thread. Wenn die run-Methode beendet ist, dann ist auch der Thread beendet (auch wenn das Thread-Objekt noch existiert).

GastMarkus · 28. Jun 2007

Guten Mittag!
Aktuelles Problem:
Neue Domain (3537) www.teamgamers.de
Exception in thread "Thread-1344" java.lang.OutOfMemoryError: Java heap space
Exception in thread "Thread-1384"
Ideen um das zu umgehen?

Murray · 28. Jun 2007

Hast du die Threads jetzt umgestellt? Poste doch mal den aktuellen Code.

Bei diesem Ansatz sehe ich zwei Probleme: erstens werden immer neue Threads erzeugt, auch wenn de facto irgendwann eine Grenze erreicht ist, wo zusätzliche Threads keinen Sinn mehr machen, weil die CPU bereits vollständig beschäftigt ist. Es werden also u.U. neue Threads schneller erzeugt, als die bestehenden abgearbeitet werden können. Das kann dann irgendwann dazu führen, dass der Speicher nicht mehr ausreicht. Dem begegnet man z.B., indem die (möglichst) parallel abzuarbeitenden Aktionen erstmal in eine Art Warteschlange einstellt. Daneben hat man dann eine gewisse Anzahl von Arbeitsthreads, die sich jeweils einen Auftrag aus der Warteschlange holen und diesen dann verarbeiten.

Das zweite Problem besteht in zyklischen Verlinkungen: wenn Seite A auf Seite B verlinkt und in Seite B dann wieder ein Link auf Seite A steckt, dann wird die Suche nie beendet. Im momentanen Ansatz ohne Thread-Pool führt das zwangsläufig irgendwann dazu, dass mehr Threads erzeugt werden, als in den Speicher passen.

GastMarkus · 28. Jun 2007

Ich kann deinem Gedankengang folgen, aber ich weiß nicht, wie man am einfachsten die Threads begrenzen kann etc.
Hier jedenfalls erst mal der aktuelle Code:
Ich habe gedacht, dass es vlt hilft, alle variablen etc am Ende des Threads auf null zu setzen.
Vielen Dank für deine Hilfe :toll:

Code:

import java.net.*;
import java.io.*;
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;


public class URLDemo
{
    private ArrayList namensListe = new ArrayList();
    private int zaehler = 0;
    Pattern pattern = Pattern.compile("www\\.([^\\.]*)\\.de");
    public static void main(String args[]) throws Exception
    {
        if (args.length != 1)
            {
                 // Print message, pause, then exit
                 System.err.println ("Invalid command parameters");
                 System.in.read();
                 System.exit(0);
            }
            
        URLDemo myURLMaker = new URLDemo();
        myURLMaker.start(args[0]);
    }
    
    public void start(String url)
    {
          domaincrawler starter = new domaincrawler(url,zaehler);
          starter.start();
    }
    
    // Alle Domainnamen in der newurl finden
    
    
    
    // Ale eigenständigen asychronen Thread starten...
    private class domaincrawler extends Thread
    {
      private String newurl;
      private int threadnummer;
      public domaincrawler(String newurl, int threadnummer)
      {
        this.newurl = newurl;
        this.threadnummer = threadnummer;
      }
      public void run()
      {

             //Pattern pattern2 = Pattern.compile('#("|\=)http://([^/\s"]*)(\.+)([A-Za-z0-9]+[^/\s"]*)\.([a-zA-Z]+[^\."/\s]{2,3})(.*)("|\s)#');
          try
          {

        // Check to see that a command parameter was entered
              // Create an URL instance
              System.out.println ("Crawl #"+threadnummer+" von "+newurl+" gestartet!");
              URL url = new URL(newurl);

              // Get an input stream for reading
              InputStream in = url.openStream();

              // Create a buffered input stream for efficency
              BufferedInputStream bufIn = new BufferedInputStream(in);

              // Repeat until end of file
              int bytesRead;
              StringBuilder urldata = new StringBuilder();
byte[] buffer = new byte[Math.max( 1000, bufIn.available())];
while ((bytesRead = in.read(buffer)) > 0)
   urldata.append( new String( buffer, 0, bytesRead));
              /*for (;;)
              {
                  int data = bufIn.read();

                  // Check for EOF
                  if (data == -1)
                      break;
                  else
                     urldata.append((char) data);
              }*/

              Matcher matcher = pattern.matcher(urldata);
              domaincrawler ocrawl;

               while (matcher.find()) {
                     if(!namensListe.contains(matcher.group()))
                     {
                     zaehler++;
                     System.out.println ("      Neue Domain ("+zaehler+")     "+matcher.group());
                     namensListe.add(matcher.group());
                     ocrawl = new domaincrawler("http://"+matcher.group(), zaehler);
                     ocrawl.start();
                     ocrawl = null;

                     }

              }
              //Speicher irgendwie freigeben ::
              matcher = null;
              urldata = null;
              buffer = null;
              bufIn = null;
              in = null;
              url = null;
              System.out.println ("Crawl #"+threadnummer+" von "+newurl+" beendet!");
              this.destroy();
              //this.stop();
          }
          catch (MalformedURLException mue)
          {
              System.err.println ("Invalid URL");
          }
          catch (IOException ioe)
          {
              System.err.println ("I/O Error - " + ioe);
          }
          catch (Exception e)
          {
              System.err.println ("Sonstiger Fehler - " + e);
          }
      }
      }
}

Guest · 28. Jun 2007

Habe jetzt versucht die Threads zu begrenzen, aber dann bleibt das irgendwann eifnach stecken:

Code:

import java.net.*;
import java.io.*;
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;


public class URLDemo
{
    private ArrayList namensListe = new ArrayList();
    private int zaehler = 0;
    private int activethreads = 0;
    public int maxthreads = 200;
    Pattern pattern = Pattern.compile("www\\.([^\\.]*)\\.de");
    public static void main(String args[]) throws Exception
    {
        if (args.length != 1)
            {
                 // Print message, pause, then exit
                 System.err.println ("Invalid command parameters");
                 System.in.read();
                 System.exit(0);
            }
            
        URLDemo myURLMaker = new URLDemo();
        myURLMaker.start(args[0]);
    }
    
    public void start(String url)
    {
          domaincrawler starter = new domaincrawler(url,zaehler);
          starter.start();
    }
    
    // Alle Domainnamen in der newurl finden
    
    
    
    // Ale eigenständigen asychronen Thread starten...
    private class domaincrawler extends Thread
    {
      private String newurl;
      private int threadnummer;
      public domaincrawler(String newurl, int threadnummer)
      {
        activethreads++;
        this.newurl = newurl;
        this.threadnummer = threadnummer;
      }
      public void run()
      {

             //Pattern pattern2 = Pattern.compile('#("|\=)http://([^/\s"]*)(\.+)([A-Za-z0-9]+[^/\s"]*)\.([a-zA-Z]+[^\."/\s]{2,3})(.*)("|\s)#');
          try
          {

        // Check to see that a command parameter was entered
              // Create an URL instance
              //System.out.println ("Crawl #"+threadnummer+" von "+newurl+" gestartet!");
              URL url = new URL(newurl);

              // Get an input stream for reading
              InputStream in = url.openStream();

              // Create a buffered input stream for efficency
              BufferedInputStream bufIn = new BufferedInputStream(in);

              // Repeat until end of file
              int bytesRead;
              StringBuilder urldata = new StringBuilder();
byte[] buffer = new byte[Math.max( 1000, bufIn.available())];
while ((bytesRead = in.read(buffer)) > 0)
   urldata.append( new String( buffer, 0, bytesRead));
              /*for (;;)
              {
                  int data = bufIn.read();

                  // Check for EOF
                  if (data == -1)
                      break;
                  else
                     urldata.append((char) data);
              }*/

              Matcher matcher = pattern.matcher(urldata);
              domaincrawler ocrawl;

               while (matcher.find()) {
                     if(!namensListe.contains(matcher.group()))
                     {
                     zaehler++;
                     while(true){
                     if(activethreads < maxthreads)
                     {
                       System.out.println ("      Neue Domain ("+zaehler+")     "+matcher.group());
                     namensListe.add(matcher.group());
                     ocrawl = new domaincrawler("http://"+matcher.group(), zaehler);
                     ocrawl.start();
                     ocrawl = null;
                     break;
                     }
                     else
                     {
                       Thread.sleep(100);
                       
                     }


                     }

                     }

              }
              //Speicher irgendwie freigeben ::
              matcher = null;
              urldata = null;
              buffer = null;
              bufIn = null;
              in = null;
              url = null;
              //System.out.println ("Crawl #"+threadnummer+" von "+newurl+" beendet!");
              System.out.println (""+activethreads+" Threads aktiv");
              activethreads--;

              //this.stop();
          }
          catch (MalformedURLException mue)
          {
              //System.err.println ("Invalid URL");
          }
          catch (IOException ioe)
          {
              //System.err.println ("I/O Error - " + ioe);
          }
          catch (Exception e)
          {
              //System.err.println ("Sonstiger Fehler - " + e);
          }
      }
      }
}

Murray · 29. Jun 2007

Du lässt dir ja ausgeben, wieviele Threads gerade aktiv sind. Bei wievielen Threads bleibt das Programm denn hängen? Mir scheinen 200 Thread, die in einer "while (!abbruch) { Thread.sleep( 100;}"-Schleife stecken, schon ziemlich viel. Eventuell musst du die Grenze niederiger ansetzen. Außerdem könnte es hilfreich sein, vom "busy-waiting" mit sleep() auf den "wait-notify"-Mechanismus umzustellen.

Murray · 29. Jun 2007

Das Problem besteht hier ja darin, dass man in der Anwendung eigentlich nur mit parallel abzuarbeitenden Aufgaben hantiert, ohne dass sich man dabei um die Limitierungen kümmern möchte, die sich aus der konkreten Implementierung des Multithreadings ergeben. Natürlich kann man sich Mühe geben, die Anwendung mit diesen Limitierungen umgehen zu lassen (Begrenzung der Thread-Anzahl, Warteschlange, Thread-Pool), was wir hier jetzt ein Stück weit gemacht haben (und was sicher dem Verständnis von Multithreading und Thread-Synchronisierung dient).

Wenn es aber "nur" darum geht, dass die Anwendung funktioniert, dann bietet Java ab JDK 1.5 mit dem java.util.concurrent-Package eine elegante Abstraktionschicht. Man arbeitet nicht mehr direkt mit Threads, sondern mit Runnables, deren Ausführung man einem Scheduler überlässt. Damit könnte das Programm dann z.B. so aussehen:

Code:

import java.net.MalformedURLException;
import java.net.URL;
import java.io.BufferedInputStream;
import java.io.InputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;
import java.util.regex.Pattern;
import java.util.regex.Matcher;



public class URLDemo {
	
		private ArrayList<String> namensListe = new ArrayList<String>();
		private Pattern pattern = Pattern.compile("www\\.([^\\.]*)\\.de");
		private long t0 = System.currentTimeMillis();		
		ExecutorService executor = Executors.newFixedThreadPool( 100);
		
		private static int nextTN = 0;

		public static void main(String args[]) throws Exception {
			
			if (args.length != 1) {
				// Print message, pause, then exit
				System.err.println ("Invalid command parameters");
				System.in.read();
				System.exit(0);
			}
					 
			URLDemo myURLMaker = new URLDemo();
			myURLMaker.start(args[0]);
		}
	 
		public void start( String url) {
					domaincrawler starter = new domaincrawler( url);
					executor.execute( starter);
		}
	 
	 
		private class domaincrawler implements Runnable {
			private String newurl;
			private int threadnummer;
			public domaincrawler( String newurl) {
				this.newurl = newurl;
				this.threadnummer = nextTN++;
			}
 
			public void run() {

				try {

					//System.out.println ("Crawl #"+threadnummer+" von "+newurl+" gestartet!");

					// Create an URL instance
					URL url = new URL( newurl);

					// Get an input stream for reading
					InputStream in = url.openStream();

					// Create a buffered input stream for efficency
					BufferedInputStream bufIn = new BufferedInputStream(in);

					// Repeat until end of file
					int bytesRead;
					StringBuilder urldata = new StringBuilder();
					byte[] buffer = new byte[Math.max( 1000, bufIn.available())];
					while ((bytesRead = in.read(buffer)) > 0) {
						urldata.append( new String( buffer, 0, bytesRead));
					}

					//--- find domains within the content
					Matcher matcher = pattern.matcher( urldata);

					while (matcher.find()) {
							String newDomain = matcher.group();
							if( !namensListe.contains( newDomain)) {
								//--- found a new domain -> add to result list and spawn a new crawler
								namensListe.add( newDomain);
								System.out.println ("Neue Domain: (Domains: " + namensListe.size() + 
									", Crawls: " + nextTN + ", Zeit: "  + 
									(System.currentTimeMillis()-t0) + "ms)  " + newDomain );
								executor.execute( new domaincrawler("http://" + newDomain));
							}

					}
					//System.out.println ("Crawl #"+threadnummer+" von "+newurl+" beendet!");
				} catch (MalformedURLException mue) {
							/**/System.err.println ("Invalid URL");
				} catch (IOException ioe) {
							/**/System.err.println ("I/O Error - " + ioe);
				} catch (Exception e) {
							/**/System.err.println ("Sonstiger Fehler - " + e);
				}
		}
	}
}

Mit dem Wert für Executors.newFixedThreadPool musst du vielleicht noch etwas experimentieren; ja nach CPU, Netzwerkanbindung und Antwortzeiten der jeweiligen Server kann das Optimum sicher variieren.

Auf meiner Maschine besteht z.B. ein recht grosser Unterschied zwischen 10 und 20 Threads, 100 Threads sind nochmal etwas besser, 200 bringen nicht mehr viel, aber immer noch ein bisschen.

GastMarkus · 29. Jun 2007

Ich möchte mich nochmal für deine Hilfe bedanken. Wirklich super! Hat mir sehr weitergeholfen!

Murray · 30. Jun 2007

Gern geschehen.

Domainen crawlen & Domainnamen listen -> LANGSAM!

GastMarkus

Gast

Top Contributor

GastMarkus

Gast

GastMarkus

Gast

Top Contributor

Top Contributor

GastMarkus

Gast

Top Contributor

GastMarkus

Gast

Top Contributor

GastMarkus

Gast

Top Contributor

GastMarkus

Gast

Top Contributor

GastMarkus

Gast

Guest

Gast

Top Contributor

Top Contributor

GastMarkus

Gast

Top Contributor

Ähnliche Java Themen