Hacker News Reader

Comment by emmelaich | Hacker News Reader

I you want ids without collisions you should use a monotonically increasing number instead (or as well).

I would concatenate utc time in ms to the random number.

You can't use monotonically increasing numbers from multiple threads (or servers) without either synchronizing (which is terrible for scalability) or using separate prefixes for different threads or servers (in which case you have problems related to sizing and allocating the prefixes). Right?

The UTC time + random number idea is interesting, but I'm not sure it's any better than totally random. Say you want a 64-bit unique id. It would take about 42 bits to store a millisecond Unix timestamp, leaving 22 bits for randomness. If you consider the probability that a given id will collide with a previously-generated one: with this scheme, you only need to consider ids generated in the same millisecond, but you only have 22 bits of randomness that can be used to avoid a collision. If you use 64 random bits, you can theoretically collide with ids generated across all of time, but the odds of collision are many orders of magnitude lower. By constraining the first 42 bits to store a millisecond timestamp, every millisecond that goes by removes 2^22 values from the possible id space (regardless of whether they're used). (Besides that, this scheme removes from the space of possible ids all of the millisecond values from before the system was created, which seems like about 2/3 of them, assuming about a 68-year span of values for Unix times, which started 45 years ago.)

That's kind of handwavy, so let's do the math. With 22 bits of randomness, the odds of any randomly selected pair of ids generated in the same millisecond colliding is 1/4194304. Assuming independently generated ids, the expected number of collisions after 4194304 milliseconds is 1. So if you have just two threads generating ids once per millisecond, you'd expect a collision in just 70 minutes. That's not great.

It's late, though. Maybe my math is wrong?

You can't use a PRNG from multiple threads without synchronizing either. And interlocked increment is probably a thousand times cheaper than mutexing a PRNG...

Sure you can. A different seed in each thread and you're done.

But you still have to generate a seed for each thread. Then you could just generate a random starting point for each thread and run with incrementing counters instead of hitting the PRNG for each ID.

True. But I don't think it's hard to come up with a seed which is guaranteed to be unique. If you use counters you have a ton of management overhead. You now need to keep track of where the counter for each thread should start and what happens when a thread crashes. Also, what happens when you want to add a new thread? Now you have to change the increment for your counters.

Why do you have to care about all that? Just pick a random number and start incrementing++ from there. I don't see how this would yield any more collisions than a PRNG? Just because you move across the ID space sequentially instead of in an obfuscated pattern doesn't really mean there's a higher chance of picking the same ID twice?

(My argument here, really, is that using a PRNG at all sounds pretty crazy for ID generation, if you don't take steps to prevent or detect collisions)

You have to care about that if you don't want any synchronization. How do you generate IDs across multiple servers otherwise?

Yep, length could be a problem, I was assuming a longer id. They're using 22 char identifiers. A base64'd unix epoch time in ms is another 36 chars. But I'm sure you could do better than that.

The chances of a collision must be vanishingly smaller within even a second (let alone a millisecond) even if the random number generation is defective.

I didn't check your maths.

> base64'd unix epoch time in ms is 36 chars

Correction - 21 chars.

With a second resolution its 17 chars.

Counting from now, the addition would only be five chars.

    echo -n 0 | base64 | wc -c
    5

or just use UUIDs which are designed for this exact use case

What kind of UUID? Standard UUIDs of versions 1, 2, and 3 are not really unique enough[1]. Version 4 is basically a random number, so it doesn't help to say "just use that".

[1] https://en.wikipedia.org/wiki/Universally_unique_identifier

well, I use uuidgen[1]. If I have to generate uuids for multiple servers, then I create a microservice to handle uuid generation, and get it to generate a few held in a buffer so the rest of the system doesn't have to wait for one.

[1] http://man7.org/linux/man-pages/man1/uuidgen.1.html

Exactly, my biggest takeaway is "don't write your own unique ID algorithm." At best it does the same as existing methods, at worst you screw it up and end up here.

Reply on news.ycombinator.com