5 ms·

SCRU128: Sortable, Clock and Random number-based Unique identifier

49 points by andrenth 4y ago

aidenn0 4y ago
It drives me a bit nuts when people use a case-insensitive base-32 encoding that includes all of "I1lO0"
- stevesimmons 4y ago
  I use a format I call id25, with takes a time-sorted UUIDv7, and represents its 128 bits as 25 chars from a Base 35 alphabet which has 0-9, a-k, m-z. Since I could drop one char from Base 36, and still store 128 bits, I decided to drop the "l", to reduce ambiguity with "1". And since I used lower case letters, "o" and "0" look quite different.
  - noodlesUK 4y ago
    This sounds useful, do you have a library in any languages for this?
- layer8 4y ago
  The canonical form should also use lowercase, as that’s easier to read.
j-pb 4y ago
I don't get these "usable for 500 years" approaches. If you have an overflow condition you want to encounter (i.e. test) it often. 32bit miliseconds + 96 bit of real entropy is brute force resistant, and has a ~50 day overflow period. That's plenty for eyeball statistics and to make DB indices happy. Any more sophisticated analytics will require larger precision and timezoning anyways, so don't cram it into the ID and give it it's own field. Also don't muck with entropy. All these smart counter schemes are potential attack vectors and have a much higher collision probability. You're more likely to get a collision due to but flips in such a counting scheme than from two randomly colliding full entropy bitstrings.
- aseipp 4y ago
  The intent of these IDs is to be used e.g. as primary keys in a database, and the timestamp improves sortability, helping the database engine pack tuples that are related "in time" into the same pages, which decreases the need for seeks. You can't split the ID and timestamp fields apart; the intent is that they are spatially and temporally related.
  - layer8 4y ago
    You can use a composite primary key (TIMESTAMP, ID), no strict need to encode the timestamp into the ID.
  - j-pb 4y ago
    > and to make DB indices happy. You can do both, use a low precision timestamp with overflows in the ID to keep the index happy, and add a proper timestamp field for analytics. The 32 + 96 split is what postgres uses for example. I'd say that's a pretty good endorsement.
cabirum 4y ago
I think it should be customizable: let users pass the number of bits for time, and the number of bits for randomness. Maybe also add fixed bits for partitioning. 128 bits is often an overkill when dealing with single-digit rps.
danbruc 4y ago
Misses the most important section - why yet another monotonic UUID? What issues in order implementations does this one solve? And is it an actual improvement or does this one just pick a different trade off?
noodlesUK 4y ago
See also: uuidv6-8 which are described here. They are uuids that are timestamp based and ordered. https://www.ietf.org/archive/id/draft-peabody-dispatch-new-uuid-format-01.html https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...
timcavel 4y ago
time.monotonic_ns() may be more appropriate than datetime.datetime.now().timestamp()
throwaway81523 4y ago
> SCRU128 gives some random bits a longer life to reduce the number of random number generation per a unit of time. As a result, even if each of multiple generators generates a million IDs at the same millisecond, no collision will occur as long as the random numbers generated only once per second (per_sec_random) differ. This is perplexing and I'd like to see the assumptions spelled out about how many such generators will run at the same time. If there are 1000s of generators, that almost guarantees occasional free collisions in the per-second field. If two such colliding generators each make a million ID's in the same millisecond, that basically guarantees full 72-bit collisions. Plus the monotonically increasing counter field can be a technical challenge in its own right. If you can generate those reliably and want to make the uuid's opaque to attackers, you might as well just encrypt a 64-bit monotonic counter with a 128 bit block cipher, with your db able to decrypt the counter for indexing purposes.

49 points by andrenth 4y ago

aidenn0 4y ago

It drives me a bit nuts when people use a case-insensitive base-32 encoding that includes all of "I1lO0"

stevesimmons 4y ago
I use a format I call id25, with takes a time-sorted UUIDv7, and represents its 128 bits as 25 chars from a Base 35 alphabet which has 0-9, a-k, m-z. Since I could drop one char from Base 36, and still store 128 bits, I decided to drop the "l", to reduce ambiguity with "1". And since I used lower case letters, "o" and "0" look quite different.
- noodlesUK 4y ago
  This sounds useful, do you have a library in any languages for this?
layer8 4y ago
The canonical form should also use lowercase, as that’s easier to read.

j-pb 4y ago

I don't get these "usable for 500 years" approaches. If you have an overflow condition you want to encounter (i.e. test) it often. 32bit miliseconds + 96 bit of real entropy is brute force resistant, and has a ~50 day overflow period. That's plenty for eyeball statistics and to make DB indices happy. Any more sophisticated analytics will require larger precision and timezoning anyways, so don't cram it into the ID and give it it's own field. Also don't muck with entropy. All these smart counter schemes are potential attack vectors and have a much higher collision probability. You're more likely to get a collision due to but flips in such a counting scheme than from two randomly colliding full entropy bitstrings.

aseipp 4y ago
The intent of these IDs is to be used e.g. as primary keys in a database, and the timestamp improves sortability, helping the database engine pack tuples that are related "in time" into the same pages, which decreases the need for seeks. You can't split the ID and timestamp fields apart; the intent is that they are spatially and temporally related.
- layer8 4y ago
  You can use a composite primary key (TIMESTAMP, ID), no strict need to encode the timestamp into the ID.
- j-pb 4y ago
  > and to make DB indices happy. You can do both, use a low precision timestamp with overflows in the ID to keep the index happy, and add a proper timestamp field for analytics. The 32 + 96 split is what postgres uses for example. I'd say that's a pretty good endorsement.

cabirum 4y ago

I think it should be customizable: let users pass the number of bits for time, and the number of bits for randomness. Maybe also add fixed bits for partitioning. 128 bits is often an overkill when dealing with single-digit rps.

danbruc 4y ago

Misses the most important section - why yet another monotonic UUID? What issues in order implementations does this one solve? And is it an actual improvement or does this one just pick a different trade off?

noodlesUK 4y ago

See also: uuidv6-8 which are described here. They are uuids that are timestamp based and ordered. https://www.ietf.org/archive/id/draft-peabody-dispatch-new-uuid-format-01.html https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...

timcavel 4y ago

time.monotonic_ns() may be more appropriate than datetime.datetime.now().timestamp()

throwaway81523 4y ago

> SCRU128 gives some random bits a longer life to reduce the number of random number generation per a unit of time. As a result, even if each of multiple generators generates a million IDs at the same millisecond, no collision will occur as long as the random numbers generated only once per second (per_sec_random) differ. This is perplexing and I'd like to see the assumptions spelled out about how many such generators will run at the same time. If there are 1000s of generators, that almost guarantees occasional free collisions in the per-second field. If two such colliding generators each make a million ID's in the same millisecond, that basically guarantees full 72-bit collisions. Plus the monotonically increasing counter field can be a technical challenge in its own right. If you can generate those reliably and want to make the uuid's opaque to attackers, you might as well just encrypt a 64-bit monotonic counter with a 128 bit block cipher, with your db able to decrypt the counter for indexing purposes.