When are you truly forced to use UUID as part of the design?

Question

I don't really see the point of UUID. I know the probability of a collision is effectively nil, but effectively nil is not even close to impossible.

Can somebody give an example where you have no choice but to use UUID? From all the uses I've seen, I can see an alternative design without UUID. Sure the design might be slightly more complicated, but at least it doesn't have a non-zero probability of failure.

UUID smells like global variables to me. There are many ways global variables make for simpler design, but its just lazy design.

Answer 1

At my last job, we were getting objects from third parties that were uniquely identified with UUID. I put in a UUID->long integer lookup table and used long integer as my primary keys because it was way faster that way.

Answer 2

A classic example is when you are replicating between two databases.

DB(A) inserts a record with int ID 10 and at the same time DB(B) creates a a record with in ID 10. This is a collision.

With UUIDs this will not happen as they will not match. (almost certainly)

Answer 3

An emphasis on "reasonably" or, as you put it, "effectively": good enough is how the real world works. The amount of computational work involved in covering that gap between "practically unique" and "truly unique" is enormous. Uniqueness is a curve with diminishing returns. At some point on that curve, there is a line between where "unique enough" is still affordable, and then we curve VERY steeply. The cost of adding more uniqueness becomes quite large. Infinite uniqueness has infinite cost.

UUID/GUID is, relatively speaking, a computationally quick and easy way to generate an ID which can be reasonably assumed to be universally unique. This is very important in many systems which need to integrate data from previously unconnected systems. For example: if you have a Content Management System which runs on two different platforms, but at some point need to import the content from one system into the other. You don't want IDs to change, so your references between data from system A remain intact, but you don't want any collisions with data created in system B. A UUID solves this.

Answer 4

It is never absolutely necesary to create a UUID. It is, however convinient to have a standard where offline users can each generate a key to something with a very low probability of collision.

This can aid in database replication resolution etc...

It would be easy for online users to generate unique keys for something without the overhead or possibility of collision, but that is not what UUIDs are for.

Anyways, a word on the probability of collision, taken from Wikipedia:

To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion, equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%.

Answer 5

Using the version 1 algorithm it seems that it is impossible collision under the constraint that less than 10 UUIDs per millisecond are generated from the same MAC address

Conceptually, the original (version 1) generation scheme for UUIDs was to concatenate the UUID version with the MAC address of the computer that is generating the UUID, and with the number of 100-nanosecond intervals since the adoption of the Gregorian calendar in the West. In practice, the actual algorithm is more complicated. This scheme has been criticized in that it is not sufficiently 'opaque'; it reveals both the identity of the computer that generated the UUID and the time at which it did so.

Someone correct me if I misinterpreted how it works

Answer 6

The thing that UUIDs buy you that is very difficult to do otherwise is to get a unique identifier without having to consult or coordinate with a central authority. The general problem of being able to get such a thing without some sort of managed infrastructure is the problem the UUIDs solve.

I've read that according to the birthday paradox the chance of a UUID collision occuring is 50% once 2^64 UUIDs have been generated. Now 2^64 is a pretty big number, but a 50% chance of collision seems far too risky (for example, how many UUIDs need to exist before there's a 5% chance of collision - even that seems like too large of a probability).

The problem with that analysis is twofold:

1. UUIDs are not entirely random - there are major components of the UUID that are time and/or location-based. So to have any real chance at a collision, the colliding UUIDs need tobe generated at the exact same time from different UUID generators. I'd say that while there is a reasonable chance that several UUID's might be generated at the same time, there's enough other gunk (including location info or random bits) to make the likeyhood of a collision between this very small set of UUIDs nearly impossible.

2. strictly speaking, UUIDs only need to be unique among the set of other UUIDs that they might be compared against. If you're generating a UUID to use as a database key, it doesn't matter if somewhere else in an evil alternate universe that the same UUID is being used to identify a COM interface. Just like it'll cause no confusion if there's someone (or something) else named "Michael Burr" on Alpha-Centauri.

Answer 7

On UUID==lazy design

I disagree its about picking your fights. If a duplicate UUID is statistically impossible and the maths is proven then why worry? Spending time designing around your small N UUID generating system is impractical, there are always a dozen other ways you can improve your system.

Answer 8

There is also a non-zero probability that every particle in your body will simultaneously tunnel through the chair you're sitting on and you will suddenly find yourself sitting on the floor.

Do you worry about that?

Answer 9

Everything has a non-zero chance of failure. I would concentrate on far more likely to occur problems (i.e. almost anything you can think of) than the collision of UUIDs

Answer 10

I wrote the UUID generator/parser for Ruby, so I consider myself to be reasonably well-informed on the subject. There are four major UUID versions:

Version 4 UUIDs are essentially just 16 bytes of randomness pulled from a cryptographically secure random number generator, with some bit-twiddling to identify the UUID version and variant. These are extremely unlikely to collide, but it could happen if a PRNG is used or if you just happen to have really, really, really, really, really bad luck.

Version 5 and Version 3 UUIDs use the SHA1 and MD5 hash functions respectively, to combine a namespace with a piece of already unique data to generate a UUID. This will, for example, allow you to produce a UUID from a URL. Collisions here are only possible if the underlying hash function also has a collision.

Version 1 UUIDs are the most common. They use the network card's MAC address (which unless spoofed, should be unique), plus a timestamp, plus the usual bit-twiddling to generate the UUID. In the case of a machine that doesn't have a MAC address, the 6 node bytes are generated with a cryptographically secure random number generator. If two UUIDs are generated in sequence fast enough that the timestamp matches the previous UUID, the timestamp is incremented by 1. Collisions should not occur unless one of the following happens: The MAC address is spoofed. One machine running two different UUID generating applications produces UUIDs at the exact same moment. Two machines without a network card or without user level access to the MAC address are given the same random node sequence, and generate UUIDs at the exact same moment. We run out of bytes to represent the timestamp and rollover back to zero.

Realistically, none of these events occur by accident within a single application's ID space. Unless you're accepting IDs on, say, an Internet-wide scale, or with an untrusted environment where malicious individuals might be able to do something bad in the case of an ID collision, it's just not something you should worry about. It's critical to understand that if you happen to generate the same version 4 UUID as I do, in most cases, it doesn't matter. I've generated the ID in a completely different ID space from yours. My application will never know about the collision so the collision doesn't matter. Frankly, in a single application space without malicious actors, the extinction of all life on earth will occur long before you have a collision, even on a version 4 UUID, even if you're generating quite a few UUIDs per second.

Also, 2^64 * 16 is 256 exabytes. As in, you would need to store 256 exabytes worth of IDs before you had a 50% chance of an ID collision in a single application space.

Answer 11

spend your money fixing bugs, not making extremely unlikely events mathematically impossible. anyway UUIDs aren't just a random number, they use various uniqueness-proofing techniques e.g. embedding timestamps and computer signatures, so probability of collision is magnitudes lower as compared to a naive random distribution.

Answer 12

If you just look at the alternatives e.g. for a simple database application, to have to query the database every time before you create a new object, you will soon find that using UUID can effectively reduce to complexity of your system. Granted - if you use int keys the are 32bit, which will store in a quarter of the 128bit UUID. Granted - UUID generation algorithms take up more computational power than simply incrementing a number. But - who cares? The overhead of managing an "authority" to assign otherwise unique numbers easily outweighs that by orders of magnitude, depending on your intended uniqueness ID space.

Answer 13

I have a scheme for avoiding UUIDs. Set up a server somewhere and have it so that every time some piece of software wants a universally unique identifier, they contact that server and it hands one out. Simple!

Except that there are some real practical problems with this, even if we ignore outright malice. In particular, that server can fail or become unreachable from part of the internet. Dealing with server failure requires replication, and that's very difficult to get right (see the literature on the Paxos algorithm for why consensus building is awkward) and is pretty slow too. Moreover, if all the servers are unreachable from a particular part of the 'net, none of the clients connected to that subnet will be able to do anything because they'll all be waiting for new IDs.

So... use a simple probabilistic algorithm to generate them that is unlikely to fail during the lifetime of the Earth, or (fund and) build a major infrastructure that is going to be a deployment PITA and have frequent failures. I know which one I'd go for.