5 ms·

Surprising we're using 128 bits - some back of the napkin math tells me that may not be enough to avoid collisions...

by ComplexSystems 2y ago

AaronFriel 2y ago
Care to share your math? My understanding of the birthday paradox is that it is astoundingly unlikely.
- ComplexSystems 2y ago
  It's just about on the cusp. We would need to generate 1.1774sqrt(2^128) UUID's before getting a collision with 51% probability. That's about 2.17 10^19 total UUIDs. The real question is how many UUIDs are generated per second around the world. This RFC suggests using them for automated processes, transactions, etc and generally seems to view them as an inexhaustible resource. If humanity collectively generates 1 trillion per second we can expect to see a 51% chance of collision in 8 months; if it's 100 billion it'd be 10 years, and if it's only 10 billion it'd be 100 years. I would expect even just one single computer with a modest GPU could get in the ballpark of these numbers if it wanted to just spawn UUIDs all day, let alone a huge server farm using them as part of some automated process.
  - t0mas88 2y ago
    But not all UUIDS are going into the same "pool". There is no problem if your GPU generates a collision with one of my database identifies, since I only care about my identifiers being unique in my system. For comparison, before UUIDs most databases were using auto increment integers. That means nearly everyone had id 1, 2 etc in use. Still not a problem.
  - AaronFriel 2y ago
    True, as universally unique identifiers, 128 (less a few) bits is not enough. You're talking about humanity generating 505 exabytes per year of just UUIDs. That won't happen any time soon.
    - ComplexSystems 2y ago
      Of course it will: "The UUID generation algorithm described here supports very high allocation rates of 10 million per second per machine or more, if necessary, so that they could even be used as transaction IDs." This is the use case they had in mind when building this algorithm, and it would only take about 10k machines worldwide to reach the above levels.
      - AaronFriel 2y ago
        "Only" 10k machines producing a combined 100 billion transactions per second is pretty hard to imagine, least of all that would all be producing transactions that are part of the same namespace. Virtually all UUIDs are meaningless outside of a particular system in which they were created. There is a solution that doesn't require extending UUIDs (which has a storage cost everyone pays), which is to use a URI/URN instead of a UUID to provide a namespace. In practice this already occurs, except the namespace (scheme, path) containing the UUID is implicit, as it hasn't been named.
free_bip 2y ago
The time field ensures that collisions cannot occur until at minimum the time field rolls over.
- debatem1 2y ago
  Having been badly bitten by the timestamp equivalent of eating gum you scraped off the bottom of a desk just let me add that there is an implicit "if your time source is good/non-adversarial" assumption here. Friends don't let friends use malicious clocks!
deleted 2y ago
[deleted]
WorldMaker 2y ago
For hash functions, maybe not anymore, given the birthday paradox/pigeon-hole principle and other math problems in bucketing inputs versus the attack patterns for breaking hash functions and causing intentional collisions. For mostly purely random entropy in uses like UUID (and IPv6) the classic answer is that it is still more overall space than "atoms in the visible universe".
Spivak 2y ago
Depends on your problem domain. You can be Twitter/Discord sized and get away with 64 bits. When you start dedicating parts of your UUID to a timestamp the possibility of collisions does go way up since now a significant chunk of the UUID will be the same for everyone. But when you deploy this variant you aren't trying to make globally unique ids anymore, you're trying to make application unique ids. You are sill very unlikely to not also have a globally unique id because 128 bits gives a lot of room to play around.

Surprising we're using 128 bits - some back of the napkin math tells me that may not be enough to avoid collisions...

AaronFriel 2y ago

Care to share your math? My understanding of the birthday paradox is that it is astoundingly unlikely.

ComplexSystems 2y ago
It's just about on the cusp. We would need to generate 1.1774sqrt(2^128) UUID's before getting a collision with 51% probability. That's about 2.17 10^19 total UUIDs. The real question is how many UUIDs are generated per second around the world. This RFC suggests using them for automated processes, transactions, etc and generally seems to view them as an inexhaustible resource. If humanity collectively generates 1 trillion per second we can expect to see a 51% chance of collision in 8 months; if it's 100 billion it'd be 10 years, and if it's only 10 billion it'd be 100 years. I would expect even just one single computer with a modest GPU could get in the ballpark of these numbers if it wanted to just spawn UUIDs all day, let alone a huge server farm using them as part of some automated process.
- t0mas88 2y ago
  But not all UUIDS are going into the same "pool". There is no problem if your GPU generates a collision with one of my database identifies, since I only care about my identifiers being unique in my system. For comparison, before UUIDs most databases were using auto increment integers. That means nearly everyone had id 1, 2 etc in use. Still not a problem.
- AaronFriel 2y ago
  True, as universally unique identifiers, 128 (less a few) bits is not enough. You're talking about humanity generating 505 exabytes per year of just UUIDs. That won't happen any time soon.
  - ComplexSystems 2y ago
    Of course it will: "The UUID generation algorithm described here supports very high allocation rates of 10 million per second per machine or more, if necessary, so that they could even be used as transaction IDs." This is the use case they had in mind when building this algorithm, and it would only take about 10k machines worldwide to reach the above levels.
    - AaronFriel 2y ago
      "Only" 10k machines producing a combined 100 billion transactions per second is pretty hard to imagine, least of all that would all be producing transactions that are part of the same namespace. Virtually all UUIDs are meaningless outside of a particular system in which they were created. There is a solution that doesn't require extending UUIDs (which has a storage cost everyone pays), which is to use a URI/URN instead of a UUID to provide a namespace. In practice this already occurs, except the namespace (scheme, path) containing the UUID is implicit, as it hasn't been named.

free_bip 2y ago

The time field ensures that collisions cannot occur until at minimum the time field rolls over.

debatem1 2y ago
Having been badly bitten by the timestamp equivalent of eating gum you scraped off the bottom of a desk just let me add that there is an implicit "if your time source is good/non-adversarial" assumption here. Friends don't let friends use malicious clocks!

deleted 2y ago

[deleted]

WorldMaker 2y ago

For hash functions, maybe not anymore, given the birthday paradox/pigeon-hole principle and other math problems in bucketing inputs versus the attack patterns for breaking hash functions and causing intentional collisions. For mostly purely random entropy in uses like UUID (and IPv6) the classic answer is that it is still more overall space than "atoms in the visible universe".

Spivak 2y ago

Depends on your problem domain. You can be Twitter/Discord sized and get away with 64 bits. When you start dedicating parts of your UUID to a timestamp the possibility of collisions does go way up since now a significant chunk of the UUID will be the same for everyone. But when you deploy this variant you aren't trying to make globally unique ids anymore, you're trying to make application unique ids. You are sill very unlikely to not also have a globally unique id because 128 bits gives a lot of room to play around.