Mini 1: Distributed Crawler

Some of you have written a web crawler before, maybe in Java with Jsoup and Apache Commons HTTP. In this mini, you'll write one again, this time in Rust (async, on top of tokio), with a twist: the crawl is split across several crawler processes (nodes). Each node crawls many pages in parallel, and the nodes coordinate through a shared Redis instance. You'll drive the whole thing from a small command-line tool.

The Task

Given a base path, crawl every page reachable from it and collect a few statistics about what you find. The result of a crawl is a WebStats:

pub struct WebStats {
    // the total number of (unique) files found
    pub num_files: usize,
    // the total number of (unique) file extensions (.jpg is different from .jpeg)
    pub num_exts: usize,
    // the total number of files for each extension
    pub ext_counts: HashMap<String, usize>,
    // the total number of words in all HTML files combined, excluding
    // all HTML tags, attributes, and HTML comments
    pub total_word_count: u64,
}

Files. A file is any URL under the base path that you find a link to and that actually exists: HTML pages, but also images, zips, PDFs and so on. Broken links don't count. You don't need to download a whole zip to know it's there; a HEAD request will do.

Same URL or not? Drop the fragment, so page.html#intro and page.html#usage are both just page.html. For other corner cases, do what's reasonable and mention your choices in the README.

Words and extensions. A page counts as HTML if its Content-Type says so, whatever its URL looks like. When counting words, lowercase the text first (so Ant and ant are the same word) and only count strings that begin with a-z. Beyond that, our definition of a word is pretty loose, so do what's reasonable. Extensions are lowercased too, so JPEG and jpeg are the same extension. (jpg and jpeg are still different.) A URL with no extension, such as /api/ or /docs/intro, counts as html.

The base path. As a familiar example, submitting

https://cs.muic.mahidol.ac.th/courses/ooc/api/

means the crawl starts at that page and only retrieves URLs that begin with this base path. This matters. If you follow links outside the base path, you may end up crawling a good chunk of the Internet. When you crawl a page p, parse it fully and follow every hyperlink on p that falls under the base path.

We won't publish "correct" stats for any site. Pick a few sites of your own to try, and compare notes with your classmates.

The CLI

Users interact with the cluster through a single binary (call it crawl, or something better). It should support at least the following:

• crawl node starts a crawler node that joins the cluster, given the Redis instance's address. Run it N times, on one machine or on several.
• crawl submit <url>... submits one or more URLs. Each URL is its own crawl job, with that URL as both starting point and base path. The command prints a job ID for each and returns right away; it doesn't wait for the crawl. If a URL has already been submitted, don't crawl it again. Just print the existing job's ID.
• crawl status <job> prints a snapshot of the job's progress: pages crawled so far, pages waiting in the frontier, pages in flight, whether the job is done, and anything else you find useful.
• crawl status -f <job> follows the job, printing updates as progress is made (think tail -f) and exiting once the job finishes. Polling Redis every so often is perfectly fine; pub/sub or keyspace notifications are fancier options. Your call.
• crawl stats <job> prints the job's WebStats. The stats should be available as soon as the job is done, with no restart or manual step in between, and should stick around until Redis is cleared or shut down. If the job isn't done yet, say so rather than printing partial numbers.

A session might look something like this. The exact output format is up to you.

$ crawl submit https://cs.muic.mahidol.ac.th/courses/ooc/api/ https://example.org/docs/
job 7f3a  https://cs.muic.mahidol.ac.th/courses/ooc/api/
job 91c2  https://example.org/docs/

$ crawl status 7f3a
crawled 812   frontier 140   in flight 24   running

$ crawl status -f 7f3a
crawled 836   frontier 131   in flight 24   running
crawled 901   frontier 88    in flight 24   running
...
crawled 1540  frontier 0     in flight 0    done

$ crawl stats 7f3a
files: 1540   extensions: 6   words: 1283077
  html 1391   css 12   js 41   png 88   gif 7   zip 1

The CLI talks only to Redis, not to the nodes directly. That keeps things simple, and it means the CLI works no matter how many nodes are running.

Core Design Requirements

• N ≥ 1 nodes. N is the number of separate crawler processes. They can all run on one machine or be spread across several; it shouldn't matter to your code. It's fine for all nodes to be started up front, and a single-node run should work too.
• Redis for coordination. Nodes and the CLI coordinate through a single Redis instance, which runs in Docker. The crawler processes themselves run directly on the host, not in containers, and reach Redis by IP address. What lives in Redis (jobs, frontiers, visited sets, progress counters, partial counts, …) is your call.
• Each page is crawled once. Within a job, no URL should be fetched more than once across the whole cluster. Two nodes that discover the same link at the same time must not both crawl it. This is the heart of the mini, so think carefully about which Redis operations are atomic.
• Several jobs at once. Several jobs can be running at the same time, and they shouldn't step on each other's toes.
• Parallel within a node, too. Each node should crawl several pages concurrently, not one at a time, using tokio tasks. Keep it to at most 10 requests in flight per node.
• Knowing when you're done. The cluster must figure out, on its own, when a job is finished. This is trickier than it looks: an empty frontier doesn't mean you're done if another node is still halfway through a page that's about to produce new links.
• Same answer, any N. A job's WebStats from a run on N nodes should match a single-node run on the same site.
• Failure model. Assume nodes don't crash, Redis doesn't crash, and the network behaves. For now, the only thing that can go wrong is our own code. (Crashing nodes are covered in the extra challenge.)

Concurrency. One effective way to avoid crawling pages twice is breadth-first search. Given the current frontier, you crawl all of its pages in parallel, across nodes and within each node, to build the next frontier. Another way is to drop the lock-step rounds and keep one shared work queue that nodes pull from and push to. Both work, and there are others. Choose whichever you can argue is correct.

Exclusionary

You don't need to honor robots.txt or implement politeness policies beyond the per-node cap above. You don't need to run JavaScript or handle pages that are rendered client-side, you don't need to cancel jobs, and you don't need to recover from crashed nodes.

How to hand in

• Your code, along with its build configuration (Cargo.toml and friends).
• A way to start Redis in Docker (a one-line docker run or a small docker-compose.yml).
• A README that explains how the nodes coordinate, how progress is tracked, and how the cluster knows a job is done. It should also give step-by-step instructions to start Redis, launch N nodes pointed at it, and use the CLI. We'll use it to run your crawler ourselves after demo day.

Getting Started & Hand-in Instructions

This mini is individual. You'll work in your own GitHub repository.

• Create a repository on GitHub for this mini, and keep it private until after your demo.
• Follow good commit and branching practices.
• Tag the version you want graded as 1.0.0.
• Submit the repository's URL on the course LMS.

Demo day. You'll demo your crawler live, running several nodes plus the CLI. Find another person to help you on the day. Once you've demoed, make the repository public so we can grade it.

Tips and Pointers:

• reqwest is async out of the box and runs on tokio, so it's a natural fit. Share one Client across tasks (it's cheap to clone), and stay away from the blocking feature. It also does HEAD requests.
• The redis crate works well with tokio. Turn on the tokio-comp feature and use a MultiplexedConnection, which is cheap to clone and safe to share across tasks. It supports async pub/sub too, if you go that route for status -f. (Add connection-manager if you want automatic reconnects.)
• scraper is handy for parsing HTML, pulling out links and extracting text. Parsing is synchronous, and its Html type isn't Send, so parse and extract what you need in one go instead of holding the document across an .await.
• clap makes the subcommands and the -f flag painless.

Extra Challenge (for No Real Credit)

Make your crawler survive a node being killed mid-crawl. The job should still finish, with every page counted exactly once. Leases or timeouts on claimed URLs are a good place to start.