UUID

  • 128 bits of randomness (36 characters)
  • UUID v1/v2 requires access to a unique, stable MAC address
  • UUID v3/v5 requires a unique seed and produces randomly distributed IDs
  • UUID v4 provides no other information than randomness

MongoDB’s ObjectId

ObjectId

The 12-byte ObjectId consists of:

  • A 4-byte timestamp, representing the ObjectId’s creation, measured in seconds since the Unix epoch.
  • A 5-byte random value generated once per process. This random value is unique to the machine and process.
  • A 3-byte incrementing counter, initialized to a random value.

Twitter Snowflake (archive)

Snowflake is a network service for generating unique ID numbers at high scale

  • Time Ordered
  • under 64bits
  • id is composed of:
    • time - 41 bits (millisecond precision w/ a custom epoch gives us 69 years)
    • configured machine id - 10 bits - gives us up to 1024 machines
    • sequence number - 12 bits - rolls over every 4096 per machine (with protection to avoid rollover in the same ms)

Instagram IDs

Sharding & IDs at Instagram

Delegate ID creation to each table inside each shard, by using PL/PGSQL.

Each of IDs consists of:

  • 41 bits for time in milliseconds (gives us 41 years of IDs with a custom epoch)
  • 13 bits that represent the logical shard ID
  • 10 bits that represent an auto-incrementing sequence, modulus 1024. This means we can generate 1024 IDs, per shard, per millisecond

ksuid

K-Sortable Unique IDentifier

  • Time Ordered
  • Binary KSUIDs are 20-bytes:
    • a 32-bit unsigned integer UTC timestamp. The timestamp epoch is adjusted to May 13th, 2014, providing over 100 years of life.
    • a 128-bit randomly generated payload.
  • The text representation is always 27 characters, encoded in alphanumeric base62 that will lexicographically sort by timestamp.
# generate a KSUID and inspect its components
$ ksuid -f inspect

REPRESENTATION:

  String: 0ujzPyRiIAffKhBux4PvQdDqMHY
     Raw: 066A029C73FC1AA3B2446246D6E89FCD909E8FE8

COMPONENTS:

       Time: 2017-10-09 21:46:20 -0700 PDT
  Timestamp: 107610780
    Payload: 73FC1AA3B2446246D6E89FCD909E8FE8

ulid

https://github.com/ulid/spec

  • Lexicographically sortable
  • Canonically encoded as a 26 character string, uses Crockford's base32 (case insensitive)
  • 128-bit:
    • Timestamp: 48 bit integer, UNIX-time in milliseconds. Won’t run out of space ‘til the year 10889 AD.
    • Randomness: 80 bits. Cryptographically secure source of randomness, if possible
 01AN4Z07BY      79KA1307SR9X4MV3

|----------|    |----------------|
 Timestamp          Randomness
   48bits             80bits

Other impl

  • https://github.com/ericelliott/cuid

Prior Art

  • https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
  • https://firebase.googleblog.com/2015/02/the-2120-ways-to-ensure-unique_68.html