Unique IDs across many machines

Part of the free System Design course on LogicWiz, in the chapter: Consistency and coordination. The interactive whiteboard exercises and simulations run in the app.

Two orders called 1,042

"Two customers rang about order 1,042. Both were right. One had ordered paneer, the other diapers."

A SwiftKart support agent

Two shards, one order number

SwiftKart's orders are split across 8 shards by customer id. Each shard is a separate SQL database. Each new order gets its id from an auto-increment column: the database keeps a counter and gives every new row the next number, 1, 2, 3 and so on.

On one database that is perfect: one counter never repeats. With 8 shards there are 8 counters, and every one of them started at 1. Shard 2 gives order 1,042 to a customer in Pune. Shard 5 gives order 1,042 to a customer in Delhi. Each shard is right on its own. Together they are wrong. Every tool that looks up "order 1,042" now finds two orders.

Two quick patches both age badly:

• Offsets. Shard 1 hands out 1, 9, 17; shard 2 hands out 2, 10, 18, in steps of 8. Add a ninth shard and every step must change without any id repeating.
• Shard prefixes, like "5-1042". Moving a customer to another shard then changes all their order ids.

So the real question is: how can many machines create ids that never collide, without asking each other every time? Here an id means a value that names exactly one row, forever.

Picture a railway booking office with 8 counters. If every clerk numbers tickets from 1, two passengers hold ticket 1,042. There are three ways out: a long random number on each ticket, a pad of numbered tickets from head office, or a stamp of the time, the counter number and a running count. Those are the three ideas below. The analogy stops working in one place: the clerks share one wall clock, and machines do not.

UUIDs: unique with no coordination, but heavy

A UUID (universally unique identifier) is a 128-bit number. It is usually written as 36 characters, such as 3f2a9c1e-7b4d-4e8a-9c2f-5d1b6e0a7f34. Version 4, the common kind, fills 122 of those bits at random. Any machine, even a phone, can make one alone, with no network call. That is the big win: zero coordination.

Will two ever match? There are about 5 × 10^36 possible values. If SwiftKart created a billion UUIDs, the chance that any two match is roughly 1 in 10 billion billion. With a good random generator, treat it as never.

The costs appear in the database:

• Size. 16 bytes as a number, or 36 as text, against 8 bytes for a 64-bit integer. Every index and every table that refers to the order grows too.
• No order. An index is kept sorted. Rising ids are always added at the end, where recent pages already sit in memory. Random ids land anywhere, so once the index outgrows memory, inserts touch pages all over the disk and slow down.
• No time. Sorting by id does not give "newest first".

In a mock interview, Meera said, "A UUID is always the safe choice." Kabir agreed with only half of it. It is safe from collisions, but you pay for it in every index, on every insert, forever. Newer UUIDs (version 7) put a millisecond timestamp first, so they rise over time and index well, though they stay 16 bytes.

A ticket server that hands out blocks

The second idea keeps one counter but stops asking it for every id. A ticket server, also called an id range service, is a small service that owns one number: the next free id. An order service instance asks it for a block, say 1,000 ids. The ticket server adds 1,000 to its counter, saves it, and replies "yours are 41,001 to 42,000". The instance then issues those ids from memory until the block runs out.

flowchart LR
  T["Ticket server (next: 43,001)"] -->|"41,001 to 42,000"| A["Order service A"]
  T -->|"42,001 to 43,000"| B["Order service B"]
  A --> S2["Shard 2"]
  B --> S5["Shard 5"]

Say a festival sale peaks at about 100 orders a second. With blocks of 1,000, the ticket server sees one request every 10 seconds. The trade-offs:

• Ids are 64-bit and mostly rising, but not strictly in time order. Instance A may still be using the 41,000s after B has started on the 42,000s.
• An instance that crashes loses the rest of its block. That leaves gaps, numbers never used. That is fine: ids must be unique, not continuous.
• The counter must never go backwards, even after a failover. So the ticket server saves the new counter in a replicated, strongly consistent store before it replies. If it goes down, instances keep working until their blocks run out.

The URL shortener question later in the course uses this scheme, plus a scramble so codes cannot be guessed.

Snowflake ids: time, machine and counter in 64 bits

The third idea builds each id from parts that are unique by construction. It is called a Snowflake-style id, after the id service that made it popular. It packs three fields into one 64-bit integer:

| 1 bit | 41 bits               | 10 bits    | 12 bits  |
| 0     | ms since custom epoch | machine id | sequence |

• 1 bit stays 0, so the id stays positive in an ordinary 64-bit integer column.
• 41 bits of time: milliseconds since a custom epoch, a start date you choose, such as 1 January 2025. 2^41 milliseconds is about 2.2 trillion, roughly 69 years. So these ids last until about 2094.
• 10 bits of machine id: 2^10 = 1,024 machines, each with its own number.
• 12 bits of sequence: a counter that restarts every millisecond. 2^12 = 4,096 ids per millisecond per machine, about 4 million a second. If a machine uses all 4,096 inside one millisecond, it waits for the next one.

To build an id, push each field up past the bits below it. The time moves up 22 bits (10 plus 12), so it is multiplied by 2^22:

time     = 50,000,000,000 ms since the epoch (about 1.6 years in)
machine  = 37
sequence = 5
id = time × 2^22 + machine × 2^12 + sequence
   = 50,000,000,000 × 4,194,304 + 37 × 4,096 + 5
   = 209,715,200,000,000,000 + 151,552 + 5
   = 209,715,200,000,151,557

Why can two ids never match? Ids from different machines differ in the machine bits. Ids from the same machine in the same millisecond differ in the sequence. A later millisecond gives a bigger number, so ids rise with time. They fit in 8 bytes and need no network call. The catch is that the scheme trusts two things: the clock, and the machine id.

Clocks that go backwards, and who hands out machine ids

Every machine keeps its own clock, and clocks drift. A time service, NTP (network time protocol), corrects them regularly. Even so, two machines may disagree by a few milliseconds, with two effects.

First, ids sort by time only roughly across machines. An order placed a moment later on another machine can get a smaller id. Never use ids to decide the exact order of events.

Second, and worse, a correction can move a clock backwards. Machine 37 issues ids at millisecond 1,000, then its clock jumps back to 995. Milliseconds 995 to 1,000 come round again, the sequence restarts at 0, and machine 37 can produce an id it already produced. The fix: the generator remembers the last timestamp it used, and if the clock reads earlier, it issues nothing. For a jump of a few milliseconds it waits until the clock passes the old value. For a large jump it stops and raises an alert. Many teams also set the time service to slew the clock: run it slightly slow until it is right, instead of stepping it back.

The machine id is a coordination problem. Writing it in a config file fails once machines are added and replaced automatically. The common answer: on start, each instance takes a free number from a coordination service such as etcd or ZooKeeper. It holds the number with a lease, a claim that expires unless renewed, and keeps renewing it. If the instance dies, the lease expires and the number is free again. Remember the paused worker from the last lesson: a frozen machine may wake up still using number 37 after the lease went to someone else. So a generator stops issuing ids the moment it cannot renew, and a freed number waits a while before reuse.

Choosing an id scheme

A decision guide:

• One database, no plans to shard: auto-increment. Simple and correct.
• Ids made on phones, or by systems that never talk: a UUID. Prefer version 7 if it becomes a primary key.
• Short numbers people read or type, like short links: a ticket server with blocks.
• Many machines, high volume, 64-bit ids that sort by time: Snowflake-style. SwiftKart picks this for orders.

⚠️ Warning: Counter ids leak information. Order at 9 a.m. and 9 p.m., subtract the ids, and you can estimate a day's orders. Never treat an id as a secret: check the order belongs to the caller.

📌 Summary: Auto-increment repeats across shards. UUIDs need no coordination but are big and unordered. Ticket servers hand out blocks. Snowflake ids pack time, machine and sequence into 64 bits; guard against clocks going backwards.

What Meera learns next

Unique ids keep orders apart, but they cannot keep checkout running when a service it depends on fails. Next week: designing for failure, so one broken part does not take payments down with it.

Check your understanding

1. SwiftKart's orders sit on 8 SQL shards, and each shard uses an auto-increment id. Support finds two different orders numbered 1,042. Why?
2. A Snowflake-style generator last issued an id at millisecond 1,000. A time correction moves its clock back to 995. What should it do?
3. A candidate says: "UUIDs are always the safe choice, so I will use random UUIDs as the primary key for billions of orders." What is the best reply?
4. A Snowflake-style id gives 12 bits to the sequence. At most, how many ids can one machine issue in a second?