Live data from Hacker News

Sortable Collision-Free UUIDs

github.com

21–30 of 65 posts

Re: Sortable Collision-Free UUIDs

#21
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…

The examples use both letters and numbers in the ID composition so I would guess not - in all honesty though your question needs some clarification because the string representation of UUIDs is pretty fluid - there's the generally expressed version like `01324332-f66a-054a-76e4-fbdc7f772cd1` which appears to be what this generator favors - but for indexing UUIDs are usually considered to be their binary values so it's highly unlikely that a DB would see anything beyond a coincidental marginal benefit from using this package.

It's hard to tell since the package says "sortable using UNIX sort" so it's not a format agnostic sorter - but it's also not conclusive whether the author meant the common human-readable strings can be sorted using UNIX sort or the binary strings can be sorted using UNIX sort.

Re: Sortable Collision-Free UUIDs

#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 bytes to store the number of seconds since a custom epoch of... Sep 13 2020 12:26:40, and 12 bytes of randomness. Puzzling choice.

Format 2: 8 bytes to store the number of nanoseconds since the same custom epoch, and 8 bytes of randomness.

And the collision resistance...doesn't exist at all; it's just relying on 12 (or 8) bytes of randomness and a time prefix. Which seems like it'll be totally fine in practice, but if you actually care about collisions (and in my experience, almost everyone who thinks they do really doesn't), this is unlikely to be an optimal choice.

Functionally, I think this is closest to KSUIDs (https://github.com/segmentio/ksuid) which are also the result of combining a timestamp (with a custom epoch) and some randomness, and then concatenating them in a way which is not a valid UUID, will work efficiently as a DB index, and is extremely unlikely to collide. But KSUIDs are much more widely adopted and better documented.

Re: Sortable Collision-Free UUIDs

#24
post #15

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.

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

Re: Sortable Collision-Free UUIDs

#25
OT: Github READMEs have got to the point where they don't say what it actually does, how it does it, things you can depend on or not. They are now QUICKSTART.md. With the dependency insecurities going around, why would anyone think this is okay?

Re: Sortable Collision-Free UUIDs

#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]

Re: Sortable Collision-Free UUIDs

#29
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.
Post reply on HN