5 ms·

You can't use monotonically increasing numbers from multiple threads (or servers) without either synchronizing (which is terrible for scalability) or using sepa

by dap 11y ago

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?

emmelaich 11y ago
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.
- 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 ago
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...
- michaelmior 11y ago
  Sure you can. A different seed in each thread and you're done.
  - 0x0 11y ago
    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.
    - michaelmior 11y ago
      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.
      - 0x0 11y ago
        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)
        michaelmior 11y ago
        You have to care about that if you don't want any synchronization. How do you generate IDs across multiple servers otherwise?

by dap 11y ago

emmelaich 11y ago

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.

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 ago

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...

michaelmior 11y ago
Sure you can. A different seed in each thread and you're done.
- 0x0 11y ago
  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.
  - michaelmior 11y ago
    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.
    - 0x0 11y ago
      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)
      - michaelmior 11y ago
        You have to care about that if you don't want any synchronization. How do you generate IDs across multiple servers otherwise?