Duplicate DeDuplicators?

A question on the Heritrix mailing list prompted my to write a few words about deduplication in Heritrix and why there are multiple ways of doing.

Heritrix's built in service

Heritrix's inbuilt deduplication service comes in two processors. One processor records each URL in a BDB datastore or index (PersistStoreProcessor), the other looks up the current URL in this datastore and, if it finds it, compares the content digest (FetchHistoryProcessor).

The index used to be mingled in with other crawler state. That is often undesirable as you may not wish to carry forward any of that state to subsequent crawls. Typically, thus, you configure the above processors to use their own directory by wiring in a special "BDB module" configured to write to an alternative directory.

There is no way to construct the index outside of a crawl. Which can be problematic since a hard crash will often corrupt the DBD data. Of course, you can recover from a checkpoint, if you have one.

More recently, a new set of processors have been added. The ContentDigestHistoryLoader and ContentDigestHistoryStorer. They work in much the same way except they use an index that is keyed on the content digest, rather than the URL. This enables URL agnostic deduplication.

This was a questionable feature when introduced, but after the changes made to implement a more robust way of recording non-URL duplicates, it became a useful feature. Although its utility will vary based on the nature of your crawl.

As this index is updated at crawl time, it also makes it possible to deduplicate on material discovered during the same crawl. A very useful feature that I now use in most crawls.

You still can't build the index outside of a crawl.

For more information about the built in features, consult the Duplication Reduction Processors page on the Heritrix wiki.

The DeDuplicator add-on

The DeDuplicator add-on pre-dates the built in function in Heritrix by about a year (released in 2006). It essentially accomplishes the same thing, but with a few notable notable differences in tactics.

Most importantly, its index is always built outside of a crawl. Either from the crawl.log (possibly multiple log files) or from WARC files. This provides a considerable amount of flexibility as you can build an index covering multiple crawls. You can also gain the benefit of the deduplication as soon as you implement it. You don't have to run one crawl just to populate it.

The DeDuplicator uses Lucene to build its index. This allows for multiple searchable fields which in turn means that deduplication can do things like prefer exact URL matches but still do digest only matches when exact URL matches do not exist. This affords a choice of search strategies.

The DeDuplicator also some additional statistics, can write more detailed deduplication data to the crawl.log and comes with pre-configured job profiles.

The Heritrix 1 version of the DeDuplicator actually also supported deduplication based on 'server not modified'. But it was dropped when migrating the H3 as no one seemed to be using it. The index still contains enough information to easily bring it back.

Bottom line

Both approaches ultimately accomplish the same thing. Especially after the changes that were made a couple of years ago to how these modules interact with the rest of Heritrix, there really isn't any notable difference in the output. All these processors, after determining an document is a duplicate, set the same flags and cause the same information to be written to the WARC (if you are using ARCs, do not use any URL agnostic features!)

Ultimately, it is just a question of which fits better into your workflow.

Preservation Working Group Web Archiving Deduplication Survey

The IIPC Preservation Working Group is conducting a survey of member institutions deduplication activities. If you or your institution hasn't yet responded, I urge you to do so. Right now. Don't worry, I'll wait.

Answering the survey for my own institution brought up a few things I'd like to go into in greater detail than was possible in the survey.

What kind of content do you deduplicate?

We've been doing deduplication for over nine years. In that time we've done some analysis on this from time to time. Most recently last December which led to this blog posts on deduplication of text based data.

Ultimately, it boils down to a trade off between the impact the deduplication has on crawl rate and the potential savings in terms of storage. For our large, thrice yearly crawls we're now only excluding data whose content type equals "text/html".

HTML documents make up over half of all documents, but they are generally small, frequently created dynamically and compress easily. In other words, they make the deduplication index much bigger while not contributing much to deduplication space saving.

Despite this, for our weekly and other focused crawls, we do deduplicate on all content types as those crawls' speeds are usually dictated by politeness rules. Deduplicating on all content types thus comes at near zero cost. Also the more frequent crawl schedules means that there is, relatively, more savings to be had from deduplicating on HTML than in less frequent crawls.

One aspect that the survey didn't tackle, was on which protocols and response types we deduplicate. We currently do not deduplicate on FTP (we do not crawl much FTP content). We also only deduplicate on HTTP 200 responses. I plan to look into deduplicating on 404 responses in the near future. Most other response types have an empty or negligible payload.

If you deduplicate, do you deduplicate based on URL, hash or both?

Historically, we've only done URL based deduplication. Starting with the last domain crawl of 2014, we've begun rolling out hash based deduplication. This is done fairly conservatively with the same URL being chosen as the 'original' when possible. This has an impact on crawl speeds and we may revise this policy as we gain more confidence in hash based deduplication.

The reason why hash based deduplication hasn't been used earlier is all about tool support. OpenWayback has never had a secondary index to look up based on hashes. It wasn't until we introduced additional data into the WARC revisit records that this was possible. This has now been implemented by both Heritrix and OpenWayback making hash based deduplication viable.

The additional savings gained by hash based deduplication are modest or about 10% in our crawls. In certain circumstances, however, they may help deal with unfortunate website design choices.

For example, one media site we crawl recently started adding a time code to their videos' URLs so their JavaScript player could skip to the right place in them. The time code is an URL parameter (e.g. "video.mp4?t=100") that doesn't affect the downloaded content at all. It is merely a hint to the JavaScript player. With crawl time hash based deduplication, it is possible to store each video only once.

How do you deduplicate?

This question and the next few after it addresses the same issues I discussed in my blog post about the downsides of web archive deduplication.

The primary motivation behind our deduplication effort is to save on storage. We wouldn't be able to crawl nearly as often without it. Moreover, our focused crawls would be impossible without deduplication as we discard as much as 90% of data as duplicates in such crawls.

Even doing a single 'clean' (non deduplicated) crawl every two years would mean we had to go from three to two crawls a year due to our storage budget. So we don't do that.

It's an arguable tradeoff. Certainly, it is going to be more difficult for us to break out discrete crawls due to the reduplication problem. Ultimately it comes down to the fact that what we don't crawl now is lost to us, forever. The reduplication problem can be left to the future.

That just leaves...

Do you see any preservation risks related to deduplication? 
Do you see any preservation risks related to deduplication and the number of W/ARC copies the institution should keep? 

In general, yes, there is a risk. Any data loss has the potential to affect a larger part of your archive.

To make matters worse, if you lose a WARC you may not be able to accurately judge the effects of its loss! Unless you have an index of all the original records that all the revisit records point to, you may need to scan all the WARCs that could potentially contain revisit records pointing to the lost WARC.

This is clearly a risk.

You also can't easily mitigate it by having some highly cited original records be stored with additional copies as those original records are scattered far and wide within your archive. Again, you'd need some kind of index of revisit references.

We address this simply by having three full copies (two of which are, in turn, stored on RAID based media). You may ask, but doesn't that negate some of the monetary savings of deduplication if you then store it multiple times? True, but we are going to want at least two copies at a minimum. Additionally, only one copy need be on a high speed, high availability system (we have two copies on such systems) for access. Further copies can be stored in slower or offline media which tends to be much cheaper.

Whether three (technically 3.5 due to RAID) is enough is then the question. I don't have a definitive answer. Do you?

The downside of web archive deduplication

I've talked a lot about deduplication (both here and elsewhere). It's a huge boon for web archiving efforts lacking infinite storage. Its value increases as you crawl more frequently, and crawling frequently has been a key aim for my institution. The web is just too fickle.

Still, we mustn't forget about the downsides of deduplication. It's not all rainbows and unicorns, after all.

Using proper deduplication, the aim is that you should be able to undo it. You can dededuplicate, as it were, or perhaps (less tongue-twisty) reduplicate. This was, in part, the reason for the IIPC Proposal for Standardizing the Recording of Arbitrary Duplicates in WARC Files.

So, if it is reversible, there can't be a downside? Right? Err, wrong.

We'll ignore for the moment the fact that many institutions have in the past done (and some may well still do) non-reversible deduplication (notably, not storing the response header in the revisit record). There are some practical implications of having a deduplicated archive. The two primary ones are loss potential and loss of coherence.

Loss potential

There is the adage that 'lots of copies keeps stuff safe'. In a fully deduplicated archive, the loss of one original record could affect the replay of many different collections. One could argue that if a resource is used enough to be represented in multiple crawls, it may be of value to store more than one copy in order to reduce the chance of its loss.

It is worrying to think that the loss of one collection (or part of one collection) could damage the integrity of multiple other collections. Even if we only deduplicate based on previous crawl for the same collection there are implications to data safety.

Complicating this is the fact that we do not normally have any oversight over which original records have a lot of revisit records referencing them. It might be an interesting ability, to be able to map out which records are most heavily cited. This could enable additional replication when a certain threshold is met.

Concerns about data safety/integrity must be weighed against the cost of storage and the likelihood of data loss. That is a judgement each institution must make for its own collection.

Loss of coherence

While the deduplication is reversible (or should be!), that is not to say that reversing it is trivial. If you wish to extract a single harvest from a series of (lets say) weekly crawls that have been going on for years, you may find yourself resolving revisit records to hundreds of different harvests.

While resolving any one revisit is relatively cheap, it is not entirely free. A weekly crawl of one million URLs, may have as many as half a million revisit records. For each such record you need to query an index (CDX or otherwise) to resolve the original record and then you need to access and copy that record. Index searches take in the order of hundreds of milliseconds for non-trivial indexes and because the original records will be scattered all over, you'll be reading bits and pieces from all over your disk. Reading bits and pieces is much more costly on spinning HDDs than linear reads of large files.

Copying this hypothetical harvest might only take minutes if non-deduplicated. Creating a reduplicated harvest might take days. (Of course, if you have an Hadoop cluster or other high performance infrastructure this may not be an issue.)

I'm sure there are ways of optimizing this. For example, it is probably best to record all the revisits, order them and then search the index for them in the same order as the index is structured in. This will improve the indexes cache hit. Similar things can be done for reading the originals from the WARC files.

There is though one other problem. No tool, currently, exists to do this. You'll need to write your own "reduplicator" if you need to do this.


Neither of these issues is argument enough to cause me to abandon deduplication. The fact is that we simply could not do the web archiving we currently do without it. But it is worth being aware of the downsides as well.

Answering my own question. Does it matter which record is marked as the original?

Back in October, I posed the question about web archive deduplication, does it matter which record is marked as the original?

I've come up with a least one reason why it might matter during playback.

Consider what happens in a replay tool like OpenWayback when it encounters a revisit record. The revisit record should contain information about the original URL and original capture time. The replay tool then has to go and make another query on its index to resolve these values.

If the URL is the same URL as was just resolved for the revisit record itself, it follows that any cache (including the OS disk cache for a CDX file) will likely be warm, leading to a quick look up. In fact, OpenWayback will likely just be able to scroll backwards in its 'hit' list for original query.

On the other hand, if the URL is different it will be located in a different part of the index (whether it is a CDX file or some other structure) and may require hitting the disk(s) again. Any help form the cache will be incidental.

Just how much this matters in practice depends on how large your index is and how quickly it can be accessed. If it is served from a machine with super fast SSDs and copious amounts of RAM, it may not matter at all. If the index is on a 5400 RPM HDD on a memory starved machine it may matter a lot.

In any case, I think this is sufficient justification for keeping the deduplication strategy of preferring exact URL matches when available while allowing digest only matches when there isn't.

Deduplicating text based data

In my last two posts about deduplication, you may have noticed the following caveat:

It should also be noted that only URLs whose content (mime) type did not begin with "text/" were deduplicated.

The reasons for ignoring text documents derive from analysis I did 8-9 years ago when first developing the DeDuplicator. The basic argument was essentially, that HTML documents (which at the time were the overwhelming type of plain text documents) were highly dynamic (yielding little by way of deduplication), generally small and highly compressible.

The first and last assumptions are still true, but HTML files have certainly gotten bigger in the interim. Perhaps more importantly, other text files are becoming more common and may benefit from deduplication. For example, CSS and JavaScript files are unlikely to change very frequently and have gotten much larger. Also, commonly used JavaScript libraries are replicated across many websites.

So, I figured it was time to do a little analysis and see what numbers came up. I've used the same crawl logs as were discussed in the two last posts.

In my last post there was a table that showed that a total of 73.6 million URLs had been exempted from deduplication based on mime type. This is about two thirds of all URLs crawled. This is a bit misleading as it includes non-200 responses. When we limit ourselves to 200 responses, the actual number is 53.9 million. Thus text documents account for 62% of URLs

The table also showed that these URLs accounted for about 2.3 TiB of the data collected, about 32% of all the data (that is about right as non-200 responses usually have no or negligible payload). Clearly the average uncompressed file size of text documents is much smaller than of non-text documents.

Of the 2.3 TiB, 25% could have been deduplicated (553 GiB). By URL, it was about 26% overall.

I didn't attempt to break it down to exact-url, digest and crawl time deduplication.

Looking at it further, about half of the duplicate data was from non-HTML documents. More interesting is that while 14 million of the 50 million HTML documents were deemed duplicates, 2 million of the 3.1 million non-HTML text documents were deemed duplicates. The probability of a non-HTML text document being a duplicate is very high (almost comparable to non-text documents) and it size is, on average, much larger than that of an HTML document.

This is pretty conclusive. Including non-HTML text documents in deduplication yields significant savings and is fairly cheap in terms of index size and number of additional lookups.

The savings with regards to HTML is more questionable. By more than doubling the number of lookups there is a potential saving of about 5% of the total compressed data size (assuming 60% compression, which is likely conservative). With a larger index, the cost of each lookup also becomes more expensive.

Unless resources are plentiful, I believe that skipping HTML documents when deduplicating is still a reasonable choice for large scale crawls. For focused crawls (especially those conducted on short intervals), I would however recommend including HTML content.

URI agnostic deduplication on content discovered at crawl time

In my last blog post I showed that URI agnostic duplicates accounted for about 5% of all duplicates by volume (bytes) and about 11% by URI count. But this is limited to looking up content digests that had been discovered in a previous crawl. What if we also deduplicated on content digests that are discovered during a crawl?

So I put together a little script and set it lose on the crawl logs for the domain crawl. As before I only considered documents whose content (mime) type does not start with "text/".

In all, this would have increased the number of duplicates found by 3.5%. It would also increase the number of bytes deemed duplicate by 3.5%.

In practical terms this means I could have avoided storing 121 GiB of data. This is about 9.2% of the data volume that was subjected to deduplication and deemed novel. Or 3.3% of the overall data volume deemed novel and stored.

The following is a table showing the actual numbers. The difference between the total and 'subject to deduplication' is made up of URIs whose content type started with "text/".

	URIs	GiB
Total:	106.690.792	7.127
Subject to deduplication:	33.096.219	4.791
Deemed duplicates (total):	24.522.409	3.477
- Exact URL matches:	18.505.138	2.941
- Canonical URL matches:	3.273.397	353
- Digest only matches:	2.743.874	176
Missed digest at crawl time matches:	853.013	121

So there doesn't seem to be that much gain from tackling this class of duplicates. Heritrix does offer a tool for this  (that I haven't tried). I think it'll come down to how difficult this is to implement and its effect on performance. If its easy and doesn't hurt performance, reducing data volume by 3-4% can add up.

The results of URI-agnostic deduplication on a domain crawl

During the recently completed .is domain crawl, URI-agnostic deduplicaction was employed for the first time. Until now, .is domain crawls have only deduplicated in instances where the same URI served up identical content to that observed during the most recent prior crawl.

It should be noted that the URI-agnostic deduplication only relied on the data from the index created pre-crawl. It did not try to deduplicate on documents that were discovered for the first time during the crawl.

It should also be noted that only URLs whose content (mime) type did not begin with "text/" were deduplicated. Generally, deduplicating on HTML and other text based documents yields limited results due to them being dynamically generated and heavily compressible. We will be looking at this class in the future.


The deduplication index contained all known URIs for known hashes. This made it possible to record for each encountered duplicate if it was...

• An exact URL match.
  Meaning that that exact URL had already been recorded as having this payload
• A canonical URL match.
  Meaning that an URL whose canonical form is identical to the current URL's canonical form had already been recorded as having this payload. The canonicalization employed is the same one utilized by OpenWayback when determining URL equivalency. Exact URL matches do not count as canonical matches.
• A digest only match
  Meaning that we have recorded an unrelated URL as having the same payload. Exact and canonical URL matches do not count towards this.

The results:

• Exact URL: 75,46% of URLs, 84.58% of bytes deduplicated
• Canonical URL: 13,35% of URLs, 10.15% of bytes deduplicated
• Digest only: 11,19% of URLs, 5.07% of bytes deduplicated

As you can see, allowing URI-agnostic does not significantly affect the amount of data that can be deduplicated. It is also clear that it is primarily smaller files that are likely to be deduplicated in this manner.

In all, URI-agnostic deduplication saved 176 GiB in a crawl that ultimately required 2.1 TiB of storage space. So even if we assume that none of the 176 was compressible it is a saving of 7.6%. The actual value is probably closer to 5%.

If you count canonical URL matches as URI-agnostic (it is an arguable point) then the number rises notably to 19.7%.

Webarchive deduplication. Does it matter which record is marked as the original?

We've been doing deduplication in webarchiving for a long time now. But, due to limits in our tools and storage format (WARC) it has always been, so called, URL based deduplication. I.e. we record that this capture of a particular URL is a duplicate (or revisit if you prefer). The content isn't stored and playback software simply moves 'backwards in time' until it finds the original record.

With recent clarifications to the WARC spec adopted by the IIPC and implemented in tools like Heritrix and OpenWayback we are no longer limited to this URL based deduplication.

With Heritrix 3.3.0 (still in development) now having robust handling for 'url agnostic' or 'digest based' deduplication, I set out to update my DeDuplicator software, an add-on for Heritrix. Implementing digest based deduplication was super easy.

But something nagged at me.

Consider the following scenario. You are crawling URL A. Its content digest indicates that it is a duplicate of URL A from some earlier crawl (lets call this A-1), but is also a duplicate of URL B. B may have been crawled at the same time (i.e. during the same harvesting round) as A-1, or at another time altogether, including earlier during the current round of harvesting.

Obviously, if we didn't have A-1, we would deduplicate on B and say that A is a duplicate of B. That's the whole point of digest based deduplication.

But, if you do have A-1, does it matter which one A is declared a duplicate of?

During large scale crawling you need lookups in your deduplication index to be as efficient as possible. Doing simple lookups on digests is more performant than doing a lookup on both digest and URL (or searching within a result set for the digest). Additionally, you can make the index smaller by only including one instance of each digest in the index.

But this bowing to performance means that it is blind chance whether A-1 or B will be designated as the 'original' for A.

The engineer in me insist that this is irrelevant. After all, if we didn't have A-1, we'd want to use B. So does the existence of A-1 in our archive really matter.

I haven't been able to come up with any solid argument for preferring A-1. Logically, it shouldn't matter. But, somehow, it just feels off to me.

If anyone has a concrete technical or practical reason for preferring A-1 (when available) please share!

Thank you.

Edit: In response to Peter Websters comment, let me just clarify that replay tools (e.g. OpenWayback) would still be aware of A-1, is it would be in their index, and they would show it as the precursor to A. The link between A and B would be considered incidental (as far as replay tools are concerned) and would not be directly evident to users.

Update: I've come up with at least one reason why it might matter. See my blog post answering my own question.