ProblemData and infrastructure
Distributed ID generator
Hand out unique IDs to every service, millions a second, that never repeat and roughly sort by time.
The brief
Platform-wide ids · suggested for Senior
Design a unique ID generator for a large platform
Design how a large platform’s services get unique ids for orders, users and messages: never the same id twice, fast enough for every request, in time order, 64 bits that last for decades, and safe through failures and several regions.
A large platform runs about 300 services in three regions. About 6,000 service instances create ids, about 2,000 in each region, and instances start and stop about 50,000 times a day through autoscaling and deploys. At peak the platform needs about 2 million new ids a second, mostly for messages, then orders and users; the busiest single instance needs about 50,000 a second. Ids are primary keys in sharded MySQL and Postgres databases with B-tree indexes, travel through event streams, and reach web clients written in JavaScript and mobile apps. Order and user ids appear in URLs and on receipts; last year a competitor estimated the platform’s order volume from order numbers. About 1.2 billion existing users have ids from a MySQL auto-increment column, and those ids must keep working. Servers keep their clocks in sync over the network, but a few machines a week have their clock set back by up to a second, and VMs are sometimes restored from snapshots. Last year one region was cut off from the other two for 40 minutes. Design how ids are made: what an id is made of, how two machines never make the same one, and how ids stay fast, ordered and safe through clock problems, restarts and regions.
Functional requirements
- CoreAny service can get a new id, or a batch of them, for an order, a user or a message.
- CoreGiven an id, support staff can see when it was created.
- CoreIds appear in APIs, URLs and on receipts, and reach web and mobile clients.
Non-functional requirements
- ConsistencyNo two entities ever get the same id, across all services, regions, restarts and clock problems.
- LatencyAn id is available within 1 ms at p99, with no call to another region.
- AvailabilityIds keep being issued while a machine, a zone or any shared component is down for a while.
- QualityIds from one service sort by creation time, and ids created more than about a second apart sort in time order across the platform.
- QualityAn id fits in a signed 64-bit integer, and the scheme lasts at least 50 years.
- SecurityIds shown to customers reveal neither the platform’s volumes nor a way to reach other users’ data.
- AvailabilityA region cut off from the others keeps issuing ids that never collide with theirs.
Scale
- ScaleAbout 2 million new ids a second at peak across the platform; the busiest instance needs about 50,000 a second.
- ScaleAbout 6,000 instances create ids, about 2,000 in each of three regions, with about 50,000 instance starts a day.
- ScaleIds are B-tree primary keys and reach JavaScript web clients and mobile apps; about 1.2 billion old user ids must keep working.
- ScaleA few machines a week have their clock set back by up to a second; one region was cut off for 40 minutes last year.
Nice to mention (below the line)
- Below the lineHuman-friendly short codes.
- Below the lineStrictly gap-free numbering, such as invoice numbers.
- Below the lineA single total order of every event on the platform.
Out of scope
- Out of scopeThe services’ own databases and what they store.
- Out of scopeAuthentication internals: services already have identities.
- Out of scopeClient apps’ screens.
- Out of scopeHardware and the network between regions.
The variant
One fully specified brief, with the level it suits best. You can practise it at any level.
- Platform-wide idsSuggested for Senior
Ids for 300 services in three regions: 2 million a second, never a duplicate, in time order, 64 bits for 50 years, through clock steps and outages.
10 steps · 7 must-pass · about 47 min at Senior
What each level is graded on
Platform-wide ids, step by step. A result at a level needs its must-pass steps answered, and only the steps you answer count. Going up a level adds steps or holds them to a stricter bar.
| Step | Entry level | Mid-level | Your levelSenior | Staff |
|---|---|---|---|---|
| The numbers that shape the design (optional) | Graded | Graded | Graded | Graded |
| What an id is made of | Graded | Must-pass | Must-pass | Must-pass |
| How services get ids | Graded | Graded | Graded | Graded |
| Two generators, one millisecond | Must-passcan block | Must-passcan block | Must-passcan block | Must-passcan block |
| Two million ids a second | Must-pass | Must-pass | Must-pass | Must-pass |
| Newest first, and fast inserts | Must-pass | Must-pass | Must-pass | Must-pass |
| The clock jumps back | Graded | Must-pass | Must-pass | Must-pass |
| Order numbers in the address bar | Graded | Graded | Must-pass | Must-pass |
| A generator freezes, and its number is handed out again | — | Graded | Must-pass | Must-pass |
| Sale day on one table | — | — | Graded | Graded |
| Three regions, and the old ids | — | — | — | Must-pass |
| At this level | 8 steps 3 must-pass about 36 min | 9 steps 5 must-pass about 42 min | 10 steps 7 must-pass about 47 min | 11 steps 8 must-pass about 53 min |
Entry level8 steps · 3 must-pass · about 36 min
- The numbers that shape the design (optional)Graded
- What an id is made ofGraded
- How services get idsGraded
- Two generators, one millisecondMust-passcan block
- Two million ids a secondMust-pass
- Newest first, and fast insertsMust-pass
- The clock jumps backGraded
- Order numbers in the address barGraded
Mid-level9 steps · 5 must-pass · about 42 min
- The numbers that shape the design (optional)Graded
- What an id is made ofMust-pass
- How services get idsGraded
- Two generators, one millisecondMust-passcan block
- Two million ids a secondMust-pass
- Newest first, and fast insertsMust-pass
- The clock jumps backMust-pass
- Order numbers in the address barGraded
- A generator freezes, and its number is handed out againGraded
SeniorYour level10 steps · 7 must-pass · about 47 min
- The numbers that shape the design (optional)Graded
- What an id is made ofMust-pass
- How services get idsGraded
- Two generators, one millisecondMust-passcan block
- Two million ids a secondMust-pass
- Newest first, and fast insertsMust-pass
- The clock jumps backMust-pass
- Order numbers in the address barMust-pass
- A generator freezes, and its number is handed out againMust-pass
- Sale day on one tableGraded
Staff11 steps · 8 must-pass · about 53 min
- The numbers that shape the design (optional)Graded
- What an id is made ofMust-pass
- How services get idsGraded
- Two generators, one millisecondMust-passcan block
- Two million ids a secondMust-pass
- Newest first, and fast insertsMust-pass
- The clock jumps backMust-pass
- Order numbers in the address barMust-pass
- A generator freezes, and its number is handed out againMust-pass
- Sale day on one tableGraded
- Three regions, and the old idsMust-pass
- Must-pass
- a result at that level needs this step answered.
- Can block
- a miss there is a Blocking issue at that level.
Going up a level
- Mid-level
- “What an id is made of” becomes must-pass.“The clock jumps back” becomes must-pass.Adds “A generator freezes, and its number is handed out again”.
- Senior
- “Order numbers in the address bar” becomes must-pass.“A generator freezes, and its number is handed out again” becomes must-pass.Adds “Sale day on one table”.
- Staff
- Adds “Three regions, and the old ids”, must-pass.
Skills this problem practises
Your coach tracks readiness per skill across every problem you practise. Each links to the lesson that teaches it.
- Capacity estimation
- API design
- Data modelling
- Choosing storage
- Indexing
- Sharding and partitioning
- High-level architecture
- Consistency and concurrency
- Failure modes and recovery
- Observability and operations
- Rate limiting and abuse
Worked solution
Try it first: practise a variant, then read the walkthrough and compare it with your own design. Reading it first makes the practice much less useful.
Learn: Design a unique ID generatorYour history
Sign in to see your sessions on this problem.