Skip to content

Instantly share code, notes, and snippets.

@gnat

gnat/uuid_ulid_alternative.md

Last active June 14, 2024 19:48
Show Gist options
  • Save gnat/774bc540c0b300146cdedb0744bad081 to your computer and use it in GitHub Desktop.
Save gnat/774bc540c0b300146cdedb0744bad081 to your computer and use it in GitHub Desktop.
Download ZIP
64 bit ordered unique id.
Raw
uuid_ulid_alternative.md

Better Primary Keys / PK / id

Why not just use sequential ID's (SERIAL or AUTO INCREMENT) ?

  • Scaling writes require partitions / shards at some level.
    • Avoid SERIAL and AUTO INCREMENT from start.
      • Servers have to ask "what's the next available id in the sequence?" = huge global contention / slow down.
      • Turns into a queue. OK for 1 server. Bad for many servers.
        • Vitess and FoundationDB can work around this using sequence counters per server. Vitess one has an awful DX. Not sure about FoundationDB.
    • Alternative: Use time or random.
      • UUID bonus: Split, merge tables, and load any rows any time you wish, since rows are globally unique.

Up front reading.

Why this implementation?

  • ✅ Universal compatibility with all major databases.
    • No datatype converstions. Fits in 64 bit signed int.
      • Max value for Postgres, CockroachDB, SQLite, MySQL BIGINT is 9223372036854775807 (19 digit)
      • Enables unix timestamps to go up to 9223372036 (10 digits).
        • 9223372036 = Fri Apr 11 2262 23:47:16 GMT+0000
      • Similar to CockroachDB's unique_rowid(), but additionally allows you to extract the created_at time. Works with CockroachDB's INT type.
  • ✅ Easy selection with double clicking.
    • Copy and paste your ID's from your database/app and back!
  • ✅ Contains creation timestamp.
    • created_at in unix time is just the first 10 digits! No more extra column.
  • ✅ Base64 encode to get YouTube-esque id's instantly.
  • ✅ Configuration-free.
    • 🟠 Below 1 ms, 1 in 1,000,000 chance of collision, per table.
      • Downside of only 8 bytes.
      • ⚪ Solution A (Easy): Retry on collision. Good if IF NOT EXIST is not expensive. (Rare but will happen on high writes: 100,000 INSERT per second per table).
        • No worker / machine ID required!
        • Ideal solution at early scale. Can convert to Solution B or C or UUID later.
          • UUID would need table migration / backfill, but your timestamps would fit cleanly into UUID.
        • ScyllaDB 3.2+ can optionally fall back to Paxos / Raft for IF NOT EXIST (expensive).
      • 🔵 Solution B: Replace the random sequence with a worker ID from your environment (or database query on startup), and higher res time, so you get a legitimately unique sequence.
        • Only advantage is better collision prevention. Like Instagram's Snowflake.
        • Workers on the same server need to be unique... complexity.
      • 🟣 Solution C: Composite keys (Ex: server/day, server/channel) Discord uses ScyllaDB with INT8.

When to migrate to full 128 bit UUID v7 ?

  • UUIDv7 has 74 bits of randomness. The collision chance per millisecond is 18,446,744,073,709,551,616 to 1.
  • Only downside is ability to fit pages into RAM, and disk usage.
  • Are unique checks or retries or quorum very expensive in your database? ✅ Use 128 bit.
  • Planning over 100 database servers? ✅ Use 128 bit.
  • Are you running a cluster of ScyllaDB / Cassandra? ✅ Use 128 bit.
  • Planning a table to INSERT more than 10,000 / second? ✅ Use 128 bit.
  • Really want unique id's across all tables? ✅ Use 128 bit.

Key Sizes. Storage is the biggest reason to not use 128 bit primary keys right away.

Type Type Size Estimated Row Size Estimated Rows to Fill 1 TB Relative Size
INT / Classic Primary Key 32-bit
(4 byte)		 4 byte * 5 columns * 50 tables = 1,000 bytes 1,000,000,000,000 bytes / 1,000 = 1,000,000,000 rows per table. 1x 🔳⬜⬜⬜⬜⬜⬜⬜
BIGINT / Snowflake 64-bit
(8 byte)		 8 byte * 5 columns * 50 tables = 2,000 bytes 1,000,000,000,000 bytes / 2,000 = 500,000,000 rows per table. 2x 🔳🔳⬜⬜⬜⬜⬜⬜
UUID
(UUID / BYTES / BLOB)		 128-bit
(16 byte)		 16 byte * 5 columns * 50 tables = 4,000 bytes 1,000,000,000,000 bytes / 4,000 = 250,000,000 rows per table. 4x 🔳🔳🔳🔳⬜⬜⬜⬜
BASE64 (Push ID)
(TEXT / VARCHAR(255))		 160-bit
(20 byte)		 20 byte * 5 columns * 50 tables = 5,000 bytes 1,000,000,000,000 bytes / 5,000 = 200,000,000 rows per table. 5x 🔳🔳🔳🔳🔳⬜⬜⬜
BASE62 (Remove _-)
(TEXT / VARCHAR(255))		 176-bit
(22 byte)		 22 byte * 5 columns * 50 tables = 5,500 bytes 1,000,000,000,000 bytes / 5,500 = 182,000,000 rows per table. 6x 🔳🔳🔳🔳🔳🔳⬜⬜
ULID (BASE32)
(TEXT / VARCHAR(255))		 208-bit
(26 byte)		 26 byte * 5 columns * 50 tables = 6,500 bytes 1,000,000,000,000 bytes / 6,500 = 154,000,000 rows per table. 7x 🔳🔳🔳🔳🔳🔳🔳⬜
UUID (BASE16)
(TEXT / VARCHAR(255))		 256-bit
(32 byte)		 32 byte * 5 columns * 50 tables = 8,000 bytes 1,000,000,000,000 bytes / 8,000 = 125,000,000 rows per table. 8x 🔳🔳🔳🔳🔳🔳🔳🔳

Proposed Format Breakdown

🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦🟩🟩🟩🟪🟪🟪🟪🟪🟪

  • 🟦 Seconds. 10 digits. (Unix timestamp)
  • 🟩 Milliseconds. 3 digits.
  • 🟪 Nanoseconds (or random). 6 digits.
  • 64-bit signed for CockroachDB, Sqlite, Postgres compatibility.
  • Example Value: 1679261771328879830
  • 19 digits max. Max value: 9223372036854775807
  • Max Unix timestamp: 9223372036 (Fri Apr 11 2262 23:47:16 GMT+0000)
  • NTP generally isn't more accurate than 1 ms over a network.

ULID / UUIDv7 Format Breakdown

🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪🟪

  • 🟦 Timestamp. 48 bits.
  • 🟪 Random. 80 bits.

PHP

function unique_id() {
	# Goes up to 9223372036854775807 so we're safe until year 2262 unix time (9223372036).
	# T = Unix time.
	# M = Sub-second (Millisecond / nanosecond).
	# R = Random.
	# TTTTTTTTTTMMMMRRRRR
	# 9223372036854775807
	# 1679261771328879830 = Typical output.
	#
	# Fits inside SQLite int (64 bit signed) (max: 9223372036854775807)
	# 1 in 99,999 collision chance per millisecond.
	#
	# Warning: Do NOT use hrtime(). That's just arbitrary from system bootup.
	return str_replace('.', '', (number_format(microtime(true), 4, '.', '')).sprintf("%05d", rand(0,99999)));
}
  • Warning: Do NOT use PHP hrtime(). It's relative to system bootup, not a timestamp.

Python

def unique_id():
	# Goes up to 9223372036854775807 so we're safe until year 2262 unix time (9223372036).
	# T = Unix time.
	# M = Milliseconds.
	# R = Random.
	# TTTTTTTTTTMMMMRRRRR
	# 9223372036854775807
	# 1679261771328879830 = Typical output.
	#
	# Fits inside SQLite int (64 bit signed) (max: 9223372036854775807)
	# 1 in 99,999 collision chance per millisecond.
	#
	# time_ns() is ok to use!
	return f"{str(time.time_ns())[:14]}{str(random.randrange(0,99999)).rjust(5, '0')}"
  • Python time.time_ns() is okay, as it's from epoch.

Ph

def unique_id()
	# Goes up to 9223372036854775807 so we're safe until year 2262 unix time (9223372036).
	# T = Unix time.
	# M = Milliseconds.
	# R = Random.
	# TTTTTTTTTTMMMMRRRRR
	# 9223372036854775807
	# 1679261771328879830 = Typical output.
	#
	# Fits inside SQLite int (64 bit signed) (max: 9223372036854775807)
	# 1 in 99,999 collision chance per millisecond.
	#
	# Warning: Do NOT use hrtime(). That's just arbitrary from system bootup.
	return str_replace('.', '', (number_format(microtime(true), 4, '.', '')).sprintf("%05d", rand(0,99999)))

Other alternatives to consider.

Name Binary Size String Size Features
UUID 16 bytes 36 chars configuration free, not sortable
shortuuid 16 bytes 22 chars configuration free, not sortable
Snowflake 8 bytes up to 20 chars needs machine/DC configuration, needs central server, sortable
MongoID 12 bytes 24 chars configuration free, sortable
xid 12 bytes 20 chars configuration free, sortable
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment