4 ms·

What algorithm does the application use to figure out if two files are identical? There's a lot of interesting algorithms out there. Hashes, bit by bit comparis

What algorithm does the application use to figure out if two files are identical? There's a lot of interesting algorithms out there. Hashes, bit by bit comparison etc. But these techniques have their own disadvantages. What is the best way to do this for a large amount of files?

diegs 2y ago
This reminds me of https://en.wikipedia.org/wiki/Venti_(software) https://en.wikipedia.org/wiki/Venti_(software) which was a content-addressible filesystem which used hashes for de-duplication. Since the hashes were computed at write time, the performance penalty is amortized.
w4yai 2y ago
I'd hash the first 1024 bytes of all files, and starts from there is any collision. That way you don't need to hash the whole (large) files, but only those with same hashes.
- kstrauser 2y ago
  At that point, why hash them instead of just using the first 1024 bytes as-is?
  - sedatk 2y ago
    Probably because you need to keep a lot of those in memory.
    - kstrauser 2y ago
      I suspect that a computer with so many files that this would be useful probably has a lot of RAM in it, at least in the common case.
      - sedatk 2y ago
        But you need to constantly process them too, not just store them.
  - borland 2y ago
    In order to check if a file is a duplicate of another, you need to check it against _every other possible file_. You need some kind of "lookup key". If we took the first 1024 bytes of each file as the lookup key, then our key size would be 1024 bytes. If you have 1 million files on your disk, then that's 128MB of ram just to store all the keys. That's not a big deal these days, but it's also annoying if you have a bunch of files that all start with the same 1024 bytes -- e.g. perhaps all the photoshop documents start with the same header. You'd need a 2-stage comparison, where you first match the key (1024 bytes) and then do a full comparison to see if it really matches. Far more efficient - and less work - If you just use a SHA256 of the file's contents. That gets you a much smaller 32 byte key, and you don't need to bother with 2-stage comparisons.
    - kstrauser 2y ago
      I understand the concept. My main point is that it's probably not a huge advantage to store hashes of the first 1KB, which requires CPU to calculate, over just the raw bytes, which requires storage. There's a tradeoff either way. I don't think it would be far more efficient to do hash the entire contents though. If you have a million files storing a terabyte of data, the 2 stage comparison would read at most 1GB (1 million * 1KB) of data, and less for smaller files. If you do a comparison of the whole hashed contents, you have to read the entire 1TB. There are a hundred confounding variables, for sure. I don't think you could confidently estimate which would be more efficient without a lot of experimenting.
      - philsnow 2y ago
        If you're going to keep partial hashes in memory, may as well align it on whatever boundary is the minimal block/sector size that your drives give back to you. Hashing (say) 8kB takes less time than it takes to fetch it from SSD (much less disk), so if you only used the first 1kB, you'd (eventually) need to re-fetch the same block to calculate the hash for the rest of the bytes in that block. ... okay, so as long as you always feed chunks of data into your hash in the same deterministic order, it doesn't matter for the sake of correctness what that order is or even if you process some bytes multiple times. You could hash the first 1kB, then the second-through-last disk blocks, then the entire first disk block again (double-hashing the first 1kB) and it would still tell you whether two files are identical. If you're reading from an SSD and seek times don't matter, it's in fact probable that on average a lot of files are going to differ near the start and end (file formats with a header and/or footer) more than in the middle, so maybe a good strategy is to use the first 32k and the last 32k, and then if they're still identical, continue with the middle blocks. In memory, per-file, you can keep something like - the length - h(block[0:4]) - h(block[0:4] | block[-5:]) - h(block[0:4] | block[-5:] | block[4:32]) - h(block[0:4] | block[-5:] | block[4:128]) - ... - h(block[0:4] | block[-5:] | block[4:]) etc, and only calculate the latter partial hashes when there is a collision between earlier ones. If you have 10M files and none of them have the same length, you don't need to hash anything. If you have 10M files and 9M of them are copies of each other except for a metadata tweak that resides in the last handful of bytes, you don't need to read the entirety of all 10M files, just a few blocks from each. A further refinement would be to have per-file-format hashing strategies... but then hashes wouldn't be comparable between different formats, so if you had 1M pngs, 1M zips, and 1M png-but-also-zip quine files, it gets weird. Probably not worth it to go down this road.
  - smusamashah 2y ago
    And why first 1024, can pick from predefined points.
    - f1shy 2y ago
      Depending on the medium, the penalty of reading single bytes in sparse locations could be comparable with reading the whole file. Maybe not a big win.
- amelius 2y ago
  I suspect that bytes near the end are more likely to be different (even if there may be some padding). For example, imagine you have several versions of the same document. Also, use the length of the file for a fast check.
borland 2y ago
I don't know exactly what Siracusa is doing here, but I can take an educated guess: For each candidate file, you need some "key" that you can use to check if another candidate file is the same. There can be millions of files so the key needs to be small and quick to generate, but at the same time we don't want any false positives. The obvious answer today is a SHA256 hash of the file's contents; It's very fast, not too large (32 bytes) and the odds of a false positive/collision are low enough that the world will end before you ever encounter one. SHA256 is the de-facto standard for this kind of thing and I'd be very surprised if he'd done anything else.
- deleted 2y ago
  [deleted]
- MBCook 2y ago
  You can start with the size, which is probably really unique. That would likely cut down the search space fast. At that point maybe it’s better to just compare byte by byte? You’ll have to read the whole file to generate the hash and if you just compare the bytes there is no chance of hash collision no matter how small. Plus if you find a difference in bytes 1290 you can just stop there instead of reading the whole thing to finish the hash. I don’t think John has said exactly how on ATP (his podcast with Marco and Casey), but knowing him as a longtime listener/reader he’s being very careful. And I think he’s said that on the podcast too.
  - unclebucknasty 2y ago
    >which is probably really unique Wonder what the distribution is here, on average? I know certain file types tend to cluster in specific ranges. >maybe it’s better to just compare byte by byte? You’ll have to read the whole file to generate the hash Definitely, for comparing any two files. But, if you're searching for duplicates across the entire disk, then you're theoretically checking each file multiple times, and each file is checked against multiple times. So, hashing them on first pass could conceivably be more efficient. >if you just compare the bytes there is no chance of hash collision You could then compare hashes and, only in the exceedingly rare case of a collision, do a byte-by-byte comparison to rule out false positives. But, if your first optimization (the file size comparison) really does dramatically reduce the search space, then you'd also dramatically cut down on the number of re-comparisons, meaning you may be better off not hashing after all. You could probably run the file size check, then based on how many comparisons you'll have to do for each matched set, decide whether hashing or byte-by-byte is optimal.
williamsmj 2y ago
Deleted comment based on a misunderstanding.
- Sohcahtoa82 2y ago
  > This tool simply identifies files that point at literally the same data on disk because they were duplicated in a copy-on-write setting. You misunderstood the article, as it's basically doing the opposite of what you said. This tool finds duplicate data that is specifically not duplicated via copy-on-write, and then turns it into a copy-on-write copy.
  - williamsmj 2y ago
    Fair. Deleted.

diegs 2y ago

This reminds me of https://en.wikipedia.org/wiki/Venti_(software) https://en.wikipedia.org/wiki/Venti_(software) which was a content-addressible filesystem which used hashes for de-duplication. Since the hashes were computed at write time, the performance penalty is amortized.

w4yai 2y ago

I'd hash the first 1024 bytes of all files, and starts from there is any collision. That way you don't need to hash the whole (large) files, but only those with same hashes.

kstrauser 2y ago
At that point, why hash them instead of just using the first 1024 bytes as-is?
- sedatk 2y ago
  Probably because you need to keep a lot of those in memory.
  - kstrauser 2y ago
    I suspect that a computer with so many files that this would be useful probably has a lot of RAM in it, at least in the common case.
    - sedatk 2y ago
      But you need to constantly process them too, not just store them.
- borland 2y ago
  In order to check if a file is a duplicate of another, you need to check it against _every other possible file_. You need some kind of "lookup key". If we took the first 1024 bytes of each file as the lookup key, then our key size would be 1024 bytes. If you have 1 million files on your disk, then that's 128MB of ram just to store all the keys. That's not a big deal these days, but it's also annoying if you have a bunch of files that all start with the same 1024 bytes -- e.g. perhaps all the photoshop documents start with the same header. You'd need a 2-stage comparison, where you first match the key (1024 bytes) and then do a full comparison to see if it really matches. Far more efficient - and less work - If you just use a SHA256 of the file's contents. That gets you a much smaller 32 byte key, and you don't need to bother with 2-stage comparisons.
  - kstrauser 2y ago
    I understand the concept. My main point is that it's probably not a huge advantage to store hashes of the first 1KB, which requires CPU to calculate, over just the raw bytes, which requires storage. There's a tradeoff either way. I don't think it would be far more efficient to do hash the entire contents though. If you have a million files storing a terabyte of data, the 2 stage comparison would read at most 1GB (1 million * 1KB) of data, and less for smaller files. If you do a comparison of the whole hashed contents, you have to read the entire 1TB. There are a hundred confounding variables, for sure. I don't think you could confidently estimate which would be more efficient without a lot of experimenting.
    - philsnow 2y ago
      If you're going to keep partial hashes in memory, may as well align it on whatever boundary is the minimal block/sector size that your drives give back to you. Hashing (say) 8kB takes less time than it takes to fetch it from SSD (much less disk), so if you only used the first 1kB, you'd (eventually) need to re-fetch the same block to calculate the hash for the rest of the bytes in that block. ... okay, so as long as you always feed chunks of data into your hash in the same deterministic order, it doesn't matter for the sake of correctness what that order is or even if you process some bytes multiple times. You could hash the first 1kB, then the second-through-last disk blocks, then the entire first disk block again (double-hashing the first 1kB) and it would still tell you whether two files are identical. If you're reading from an SSD and seek times don't matter, it's in fact probable that on average a lot of files are going to differ near the start and end (file formats with a header and/or footer) more than in the middle, so maybe a good strategy is to use the first 32k and the last 32k, and then if they're still identical, continue with the middle blocks. In memory, per-file, you can keep something like - the length - h(block[0:4]) - h(block[0:4] | block[-5:]) - h(block[0:4] | block[-5:] | block[4:32]) - h(block[0:4] | block[-5:] | block[4:128]) - ... - h(block[0:4] | block[-5:] | block[4:]) etc, and only calculate the latter partial hashes when there is a collision between earlier ones. If you have 10M files and none of them have the same length, you don't need to hash anything. If you have 10M files and 9M of them are copies of each other except for a metadata tweak that resides in the last handful of bytes, you don't need to read the entirety of all 10M files, just a few blocks from each. A further refinement would be to have per-file-format hashing strategies... but then hashes wouldn't be comparable between different formats, so if you had 1M pngs, 1M zips, and 1M png-but-also-zip quine files, it gets weird. Probably not worth it to go down this road.
- smusamashah 2y ago
  And why first 1024, can pick from predefined points.
  - f1shy 2y ago
    Depending on the medium, the penalty of reading single bytes in sparse locations could be comparable with reading the whole file. Maybe not a big win.
amelius 2y ago
I suspect that bytes near the end are more likely to be different (even if there may be some padding). For example, imagine you have several versions of the same document. Also, use the length of the file for a fast check.

borland 2y ago

I don't know exactly what Siracusa is doing here, but I can take an educated guess: For each candidate file, you need some "key" that you can use to check if another candidate file is the same. There can be millions of files so the key needs to be small and quick to generate, but at the same time we don't want any false positives. The obvious answer today is a SHA256 hash of the file's contents; It's very fast, not too large (32 bytes) and the odds of a false positive/collision are low enough that the world will end before you ever encounter one. SHA256 is the de-facto standard for this kind of thing and I'd be very surprised if he'd done anything else.

deleted 2y ago
[deleted]
MBCook 2y ago
You can start with the size, which is probably really unique. That would likely cut down the search space fast. At that point maybe it’s better to just compare byte by byte? You’ll have to read the whole file to generate the hash and if you just compare the bytes there is no chance of hash collision no matter how small. Plus if you find a difference in bytes 1290 you can just stop there instead of reading the whole thing to finish the hash. I don’t think John has said exactly how on ATP (his podcast with Marco and Casey), but knowing him as a longtime listener/reader he’s being very careful. And I think he’s said that on the podcast too.
- unclebucknasty 2y ago
  >which is probably really unique Wonder what the distribution is here, on average? I know certain file types tend to cluster in specific ranges. >maybe it’s better to just compare byte by byte? You’ll have to read the whole file to generate the hash Definitely, for comparing any two files. But, if you're searching for duplicates across the entire disk, then you're theoretically checking each file multiple times, and each file is checked against multiple times. So, hashing them on first pass could conceivably be more efficient. >if you just compare the bytes there is no chance of hash collision You could then compare hashes and, only in the exceedingly rare case of a collision, do a byte-by-byte comparison to rule out false positives. But, if your first optimization (the file size comparison) really does dramatically reduce the search space, then you'd also dramatically cut down on the number of re-comparisons, meaning you may be better off not hashing after all. You could probably run the file size check, then based on how many comparisons you'll have to do for each matched set, decide whether hashing or byte-by-byte is optimal.

williamsmj 2y ago

Deleted comment based on a misunderstanding.

Sohcahtoa82 2y ago
> This tool simply identifies files that point at literally the same data on disk because they were duplicated in a copy-on-write setting. You misunderstood the article, as it's basically doing the opposite of what you said. This tool finds duplicate data that is specifically not duplicated via copy-on-write, and then turns it into a copy-on-write copy.
- williamsmj 2y ago
  Fair. Deleted.