Small UID

Small UID is a small, url-safe, user-friendly unique, lexicographically sortable id generator.

UUIDs are frequently used as database Primary Key in software development. However, they aren't the best choice mainly due to their random sorting and the resulting fragmentation in databases indexes.

UUIDs are frequently used as database Primary Key in software development. However, they aren't the best choice mainly due to their random sorting and the resulting fragmentation in databases indexes.

Using ULIDs is generally a very good alternative, solving most of UUID flaws.

Twitter's Snowflake is another option if you want to generate roughly sortable uid. But, Snowflake is not using random numbers instead it used machine id to generate the uid. It's a good choice if you integrate it into a distributed systems and doesn't really need randomness.

Small UIDs are also an ideal alternative when you do not need as much uniqueness and want shorter "user-friendly" encoded strings.

Introduction

Small UIDs are short unique identifiers especially designed to be used as efficient database Primary Key:

• Half smaller than UUID / ULID (64-bit)
• Lexicographically sortable
• Encodable as a short user-friendly and URL-safe base-64 string (a-zA-Z0-9_-)
• User-friendly strings are generated in a way to be always very different (no shared prefix due to similar timestamps)

* theorical number of generated uids before the first expected collision.
** the uid includes a timestamp, so collisions may occur only during the same millisecond.
*** monotonic sort order, but random order when generated at the same millisecond.

They are internally stored as 64-bit integers (44-bit timestamp followed by 20 random bits)

The random number suffix still guarantees a decent amount of uniqueness when many ids are created in the same millisecond (up to 1,048,576 different values) and you may only expect collision if you're generating more than 1024 random ids during the same millisecond.

Sorting

Because of the sequential timestamp, Small UIDs are naturally sorted chronologically. It improves indexing when inserting values in databases, new ids being appended to the end of the table without reshuffling existing data (read more in this article).

However, sort order within the same millisecond is not guaranteed because of the random bits suffix.

This project is loose reimplementation of Small-UID by Mediagone with the only difference is the string encoding for this one is base64-url instead of base62 for enabling wider usecases.

Monotonicity

Standard Small UID, as you already read, provide monotonicity beetween millisecond.

In the rust version I made a guaranteed monotonic version that replace the first 10-bit of randomness with increment value, basically capping generation to 1024/S.

Tell me if anyone want a version with only increment.

Rust

Wasm

You might need to add cargo config for getrandom.

[target.wasm32-unknown-unknown]
rustflags = ['--cfg', 'getrandom_backend="wasm_js"']

Example

Rust

Generating Small UIDs

use small_uid::SmallUid;

let smalluid1 = SmallUid::new();
let smalluid2 = SmallUid::try_from("GSntNvOw6n8".to_string()).unwrap();

Converting Small UIDs

use small_uid::SmallUid;

let smalluid = SmallUid::new();
let uid_string = smalluid.to_string();

Generating Monotonic Small UIDs

use small_uid::SmallUid;

let mut generator = SmallUid::init_monotonic();
let id = generator.generate();
let id2 = generator.generate();
assert!(id2 > id);

Typescript

Generating Small UIDs

import { SmallUid } from "@al-ula/small-uid";

const uid = SmallUid.gen();
console.log(uid.string); // prints the base64url encoded string
console.log(uid.value); // prints the underlying integer value

Generating Small UIDs from a 64-bit integer

const smallUidValue: bigint = 0x123456789abcdefn;
const uid = new SmallUid(smallUidValue);
console.log(uid.string); // prints the base64url encoded string
console.log(uid.value); // prints the underlying numeric value

Generating Small UIDs from a string

const smallUidString = "XxXxXxXxXxX";
const uid = new SmallUid(smallUidString);
console.log(uid.string); // prints the base64url encoded string
console.log(uid.value); // prints the underlying numeric value

Version 1.0.0 when?

This library is considered API stable and ready for production use. There will be no breaking changes to the API except for critical issues.

But I still want to implement monotonicity. The v1 release will be done when I'm finished implementing monotonicity.