cockroachdb / cockroachdb/cockroach
builtins: `GenerateUniqueID` could theoretically generate collisions
- 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
Assessment
This issue has not been assessed yet.