Subject: RE: UUID v7

From: "Kyzer Davis (kydavis)" <[email-masked]>
Date: Tue, 14 Feb 2023 14:13:43 +0000

Hello Group,

I am happy to see others interested in the improvements provided by UUIDv7!

I caught up on the thread and you all are correct.

Work has moved on GitHub from uuid6/uuid6-ietf-draft to 
ietf-wg-uuidrev/rfc4122bis
- Draft 00 merged RFC4122 with Draft 04 and fixed as many problems as possible 
with RFC4122.
- Draft 01 continued to iterate on RFC4122 problems: 
https://author-tools.ietf.org/iddiff?url2=draft-ietf-uuidrev-rfc4122bis-01
- Draft 02 items being changed are summarized in the latest PR for review in 
the upcoming interim meeting (Feb 16th): 
https://github.com/ietf-wg-uuidrev/rfc4122bis/pull/60
Note: Draft 02 should be published by the end of the week and long term we 
have one more meeting at IETF 116 to iron out the replacement of RFC4122, 
perform last call and submit to the IESG for official review and consideration 
for replacement of RFC4122 (actual timeline for that varies based on what IESG 
wants me to fix.)

That all being said:
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.

If anybody has any feedback found during draft reviewing or prototyping; 
please either email [email-masked] or drop an issue on the tracker:
https://github.com/ietf-wg-uuidrev/rfc4122bis/issues

Lastly, I have added the C/SQL implementation to the prototypes page below:
https://github.com/uuid6/prototypes

Thanks!

-----Original Message-----
From: Peter Eisentraut <[email-masked]>
Sent: Saturday, February 11, 2023 10:51 AM
To: Andres Freund <[email-masked]>; Andrey Borodin <[email-masked]>
Cc: pgsql-hackers <[email-masked]>; [email-masked]; 
[email-masked]; Kyzer Davis (kydavis) <[email-masked]>; Nikolay 
Samokhvalov <[email-masked]>
Subject: Re: UUID v7

On 11.02.23 02:14, Andres Freund wrote:
> On 2023-02-10 15:57:50 -0800, Andrey Borodin wrote:
>> As you may know there's a new version of UUID being standardized [0].
>> These new algorithms of UUID generation are very promising for
>> database performance.
>
> I agree it's very useful to have.
>
>
>> [0]
>> https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid
>> -format-04
>
> That looks to not be the current version anymore, it's superseded by:
> https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis

Yes, this means that the draft that an individual had uploaded has now been 
taken on by a working group for formal review.  If there is a prototype 
implementation, this is a good time to provide feedback.  But it's too early 
to ship a production version.

---

From: Nikolay Samokhvalov <[email-masked]>
Date: Thu, 22 Jun 2023 11:30:20 -0700

> I am happy to see others interested in the improvements provided by UUIDv7!

Thank you for providing the details!

Some small updates as I see them:
- there is revision 7 now in https://github.com/ietf-wg-uuidrev/rfc4122bis
- noticing that there is no commitfest record, I created one:
https://commitfest.postgresql.org/43/4388/
- recent post by Ants Aasma, Cybertec about the downsides of
traditional UUID raised a big discussion today on HN:
https://news.ycombinator.com/item?id=36429986

---

From: Daniel Gustafsson <[email-masked]>
Date: Thu, 6 Jul 2023 14:24:11 +0200

> On 22 Jun 2023, at 20:30, Nikolay Samokhvalov <[email-masked]> wrote:

> - noticing that there is no commitfest record, I created one:

I will actually go ahead and close this entry in the current CF, not because we
don't want the feature but because it's unlikely that it will go in now given
that standardization is still underway.  Comitting anything right now seems
premature, we might as well wait for standardization given that we have lots of
time before the v17 freeze.

--
Daniel Gustafsson

---

From: Matthias van de Meent <[email-masked]>
Date: Thu, 6 Jul 2023 15:29:50 +0200

> time before the v17 freeze.

I'd like to note that this draft has recently had its last call
period, and has been proposed for publishing early last month. I don't
know how long this publishing process usually takes, but it seems like
the WG considers the text final, so unless this would take months I
wouldn't mind keeping this patch around as "waiting for external
process to complete". Sure, it's earlier than the actual release of
the standard, but that wasn't a blocker for SQL features that were
considered finalized either.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

---

From: Daniel Gustafsson <[email-masked]>
Date: Thu, 6 Jul 2023 15:43:06 +0200

> On 6 Jul 2023, at 15:29, Matthias van de Meent <[email-masked]> wrote:
> 
> period, and has been proposed for publishing early last month.

Sure, but this document is in AD Evaluation and there are many stages left in
the IESG process, it may still take a fair bit of time before this is done.

> Sure, it's earlier than the actual release of

I can't speak for any SQL standard features we've committed before being
standardized, it's for sure not the norm for the project.  I'm only commenting
on this particular Internet standard which we have plenty of time to commit
before v17 without rushing to beat a standards committee.

Also, if you look you can see that I moved it to the next CF in a vague hope
that standardization will be swift (which is admittedly never is).

--
Daniel Gustafsson

---

From: Tom Lane <[email-masked]>
Date: Thu, 06 Jul 2023 10:02:44 -0400

> standardized, it's for sure not the norm for the project.

We have done a couple of things that way recently.  An important
reason why we felt we could get away with that is that nowadays
we have people who actually sit on the SQL committee and have
reliable information on what's likely to make it into the final text
of the next version.  I don't think we have equivalent visibility or
should have equivalent confidence about how UUID v7 standardization
will play out.

			regards, tom lane

---

From: Peter Eisentraut <[email-masked]>
Date: Thu, 6 Jul 2023 18:38:27 +0200

> should have equivalent confidence about how UUID v7 standardization

(I have been attending some meetings and I'm on the mailing list.)

Anyway, I think it would be reasonable to review this patch now.  We 
might leave it hanging in "Ready for Committer" for a while when we get 
there.  But surely review can start now.

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Fri, 7 Jul 2023 17:06:19 +0500

> On 6 Jul 2023, at 21:38, Peter Eisentraut <[email-masked]> wrote:
> 
> I think it would be reasonable to review this patch now.
+1.

Also, I think we should discuss UUID v8. UUID version 8 provides an RFC-compatible format for experimental or vendor-specific use cases. Revision 1 of IETF draft contained interesting code for v8: almost similar to v7, but with fields for "node ID" and "rolling sequence number".
I think this is reasonable approach, thus I attach implementation of UUID v8 per [0]. But from my point of view this implementation has some flaws.
These two new fields "node ID" and "sequence" are there not for uniqueness, but rather for data locality.
But they are placed at the end, in bytes 14 and 15, after randomly generated numbers.

I think that "sequence" is there to help generate local ascending identifiers when the real time clock do not provide enough resolution. So "sequence" field must be placed after 6 bytes of time-generated identifier.

On a contrary "node ID" must differentiate identifiers generated on different nodes. So it makes sense to place "node ID" before timing. So identifiers generated on different nodes will tend to be in different ranges.
Although, section "6.4. Distributed UUID Generation" states that "node ID" is there to decrease the likelihood of a collision. So my intuition might be wrong here.

Do we want to provide this "vendor-specific" UUID with tweaks for databases? Or should we limit the scope with well defined UUID v7?

Best regards, Andrey Borodin.

[0] https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis-01

---

From: Peter Eisentraut <[email-masked]>
Date: Mon, 10 Jul 2023 18:50:38 +0200

On 07.07.23 14:06, Andrey M. Borodin wrote:
> I think this is reasonable approach, thus I attach implementation of UUID v8 per [0].

I suggest we keep this thread to v7, which has pretty straightforward 
semantics for PostgreSQL.  v8 by definition has many possible 
implementations, so you're going to have to make pretty strong arguments 
that yours is the best and only one, if you are going to claim the 
gen_uuid_v8 function name.

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Sun, 30 Jul 2023 15:08:41 +0500

> On 10 Jul 2023, at 21:50, Peter Eisentraut <[email-masked]> wrote:
> 
> I suggest we keep this thread to v7, which has pretty straightforward semantics for PostgreSQL.  v8 by definition has many possible implementations, so you're going to have to make pretty strong arguments that yours is the best and only one, if you are going to claim the gen_uuid_v8 function name.

Thanks Peter, I'll follow this course of action.

After discussion on GitHub with Sergey Prokhorenko [0] I understood that counter is optional, but useful part of UUID v7. It actually promotes sortability of data generated at high speed.
The standard does not specify how big counter should be. PFA patch with 16 bit counter. Maybe it worth doing 18bit counter - it will save us one byte of PRNG data. Currently we only take 2 bits out of the whole random byte.

[0] https://github.com/x4m/pg_uuid_next/issues/1#issuecomment-1657074776 <https://github.com/x4m/pg_uuid_next/issues/1#issuecomment-1657074776>

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Sun, 20 Aug 2023 23:56:34 +0300

> On 30 Jul 2023, at 13:08, Andrey M. Borodin <[email-masked]> wrote:
> 
> 

Here's a new patch version. Now counter is initialised with strong random on every time change (each ms). However, one first bit of the counter is preserved to zero. This is done to extend counter capacity (I left comments with reference to RFC with explanations).

Thanks!

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Mon, 21 Aug 2023 11:42:20 +0300

> On 20 Aug 2023, at 23:56, Andrey M. Borodin <[email-masked]> wrote:
> 
> <v4-0001-Implement-UUID-v7-as-per-IETF-draft.patch>

I've observed, that pre-generating and buffering random numbers makes UUID generation 10 times faster.

Without buffering
postgres=# with x as (select gen_uuid_v7() from generate_series(1,1e6)) select count(*) from x;
Time: 5286.572 ms (00:05.287)

With buffering
postgres=# with x as (select gen_uuid_v7() from generate_series(1,1e6)) select count(*) from x;
Time: 390.091 ms

This can speed up gen_random_uuid() on the same scale too. PFA implementation of this technique.

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Thu, 31 Aug 2023 00:04:46 +0500

> On 21 Aug 2023, at 13:42, Andrey M. Borodin <[email-masked]> wrote:
> 
> <v5-0001-Implement-UUID-v7-as-per-IETF-draft.patch><v5-0002-Buffer-random-numbers.patch><v5-0003-Use-cached-random-numbers-in-gen_random_uuid-too.patch>

FPA attached next version.
Changes:
- implemented protection from time leap backwards when series is generated on the same backend
- counter overflow is now translated into ms step forward