Skip to content

Unique ID generation

How a system hands out ids that should never repeat: one counter, counters split into blocks, random UUIDs, time-ordered ids built from a clock and a machine number, or hashes checked against a unique key.

On this page

What it is

When a row, message or link needs an id, it must be one no other ever gets. On one machine this is easy: keep a number and add one. The hard part starts when many servers create things at once and you may also want them short, or sorted by when they were made. Each scheme below gives up a different thing to get there.

Auto-increment and sequences. The database keeps a counter and hands out the next value when asked, for example as a column default on insert. In PostgreSQL a sequence can preallocate a cache of values per session; values stay distinct across sessions, but they may come out of order, and cached values a session never used are lost when it ends, leaving gaps.

Counter blocks. A shared counter hands each server a whole block of values at once, and the server spends them locally. With Redis, a server can call INCRBY with the block size and get back the top of its new block in one step. Flickr went further with two MySQL ticket servers, one handing out odd numbers and the other even, so either can go down without stopping new ids.

UUIDs. A UUID is a 128-bit value. Version 4 fills 122 of those bits at random, so any machine can make one with no coordination; you would need about 2.71 quintillion of them for a 50% chance of a single repeat. Version 7 starts with a 48-bit Unix timestamp in milliseconds, so values sort roughly by creation time, which suits keys in large databases. PostgreSQL ships both as uuidv4() and uuidv7().

Snowflake-style ids. Twitter’s Snowflake, announced in 2010, packs a 64-bit id from 41 bits of milliseconds since a chosen epoch, a 10-bit machine id and a 12-bit sequence, so each machine can make 2^12 = 4,096 ids per millisecond with no talk between machines, and the ids sort roughly by time. Instagram uses the same idea with 41 bits of time, 13 bits of shard id and 10 bits of sequence.

Hash-based codes. Hash the content (a long URL, a file), encode it, keep the first few characters, and insert under a unique constraint; on a clash, add a salt and try again, a bounded number of times. If codes spread evenly over the space, the chance that one new code clashes is about the share already taken. Across many random codes, clashes come sooner than intuition says: by the birthday problem, a collision among N-bit values is expected after about 2^(N/2) of them, not 2^N.

When to use it

Use auto-increment when one database owns the table and writes are modest: it is the simplest thing that works, and small integer ids keep indexes compact. Use counter blocks when you need short ids from many servers, such as short links, and can live with ids that come in order. Use UUIDv4 when writers cannot reach any shared service, such as ids made on phones or across organizations. Use Snowflake-style ids or UUIDv7 when many machines create ids at a high rate and readers want them sorted by time, such as messages or posts. Use hash-based codes when the same content should map to the same code, or codes must look random.

When not to

Skip auto-increment when ids must not reveal how many rows exist or be guessable from a neighbor: sequential ids hint at both. Skip UUIDs when the id appears in something people type or read, such as a short link; 128 bits do not fit in a few characters. Flickr also rejected GUIDs because they are large and index poorly in MySQL. Skip Snowflake ids unless you can assign every machine a unique number and keep clocks sane, since the time bits carry the order. Skip hash-based codes when the space is nearly full, because every clash costs another round trip to the database.

Compared

SchemeStays unique becauseSize and orderGives up

Auto-increment

One database hands out every value

Small, mostly increasing

Every id waits on that database; ids are guessable

Counter blocks

Each server owns a block no one else gets

Small, in order within each server

Unused values on a crash; the counter must never go backwards

UUIDv4

122 random bits make a repeat vanishingly rare

128 bits, no order

Length; random inserts across an index

UUIDv7

A millisecond timestamp plus random or counter bits; how unlikely a repeat is depends on the implementation

128 bits, roughly sorted by time

Length; it reveals roughly when the id was made

Snowflake-style

No two machines share an id, and each counts within a millisecond

64 bits, roughly sorted by time

Every machine needs its own id; it depends on the clock

Hash with retry

A unique key rejects a clash, and a salt retries it

As short as the number of codes allows, no order

A database round trip per clash, more as the space fills

In a picture

its own blockthe next blockinsert, uniquekeyinsert, uniquekeyShared counterWrite server AWrite server BTable
Counter blocks: each server spends its own block, and the unique key backs it up.

How to say it in an interview

The common mistake

Quiz

Write servers take counter values in blocks. One crashes with part of its block unused. What is the right move?
Many servers must create message ids at a high rate, with no shared service, and readers want them in time order. Which fits?
Why does a system that makes random short codes still need a unique constraint?

Questions that use this

Related

Sources

  1. PostgreSQL documentation: CREATE SEQUENCE
  2. Redis documentation: INCRBY
  3. Flickr engineering: Ticket servers, distributed unique primary keys on the cheap
  4. Wikipedia: Universally unique identifier
  5. PostgreSQL documentation: UUID functions
  6. Wikipedia: Snowflake ID
  7. Wikipedia: Birthday problem
Sign in to report a mistake