Hacker News Reader

Comment by Tharkun | Hacker News Reader

If you don't need consecutive IDs, use a UUID or a Random UUID if you can get away with it.

If you do need consecutive IDs, use atomic operations on a counter (compare-and-swap type increments, AtomicInt in Java, etc). Need to preserve them after a restart? Reserve a block of size N, when you get close to N, stop generating until you've persisted the reservation for the next N identifiers. Atomic increments will ensure you never hand out the same number twice, and reserving a block before you persist will ensure that you'll be save even after a power outage or whatever.

Why bother with incredibly long random numbers? It can go wrong in so many ways. The probability of duplicates being low does not mean that you won't get duplicates.

View on HN

This is a common misconception. The actual real world effect is that you'll never ever run into a collision, because it is much more probably than any other catastrophic event will happen in your computer, or that bits will flip at random in your processors and so forth. Note that:

1) Economic transactions, signatures, files, are often verified using "incredibly long random numbers".

2) Rsync transfers files hashing blocks with hash functions and avoid transferring blocks with HMACs that match.

You'll never see a collision if not on-purpose in the case the hash function has a vulnerability that allows the attacker to craft a plaintext P2 so that HASH(P2) == HASH(P1), or at least allows an attacker to select two P1 and P2 so that HASH(P1) == HASH(P2).

If you don't trust crypto hash functions to be collision resistant in the explained use case, where even the above attacks are irrelevant since we are just using the distribution properties, you can't trust most modern computing at all.

If you generate a sufficiently long random number then the probability of duplicates easily becomes lower than the probability of duplicates in a counter scheme due to a bug or hardware fault. And "sufficiently" long doesn't require a novel. 128 bits is sufficient for just about everything, and 256 bits is enough for everything.

Why bother with a complicated atomic ID operation (and that's going to be fun to scale, too) when a relatively short string of random bits will do the job?

All a UUID is really is an incredibly long random number (at least v4). I'm not sure exactly what you're advocating here.

Agree. And if you only need unique (or increasing) IDs and not consecutive then it's easier. Long random/GUID ids are only needed when the id should not he guessable or predictable. Which is sometimes important, sometimes not.

The probability of duplicates being low does not mean that you won't get duplicates.

This is true for cryptographic hash functions, yet in practice no one has a problem with using them for identifying files etc., because their output space is so large as to make the chance of a collision sufficiently low. I'm almost willing to bet that even for ones which are cryptographically insecure like MD5, and for which colliding pairs can be easily deliberately created, there hasn't been a truly accidental collision.

(Fun experiment to try: hash all the files you own, and then compare byte-by-byte the ones with the same hash. Try a few different cryptographic hash functions. If you do find accidental collisions, you've just experienced an event far more improbable than winning the lottery; and if it's SHA1, SHA256, or bigger, it's worth publicising this event.)

I have seen an md5 collision happen at work. Having low probability doesn't mean it won't happen, you just don't know when - people win the lottery around the world daily.

Did you see a MD5 collision that happened randomly, or was someone intentionally trying to create one?

Intentionally creating a collision with MD5 is fairly easy; having one happen at random would require creating something like 10 ^ 14 billion hashes in order to have the same chance of a collision as winning the lottery. People win the lottery, yes, but they don't happen across MD5 collisions by accident.

Random! I don't remember the details, but we spent a good half hour looking up probabilities and marvelling at it. I think at the time nobody realized just how unlikely it was, should have saved the inputs :(

That sounds like an interesting story. Consider yourself very lucky! Were the data being hashed related in some way, or user input (whereby someone could relatively easily feed in a collision pair)?

If I came across an MD5 collision by accident, I'd certainly try to save the input pair, because such events are exceedingly rare. Owning a pair of entirely naturally occurring data with colliding MD5s is itself article-worthy, I think.

Reply on news.ycombinator.com