Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sortable Collision-Free UUIDs

github.com

Post reply on HN
Print view View original

41–50 of 65 posts

Re: Sortable Collision-Free UUIDs

#41

Post by Lazare »

zoltar wrote: post #32
Lazare wrote: post #23

First, for something like this, the details matter a lot. How many bits of randomness is this, how many bits used for the timestamp, what's the format, why does it yield the advantages claimed, and most of all, how does it provide collision resistance? Is it using a MAC address (like UUID v1/v6) or a custom namespace (like UUID v5), or what? In this case...looking at the code.... It exposes two formats. Format 1: 4 b…

laptop% date -d 'Sep 13 2020 12:26:40Z' +'%s' 1600000000

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.

Re: Sortable Collision-Free UUIDs

#42

Post by chmod775 »

axiosgunnar wrote: post #40
jandrewrogers wrote: post #38

Earlier quoted context omitted.

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 advanta…

I'm curious, what systems were those that generate >10e9 UUIDs/s?

POV: You're AWS and logging every API call.

Just as an example where you could easily reach high ballparks, though I doubt it's that many.

Maybe some some distributed computing applications on server farms otherwise? Certainly not anything that you'd store in a regular database.

Re: Sortable Collision-Free UUIDs

#43

Post by js2 »

ineedasername wrote: post #35
js2 wrote: post #10

I'd advise UUID v6 over this which is at least an RFC 4122 extension. As coded, this isn't UUID compatible other than being 128 bits. http://gh.peabody.io/uuidv6/ Also some recent similar submissions: Timeflake is a 128-bit, roughly-ordered, URL-safe UUID. https://news.ycombinator.com/item?id=25870482 https://github.com/anthonynsimon/timeflake ULIDs: https://news.ycombinator.com/item?id=18768909 Sonyflake: https://ne…

Is there a reason or need to be UUID compatible? I honestly don't know. I use them in databases and know they're pretty safe to use when integrating data across multiple databases because collisions are astronomically unlikely, if implemented properly.

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.

Re: Sortable Collision-Free UUIDs

#44

Post by jandrewrogers »

ineedasername wrote: post #35
js2 wrote: post #10

I'd advise UUID v6 over this which is at least an RFC 4122 extension. As coded, this isn't UUID compatible other than being 128 bits. http://gh.peabody.io/uuidv6/ Also some recent similar submissions: Timeflake is a 128-bit, roughly-ordered, URL-safe UUID. https://news.ycombinator.com/item?id=25870482 https://github.com/anthonynsimon/timeflake ULIDs: https://news.ycombinator.com/item?id=18768909 Sonyflake: https://ne…

Is there a reason or need to be UUID compatible? I honestly don't know. I use them in databases and know they're pretty safe to use when integrating data across multiple databases because collisions are astronomically unlikely, if implemented properly.

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.

Re: Sortable Collision-Free UUIDs

#45

Post by Lazare »

jandrewrogers wrote: post #38
YetAnotherNick wrote: post #29

Earlier quoted context omitted.

Umm.. 12 bytes of randomness has 7*10^28 unique uuid per second. We generally take order of square root of this due to birthday paradox which means that if you generate less than something like 10^10 UUID per second you couldn't get collision.

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 advanta…

There's also the risk of bad randomness sources and/or bugs.

One popular UUID library got a bug report stating: "We are generating about 1M UUID4 a day, and we are getting several hundred collisions a day". And so they were; turned out to be a bug/weird interaction between the OpenSSL library they were using for randomness and forking. (Details here, although it was all fixed years ago of course: https://github.com/ramsey/uuid/issues/80)

On paper, you should never, ever, ever see a collision when generating a mere million v4 UUIDs a day, much less hundreds of collisions. But that doesn't mean it can't happen!

This is also an interesting bit of analysis; comes from a company that processed a lot of UUIDs generated in browsers, checked, and discovered about 5 collisions per million UUIDs. Again, not what you'd naively expect! (Turned out to be mostly driven by misbehaving crawlers.) https://medium.com/teads-engineering/generating-uuids-at-sca...

Re: Sortable Collision-Free UUIDs

#46

Post by jandrewrogers »

axiosgunnar wrote: post #40
jandrewrogers wrote: post #38

Earlier quoted context omitted.

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 advanta…

I'm curious, what systems were those that generate >10e9 UUIDs/s?

Many types of telemetry and sensor data models; vast networks of machines can generate a stupendous quantity of events. UUIDs are not good design choice in these cases but it is a hard requirement for some users for compatibility with legacy systems which require a 128-bit unique identifier for everything.

Another issue with probabilistic UUIDs, possibly more important than collisions, is that they don’t compress very well when stored.

Re: Sortable Collision-Free UUIDs

#47

Post by [deleted] »

Lazare wrote: post #37
YetAnotherNick wrote: post #29

Earlier quoted context omitted.

Umm.. 12 bytes of randomness has 7*10^28 unique uuid per second. We generally take order of square root of this due to birthday paradox which means that if you generate less than something like 10^10 UUID per second you couldn't get collision.

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 wil…

[deleted]

Re: Sortable Collision-Free UUIDs

#49

Post by saurik »

hamandcheese wrote: post #34
joeyh wrote: post #27

Regular old v1 UUIDs contain 60 bits of the system time and are sortable by it, all you need is a uuid library to extract that information from them. Eg, in haskell: ghci> sortOn Data.UUID.Util.extractTime (map (fromJust . Data.UUID.fromString) ["8fca290c-ac63-11eb-9e74-79cdba6ee3eb", "8d543a32-ac63-11eb-9e74-79cdba6ee3eb"]) [8d543a32-ac63-11eb-9e74-79cdba6ee3eb,8fca290c-ac63-11eb-9e74-79cdba6ee3eb]

Not having the leading bits be the timestamp limits the utility, though, because then you don't get sorting "for free" just by having an index on the ID. At least for me, that is the primary appeal of a time-base UUID.

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

Re: Sortable Collision-Free UUIDs

#50

Post by jstrong »

jandrewrogers wrote: post #44
ineedasername wrote: post #35

Earlier quoted context omitted.

Is there a reason or need to be UUID compatible? I honestly don't know. I use them in databases and know they're pretty safe to use when integrating data across multiple databases because collisions are astronomically unlikely, if implemented properly.

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 custo…

I have stored a wide manner of arbitrary data in UUIDs, and had great success with that technique.
Post reply on HN