Re: UUID version 6 proposal, initial feedback

[Brad Peabody <[e-mail]>]

The primary motivation for compatibility is that there is a lot of existing software that expects to parse a UUID as:

NNNNNNNN-NNNN-NNNN-NNNN-NNNNNNNNNNNN

And store it as:

byte[16]

Examples:

https://github.com/s-u/uuid/blob/master/src/uuid.h <https://github.com/s-u/uuid/blob/master/src/uuid.h>
https://docs.oracle.com/javase/6/docs/api/java/util/UUID.html <https://docs.oracle.com/javase/6/docs/api/java/util/UUID.html>
https://docs.python.org/3/library/uuid.html <https://docs.python.org/3/library/uuid.html>

The binary form is more compact, especially when compared to hex.   It seems reasonable to me that applications should be able to continue to parse a text UUID and store it in it’s most compact form in memory or on disk.    An opaque string is useful in a lot of cases, but I think it’s also totally possible and useful to support a standard text format so programs can get at the raw data for space-saving concerns.

That said, I do want to make sure I understand the alternatives.  Are you thinking that maybe the clock resolution should be lowered (100-ns resolution is not needed for index locality) and then the additional bits can be used for randomness?  (Indeed this is the approached used by some of the projects linked to in the message from Tony Finch.)

If so, my only concern is that the ability to use the timestamp as a creation time is useful for some applications.

One idea would be to introduce two new versions, one with the extractable and high-resolution timestamp, one with a lower resolution time focused on providing as many random bits as possible.  Both with the improved text formats (base64 and base32) and variable length additions mentioned previously.  What do you think about that?


> On Jul 4, 2018, at 2:40 AM, Martin Thomson <[e-mail]> wrote:
> 
> Still not sure that I understand the compatibility motivation.  Unless
> you are trying to fill pre-existing fields that only accept UUID, then
> an text or octet string key is superior in almost every way to a UUID.
> 
> I appreciate the value of locality of reference (assuming null
> hashing, contiguous or near-contiguous keys would end up in close
> proximity), but that's better served by text or octet string as well.
> When you consider birthday paradox and the need for global uniqueness,
> the 120 bits you have available to you needs to be spent mostly on
> randomness unless your database is so small as to make this effort
> essentially more academic than useful.
> On Wed, Jul 4, 2018 at 6:52 PM Brad Peabody <[e-mail]> wrote:
>> 
>> Thanks Martin,
>> 
>> Those are really good points and I agree.
>> 
>> I’m a bit concerned about moving entirely away from the existing format, as I think there are some useful properties - particularly the ability to extract the time stamp. Also by producing newer versions of UUIDs that are the same size and layout a lot of existing software will continue to work (for example, Cassandra understands UUIDs and works with my prototype “version 6” UUIDs without any modification).
>> 
>> But the points you bring up are quite relevant.  I’m not sure how to address the clock skew leakage that might occur, but definitely the counters and MAC address can go the way of the buffalo. Simply reading from /dev/urandom, et al makes so much more sense these days.
>> 
>> I think there is also real potential in the idea of making them variable length.  If you need compatibility with existing UUID schemes you can use the 128 bit length, but you can also go longer if you require more guarantee of uniqueness or un-guess-ability.
>> 
>> The only other thing that has me pondering on this is how important is the property of being able to tell “is this a valid UUID, and if so what type”.  If we don’t care about this, then it might make sense to have two additional formats - a base64 which is as compact as reasonably possible while still being ASCII, and a base32 which is case-insensitive - they both have merit depending on the use case.  But then add the fact that it’s variable length and it becomes impossible to distinguish the format reliably (i.e you might read the base32 value as base64 by accident).  I can think of some ways to work around this in the format using specific characters in one and not the other, but it starts to feel really hacky.  I’m just not sure if this is actually important for real-world applications.  Many applications just use the UUID opaquely, but not all.  And again, extracting the timestamp can be useful - but then is it reasonable to also say “if you want the time, you’ll need to know the format, you won’t be able to automatically tell the difference between a base64 and base32 UUID”.  One possible simple solution: For UUIDs longer than 128 bits, put a period after the first 128 bits and then encode the rest.  This would make it possible with a few basic checks to tell which encoding format, and would remain URL safe.  And is simple to implement.
>> 
>> All that said, it seems to me we’re headed for a spec that has the following properties:
>> 
>> - Encodes timestamp
>> - Sorts correctly as raw bytes
>> - Has the version field in the same place for compatibility
>> - Supports the existing 128-bit hex representation (NNNNNNNN-NNNN-NNNN-NNNN-NNNNNNNNNNNN) for compatibility but also...
>> - Specifies alternative (url-safe) base64 encoding for compact string representation while still sorting correctly; and also a base32 encoding where case-insensitivity is required (ideally with a way to scan the string and easily tell which encoding format is being used)
>> - Instead of existing dangerous bits like counter and MAC address, use secure random data available from OS
>> - Can be arbitrarily longer as needed, filled with additional random data.
>> 
>> Does that seem about right?
>> 
>> Also, when things settle in terms of the high level requirements, at what point should a rough draft of the spec on this be written?  (And is there some sort of outline I would follow?)
>> 
>> -Brad
>> 
>> 
>>> On Jul 3, 2018, at 7:11 PM, Martin Thomson <[e-mail]> wrote:
>>> 
>>> Nice presentation.
>>> 
>>> I've always been skeptical of the value of UUIDs.  It's very easy to
>>> make a unique string.  Formatting it in a particular way, however,
>>> serves no real purpose and it might not be necessary for your use
>>> case.
>>> 
>>> UUIDs (aside from v4) also have some nasty properties.  For instance,
>>> revealing a MAC address is now considered problematic.  As is exposing
>>> the output of a clock, which has been used in interesting ways to
>>> undermine privacy (clock skew can be used for de-anonymisation, even
>>> for determining CPU load).  Counters and timers also allow an observer
>>> to correlate the creation of different identifiers.
>>> 
>>> Why not make a string with the properties you desire?  You might need
>>> more than 120 bits to achieve all that, but that's just another reason
>>> not to use UUIDs.  A library that provided these functions (maybe
>>> while addressing the above concerns), would be a valuable addition.
>>> On Wed, Jul 4, 2018 at 10:42 AM Brad Peabody <[e-mail]> wrote:
>>>> 
>>>> I would like to get some initial feedback, and suggested next steps, on the idea of making an RFC that covers a version 6 for UUIDs.  It would have an embedded timestamp and sorting by its raw bytes results in a sequence equivalent to sorting by time.  This is not addressed by existing UUID types.  (The closest one is version 1, but due to the byte encoding it does not sort correctly.)
>>>> 
>>>> There is also seems to be some ambiguity in the existing RFC on when to increment the counter field which I think can be clarified.
>>>> 
>>>> I did a prototype implementation and basic write-up on the details here: https://bradleypeabody.github.io/uuidv6/
>>>> 
>>>> I’m also thinking of covering the base64 encoding form which retains the sorting properties but makes it human readable and is significantly shorter than the long hex encoded form.
>>>> 
>>>> Having these things is very useful when considering UUIDs as database primary keys, which is becoming more and more common in distributed systems; and indeed this is the main motivation.
>>>> 
>>>> Any help or advice on moving forward with this would be appreciated.
>>>> 
>>>> - Brad
>>>> 
>>