Sortable Collision-Free UUIDs

So here's a real-world use case that having an RFC 4122 UUID was useful for me.

I have a server which accepts reports and stores them in S3. For each new report, a v4 UUID is generated that that is used as the base of the S3 object name. This UUID becomes the report ID.

An entire system has been built around the report ID, expecting a hex UUID. Recently, I needed to change how the objects are stored in S3 in order to partition them into multiple S3 prefixes. Instead of storing every object in a single place in the S3 bucket, I needed to do something like:

    "reports/%s/%s" % (report_id[:2], report_id[2:])

The issue was that I had one component that was writing the reports, and a second component reading the reports. And somehow, the reader needed to know whether a report was stored using the old path layout:

    "reports/%s" % (report_id,)

Or the new path layout. I took advantage of the fact that RFC 4122 UUIDs have four bits set aside for version. After generating a v4 UUID, I update its version to 5. The reader can then check the report UUID version to know which path layout to use. Once all the reports stored using the old path layout expire, I can undo this hack.

Of course, I could have made the reader try the new path layout, then fall back to the old path layout. Or I could have updated the entire system to have a better way of communicating the path layout, but that would've been less efficient or have meant touching a lot more code.

I guess the moral of the story is: you never know when you're going to need to change something in a backwards compatible way, and having a few bits set aside even for something as simple as an object ID can be useful. I'm fortunate the UUID designers thought of that.

In broader industry these days, UUID effectively means “128-bit unique identifier” with no other standardization implied. I’ve seen dozens of custom “UUID” designs with no public description in the wild used at massive scales. A major reason for this is that the classic standard UUIDs v1-v5 have a broken design for some use cases so companies invent their own equivalents.

There is nothing wrong with designing a custom pseudo-UUID, and in fact there are often real advantages. The caveat is that you will want to use the same scheme consistently.

Well, yes. As I said, it'll be "totally fine". :)

The problem is, the submission said "collision-free". This isn't "collision-free", it's "collisions are so unlikely you don't need to worry even under extremely conservative assumptions, assuming you have a decent source of randomness". And that's good enough for me, absolutely.

But...if that's good enough, then really, any of the common UUID and UUID-like schemes will be good enough. I'm taking the submission title to mean either "guaranteed collision-free" or, failing that, as "more collision resistant than some alternatives", or maybe "guaranteed collision-free in some specific use cases". But this doesn't seem to be any of those; it's just a timestamp and enough randomness that you'll be safe under reasonable assumptions.

In short, I'm not saying "don't use this because you'll get collisions", I'm saying "even though as a practical matter you won't see any collisions, I don't think the collision free label is appropriate".

The collision risk depends on the application and use case. In sufficiently large real systems, a probabilistic pseudo-UUID with only 96 bits of entropy has a collision probability that is very small but not so small that you can treat it as effectively zero if avoiding collisions is critical. I’ve seen multiple systems that generate unique identifiers at rates > 10^9 per second. The 128-bit size has a lot of advantages, but probabilistic identifiers are expressly disallowed for some applications and contracts because of the collision tail risk. Making the identifier larger than 128-bits has other significant costs so that generally is not an option either.

That aside, generating probabilistic UUIDs at the rates where this is an issue is a bad idea regardless for performance reasons.

> you couldn't get collision.

You mean probably. With which you mean there's a low chance of this happening. For that one second. But there are many more seconds after that. Plus you have to assume your PRNG never has any weird hiccups - such as when someone does VM shenanigans.

This isn't "guaranteed" to be collision free at all.

I'm not playing dice when I want implement reliable systems.

Yes, the offset is a round decimal number, but I'm not sure why that makes it a very good epoch. The code actually has it as "16 * 10 * 8", but it seems like an obvious optimization would be to hard code it as, yes, 1600000000. But if you're hard coding that, you could hard code 1609459200 (for a round date) or 1620073869 (for when the initial commit was made) or whatever instead.

Any choice will inevitably be arbitrary, but this feels like it may have been chosen for odd reasons to me.

It’s worse with clustered indexes — all of the data experiences this issue, not just the index.

Though something to point out that this project misses is that UUID sorting is its whole own weird can of worms. I just went through this exercise trying to get ULID to GUID conversion/round-tripping that matched MS SQL Server's GUID sort order in hopes for the benefits of those small, pleasant properties.

In short, because SQL Server's sort order is based on GUID/UUID v1, the "group" that matters most significantly for sort order (in SQL Server, but other GUID tools are different) is the tail 6 bytes (not the head bytes as these FUUIDs are using which would allow them to sort in unix sort in GUID form). (As the tail 6 bytes are the "machine ID" in v1 UUIDs.)

For anyone curious how deep (and which endian) the rabbit hole goes in GUID sorting, I kept referring to Raymond Chen's somewhat comprehensive description of GUID sort orders across Microsoft products in my efforts: https://devblogs.microsoft.com/oldnewthing/20190426-00/?p=10...

On the other hand, doesn’t that mean that a workload that inserts new sortable uuids would experience lots of contention, while one that inserts random uuids would better spread load? (This is probably more significant in a distributed database sharded by uuid, where this means all the write load is going to one shard at a time.)

Version 4 would still be more secure in the sense that it doesn’t leak any extra info and as you note it can be generated using a a cryptographically-secure PRNG.

With sortable IDs, you could potentially know when some item was generated, which may or may not be useful info, but why take the risk? I think it makes sense to minimise the data that the app or service exposes. With a regular uuid you can control whether you expose or not the creation time, while with sortable ids you can’t.

I always just define a custom comparison operator, which is easy enough in both C++ and PostgreSQL.

Good to know, thanks.

The format only reserves for bytes