URL Prioritisation

[jnioche]

Copied from @anjackson Some feedback on the URL Frontier API #11

It's a critical part of the role of the Frontier, but it's currently absent from the API entirely. Of course, there are lots of ways of doing prioritisation, and this makes it hard to standardise. But in the absense of standardisation, this will be dependent on out-of-band conventions that will affect compatibility between different implementations.

For example, among other things, we use hop-path depth to influence prioritisation, which works fine because the underlying frontier implementation just stores an prioritisation number that's used as a key prefix. The downside of this model is URL prioritisation is fixed at insertion time, and re-prioritising URLs is hard. The proposed Frontier API does not support prioritisation explicitly, so this would have to be a metadata key convention shared by fetcher and frontier implementation.

A more flexible approach is to prioritise when URLs are released from the frontier, e.g. by storing metadata fields like hop-path in the frontier and changing the prioritisation query to use the metadata. But this still relies on the fetchers knowing that the necessary metadata fields must be supplied.

Perhaps there's not much to be done about that at the API level. But it would be crucial for cross-crawler compatability that any metadata conventions are declared somehow.

and from #2

The 'ordered by next fetch date` queue prioritisation is not terribly appealing to me to be honest. I can see it working in the case where you pretty effectively get through the queues, but TBH we've moved away from scheduling future crawls directly in the frontier because it makes it difficult for change the schedules. i.e. we're using the H3 frontier to prioritise the backlog and manage crawl delay. We launch and relaunch crawls using external cron jobs that inject launch events into the crawler. This means if we want to stop recrawling (for example), we just don't request a recrawl. But perhaps there's a better way?

[jnioche]

Hi @anjackson

Things have changed a bit since my comment in December.

Discovered URLs are not expected to have a nextFetchDate - in fact the term is now refetchable_from_date; they are expected to be fetched as soon as possible FIFO-style. It's only updated URLs ('known') that can have a _refetchable_from_date, and they don't have to have one. If not they are considered finished. You could however manage that with an external cron job and push an update for the URL with a fetch date to resuscitate it.

Changing the priority of URLs at query time is indeed more flexible and could be done via metadata. Would that just be a matter of adding an optional param to GetParams to be able to specify one or more metadata keys to be used to sort URLs within a queue? It doesn't solve the problem of whether backends support the functionality but at least for those which will, it provides a mechanism to do so.

[jnioche]

@anjackson the RocksDB implementation sorts the URLs for scheduling based on the following key (see RocksDBService)

schedulingKey = (keyNormalisation(Qkey) + "" + nextFetchDate + "" + url) .getBytes(StandardCharsets.UTF_8);

You can put the robots.txt URL to the front of the queue at any time by sending it to the Frontier as a known URL and give it a very early refetchable_from_date e.g. 01/01/1970. This way, it will be sent to the crawler before any other URLs.

This is similar to the way the scheduling is handled is StormCrawler with the various backends. In most cases discovered URLs use NOW as a date, which is what happens with URLFrontier under the bonnet.

[anjackson]

Thanks @jnioche - I was wondering about that.

I think I can make that work with Heritrix's lower number = higher priority prioritisation scheme. As you're concatenating the strings, a nextFetchDate of e.g. 2 will sort after a nextFetchDate of e.g. 1631133448, but I think I can work around that by using 1000000000 + priority. That plus using the BlockQueueUntil to implement Heritrix's crawl delay logic should work fine I think.

Would it be worth me making a PR to add a meta['priority'] field to pass this into the RocksDBService as an explicit parameter rather than a date hack? And/or to make the sort order work numerically rather than lexicographically?

[jnioche]

I think I can make that work with Heritrix's lower number = higher priority prioritisation scheme. As you're concatenating the strings, a nextFetchDate of e.g. 2 will sort after a nextFetchDate of e.g. 1631133448, but I think I can work around that by using 1000000000 + priority

The timestamps are of type long and correspond to the number of seconds since epoch. Now for instance is 1631267514 and a date long in the future e.g. 22 Feb 2222 22:22:22 GMT -> 7956915742, so when represented in text, we could assume that it usually takes 10 chars. Instead of 1000000000 + priority we could simply prepend 0s to the String representation of the chars if they are not 10 chars long already? This way we'd get a strict numerical sort order.

Setting dates in the future is needed for scheduling revisits of URLs which is maybe not relevant to Heritrix if it does crawl once only so you could indeed have all your URLs scheduled into the past. Out of interest, what is the range of values in Heritrix for the priorities?

That plus using the BlockQueueUntil to implement Heritrix's crawl delay logic should work fine I think.

That's not quite what that method was about but if it is the only way of implementing Heritrix's logic - then why not! That method is not streamed so that would mean a call the Frontier per queue, so not sure about its efficiency.

I see in the Heritrix conf that the delay factor is set based on the time it took to fetch the previous URL. We could have something similar in the Frontier whereby the QueueMetadata would track when a particular URL was emitted and when it got updated as finished. Or add a new field in the schema for the time it took to fetch a URL when it is an update and adapt the delay in the queue accordingly. The latter would be more accurate as the former would include time spent in parts of the process which are not fetching as such. It would also be more efficient as it would save a call to the Frontier and back for every time a URL is fetched. Ideally, this would be configurable and users could decide whether to use it or not.

What do you think @anjackson?

[anjackson]

Given the stage things are at, I don't think we should put Heritrix's crawl-delay behaviour into URL Frontier just yet. I think I'd like to get the proof-of-concept working first. Also, I think it would likely be possible to use SetDelay rather than BlockQueueUntil and cache the values so Heritrix3 only sends an update when necessary. That's probably good enough to show how it might work.

Oh, and yes, zero-padding the nextFetchDate sounds good to me.

One additional thought that came up was that I don't really understand how scaling-out is expected to work. i.e. if there were multiple Heritrixen/crawlers, would that just work and e.g. not send URLs from the same queues to multiple crawlers simultanously? Or would some kind of partitioning have to be added? Or is that all out of scope?

[jnioche]

Given the stage things are at, I don't think we should put Heritrix's crawl-delay behaviour into URL Frontier just yet. I think I'd like to get the proof-of-concept working first.

Makes sense.

Also, I think it would likely be possible to use SetDelay rather than BlockQueueUntil and cache the values so Heritrix3 only sends an update when necessary. That's probably good enough to show how it might work.

Great!

Oh, and yes, zero-padding the nextFetchDate sounds good to me.

Ok, will add that.

One additional thought that came up was that I don't really understand how scaling-out is expected to work. i.e. if there were multiple Heritrixen/crawlers, would that just work and e.g. not send URLs from the same queues to multiple crawlers simultanously? Or would some kind of partitioning have to be added? Or is that all out of scope?

At the moment the Frontier does not distinguish between clients and might send URLs from the same queue to different crawlers. In StormCrawler for instance, one of the bolts routes the incoming tuples to a specific instance of a Fetcher based on the hostname but for other crawlers, there might not be such a guarantee. One way around it would be to assign one instance of the Frontier to a specific crawler so that it reads and writes only to that instance. That would work as long as there is a way of injecting the URLs for the queues to a specific instance of a crawler in the first place.