fix: Monotonicity in UUIDv7 #150

it512 · 2024-01-09T15:11:52Z

Monotonicity in UUIDv7
#148

conventional-commit-lint-gcf · 2024-01-09T16:34:39Z

🤖 I detect that the PR title and the commit message differ and there's only one commit. To use the PR title for the commit history, you can use Github's automerge feature with squashing, or use automerge label. Good luck human!

-- conventional-commit-lint bot
https://conventionalcommits.org/

bormanp · 2024-01-10T02:36:59Z

uuid_test.go

@@ -887,7 +887,26 @@ func TestVersion7FromReader(t *testing.T) {
 	if err != nil {
 		t.Errorf("failed generating UUID from a reader")
 	}
-	if uuid1 != uuid3 {
+	if uuid1 == uuid3 { // Montonicity
 		t.Errorf("expected duplicates, got %q and %q", uuid1, uuid3)


this message is no longer accurate.

bormanp · 2024-01-10T02:38:14Z

uuid_test.go

+	}
+
+	for i := 1; i < len(uuids); i++ {
+		if uuids[i-1] > uuids[i] {


Should this be >= ?

bormanp · 2024-01-10T02:40:33Z

version7.go

@@ -20,6 +20,7 @@ import (
 // NewV7 returns a Version 7 UUID based on the current time(Unix Epoch).
 // Uses the randomness pool if it was enabled with EnableRandPool.
 // On error, NewV7 returns Nil and an error
+// Note: this implement only has 12 bit seq, maximum of 4096 uuids are generated in 1 milliseconds


As I understand it, this is not a limitation of the implementation but rather of the standard.

// Note: Version 7 UUIDs have a 12 bit sequence number limiting the number of // unique UUIDs to 4096 in 1 millesecond.

bormanp · 2024-01-10T03:06:12Z

version7.go

+	uuid[7] = byte(s)
+}
+
+func getTimeV7() (int64, uint16) {


I don 't think this is quite right. Maybe something along the lines of:

now := time.Now().UnixNano() milli := now / 1000 seq := (now - milli * 1000) << 2 // use the upper 10 bits

There is nothing in the standard that requires Version 7 UUIDs to be monotonically increasing within a given millisecond but it is acceptable to use sub-millisecond values. It is also legitimate for the first 64 bits of two Version 7 UUIDs to be identical. The randomness in the last 62 bits is what makes them unique.

I misread part of the standard, it should be monotonic, but the above is still basically correct. What you need to do is have a protected global variable:

now := time.Now().UnixNano() << 2 // time in 1/4 nanoseconds if now <= lastTime { now = lastTime + 1 } lastTime = now milli := now / 4000 seq := now - milli * 4000

By using 1/4 nanoseconds we can generate 4 UUIDs within a nanosecond that do not cause us to return a time that is actually in the future by a nanosecond.

v7 using millisecond (1/1000) timestamp, we are using microsecond (1/1000000) lower 12 bit set to rand_a
1 millisecond can generate 4096 uuids

now := timeNow().UnixMicro() t, s := now/1000, now&4095 // 2^12-1, 12 bits uuid[6] = 0x70 | (0x0F & byte(s>>8)) uuid[7] = byte(s)

bormanp · 2024-01-10T03:06:44Z

uuid_test.go

+
+	for i := 1; i < len(uuids); i++ {
+		if uuids[i-1] > uuids[i] {
+			t.Errorf("expected seq  got %s > %s", uuids[i-1], uuids[i])


s/expected/unexpected

…ub.com/it512/uuid into monotonicity

it512 · 2024-01-10T07:23:02Z

Thank you for review, fixed

bormanp · 2024-01-10T19:35:44Z

uuid_test.go

+	for i := 0; i < length; i++ {
+		uuidString, _ := NewV7()
+		uuids[i] = uuidString.String()
+		time.Sleep(time.Millisecond)


This forces this single test to take a full second. A better test might be to force timeNow to return the same time on every call. You don't need to store all the UUIDs, just the last one:

u, _ := NewV7() lastUUID := u.String() for i := 0; i < length; i++ { u, _ := Newv7() nextUUID := u.String() if lastUUID >= nextUUID { t.Errorf("monotonicity failed at #%d: %s !< %s", i, lastUUID, nextUUID) break } }

You could also run this test again where timeNow returns time incrementing by say 100 nanoseconds per call and if you want to go crazy, where timeNow returns time going backwards.

bormanp · 2024-01-10T19:51:34Z

version7.go

@@ -62,7 +61,8 @@ func makeV7(uuid []byte) {
 	*/
 	_ = uuid[15] // bounds check

-	t, s := getTimeV7()
+	now := timeNow().UnixMicro()
+	t, s := now/1000, now&4095 // 2^12-1, 12 bits


so this can still return a UUID that is less than the previous UUID (two calls within the same microsecond).

The only way to guarantee an always increasing UUID is to remember the last time/sequence returned. Perhaps something like:

// lastV7time is the last last time we returned stored as: // // 52 bits of time in milliseconds since epoch // 12 bits of (fractional nanoseconds) >> 8 var lastV7time int64 const nanoPerMilli = 1000000 // getV7Time returns the time in milliseconds and nanoseconds / 256. // The returned (milli << 12 + seq) is guarenteed to be greater than // (milli << 12 + seq) returned by any previous call to getV7Time. func getV7Time() (milli, seq int64) { nano := timeNow().UnixNano() milli = nano / nanoPerMilli // Sequence number is between 0 and 3906 (nanoPerMilli>>8) seq = (nano - milli*nanoPerMilli) >> 8 now := milli<<12 + seq if now <= lastV7time { now = lastV7time + 1 milli = now >> 12 seq = now & 0xfff } lastV7time = now return milli, seq }

bormanp

Just a comment issue. Also the commit message did not follow Conventional Commits causing the presubmit tests to fail.

https://github.com/google/uuid/pull/150/checks?check_run_id=20377607744

bormanp · 2024-01-11T16:56:57Z

time.go

@@ -86,8 +86,8 @@ func clockSequence() int {
 	return int(clockSeq & 0x3fff)
 }

-// SetClockSequence sets the clock sequence to the lower 14 bits of seq.  Setting to
-// -1 causes a new sequence to be generated.
+// SetClockSequence sets the clock sequence to the lower 14 bits of seq


The period was lost here. In general, do not reformat comments unless they are incorrect.

sergeyprokhorenko · 2024-01-28T10:19:07Z

I advise you to take the following implementations as an example:
Rust
PostgreSQL
It is these implementations, created with the participation of the most important RFC contributors (LiosK and Sergey Prokhorenko), that are closest to understanding the RFC.

bensie · 2024-01-29T18:14:39Z

Thanks for your work on this @it512!

Monotonicity in UUIDv7

960071a

it512 requested a review from a team as a code owner January 9, 2024 15:11

it512 mentioned this pull request Jan 9, 2024

Monotonicity in UUIDv7 #148

Closed

it512 changed the title ~~Monotonicity in UUIDv7~~ feat: Monotonicity in UUIDv7 Jan 9, 2024

it512 changed the title ~~feat: Monotonicity in UUIDv7~~ Monotonicity in UUIDv7 Jan 9, 2024

Merge branch 'master' into monotonicity

f27ed75

bormanp requested changes Jan 10, 2024

View reviewed changes

it512 added 3 commits January 10, 2024 15:12

fix Monotonicity

654bc6c

Merge branch 'monotonicity' of http://47.75.211.166:5080/https://gith…

64f9de4

…ub.com/it512/uuid into monotonicity

fix comment

5986a71

bormanp requested changes Jan 10, 2024

View reviewed changes

it512 added 2 commits January 11, 2024 11:20

Monotonicity 2

4b1aab9

lock

314e206

bormanp reviewed Jan 11, 2024

View reviewed changes

fix comment

8888abc

it512 changed the title ~~Monotonicity in UUIDv7~~ fix: Monotonicity in UUIDv7 Jan 11, 2024

fix comment

a6e034a

bormanp approved these changes Jan 11, 2024

View reviewed changes

bormanp merged commit a2b2b32 into google:master Jan 11, 2024
6 checks passed

release-please bot mentioned this pull request Jan 11, 2024

chore(master): release 1.6.0 #151

Merged

it512 deleted the monotonicity branch January 12, 2024 00:12

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix: Monotonicity in UUIDv7 #150

fix: Monotonicity in UUIDv7 #150

it512 commented Jan 9, 2024 •

edited

conventional-commit-lint-gcf bot commented Jan 9, 2024

bormanp Jan 10, 2024

bormanp Jan 10, 2024

it512 Jan 10, 2024

bormanp Jan 10, 2024

bormanp Jan 10, 2024

bormanp Jan 10, 2024

it512 Jan 10, 2024

bormanp Jan 10, 2024

it512 Jan 10, 2024

it512 commented Jan 10, 2024

bormanp Jan 10, 2024

bormanp Jan 10, 2024

bormanp left a comment

bormanp Jan 11, 2024

it512 Jan 11, 2024

sergeyprokhorenko commented Jan 28, 2024

bensie commented Jan 29, 2024

fix: Monotonicity in UUIDv7 #150

fix: Monotonicity in UUIDv7 #150

Conversation

it512 commented Jan 9, 2024 • edited

conventional-commit-lint-gcf bot commented Jan 9, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

it512 commented Jan 10, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bormanp left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sergeyprokhorenko commented Jan 28, 2024

bensie commented Jan 29, 2024

it512 commented Jan 9, 2024 •

edited