Subject: Re: UUID v7

From: "Andrey M. Borodin" <[email-masked]>
Date: Sun, 10 Mar 2024 21:08:24 +0500

> On 10 Mar 2024, at 17:59, Andrey M. Borodin <[email-masked]> wrote:
> 
> I tried to "make docs", but it gives me gazilion of errors... Is there an easy way to see resulting HTML?

Oops, CFbot expectedly found a problem...
Sorry for the noise, this version, I hope, will pass all the tests.
Thanks!

Best regards, Andrey Borodin.

---

From: Aleksander Alekseev <[email-masked]>
Date: Mon, 11 Mar 2024 15:44:58 +0300

Hi,

> Best regards, Andrey Borodin.

I had some issues applying v19 against the current `master` branch.
PFA the rebased and minorly tweaked v20.

The patch LGTM. I think it could be merged unless there are any open
issues left. I don't think so, but maybe I missed something.

-- 
Best regards,
Aleksander Alekseev

---

From: Jelte Fennema-Nio <[email-masked]>
Date: Mon, 11 Mar 2024 16:56:23 +0100

Attached a few comment fixes/improvements and a pgindent run (patch 0002-0004)

Now with the added comments, one thing pops out to me: The comments
mention that we use "Monotonic Random", but when I read the spec that
explicitly recommends against using an increment of 1 when using
monotonic random. I feel like if we use an increment of 1, we're
better off going for the "Fixed-Length Dedicated Counter Bits" method
(i.e. change the code to start the counter at 0). See patch 0005 for
an example of that change.

I'm also wondering if we really want to use the extra rand_b bits for
this. The spec says we MAY, but it does remove the amount of
randomness in our UUIDs.

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Mon, 11 Mar 2024 23:27:43 +0500

> On 11 Mar 2024, at 20:56, Jelte Fennema-Nio <[email-masked]> wrote:
> 

Thanks!

> this. The spec says we MAY, but it does remove the amount of

Method 1 is a just a Method 2 with specifically picked constants.
But I'll have to use some hand-wavy wordings...

UUID consists of these 128 bits:
a. Mandatory 2 var and 4 ver bits.
b. Flexible but strongly recommended 48 bits unix_ts_ms. These bits contribute to global sortability of values generated at frequency less than 1KHz.
c. Counter bits:
c1. Initialised with 0 on any time tick.
c2. Initialised with randomness.
c3*. bit width of a counter step (*not counted in 128 bit capacity, can be non-integral)
d. Randomness bits.

Method 1 is when c2=0. My implementation of method 2 uses c1=1, c2=17

Consider all UUIDs generated at any given milliseconds. Probability of a collision of two UUIDs generated at frequency less than 1KHz is p = 2^-(c2+d)
Capacity of a counter has expected value of c = 2^(c1)*2^(c2-1)/2^c3
To guess next UUID you can correctly pick one of u = 2^(d+c3)

First, observe that c3 contributes unguessability at exactly same scale as decreases counter capacity. There is no difference between using bits in d directly, or in c3. There is no point in non-zero c3. Every bit that could be given to c3 can equally be given to d.

Second, observe that c2 bits contribute to both collision protection and counter capacity! And when the time ticks, c2 also contribute to unguessability! So, technically, we should consider using all available bits as c2 bits.

How many c1 bits do we need? I've chosen one - to prevent occasional counter capacity reduction.

If c1 = 1, we can distribute 73 bits between c2 and d. I've chosen c2 = 17 and d = 56 as an arbitrary compromise between capacity of one backend per ms and prevention of global collision.
This compromise is mostly dictated by maximum frequency of UUID generation by one backend, I've chosen 200MHz as a sane value.

This compromise is much easier when you do not have 74 spare bits, this crazy amount of information forgives almost any mistake. Imagine you have to distribute 10 bits between c2 and d. And you try to prevent collision between 10 independent devices which need capacity to generate IDs with frequency of 10KHz each and keep sortability. You would have something like c1=1, c2=3,d=6.

Sorry for this long and vague explanation, if it still seems too uncertain we can have a chat or something like that. I don't think this number picking stuff deserve to be commented, because it still is quite close to random. RFC gives us too much freedom of choice.

Thanks!

---

From: Michael Paquier <[email-masked]>
Date: Tue, 12 Mar 2024 14:53:27 +0900

On Mon, Mar 11, 2024 at 11:27:43PM +0500, Andrey M. Borodin wrote:
> Sorry for this long and vague explanation, if it still seems too
> uncertain we can have a chat or something like that. I don't think
> this number picking stuff deserve to be commented, because it still
> is quite close to random. RFC gives us too much freedom of choice.

Speaking about the RFC, I can see that there is a draft but nothing
formal yet.  The last one I can see is v14 from last November:
https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis-14

It does not strike me as a good idea to rush an implementation without
a specification officially approved because there is always a risk of
shipping something that's non-compliant into core.  But perhaps I am
missing something on the RFC side?
--
Michael

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Tue, 12 Mar 2024 11:10:37 +0500

> On 12 Mar 2024, at 10:53, Michael Paquier <[email-masked]> wrote:
> 

Upthread one of document’s authors commented:

> On 14 Feb 2023, at 19:13, Kyzer Davis (kydavis) <[email-masked]> wrote:
> 
> The point is 99% of the work since adoption by the IETF has been ironing out 
> RFC4122's problems and nothing major related to UUIDv6/7/8 which are all in a 
> very good state.

And also

> On 22 Jan 2024, at 09:22, Nikolay Samokhvalov <[email-masked]> wrote:
> 
> And many libraries are already including implementation of UUIDv7 – here are some examples:
> 
> - https://www.npmjs.com/package/uuidv7
> - https://crates.io/crates/uuidv7
> - https://github.com/google/uuid/pull/139

So at least reviewing patch and agreeing on chosen methods and constants makes sense.

---

From: Jelte Fennema-Nio <[email-masked]>
Date: Tue, 12 Mar 2024 16:35:59 +0100

> Sorry for this long and vague explanation, if it still seems too uncertain we can have a chat or something like that. I don't think this number picking stuff deserve to be commented, because it sti…

I thought your explanation was quite clear and I agree that this
approach makes the most sense. I sent an email to the RFC authors to
ask for their feedback with you (Andrey) in the CC, because even
though it makes the most sense it does not comply with the either of
method 1 or 2 as described in the RFC.

---

From: Sergey Prokhorenko <[email-masked]>
Date: Tue, 12 Mar 2024 17:18:17 +0000 (UTC)

Hi Jelte,
I am one of the contributors to this RFC.

Andrey's patch corresponds exactly to Fixed-Length Dedicated Counter Bits (Method 1).

Andrey and you simply did not read the RFC a little further down in the text:
__________________________________________________________________

The following sub-topics cover topics related solely with creating reliable fixed-length dedicated counters:
   
   - Fixed-Length Dedicated Counter Seeding:
      -    
Implementations utilizing the fixed-length counter method randomly initialize the counter with each new timestamp tick. However, when the timestamp has not increased, the counter is instead incremented by the desired increment logic. When utilizing a randomly seeded counter alongside Method 1, the random value MAY be regenerated with each counter increment without impacting sortability. The downside is that Method 1 is prone to overflows if a counter of adequate length is not selected or the random data generated leaves little room for the required number of increments. Implementations utilizing fixed-length counter method MAY also choose to randomly initialize a portion of the counter rather than the entire counter. For example, a 24 bit counter could have the 23 bits in least-significant, right-most, position randomly initialized. The remaining most significant, left-most counter bit is initialized as zero for the sole purpose of guarding against counter rollovers.

      - 
   - Fixed-Length Dedicated Counter Length:
      - Select a counter bit-length that can properly handle the level of timestamp precision in use. For example, millisecond precision generally requires a larger counter than a timestamp with nanosecond precision. General guidance is that the counter SHOULD be at least 12 bits but no longer than 42 bits. Care must be taken to ensure that the counter length selected leaves room for sufficient entropy in the random portion of the UUID after the counter. This entropy helps improve the unguessability characteristics of UUIDs created within the batch.
      - The following sub-topics cover rollover handling with either type of counter method:   

      - ...
      - 
   - Counter Rollover Handling:
      -    
Counter rollovers MUST be handled by the application to avoid sorting issues. The general guidance is that applications that care about absolute monotonicity and sortability should freeze the counter and wait for the timestamp to advance which ensures monotonicity is not broken. Alternatively, implementations MAY increment the timestamp ahead of the actual time and reinitialize the counter.

Sergey [email-masked] 

    On Tuesday, 12 March 2024 at 06:36:13 pm GMT+3, Jelte Fennema-Nio <[email-masked]> wrote:

---

From: Jelte Fennema-Nio <[email-masked]>
Date: Tue, 12 Mar 2024 18:26:09 +0100

> Andrey and you simply did not read the RFC a little further down in the text:

You're totally right, sorry about that. Maybe it would be good to move
those subsections around a bit in the RFC though, so that anything
related to only one method is included in the section for that method.