How long do GUIDs really need to be? | Hacker News Reader

How long do GUIDs really need to be?

eager.io

140 pointsadamschwartz100 comments

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?

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

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.

"The URL is as much a part of the UX as anything else."

Given what we've seen from the browser vendors lately (hiding bits of the address bar, etc), I'd say there's a lot of momentum to disagree with that statement.

I think it depends on who your customer is / what your product is. When I'm developing against an api, I end up writing API calls in my terminal to test things. I prefer cleaner URLs for APIs.

Is the difference between bkirwi's two examples really significant? The eager.io URL is still a mash of random characters.

(FWIW I like seeing UUIDs in my URLs, because it tells me that the company on the other end has its shit together. That might be a bit programmer-specific though)

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.

Sometimes you don't need to index all 16 bytes, and can get by with a prefix index.

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.

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

I've watched as the application we develop at work has switched from ancient single and dual core Linux boxes to (now) dual-dodeca-core boxes and all sort of "completely impossible" races have surfaced. All progressively more "impossible" as the number of cores and their speed has kept on increasing.

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.

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

This is all true, and I'm not here to say the original implementers did anything wrong. As you say though, UUIDs are a general solution, which means they're not going to be optimal for every problem.

UUIDs are optimal for every problem, in that they are unique and fairly fast to generate. There can be no better solution than that, except maybe to save a few bits. And we're only talking about 16 bytes here; not much to complain about. They're cheap at the price.

Yeah its hard to get folks to come into the modern age of computering. FOr some reason there's tremendous resistance to abandoning the old crusty buggy solutions (indexes and handles that collide and need remapping) and using stuff that just works (identifying everything immutable with a uuid). Folks say 'its too many bits' and 'it takes too long'. Then they proceed to write megabytes worth of patchy code to try and save 64 bits worth of identifier.

As for database efficiency, that's a problem. But its a problem with the database - certainly no comfort for the user. But databases could do better, and I think they will one day come to handle uuids with less grief to the developer.

They already do. Postgres and SQL Server have UUID types.

Yeah, exactly. Building weakness into one's protocol because of an unhealthy attachment to saving a few bits and an even more unhealthy attachment to MySQL just seems foolish.

If you work with large amounts of data it hugely matters. 16 bytes times 1 billion records ends up being way more than 16GB of data, indexes, foreign keys, hot backup, etc. to manage and query.

Even that is a small amount of memory. I have that much RAM on my computer. See, its an obsolete conversation, yet folks raised in an ecology of scarcity can't get past it.

It depends on what you are optimizing for. If you need to store your entire database in physical memory, then the difference between 16GB and 128MB is significant.

No, but I think most people overoptimise on the shiny stuff ("oooooh, I saved some bits!") over the important stuff (nasty surprises, several years from now).

Yeah, but sometimes "saving some bits" is really important. It's also really inconvenient to work with UUIDS, like in writing SQL queries etc. The solution these guys came up with obviously works for them.

Precisely the argument from Dilbert's Y2K episode: http://www.tv.com/shows/dilbert/y2k-12015/

How are these eager.io IDs any easier to work with in SQL queries etc.?

> It's also really inconvenient to work with UUIDS, like in writing SQL queries etc.

http://www.postgresql.org/docs/8.3/static/datatype-uuid.html makes it look pretty easy…

UUIDs are 128-bits...

> If they'd used 64 bits

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

I think thats a business decision, not a technical one. You have to decide what odds you are willing to accept, based on how many records you anticipate, how hard it will be to increase the length if that estimation is wrong, and how bad it would be if there was a collision.

In any case though, there are certainly many bad things which could happen to your company which are more likely than 1 in a million.

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

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

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.

A lot of platforms (iOS) also spoof MAC addresses too

The spoofing happens when talking to other devices (not themselves); i.e., there is some layer of the device that knows its true MAC address and the UUID generation code should use that layer.

Can confirm that this is a bad idea as manfuarcturing defects do happen. Took a shipment of brand new NetApp toasters this year and they all had the same WWN/WWPN's!

Needless to say NetApp where quite embarrassed and we are glad that we noticed it in pre-prod otherwise it could have been quite bad.

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

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.

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

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

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.

"no chance" means making a claim that there will never be 2^N devices generating IDs simultaneously (for N somewhere around 30-60)

2 machines can have the same MAC addresses (they are reprogrammable) and can operate at the same microsecond.

"aren't randomly generated" is not practical constraint in a high-speed distributed system (where you don't have time for synchronization overhead).

Its an infinitesimally small chance. You'd need a mac collision, must be generated at the same time, and a uuid collision. Even at the largest scales (Google et all) the probability of that happening is effectively 0.

Yes. And my glass of water could spontaneously turn into ice. However, I do not expect it to happen anytime soon.

Please, generate 2^<length>+1 of them and let me know how it goes.

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.

Right, but that's the point of a GUID. Claiming no chance makes it sound like its distinct from other GUID generators in that way. I think the intended claim is "here is a scheme for roughly timestamp-ordered GUIDs", which makes it clear that the timestamp-ordering is the interesting part.

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

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

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.

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

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?

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.

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.

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.

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.

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.

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.

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.

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

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

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.

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.

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.

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.

Reading comprehension fail?

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.

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?

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"?

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

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.

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.

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.

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.

Ah. Thank you for clarifying that point. Seems 1 per 100 trillion records would be much more acceptable.

Also, to whoever downvoted my very first post here: Way to build a community @sshole. I'm never commenting here again thanks to you, jack@ss.

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.

Postgres has a UUID type, for example.

I've always seen UUIDs stored as strings. What's the suspect part? Favoring human readability over optimal machine storage utilization?

Human readability is a concern of a client and is independent of the storage mechanism. Every modern database stores integers in binary format, for instance, but clients display them as a decimal string of characters as opposed to a binary or hexadecimal representation. Timestamps are similarly stored in binary fashion, but often formatted for human readability in the client.

UUID is not a universally available primitive type like integer or date.

Someone hasn't used Postgres. http://www.postgresql.org/docs/9.1/static/datatype-uuid.html

And anyway, all a UUID is, ultimately, is a big number. It's a simple transcoding to get it into base-10 integer format and back.

If you're using an SQL database you're presumably doing so so that humans can run ad-hoc reports (otherwise there are better datastores). So the UX they get for that is important. And in mysql (yes, not the best choice these days, but a reasonable one when the decision was made), if you store UUIDs as binary (there's no native UUID type) then you do not provide a good UX.

MySQL itself should not be the main interface; there should be some kind of model layer on top of that which does the translation of things like that, such as (for example) ActiveRecord if you were on a Rails stack. That gets you the best of both worlds.

OR you could store the uuid twice, once "natively" and once as a computed column. Searches on the native field would be faster vs. an index on a string column.

> you're presumably doing so so that humans can run ad-hoc reports (otherwise there are better datastores)

oh dear, someone has drank the NoSQL punch... Storing data relationally is NOT something only suitable for ad-hoc queries by end-users! :O

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.

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.

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.

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

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.

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

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.

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.

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.

Sure but why? We have UUID's and good generators. Run with it.

UUIDs solve a problem many, many people do have - identifying things over time and space - without having to even consider communication/coordination. That's a very powerful property.

Again, I'm not arguing that UUIDs aren't a powerful tool. But the article points out two problems with them - they're inconveniently long when you expose them to the user, and they lead to a fragmented database because they're not generated in order. If those problems matter to you, then you look for an alternative. If they don't, then the UUID is the go-to solution.

Very true. Some help: Inside a self-consistent database you might index the UUIDs and use the index internally to link them other places. Or something like that. Its work. If more use were made of UUIDs, databases would handle them better and that's probably going to happen.

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

The debate regarding the length is the same though.

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.

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

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

Reply on news.ycombinator.com