scru128

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

SCRU128 ID is yet another attempt to supersede UUID in the use cases that need decentralized, globally unique time-ordered identifiers. SCRU128 is inspired by ULID and KSUID and has the following features:

• 128-bit unsigned integer type
• Sortable by generation time (as integer and as text)
• 26-character case-insensitive portable textual representation
• 44-bit biased millisecond timestamp that ensures remaining life of 550 years
• Up to 268 million time-ordered but unpredictable unique IDs per millisecond
• 84-bit layered randomness for collision resistance

import { scru128 } from "scru128";

console.log(scru128()); // e.g. "00PGHAJ3Q9VAJ7IU6PQBHBUAK4"
console.log(scru128()); // e.g. "00PGHAJ3Q9VAJ7KU6PQ92NVBTV"

Design

A SCRU128 ID is a 128-bit unsigned integer consisting of four terms:

timestamp * 2^84 + counter * 2^56 + per_sec_random * 2^32 + per_gen_random

Where:

• timestamp is a 44-bit unix time in milliseconds biased by 50 years (i.e. milliseconds elapsed since 2020-01-01 00:00:00+00:00, ignoring leap seconds).
• counter is a 28-bit counter incremented by one for each ID generated within the same timestamp (reset to a random number every millisecond).
• per_sec_random is a 24-bit random number refreshed only once per second.
• per_gen_random is a 32-bit random number renewed per generation of a new ID.

This is essentially equivalent to allocating four unsigned integer fields to a 128-bit space as follows in a big-endian system, and thus it is easily implemented with binary operations.

Bit numbers	Field name	Size	Data type
Msb 0 - 43	timestamp	44 bits	Unsigned integer
Msb 44 - 71	counter	28 bits	Unsigned integer
Msb 72 - 95	per_sec_random	24 bits	Unsigned integer
Msb 96 - 127	per_gen_random	32 bits	Unsigned integer

Layered randomness

SCRU128 utilizes monotonic counter to guarantee the uniqueness of IDs with the same timestamp; however, this mechanism does not ensure the uniqueness of IDs generated by multiple generators that do not share a counter state. SCRU128 relies on random numbers to avoid such collisions.

For a given length of random bits, the greater the number of random numbers generated, the higher the probability of collision. Therefore, 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.

That being said, the per_sec_random field is refreshed every second to prevent potential attackers from using this field as a generator's fingerprint. Also, the 32-bit per_gen_random field is reset to a new random number whenever an ID is generated to make sure the adjacent IDs generated within the same timestamp are not predictable.

Textual representation

A SCRU128 ID is encoded in a string as a 128-bit unsigned integer denoted in the radix of 32 using the digits of [0-9A-V], with leading zeros added to form a 26-digit canonical representation. Converters for this simple base 32 notation are widely available in many languages; even if not, it is easily implemented with bitwise operations by translating each 5-bit group into one digit of [0-9A-V], from the least significant digit to the most. Since the three most significant bits are mapped to one of [0-7], any numeral greater than 7VVVVVVVVVVVVVVVVVVVVVVVVV is not a valid SCRU128 ID.

Note that this is different from some binary-to-text encodings referred to as base32 or base32hex (e.g. RFC 4648), which read and translate 5-bit groups from the most significant one to the least.

License

Copyright 2021 LiosK

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

See also

• scru128 - npm
• API Documentation
• Run tests on your browser