Unique IDs

The problem: ids once the data is split

Every row needs an id no other row has: it goes into links, receipts and every table that points to the row. With one database it's easy: the database sees new rows one at a time, so its auto-increment counter hands out 1, 2, 3… and never repeats. The ids are short, cost nothing, and sort in the order rows arrived.

That breaks once the data is sharded. Say orders are split by customer over 3 shards, each its own database with its own counter, and Shards 0 and 1 have used ids 1 to 6. Ana's order goes to Shard 0 and gets id 7. A minute later Ben's order goes to Shard 1, which knows only its own counter, so it gets id 7 too. Nothing fails, but "order 7" now names two orders, and a payment, a link like /orders/7 or a support ticket can't tell them apart.

Two quick fixes and their costs

A central counter hands out every id, whatever the shard. Every insert now waits for one more call (a round trip inside a data center is about 0.5 ms), and if the counter is down, no shard can take a new row: a single point of failure. Handing out blocks of 1,000 ids cuts the calls to one per block, as the URL shortener lesson does for its codes, but everything still depends on one part.

Or each shard counts with a step: it adds 3 instead of 1 and starts at its own number.

shard     its ids
Shard 0   1, 4, 7, 10, …
Shard 1   2, 5, 8, 11, …
Shard 2   3, 6, 9, 12, …

The ids never meet and inserts cost nothing extra. Flickr described a mix of both fixes in 2010: two counter servers, one handing out odd ids and the other even ones. The catch: every number already belongs to a shard, so a fourth shard has nowhere to start, and all shards must switch to a step of 4 at the same moment.

UUIDs: random ids nobody coordinates

A UUID is 128 bits. Version 4, the common one, fills 122 of them with random bits (the other 6 mark the version and variant), written as 36 characters:

3f9c2a71-5e0b-4d8f-9a26-c1e47b830d5f

Any server, or a phone with no connection, makes one alone. They don't clash: there are 2¹²² possible values, a number 37 digits long. Even counting every pair (the birthday effect), a billion UUIDs have less than one chance in a billion billion that any two match; you'd need about a billion a second for about 86 years before one clash is as likely as not. That assumes a proper random source.

• Size: 36 characters as text, 16 bytes even as binary, twice a 64-bit number, in every row and index that holds it.
• No order: sorting by a random id says nothing about time, so "newest first" needs a separate time column and index.
• Scattered inserts: an index is a sorted tree of pages. Counted ids always go into the last page, which stays in memory; random ids land on a random page each time, so inserts read, write and split pages all over it.

UUID version 7, standardized in 2024, puts a millisecond timestamp in its first 48 bits, so it sorts by time with no coordination, but it's still 128 bits.

Snowflake ids: time, machine, counter

Twitter published a design in 2010, Snowflake, for ids made alone that still grow with time: one 64-bit number in four parts, highest bits first.

part      bits   holds
sign      1      always 0, so the id is positive
time      41     milliseconds since a start date
machine   10     which server made it
counter   12     ids this server made in this millisecond

41 bits of milliseconds last about 69 years from the start date, 10 bits name 1,024 machines, and 12 bits count 4,096 ids per millisecond per machine, about 4 million a second each. Because the time sits in the highest bits, a later millisecond always means a bigger id, so sorting by id sorts by time.

A worked example

Server A has machine id 1, server B machine id 2; small times keep the numbers readable (ms 105 is 105 milliseconds after the start date):

id        time   machine   counter   the number
A's 1st   105    1         0         440,406,016
A's 2nd   105    1         1         440,406,017
B's 1st   105    2         0         440,410,112
A's 3rd   106    1         0         444,600,320

A second id in the same millisecond bumps the counter; B's ids can't match A's, because the machine part differs; a new millisecond starts the counter at 0, and every id from ms 106 beats every id from ms 105. In code:

class IdMaker:
    def __init__(self, machine, clock_ms):
        self.machine, self.clock_ms = machine, clock_ms
        self.last_ms, self.counter = -1, 0

    def next_id(self):
        now = self.clock_ms()                 # ms since the start date
        if now < self.last_ms:
            raise RuntimeError('clock moved back')
        if now == self.last_ms:
            self.counter = (self.counter + 1) % 4096
            if self.counter == 0:             # all 4,096 used: wait
                while now <= self.last_ms:
                    now = self.clock_ms()
        else:
            self.counter = 0
        self.last_ms = now
        return (now << 22) | (self.machine << 12) | self.counter

When the counter runs out, or the clock runs back

If a burst uses all 4,096 counter values in one millisecond, the generator waits for the next one. Counting on to 4,096 would need a 13th bit, which belongs to the machine part, so the id would repeat one already made. Likewise, a clock that jumps back (servers correct their clocks over the network) could repeat a time and counter, so the generator refuses to make ids, or waits, until the clock passes the last time it used.

Each server needs its own machine id, handed out once when it starts (from its configuration or a coordination service), not on every insert. And the order is only rough: clocks never agree exactly, and within one millisecond ids are ordered by machine.

Which id to choose

kind              made by        sorts by time   guessable   size
auto-increment    one database   yes             yes         4 or 8 bytes
UUID version 4    anyone         no              no          16 bytes
Snowflake-style   each server    roughly         partly      8 bytes

One database and nothing to hide, like a small internal tool: auto-increment. Unguessable, or made where no machine id can be handed out, like a shared document's link or ids a phone makes offline: a UUID. Counted ids also leak your size: order number 1,042 says you've had about a thousand orders. Many servers and newest first, like tweets, chat messages or orders on several shards: Snowflake-style ids.

Unique IDs in system design interviews

Ids come up whenever data is sharded: short links, tweets, messages, orders. Say how ids stay unique without a call on every insert, then ask what they must do: sort by time (feeds, chat) or be unguessable (share links, invite codes). Name the limits: a Snowflake-style generator needs a machine id per server and a clock that doesn't run back; a UUID is long and scatters the index.

Common interview questions

How do you generate unique ids in a distributed system?

Without a call on each insert: random UUIDs, or Snowflake-style ids from a timestamp, a machine id and a per-millisecond counter. A central counter handing out blocks of ids also works, at the price of one service everything depends on.

UUID or Snowflake id?

A Snowflake-style id is 8 bytes, sorts by time and keeps index inserts at the end: feeds, messages, orders. A random UUID needs no machine ids and can't be guessed: public links and ids made on clients.

What happens if a server's clock goes backwards?

It could reuse a time and counter, and so repeat an id. The generator remembers the last time it used and refuses, or waits, until the clock passes it.

Summary

• Auto-increment: simple and sorted, but each shard's own counter hands out the same ids.
• Quick fixes: a central counter costs a call and can fail; a step breaks when you add a shard.
• UUID: 122 random bits, made anywhere, practically never clashes; long, unsorted, scatters the index.
• Snowflake: time, machine, counter in 64 bits; sorted by time; waits when the counter runs out or the clock runs back.
• Choosing: ask whether the ids must sort by time or be unguessable.