Implementing a POC Async Web Crawler

Question

I've created a small proof of concept web crawler to learn more about asynchrony in .NET.

Currently when run it crawls stack overflow with a fixed number of current requests (workers).

I was interested if I have made any common mistakes and if there is more of the framework / TPL I could be using to reduce the amount of code used.

To run it you would need to install the HtmlAgilityPack.

I am only really interested in feedback on program structure and the asynchronous aspects of it.

class Program
{
    static void Main(string[] args)
    {
        var crawler = new WebCrawler();
        crawler.Start();
    }

    public class WebCrawler
    {
        private readonly HttpClient client;
        private const string SiteUrl = "http://stackoverflow.com";
        private CrawlList crawlList;
        private const int MaxWorkers =5;
        private int workers;

        public WebCrawler()
        {
            client = new HttpClient();
            crawlList = new CrawlList();
        }

        public void Start()
        {
            crawlList = new CrawlList();
            crawlList.AddUrl(SiteUrl);

            do
            {
                if (workers >= MaxWorkers) continue;

                if (!crawlList.HasNext()) continue;

                Interlocked.Increment(ref workers);

                Debug.Write("Workers " + workers);
                ProcessUrl(crawlList.GetNext());

            } while (crawlList.HasNext() || workers > 0);

        }

        private async void ProcessUrl(string url)
        {
            Debug.Print("Processing " + url);
            await client.GetAsync(url).ContinueWith(ProcessResponse);
        }

        private async void ProcessResponse(Task<HttpResponseMessage> response)
        {
            Debug.Print("Processing response ");
            var html = await response.Result.Content.ReadAsStringAsync();
            var doc = new HtmlDocument();
            doc.LoadHtml(html);
            var internalLinks = doc.DocumentNode.SelectNodes("//a[@href]").Where(x => x.Attributes["href"].Value.StartsWith("/")).Select(x =>  SiteUrl + x.Attributes["href"].Value).ToList();
            internalLinks.ForEach(x => crawlList.AddUrl(x));

            Interlocked.Decrement(ref workers);
        }
    }

    public class CrawlList
    {
        private readonly ConcurrentBag<string> urlsToCrawl;
        private readonly ConcurrentBag<string> urlsCompleted;

        public CrawlList()
        {
            urlsToCrawl = new ConcurrentBag<string>();
            urlsCompleted = new ConcurrentBag<string>();
        }

        public bool HasNext()
        {
            return urlsToCrawl.Any();
        }

        public string GetNext()
        {
            string url;
            urlsToCrawl.TryTake(out url);
            urlsCompleted.Add(url);
            return url;
        }

        public void AddUrl(string url)
        {
            if (!UrlAlreadyAdded(url))
            {
                urlsToCrawl.Add(url);
                Debug.Print("Adding Url "  + url);
            }
        }

        public bool UrlAlreadyAdded(string url)
        {
            return urlsToCrawl.Contains(url) || urlsCompleted.Contains(url);
        }
    }
}

After runnning through all the suggestions I have a new implementation here below. I think this simple POC covers most of the issues people found with my code previously. Be great to hear back from all the contributers to what they think about it now?

Really liking the Task.WhenAny approach. Think my work is thread safe but that is my only concern.

class Program
    {

        static void Main(string[] args)
        {
            var crawler = new Crawler(5);

            try
            {
                crawler.Crawl("http://cask-marque.co.uk/").Wait();
            }
            catch (AggregateException e)
            {
                foreach (var ex in e.InnerExceptions)
                {
                    Console.WriteLine(ex.InnerException);
                }
                Console.ReadLine();
            }
        }


        public class Crawler
        {
            public readonly CrawlList CrawlList;
            private readonly List<Task<string>> runningTasks = new List<Task<string>>();
            private readonly HttpClient client;
            private readonly int maxConcurrentDownload;
            private const string BaseUrl = "http://cask-marque.co.uk";

            public Crawler(int maxConcurrentDownload)
            {
                CrawlList = new CrawlList();
                client = new HttpClient();
                this.maxConcurrentDownload = maxConcurrentDownload;
                ServicePointManager.DefaultConnectionLimit = maxConcurrentDownload;
            }

            public async Task<bool> Crawl(string startUrl)
            {
                runningTasks.Add(ProcessUrl(startUrl));

                while (runningTasks.Any())
                {
                    var completedTask = await Task.WhenAny(runningTasks);
                    runningTasks.Remove(completedTask);
                    var pageHtml = await completedTask;

                    while (CrawlList.HasNext() && runningTasks.Count < maxConcurrentDownload)
                    {
                        var url = CrawlList.GetNext();
                        runningTasks.Add(ProcessUrl(url));
                    }
                }

                return true;
            }


            private async Task<string> ProcessUrl(string url)
            {
                Console.WriteLine("url " +  url);
                var response = await client.GetAsync(url);
                var content = await response.Content.ReadAsStringAsync();
                var doc = new HtmlDocument();
                doc.LoadHtml(content);
                var urls = doc.DocumentNode.SelectNodes("//a[@href]").Where(x => x.Attributes["href"].Value.StartsWith("/")).Select(x => BaseUrl + x.Attributes["href"].Value).ToList();
                CrawlList.AddUrls(urls);
                return content;
            }
        }

        public class CrawlList
        {
            public readonly Queue<string> UrlsToCrawl;
            public readonly List<string> UrlsCompleted;

            public CrawlList()
            {
                UrlsToCrawl = new Queue<string>();
                UrlsCompleted = new List<string>();
            }

            public bool HasNext()
            {
                return UrlsToCrawl.Any();
            }

            public string GetNext()
            {
                return UrlsToCrawl.Dequeue();
            }

            public void AddUrls(List<string> urls)
            {
                foreach (var url in urls)
                {
                    AddUrl(url);
                }
            }

            public void AddUrl(string url)
            {
                if (UrlAlreadyAdded(url)) return;

                UrlsToCrawl.Enqueue(url);
            }

            public bool UrlAlreadyAdded(string url)
            {
                return UrlsToCrawl.Contains(url) || UrlsCompleted.Contains(url);
            }
        }
    }
}

Answer 1

crawler.Start();

This is very confusing naming. If a method is called Start(), I would expect it to, well, start the work and then return, not do all of the work. A better name would be something like Run(), or maybe even better, something more specific.

---

private const string SiteUrl = "http://stackoverflow.com";

Why is this here? I think this makes much more sense as a constructor parameter, or maybe parameter to Start().

---

private const int MaxWorkers =5;

Again, this should be probably configurable. Also, if you're processing a single website, it doesn't make much sense to have more workers than ServicePointManager.DefaultConnectionLimit, which by default is set to 2.

---

public WebCrawler()
{
    client = new HttpClient();
    crawlList = new CrawlList();
}

public void Start()
{
    crawlList = new CrawlList();

If you're going to set crawlList every time Start() is called, you don't need to set it in the constructor.

---

do
{
    …
} while (crawlList.HasNext() || workers > 0);

So, while some download is in progress, you're going to loop around and waste a whole CPU core doing nothing useful? That's a terrible idea. mariosangiorgio's answer has one way of solving this.

---

await client.GetAsync(url).ContinueWith(ProcessResponse);

You don't need ContinueWith() here, that's what await is for:

var response = await client.GetAsync(url);
await ProcessResponseAsync(response);

This assumes that you're going to change async void ProcessResponse(Task<HttpResponseMessage> response) to async Task ProcessResponseAsync(HttpResponseMessage response), following the Task-based Asynchronous Pattern.

---

var internalLinks = doc.DocumentNode.SelectNodes("//a[@href]").Where(x => x.Attributes["href"].Value.StartsWith("/")).Select(x =>  SiteUrl + x.Attributes["href"].Value).ToList();

Why is this all a single line? You should break it into multiple lines, to make it more readable:

var internalLinks = doc.DocumentNode.SelectNodes("//a[@href]")
    .Where(x => x.Attributes["href"].Value.StartsWith("/"))
    .Select(x =>  SiteUrl + x.Attributes["href"].Value)
    .ToList();

And you could also use query syntax to avoid some repetition:

var internalLinks =
    from node in doc.DocumentNode.SelectNodes("//a[@href]")
    let href = node.Attributes["href"].Value
    where href.StartsWith("/")
    select SiteUrl + href;

Or maybe:

var internalLinks =
    from node in doc.DocumentNode.SelectNodes("//a[@href]")
    select node.Attributes["href"].Value into href
    where href.StartsWith("/")
    select SiteUrl + href;

The difference is that the second version is going to be slightly more efficient that the first one, but I also think it's less readable.

Also, I removed ToList(), see below.

---

internalLinks.ForEach(x => crawlList.AddUrl(x));

I don't think List.ForEach should be used. Instead use foreach, or add something like AddUrls() to your collection.

---

public string GetNext()
{
    string url;
    urlsToCrawl.TryTake(out url);
    urlsCompleted.Add(url);
    return url;
}

So, when urlsToCrawl is empty, you're going to add null to urlsCompleted and then return it? That doesn't sound like a good idea to me.

If this method is supposed to be called only when urlsToCrawl is not empty, then it should throw an exception when it's called incorrectly.

---

public void AddUrl(string url)
{
    if (!UrlAlreadyAdded(url))
    {
        urlsToCrawl.Add(url);
        Debug.Print("Adding Url "  + url);
    }
}

This is not thread-safe. Since this method can be called from multiple threads at the same time, you can end up downloading the same URL multiple times.

Answer 2

        do
        {
            if (workers >= MaxWorkers) continue;

            if (!crawlList.HasNext()) continue;

            Interlocked.Increment(ref workers);

            Debug.Write("Workers " + workers);
            ProcessUrl(crawlList.GetNext());

        } while (crawlList.HasNext() || workers > 0);

Assuming that the first time you hit this block of code you are set up for crawling, you could probably get rid of the first 2 if statements by making this a while loop instead of a do while, something like this

while (crawlList.HasNext() && workers > 0 && workers <= MaxWorkers)
{
    Interlocked.Increment(ref workers);
    Debug.Write("Workers " + workers);
    ProcessUrl(crawlList.GetNext());
}

I also assumed that you wouldn't want to try assigning a worker to the next item on the crawlList if there weren't anymore workers so I changed the or (||) to an and (&&)

I also assumed that you didn't want to go over your max number of workers so I added that into the conditional of the while statement as well.

---

I was looking at this, and thought that you probably want to wait for workers to get freed up and not actually exit the loop when the amount of workers are working are at the programs maximum, you probably want something that will keep the loop going until a worker is freed up.

So, something like this.

while (crawlList.HasNext() && workers > 0)
{
    if (workers > MaxWorkers)
    {
        continue;
    }
    Interlocked.Increment(ref workers);
    Debug.Write("Workers " + workers);
    ProcessUrl(crawlList.GetNext());
}   

Answer 3

I think you should clarify what async is for. It is true that it allows you to run some slow operation outside the main thread but it is not meant as a way to achieve parallelism. It is just a way to allow your application to continue processing without blocking on expensive operations. Have a look at this video which explains it quite clearly.

You obtain multiple threads with your fire and forget execution deriving from async void but you should avoid using them. They should be used only in event handlers.

You need a more structured approach. You need to create several Task instances and start them in parallel. Obviously, each task can perform async operations. This MSDN article is a good starting point on how you can do that.

This is the code I came up with and that should do the trick in a cleaner way.

using System;
using System.Net.Http;
using System.Collections.Generic;
using System.Threading.Tasks;
using HtmlAgilityPack;
using System.Linq;

namespace Async
{
    public class Crawler
    {
        private readonly HttpClient client;
        private readonly int maxConcurrentDownload;
        string baseUrl;

        public Crawler (HttpClient client, string baseUrl, int maxConcurrentDownload)
        {
            this.maxConcurrentDownload = maxConcurrentDownload;
            this.baseUrl = baseUrl;
            this.client = client;
        }

        public async Task<IEnumerable<string>> Crawl(string startUrl)
        {
            var result = new List<string> (); // I know list is not the ideal data structure here. Let's use it for simplicity
            var pagesToProcess = new Queue<string> ();

            var runningTasks = new List<Task<IEnumerable<string>>> ();
            runningTasks.Add (processUrl(startUrl));
            result.Add (startUrl);

            while (runningTasks.Any())
            {
                var firstCompletedTask = await Task.WhenAny (runningTasks);
                runningTasks.Remove (firstCompletedTask);
                var urlsFound = await firstCompletedTask;

                /*
                 * At this point we know the url we found in the page
                 * we finished to process. 
                 * It's time to enque them
                 */
                foreach (var url in urlsFound)
                {
                    if(!result.Contains(url))
                        pagesToProcess.Enqueue (url);
                }
                /*
                 * Now we should start some new Taks
                 * to process new pages
                 */
                while (pagesToProcess.Any () && runningTasks.Count < maxConcurrentDownload)
                {
                    var url = pagesToProcess.Dequeue ();
                    runningTasks.Add (processUrl (url));
                    result.Add(url);
                }
            }
            return result;
        }

        private async Task<IEnumerable<string>> processUrl(string url)
        {
            Console.WriteLine ("Processing {0}", url);
            var response = await client.GetAsync (url);
            var childUrls = await ProcessResponse (response);
            Console.WriteLine ("{0} child urls for {1}", childUrls.Count, url);
            return childUrls;
        }

        private async Task<List<string>> ProcessResponse(HttpResponseMessage response)
        {
            var html = await response.Content.ReadAsStringAsync();
            var doc = new HtmlDocument();
            doc.LoadHtml(html);
            return doc.DocumentNode.SelectNodes("//a[@href]").Where(x => x.Attributes["href"].Value.StartsWith("/")).Select(x => baseUrl + x.Attributes["href"].Value).ToList();
        }
    }
}

This is how you start it:

    public static void Main (string[] args)
    {
        Console.WriteLine ("Starting up!");
        var crawler = new Crawler (new System.Net.Http.HttpClient (), "http://stackoverflow.com", 3);
        crawler.Crawl ("http://stackoverflow.com").Wait();
    }