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

Understanding UUIDs, ULIDs and string representations

sudhir.io

Post reply on HN
Print view View original

91–100 of 104 posts

Re: Understanding UUIDs, ULIDs and string representations

#91

Post by jandrewrogers »

noodlesUK wrote: post #88
jandrewrogers wrote: post #84

Earlier quoted context omitted.

This is often dealt with trivially using collision-free hashing. It exports a number in the same domain as the sequence (i.e. 64-bit sequence -> 64-bit id) but is not reversible and is guaranteed to be unique.

This is true with identifiers which are already random, but unless you’re doing something like keyed hashing, a naive implementation of say SHA256(predictable_id) isn’t going to solve this problem against a determined attacker, but I’d like to learn a bit more about what you’re discussing here.

For example, running the sequence generator through AES rounds. This is keyed, very fast if the hardware supports it, and permutations of types smaller than the block size are collision-free and non-reversible[0] if the AES block is setup suitably.

In other cases, a 128-bit key is simply encrypted (conveniently being the same block size as AES), which allows you to put arbitrary structure inside the exported key.

[0] http://www.jandrewrogers.com/2019/02/12/fast-perfect-hashing...

Re: Understanding UUIDs, ULIDs and string representations

#92

Post by layer8 »

elevader wrote: post #85
jrochkind1 wrote: post #76

Earlier quoted context omitted.

Interesting, I learned about ULIDs for the first time from this article, which says: "The remaining 80 bits [in a ULID] are available for randomness", which I read as saying those last 80 (non-timestamp) bytes were random, not incremental. But this was misleading/I got the wrong idea? Going to the spec [1]... Yeah, that's weird. The spec calls those 80 bytes "randomness", and apparently you are meant to generate a ra…

From what I gather this is done to persist the sort order. All calls within the same millisecond will get the same timestamp component so that can't be used to sort the ULIDs. So the "random" part is incremented and the resulting ULIDs can still be sorted by the order of function calls. This wouldn't be possible if the random part were truly random. I'm not sure this is a good idea but that is what I understood from…

It’s not clear why they don’t just use a finer-grained timestamp component (e.g. nanoseconds) and increase that number if two events are within the same clock interval, and keep the random component random.

Re: Understanding UUIDs, ULIDs and string representations

#93

Post by elevader »

layer8 wrote: post #92
elevader wrote: post #85

Earlier quoted context omitted.

From what I gather this is done to persist the sort order. All calls within the same millisecond will get the same timestamp component so that can't be used to sort the ULIDs. So the "random" part is incremented and the resulting ULIDs can still be sorted by the order of function calls. This wouldn't be possible if the random part were truly random. I'm not sure this is a good idea but that is what I understood from…

It’s not clear why they don’t just use a finer-grained timestamp component (e.g. nanoseconds) and increase that number if two events are within the same clock interval, and keep the random component random.

The reference implementation is written in Javascript and I don't think that provides a reliable way to get timestamps this fine grained.

Re: Understanding UUIDs, ULIDs and string representations

#94

Post by WorldMaker »

xyzzy_plugh wrote: post #66
hderms wrote: post #61

Earlier quoted context omitted.

Is it really true that concerns around UUIDs as primary keys are wholly irrelevant? Maybe I'm working off outdated information but in high scale environments there are a lot of downsides primarily related to the random write patterns into B-trees causing page splitting and things like that.

You're right that random unordered writes are worst case for an indexed (ordered) key. ULID and ordered UUIDs (v6+) help solve this. For dimensions, UUIDs are usually fine since writes are infrequent. For facts or timeseries data, ordered IDs are more efficient.

Yes, ordered UUIDs help solve this. The unfortunate deep dive rabbit hole here is how UUIDs are sorted in different databases and making sure your UUID generation matches that.

One fun for instance I worked directly with: Microsoft's SQL Server made some interesting assumptions based on UUID v1 and sorts the last six bytes first. In UUIDv1 those would have been the MAC addresses and clustering by originating machine first has some sort of sense to it in terms of ordered writes. The ULID timestamp is coincidentally also six bytes (48 bits) so (ignoring the Endian issues of the other "fields" in the UUID) you can get Microsoft's SQL Server to order UUIDs in mostly the same way as their ULID representation by just transposing the first six bytes to be the last six bytes.

Unfortunately UUID v6+ won't sort well in Microsoft SQL Server's sort order today.

Other databases will vary on what you need to do to get sortable UUIDs.

A reference to me on all of this deep rabbit hole was Raymond Chen's blog on the many GUID/UUID sort orders just in Microsoft products: https://devblogs.microsoft.com/oldnewthing/20190426-00/?p=10...

(With the fun punchline at the bottom being the link to the Java sort order. My sympathies to anyone trying to sort UUIDs in an Oracle database.)

Re: Understanding UUIDs, ULIDs and string representations

#95

Post by AtlasBarfed »

mikl wrote: post #81

The whole section on serial number IDs is a bit FUDy in my opinion, especially this: > If you suddenly have a million people who want to buy things on your store, you can't ask them to wait because your sequence generator can't number their order line items fast enough. And because a sequence must store each number to disk before giving it out, your entire system is bottle-necked by the speed of rewriting a number on…

Sequence numbers don't scale to distributed databases and distributed data creation though.

"Handful" is wrong. Any major system will start to run into this as soon as you start saying the word "scale" in design meetings.

UUIDs can also provide room for encoding other information, like the type of the object, where it was created, etc, since MAC address is often integrated in the UUID.

Re: Understanding UUIDs, ULIDs and string representations

#96

Post by donarb »

atoav wrote: post #24
gorgoiler wrote: post #20

All this stuff about collisions and avoiding them, even though they will never happen, feels like a PHB compliance issue. “Great work Geoff! One question: what’s the probability of two transactions having the same ID?” “It is very low” “Hmmm. But it’s not zero?” “It’s so low that it practically is zero.” “But it’s not technically zero? This company wasn’t built on taking chances, son! Come back when your product comp…

This is when any tech person worth their salt should lean over and say: "Okay boss, we _could_ do that, but so you know what that would mean?" And then you tell them about cosmic rays, bitflips and redundant computing and what that would mean for the cost of IT at your company. "... or, we could just use UUIDs like nearly everybody else. I will spend a few days thinking about what would happen in case of a UUID colli…

During the Boeing 737 Max software fix, the FAA required Boeing engineers to make the system handle 5 simultaneous cosmic bit flips.

https://www.seattletimes.com/business/boeing-aerospace/newly...

Re: Understanding UUIDs, ULIDs and string representations

#97

Post by WorldMaker »

elevader wrote: post #93
layer8 wrote: post #92

Earlier quoted context omitted.

It’s not clear why they don’t just use a finer-grained timestamp component (e.g. nanoseconds) and increase that number if two events are within the same clock interval, and keep the random component random.

The reference implementation is written in Javascript and I don't think that provides a reliable way to get timestamps this fine grained.

Also, the spec notes there is an entropy trade off in using more bits for the time stamp. More timestamp bits is fewer random bits, because ULIDs constrained themselves to a combined total 128 bits (to match GUID/UUID width).

Re: Understanding UUIDs, ULIDs and string representations

#98

Post by mikl »

AtlasBarfed wrote: post #95
mikl wrote: post #81

The whole section on serial number IDs is a bit FUDy in my opinion, especially this: > If you suddenly have a million people who want to buy things on your store, you can't ask them to wait because your sequence generator can't number their order line items fast enough. And because a sequence must store each number to disk before giving it out, your entire system is bottle-necked by the speed of rewriting a number on…

Sequence numbers don't scale to distributed databases and distributed data creation though. "Handful" is wrong. Any major system will start to run into this as soon as you start saying the word "scale" in design meetings. UUIDs can also provide room for encoding other information, like the type of the object, where it was created, etc, since MAC address is often integrated in the UUID.

“Handful” is referring to cases where “your sequence generator can't number their order line items fast enough” is true. And I stand by that.

And if you want “other information”, good database design would put that other information in a column of its own.

Distributed databases have their place. But the tradeoffs they bring are often not worth it for your 1.0/MVP app.

Re: Understanding UUIDs, ULIDs and string representations

#99

Post by vyrotek »

justinholmes wrote: post #46
elevader wrote: post #25

I really liked this article but I feel it misses one somewhat important point about using incremental numbers: They are trivially guessable and one needs to be very cautious when exposing them to the outside world. If you encounter some URL like https://fancy.page/users/15 chances are that the 15 is a numeric ID and 1 to 14 also exist. And the lower numbers tend to be admin accounts as they are usually created first.…

Using https://hashids.org is sensible for mapping to external ID.

I recently learned about this. We're thinking of using them with our project really soon. Are there any gotchas to be aware of with it?

Re: Understanding UUIDs, ULIDs and string representations

#100

Post by mikl »

halpert wrote: post #82
mikl wrote: post #81

The whole section on serial number IDs is a bit FUDy in my opinion, especially this: > If you suddenly have a million people who want to buy things on your store, you can't ask them to wait because your sequence generator can't number their order line items fast enough. And because a sequence must store each number to disk before giving it out, your entire system is bottle-necked by the speed of rewriting a number on…

UUIDs aren’t particularly complex. In a lot of ways, they’re more convenient than using an auto-incrementing identifier. For instance, if you’re using DynamoDB, getting an incrementing integer is way more complicated than a random UUID.

Well, they do have opportunities for screw-ups. We recently had some bad data loss issues because part of an application was using a buggy UUID generator that produced lots of collisions. If you google for UUID collision bugs, its not an uncommon occurrence.

Besides, UUIDs have fragmentation issues. I’d use ULID if I had need to generate IDs in a distributed fashion.

Post reply on HN