Unique ID generation

A photo-sharing app stores its photos on eight database shards (Sharding & partitioning). Each shard is a normal database with an auto-increment counter, so each one happily numbers its photos 1, 2, 3. A thousand uploads later, photo 1,001 exists on every shard:

The obvious fix, one central counter for everyone, works until it doesn't. Every upload in the world now waits for one server, and when that server is down nobody can upload anything. The ID service has become the most shared part of the system (Scalability explains why that limits everything).

So the goal is IDs that each server can make on its own. What else should a good ID do?

No scheme scores perfectly on all five. The rest of this page is three families of answers, and what each one gives up.

The first family keeps counters but stops them colliding. There are two classic ways.

Interleaved counters. Two ID servers both count, one in odd numbers (1, 3, 5) and one in even (2, 4, 6). Databases support this directly: MySQL's auto_increment_increment = 2 with offsets 1 and 2. Clients alternate between them, and if one is down they use the other. Flickr generated its IDs this way, on two small "ticket servers". Adding a third server later means re-planning the steps.

Block allocation. A central counter hands out ranges instead of single IDs. Each server takes a block of, say, 100,000 numbers, issues them from memory, and only goes back for a new block when it runs low:

Both keep IDs small and mostly increasing, and both still lean on a central store, just far less often. Two costs remain:

• Order is only per server. Server B's IDs are all larger than server A's, even for photos uploaded earlier, so "highest ID" no longer means "newest".
• Counters leak. Anyone who sees two of your IDs a day apart knows how many photos were uploaded that day, and can try the numbers in between.

The second family drops counting entirely: every server picks a random number and trusts that nobody else will pick the same one. The standard form is the UUID version 4: 128 bits, of which 122 are random, usually written as 36 characters like 9f1c…-….

How safe is "random"? The birthday problem answers it: in a space of S possible values, a collision becomes likely after only about √S picks, not S. (In a room of 23 people, two probably share a birthday.) So the number of bits matters far more than intuition suggests:

A 6-character random code, the kind short links use, collides after a few hundred thousand links, so a system using one must check every new code and retry on a clash. A UUID can skip the check for all practical purposes, provided the random numbers come from a good generator: a badly seeded one breaks the arithmetic.

UUIDs pay for that safety in two ways:

• Size. 16 bytes instead of 8, in every index and every table that refers to the row.
• Scattered inserts. Consecutive random IDs land at random places in a database index, so each insert touches a different page and the index's working set no longer fits in memory. The UUID standard itself names this "poor database-index locality".

The third family builds the ID from parts, with the time at the front. The best-known layout is Twitter's Snowflake. It packs three fields into one 64-bit integer:

Each machine makes IDs alone: same machine, same millisecond, next sequence number. Because the time comes first, sorting by ID sorts by creation time, and new rows land at the end of the index. The order is only rough across machines, since their clocks differ by a few milliseconds; Twitter called this k-sorted. And anyone can read the creation time straight out of an ID.

Variants move the bits around for their own needs:

• Instagram replaced the machine ID with a 13-bit logical shard ID and a 10-bit sequence, generated inside each shard's database. An ID then tells you which shard holds the row, the trick Sharding & partitioning recommends.
• UUID version 7, standardized in 2024, puts a 48-bit millisecond timestamp in front of 74 random bits. It needs no machine IDs at all, and sorts by time.
• ULID does the same in 128 bits, written as 26 sortable characters.

Version 7 replaces the older time-based versions. If you want UUIDs, want them sortable, and don't want to manage machine numbers, it is the default choice today.

A Snowflake-style generator is only as unique as its inputs. Three things can go wrong:

The clock jumps back. Time synchronization (NTP) can step a server's clock backwards. If the generator keeps going, it can reissue timestamps it has already used, and with the same sequence numbers that means duplicate IDs. A careful generator remembers the last timestamp it used and refuses to issue IDs until the clock passes it:

Two machines share a number. Ten bits of machine ID only help if every generator has a different one. Hard-coding them in config breaks when a server is cloned or a container restarts somewhere else. Assign them from a coordination service, or a database row each machine claims, with a lease that expires when the machine dies.

The sequence runs out. At 4,096 IDs in one millisecond on one machine, the next request has to wait for the next millisecond. That is rarely a problem, but it means a single generator can't be pushed past about 4 million IDs a second.

And all three families leak something. Counters reveal how many rows you have; time-based IDs reveal when a row was created. Neither is a security problem by itself, as long as nobody treats an ID as a password: UUIDs must not be used as capabilities whose mere possession grants access. Check permissions on every request, whatever the ID looks like.

Short codes deserve a word. Writing a number in base 62 (a–z, A–Z, 0–9) packs it tightly: six characters cover 62⁶ ≈ 56.8 billion values, seven cover about 3.5 trillion. Hashing the long URL and keeping the first few characters looks tempting, but it is the random case again: collisions after a few hundred thousand links. Counting and encoding never collides.

Whatever you pick, decide it early. An ID ends up in URLs, in other tables, in logs and in other companies' systems, and changing its format later is a migration of everything that ever stored one.