-
Notifications
You must be signed in to change notification settings - Fork 372
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
fix: Monotonicity in UUIDv7 #150
Conversation
🤖 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 -- conventional-commit-lint bot |
uuid_test.go
Outdated
@@ -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) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
this message is no longer accurate.
uuid_test.go
Outdated
} | ||
|
||
for i := 1; i < len(uuids); i++ { | ||
if uuids[i-1] > uuids[i] { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Should this be >= ?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ok
version7.go
Outdated
@@ -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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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.
version7.go
Outdated
uuid[7] = byte(s) | ||
} | ||
|
||
func getTimeV7() (int64, uint16) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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)
uuid_test.go
Outdated
|
||
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]) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
s/expected/unexpected
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ok
Thank you for review, fixed |
uuid_test.go
Outdated
for i := 0; i < length; i++ { | ||
uuidString, _ := NewV7() | ||
uuids[i] = uuidString.String() | ||
time.Sleep(time.Millisecond) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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.
version7.go
Outdated
@@ -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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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
}
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
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
time.go
Outdated
@@ -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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The period was lost here. In general, do not reformat comments unless they are incorrect.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
fixed
I advise you to take the following implementations as an example: |
Thanks for your work on this @it512! |
* Monotonicity in UUIDv7 * fix Monotonicity * fix comment * Monotonicity 2 * lock * fix comment * fix comment
Monotonicity in UUIDv7
#148