6

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.

  • 4
    OK, so what is your question? Are you just asking for our blessing? OK, you have our blessing. Checking the MD5 of the first and last 4K of the file seems like a reasonable approach to me. Congratulations for exercising some creativity, and not just assuming that there's a "standard approach" to every possible programming problem. (that would be stupefyingly boring, wouldn't it?) – Robert Harvey Dec 17 '14 at 21:46
  • 1
    What kind of files are these? Could you get a mismatch in a header yet still have what you'd consider to be the same data? Video, audio, & image files might fall into this category. – Dan Pichelman Dec 17 '14 at 21:51
  • @RobertHarvey Not looking for a blessing, just to see if I'm missing something obvious. I also stand by my question, is there a best practice when attempting to check if a file has been seen by a program previously. – AlexLordThorsen Dec 17 '14 at 21:55
  • @DanPichelman These are mainly time stamped logfiles. /var/log/messages type files. – AlexLordThorsen Dec 17 '14 at 21:55
  • 1
    @Doval Fair enough. My problem is that I'm attempting to deduplicate a decently sized set of data ( 2Pb ) that contains a large amount of time stamped files 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. – AlexLordThorsen Dec 17 '14 at 22:13
6

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

  1. If two files have different sizes, they must be different files.
  2. 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.

  • 4
    I would not use multiple hashes. One collision resistant hash (e.g. SHA2) should be enough. The probability of accidental collisions is negligible with good hashes of at least 256 bits and beyond ridiculous at 512 bits (e.g. SHA-512). Against deliberate collisions using multiple hashes is only about as strong as the strongest hash, not stronger. In general it's typically better to spend the CPU budget on using a stronger hash instead of multiple weak hashes. Personally I wouldn't even bother with byte-by-byte comparison of files if the have the same SHA-2 hash. – CodesInChaos Dec 18 '14 at 9:45
  • Agree. Two 256 bit hashes are not nearly as good as one 512 bit hash. The underlying reason is that good hashes have a high mix factor, and you simply cannot mix bits between two independent hashes at all. – MSalters Dec 18 '14 at 17:29
  • Good point, the problem is similar to hash chains. While that question is focused on security, the uniqueness property also applies here. I updated my answer to address this concern. – user22815 Dec 18 '14 at 18:18
3

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

  1. 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.
  2. 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.

  • If you are doing life-critical code, you shouldn't be handwaving but doing the actual math. (Your example is more than just mission-critical, mission-critical would be e.g. loss of solar panels on the ISS) And at that point, the 1E-38 chance of an MD5 collision may very well be in acceptable range. – MSalters Dec 18 '14 at 17:32
1

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.

1

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.