Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qHkEI-0005IQ-Ux for pgsql-hackers@arkaria.postgresql.org; Fri, 07 Jul 2023 12:06:31 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1qHkEH-0007zx-Er for pgsql-hackers@arkaria.postgresql.org; Fri, 07 Jul 2023 12:06:29 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qHkEH-0007zo-1m for pgsql-hackers@lists.postgresql.org; Fri, 07 Jul 2023 12:06:29 +0000 Received: from forwardcorp1b.mail.yandex.net ([2a02:6b8:c02:900:1:45:d181:df01]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qHkED-002iwv-H9 for pgsql-hackers@postgresql.org; Fri, 07 Jul 2023 12:06:28 +0000 Received: from mail-nwsmtp-smtp-corp-main-26.myt.yp-c.yandex.net (mail-nwsmtp-smtp-corp-main-26.myt.yp-c.yandex.net [IPv6:2a02:6b8:c12:1d86:0:640:2a41:0]) by forwardcorp1b.mail.yandex.net (Yandex) with ESMTP id C1CCA603EB; Fri, 7 Jul 2023 15:06:21 +0300 (MSK) Received: from smtpclient.apple (unknown [2a02:6b8:82:604:749f:5d18:9d8a:804c]) by mail-nwsmtp-smtp-corp-main-26.myt.yp-c.yandex.net (smtpcorp/Yandex) with ESMTPSA id J6Ucex0Og8c0-YkYpLAbU; Fri, 07 Jul 2023 15:06:21 +0300 X-Yandex-Fwd: 1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex-team.ru; s=default; t=1688731581; bh=Lt5yAic1Ux6XO1jeC4MjxW9hCnqqvhhMMxiFptRe+/w=; h=References:To:Cc:In-Reply-To:Date:From:Message-Id:Subject; b=ZGy8Fp+s//4+WtnYBnSruDIDKvSDVboWgtvIYMPkal+Odi9n3vrKHqs+38ifQbZXW lwYC2xnrVb+EYCWkNWtwz2blWq/lUL4jDiNeMgdk4k/izzh4r5KTNP0NM8LIjK7pIR yxtbWjhU6XYz0Q/qTQTaZHH9MUoO5v8oG+hv+uFE= Authentication-Results: mail-nwsmtp-smtp-corp-main-26.myt.yp-c.yandex.net; dkim=pass header.i=@yandex-team.ru From: "Andrey M. Borodin" Message-Id: Content-Type: multipart/mixed; boundary="Apple-Mail=_9EC995CF-F9D3-4318-A9F2-894190396C17" Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.120.41.1.2\)) Subject: Re: UUID v7 Date: Fri, 7 Jul 2023 17:06:19 +0500 In-Reply-To: <457ba532-ea71-dc13-6d60-2b79bb32eeeb@enterprisedb.com> Cc: Tom Lane , Daniel Gustafsson , Matthias van de Meent , Nikolay Samokhvalov , "Kyzer Davis (kydavis)" , Andres Freund , Andrey Borodin , PostgreSQL Hackers , "brad@peabody.io" , "wolakk@gmail.com" To: Peter Eisentraut References: <20230211011453.uq2yopunpbovcbnn@awork3.anarazel.de> <5ceb7394-7488-d438-0951-fcc940feb539@enterprisedb.com> <5176A0E4-CA75-47D0-A1F3-FBC9B6116595@yesql.se> <7AC9F1D2-A02B-4FF6-A331-C686C7EA244B@yesql.se> <1204013.1688652164@sss.pgh.pa.us> <457ba532-ea71-dc13-6d60-2b79bb32eeeb@enterprisedb.com> X-Mailer: Apple Mail (2.3696.120.41.1.2) List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --Apple-Mail=_9EC995CF-F9D3-4318-A9F2-894190396C17 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii > On 6 Jul 2023, at 21:38, Peter Eisentraut = wrote: >=20 > 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 --Apple-Mail=_9EC995CF-F9D3-4318-A9F2-894190396C17 Content-Disposition: attachment; filename=v2-0001-Implement-UUID-v7-and-v8-as-per-IETF-draft.patch Content-Type: application/octet-stream; x-unix-mode=0644; name="v2-0001-Implement-UUID-v7-and-v8-as-per-IETF-draft.patch" Content-Transfer-Encoding: quoted-printable =46rom=209f4c97a81aae3087581a024374a06e49156f2689=20Mon=20Sep=2017=20= 00:00:00=202001=0AFrom:=20Andrey=20Borodin=20=0A= Date:=20Fri,=2010=20Feb=202023=2015:38:40=20-0800=0ASubject:=20[PATCH=20= v2]=20Implement=20UUID=20v7=20and=20v8=20as=20per=20IETF=20draft=0A=0A= ---=0A=20doc/src/sgml/func.sgml=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20|=2018=20++++-=0A=20src/backend/utils/adt/uuid.c=20=20=20=20= =20=20=20=20=20=20=20=20=20|=2087=20++++++++++++++++++++++++=0A=20= src/include/catalog/pg_proc.dat=20=20=20=20=20=20=20=20=20=20|=20=206=20= ++=0A=20src/test/regress/expected/opr_sanity.out=20|=20=202=20+=0A=20= src/test/regress/expected/uuid.out=20=20=20=20=20=20=20|=2020=20++++++=0A= =20src/test/regress/sql/uuid.sql=20=20=20=20=20=20=20=20=20=20=20=20|=20= 12=20++++=0A=206=20files=20changed,=20144=20insertions(+),=201=20= deletion(-)=0A=0Adiff=20--git=20a/doc/src/sgml/func.sgml=20= b/doc/src/sgml/func.sgml=0Aindex=205a47ce4343..b8b5ee210a=20100644=0A---=20= a/doc/src/sgml/func.sgml=0A+++=20b/doc/src/sgml/func.sgml=0A@@=20= -13947,13=20+13947,29=20@@=20CREATE=20TYPE=20rainbow=20AS=20ENUM=20= ('red',=20'orange',=20'yellow',=20'green',=20'blue',=20'purple=0A=20=20=20= =20gen_random_uuid=0A=20=20=20=0A=20=0A+=20= =20=0A+=20=20=20gen_uuid_v7=0A+=20=20= =0A+=0A+=20=20=0A+=20=20=20= gen_uuid_v8=0A+=20=20=0A+=0A=20=20=20= =0A-=20=20=20PostgreSQL=20includes=20= one=20function=20to=20generate=20a=20UUID:=0A+=20=20=20= PostgreSQL=20includes=20three=20functions=20= to=20generate=20a=20UUID:=0A=20=0A=20= gen_random_uuid=20()=20= uuid=0A=20=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+=0A= +gen_uuid_v7=20()=20uuid=0A= +=0A+=20=20=20This=20function=20returns=20a=20version=207=20= (time-ordered=20+=20random)=20UUID.=0A+=0A= +gen_uuid_v8=20()=20uuid=0A= +=0A+=20=20=20This=20function=20returns=20a=20version=208=20= (time-ordered=20+=20random=20+=20node=20ID=20+=20rolling=20sequence=20= number)=20UUID.=0A=20=20=20=0A=20=0A=20=20=20=0Adiff=20= --git=20a/src/backend/utils/adt/uuid.c=20b/src/backend/utils/adt/uuid.c=0A= index=204f7aa768fd..44deead6b1=20100644=0A---=20= a/src/backend/utils/adt/uuid.c=0A+++=20b/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=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,87=20@@=20= gen_random_uuid(PG_FUNCTION_ARGS)=0A=20=0A=20=09PG_RETURN_UUID_P(uuid);=0A= =20}=0A+=0A+Datum=0A+gen_uuid_v7(PG_FUNCTION_ARGS)=0A+{=0A+=09pg_uuid_t=20= =20*uuid=20=3D=20palloc(UUID_LEN);=0A+=09struct=20timeval=20tp;=0A+=09= uint64_t=20tms;=0A+=0A+=09gettimeofday(&tp,=20NULL);=0A+=0A+=09tms=20=3D=20= ((uint64_t)tp.tv_sec)=20*=201000;=0A+=09tms=20+=3D=20= ((uint64_t)tp.tv_usec)=20/=201000;=0A+=0A+=09tms=20=3D=20= pg_hton64(tms<<16);=0A+=0A+=09/*=20Fill=20in=20time=20part=20*/=0A+=09= memcpy(&uuid->data[0],=20&tms,=206);=0A+=0A+=09/*=20fill=20everything=20= after=20the=20timestamp=20with=20random=20bytes=20*/=0A+=09if=20= (!pg_strong_random(&uuid->data[6],=20UUID_LEN=20-=206))=0A+=09=09= ereport(ERROR,=0A+=09=09=09=09(errcode(ERRCODE_INTERNAL_ERROR),=0A+=09=09= =09=09=20errmsg("could=20not=20generate=20random=20values")));=0A+=0A+=09= /*=0A+=09=20*=20Set=20magic=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+}=0A+=0A+static=20uint8_t=20sequence_counter;=0A= +=0A+Datum=0A+gen_uuid_v8(PG_FUNCTION_ARGS)=0A+{=0A+=09pg_uuid_t=20=20= *uuid=20=3D=20palloc(UUID_LEN);=0A+=09struct=20timeval=20tp;=0A+=09= uint32_t=20t;=0A+=09uint16_t=20ut;=0A+=09uint8_t=20node_id=20=3D=20= GetSystemIdentifier();=0A+=09uint8_t=20sequence=20=3D=20= sequence_counter++;=0A+=0A+=09/*=0A+=09TODO:=20Consider=20supplying=20= node=20ID=20and=20rolling=20sequence=20number=0A+=09if=20(PG_NARGS()=20= >=3D=201)=0A+=09=09node_id=20=3D=20PG_GETARG_CHAR(0);=0A+=09if=20= (PG_NARGS()=20>=3D=202)=0A+=09=09node_id=20=3D=20PG_GETARG_CHAR(1);=0A+=09= */=0A+=0A+=09gettimeofday(&tp,=20NULL);=0A+=09t=20=3D=20tp.tv_sec=20-=20= 1577836800;=0A+=09t=20=3D=20pg_hton32(t);=0A+=09memcpy(&uuid->data[0],=20= &t,=204);=0A+=0A+=09/*=2016=20bit=20subsecond=20fraction=20(~15=20= microsecond=20resolution)=20*/=0A+=09ut=20=3D=20((uint64_t)tp.tv_usec=20= <<=2016)=20/=201000000;=0A+=09memcpy(&uuid->data[4],=20&ut,=202);=0A+=0A= +=09/*=20fill=20everything=20after=20the=20timestamp=20with=20random=20= bytes=20*/=0A+=09if=20(!pg_strong_random(&uuid->data[6],=20UUID_LEN=20-=20= 6))=0A+=09=09ereport(ERROR,=0A+=09=09=09=09= (errcode(ERRCODE_INTERNAL_ERROR),=0A+=09=09=09=09=20errmsg("could=20not=20= generate=20random=20values")));=0A+=0A+=09/*=0A+=09=20*=20Set=20magic=20= numbers=20for=20a=20"version=208"=20UID,=20see=0A+=09=20*=20= https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis#name-c= reating-a-uuidv8-value=0A+=09=20*/=0A+=09uuid->data[6]=20=3D=20= (uuid->data[6]=20&=200x0f)=20|=200x80;=0A+=09uuid->data[8]=20=3D=20= (uuid->data[8]=20&=200x3f)=20|=200x80;=0A+=0A+=09uuid->data[14]=20=3D=20= node_id;=0A+=09uuid->data[15]=20=3D=20sequence;=0A+=0A+=09= PG_RETURN_UUID_P(uuid);=0A+}=0A\=20No=20newline=20at=20end=20of=20file=0A= diff=20--git=20a/src/include/catalog/pg_proc.dat=20= b/src/include/catalog/pg_proc.dat=0Aindex=206996073989..0c82f9280f=20= 100644=0A---=20a/src/include/catalog/pg_proc.dat=0A+++=20= b/src/include/catalog/pg_proc.dat=0A@@=20-9119,6=20+9119,12=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+{=20oid=20= =3D>=20'3814',=20descr=20=3D>=20'generate=20UUID=20version=208',=0A+=20=20= proname=20=3D>=20'gen_uuid_v8',=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_v8'=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..1fb9c654d3=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,8=20@@=20= sha384(bytea)=0A=20sha512(bytea)=0A=20gen_random_uuid()=0A=20= starts_with(text,text)=0A+gen_uuid_v7()=0A+gen_uuid_v8()=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..516d4998a7=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,25=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= +--=20generation=20test=20for=20v8=0A+TRUNCATE=20guid1;=0A+INSERT=20INTO=20= guid1=20(guid_field)=20VALUES=20(gen_uuid_v8());=0A+INSERT=20INTO=20= guid1=20(guid_field)=20VALUES=20(gen_uuid_v8());=0A+SELECT=20= count(DISTINCT=20guid_field)=20FROM=20guid1;=0A+=20count=20=0A+-------=0A= +=20=20=20=20=202=0A+(1=20row)=0A+=0A=20--=20clean=20up=0A=20DROP=20= TABLE=20guid1,=20guid2=20CASCADE;=0Adiff=20--git=20= a/src/test/regress/sql/uuid.sql=20b/src/test/regress/sql/uuid.sql=0A= index=209a8f437c7d..0d6784e70b=20100644=0A---=20= a/src/test/regress/sql/uuid.sql=0A+++=20b/src/test/regress/sql/uuid.sql=0A= @@=20-85,5=20+85,17=20@@=20INSERT=20INTO=20guid1=20(guid_field)=20VALUES=20= (gen_random_uuid());=0A=20INSERT=20INTO=20guid1=20(guid_field)=20VALUES=20= (gen_random_uuid());=0A=20SELECT=20count(DISTINCT=20guid_field)=20FROM=20= guid1;=0A=20=0A+--=20generation=20test=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=20guid_field)=20FROM=20guid1;=0A+=0A+--=20= generation=20test=20for=20v8=0A+TRUNCATE=20guid1;=0A+INSERT=20INTO=20= guid1=20(guid_field)=20VALUES=20(gen_uuid_v8());=0A+INSERT=20INTO=20= guid1=20(guid_field)=20VALUES=20(gen_uuid_v8());=0A+SELECT=20= count(DISTINCT=20guid_field)=20FROM=20guid1;=0A+=0A=20--=20clean=20up=0A=20= DROP=20TABLE=20guid1,=20guid2=20CASCADE;=0A--=20=0A2.37.1=20(Apple=20= Git-137.1)=0A=0A= --Apple-Mail=_9EC995CF-F9D3-4318-A9F2-894190396C17--