YOUR BRIEF
What to work through
Work through a unique ID generator as a spoken system design interview. Start by clarifying the scope, sketch a working design and explain the trade-offs behind your choices.
- Each call returns a new id that no other call ever returns
- Ids are numeric and fit in 64 bits
- Ids sort by creation time; they need not grow by exactly one
- Spread the keys these ids name across servers, so adding a server moves few keys
BEFORE YOU START
Constraints to discuss
- 10,000 ids a second
- Up to 32 data centres with 32 machines each, with no coordination per id
- The timestamp lasts 69 years from the chosen epoch
- With 100 to 200 virtual nodes per server, a standard deviation of load of 5% to 10%
Need a starting point?
Watch for these common gaps as you prepare:
- A database auto increment shared by every server
- UUIDs when the requirement says 64 bits and sortable
- Assuming clocks agree, with nothing for a clock that moves backwards
- hash mod N for keys, which remaps almost everything on each change