Unique IDs and Sequencers

It is 8:50 am at a tea stall outside Pune station, and forty commuters scan the same QR code in five minutes. Behind each scan, a payments app creates a transaction and gives it an ID. Last night the team split the transactions table across four database shards to survive the morning rush, and each shard kept its own auto-increment counter. By 9 am shards 1 and 3 have both issued transaction 5,000,214: one ₹12 chai and one ₹15,000 rent payment. When the chai seller refunds a customer, the refund job looks up 5,000,214 and reverses the rent.

This chapter follows that payments app. An ID is a value that names exactly one thing, forever. Uniqueness is the must-have; the other properties are choices that pull against each other:

No scheme wins on every row, so each one in this chapter is a different set of trade-offs. The first is the one that broke at the tea stall.

Why did the counters collide? An auto-increment column gives rows 1, 2, 3 and so on, like a token machine at a bank counter. It is unique, compact, sorted by insert time and needs no extra system. For a single database server it is often the right answer.

It breaks in three ways as the payments app grows:

• One writer. Every ID comes from one database, so that server caps inserts and is a single point of failure for every payment.
• Shards collide. Once the table is partitioned, as in the databases chapter, every shard counts on its own. Shard 1's transaction 5,000,214 and shard 3's are different payments with one ID.
• It leaks. Sequential IDs tell outsiders your volume: pay once today and once tomorrow, and the difference is your daily count. They also let anyone try /receipt/1001, /receipt/1002 and onwards.

A classic patch gives each shard its own step. With 4 shards, shard 1 issues 1, 5, 9, shard 2 issues 2, 6, 10, and so on. IDs stay unique, but a fifth shard means changing every step, and IDs from different shards no longer sort by time. Auto-increment ties uniqueness to one counter, so it fails the moment there are several.

What if IDs did not come from a counter at all? The next page gives up on order entirely and picks them at random.

A random ID works like picking a lottery number from a space so vast that no two people ever pick the same one. A UUID (universally unique identifier) is 128 bits, usually written as 36 characters such as 3b9e2c71-8d4f-4a06-9c15-7e2d0a5b6f48. In version 4, 122 bits are random and the other 6 mark the version and variant.

Collisions are possible in principle. In practice you would need about a billion UUIDs every second for roughly 85 years before the chance of even one duplicate reached 50%, provided they come from a proper random generator. Here is what that buys and costs:

Random UUIDs buy zero coordination with size and lost order.

The hidden cost is the index. A time-ordered key inserts at the right-hand edge of a B-tree index, which stays in memory. Random keys land on any page, so a big transactions table keeps reading cold pages from disk and splitting them, and inserts slow down. With a billion rows, the extra 8 bytes per ID also cost 8 GB in every index that holds the ID.

Can an ID be compact, roughly sorted and made without coordination, all at once? Think of a receipt printed with the time, the counter number and a running count: two counters never print the same receipt, even in the same second. Pack the same three things into one 64-bit integer and you get a Snowflake-style ID:

Each field answers one question: when, who, and which one of that millisecond.

The custom epoch is a zero point you choose, such as 1 January 2026. Counting from a recent date rather than 1970 keeps all 69 years ahead of you. The sequence restarts at 0 every millisecond; a generator that wants a 4,097th ID within one millisecond waits for the next.

A worked example: 24,000,000,000 ms after the epoch (about 278 days in), payment server 7 issues its fourth ID of that millisecond, sequence 3. The ID is 24000000000 × 2^22 + 7 × 2^12 + 3 = 100,663,296,000,028,675. Shift it right by 22 bits and the time comes back, which helps when debugging a payment. The next page turns the layout into code.

Where does the generator run? Inside each payment server process, as a small library: making an ID is a function call of a few microseconds, with no network hop. Each process holds one machine id, so two processes on one machine need two ids.

Three branches carry the design:

• Clock went back: wait out a step of up to 10 ms; refuse anything larger, so a timestamp is never reused.
• Same millisecond: add one to the sequence; after 4,096, wait for the next millisecond.
• New millisecond: restart the sequence at 0. The lock keeps two threads from taking the same sequence number.

The machine id is what makes this work across a fleet. As long as no two running generators share one, their IDs differ in those 10 bits even when the time and sequence match. Generators never talk to each other, or to anyone, while making IDs.

The only shared step is leasing a machine id, once per process, not once per ID. Everything else is local arithmetic, which is why one generator makes millions of IDs a second and why a short registry outage stops nothing. Clocks, though, can still hurt a generator that never talks to anyone; that comes after one more question: where machine ids come from.

If two live generators ever share a machine id, they can issue identical IDs in the same millisecond. So how does each process get a unique one? There are three common answers:

Leasing is the safe default for fleets that scale up and down.

The lease rules come straight from the coordination chapter. Lease for, say, 60 seconds and renew every 20. If a process cannot renew before its lease ends, it stops issuing IDs, because the registry may hand that number to a new process. The registry, in turn, never reuses a number until its old lease has fully expired plus a margin.

Ten bits allow 1,024 live generators. That sounds like plenty, but containers that restart every few minutes each take a fresh number and leave old ones waiting out their leases. Size the machine field for peak churn, not for the steady fleet; if 1,024 is tight, move a bit or two from the sequence, which few generators fill.

A generator that talks to nobody still trusts one thing: its clock. Servers keep time with NTP, which keeps nudging each clock towards reference servers. Within a data centre, clocks usually agree within a few milliseconds, never exactly, and now and then a clock jumps backwards: after a large NTP correction, a leap second, or a wrong manual change.

Skew between machines only makes ordering approximate. If server 1 runs 3 ms ahead of server 2, its IDs sort as if made 3 ms later, so these IDs are roughly sorted: fine for a payment history, not proof of which payment happened first. When order across machines matters, use a hybrid logical clock: physical time plus a small counter, carried on every message, so timestamps stay near real time, never go backwards, and always sort a reply after the message it answers.

A clock that goes backwards on one machine is worse: its timestamps repeat, and with a repeated sequence it issues an ID it already gave out. A generator must notice and react:

Every row has one aim: a generator never reuses a timestamp, even if it must stop.

In one database, a time-ordered key is a gift: every insert lands at the right-hand edge of the index. Now split the transactions table across nodes by key range, as many distributed SQL databases and wide-column stores do; the databases chapter called this range partitioning. Every new ID is larger than all before it, so every insert lands in the last range, on one node, while the others idle.

Splitting the hot range does not help for long, because the new upper half takes all the writes again. Write throughput stops at what one node absorbs, however many nodes you add. The same goes for UUIDv7, ULID and any key that starts with a timestamp. Three fixes spread the writes, each at a price:

Pick by the reads you need most: a merchant's statement favours owner-first, a global audit stream favours buckets.

The payments app chooses owner-first: a merchant's transactions live together and come back in time order with one range scan, which is exactly what a daily statement reads.

If transactions are partitioned by merchant anyway, why not let the ID say where it lives? A related layout puts a logical shard number inside the ID, for example 41 bits of time, 12 bits of shard and 10 bits of sequence.

Any service can then read the shard straight from an ID and route a request with no lookup table, and IDs still sort by time within a shard. Pick the shard from the owner, such as a hash of the merchant, so one merchant's rows live together. Let the database that owns the shard generate the sequence, so two payment servers never race for the same number; 10 bits give 1,024 IDs per millisecond per shard.

The catch is permanence: an ID can never change, so the shard number inside it is fixed forever. Create far more logical shards than machines, so data can move without changing a single ID.

The cost is fewer bits elsewhere: 12 bits of shard leave 10 for the sequence and none for a machine id, so this layout only works where one owner per shard creates IDs. Few designs need it; the plain layout with an owner-first key is usually enough.

A few more ways time-based IDs fail, each easy to prevent once you know it:

• Running out of time bits. 41 bits of milliseconds last about 69 years from the epoch. Pick a recent epoch and write it down; an ID scheme often outlives the team that designed it.
• Running out of sequence. 4,096 IDs per millisecond per generator is plenty for most services. If one process needs more, give it two machine ids, or move bits from the machine field to the sequence.
• IDs in JavaScript. JavaScript numbers are exact only up to 2^53, about 9 × 10^15, and these IDs pass that about 25 days after the epoch. A browser that parses one as a JSON number silently rounds it to a different ID.
• Information in the ID. A time-based ID reveals when a payment was made, and the machine bits hint at fleet size. Usually harmless; use a random public ID where it matters.

Most ID bugs are limits nobody wrote down: bits, epochs and number types. The last part leaves clocks behind and returns to counters, used carefully.

A counter was the problem at the tea stall only because every shard had its own. Keep one counter, but stop asking it for every ID: a small ID service hands out blocks of numbers, say 10,000 at a time. Each payment server assigns IDs from its block in memory and asks for another when it runs low.

-- one row per sequence, for example 'txn'
UPDATE id_blocks
   SET next_start = next_start + 10000
 WHERE name = 'txn'
RETURNING next_start - 10000 AS block_start;

PostgreSQL-style SQL. One atomic update per block; the caller owns block_start to block_start + 9,999.

If a server uses 2,000 IDs a second, a block of 10,000 lasts 5 seconds, so the ID service sees one request per server every 5 seconds instead of 2,000 a second. Fetch the next block in the background and keep a spare in hand, so a few seconds of ID-service downtime go unnoticed.

Block size is the trade. A block of 1,000,000 would ride out about 8 minutes of outage, but a crashed server throws away up to a million numbers, and IDs from different servers drift minutes apart in time. Bigger blocks buy outage cover with bigger gaps and looser order.

Three properties follow from the design:

• Compact and mostly increasing: small integers that grow over time, though servers working through different blocks interleave.
• Gaps are normal: a crashed server loses the rest of its block. IDs stay unique, not continuous.
• One dependency: the counter row must be highly available, for example in a consensus-backed store using compare-and-set, but it is called rarely.

Everything so far gives IDs that are unique and roughly ordered. A few needs go further, and each has its own price:

Each row costs more agreement than the one above it needs; take only the guarantee the record demands.

Invoices are the common case. India's GST rules, for example, ask for invoice serial numbers that are consecutive and unique within a financial year, and they allow more than one series. The counter row does it:

Plain auto-increment is not gap-free: a rolled-back insert still uses up its number. The counter row rolls back with the invoice. The price is throughput: the row stays locked until commit, so at about 5 ms per transaction one series manages about 200 invoices a second. Strict order is one writer at a time, so split the work into independent series, such as one per shop per financial year.

With every option on the table, pick by the property the product cares about most. Here they are side by side:

Unique is cheap and local; ordered is expensive, because order needs agreement, either one central point or the consensus from the coordination chapter.

For a large service like the payments app, a sensible default is Snowflake-style IDs inside, sent to clients as strings, plus a random public ID wherever a link must not be guessable, and a counter row only for invoices. Switch to UUIDv7 when 128 bits are affordable and you want no machine ids at all; choose UUIDv4 when IDs are made on phones or merged from many sources.

ID generation usually comes up inside a bigger design, such as payments, chat or a link shortener, so answer in two or three sentences and move on.