Discussion: Variable Length UUIDs | UUID Long

[kyzer-davis]

All things Variable Length UUIDs!

Biggest Question up front: Should this be in scope for this RFC Draft?

If so as per @broofa

• If a UUID is larger than 16 bytes, how is it padded?
• ... what are the extra bits / bytes used for?
• ... can a UUID have a fractional-byte length? (e.g. 173 bits) ... how would that be parsed?
• What does the string-form of a non-standard length UUID look like? a.k.a "Where do the hyphens go?"
• What does it mean for a uuid to have length < 16 bytes?
• As an implementor, when scanning a UUID field, how do I know how many bytes/bits to read? I.e. how does a UUID indicate it's length? This is important, if for no other reason than to know where the next field in the data starts.
• What does variable field length imply for other, existing RFC versions? "Why can't those now be longer?"

[peterbourgon]

I think the more common name for "variable-length UUID" is "string" :)

[kyzer-davis]

Throwing my 2 cents in:

• During research of existing and legacy unique ID implementations I dove into this topic. Here is a copy of my summary from the research doc on this same repo.

Length

Q: Are we sticking with 128-bits or are we introducing variable-length.

• The most common implementations utilize 128 bits for globally unique values. This should be kept for backwards compatibility.
• Where required, to best optimize database sizes, 64 bits is the second most common and provide a level of uniqueness sufficient to a specific applications context.
• Many articles exist on the general topic of "how long should an ID be to guarantee uniqueness" most agree that 128 is great, 64 is just as good if you only require uniqueness in the application context.
• Larger than 128 bits is not required from a collision avoidance perspective and adds extra unneeded data to the application/database/wire/etc

Sources:

• https://www.slideshare.net/davegardnerisme/unique-id-generation-in-distributed-systems
• https://medium.com/javascript-in-plain-english/you-might-not-need-uuid-v4-for-generating-random-identifiers-89e8a28a7d77
• https://towardsdatascience.com/are-uuids-really-unique-57eb80fc2a87
• https://www.percona.com/blog/2019/11/22/uuids-are-popular-but-bad-for-performance-lets-discuss/
• https://eager.io/blog/how-long-does-an-id-need-to-be/?hn

[broofa]

Should this be in scope for this RFC Draft?

No. Not enough real-world use cases, evidence of need, or experience among contributors to merit including this.

[bradleypeabody]

I think the more common name for "variable-length UUID" is "string" :)

Agreed. But this is also kind of the whole point, see next.

Not enough real-world use cases

Let's break it down like this: We're making a new UUID spec. One of the whole points of this is to make it useful for database identifiers. I'm hoping that we will see things such as SQL statements like INSERT INTO ... VALUES ( NewUUID7(), ...) (or their crazy NoSQL or whatever language equivalent) - where databases will eventually add native support with functions etc. This was the original problem that drove the UUIDv6 idea in the first place.

So the question becomes: is there a use for case for supporting NewUUID7(20) (instead of the default which would use 16 bytes/128 bits). To me, that's one of the main things we're trying to answer with this.

Larger than 128 bits is not required from a collision avoidance perspective and adds extra unneeded data to the application/database/wire/etc

If this is really the case and it's not needed, then fine, maybe it's a moot point. I admittedly haven't studied the collision probabilities carefully enough to have a firm opinion on it. But I just don't see how we can say that one degree of collision resistance is "good enough for everyone", that's the point I'm stuck on. Maybe an idea here would be to get a list put together of collision probabilities at various lengths. I still don't know how to convert "1 in (some huge number)" into "good enough for most applications" - I'm open to ideas on how to evaluate this.

The other questions brought up, while valid, do have straightforward answers:

If a UUID is larger than 16 bytes, how is it padded?

It's not, the thing holding the value is responsible for knowing it's length.

... what are the extra bits / bytes used for?

Entropy/collision resistance

... can a UUID have a fractional-byte length? (e.g. 173 bits) ... how would that be parsed?

No. Just like lengths in most systems are specified in bytes, we would limit to byte-aligned lengths.

What does the string-form of a non-standard length UUID look like? a.k.a "Where do the hyphens go?"

Add one more hyphen after the 16th byte and then no more in the ensuing digits.

What does it mean for a uuid to have length < 16 bytes?

It's just a shorter form with less entropy. I'm not stuck on this one, if we added the ability to make longer UUIDs but not shorter ones, that would at least handle the "is this enough entropy" concern, which is the primary one.

As an implementor, when scanning a UUID field, how do I know how many bytes/bits to read? I.e. how does a UUID indicate it's length? This is important, if for no other reason than to know where the next field in the data starts.

It depends on protocol using the UUID. If there is an existing protocol/format which expects to transmit a UUID as exactly 16 bytes well than yeah that's not going to work with variable length. But a lot of transports already have a separate encoding mechanism for the length. (I.e. if it's in a field in the database then the database already keeps track of how many bytes that field is, since it would be a string or a blob - JSON has delimiters, msgpack has a length number, and so on) So again, I understand why some applications wouldn't need or want variable length UUIDs and couldn't use them. But is there really a reason to explicitly make NewUUID(20) "invalid"? - even though databases could easily handle this because they have a means of storing the length outside of the actual value.

What does variable field length imply for other, existing RFC versions? "Why can't those now be longer?"

Not our problem. RFC4122 is fixed length and that's fine. UUIDv8 allows people to do whatever they want. I think there is enough flexibility here for people to do what they need. If someone needs some specific variable length UUID that isn't UUIDv7, they just use UUIDv8.

[LiosK]

+1 to the opinions that the variable length stuff should NOT be in scope for the new RFC. But if it were:

• Limit the length options with sufficient intervals in between (say, 160, 192, 256 bits, etc.). With this constraint, a decoder will be able to determine the byte length from the number of characters of textual representation in any potential encodings (e.g. base 32, 58, 62, 64, etc.) that the UUID standard might utilize in the future. This will address the padding issue of such binary-to-text encodings.
• Reserve the first bit of extension field for future extendability. There can be a strong need in the future to "tag" or describe the structure of extension field (e.g. length, role, namespace, etc.). Such a need is not obvious right now, but we can just require to set the first bit to '0' and allow future spec authors to define another variant that starts with '10'. This is exactly the same argument as the var field expansion.

I don't think the shorter UUID is feasible. Short ID implementations usually utilize application-specific shared knowledge to ensure the uniqueness, while the UUID specs are not designed so. It is unlikely possible to ensure practical collision resistance by simply shortening the 128-bit UUID versions.

UUID is not an all-in-one ID standard but just a universally unique ID standard; it will be just confusing to include a spec that will never be universally unique.

---

IMO, the longer UUID spec is not necessary until 128-bit length is proven to be insufficient and many applications seek for longer IDs. At that time a new standard will be necessary to coordinate many applications and libraries, but in the meantime, an application, if concerned about collisions, can simply extend UUID on their own, for example, by utilizing the following struct:

struct MyUniqueId {
  uint8_t uuid[16];
  uint8_t ext_entropy[8];
  uint8_t machine_id[8];
};

I have never seen this kind of approach employed to append extra entropy, but I think it is often common to add a type or namespace tag at the application level to discriminate UUIDs (e.g. user/xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx and item/xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx). Therefore, I think the new RFC can discuss this kind of approach for those who need extra collision resistance, instead of specifying a variable length UUID standard.

It would be valuable if the new RFC includes a section that identifies the source of collision resistance and its limitations and suggests the possible approaches to mitigate such limitations.

[fabiolimace]

I am of the opinion that the variable length UUID should be out of scope.

@LiosK, I couldn’t agree with you more.

[bradleypeabody]

Understood on the above points, and that a fair number of people dislike this idea.

How about this as an approach that would significantly simply the whole thing and both remove variable length from the scope of UUID implementations, but also provide guidance to those applications that absolutely must have more entropy because 128 bits is not enough. How about this text such as this for spec:

UUID as a Source of Opaque Bytes or Strings

For many applications, UUIDs are treated as an opaque (i.e. never parsed) sequences of bytes. Or the text form is used as an opaque string of characters. The purpose being solely to uniquely identify a resource, and its exact form is not otherwise relevant.

In these cases, if an application wishes to emit longer random byte sequences or strings in order to add more entropy, there is nothing stopping them from doing so. Such outputs are not covered by this specification, and as such, library and application implementors are not obligated to support them.

If used, applications should take care not to call such values "UUIDs" as they are not. E.g. the more generic term "ID" or simply "unique string" would be more appropriate.

---

In this way, nobody reading the spec and trying to implement a UUID library is obligated to anything with this at all. UUIDs are not variable length. Parsers (which I believe should be minimal anyway) don't have to deal with it if they don't want to, and so on. However, for those people are who are like "No you don't understand, I absolutely must have more entropy for my application and I don't want to invent something new", they can just turn the UUID generator into a generator for whatever length they want. This handles my concern and I removes the complexity that would have been added if "variable length" were specified as a feature. It also means that a database implementor could make something like "NewID(20)" work and output something in the form of UUIDv7 plus more bytes, if they felt it necessary and they wouldn't have a "non-standard implementation", they are just doing what the above section says.

[broofa]

@bradleypeabody Such verbiage serves no purpose other than to confuse things. It's just saying that UUIDs can be embedded as part of a larger data structure and that such data structures should not be considered UUIDs.

This has always been the case. I think it's generally understood that all standards can be (ab)used in this way should implementors choose to do so. There's no need to encourage it by actually talking about it.

If we're going to say longer-form UUIDs are out of scope we should just omit all discussion of them. [Edit: ... other than to say, "Longer UUIDs were considered by the authors but were not deemed to be worth addressing at this time."]

[bradleypeabody]

Such verbiage serves no purpose other than to confuse things.

This question of "so I'm implementing a 'make me an ID function, what should I do?' is quite literally the use case that drove this project in the first place.

And on this same line, "Should we allow longer IDs for applications that need more entropy/collision resistance" is a very relevant question that has come up many, many times. Here on GitHub and also in prior discussions on the IETF mailing list (if someone is interested I can try to go dig up the links to these things).

You will notice there is an overarching theme to the current draft where concerns that are only applicable in certain cases were removed from the actual specification and instead turned into a short section to discuss the topic, as guidance to the implementor. In my mind this falls into that category. Even if longer values are "not a UUID", it is still a relevant concern to people reading the document. Because the goal is not just to "make a new UUID format", but also to answer the question "how should I generate unique IDs in a distributed environment".

I doubt I will be able to convince you personally of the importance of this, but hopefully the above makes it clear that this subject is in fact relevant to other use cases and users. And considering it adds no implementation requirements, and clearly addresses a concern that I've been asked about easily a dozen time in the course of doing all this, I think it's relevant enough to include.

If you have ideas of how to improve the wording, suggestions are welcome.

[ben221199]

Seems to me that if you talk about UUID, you talk about 128 bits. Imagine the work is needed to update all that software that just made an 128 bit field. Also for me, variable-length UUID is out of scope. I you want a UUID with variable length, it would be better to create a new type of identifier. For example, lets introduce the UOID (Universal Object ID). Everyone talking about UUID knows about 128 bits and everybody talking about UOID knows that it follows a different standard that could possibly have a variable-length version.

[broofa]

@bradleypeabody My concern is that we risk sending a mixed message. For example, in the proposed text you say:

applications should take care not to call such values "UUIDs" as they are not

... which I agree with 100%. But your explanatory text seems to suggest otherwise (emphasis mine):

It also means that a database implementor could make something like "NewID(20)" work and output something in the form of UUIDv7 plus more bytes, if they felt it necessary and they wouldn't have a "non-standard implementation", they are just doing what the above section says.

A UUID is 128 bits. If an ID is longer or shorter, or composed in way that does not comply with the specification, it should not be considered standard, or even "not non-standard".

an overarching theme to the current draft where concerns ... turned into a short section to discuss the topic

I actually quite like this section. Nor am I averse to addressing the "should IDs be longer" topic there. As you say, they're a much-discussed topic. I just think it should be done in a way that is unambiguous about the fact longer ids are not part of this standard.

suggestions

"Since you asked..." 😄

Longer UUIDs, Composition With Other Data

There has been much debate on the utility of longer forms of ids that provide additional uniqueness guarantees, or that allow for encoding additional information. Such ids are deliberately not addressed by this specification, as it is felt the requirements are too specialized to be effectively addressed at this time.

That said, no prohibition is made that prevents applications from using a longer form of ID that combines a UUID with other data. Such constructs should be considered non-standard, however, and care should be taken not to refer to them as "UUIDs". In such cases, applications are encouraged to use a more generic term such as "ID" or "unique string", or invent a new term so as to avoid confusion with standard, 128-bit UUIDs.