public inbox for [email protected]
help / color / mirror / Atom feedFrom: Andrey M. Borodin <[email protected]>
To: Peter Eisentraut <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: Daniel Gustafsson <[email protected]>
Cc: Matthias van de Meent <[email protected]>
Cc: Nikolay Samokhvalov <[email protected]>
Cc: Kyzer Davis (kydavis) <[email protected]>
Cc: Andres Freund <[email protected]>
Cc: Andrey Borodin <[email protected]>
Cc: PostgreSQL Hackers <[email protected]>
Cc: [email protected] <[email protected]>
Cc: [email protected] <[email protected]>
Cc: [email protected]
Subject: Re: UUID v7
Date: Sun, 20 Aug 2023 23:56:34 +0300
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <CAAhFRxitJv=yoGnXUgeLB_O+M7J2BJAmb5jqAT9gZ3bij3uLDA@mail.gmail.com>
<[email protected]>
<[email protected]>
<PH0PR11MB5029DF5E0A0EAF8E3CC2C652BBA29@PH0PR11MB5029.namprd11.prod.outlook.com>
<CANNMO+L9pmgrEZPLhpRrjRcTnzMKgzURSeWFofuKfbHJT9euiA@mail.gmail.com>
<[email protected]>
<CAEze2WhHf8WURmcqu4ZxS7HFzVxPxK4jXUijnPu-easySjgZWg@mail.gmail.com>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
> On 30 Jul 2023, at 13:08, Andrey M. Borodin <[email protected]> wrote:
>
>
> 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.
>
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.
Attachments:
[application/octet-stream] v4-0001-Implement-UUID-v7-as-per-IETF-draft.patch (6.5K, ../[email protected]/2-v4-0001-Implement-UUID-v7-as-per-IETF-draft.patch)
download | inline diff:
From f53c76291c2b832aab9bcac0dd96b05ad37c37cd Mon Sep 17 00:00:00 2001
From: "Andrey M. Borodin" <[email protected]>
Date: Sun, 20 Aug 2023 23:55:31 +0300
Subject: [PATCH v4] Implement UUID v7 as per IETF draft
Authors: Andrey Borodin, Sergey Prokhorenko
---
doc/src/sgml/func.sgml | 10 +++-
src/backend/utils/adt/uuid.c | 76 ++++++++++++++++++++++++
src/include/catalog/pg_proc.dat | 3 +
src/test/regress/expected/opr_sanity.out | 1 +
src/test/regress/expected/uuid.out | 10 ++++
src/test/regress/sql/uuid.sql | 6 ++
6 files changed, 105 insertions(+), 1 deletion(-)
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index be2f54c914..b2d89cf415 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -13947,13 +13947,21 @@ CREATE TYPE rainbow AS ENUM ('red', 'orange', 'yellow', 'green', 'blue', 'purple
<primary>gen_random_uuid</primary>
</indexterm>
+ <indexterm>
+ <primary>gen_uuid_v7</primary>
+ </indexterm>
+
<para>
- <productname>PostgreSQL</productname> includes one function to generate a UUID:
+ <productname>PostgreSQL</productname> includes three functions to generate a UUID:
<synopsis>
<function>gen_random_uuid</function> () <returnvalue>uuid</returnvalue>
</synopsis>
This function returns a version 4 (random) UUID. This is the most commonly
used type of UUID and is appropriate for most applications.
+<synopsis>
+<function>gen_uuid_v7</function> () <returnvalue>uuid</returnvalue>
+</synopsis>
+ This function returns a version 7 (time-ordered + random) UUID.
</para>
<para>
diff --git a/src/backend/utils/adt/uuid.c b/src/backend/utils/adt/uuid.c
index 4f7aa768fd..fed0b1bc52 100644
--- a/src/backend/utils/adt/uuid.c
+++ b/src/backend/utils/adt/uuid.c
@@ -13,6 +13,9 @@
#include "postgres.h"
+#include <sys/time.h>
+
+#include "access/xlog.h"
#include "common/hashfn.h"
#include "lib/hyperloglog.h"
#include "libpq/pqformat.h"
@@ -421,3 +424,76 @@ gen_random_uuid(PG_FUNCTION_ARGS)
PG_RETURN_UUID_P(uuid);
}
+
+static uint32_t sequence_counter;
+static uint64_t previous_timestamp = 0;
+
+
+Datum
+gen_uuid_v7(PG_FUNCTION_ARGS)
+{
+ pg_uuid_t *uuid = palloc(UUID_LEN);
+ uint64_t tms;
+ struct timeval tp;
+
+ gettimeofday(&tp, NULL);
+
+ tms = ((uint64_t)tp.tv_sec) * 1000 + (tp.tv_usec) / 1000;
+
+ tms = pg_hton64(tms<<16);
+
+ /* Fill in time part */
+ memcpy(&uuid->data[0], &tms, 6);
+
+ if (tms == previous_timestamp)
+ {
+ /* Time did not change from the previous generation, we must increment counter */
+ ++sequence_counter;
+ /* fill everything after the timestamp and counter with random bytes */
+ if (!pg_strong_random(&uuid->data[8], UUID_LEN - 8))
+ ereport(ERROR,
+ (errcode(ERRCODE_INTERNAL_ERROR),
+ errmsg("could not generate random values")));
+
+ /* most significant 4 bits of 18-bit counter */
+ uuid->data[6] = (unsigned char)(sequence_counter >> 14);
+ /* next 8 bits */
+ uuid->data[7] = (unsigned char)(sequence_counter >> 6);
+ /* least significant 6 bits */
+ uuid->data[8] = (unsigned char)(sequence_counter);
+ }
+ else
+ {
+ /* fill everything after the timestamp with random bytes */
+ if (!pg_strong_random(&uuid->data[6], UUID_LEN - 6))
+ ereport(ERROR,
+ (errcode(ERRCODE_INTERNAL_ERROR),
+ errmsg("could not generate random values")));
+
+ /*
+ * Left-most counter bits are initialized as zero for the sole purpose
+ * of guarding against counter rollovers.
+ * See section "Fixed-Length Dedicated Counter Seeding"
+ * https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis-09#monotonicity_counters
+ */
+ uuid->data[6] = (uuid->data[6] & 0xf7);
+
+ sequence_counter = ((uint32_t)uuid->data[8] & 0x3f) +
+ (((uint32_t)uuid->data[7]) << 6) +
+ (((uint32_t)uuid->data[6] & 0x0f) << 14);
+
+ previous_timestamp = tms;
+ }
+
+ /*
+ * Set magic numbers for a "version 7" (pseudorandom) UUID, see
+ * http://tools.ietf.org/html/rfc ???
+ * https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format#name-creating-a-uuidv7-value
+ */
+ /* set version field, top four bits are 0, 1, 1, 1 */
+ uuid->data[6] = (uuid->data[6] & 0x0f) | 0x70;
+ /* set variant field, top two bits are 1, 0 */
+ uuid->data[8] = (uuid->data[8] & 0x3f) | 0x80;
+
+ PG_RETURN_UUID_P(uuid);
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 12fac15ceb..4e6089060a 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -9125,6 +9125,9 @@
{ oid => '3432', descr => 'generate random UUID',
proname => 'gen_random_uuid', proleakproof => 't', provolatile => 'v',
prorettype => 'uuid', proargtypes => '', prosrc => 'gen_random_uuid' },
+{ oid => '3813', descr => 'generate UUID version 7',
+ proname => 'gen_uuid_v7', proleakproof => 't', provolatile => 'v',
+ prorettype => 'uuid', proargtypes => '', prosrc => 'gen_uuid_v7' },
# pg_lsn
{ oid => '3229', descr => 'I/O',
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index a1bdf2c0b5..3141183b01 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -857,6 +857,7 @@ sha384(bytea)
sha512(bytea)
gen_random_uuid()
starts_with(text,text)
+gen_uuid_v7()
macaddr8_eq(macaddr8,macaddr8)
macaddr8_lt(macaddr8,macaddr8)
macaddr8_le(macaddr8,macaddr8)
diff --git a/src/test/regress/expected/uuid.out b/src/test/regress/expected/uuid.out
index 8e7f21910d..fc9f50e69e 100644
--- a/src/test/regress/expected/uuid.out
+++ b/src/test/regress/expected/uuid.out
@@ -168,5 +168,15 @@ SELECT count(DISTINCT guid_field) FROM guid1;
2
(1 row)
+-- generation test for v7
+TRUNCATE guid1;
+INSERT INTO guid1 (guid_field) VALUES (gen_uuid_v7());
+INSERT INTO guid1 (guid_field) VALUES (gen_uuid_v7());
+SELECT count(DISTINCT guid_field) FROM guid1;
+ count
+-------
+ 2
+(1 row)
+
-- clean up
DROP TABLE guid1, guid2 CASCADE;
diff --git a/src/test/regress/sql/uuid.sql b/src/test/regress/sql/uuid.sql
index 9a8f437c7d..02b8e7f10c 100644
--- a/src/test/regress/sql/uuid.sql
+++ b/src/test/regress/sql/uuid.sql
@@ -85,5 +85,11 @@ INSERT INTO guid1 (guid_field) VALUES (gen_random_uuid());
INSERT INTO guid1 (guid_field) VALUES (gen_random_uuid());
SELECT count(DISTINCT guid_field) FROM guid1;
+-- generation test for v7
+TRUNCATE guid1;
+INSERT INTO guid1 (guid_field) VALUES (gen_uuid_v7());
+INSERT INTO guid1 (guid_field) VALUES (gen_uuid_v7());
+SELECT count(DISTINCT guid_field) FROM guid1;
+
-- clean up
DROP TABLE guid1, guid2 CASCADE;
--
2.37.1 (Apple Git-137.1)
view thread (14+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: UUID v7
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox