> In a large enough population of data, collisions happen.
So you pick a hash function whose space is so large that the risk of collision is less than the risk of any other possible reason for accidental mis-identification (like all the file's bytes spontaneously switching to the collided file's bytes). You can have databases with trillions of objects with less than a one in a million chance of collision in a 256-bit space.
Realistically, there are a lot of things that are better to worry about than a one-in-a-million chance of losing a file. And if you really need so many objects that that's not enough, just increase the size of the hash space.
Yes; if you increase the hash space sufficiently, these problems go away. I don't think wide hashing has really become a standard industry practice though, because services want to pick the option that is least burdensome to end users' CPUs. Another issue is that once they have a big de-duplication database established based on a particular hash, switching is expensive. I suspect a lot of shops are using md5 still.
Perhaps. That said, even a SHA-512 sum on my computer seems to take a little less than a CPU-second per hundred megabytes. Odds are you're not going to be uploading that fast, so you should be able to do that work "online" and not have a noticeable impact on either upload throughput or user-visible impact. This is doubly true on a multi-core device, since the sha sum I quoted was single-threaded. I would think the more important thing to minimize is user-impacting disk latency from the backup scan.
Comments
> In a large enough population of data, collisions happen.
So you pick a hash function whose space is so large that the risk of collision is less than the risk of any other possible reason for accidental mis-identification (like all the file's bytes spontaneously switching to the collided file's bytes). You can have databases with trillions of objects with less than a one in a million chance of collision in a 256-bit space.
Realistically, there are a lot of things that are better to worry about than a one-in-a-million chance of losing a file. And if you really need so many objects that that's not enough, just increase the size of the hash space.
Yes; if you increase the hash space sufficiently, these problems go away. I don't think wide hashing has really become a standard industry practice though, because services want to pick the option that is least burdensome to end users' CPUs. Another issue is that once they have a big de-duplication database established based on a particular hash, switching is expensive. I suspect a lot of shops are using md5 still.
Perhaps. That said, even a SHA-512 sum on my computer seems to take a little less than a CPU-second per hundred megabytes. Odds are you're not going to be uploading that fast, so you should be able to do that work "online" and not have a noticeable impact on either upload throughput or user-visible impact. This is doubly true on a multi-core device, since the sha sum I quoted was single-threaded. I would think the more important thing to minimize is user-impacting disk latency from the backup scan.