> On 4 Apr 2024, at 18:45, Peter Eisentraut <pe...@eisentraut.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.
0D
0E
0F
10
11
12
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
FF
00 <--- rollover to next millisecond
01
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.
