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

81–90 of 104 posts

Re: Understanding UUIDs, ULIDs and string representations

#81

Post by mikl »

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 one SSD or hard disk — no matter how many servers you have.

There’s maybe a handful of apps in the world that see so much traffic that this would be a problem. Unless you expect to reach Amazon-scale anytime soon, or need distributed ID generation (like generating them in mobile apps or SPAs), just starting with a simple BIGSERIAL (or rather, BIGINT GENERATED BY DEFAULT AS IDENTITY as the state of the art is) will be good enough to get started.

You can always add complexity to your app later. Taking it away once added is much more difficult.

Re: Understanding UUIDs, ULIDs and string representations

#82

Post by halpert »

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.

Re: Understanding UUIDs, ULIDs and string representations

#83

Post by jandrewrogers »

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…

Yes, this was hyperbole. Durably generating tens of millions per second is entirely within the realm of possibility. However, events generated by intentional human action, like buying something or sending a text message, historically maxes out at hundreds of thousands per second.

Re: Understanding UUIDs, ULIDs and string representations

#84

Post by jandrewrogers »

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

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.

Re: Understanding UUIDs, ULIDs and string representations

#85

Post by elevader »

jrochkind1 wrote: post #76
Sjoerd wrote: post #69

Earlier quoted context omitted.

They aren't guessable, except for ULIDs generated by the same process in the same millisecond. To keep chronological order even within the same timestamp, ULIDs within generated within the same millsecond become incremental. This can become relevant for example when an attacker requests a password reset for himself and the victim simultaneously.

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

Re: Understanding UUIDs, ULIDs and string representations

#86

Post by kuratkull »

mrpotato wrote: post #74

> This entire idea of using random IDs assumes that your computers can generate random numbers that are random and unpredictable — this isn't an easy problem, and there's a lot of research being done in the field. Can anyone here provide some hints as to how you can verify that the randomness is actually random? If I was to create some blackbox and I claimed it generated 100% random numbers, is it possible to disprov…

If trickery is the goal then you could for example hash a seed using a strong hash function. Output the hash bytes and feed the hash back in. You have random looking data that should pass statistical tests (dieharder et al).

This question arises with hardware RNGs - could some of them just output random looking data that the dark-powers know the seed of?

Re: Understanding UUIDs, ULIDs and string representations

#87

Post by leetrout »

jandrewrogers wrote: post #84
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.…

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.

I was not aware of this!

Do you have a favorite link for more information on this?

Re: Understanding UUIDs, ULIDs and string representations

#88

Post by noodlesUK »

jandrewrogers wrote: post #84
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.…

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.

Re: Understanding UUIDs, ULIDs and string representations

#89

Post by jandrewrogers »

traceroute66 wrote: post #51
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.…

Beyond the obvious and important security implications of incremental numbers, there is one other major problem with them. They make life hell for database clustering, merges and migrations. In addition, on a more minor level, in a client-centric (apps, browser JS etc) world, the use of incremental numbers is an un-necessary pain point. If you use UUIDs, the client can generate its own without the need to a call back…

This greatly overstates the benefits of UUIDs, and ignores the myriad ways in which they demonstrably have poor properties in real systems. I've worked on several large systems designed around UUIDs at scale that we had to later modify to not use UUIDs due to their manifest issues in practice. And then there is the reality that v3/4/5 UUIDs are expressly prohibited in some application contexts due to their defects and weaknesses.

Also, sequence generators are a non-problem in competent architectures, since you can trivially permute the number such that it is both collision-free and non-reversible (or only reversible with a key).

It is still common to use structured 128-bit keys in very large scale databases, and it is good practice in some cases, but these are not UUIDs because the standardized versions all have problems that can't be ignored. This leads to the case where there are myriad non-standard UUID-like identifiers (in that they are 128-bit) but not interoperable.

Re: Understanding UUIDs, ULIDs and string representations

#90

Post by traceroute66 »

jandrewrogers wrote: post #89
traceroute66 wrote: post #51

Earlier quoted context omitted.

Beyond the obvious and important security implications of incremental numbers, there is one other major problem with them. They make life hell for database clustering, merges and migrations. In addition, on a more minor level, in a client-centric (apps, browser JS etc) world, the use of incremental numbers is an un-necessary pain point. If you use UUIDs, the client can generate its own without the need to a call back…

This greatly overstates the benefits of UUIDs, and ignores the myriad ways in which they demonstrably have poor properties in real systems. I've worked on several large systems designed around UUIDs at scale that we had to later modify to not use UUIDs due to their manifest issues in practice. And then there is the reality that v3/4/5 UUIDs are expressly prohibited in some application contexts due to their defects an…

> I've worked on several large systems designed around UUIDs at scale that we had to later modify to not use UUIDs due to their manifest issues in practice.

As I said in my later comment, let's put the "don't use UUID because high scale" argument to one side, shall we ?

Because per-later comment:

    1) Vast majority of database implementations are not remotely "high scale". Most database implementations could use UUIDs and nobody would ever notice.
    2) "High scale" brings specific environment concerns, not only related to databases
Seeking to bring "high scale" mentality lower down the foodchain only results in people implementing premature optimisation (and vastly overspending on over-complex cloud implementations).
Post reply on HN