cockroachdb / cockroachdb/cockroach

builtins: `GenerateUniqueID` could theoretically generate collisions

Open
#108,050 3 comments 0 reactions 0 assignees View on GitHub
A-sql-builtins C-bug T-sql-foundations
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

The `GenerateUniqueID` function, which underlies the `unique_rowid` and `unordered_unique_rowid` builtins could theoretically generate collisions.

The generated unique ID is a 64-bit integer where the leading bit is zero, followed by 48 bits for the timestamp, and 15 bits for the instance ID.

The timestamp is guaranteed to be unique by `GenerateUniqueInt` by using a mutex-protected variable:
https://github.com/cockroachdb/cockroach/blob/05dd384b26e3786b2f1e7d0abbe2a9fa043f18fb/pkg/sql/sem/builtins/builtins.go#L9846-L9851

However, when the instance ID exceeds 32K, it is bitwise XOR-ed with the timestamp:
https://github.com/cockroachdb/cockroach/blob/05dd384b26e3786b2f1e7d0abbe2a9fa043f18fb/pkg/sql/sem/builtins/builtins.go#L9858-L9863

This theoretically allows for collisions to occur.

Consider the following example:
``` go
func TestGenerateUniqueID(t *testing.T) {
a := GenerateUniqueID(0b0000000000000001, 0b10)
b := GenerateUniqueID(0b1000000000000001, 0b11)
c := fmt.Sprintf("%064b", a)
d := fmt.Sprintf("%064b", b)
require.NotEqual(t, c, d)
}
```

This fails since after the XOR, the resulting value is the same:
```
0 000000000000000000000000000000000000000000000011
XOR
1 000000000000001
=
0 000000000000000000000000000000000000000000000010 000000000000001

0 000000000000000000000000000000000000000000000010
XOR
0 000000000000001
=
0 000000000000000000000000000000000000000000000010 000000000000001
```

Jira issue: CRDB-30300

Epic CRDB-60946

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.