System Design Interview: Globally Unique ID Generation

It’s been a while since my last system design interview post. I figure it’s about time to pick up the series again. Today, I want to talk about globally unique ID generation. It sounds like an interesting topic, through which interviewers can see the depth of knowledge candidates have.

Requirements

First, let’s decipher the topic word by word.

• Globally: it implies that there are multiple systems, components, or machines that are working together. We should consider them as a whole. At the same time we should not forget that they may be somewhat decoupled, making coordination challenging.
• Unique: it needs to be exclusive, one and only. Duplicates are disallowed. Repetition is forbidden. Collision is catastrophic.
• ID: it may be an integer. If it’s an integer, we need to ask the range — signed vs unsigned, 32 bits vs 64 bits. It may be a string. If it’s a string, we need to ask about the character set, the encoding — UTF-8 vs ASCII, and the min-max length.
• Generation: the system needs to create those IDs. It may provide it as a service to other systems.

The next step in a system design interview is usually asking clarification questions. But a trick is that for those open ended questions, interviewers are often amenable to us stating our assumption and asking for confirmation. So we have a chance to steer the conversation towards the direction that we feel comfortable…