Design a Unique ID Generator in Distributed Systems
A single database can use auto_increment for primary keys. In a distributed system that breaks down: one database isn't big enough, and generating unique IDs across many databases with low latency is hard. Let's look at four approaches and build Twitter's Snowflake.
- 7.1RequirementsFrom the interview: Every ID is unique. IDs contain digits only (no letters). Each ID fits in 64 bits. IDs are ordered by date: one created…
- 7.2Option 1: Multi-master replicationUse the database's auto_increment, but increase by k instead of 1, where k is the number of database servers. Server 1 generates 1, 3, 5…;…
- 7.3Option 2: UUIDA UUID is a 128-bit number, e.g. 09c93e62-50b4-468d-bf8a-c07e1040bfb2. The chance of a collision is tiny: generate 1 billion UUIDs per…
- 7.4Option 3: Ticket serverFlickr built ticket servers: a centralized auto_increment feature in a single database server (the ticket server). Every web server asks it…
- 7.5Option 4: Twitter Snowflake ✅Divide and conquer: instead of generating an ID directly, split the 64 bits into sections: Section Bits Meaning Sign 1 Always 0. Reserved…
- 7.6Deep dive and wrap upTimestamp 41 bits hold at most 2⁴¹ − 1 = 2,199,023,255,551 milliseconds, which is about 69 years. So a Snowflake generator works for ~69…