Skip to content
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.

Sign up for GitHub

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

Merged
merged 9 commits into from
Jan 11, 2024
Merged

fix: Monotonicity in UUIDv7 #150

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
9 commits
Select commit Hold shift + click to select a range
960071a
Monotonicity in UUIDv7
it512 Jan 9, 2024
f27ed75
Merge branch 'master' into monotonicity
it512 Jan 9, 2024
654bc6c
fix Monotonicity
it512 Jan 10, 2024
64f9de4
Merge branch 'monotonicity' of http://47.75.211.166:5080/https://gith…
it512 Jan 10, 2024
5986a71
fix comment
it512 Jan 10, 2024
4b1aab9
Monotonicity 2
it512 Jan 11, 2024
314e206
lock
it512 Jan 11, 2024
8888abc
fix comment
it512 Jan 11, 2024
a6e034a
fix comment
it512 Jan 11, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
fix Monotonicity
  • Loading branch information
@it512
it512 committed Jan 10, 2024
commit 654bc6c0d0f45007617661302b0a9dbd2b30915c
4 changes: 0 additions & 4 deletions time.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,8 +27,6 @@ var (
lasttime uint64 // last time we returned
clockSeq uint16 // clock sequence for this run

lasttimev7 int64 // for uuid v7

timeNow = time.Now // for testing
)

Expand Down Expand Up @@ -89,7 +87,6 @@ func clockSequence() int {
}

// SetClockSequence sets the clock sequence to the lower 14 bits of seq
Copy link
Collaborator

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.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

fixed

// uuid v1 and v6 use 14 bits seq. uuid v7 use 12 bits seq.
// Setting to -1 causes a new sequence to be generated.
func SetClockSequence(seq int) {
defer timeMu.Unlock()
Expand All @@ -107,7 +104,6 @@ func setClockSequence(seq int) {
clockSeq = uint16(seq&0x3fff) | 0x8000 // Set our variant
if oldSeq != clockSeq {
lasttime = 0
lasttimev7 = 0
}
}

Expand Down
23 changes: 7 additions & 16 deletions uuid_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -874,39 +874,30 @@ func TestVersion7_pooled(t *testing.T) {
func TestVersion7FromReader(t *testing.T) {
myString := "8059ddhdle77cb52"
r := bytes.NewReader([]byte(myString))
r2 := bytes.NewReader([]byte(myString))
uuid1, err := NewV7FromReader(r)
_, err := NewV7FromReader(r)
if err != nil {
t.Errorf("failed generating UUID from a reader")
}
_, err = NewV7FromReader(r)
if err == nil {
t.Errorf("expecting an error as reader has no more bytes. Got uuid. NewV7FromReader may not be using the provided reader")
}
uuid3, err := NewV7FromReader(r2)
if err != nil {
t.Errorf("failed generating UUID from a reader")
}
if uuid1 == uuid3 { // Montonicity
t.Errorf("expected duplicates, got %q and %q", uuid1, uuid3)
}
}

func TestVersion7Monotonicity(t *testing.T) {
length := 4097 // [0x000 - 0xfff]
myString := "8059ddhdle77cb52"

SetClockSequence(0)
length := 1000

uuids := make([]string, length)
for i := 0; i < length; i++ {
uuidString, _ := NewV7FromReader(bytes.NewReader([]byte(myString)))
uuidString, _ := NewV7()
uuids[i] = uuidString.String()
time.Sleep(time.Millisecond)
Copy link
Collaborator

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.

//time.Sleep(time.Millisecond / 50)
}

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])
if uuids[i-1] >= uuids[i] {
t.Errorf("unexpected seq got %s >= %s", uuids[i-1], uuids[i])
}
}
}
23 changes: 3 additions & 20 deletions version7.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,7 +20,6 @@ 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
func NewV7() (UUID, error) {
uuid, err := NewRandom()
if err != nil {
Expand Down Expand Up @@ -53,7 +52,7 @@ func makeV7(uuid []byte) {
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| unix_ts_ms |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| unix_ts_ms | ver |rand_a (12 bit counter)|
| unix_ts_ms | ver | rand_a (12 bit seq) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var| rand_b |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Expand All @@ -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
Copy link
Collaborator

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
}


uuid[0] = byte(t >> 40)
uuid[1] = byte(t >> 32)
Expand All @@ -74,20 +74,3 @@ func makeV7(uuid []byte) {
uuid[6] = 0x70 | (0x0F & byte(s>>8))
uuid[7] = byte(s)
}

func getTimeV7() (int64, uint16) {

defer timeMu.Unlock()
timeMu.Lock()

if clockSeq == 0 {
setClockSequence(-1)
}
now := timeNow().UnixMilli()

if now <= lasttimev7 {
clockSeq = clockSeq + 1
}
lasttimev7 = now
return now, clockSeq
}