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

51–60 of 65 posts

Re: Sortable Collision-Free UUIDs

#51

Post by halfmatthalfcat »

cratermoon wrote: post #31
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

Good to know, thanks.

Re: Sortable Collision-Free UUIDs

#52

Post by duxup »

js2 wrote: post #43
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.

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…

That was very interesting, thank you. I didn't realize some uuids were anything other than... unique. A version seems very useful.

Re: Sortable Collision-Free UUIDs

#53

Post by dap »

koolba wrote: post #15
laurent123456 wrote: post #8

I think the issue with a lib like this is that people might use it, thinking they don't need the IDs to be secure... until they need to be. But by then plenty would have been generated, and a lot of code would rely on this sortable property. In fact, I don't see the point of a library like this, it's trying to encode two pieces of information into one string. Why is that? Why not encode geolocation or IP while they'r…

Sortable IDs have pleasant properties on insertion in traditional btree indexes as all the new values are on one edge of the tree. Truly random IDs end up with random I/O on the index tree. With a database like postgres with full page writes enabled, it can blow out quite quickly at scale.

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

Re: Sortable Collision-Free UUIDs

#55

Post by emidln »

I've used something very similar in the past, called SimpleFlake[0], which is essentially a 64 bit version with the same principles. I've used it in Lisp, C, C++, Clojure, Python, and Rust. It's conceptually simple, and fits in a 64bit int, which is natively available in a lot of databases.

[0] SimpleFlake - https://github.com/SawdustSoftware/simpleflake/blob/f2b51f76...

Re: Sortable Collision-Free UUIDs

#56

Post by SPBS »

Given that time-ordered UUIDs are hardly a new concept, it would be nice if the author did a comparison with the current state of the art rather than let such a bland README do the talking.

Re: Sortable Collision-Free UUIDs

#57

Post by Dylan16807 »

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…

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

Are you sure? Fast cryptographic hashes are around one cycle per byte on a recent processor, and slower methods aren't that much slower.

Re: Sortable Collision-Free UUIDs

#58

Post by globular-toast »

I don't get why anyone would need to sort them. Just store a timestamp if you want to sort records by order of creation.

If this was about efficient indexing or something I would get it. But the only justification is "you can run it through sort".

Re: Sortable Collision-Free UUIDs

#59

Post by YetAnotherNick »

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…

Let's do some math. Assume you generate a million UUID per second. The probability of collision in a second is c=1-e^((-10^6)^2/(2*7*10^28))=-7*10^-18. The probability it will collide once in next 10 years is 1 in a billion(seconds in 10 year * c).
Post reply on HN