Content-Type: text/plain;
	charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.120.41.1.4\))
Subject: Re: UUID v7
From: "Andrey M. Borodin" <x4mmm@yandex-team.ru>
In-Reply-To: <CAGECzQRYit62xO=HqX7kAf8tELjZTsYc0LQ1LStUsaKSPqJu_w@mail.gmail.com>
Date: Mon, 11 Mar 2024 23:27:43 +0500
Cc: Aleksander Alekseev <aleksander@timescale.com>,
 pgsql-hackers mailing list <pgsql-hackers@postgresql.org>,
 Peter Eisentraut <peter@eisentraut.org>,
 Sergey Prokhorenko <sergeyprokhorenko@yahoo.com.au>,
 =?utf-8?Q?Przemys=C5=82aw_Sztoch?= <przemyslaw@sztoch.pl>,
 "David G. Johnston" <david.g.johnston@gmail.com>,
 Mat Arye <mat@timescaledb.com>,
 Matthias van de Meent <boekewurm+postgres@gmail.com>,
 Nikolay Samokhvalov <samokhvalov@gmail.com>,
 Junwang Zhao <zhjwpku@gmail.com>
Content-Transfer-Encoding: quoted-printable
Message-Id: <844E6A65-4A36-4A36-94C2-0CDF7615B53F@yandex-team.ru>
References: <CAAhFRxitJv=yoGnXUgeLB_O+M7J2BJAmb5jqAT9gZ3bij3uLDA@mail.gmail.com>
 <CAKFQuwai1N+Tm-P91zqnJEmT11kD7RqJLJrrhWFSxS1pRSR47w@mail.gmail.com>
 <B4034B63-6C3F-46B1-A26F-23B4B8CC72D6@yandex-team.ru>
 <0A0D7507-C434-46AC-BCC4-1166C5A2742A@yandex-team.ru>
 <CAM527d__3qQxvpUC_5tWW5TeodE=bivYT3eNDpjrVAk3-uU0TA@mail.gmail.com>
 <1459150585.359059.1706132985954@mail.yahoo.com>
 <CAM527d8QbYa9CfsUezn_owUP8M0JWGYiosMEOkQqD6=PsncEnA@mail.gmail.com>
 <00B784AB-5B52-4CC7-8A0D-B1C0C53B52DC@yandex-team.ru>
 <1014147035.642629.1706202245918@mail.yahoo.com>
 <5932FFF8-4E5F-44DC-8FEA-22E8302759C7@yandex-team.ru>
 <CAGECzQTVi1JUE43uisQ+uKz46bQ+e+uwR9PUsmNfo2rjKaqwoA@mail.gmail.com>
 <8AA22330-7D3A-46CF-B311-2FF874D7C713@yandex-team.ru>
 <1971811009.2132347.1706599708209@mail.yahoo.com>
 <72C1E7CB-E2EC-46CF-AD2C-B3180CED885B@yandex-team.ru>
 <CAEG8a3JUgkY3EMp393kJ+bcye8q=VHfQDTQz7Ci-moNVjhPLZA@mail.gmail.com>
 <0906F8BA-CA52-4956-AA68-E9193E50DFDF@yandex-team.ru>
 <10553e4c-6b66-44b9-86a7-80bb1958a767@eisentraut.org>
 <BFDA918D-1CB0-4980-A31F-C1AC95BE68F6@yandex-team.ru>
 <5D22C2BF-5DED-43CA-A3D7-B724EE0A159D@yandex-team.ru>
 <CAJ7c6TPOOpr-39CNz32oC_ruEAiqhPZ=PBe0OE+d-W4wjBabWA@mail.gmail.com>
 <CAGECzQRYit62xO=HqX7kAf8tELjZTsYc0LQ1LStUsaKSPqJu_w@mail.gmail.com>
To: Jelte Fennema-Nio <postgres@jeltef.nl>
Archived-At: <https://www.postgresql.org/message-id/844E6A65-4A36-4A36-94C2-0CDF7615B53F%40yandex-team.ru>
Precedence: bulk


> On 11 Mar 2024, at 20:56, Jelte Fennema-Nio <postgres@jeltef.nl> =
wrote:
>=20
> Attached a few comment fixes/improvements and a pgindent run (patch =
0002-0004)

Thanks!

> 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.
>=20
> 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.

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=3D0. My implementation of method 2 uses c1=3D1, =
c2=3D17

Consider all UUIDs generated at any given milliseconds. Probability of a =
collision of two UUIDs generated at frequency less than 1KHz is p =3D =
2^-(c2+d)
Capacity of a counter has expected value of c =3D 2^(c1)*2^(c2-1)/2^c3
To guess next UUID you can correctly pick one of u =3D 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 =3D 1, we can distribute 73 bits between c2 and d. I've chosen c2 =
=3D 17 and d =3D 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=3D1, c2=3D3,d=3D6.

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!


Best regards, Andrey Borodin.=