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

31–40 of 65 posts

Re: Sortable Collision-Free UUIDs

#31

Post by cratermoon »

halfmatthalfcat wrote: post #11

I started looking into TSID/KSUID/ULID in order to support cursor based pagination schemes in GraphQL against non-integer based unique id fields (such as uuids or unique string ids). A couple of notable Java libs: https://github.com/f4b6a3/ulid-creator https://github.com/f4b6a3/tsid-creator https://github.com/akhawaja/ksuid

Please don't use the akhawaja ksuid generator for Java unchanged. We used it at my last job until we realized 1. the Base62 code is not thread-safe (it uses a static StringBuilder) and more importantly 2. The epoch used is different from the standard, so the generated ksuid aren't portable.

Use https://github.com/ksuid/ksuid insteads

Re: Sortable Collision-Free UUIDs

#32

Post by zoltar »

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

Re: Sortable Collision-Free UUIDs

#33

Post by kpdemetriou »

Hi everyone, OP here. Let me offer some background. fuuids are designed to be sortable and collision-free (for most practical purposes, details below) IDs within a 16-byte footprint making them interpretable as UUIDs.

Lazare very helpfully detailed the internals of the two available formats but I'll summarize them here and I'm happy to answer any questions:

Format A (fuuid) consists of a 4-byte second timestamp concatenated with a 12-byte random tag.

Format B (fuuid_ns) consists of an 8-byte nanosecond timestamp concatenated with an 8-byte random tag.

As far as collision resistance is concerned, here's a list of probabilities at various production rates for Format A. Collisions for Format B are only relevant when the production rate begins to approach 10^9 IDs per second (assuming IDs are produced uniformly in time).

- 2^-90.51 at 10 IDs/second

- 2^-83.73 at 100 IDs/second

- 2^-77.07 at 1,000 IDs/second

- 2^-70.42 at 10,000 IDs/second

- 2^-63.78 at 100,000 IDs/second

- 2^-57.14 at 1,000,000 IDs/second

Hope this helps!

Re: Sortable Collision-Free UUIDs

#34

Post by hamandcheese »

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.

Re: Sortable Collision-Free UUIDs

#35

Post by ineedasername »

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.

Re: Sortable Collision-Free UUIDs

#36

Post by hamandcheese »

pkulak wrote: post #4

Are they sortable as a string or as binary? Once you deploy something like this, that becomes important because you'll end up storing binary and string representations in different spots, unless you're _really_ careful (and DBs can insert way faster if you're always doing so near the end of the primary key sorting). And unless you use a totally custom string function, you can't have both, since base64 has letters bef…

I think if you store as hex, which is the traditional string representation of a UUID, then the string and binary representation will sort identically.

Re: Sortable Collision-Free UUIDs

#37

Post by Lazare »

YetAnotherNick wrote: post #29
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…

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

Re: Sortable Collision-Free UUIDs

#38

Post by jandrewrogers »

YetAnotherNick wrote: post #29
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…

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

Re: Sortable Collision-Free UUIDs

#39

Post by chmod775 »

YetAnotherNick wrote: post #29
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…

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.

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

Re: Sortable Collision-Free UUIDs

#40

Post by axiosgunnar »

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…

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