From: "Andrey M. Borodin" <x4mmm@yandex-team.ru>
Message-Id: <F91948DD-500A-4A22-ABB9-5F4C59C28851@yandex-team.ru>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_2D58B6DC-6E7E-41D8-A55C-61581025F526"
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.120.41.1.2\))
Subject: Re: UUID v7
Date: Sun, 20 Aug 2023 23:56:34 +0300
In-Reply-To: <84D20D0F-B5FF-41CD-9F48-E282CE9FEC1D@yandex-team.ru>
Cc: Tom Lane <tgl@sss.pgh.pa.us>,
 Daniel Gustafsson <daniel@yesql.se>,
 Matthias van de Meent <boekewurm+postgres@gmail.com>,
 Nikolay Samokhvalov <samokhvalov@gmail.com>,
 "Kyzer Davis (kydavis)" <kydavis@cisco.com>,
 Andres Freund <andres@anarazel.de>,
 Andrey Borodin <amborodin86@gmail.com>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>,
 "brad@peabody.io" <brad@peabody.io>,
 "wolakk@gmail.com" <wolakk@gmail.com>,
 sergeyprokhorenko@yahoo.com.au
To: Peter Eisentraut <peter.eisentraut@enterprisedb.com>
References: <CAAhFRxitJv=yoGnXUgeLB_O+M7J2BJAmb5jqAT9gZ3bij3uLDA@mail.gmail.com>
 <20230211011453.uq2yopunpbovcbnn@awork3.anarazel.de>
 <5ceb7394-7488-d438-0951-fcc940feb539@enterprisedb.com>
 <PH0PR11MB5029DF5E0A0EAF8E3CC2C652BBA29@PH0PR11MB5029.namprd11.prod.outlook.com>
 <CANNMO+L9pmgrEZPLhpRrjRcTnzMKgzURSeWFofuKfbHJT9euiA@mail.gmail.com>
 <5176A0E4-CA75-47D0-A1F3-FBC9B6116595@yesql.se>
 <CAEze2WhHf8WURmcqu4ZxS7HFzVxPxK4jXUijnPu-easySjgZWg@mail.gmail.com>
 <7AC9F1D2-A02B-4FF6-A331-C686C7EA244B@yesql.se>
 <1204013.1688652164@sss.pgh.pa.us>
 <457ba532-ea71-dc13-6d60-2b79bb32eeeb@enterprisedb.com>
 <D8F6A3ED-9F70-4FBE-A259-AABFD89083C4@yandex-team.ru>
 <5dc6fdaa-5896-ebc4-7094-eac45a818846@enterprisedb.com>
 <84D20D0F-B5FF-41CD-9F48-E282CE9FEC1D@yandex-team.ru>
Archived-At: <https://www.postgresql.org/message-id/F91948DD-500A-4A22-ABB9-5F4C59C28851%40yandex-team.ru>
Precedence: bulk


--Apple-Mail=_2D58B6DC-6E7E-41D8-A55C-61581025F526
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii


> On 30 Jul 2023, at 13:08, Andrey M. Borodin <x4mmm@yandex-team.ru> =
wrote:
>=20
>=20
> 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.
>=20

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!

Best regards, Andrey Borodin.

--Apple-Mail=_2D58B6DC-6E7E-41D8-A55C-61581025F526
Content-Disposition: attachment;
	filename=v4-0001-Implement-UUID-v7-as-per-IETF-draft.patch
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="v4-0001-Implement-UUID-v7-as-per-IETF-draft.patch"
Content-Transfer-Encoding: quoted-printable

=46rom=20f53c76291c2b832aab9bcac0dd96b05ad37c37cd=20Mon=20Sep=2017=20=
00:00:00=202001=0AFrom:=20"Andrey=20M.=20Borodin"=20<x4mmm@night.local>=0A=
Date:=20Sun,=2020=20Aug=202023=2023:55:31=20+0300=0ASubject:=20[PATCH=20=
v4]=20Implement=20UUID=20v7=20as=20per=20IETF=20draft=0A=0AAuthors:=20=
Andrey=20Borodin,=20Sergey=20Prokhorenko=0A---=0A=20=
doc/src/sgml/func.sgml=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20|=2010=20+++-=0A=20src/backend/utils/adt/uuid.c=20=20=20=20=20=20=20=
=20=20=20=20=20=20|=2076=20++++++++++++++++++++++++=0A=20=
src/include/catalog/pg_proc.dat=20=20=20=20=20=20=20=20=20=20|=20=203=20=
+=0A=20src/test/regress/expected/opr_sanity.out=20|=20=201=20+=0A=20=
src/test/regress/expected/uuid.out=20=20=20=20=20=20=20|=2010=20++++=0A=20=
src/test/regress/sql/uuid.sql=20=20=20=20=20=20=20=20=20=20=20=20|=20=20=
6=20++=0A=206=20files=20changed,=20105=20insertions(+),=201=20=
deletion(-)=0A=0Adiff=20--git=20a/doc/src/sgml/func.sgml=20=
b/doc/src/sgml/func.sgml=0Aindex=20be2f54c914..b2d89cf415=20100644=0A---=20=
a/doc/src/sgml/func.sgml=0A+++=20b/doc/src/sgml/func.sgml=0A@@=20=
-13947,13=20+13947,21=20@@=20CREATE=20TYPE=20rainbow=20AS=20ENUM=20=
('red',=20'orange',=20'yellow',=20'green',=20'blue',=20'purple=0A=20=20=20=
=20<primary>gen_random_uuid</primary>=0A=20=20=20</indexterm>=0A=20=0A+=20=
=20<indexterm>=0A+=20=20=20<primary>gen_uuid_v7</primary>=0A+=20=20=
</indexterm>=0A+=0A=20=20=20<para>=0A-=20=20=20=
<productname>PostgreSQL</productname>=20includes=20one=20function=20to=20=
generate=20a=20UUID:=0A+=20=20=20<productname>PostgreSQL</productname>=20=
includes=20three=20functions=20to=20generate=20a=20UUID:=0A=20<synopsis>=0A=
=20<function>gen_random_uuid</function>=20()=20=
<returnvalue>uuid</returnvalue>=0A=20</synopsis>=0A=20=20=20=20This=20=
function=20returns=20a=20version=204=20(random)=20UUID.=20=20This=20is=20=
the=20most=20commonly=0A=20=20=20=20used=20type=20of=20UUID=20and=20is=20=
appropriate=20for=20most=20applications.=0A+<synopsis>=0A=
+<function>gen_uuid_v7</function>=20()=20<returnvalue>uuid</returnvalue>=0A=
+</synopsis>=0A+=20=20=20This=20function=20returns=20a=20version=207=20=
(time-ordered=20+=20random)=20UUID.=0A=20=20=20</para>=0A=20=0A=20=20=20=
<para>=0Adiff=20--git=20a/src/backend/utils/adt/uuid.c=20=
b/src/backend/utils/adt/uuid.c=0Aindex=204f7aa768fd..fed0b1bc52=20100644=0A=
---=20a/src/backend/utils/adt/uuid.c=0A+++=20=
b/src/backend/utils/adt/uuid.c=0A@@=20-13,6=20+13,9=20@@=0A=20=0A=20=
#include=20"postgres.h"=0A=20=0A+#include=20<sys/time.h>=0A+=0A+#include=20=
"access/xlog.h"=0A=20#include=20"common/hashfn.h"=0A=20#include=20=
"lib/hyperloglog.h"=0A=20#include=20"libpq/pqformat.h"=0A@@=20-421,3=20=
+424,76=20@@=20gen_random_uuid(PG_FUNCTION_ARGS)=0A=20=0A=20=09=
PG_RETURN_UUID_P(uuid);=0A=20}=0A+=0A+static=20uint32_t=20=
sequence_counter;=0A+static=20uint64_t=20previous_timestamp=20=3D=200;=0A=
+=0A+=0A+Datum=0A+gen_uuid_v7(PG_FUNCTION_ARGS)=0A+{=0A+=09pg_uuid_t=20=20=
*uuid=20=3D=20palloc(UUID_LEN);=0A+=09uint64_t=20tms;=0A+=09struct=20=
timeval=20tp;=0A+=0A+=09gettimeofday(&tp,=20NULL);=0A+=0A+=09tms=20=3D=20=
((uint64_t)tp.tv_sec)=20*=201000=20+=20(tp.tv_usec)=20/=201000;=0A+=0A+=09=
tms=20=3D=20pg_hton64(tms<<16);=0A+=0A+=09/*=20Fill=20in=20time=20part=20=
*/=0A+=09memcpy(&uuid->data[0],=20&tms,=206);=0A+=0A+=09if=20(tms=20=3D=3D=
=20previous_timestamp)=0A+=09{=0A+=09=09/*=20Time=20did=20not=20change=20=
from=20the=20previous=20generation,=20we=20must=20increment=20counter=20=
*/=0A+=09=09++sequence_counter;=0A+=09=09/*=20fill=20everything=20after=20=
the=20timestamp=20and=20counter=20with=20random=20bytes=20*/=0A+=09=09if=20=
(!pg_strong_random(&uuid->data[8],=20UUID_LEN=20-=208))=0A+=09=09=09=
ereport(ERROR,=0A+=09=09=09=09=09(errcode(ERRCODE_INTERNAL_ERROR),=0A+=09=
=09=09=09=09errmsg("could=20not=20generate=20random=20values")));=0A+=0A=
+=09=09/*=20most=20significant=204=20bits=20of=2018-bit=20counter=20*/=0A=
+=09=09uuid->data[6]=20=3D=20(unsigned=20char)(sequence_counter=20>>=20=
14);=0A+=09=09/*=20next=208=20bits=20*/=0A+=09=09uuid->data[7]=20=3D=20=
(unsigned=20char)(sequence_counter=20>>=206);=0A+=09=09/*=20least=20=
significant=206=20bits=20*/=0A+=09=09uuid->data[8]=20=3D=20(unsigned=20=
char)(sequence_counter);=0A+=09}=0A+=09else=0A+=09{=0A+=09=09/*=20fill=20=
everything=20after=20the=20timestamp=20with=20random=20bytes=20*/=0A+=09=09=
if=20(!pg_strong_random(&uuid->data[6],=20UUID_LEN=20-=206))=0A+=09=09=09=
ereport(ERROR,=0A+=09=09=09=09=09(errcode(ERRCODE_INTERNAL_ERROR),=0A+=09=
=09=09=09=09errmsg("could=20not=20generate=20random=20values")));=0A+=0A=
+=09=09/*=0A+=09=09=20*=20Left-most=20counter=20bits=20are=20initialized=20=
as=20zero=20for=20the=20sole=20purpose=0A+=09=09=20*=20of=20guarding=20=
against=20counter=20rollovers.=0A+=09=09=20*=20See=20section=20=
"Fixed-Length=20Dedicated=20Counter=20Seeding"=0A+=09=09=20*=20=
https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis-09#mon=
otonicity_counters=0A+=09=09=20*/=0A+=09=09uuid->data[6]=20=3D=20=
(uuid->data[6]=20&=200xf7);=0A+=0A+=09=09sequence_counter=20=3D=20=
((uint32_t)uuid->data[8]=20&=200x3f)=20+=0A+=09=09=09=09=09=09=09=
(((uint32_t)uuid->data[7])=20<<=206)=20+=0A+=09=09=09=09=09=09=09=
(((uint32_t)uuid->data[6]=20&=200x0f)=20<<=2014);=0A+=0A+=09=09=
previous_timestamp=20=3D=20tms;=0A+=09}=0A+=0A+=09/*=0A+=09=20*=20Set=20=
magic=20numbers=20for=20a=20"version=207"=20(pseudorandom)=20UUID,=20see=0A=
+=09=20*=20http://tools.ietf.org/html/rfc=20???=0A+=09=20*=20=
https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-form=
at#name-creating-a-uuidv7-value=0A+=09=20*/=0A+=09/*=20set=20version=20=
field,=20top=20four=20bits=20are=200,=201,=201,=201=20*/=0A+=09=
uuid->data[6]=20=3D=20(uuid->data[6]=20&=200x0f)=20|=200x70;=0A+=09/*=20=
set=20variant=20field,=20top=20two=20bits=20are=201,=200=20*/=0A+=09=
uuid->data[8]=20=3D=20(uuid->data[8]=20&=200x3f)=20|=200x80;=0A+=0A+=09=
PG_RETURN_UUID_P(uuid);=0A+}=0Adiff=20--git=20=
a/src/include/catalog/pg_proc.dat=20b/src/include/catalog/pg_proc.dat=0A=
index=2012fac15ceb..4e6089060a=20100644=0A---=20=
a/src/include/catalog/pg_proc.dat=0A+++=20=
b/src/include/catalog/pg_proc.dat=0A@@=20-9125,6=20+9125,9=20@@=0A=20{=20=
oid=20=3D>=20'3432',=20descr=20=3D>=20'generate=20random=20UUID',=0A=20=20=
=20proname=20=3D>=20'gen_random_uuid',=20proleakproof=20=3D>=20't',=20=
provolatile=20=3D>=20'v',=0A=20=20=20prorettype=20=3D>=20'uuid',=20=
proargtypes=20=3D>=20'',=20prosrc=20=3D>=20'gen_random_uuid'=20},=0A+{=20=
oid=20=3D>=20'3813',=20descr=20=3D>=20'generate=20UUID=20version=207',=0A=
+=20=20proname=20=3D>=20'gen_uuid_v7',=20proleakproof=20=3D>=20't',=20=
provolatile=20=3D>=20'v',=0A+=20=20prorettype=20=3D>=20'uuid',=20=
proargtypes=20=3D>=20'',=20prosrc=20=3D>=20'gen_uuid_v7'=20},=0A=20=0A=20=
#=20pg_lsn=0A=20{=20oid=20=3D>=20'3229',=20descr=20=3D>=20'I/O',=0Adiff=20=
--git=20a/src/test/regress/expected/opr_sanity.out=20=
b/src/test/regress/expected/opr_sanity.out=0Aindex=20=
a1bdf2c0b5..3141183b01=20100644=0A---=20=
a/src/test/regress/expected/opr_sanity.out=0A+++=20=
b/src/test/regress/expected/opr_sanity.out=0A@@=20-857,6=20+857,7=20@@=20=
sha384(bytea)=0A=20sha512(bytea)=0A=20gen_random_uuid()=0A=20=
starts_with(text,text)=0A+gen_uuid_v7()=0A=20=
macaddr8_eq(macaddr8,macaddr8)=0A=20macaddr8_lt(macaddr8,macaddr8)=0A=20=
macaddr8_le(macaddr8,macaddr8)=0Adiff=20--git=20=
a/src/test/regress/expected/uuid.out=20=
b/src/test/regress/expected/uuid.out=0Aindex=208e7f21910d..fc9f50e69e=20=
100644=0A---=20a/src/test/regress/expected/uuid.out=0A+++=20=
b/src/test/regress/expected/uuid.out=0A@@=20-168,5=20+168,15=20@@=20=
SELECT=20count(DISTINCT=20guid_field)=20FROM=20guid1;=0A=20=20=20=20=20=20=
2=0A=20(1=20row)=0A=20=0A+--=20generation=20test=20for=20v7=0A+TRUNCATE=20=
guid1;=0A+INSERT=20INTO=20guid1=20(guid_field)=20VALUES=20=
(gen_uuid_v7());=0A+INSERT=20INTO=20guid1=20(guid_field)=20VALUES=20=
(gen_uuid_v7());=0A+SELECT=20count(DISTINCT=20guid_field)=20FROM=20=
guid1;=0A+=20count=20=0A+-------=0A+=20=20=20=20=202=0A+(1=20row)=0A+=0A=20=
--=20clean=20up=0A=20DROP=20TABLE=20guid1,=20guid2=20CASCADE;=0Adiff=20=
--git=20a/src/test/regress/sql/uuid.sql=20=
b/src/test/regress/sql/uuid.sql=0Aindex=209a8f437c7d..02b8e7f10c=20=
100644=0A---=20a/src/test/regress/sql/uuid.sql=0A+++=20=
b/src/test/regress/sql/uuid.sql=0A@@=20-85,5=20+85,11=20@@=20INSERT=20=
INTO=20guid1=20(guid_field)=20VALUES=20(gen_random_uuid());=0A=20INSERT=20=
INTO=20guid1=20(guid_field)=20VALUES=20(gen_random_uuid());=0A=20SELECT=20=
count(DISTINCT=20guid_field)=20FROM=20guid1;=0A=20=0A+--=20generation=20=
test=20for=20v7=0A+TRUNCATE=20guid1;=0A+INSERT=20INTO=20guid1=20=
(guid_field)=20VALUES=20(gen_uuid_v7());=0A+INSERT=20INTO=20guid1=20=
(guid_field)=20VALUES=20(gen_uuid_v7());=0A+SELECT=20count(DISTINCT=20=
guid_field)=20FROM=20guid1;=0A+=0A=20--=20clean=20up=0A=20DROP=20TABLE=20=
guid1,=20guid2=20CASCADE;=0A--=20=0A2.37.1=20(Apple=20Git-137.1)=0A=0A=

--Apple-Mail=_2D58B6DC-6E7E-41D8-A55C-61581025F526--