5 ms·

Except that UUIDs by themselves don't do this at all: > They provide a reliable way to ensure that each item, user, or piece of data has a unique identity. It

Except that UUIDs by themselves don't do this at all: > They provide a reliable way to ensure that each item, user, or piece of data has a unique identity. It is the registration of a UUID in a database which prohibits reuse that does that. If you aren't do doing that, ensuring that each use of a UUID is not a reuse of an already assigned UUID, they are not UNIQUE.

umpalumpaaa 3y ago
Did you read the full article? "Reducing the length of your IDs can be nice, but you need to be careful and ensure your system is protected against ID collissions. Fortunately, this is pretty easy to do in your database layer. In our MySQL database we use IDs mostly as primary key and the database protects us from collisions. In case an ID exists already, we just generate a new one and try again. If our collision rate would go up significantly, we could simply increase the length of all future IDs and we’d be fine."
- roywiggins 3y ago
  Strictly speaking you can't be sure that your UUIDv4 isn't (by pure luck) also in someone else's database, so it's not guaranteed to be universally unique. It's just very, very likely to be so.
  - partdavid 3y ago
    For some value of "strictly speaking", this is true; but it's not a very relevant value. You can't be "sure" your counter never produces a duplicate, either--strictly speaking--in reality. The bug-free program or the computer that isn't affected by external factors is like the friction-free surface: sometimes useful to think about but not something that exists in reality. And the likelihood of a cosmic ray causing a bit flip or a race condition in the way your counter updates is a lot higher (as in, we see it happen all the time) than the theoretical likelihood of a collision on a sufficiently large and random key.
  - vesinisa 3y ago
    > by pure luck No, even that is not true. If all digital (and non-digital) storage media ever manufactured by humans - meaning all hard drives, tape drives, CDs, DVDs, BluRays etc. ever manufactured to date, and every book and word ever printed or written down. If those ALL were only filled in with UUIDv4s generated from a good random source .. you would still not see even one single collision! UUID collisions are only possible with currently known human technology if your randomness source is not good enough. And it will remain so unless there are some astronomical leaps in digital information storage technology - at least 10 orders of magnitude more storage than currently exists. EDIT: I thought of a way for programmers to mentally visualize how unlikely UUID collisions really are. Let's imagine that in some not-too-distant future, there are 10 billion people on Earth. Each of them are given one thousand CPUs. These CPUs have 1024 cores each, and they run at 10 GHz (clock cycles per second). The CPUs implement a hypothetical instruction that can generate a totally random UUID in one clock cycle. As an experiment, all people on Earth one day decide to program all their thousand CPUs each to run a tight loop that will indefinitely generate UUIDs on all 1024 cores and then immediately discard them. After continuing to run this experiment (whose electicity bill will make Bitcoin look like Earth Hour) all day, 24/7, for about 800 years, the likelihood of one UUID ever having been generated twice will have exceeded 50%.
    - kwantam 3y ago
      I'm sorry to say that your analysis is wildly incorrect. - 10 billion people =~ 2^33 - 1000 CPUs =~ 2^10 - 1024 cores =~ 2^10 - 10 GHz =~ 2^33 So: one second's computation by all of these people is 2^86 UUIDs generated. UUIDs are 128 bits. With probability essentially 1, there will be a collision within one second. The reason is known as the birthday paradox. If you sample random values from a set of size k, after you've chosen about sqrt(k) values you will have chosen the same value twice with probability very close to 1/2. By 10*sqrt(k) samples you'll have found a collision with probability well over 90%. In this case, after sampling 2^64 values you'll have a collision with probability 1/2. That happens in roughly 250 nanoseconds (2^-22 seconds) in your thought experiment. 2^64 sounds like a lot, but in many contexts it's not all that much. Every bitcoin block mined takes well in excess of 2^70 SHA evaluations. Obviously the miners are not dedicated to generating UUID collisions, but if they were they'd easily find thousands of them in the time it takes to mine one block (this neglects the fact that it is much easier to sample a UUID than to evaluate double-SHA256).
deleted 3y ago
[deleted]
wongarsu 3y ago
If you ensure each UUID is generated to spec, using a good source for the random bits, they are astronomically unlikely to collide without any coordination. Choosing the same 124 bits at random just doesn't happen by chance. Of course you have to deal with the implications of people intentionally colliding UUIDs, so maybe don't generate them client-side.
tossandthrow 3y ago
that is not correct and borders wrong. a reason to use uuid (eg v4) is that you can generate id's distributed without fearing collisions. it can happen, but is not likely. so the uniqueness comes from a property of the ID and not the database.
partdavid 3y ago
In the real world, the likelihood that a bug in your database engine or ID-hander-outer (a race condition, storage edge case or the like) is a lot higher than the risk of collision on a sufficiently large and random key. The whole point of using UUIDs is that you can generate them locally without central coordination--if you want to coordinate your identifiers, you can use a much friendlier ID length (which is explained in the article).
- kevincox 3y ago
  But you still need to be wary of malicious collisions. I have seen security vulnerabilities where the client generates a UUID ID and that was inserted into the database. However by picking an ID that corresponded to objects from other users it was possible to gain some access to those objects. So any UUID coming from an untrusted source (like a client application) should be checked for uniqueness. However your client apps can be written assuming that their randomly generated UUIDs never have collisions.
  - echoangle 3y ago
    Why would you let the client generate the IDs? If you have to check them anyways, just generate them on the server and only give the ID to the client.
    - kevincox 3y ago
      It can be very useful for offline work and latency hiding. For example the client can generate data structures with the final IDs then sync them to the server. This can also be useful for implementing idempotent updates. The alternative of having some sort of "placeholder ID" until the sever gets back to you (or you get back online) adds a lot of client complexity.
      - echoangle 3y ago
        Can't you just give the client a list of generated IDs on the first request and check if the IDs are from the pregenerated IDs afterwards? That should be a lot cheaper than checking all IDs you ever generated.
pie_flavor 3y ago
You'll see your first duplicate already-assigned v4 UUID (anywhere on earth) in a few thousand years.
vesinisa 3y ago
What part of "universally unique" in Universally Unique Identifier (UUID) you don't understand? They are specifically designed so that you can generate them locally without fearing collisions. That's like.. their entire point.
- cryptonector 3y ago
  That's an aspiration, not a guarantee.
  - deleted 3y ago
    [deleted]
dragonwriter 3y ago
One of the major motivations for UUIDs is that you can generate them in a decentralized fashion, without central registration, with a very high degree of confidence that they will not be repeated, a very important feature in distributed systems where you don’t want to rely on a either a central point of failure or the need for distributed consensus just to generate an ID for data elements.

umpalumpaaa 3y ago

Did you read the full article? "Reducing the length of your IDs can be nice, but you need to be careful and ensure your system is protected against ID collissions. Fortunately, this is pretty easy to do in your database layer. In our MySQL database we use IDs mostly as primary key and the database protects us from collisions. In case an ID exists already, we just generate a new one and try again. If our collision rate would go up significantly, we could simply increase the length of all future IDs and we’d be fine."

roywiggins 3y ago
Strictly speaking you can't be sure that your UUIDv4 isn't (by pure luck) also in someone else's database, so it's not guaranteed to be universally unique. It's just very, very likely to be so.
- partdavid 3y ago
  For some value of "strictly speaking", this is true; but it's not a very relevant value. You can't be "sure" your counter never produces a duplicate, either--strictly speaking--in reality. The bug-free program or the computer that isn't affected by external factors is like the friction-free surface: sometimes useful to think about but not something that exists in reality. And the likelihood of a cosmic ray causing a bit flip or a race condition in the way your counter updates is a lot higher (as in, we see it happen all the time) than the theoretical likelihood of a collision on a sufficiently large and random key.
- vesinisa 3y ago
  > by pure luck No, even that is not true. If all digital (and non-digital) storage media ever manufactured by humans - meaning all hard drives, tape drives, CDs, DVDs, BluRays etc. ever manufactured to date, and every book and word ever printed or written down. If those ALL were only filled in with UUIDv4s generated from a good random source .. you would still not see even one single collision! UUID collisions are only possible with currently known human technology if your randomness source is not good enough. And it will remain so unless there are some astronomical leaps in digital information storage technology - at least 10 orders of magnitude more storage than currently exists. EDIT: I thought of a way for programmers to mentally visualize how unlikely UUID collisions really are. Let's imagine that in some not-too-distant future, there are 10 billion people on Earth. Each of them are given one thousand CPUs. These CPUs have 1024 cores each, and they run at 10 GHz (clock cycles per second). The CPUs implement a hypothetical instruction that can generate a totally random UUID in one clock cycle. As an experiment, all people on Earth one day decide to program all their thousand CPUs each to run a tight loop that will indefinitely generate UUIDs on all 1024 cores and then immediately discard them. After continuing to run this experiment (whose electicity bill will make Bitcoin look like Earth Hour) all day, 24/7, for about 800 years, the likelihood of one UUID ever having been generated twice will have exceeded 50%.
  - kwantam 3y ago
    I'm sorry to say that your analysis is wildly incorrect. - 10 billion people =~ 2^33 - 1000 CPUs =~ 2^10 - 1024 cores =~ 2^10 - 10 GHz =~ 2^33 So: one second's computation by all of these people is 2^86 UUIDs generated. UUIDs are 128 bits. With probability essentially 1, there will be a collision within one second. The reason is known as the birthday paradox. If you sample random values from a set of size k, after you've chosen about sqrt(k) values you will have chosen the same value twice with probability very close to 1/2. By 10*sqrt(k) samples you'll have found a collision with probability well over 90%. In this case, after sampling 2^64 values you'll have a collision with probability 1/2. That happens in roughly 250 nanoseconds (2^-22 seconds) in your thought experiment. 2^64 sounds like a lot, but in many contexts it's not all that much. Every bitcoin block mined takes well in excess of 2^70 SHA evaluations. Obviously the miners are not dedicated to generating UUID collisions, but if they were they'd easily find thousands of them in the time it takes to mine one block (this neglects the fact that it is much easier to sample a UUID than to evaluate double-SHA256).

deleted 3y ago

[deleted]

wongarsu 3y ago

If you ensure each UUID is generated to spec, using a good source for the random bits, they are astronomically unlikely to collide without any coordination. Choosing the same 124 bits at random just doesn't happen by chance. Of course you have to deal with the implications of people intentionally colliding UUIDs, so maybe don't generate them client-side.

tossandthrow 3y ago

that is not correct and borders wrong. a reason to use uuid (eg v4) is that you can generate id's distributed without fearing collisions. it can happen, but is not likely. so the uniqueness comes from a property of the ID and not the database.

partdavid 3y ago

In the real world, the likelihood that a bug in your database engine or ID-hander-outer (a race condition, storage edge case or the like) is a lot higher than the risk of collision on a sufficiently large and random key. The whole point of using UUIDs is that you can generate them locally without central coordination--if you want to coordinate your identifiers, you can use a much friendlier ID length (which is explained in the article).

kevincox 3y ago
But you still need to be wary of malicious collisions. I have seen security vulnerabilities where the client generates a UUID ID and that was inserted into the database. However by picking an ID that corresponded to objects from other users it was possible to gain some access to those objects. So any UUID coming from an untrusted source (like a client application) should be checked for uniqueness. However your client apps can be written assuming that their randomly generated UUIDs never have collisions.
- echoangle 3y ago
  Why would you let the client generate the IDs? If you have to check them anyways, just generate them on the server and only give the ID to the client.
  - kevincox 3y ago
    It can be very useful for offline work and latency hiding. For example the client can generate data structures with the final IDs then sync them to the server. This can also be useful for implementing idempotent updates. The alternative of having some sort of "placeholder ID" until the sever gets back to you (or you get back online) adds a lot of client complexity.
    - echoangle 3y ago
      Can't you just give the client a list of generated IDs on the first request and check if the IDs are from the pregenerated IDs afterwards? That should be a lot cheaper than checking all IDs you ever generated.

pie_flavor 3y ago

You'll see your first duplicate already-assigned v4 UUID (anywhere on earth) in a few thousand years.

vesinisa 3y ago

What part of "universally unique" in Universally Unique Identifier (UUID) you don't understand? They are specifically designed so that you can generate them locally without fearing collisions. That's like.. their entire point.

cryptonector 3y ago
That's an aspiration, not a guarantee.
- deleted 3y ago
  [deleted]

dragonwriter 3y ago

One of the major motivations for UUIDs is that you can generate them in a decentralized fashion, without central registration, with a very high degree of confidence that they will not be repeated, a very important feature in distributed systems where you don’t want to rely on a either a central point of failure or the need for distributed consensus just to generate an ID for data elements.