How long do GUIDs really need to be?

https://eager.io/blog/how-long-does-an-id-need-to-be/?hn

by adamschwartz • 12 years ago

140 100 12 years ago

This is interesting, but it plucks from nowhere the equation for the chances of collision. Here's my write-up of where that comes from:

http://www.solipsys.co.uk/new/TheBirthdayParadox.html?HN_201...

It's intended to be gentle, but a few people have said it's a bit quick in places. I'd appreciate any feedback.

Added in edit: I've submitted it as a separate item - it's been a few months since it was discussed here.

https://news.ycombinator.com/item?id=8540220

whitten• 12 years ago

I appreciate this article. The mention of the Birthday problem made the calculation reasonable, and the trick to ensure time-locality as a fixed bit pattern was enlightening.

dokimorning2• 12 years ago

It seems if he's planning to make 100 million records with a probability of 1 in 1 million of a collision, he's going to end up with ~100 collisions. I think I would plan to make the collision probability of N records at least < 1/N. Plus, one million records is really not so big.

I do like the point that UUIDs are generally stored as strings whereas they represent a 122 bit value. Seems encoding the UUIDs as binary would offer much greater efficiency in storage space as well as indexes.

dfbrown• 12 years ago

It's not a 1 in a million chance for each record, it's a one in a million chance of their being a collision in the entire set of 100 million records. So for every million sets of 100 million records you generate you'll get on average 1 set with a collision.

bkirwi2• 12 years ago

It's 1 in a million chance of any collision across the entire dataset, not 1 in a million records that will have a collision. This is why the article mentions the birthday paradox -- it's taking the chance of a collision between two particular values (and knowing the bits of randomness is enough to give you this) and calculating the chance that there's any collision at all.

lectrick4• 12 years ago

I would never store a UUID as a string for exactly that reason. Either a binary or a native UUID datatype. Any developer IMHO who stores a UUID as a string is suspect.

perlgeek• 12 years ago

You can generalize this idea to: if you are willing to exercise control over some parameters that go into your UID, you need fewer random bits.

For example you could encode a number that identifies the host (like, the last byte or last two bytes of the public IP address) and the process id of the process generating the ID, and as a result you need less entropy for avoiding collisions.

But you risk that somebody who doesn't know UID algorithm screws things up. For example if you use the last byte of the IP address, and some network administrator decides to give each host an IPv6 net, the last byte of the IP might very well be one for each host. (OK, that's a bit of a contrived example; maybe PID namespaces are a better one?).

Or things outside of your control. Your company gets acquired by a much bigger one, and for some reason they decide to use your system for the whole company. Or for a huge customer. And now you're facing a factor 1000 more records than you ever thought possible. Or a factor 10000. History is full of software systems that have been used way beyond what they were planned for originally, and of course nobody revisited all relevant design decisions.

Second point to consider: by making parts of your UIDs deterministic, you also leak information. Like when a dataset was created, and on what host. Which might be relevant for timing attacks, or other kinds of security nastiness that you don't even think about right now.

jacques_chester10• 12 years ago

For example you could encode a number that identifies the host (like, the last byte or last two bytes of the public IP address) and the process id of the process generating the ID, and as a result you need less entropy for avoiding collisions.

UUID v1 does this by encoding the MAC address as part of the UUID. v3 and v5 use a scheme that encode information from other namespaces, eg FQDNs.

mark-r3• 12 years ago

This seems overly complicated. Why not generate an ID out of two numbers, one a server or thread ID and another that auto-increments? Assigning a unique number to each entity that can generate IDs seems like a tractable problem, and the odds of generating a collision can be reduced to zero if you negotiate a new number when the counter wraps around.

JoeAltmaier8• 12 years ago

UUID generation collision is essentially zero too. Any scheme you can contrive has the vulnerability that somebody else may choose the same roots as you, including yourself if you restart unexpectedly.

mark-r3• 12 years ago

Certainly I agree that UUIDs aren't going to collide. But UUIDs were created to solve a problem most people don't have - how to ensure unique IDs when there is absolutely no communication between the parties generating the IDs. The article was suggesting one alternative to the UUID, and I suggested another.

riffraff• 12 years ago

UUIDv1 is in fact: server MAC Address+timestamp. UUIDv2 is instead: UID+MAC Address+timestamp

The debate regarding the length is the same though.

xenadu02• 12 years ago

This seems like useless optimization that has a high probability of biting you in the ass later on.

Using the standard UUID generation facilities in your OS of choice there's zero chance you get something wrong and screw yourself.

UUIDs are great because we can pretty much guarantee global uniqueness. Acquire a company, decide to integrate with someone, need to merge a database, etc? No problem, zero chance of record collisions no matter what happens in the future. (It also means zero chance of accidentally interpreting record #58274 as type A when you meant type C).

Furthermore, a 1 in 1 million chance of collision is far too frequent for my liking, but even if it were acceptable what happens when your service/product becomes far more popular than you imagined and you blow through your initial estimates?

bkirwi2• 12 years ago

This is absolutely right. I suspect some people do this because Twitter went out of their way to get 64-bit ids[0] -- but Twitter did this in large part because they made the mistake of baking that bit-length into the protocol back when they were tiny, and since they don't control all clients, it's very difficult to change.

For comparison, here's an eager.io URL:

https://eager.io/app/ZYBle8qUhKFJ

And here's an equivalent with UUID in base-64:

https://eager.io/app/b8tRS7h4TJ2Vt43Dp85v2A

It's a rare application for which those differences matter. (NB: I don't know anything about eager.io... it might be important for them!)

[0] https://blog.twitter.com/2010/announcing-snowflake

zackbloom6• 12 years ago

It becomes a stylistic choice, but I can say we weren't happy with the experience the longer ids gave users. It made most of the url a random hash of characters, not anything significant. The URL is as much a part of the UX as anything else.

curun1r2• 12 years ago

There's also impact at the data layer. Larger IDs make indexes get a lot bigger. Also, any article on UUIDs that mentions locality without even mentioning using type-1 UUIDs should be taken with a grain of salt.

We looked at using UUIDs last year for a project in MySQL since we had good use cases for handling ID generation outside of the data tier. We originally prototyped using type-4 UUIDs, but found the locality problem made that a non-starter (updating indexes seemed to get exponentially slower when tables went over 10m rows). But switching to type-1 UUIDs made that problem go away. Still, we eventually chose not to use UUIDs since 128 bits made our indexes too large. At the DB level, we represented them as BINARY(16), but even with the pain that caused, our indexes were still too large.

Perhaps it's just a MySQL thing (I didn't make that choice) but, from our testing, I'd be very wary of using 128-bit IDs and would probably choose something like Snowflake or other centralized ID generation service.

Sharlin• 12 years ago

Note that the 1 in 1 million figure is for 100 million IDs generated, that is, after 100 million generated IDs there's 1 in a million chance that two of them are identical.

imron• 12 years ago

It's all fun and games until you discover that one in a million is next Tuesday:

http://blogs.msdn.com/b/larryosterman/archive/2004/03/30/104...

zackbloom6• 12 years ago

I appreciate where you're coming from, but as it says in the article, UUIDs are really unnecessarily long for no good reason. The traditional hex encoding is also much longer than it needs to be.

In any case, the article exists to help you decide how long you need to make your ids for you to be comfortable. If you decide you aren't comfortable with a 1 in a million chance, the math is there for you to figure out what does work for you.

jacques_chester10• 12 years ago

UUIDs are really unnecessarily long for no good reason.

Their purpose is to be universally unique, presumably indefinitely. The practical choice is to align on a power of 2.

When UUIDs were invented, they were based on a MAC address plus a timestamp. MAC addresses are 48 bits, leaving 16 bits. Of these, between 1 and 3 are used up giving the variant code and another four bits are used giving the version code.

If they'd used 64 bits, there'd be between 8 and 11 bits left for a unique timestamp. Which is OK, but not a very strong guarantee for a "unique" scheme.

As it happens the length has made it possible to create multiple versions of UUIDs that are generated in different ways. UUID has been successful at separating the concerns of the structure of the ID from how it is generated. Most alternative schemes are effectively implementation-defined.

wodenokoto• 12 years ago

Actually I think that is the biggest problem with the article. It gives you no way to asses which probability is good enough.

mnarayan01• 12 years ago

No problem, zero chance of record collisions no matter what happens in the future.

Well until 5236-03-31 21:21:00 UTC (assuming my calculations are correct) using v1 UUIDs and assuming unique MAC addresses and no race conditions.

ed02• 12 years ago

Only until 5236?? We definitely need a better solution.

wahern• 12 years ago

Assuming unique MAC addresses is a very poor assumption.

At one company I worked at we once received a huge shipment of ethernet cards (several thousand) that all had the same MAC address. We didn't realize it until customers who had purchased multiple pieces of equipment began to call in.

I've heard several similar anecdotes from other engineers at other companies.

Yeah, very bad assumption.

yohanatan2• 12 years ago

Yea, if you remove the dashes from regular UUIDs and base64 encode them they're not much longer than his custom ones.

kephra• 12 years ago

The problem of both locality and length also only exist in modern databases. Good old Ingres QUEL offered the choice of hash and btree indexes, and the the ability to compress indexes. Index compression is of course much easier with sequential indexes, but it would at least optimize the static host part of the uuid away.

jacques_chester10• 12 years ago

UUIDs have the advantage that they are well-understood and widely supported. If you really need to shave a few bytes here and there, developing your own coding scheme is useful. But for the most part, I don't see the win.

Locality is definitely important, but I must be missing something -- if lookup by date, machine ID etc is required, why not create indices on those fields? Why rely on coincidental locality?

chacham15• 12 years ago

There is a bit of possible misunderstanding/misinformation here: there is a difference between a primary key and a rowid. The reason that I point out this distinction is that rows are stored on disk by rowid, meaning that an insert will still usually insert to the end. On the flip side, yes, the index will have this problem, but the index shouldnt be very large relative to the table meaning that it shouldnt be as expensive as the OP is thinking. Note: often the database will optimize and use the auto increment primary key as the rowid, but it wont for a uuid primary key.

curun1r2• 12 years ago

When we tested on MySQL, the update to the index really was that bad, once you reached a threshold of 10m-20m rows. And it got progressively worse to the point where we were never able to get a table with 100m rows using type-4 UUIDs.

It's a moot issue anyways since type-1 UUIDs don't have this problem. They're monotonic, which allows index updates to only need to append.

marcosdumay• 12 years ago

It really shouldn't. B-trees have O(log n) insertion time, they shouldn't take much longer when your dataset grows.

But then, it's MySQL. I was surprised by your experience, but not that much.

girvo• 12 years ago

But because Type-1 UUIDs encode the MAC address and assume it's unique, which isn't always the case, I'd be a bit worried about it. Should I be? If not, then it seems like an excellent solution.

mumrah• 12 years ago

If you want sequential IDs with no chance of collisions, read up on "flake" IDs

* https://blog.twitter.com/2010/announcing-snowflake

* http://engineering.custommade.com/simpleflake-distributed-id...

* http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-...

* https://github.com/mumrah/flake-java

thedufer3• 12 years ago

"no chance of collisions" can't be applicable to any finite-length ID. Low chance, perhaps.

That said, this appears to be exactly the scheme MongoDB uses (except Mongo IDs are 96 bits).

Goopplesoft2• 12 years ago

Actually it can. As long as they aren't randomly generated. UUID4s are random, lots of them including the mongodb use a timestamp/mac address as the first n bits of the guid. Not sure whether they have "no chance of collisions" but it is very possible.

JoeAltmaier8• 12 years ago

Ok, Less likely than the chance your computer will spontaneously catch fire while running your code. Less likely than the chance the sun will emit a colossal solar flare and engulf the earth in a firey death.

pauldbau• 12 years ago

For .NET / SQL Server people, check out GuidCombs if you want better Primary Key performance. These are a great way of making GUIDs sequential for database use, giving indexing performance close to ints on SQL Server.

I imagine this approach could also work on Postgres and other dbs that have made GUID/UUIDs a first class data type. You'd just have to understand how that database applies its indexing algorithm.

Description of the GuidComb approach here: http://www.informit.com/articles/article.asp?p=25862

GuidComb implementation in C# (from NHibernate core) here: https://github.com/nhibernate/nhibernate-core/blob/master/sr...

lectrick4• 12 years ago

Twitter came up with a different scheme called Snowflake (https://github.com/twitter/snowflake).

StavrosK• 12 years ago

I didn't like long UUIDs either, so I wrote this small Python library to re-encode them using a more varied character set:

https://github.com/stochastic-technologies/shortuuid

erik14th• 12 years ago

I don't get GUIDS, couldn't you just prefix the sequential IDS for each node producing IDS?

jacques_chester10• 12 years ago

UUIDs come in different versions. v1 UUIDs are built out of MAC addresses and a timestamp, which is similar to what you're proposing.

Unfortunately, or fortunately, depending on your requirements, it is easily predictable.

lmm6• 12 years ago

You could, if you've got a good, future-proof way of assigning each note a unique ID.

pbhjpbhj• 12 years ago

When your IDs are random however, each new record has to be placed at a random position. This means a lot more thrashing of data to and from disk. //

Just use the GUID externally and use have a sequential primary key as the table index?

zackbloom6• 12 years ago

The issue is with distributed systems where you have multiple actors all needing to insert records with minimal coordination. Using random ids is also very helpful when you want to be able to generate records on the client and then sync them to the server later. In either case, it's difficult to know what that sequential primary key should be.

pan69• 12 years ago

Exactly. I never expose my database Id's to the outside world but generate a random token for each of my objects that has to be. This token is then translated to a database Id which is then used from then on. This allows for the greatest flexibility.

zackbloom6• 12 years ago

That's not going to be the most efficient option, as it means all your indexes need to include both the primary key, and this secondary id. I would encourage you to think about just using the random token as the primary key.

ninjaplease2• 12 years ago

What on earth? Are you going to be changing object ids? Is knowing an object's id an attack vector? Sounds like you are doing it wrong.

ninjaplease2• 12 years ago

Reading comprehension fail?

lobster_johnson• 12 years ago

The article mentions "friendly" URLs as being a driving factor. That makes it a presentation issue; ie., it's part of the content, and it is wise to consider if you can derive it from the content.

For a blog post, for example, there is a title. The classic way of adding a readable date to the URL is useful, if you're reading the URL in the first place. This particular blog post uses that approach: https://eager.io/blog/how-long-does-an-id-need-to-be/.

For other objects there might still be useful data. Instead of /invitation/3jdix8jAJm you might have /invitation/myblog/bob@example.com/u7pW, the last part being an auto-generated random component. The benefit is that the ID becomes self-explanatory (self-describing) and very nice for tracing through logs and the like. Of course, one has to be careful about not exposing anything exploitable.

amelius• 12 years ago

The short answer: if the probability of a collision is smaller than the probability of a meteor landing on your head, then you're fine.

chris_va• 12 years ago

As a warning, don't try to be too clever with your ID system. You can get collision bugs that aren't usually visible in testing.

I had a catastrophic bug (ala private data going to the wrong person) from 96-bit (32 bit segment number, 64 bit random local docid) ID collisions when the caching code decided it was going to use docid as the cache key without realizing it was missing a bunch of bits.

stith• 12 years ago

I had a similar issue with an app I'm writing now. I wanted short IDs so my URLs wouldn't be fugly, but with a low chance of collisions. The solution I went with (in javascript) is:

    // Make a "pretty unique" ID for this session.
    // Since RethinkDB doesn't have a way for us to guarantee a _short_
    // random unique value (short of trying the insert and regenerating if it
    // doesn't save), we'll just have to rely on the unlikeliness of a collision
    // with both this time-based ID and the title-based slug.
    // I'm sure this will never ever cause any problems ʘ‿ʘ
    var alphabet = "0123456789abcdefghijklmnopqrstuvwxyz";
    var id = new Date().getTime().toString().match(/.{1,2}/g).map(function(val){return alphabet[val % alphabet.length];}).join('');
    var slugPart = slug((this.title || "").substring(0,60).toLowerCase());
    this.url_slug = id + "/" + slugPart;

That is, get a current timestamp (in milliseconds), and use every group of 2 digits to pull a letter out of an alphabet string. Then append "/title-of-the-thing-made-url-safe". This results in strings that look like "ee7zrm9/something-goes-here", which is then used as the primary key for the document. It's not perfect by any means, but it gets the job done, and I thing appending the title makes collisions extremely rare.

JoshTheGeek• 12 years ago

Couldn't you generate a UUID and then check the database that it is unique before using it? You could then repeat until you got a unique identifier.

jacques_chester10• 12 years ago

UUIDs have the advantage that no coordination is required. With a database you will create coordination problems as you scale up your system.

I have either a high or total assurance that any UUID I self-assign has never been used anywhere, ever, for anything else, by anyone else, in any system.

In fact, the odds that I will have a collision with another UUID are lower than a cosmic ray striking a computer at the moment when it is performing the uniqueness check.

SeoxyS• 12 years ago

I do something very similar: 64-bit IDs start with a timestamp with a custom epoch, and fill in the rest with random data. I store these in bigints in Postgres.

Kenji• 12 years ago

He assumes that the UUIDs are independent (selected independently uniformly at random). They are not. Trust me, it's very, very hard to get this kind of 'pure' randomness on computers. No matter what randomness you use, you will have some correlation and your odds to get different UUIDs drop rapidly.

jacques_chester10• 12 years ago

Then use v5 UUIDs. Or /dev/urandom, which seeds a PRNG with hardware-sourced randomness.

lmm6• 12 years ago

On the contrary, there is such a thing as a CSPRNG, and many of them exist.

gbrits• 12 years ago

This may be a bit naive but are UUIDV4 completely random from 'head-to-tail'? I mean, given the birthday paradox calculation, couldn't you just take head of the uuidv4 (i.e.: the first x characters) to arrive at the collision/space-consumption tradeoff you want?

lmm6• 12 years ago

There are a few bytes for the version number, but other than that, yes.

I mean, given the birthday paradox calculation, couldn't you just take head of the uuidv4 (i.e.: the first x characters) to arrive at the collision/space-consumption tradeoff you want?

Yes you could, but is that actually any easier than "generate x random bytes"?

How long do GUIDs really need to be?

Related Stories