Multithreaded webcrawler

Question

I've been trying to learn Java for the last day or two. This is the first project I am working on, so please bear with me. I worked on a multithreaded web crawler. It is fairly simple but I'd like to ask for some advice.

Purpose / Running

The program starts at one web address (in this code, http://google.com) and looks for all valid URLs inside the response given. All URLs found in the response will be added to the queue. The crawler will then continue crawling through the URLs in the queue. To stop the crawler, type exit in the input

Http.java

package com.janchr;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.HttpURLConnection;
import java.net.URL;

/**
 * Created by Jan on 8/20/2016.
 */
public class Http {
    public static BufferedReader Get(URL url) throws IOException {
        HttpURLConnection con = (HttpURLConnection)url.openConnection();
        con.setRequestMethod("GET");

        // pretend that we are a new-ish browser. current user agent is actually from 2015.
        con.setRequestProperty("User-Agent", "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/45.0.2454.101 Safari/537.36");
        con.setInstanceFollowRedirects(true);

        int statusCode = con.getResponseCode();

        // https://www.mkyong.com/java/java-httpurlconnection-follow-redirect-example/
        boolean redirect = false;
        if (statusCode != HttpURLConnection.HTTP_OK) {
            if (statusCode == HttpURLConnection.HTTP_MOVED_TEMP
                    || statusCode == HttpURLConnection.HTTP_MOVED_PERM
                    || statusCode == HttpURLConnection.HTTP_SEE_OTHER)
                redirect = true;
        }

        if (redirect) {
            // get redirect url from "location" header field
            String newUrl = con.getHeaderField("Location");
            // get the cookie if need
            String cookies = con.getHeaderField("Set-Cookie");

            return Http.Get(new URL(newUrl));
        }


        return new BufferedReader(new InputStreamReader(con.getInputStream()));
    }
}

Crawler.java

package com.janchr;


import java.io.BufferedReader;
import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Created by Jan on 8/20/2016.
 */

class CrawlThread implements Runnable {
    final static Pattern urlPat = Pattern.compile("(https?|ftp|file)://[-a-zA-Z0-9+&@#/%?=~_|!:,.;]*[-a-zA-Z0-9+&@#/%=~_|]");

    Crawler c;
    int num;
    boolean stop;
    public Thread t;

    public CrawlThread(Crawler c, int num) {
        this.c = c;
        this.num = num;
        this.t = new Thread(this, "CrawlThread");
        t.start();
    }

    private LinkedList<String> parse(BufferedReader r) {
        String lineBuf = "";
        LinkedList<String> urls = new LinkedList<String>();
        do {
            try {
                lineBuf = r.readLine();
            } catch (IOException e) {
                System.out.println("(" + this.num + ") error parsing: " + e);
                return urls;
            }
            if (lineBuf == null) {
                return urls;
            }

            Matcher m = urlPat.matcher(lineBuf);
            while(m.find()) {
                //System.out.println("(" + this.num + ") match: " + m.group(0));
                urls.add(m.group(0));
            }

        } while(lineBuf != null);
        return urls;
    }

    public void run() {
        // pop_front the next URL and get it
        do {
            String surl = c.next();
            //System.out.println("(" + this.num + ") getting " + surl);

            URL url;
            try {
                url = new URL(surl);
            } catch (MalformedURLException e) {
                System.out.println("(" + this.num + ") bad url " + surl + ": " + e);
                continue;
            }

            BufferedReader r;
            try {
                r = Http.Get(url);
            } catch (IOException e) {
                System.out.println("(" + this.num + ") IOException Http.Get " + surl + ": " + e);
                continue;
            }
            c.done(surl);

            for (String newUrl: this.parse(r)) {
                c.addURL(newUrl);
            }

        } while(!this.stop);
    }
}

class VisitedURL {
    public String url;
    public int visits;

    VisitedURL(String url) {
        this.url = url;
    }
}

public class Crawler {
    private List<String> queue = Collections.synchronizedList(new LinkedList<>());

    private Map<String, VisitedURL> visited = Collections.synchronizedMap(new LinkedHashMap<>());
    private ArrayList<CrawlThread> threads = new ArrayList<>();
    private int maxThreads;

    public Crawler(int maxThreads) {
        this.maxThreads = maxThreads;
    }

    public void start(String entryPoint) {
        this.queue.add(entryPoint);

        for (int i = 0; i < this.maxThreads; i++) {
            this.threads.add(new CrawlThread(this, i));
        }
    }

    public synchronized void stop() {
        for(CrawlThread t: this.threads) {
            // interrupting the thread should be fine for us in our use-case.
            t.stop = true;
            t.t.interrupt();
        }
    }

    public synchronized String next() {
        // I got IndexOutOfBoundsException here when starting up the crawler.
        // the only way to fix it for me was this loop. I don't know what would
        // be a better way to fix it. A mutex didn't work for me.
        do {
            if (this.queue.size() == 0) {
                try {
                    wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        } while(this.queue.size() == 0);

        synchronized (this.queue) {
            if (this.queue.size() == 1) {
                System.out.println("QUEUE EMPTY NOW");
            }
            return this.queue.remove(0);
        }
    }

    public void done(String url) {
        final VisitedURL obj = this.visited.putIfAbsent(url, new VisitedURL(url));
        if (obj == null) {
            this.visited.get(url).visits++;
        }
    }

    public synchronized void addURL(String url) {
        // TODO: we might want to ignore the URLs query
        if (this.queue.contains(url)) {
            return;
        }
        if (this.visited.containsKey(url)) {
            this.visited.get(url).visits++;
            return;
        }
        this.queue.add(url);
        notifyAll();
    }

    public Map<String, VisitedURL> getVisitedUrls() {
        return visited;
    }
}

Main.java

package com.janchr;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Crawler c = new Crawler(8);

        System.out.println("starting crawler");
        c.start("http://google.com");

        Scanner s = new Scanner(System.in);
        while (!s.next().equals("exit"));

        c.stop();

        synchronized (c) {
            System.out.println("\n\n---------------------------------------------------------------------");
            for (VisitedURL u : c.getVisitedUrls().values()) {
                System.out.println(u.visits + "x " + u.url);
            }
            System.out.println("---------------------------------------------------------------------");
            System.out.println("visited " + c.getVisitedUrls().size() + " unique urls");
        }
    }
}

Some questions:

1. As seen in Crawler::next, I ran into a few problems when having a lot of threads running. I haven't exactly figured out why I can't just put one of the wait calls there, but I guess it is because I use notifyAll later on(?)
2. Would it be better if I created the threads "on demand" rather than creating them all on startup and then waiting for new URLs to be in the queue? Would it eliminate the issue I have above?
3. What is the "usual Java way" to work with multiple threads?
4. By design, the crawler will get slower and slower over time because the Lists/Maps get bigger. I can't really think of a way to increase performance there. What can I improve here?

Edit

I've updated my code to use the threads how as I specified in one of my questions. Is this a better solution?

Crawler.java

package com.janchr;


import java.io.BufferedReader;
import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Created by Jan on 8/20/2016.
 */

class CrawlThread implements Runnable {
    final static Pattern urlPat = Pattern.compile("https?://[-a-zA-Z0-9+&@#/%?=~_|!:,.;]*[-a-zA-Z0-9+&@#/%=~_|]");

    Crawler c;
    String url;
    public Thread t;

    public CrawlThread(Crawler c, String url) {
        this.c = c;
        this.url = url;
        this.t = new Thread(this, "CrawlThread");
        t.start();
    }

    private LinkedList<String> parse(BufferedReader r) {
        String lineBuf = "";
        LinkedList<String> urls = new LinkedList<String>();
        do {
            try {
                lineBuf = r.readLine();
            } catch (IOException e) {
                System.out.println("error parsing: " + e);
                return urls;
            }
            if (lineBuf == null) {
                return urls;
            }

            Matcher m = urlPat.matcher(lineBuf);
            while(m.find()) {
                urls.add(m.group(0));
            }

        } while(lineBuf != null);
        return urls;
    }

    public void run() {
        URL url;
        try {
            url = new URL(this.url);
        } catch (MalformedURLException e) {
            System.out.println("bad url " + this.url + ": " + e);
            c.done(this, this.url);
            return;
        }

        BufferedReader r;
        try {
            r = Http.Get(url);
        } catch (IOException e) {
            System.out.println("IOException Http.Get " + this.url + ": " + e);
            c.done(this, this.url);
            return;
        }

        for (String newUrl: this.parse(r)) {
            c.addURL(newUrl);
        }
        c.done(this, this.url);
    }
}

class VisitedURL {
    public String url;
    public int visits;

    VisitedURL(String url) {
        this.url = url;
    }
}

public class Crawler {
    private List<String> queue = Collections.synchronizedList(new LinkedList<>());

    private Map<String, VisitedURL> visited = Collections.synchronizedMap(new LinkedHashMap<>());
    private ArrayList<CrawlThread> threads = new ArrayList<>();
    private int maxThreads;

    public Crawler(int maxThreads) {
        this.maxThreads = maxThreads;
    }

    public void start(String entryPoint) {
        this.queue.add(entryPoint);

        this.tryNext();
    }

    public synchronized void stop() {
        for(CrawlThread t: this.threads) {
            // interrupting the thread should be fine for us in our use-case.
            t.t.interrupt();
        }
    }

    public synchronized boolean hasNext() {
        return this.queue.size() > 0;
    }

    public synchronized String next() {
        if (this.queue.size() == 0) {
            return null;
        }
        return this.queue.remove(0);
    }

    private void tryNext() {
        if (!this.hasNext() || this.threads.size() == this.maxThreads) {
            return;
        }

        String next = this.next();
        if (next == null) {
            System.out.println("invalid next string");
            return;
        }

        this.threads.add(new CrawlThread(this, next));
    }

    public void done(CrawlThread t, String url) {
        final VisitedURL obj = this.visited.putIfAbsent(url, new VisitedURL(url));
        if (obj == null) {
            this.visited.get(url).visits++;
        }
        this.threads.remove(t);
        this.tryNext();
    }

    public synchronized void addURL(String url) {
        // TODO: we might want to ignore the URLs query
        if (this.queue.contains(url)) {
            return;
        }
        if (this.visited.containsKey(url)) {
            this.visited.get(url).visits++;
            return;
        }
        this.queue.add(url);

        this.tryNext();
    }

    public Map<String, VisitedURL> getVisitedUrls() {
        return visited;
    }
}

Now I am not able to .interrupt my threads anymore though. How do I fix this?

Answer 1

Nice work for someone with only a few days of Java experience! Now some improvements:

You are working on a derivative of the classic producer-consumer problem. This is a common problem, and there are well established patterns for solving it in Java.

The abstraction you want to use here is called an ExecutorService. Essentially, it allows you to submit Runnables to be executed by the ExecutorService. You can easily construct an ExecutorService using Executors#newFixedThreadPool. We can make a few modifications to your CrawlThread class to make it work in this new model:

class Crawler implements Runnable {
  private final String url;
  private final Executor executor;
  private final Map<String, SeenUrl> seenUrls;

  public Crawler(
      String url,
      Executor executor,
      Map<String, VisitedUrl> seenUrls) {
    this.url = url;
    this.executor = executor;
    this.seenUrls = seenUrls;
  }

  @Override
  public void run() {
    List<String> newUrls = parse(); // Very similar to your parse
    for (String newUrl : newUrls) {
      synchronized(seenUrls) {
        if (seenUrls.containsKey(newUrl)) {
          seenUrls.get(newUrl).timesSeen++;
        } else {
          seenUrls.put(newUrl, new SeenUrl(newUrl));
          executor.submit(new Crawler(newUrl, executor, seenUrls));
        }
      }
    }
  }
}

public class Main {
  public static void main(String[] args) {
    // Run with 5 threads, adjust as necessary.
    ExecutorService executorService = Executors.newFixedThreadPool(5);
    Map<String, SeenURL> seenUrls = new LinkedHashMap<>();
    seenUrls
      .put("http://google.com", new SeenUrl("http://google.com"));
    executorService.submit(
      new Crawler("http://google.com", executorService, seenUrls)); 
    executorService.awaitTermination();
  }
}

Now, there may be a few surprises in the above code snippets:

• VisitedUrls became SeenUrls - I think thats what you were actually counting in your code, although I could be wrong. Additionally, it allows to formulate a simple invariant: only submit a new URL for crawling if it is not in seenUrls.
• Crawler takes in an Executor, not an ExecutorService - ExecutorService implements Executor, and we don't need the full power of ExecutorService in Crawler.
• The program never terminates - I'll let you implement that :). You will probably want to use ExecutorService#shutdown().

The next improvement I would make would be to replace the map of SeenUrls with a Multiset. However, that is not included in the standard Collections library.

Answer 2

Matt H provided an excellent answer on leveraging Java's extensive libraries. Executor is a great service. Do not shy away from those APIs, they work great and speed up the coding process many-folds.

Formatting is exemplar (indentation spot on, correct cAsE). I guess I'll simply address the usual coding standards/Java idioms.

---

Naming

Classes tend to be Nouns, not Verbs (They are object categories, and do not define actions). It's the methods that provide means to perform an action, those shoud be a verb.

• CrawlThread would be better called ThreadCrawler, because of what it is, not what it does
• Crawler.done()should be named Crawler.markAsDone()

Variable access level

class CrawlThread implements Runnable {
    final static Pattern urlPat = ...;
    Crawler c;
    String url;
    public Thread t;

You're probably forgetting a few variable access levels here. I don't know if you intend to subclass those classes, but it's a good idea to make all those private, especially the static constant. Default access level is very rarely desirable.

The public Thread handle in particular is an accident waiting to happen. This allows you to call your Thread from anywhere and mess with your Threading. Hide it away, only expose safe control methods.

Class access level

Your classes have no access level defined. Make it as private as you can, especially VisitedURL.

Static side-classes

I'm not sure if the secondary classes like VisitedURL are defined in their own files, but if not you have to make those static.

Thread and Runnable

class CrawlThread implements Runnable {
    ...
    public Thread t;

You're not clear with this statement. You claim CrawlThread is Runnable so I should give it to a Thread. But as soon as I construct one, it calls a Thread on itself, do I have no control. This looks like what I would call a Thread actually!

You need to split reponsibilities. Either keep CrawlThread as Runnable but remove its Thread and manage that outside, or let it extend Thread directly.

Try / catch out of the loop

It changes on a case-by-case basis, but try to put your try/catch blocks as far out as you can. Especially if the catch clause exits the enclosing do/while.

I.E: prefer this:

try {
    do {
        lineBuf = r.readLine();
    } while(lineBuf != null);
} catch (IOException e) {
    System.out.println("error parsing: " + e);
    return urls;
}

This will better show you intend to exit the while whenever an exception occur. If the catch clause had had a continue, it might have been otherwise.

Try-with-resources

BufferedReader si a Closeable. Further more, it is also an AutoCloseable.

There is a much better way to write this code since Java 7 (which fails to close the BufferedReader):

BufferedReader r;
try {
    r = Http.Get(url);
} catch (IOException e) {
    System.out.println("IOException Http.Get " + this.url + ": " + e);
    c.done(this, this.url);
    return;
}

for (String newUrl: this.parse(r)) {
    c.addURL(newUrl);
}
c.done(this, this.url);

It can now be written as the more concise and robust:

try (BufferedReader r = Http.Get(url)){
    for (String newUrl: this.parse(r)) {
        c.addURL(newUrl);
    }
} finally {
    c.done(this, this.url);
} catch (IOException e) {
    System.out.println("error parsing: " + e);
}

Coarser Return types

private LinkedList<String> parse(BufferedReader r) {

It is a good idea to always return a List<String> so you can change implementation later on whithout a whole bunch of code edits.

Error logging

Your error loggings are not fully using Java strength:

System.out.println("(" + this.num + ") error parsing: " + e);

This will simply display the message, then the exception label, to stdout (the standard output). The most useful stuff (the stack trace) is entirely lost.

You should ensure the stack trace is not lost by at least calling e.printStackTrace() which will send the stack to stderr (the error output).

The very best, however, is to include a Logger utility. The basic one is included like this:

import java.util.logging.Logger;

// assumes the current class is called MyLogger
private final static Logger LOGGER = Logger.getLogger(MyLogger.class.getName());

And used like this to display both message and stack:

LOGGER.log("My message", theException); // Replaces both System.out.println() and printStacktrace()

Null checking

if (next == null) {
    System.out.println("invalid next string");
    return;
}

When encountering null values, you can always throw a InvalidArgumentException, InvalidStateException or the like. If you just return, the user will assume everything went well, although there is a big problem in your Object state. Which brings my next point...

Early error-checking

Fail-fast is always a good Idea. Ideally, no null reference should enter the object if you can't later handle it on your own. So upon obtaining parameters, check them and fail.

public void start(String entryPoint) throws InvalidArgumentException{
    if(entryPoint == null){ 
        throw new InvalidArgumentException("blahblahblah");
    }
    this.queue.add(entryPoint);
    this.tryNext();
}

Of course, same for addURL and the like. Don't let people mess with your object state!

Don't forget the power of Javadoc!

If you're new to Java, you might not yet relize how much a good Javadoc saves your day. Just make it happen. Don't be verbose, stay concise. A good Javadoc is not a book. Some methods (getters, setters) don't need anything ideally.

Familiarize yourself with this aspect of Java! It is as much part of the language as the for loop.

Do little and less in main

Did you chose this method's name? No. It's not part of your program, of the crawler, of anything. It is simply an arbitrary entry point, never to be used again. Keep it that way, delegate the real work to a method of an object of your design, one with meaning. This will add so much more ease of use and fonctionality.

This is what all your main methods should look like:

public static void main(String[] args){
    new MyBysinessObject(args).startDoingSomethinguseful();
}

Further cleanup

A few other methods reuire cleaning up, mostly being moved to some other object. If you need to call:

c.done(this, this.url);

That probably means that should be reversed:

this.done(c);

But it is probably because your Crawler is actually a ThreadManager of some sort, and is bound to disappear. I'll adress this when /if the code has been corrected.

---

I've been trying to learn Java for the last day or two.

Ha! My first attempt at Java wasn't anywhere near as good-looking. Great job!