Algorithm to test file equivalence

I’m writing a program that needs to test if a file is equivalent to one or more other files. To accomplish this, every time we see a new file we stat the file and get the size.

We use the size as a key and if we’ve never seen the size before than we know that’s a new file.

If we have seen that size before we were planning to md5 the first 4k and last 4k of the target file and check to see if that hash has been seen in list associated with the size key.

I don’t want to hash the whole file since these files can be rather large (largest I’ve seen so far is 90G).

The goal is to avoid spending a lot of time on redundant file comparisons. Will this algorithm work, and can it be improved?

More details on my particular problem: I’m attempting to deduplicate a decently sized set of data ( 2Pb ) that contains a large amount of time stamped files (about 40%) created from syslog on FreeBSD machines. Before I start chewing through that many files line by line I wanted to make sure that the file I was looking at hadn’t been seen before.

It sounds like you are trying to optimize the file comparison because that can be a potentially expensive operation:

If two files have different sizes, they must be different files.
If the first and last 4K of two files hash to different values, they must be different files. The first portion will check stuff like a file identifier commonly included in the first few bytes, while the last would help catch cases where a file is being appended to (e.g. a log file), similar to what tail checks.

Next you would have to compare the entire file just to be sure. At this point it might makes sense to store multiple hash values (MD5 if security is not a concern, SHA2, etc). You should be able to find a way to read in the file once and feed it to multiple hash algorithms. Then you store a data structure with all of the hashes, which you can very quickly compare with other data structures for other files.

If all of those tests pass (files likely but not necessarily equal) then you might need to perform a full file comparison.

I think your algorithm sounds reasonable, and I think my minor additions will help.

Based on the clarifications in the question, I think your approach will work. The odds that log files are the same size and the first and last portions hash the same is extremely low. If you use a strong hash algorithm with a large output size (compared to MD5), the chance is even lower: with SHA-512, the internal state and output range are ginormous. Given we are talking about log files that are very likely to have date/time stamps at the start of each line, the input should have enough entropy to make this a non-issue.

Your approach is good… if the files have completely random data. Here are some things to consider:

How bad is it if there are collisions? If you need a mission critical guarantee (e.g. those astronauts on the ISS will die if a collision occurs), your algorithm may not be good enough, even though there are 10^38 possible MD5 hashes. People do win the lottery occasionally, after all, though for random data this is probably safe.
This is the more important one: if the files are all generated in the same way, have similar formatting, records, have header/footer information, etc. then it’s actually possible that these files begin and end exactly the same way – and would thus have the same hash – even though they are not the same.

So, you’re barking up the right tree, but definitely pay attention to the actual details of your use case to ensure you’re not overlooking something obvious.

Data deduplication is also often called “record linkage”, so you may want to also use that as a search term when researching this.

There is an article on the Eventbrite engineering blog that explains how you could greatly reduce the number of file comparisons by using Multi Index Locality Sensitive Hashing. In short, you create a special kind of hash value whereby similar documents will have hash values that are close by. You can then compare potentially similar documents byte for byte because the number of documents you have to compare to is a much smaller set.

Elaborating a bit on Snowman’s answer, I think I would go for a hierarchy of hash values over (exponentially) increasing subsets of the file, computed on-demand whenever collisions occur, and memorized in a suitable data structure (hash table, but even a simple prefix tree would do) for quick future access. This should ensure quick failure in case of ‘almost identity’, and retain the worst-case complexity (up to a log factor) and achieve good average-case complexity.

It would go as follows in pseudo-Python, taking as input a file f, a set of files D and a dictionary H (again, one could do better here, but it should not matter too much) acting as a cache for previously computed hash values:

collisions = [fc for fc in D if size(fc)==size(f)]
size_hash = 4*1024
while (len(collisions) > 0) and (size_hash<=size(f)):
  H[(f,size_hash)] = md5(f,size_hash)
  for fc in collisions:
    if (fc,size_hash) not in H:
      H[(fc,size_hash)] = md5(fc,size_hash)
  collisions = [fc for fc in collisions if H[(fc,size_hash)]==H[(f,size_hash)]]
  size_hash *= 2
for fc in collisions:
  # Painstakingly read and compare content to that of f...

Worst-case complexities: In the worst case, all of the files have equal length n, and have different yet MD5 identical (unlucky!) contents, so one ends up computing MD5 hashes for chunks of size 4k, 8k, 16k… n in each of the files, only to read them in full afterward.

In term of time, the first 4k of each file are read to compute the first hash, then the first 8k for the second, 16k for the third … then the full size n. Computing an MD5 can be done in linear time, so the total time-consumption is (up to a constant) 4k+8k+16k+…+n < 2n operations, i.e. it remains in the order of magnitude of the final (unavoidable) comparison of the files.

In term of memory, log(n) MD5 hash values (one for 4k, one for 8k…), each of constant size will be stored, so the overhead should be reasonable.

Average-case complexities: I won’t detail the analysis (maths are not permitted by the markdown system here anyway 🙂 ), but even assuming a large number of files having equal size, the expected number of computed hash values should be constant on average, so this algorithm will neither read significant chunks of the files, nor clotter the memory.

Without some knowledge of the nature of the files you cannot be sure without hashing the entire file. Checking the file size and hashing only a portion of the file contents is sufficient only if you can guarantee that the contents will be unique in the hashed portions.

Filed under: softwareengineering - @ 20:43

Thẻ: comparison, design

Thiết kế website giá rẻ

Danh mục

Algorithm to test file equivalence