Generating Unique IDs at Scale

Every database you have met so far in this course has had one instance handing out IDs, and with one instance that is trivial: auto-increment, a counter that goes 1, 2, 3 and so on. The next chapters are about splitting data across several database instances, and the moment there is more than one, that assumption breaks. Before you can split data you need to know how to give every record an ID that is unique across the whole system, and this chapter shows the three standard ways.

A busy bakery has one counter with a roll of numbered tickets, and it works perfectly: ticket 482 belongs to exactly one customer. Now the bakery opens a second counter with its own roll, also starting at 1. Soon two different customers hold a ticket numbered 482, and nobody can tell them apart. There are three ways out. Give every customer a long random code that will never repeat. Put one central ticket machine in the middle that every counter must use. Or print the time and the counter's number on every ticket, so a ticket from counter 7 at 14:03:07 can never match one from counter 3.

• -Each counter's own roll is a separate database with its own auto-increment.
• -The long random code is a UUID.
• -The central ticket machine is a ticket server.
• -The ticket carrying the time and the counter's number is a Snowflake-style ID.

If Shard A and Shard B both auto-increment independently, both will eventually assign id 482, to two completely different records. Anything that points to a record by ID, such as a foreign key, a cache key or a link in an email, now cannot tell which record it means. You need IDs that are unique across the whole system, not just within one database.

A UUID is a 128-bit random value. The chance of two of them colliding is so small that it is treated as impossible in practice, and any machine can generate one with no coordination at all. The costs are size (128 bits against 64 for a normal integer) and, for the common random variant (version 4), no ordering: you cannot tell which of two UUIDs was created first. That second cost has a practical bite. A database index keeps its entries sorted, so random IDs land in random places in the index and make inserts slower, whereas increasing IDs always append at the end. Newer time-ordered UUID versions (version 7) put a timestamp first to fix this.

A single dedicated database whose only job is to hand out the next number. It is simple, produces compact increasing IDs, and was used by well-known companies early on. But every ID in the system now depends on this one machine: it is a bottleneck and a single point of failure. A common patch is to run two servers, one handing out odd numbers and one even, but that is already getting complicated.

Twitter's Snowflake design, since adopted widely including by Discord, packs several pieces of information into one 64-bit integer: a timestamp, the identifier of the machine that generated it, and a sequence number that counts IDs made within the same millisecond. The result is compact like a normal integer, unique without a central machine, and sortable by creation time just by comparing the numbers, because the timestamp is in the leading bits. The sketch below builds and splits one:

Run it and look at the first line. The first ID is smaller than the second even though its machine number (7) is bigger than the other's (3), because comparing the numbers compares the timestamp first. The second line shows that nothing is lost in the packing: the timestamp offset, machine and sequence come back out. The bit layout also sets the limits:

One more point about timestamps: the scheme relies on each machine's clock moving forward. If a clock jumps backwards, a machine could generate an ID it has already used, so real implementations refuse to issue IDs until the clock catches up. The 10-bit machine number also has to be assigned to each generator without clashing, usually by a coordination service such as ZooKeeper or etcd when the generator starts.

• -Need the simplest thing and do not care about order or size? UUID version 4.
• -Need IDs that sort by time and are small enough for a 64-bit column? Snowflake-style.
• -A small system with one database and no plans to split it? Plain auto-increment is fine. Do not pay for a distributed scheme before you need one.