Magic hash maths: Dedupe does not have to mean high compute. Wait, what?

Re: I won't pretend to understand buckets vs. blooms...

The wrinkle is a useful dedupe requires you do raw block compares on all hash matches, so it's more important to minimise collisions because the cost of checking them is so high. In particular you need to winnow out multiple collisions fast, a hierarchy of cheap hashes and fail early would be my instinctive choice.

Re: unique mathematical hash

> I must be missing something here. Surely a hash can only be unique if it's the same size as the block of data?

You're quite right that there are an infinite number of input documents, and only a finite number of hash values. What you are missing is probability.

With a well-designed hash function, the distribution of hashes over input documents is uniform and (apparently) random. The probability of finding two documents with the same hash is vanishingly small.

With a 256-bit hash, you would need to hash around 2^128 different documents before there is a reasonable chance that any two of your documents will have the same hash. (Google for "birthday paradox")

Even if you are hashing one trillion documents per second, it would be about 10^19 years before you had hashed 2^128 documents. Plus you need somewhere to store those 2^128 hashes to compare them.

So if you find two blocks in your storage array with the same hash, the probability is overwhelming that they *are* the same block. And if you are paranoid, you can always read them both and compare them before discarding the duplicate.

(With a broken hash function like MD5 or SHA1, it's possible for an evil user to intentionally submit two different blocks to your storage array which have the same hash)

Re: unique mathematical hash

Yes hashes are clearly not unique (and hence the article is just plain wrong about that).

Any dedupe system that assumes they are unique and doesn't verify the data is the same after getting a hash match is insane and should not be used. It doesn't matter how low the probability is, I do not want to risk my data getting destroyed because it just happens to have the same hash as some other data.

And yes there are programmers out there dumb enough to assume the hashes are effectively unique because the probability is so insanely low of them having a collision and then treat them as if they were actually unique. Some day their customer is going to pay for that mistake and they might not know it for a long time after it happens.

Re: Hashes and duplicates

"Because of this a dedupe tool has to compare the data blocks when there is a hash match to avoid losing or corrupting data. "

Sadly most methods do not bother doing a actual block comparison.

This is because the math shows the odds of a block collision due to them having the same hash is less likely than the disk being corrupted by multiple simultaneous bit flips that bypass parity/checksum checks.

There is also the fact that dedupe systems are limited in the size of the data set they can dedupe, due to the ever-increasing hash lookup table.

This less computational expensive method might be one that does less exact/expensive hashing and full block comparisons when it gets a possible match.

Re: Dunno what he’s on about...

It's not the calculating the hash that's the hard work, it's scanning the hash table looking for matches for every incoming write. Say you have 1TB of data and 50% of the 4K blocks are unique. If you are using a 256bit hash (SHA-256) that's 8GB of space for the hash table and you have to search for a match for every incoming block. Hence the need for clever ways to minimize the above. Some implementations are much more efficient than others.

That's an overly simplistic example but points out where the issue lies