3 ms·
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 numbe
by emmelaich 11y ago
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.
- marcus_holmes 11y agoor just use UUIDs which are designed for this exact use case
- vcarl 11y agoExactly, 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.
- dap 11y agoWhat 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 https://en.wikipedia.org/wiki/Universally_unique_identifier
- marcus_holmes 11y agowell, 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 http://man7.org/linux/man-pages/man1/uuidgen.1.html
- deleted 11y ago[deleted]
- dap 11y agoYou 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?
- emmelaich 11y agoYep, 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.
- emmelaich 11y ago> 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
- deleted 11y ago[deleted]
- 0x0 11y agoYou can't use a PRNG from multiple threads without synchronizing either. And interlocked increment is probably a thousand times cheaper than mutexing a PRNG...
- michaelmior 11y agoSure you can. A different seed in each thread and you're done.
- 0x0 11y agoBut 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.
- michaelmior 11y agoTrue. 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.