Design a unique ID generator
Ten thousand IDs a second across two data centres, every one unique and roughly in time order. The round turns on one sentence: each box packs the time, its own node id and a counter into 64 bits, so no two boxes ever need to talk.
The round this design follows
Why not use a random UUID?
A random UUID is unique with no coordination at all, and that is its strength. It fails this prompt twice: it is 128 bits when the prompt asks for 64, and it has no order, so rows keyed by it land all over the consumer's index instead of at its right edge. At the prompt's rate held for a year, the key alone is 2.52 TB as 64-bit IDs and 5.05 TB as UUIDs, before any secondary index repeats it. If the prompt allowed 128 bits, a time-ordered UUID would be a fine answer, and I would say so.
How many IDs a second can one node make?
The 12-bit sequence gives 4,096 IDs in one millisecond on one node, so 4.1 million a second. The prompt asks for 10 thousand a second across the whole fleet, which is 10 a millisecond. One node could carry the prompt about four hundred times over, so the ID path is never the bottleneck; the callers are.
What happens when the clock goes backwards?
The mint remembers the millisecond of its last ID. If the clock now reads earlier, minting could repeat an ID already handed out. A small step, up to 5 ms here, is waited out: the mint reads the clock until it passes the last millisecond. A bigger step is refused with an error and an alarm, and the caller retries on another box. Time sync normally slows a fast clock rather than stepping it back, so the refusal is rare and worth a page when it happens.
How does a new machine get its node id?
It leases one from a small registry, a consensus-backed store, at startup. Each data centre owns half of the 1,024 ids, 512 each, so the two never compete. The lease lasts 30 seconds and is renewed every 10; the registry also records the last millisecond the previous holder minted, and the new box waits until its own clock is past it. No ID ever passes through the registry, so it can be down for seconds with no effect on minting.
Are the IDs sorted exactly by time?
Roughly. Inside one node they strictly increase. Across nodes they are ordered by each node's own clock, so two IDs minted a few milliseconds apart on two machines can sort in the wrong order by as much as the clocks disagree. The name for that is k-sorted. It is enough for a feed or a time-range scan; it is not a total order of events, and I would say so before the interviewer asks.