4 ms·

Fixed Bits of Version 4 UUID (2015)

34 points by susam 3y ago

noduerme 3y ago
I'm sort of curious how the theory that "1" is most likely to be the first digit of a random number applies to this. Does anyone know or can expand on what I'm talking about?
- thewakalix 3y ago
  That's Benford's law, but I don't think it applies here. From Wikipedia: > Benford's Law tends to be most accurate when values are distributed across multiple orders of magnitude, especially if the process generating the numbers is described by a power law (which is common in nature).
  - noduerme 3y ago
    it definitely shows up in 8-bit and 32-bit stuff though, doesn't it? There's just a lot less of those numbers where the leading digit (in decimal) is larger than 3 or so.
    - saghm 3y ago
      Assuming you aren't 0 padding, there are 111 unsigned 8-bit integers beginning with 1 (1, 10-19, and 100-199), 67 beginning with 2 (2, 20-29, and 200-255); all of the other digits appear 11 times (in single-digit form and as the leading digit in the tens place for their "decade") except 0, which appears first only in 0 itself. Unsigned 32-bit integers will have 1, 2, and 3 tied for first with 4 far back in fourth place and 5-9 in even the more distant penultimate position (with 0 still being last). If you're dealing with signed integers, you'll have an even more lopsided distribution in favor of 1 for both 8-bit and 32-bit numbers (assuming you don't count the negative sign). And of course, all of this is assuming base ten; you can make things even more uniform by using binary!
      - noduerme 3y ago
        well yeah, no one would want to argue that a leading '1' wasn't pretty predominant in unpadded binary ;) thank you for the good, concise, starter breakdown of why this is a feature of decimal math.
- immibis 3y ago
  It doesn't apply.
  - noduerme 3y ago
    Isn't it a similar observation, though? I've spent a lot of time thinking about random numbers, and how to pull random booleans out of pseudo-random numbers. No one would ever choose UUIDs to serve as a source of randomness. But the observation that "4" comes out really often in UUIDs is on par with the observation that you can't just take the first digit of a 32-bit unsigned, un-padded random number and expect it to be an equally weighted random between 1 and 9. Right? So doesn't that relate?
    - cowsandmilk 3y ago
      No it isn’t. This is that the standard says you will always have 4 in this position. Distribution of randomness has no involvement.
      - noduerme 3y ago
        oh. So if you always know there's a 4 there and then you can trigger infinite recursion based on that... what's the big insight here?
- phaker 3y ago
  This depends on the distribution, for a uniform distribution all 16 hex digits are equally likely in every position. Also for benford's law to show up you want your data to span several orders of magnitude (so e.g. you have numbers in tens, hundreds and thousands) and for a datapoint to be about as likely to give an n-digit number as a n+1-digit number, not everywhere and not exactly but it needs to dominate over there being ten times times as many of them with each step.
- kevincox 3y ago
  I believe that that theory is about un-padded numbers. It doesn't apply to fixed-length numbers generated in the full range. Because 010 would have a leading 0 rather than a leading 1. Since the first byte of a UUID is random and can be any of the allowed values it has no bias in the first digit.
marcus_holmes 3y ago
I don't get why this is interesting. The RFC for UUID type 4 says the digit "4" must be set on the 14th byte. The loop checks to see if this is the case, and loops if it is. Unsurprisingly the UUID generator returns valid type 4 UUIDs so the loop is infinite. This is like making a blog post called "From Integers to Infinite Loops" and then creating a loop that tests if 1==1. I mean, yes it's an infinite loop, but why is that worth blogging about? PS: I tried commenting this on the actual site as well.
- madsbuch 3y ago
  The question is more why this is HN worthy. The fact that people blog about trivial results should be celebrated. After all, it is blogging.
  - dmvdoug 3y ago
    Indeed. I think one potential cure to what most people here recognized as the enshittification of the internet would be if people just blogged about things that interested them, regardless of whether some third-party thinks the topic(s) merited.
    - adamnaga 3y ago
      [flagged]
  - lolsal 3y ago
    I’ve been using uuids for over a decade and didn’t realize there were fixed bits in version 4. I learned something and am thankful it was posted here. Much more interesting than a lot of other submissions.
- susam 3y ago
  > The RFC for UUID type 4 says the digit "4" must be set on the 14th byte. The loop checks to see if this is the case, and loops if it is. The RFC for UUID type 4 states that bits 48 through 51 (0-based indexing) are set to 4, resulting in the character at position 14 (0-based indexing) of the hyphenated string representation being '4'. Also, this post does a little more than that. It also notes that the version 4 UUIDs we use in software today are variant 10₂ UUIDs. This is quite unsurprising too because the other variants are reserved. There is a second infinite loop in the post that demonstrates this by testing the two bits that represent the variant number. > why is that worth blogging about? Hello! I am the author of this post. This is my weblog, so I log about things that I find interesting here. In this case, the interesting thing for me was not so much that we can make an infinite loop out of a triviality but the triviality itself, i.e., not all bits of variant 10₂ of version 4 UUIDs are random, and then finding the sections in the RFC that define these bits. The infinite loops only serve as demos that there are definitely six bits that are not random. Indeed the infinite loop is just testing whether a version 4 variant 10₂ UUID is a version 4 variant 10₂ UUID and that is bound to be an infinite loop. However, I also wanted to document on my weblog where exactly the version and variant bits are located along with references to the relevant sections of the RFC. That is slightly less trivial than documenting that 1 is 1. I understand this is not going to be interesting to everyone. But this is my weblog, so I don't have to subscribe to others' notion of what is interesting to decide what I must add to my own weblog. I believe a more meaningful question would be whether this post is worthy of HN or not. Well, the moderators and the community determine that by voting with their fingers. In this case, it looks like this post is indeed not too interesting for HN, so I would have agreed with you if that were your point.
secondcoming 3y ago
That's a few minutes I'll never get back. I assumed there was a bug in the spec or something, but no.
unconed 3y ago
UUIDs: awkward, pointless cargo cult. - the dash formatting is meaningless - the only useful variant other than "all random" is "time sortable" and it's only part of uuidV7 - hexadecimal is neither compact nor human friendly
- lolsal 3y ago
  The dashes serve humans eyeballing uuids, not computers. You can remove the uuid in your language of choice and I’m confident it will be able to parse. How are uuids pointless? Hexadecimal is much more human friendly than say, binary.
  - unconed 3y ago
    - The specific divisions of the dashes is meaningless and asymmetrical for legacy reasons - Hexadecimal is bloated compared to other encodings, low entropy per digit, inefficient when e.g. embedded in URLs - Is not memorable for humans, does not use the entire alphabet, and has no redundancy or checksum to detect typoes. Pretty much anything else would be better, and is. Hence, it is a cargo cult. I've never seen a database so unusable as one that was indexed by non sortable uuids. I hate it every time I have to use it. It signals bad taste and is a warning sign to look out for more pointless code drudgery.

34 points by susam 3y ago

I'm sort of curious how the theory that "1" is most likely to be the first digit of a random number applies to this. Does anyone know or can expand on what I'm talking about?

thewakalix 3y ago
That's Benford's law, but I don't think it applies here. From Wikipedia: > Benford's Law tends to be most accurate when values are distributed across multiple orders of magnitude, especially if the process generating the numbers is described by a power law (which is common in nature).
- noduerme 3y ago
  it definitely shows up in 8-bit and 32-bit stuff though, doesn't it? There's just a lot less of those numbers where the leading digit (in decimal) is larger than 3 or so.
  - saghm 3y ago
    Assuming you aren't 0 padding, there are 111 unsigned 8-bit integers beginning with 1 (1, 10-19, and 100-199), 67 beginning with 2 (2, 20-29, and 200-255); all of the other digits appear 11 times (in single-digit form and as the leading digit in the tens place for their "decade") except 0, which appears first only in 0 itself. Unsigned 32-bit integers will have 1, 2, and 3 tied for first with 4 far back in fourth place and 5-9 in even the more distant penultimate position (with 0 still being last). If you're dealing with signed integers, you'll have an even more lopsided distribution in favor of 1 for both 8-bit and 32-bit numbers (assuming you don't count the negative sign). And of course, all of this is assuming base ten; you can make things even more uniform by using binary!
    - noduerme 3y ago
      well yeah, no one would want to argue that a leading '1' wasn't pretty predominant in unpadded binary ;) thank you for the good, concise, starter breakdown of why this is a feature of decimal math.
immibis 3y ago
It doesn't apply.
- noduerme 3y ago
  Isn't it a similar observation, though? I've spent a lot of time thinking about random numbers, and how to pull random booleans out of pseudo-random numbers. No one would ever choose UUIDs to serve as a source of randomness. But the observation that "4" comes out really often in UUIDs is on par with the observation that you can't just take the first digit of a 32-bit unsigned, un-padded random number and expect it to be an equally weighted random between 1 and 9. Right? So doesn't that relate?
  - cowsandmilk 3y ago
    No it isn’t. This is that the standard says you will always have 4 in this position. Distribution of randomness has no involvement.
    - noduerme 3y ago
      oh. So if you always know there's a 4 there and then you can trigger infinite recursion based on that... what's the big insight here?
phaker 3y ago
This depends on the distribution, for a uniform distribution all 16 hex digits are equally likely in every position. Also for benford's law to show up you want your data to span several orders of magnitude (so e.g. you have numbers in tens, hundreds and thousands) and for a datapoint to be about as likely to give an n-digit number as a n+1-digit number, not everywhere and not exactly but it needs to dominate over there being ten times times as many of them with each step.
kevincox 3y ago
I believe that that theory is about un-padded numbers. It doesn't apply to fixed-length numbers generated in the full range. Because 010 would have a leading 0 rather than a leading 1. Since the first byte of a UUID is random and can be any of the allowed values it has no bias in the first digit.

marcus_holmes 3y ago

I don't get why this is interesting. The RFC for UUID type 4 says the digit "4" must be set on the 14th byte. The loop checks to see if this is the case, and loops if it is. Unsurprisingly the UUID generator returns valid type 4 UUIDs so the loop is infinite. This is like making a blog post called "From Integers to Infinite Loops" and then creating a loop that tests if 1==1. I mean, yes it's an infinite loop, but why is that worth blogging about? PS: I tried commenting this on the actual site as well.

madsbuch 3y ago
The question is more why this is HN worthy. The fact that people blog about trivial results should be celebrated. After all, it is blogging.
- dmvdoug 3y ago
  Indeed. I think one potential cure to what most people here recognized as the enshittification of the internet would be if people just blogged about things that interested them, regardless of whether some third-party thinks the topic(s) merited.
  - adamnaga 3y ago
    [flagged]
- lolsal 3y ago
  I’ve been using uuids for over a decade and didn’t realize there were fixed bits in version 4. I learned something and am thankful it was posted here. Much more interesting than a lot of other submissions.
susam 3y ago
> The RFC for UUID type 4 says the digit "4" must be set on the 14th byte. The loop checks to see if this is the case, and loops if it is. The RFC for UUID type 4 states that bits 48 through 51 (0-based indexing) are set to 4, resulting in the character at position 14 (0-based indexing) of the hyphenated string representation being '4'. Also, this post does a little more than that. It also notes that the version 4 UUIDs we use in software today are variant 10₂ UUIDs. This is quite unsurprising too because the other variants are reserved. There is a second infinite loop in the post that demonstrates this by testing the two bits that represent the variant number. > why is that worth blogging about? Hello! I am the author of this post. This is my weblog, so I log about things that I find interesting here. In this case, the interesting thing for me was not so much that we can make an infinite loop out of a triviality but the triviality itself, i.e., not all bits of variant 10₂ of version 4 UUIDs are random, and then finding the sections in the RFC that define these bits. The infinite loops only serve as demos that there are definitely six bits that are not random. Indeed the infinite loop is just testing whether a version 4 variant 10₂ UUID is a version 4 variant 10₂ UUID and that is bound to be an infinite loop. However, I also wanted to document on my weblog where exactly the version and variant bits are located along with references to the relevant sections of the RFC. That is slightly less trivial than documenting that 1 is 1. I understand this is not going to be interesting to everyone. But this is my weblog, so I don't have to subscribe to others' notion of what is interesting to decide what I must add to my own weblog. I believe a more meaningful question would be whether this post is worthy of HN or not. Well, the moderators and the community determine that by voting with their fingers. In this case, it looks like this post is indeed not too interesting for HN, so I would have agreed with you if that were your point.

secondcoming 3y ago

That's a few minutes I'll never get back. I assumed there was a bug in the spec or something, but no.

unconed 3y ago

UUIDs: awkward, pointless cargo cult. - the dash formatting is meaningless - the only useful variant other than "all random" is "time sortable" and it's only part of uuidV7 - hexadecimal is neither compact nor human friendly

lolsal 3y ago
The dashes serve humans eyeballing uuids, not computers. You can remove the uuid in your language of choice and I’m confident it will be able to parse. How are uuids pointless? Hexadecimal is much more human friendly than say, binary.
- unconed 3y ago
  - The specific divisions of the dashes is meaningless and asymmetrical for legacy reasons - Hexadecimal is bloated compared to other encodings, low entropy per digit, inefficient when e.g. embedded in URLs - Is not memorable for humans, does not use the entire alphabet, and has no redundancy or checksum to detect typoes. Pretty much anything else would be better, and is. Hence, it is a cargo cult. I've never seen a database so unusable as one that was indexed by non sortable uuids. I hate it every time I have to use it. It signals bad taste and is a warning sign to look out for more pointless code drudgery.