CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 2 of 7 · 2 min read

Requirements and numbers

What an ID must be.

Think of numbered tickets at a busy bakery with ten counters. If each counter hands out its own tickets from 1, two customers get the same number. A shared ticket roll fixes that, but then everyone queues at the roll. The problem is to give out unique numbers without a queue.

The first idea is the auto-increment key of a database. The Xu book explains why it breaks in a large system: one database server is not big enough, and making unique IDs across several databases with little delay is hard.

Questions and the answers assumed here (taken from the book's sample talk).

  1. What must an ID be like? Unique, and sortable.
  2. Does it go up by exactly 1? No. It grows with time, so an ID made in the evening is larger than one made in the morning.
  3. Only digits? Yes, numbers only.
  4. How long? It must fit in 64 bits.
  5. How fast? Over 10,000 IDs per second.

Requirements.

  • R1. Every ID is unique across all machines and data centres.
  • R2. IDs are numbers that fit in 64 bits.
  • R3. IDs are ordered by creation time.
  • R4. The system makes more than 10,000 IDs per second.
  • R5. It stays up. IDs are needed for every write, so it is a critical service.

Numbers. At 10,000 IDs per second, there are 10 IDs per millisecond. A 64-bit number can hold up to about 1.8 × 10^19 values, so space is not an issue in itself. The real question is how to pack time and place into those bits so no two machines ever pick the same number.

Unique ID

A unique ID is a number or string that names one item and is never given to any other item.

Example: the order number 4194717696 names exactly one order.

Check yourself: 1. Why does a single auto-increment not scale? 2. What does "sortable by time" mean for the IDs? 3. How many IDs per millisecond does 10,000 per second give?