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

Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

github.com

Post reply on HN
Print view View original

101–110 of 236 posts

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#101

Post by dralley »

pphysch wrote: post #81
jeremyjh wrote: post #54

Earlier quoted context omitted.

Well UUIDv7 can be consumed as a UUIDv4 in the same way, its just 16 bytes. The point of the standard is to define how the particular bytes are chosen.

The latest standard for v7 does not meaningfully describe how to interpret the last segment. It says they could be pseudorandom and non-monotonic. Or it could be monotonic and non-random. These are completely disjoint cases! "X or not X" is tautological. And there is no way to determine which (e.g. there could be a flag that indicates this mode, but there is not). To be clear, the standard should be amended to resolv…

Postgresql doesn't care, it's not going to "interpret" those bits, it is just a 128-bit integer.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#102

Post by [deleted] »

aartav wrote: post #95

I've been doing this kind of thing for years with two notable differences: 1. I don't believe people actually hand type-in these values, so I'm not really concerned about the 'l' vs '1' issue. I do base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in. 2. I add two base-32 characters as a checksum (salted of course). This is prevents having to go look at the datastore when the valu…

[deleted]

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#103

Post by jeremyjh »

pphysch wrote: post #81
jeremyjh wrote: post #54

Earlier quoted context omitted.

Well UUIDv7 can be consumed as a UUIDv4 in the same way, its just 16 bytes. The point of the standard is to define how the particular bytes are chosen.

The latest standard for v7 does not meaningfully describe how to interpret the last segment. It says they could be pseudorandom and non-monotonic. Or it could be monotonic and non-random. These are completely disjoint cases! "X or not X" is tautological. And there is no way to determine which (e.g. there could be a flag that indicates this mode, but there is not). To be clear, the standard should be amended to resolv…

I think the purpose of the standard is so that different software implementations work the same way, so that once you've picked a standard, you can use it everywhere and know that keys are assigned the same way regardless of which software stack is generating a particular key. Its not so that systems can "interpret" it. Obviously they are your bytes to use however you want if you are rolling your own generator.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#104

Post by Daegalus »

Nelkins wrote: post #77
Daegalus wrote: post #29

Earlier quoted context omitted.

Its been going through drafts and improvements. It's very close to being standardized, and many libraries are supporting it already, or new offerings are being added. For example I maintain the Dart UUID library, and my latest beta major release has v6, v7 and a custom v8. There is a list of them somewhere, I know I get pinged on every new draft by the authors because I am listed as a library maintainer on one of the…

How much does it change between drafts? Close enough to where I could use it in production?

Seeing as how its nearly done, it doesn't change much. It changed more often in the beginning, but its like on its final draft, or near final draft. I think the IETF plans to make final soon.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#105

Post by deathanatos »

jandrewrogers wrote: post #47
ceejayoz wrote: post #41

Earlier quoted context omitted.

Re-read. You'd have to generate 103 trillion to have a one billion th chance of a collision. A billion isn't that big a number, but 103 trillion is.

I think you made a mistake in your math. The Birthday Collision probability of just a trillion random UUID is much higher than that.

Wikipedia is correct, AFAICT.

The probability of 1 trillion UUIDs having a collision is,

  def birthday_collision(n, m):
      return 1 - math.e ** (-((n -1) * n) / (2 * m))

  In : birthday_collision(1_000_000_000_000, 2 ** 122)
  Out: 9.403589018575076e-14
That number is roughly the approximation given in Wikipedia.

I.e., at 1T UUIDs, it hasn't happened. For comparison, the odds of being struck by lighting (over a lifetime) is many orders of magnitude greater:

  6.535947712418301e-05

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#106

Post by michaelt »

sokoloff wrote: post #100
aartav wrote: post #95

I've been doing this kind of thing for years with two notable differences: 1. I don't believe people actually hand type-in these values, so I'm not really concerned about the 'l' vs '1' issue. I do base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in. 2. I add two base-32 characters as a checksum (salted of course). This is prevents having to go look at the datastore when the valu…

> base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in. We had “analrita” as an autogenerated password that resulted in a complaint many years ago. Might consider adding ‘a’ as an excluded letter.

Presumably base 32 means 26 letters + 10 digits - 4 banned letters

So adding an excluded letter is not easy.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#107

Post by Daegalus »

pphysch wrote: post #89
Daegalus wrote: post #40

Earlier quoted context omitted.

I am aware, just saying per spec, its supposed to be random bit data, thats all I was saying. I am familiar with a spec since I maintain a UUID library that has 6,7, and a custom 8 implemented. It can have extra monotonicity data instead, per section 6.2 but ideally its random. Again, Not saying you can't do what you are doing, I just know per the conversations while the draft was gathering feedback, your type of cha…

> per spec, its supposed to be random bit data > It can have extra monotonicity data instead Well, which is it? These are incompatible requirements. If I give you a standard UUIDv7 sample, it is impossible for you to interpret the last 62 bits. You cannot determine how they were generated. If I give you two samples with the same timestamp, you cannot say which was generated first. These bits are de facto uninterpreta…

Well, that might be an ambiguity that needs to be brought up before its final if it is an issue.

So if we look at https://www.ietf.org/archive/id/draft-ietf-uuidrev-rfc4122bi...

For list item #3 it says "Random data for each new UUIDv7 generated for any remaining space." without the word "optional" and the bit layout diagram says `rand_b`

But when you read the description for `rand_b` it says: "The final 62 bits of pseudo-random data to provide uniqueness as per Section 6.8 and/or an optional counter to guarantee additional monotonicity as per Section 6.2."

Reading section 6.2 https://www.ietf.org/archive/id/draft-ietf-uuidrev-rfc4122bi..., it all involves incrementing counters, or other monotonic random data.

If you can guarantee that you custom uuidv7 is globally unique for 10000 values per second or more, I don't see why you can't do what you do and treat your custom data as random outside of your implementation.

I think part of this is my mistake, because I assumed you replaced most of the random data with information, but reading it now, I read that you replaced just the last 16 bits. Also since most people used random data for UUIDv1's remaining 48bits of `node` then your variation is no worse than UUIDv1 (or 6) while also being compatible with v7.

I think I just got too caught up on the the bit layout calling it `random` and misread your information. Sorry for the misunderstanding, and thanks for discussing it.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#108

Post by [deleted] »

ceejayoz wrote: post #33
stronglikedan wrote: post #14

Earlier quoted context omitted.

> combining time + random number You can't guarantee that this will be globally unique.

No identifier can guarantee that. We just get close enough to be acceptable. Per Wikipedia, the probability to find a duplicate within 103 trillion version-4 UUIDs is one in a billion. so-youre-saying-theres-a-chance.gif

[deleted]

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#109

Post by clintonb »

AtNightWeCode wrote: post #25

An important aspect of identifiers is to not leak any information in the identifier. In some scenarios a prefix might be fine but less important things have been blocked by our dpo department.

Requirements depend on the use case. I don’t consider the prefix a “leak” and neither does Stripe.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#110

Post by dloreto »

jtmarmon wrote: post #97

This looks great! Is there a reason one couldn't use this with v4 UUIDs? A quick test shows that they encode/decode just fine. Wondering if I could use the encoded form as a way to niceify our URLs without having to change how the IDs (currently v4 uuids) are stored

The CLI tool will support encoding/decoding any valid UUID, whether v1, v4, or v7. We picked v7 as the definition of the spec, because we need to choose one of them when generating a new random ID, and our opinion is that by default, that should be v7.

We might add a warning in the future if you decode/encode something that is not v7, but if it suits your use-case to encode UUIDv4 in this way, go for it. Just keep in mind that you'll lose the locality property.

Post reply on HN