Re: UUID v7

From: "Andrey M(dot) Borodin" <x4mmm(at)yandex-team(dot)ru>
To: Peter Eisentraut <peter(at)eisentraut(dot)org>
Cc: Aleksander Alekseev <aleksander(at)timescale(dot)com>, pgsql-hackers mailing list <pgsql-hackers(at)postgresql(dot)org>, Sergey Prokhorenko <sergeyprokhorenko(at)yahoo(dot)com(dot)au>, Jelte Fennema-Nio <postgres(at)jeltef(dot)nl>, Przemysław Sztoch <przemyslaw(at)sztoch(dot)pl>, "David G(dot) Johnston" <david(dot)g(dot)johnston(at)gmail(dot)com>, Mat Arye <mat(at)timescaledb(dot)com>, Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com>, Nikolay Samokhvalov <samokhvalov(at)gmail(dot)com>, Junwang Zhao <zhjwpku(at)gmail(dot)com>
Subject: Re: UUID v7
Date: 2024-04-04 18:12:10
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

> On 4 Apr 2024, at 18:45, Peter Eisentraut <peter(at)eisentraut(dot)org> wrote:
> On 26.03.24 18:26, Andrey M. Borodin wrote:
>>> Also, you are initializing 4 bits (I think?) to zero to guard against counter rollovers (so it's really just an 8 bit counter?). But nothing checks against such rollovers, so I don't understand the use of that.
>> No, there's only one guard rollover bit.
>> Here: uuid->data[6] = (uuid->data[6] & 0xf7);
>> Bits that are called "guard bits" do not guard anything, they just ensure counter capacity when it is initialized.
> Uh, I guess I don't understand this at all. I tried to dig up some information about this, but didn't find anything. What exactly is the mechanism of these "counter rollover guards"? If they don't guard anything, what are they supposed to accomplish?

My understanding of guard bits is the following: on every UUID generation, when time is advancing, counter bits are initialized with random numbers, except guard bits. Guard bits are always initialized with zeroes.

Let's consider we have a 1-byte counter with 4 guard bits and 4 normal bits.
If we generate some UUIDs at the very same millisecond we might have following counter values:

0C <--- lower nibble is initialized with random 4 bits C.

If we have no these guard bits we might get random numbers that are immifiately at the end of a range of allowed values:

FE <--- first UUID at given millisecond
00 <--- rollover to next millisecond

If we have 1 guard bit and 7 normal bits we get at worst 128 values before rollover to next millisecond.
If we have 2 guard bits and 6 normal bits this guaranty is extended to 192.
3/5 will guaranty capacity of 224.
But usefulness of every next guard bits decreases, so I think there is a point in only one.

That's my understanding of guard bits in the counter. Please correct me if I'm wrong.

At this point we can skip the counter\microseconds entirely, just fill everything after unix_ts_ms with randomness. It's still a valid UUIDv7, exhibiting much more data locality than UUIDv4. We can adjust this sortability measures later.

Best regards, Andrey Borodin.

In response to

  • Re: UUID v7 at 2024-04-04 13:45:21 from Peter Eisentraut


  • Re: UUID v7 at 2024-04-06 21:59:38 from Sergey Prokhorenko

Browse pgsql-hackers by date

  From Date Subject
Next Message Jacob Champion 2024-04-04 18:12:18 Re: WIP Incremental JSON Parser
Previous Message Tom Lane 2024-04-04 18:06:50 Re: [EXTERNAL] Re: Add non-blocking version of PQcancel