{"title":"Design Unique ID Generator","description":null,"content":"\n> **QUESTION**\n>\n> #### What is a Unique ID Generator?\n>\n> A unique ID generator is a system that produces identifiers that are globally unique across distributed services. These IDs are used to identify entities like users, orders, transactions, or messages in large-scale systems.\n>\n> Examples include Twitter’s Snowflake IDs, UUIDs, and database auto-increment keys.\n\n\nLet’s begin by clarifying the requirements.\n\n---\n\n# 1. Clarifying Requirements\n\nA system design interview should always start with a conversation to scope the problem. Here’s an example of how a candidate-interviewer discussion might flow:\n\n\n> **DISCUSSION**\n>\n> **Interviewer:** \"Let's design a distributed unique ID generator.\"\n>\n> **Candidate:** \"Great. First, I want to clarify the properties these IDs should have. Is global uniqueness the only hard requirement, or do they also need to be sortable?\"\n>\n> **Interviewer:** \"Good question. Let's say they should be roughly sortable by the time of creation.\"\n>\n> **Candidate:** \"Okay. And what about the format? Should they be numeric or can they be strings?\"\n>\n> **Interviewer:** \"Let's stick to numeric, preferably a 64-bit integer, so it fits in a standard `bigint` column.\"\n>\n> **Candidate:** \"Got it. In terms of non-functional requirements, I'll assume the service needs to be highly available, low-latency, and horizontally scalable to handle millions of requests per second.\"\n\n\n\n> **DEFINITION**\n>\n> #### What is K-Sortability?\n>\n> An ID is said to be **K-sortable** if it is **roughly ordered by creation time** meaning that newer IDs are usually greater than older ones, though slight out-of-order scenarios may occur due to distributed generation.\n\n\nAfter gathering the details, we can summarize the key system requirements.\n\n\n### Functional Requirements\n\n1. **Unique ID Generation:** Generate globally unique IDs across distributed services. Each ID must fit within **64 bits.**\n2. **Time Ordering:** IDs should be **K-sortable**, meaning they roughly increase with creation time.\n\n### Non-Functional Requirements\n\n1. **High Availability:** The service must be resilient to node failures. Aim for 99.99% availability.\n2. **Scalability:** The system must scale to handle very high throughput (millions of IDs/sec).\n3. **Low Latency:** ID generation should be extremely fast (e.g., <2ms).\n4. **K-Sortable:** IDs should be roughly sortable by creation time.\n\n\n---\n\n# 2. Approaches to ID Generation\n\n\n> [!PAYWALL] This content is for premium members only.\n\n\nNow that we’ve clarified the requirements, let’s explore several approaches to generating unique IDs, evaluating how each performs across **scalability**, **availability**, **ordering**, and **complexity** dimensions.\n\n## Approach 1: Database Auto-Increment\n\nThe simplest way to generate unique IDs is by using a **centralized database sequence** or an **auto-incrementing primary key**.\n\nIn this setup, a single database server maintains a counter. Each time a client requests an ID, the database increments the counter and returns the new value, guaranteeing strict order and uniqueness.\n\nThis is commonly implemented with an `AUTO_INCREMENT` or `IDENTITY` column in SQL.\n\n\n```sql\nCREATE TABLE tickets (\n id BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,\n stub CHAR(1) NOT NULL DEFAULT '' UNIQUE\n);\n```\n\n\nEvery time a new record is inserted, the database automatically assigns the next sequential `id` value.\n\nThis creates a simple but problematic architecture where all services depend on a single database for ID generation.\n\n\n```mermaid\nflowchart TB\n subgraph CLIENTS[\"Clients\"]\n direction LR\n SA[ServiceA]:::primary ~~~ SB[ServiceB]:::primary ~~~ SC[ServiceC]:::primary\n end\n\n DB[(Database)]:::green\n\n SA -->|ID Request| DB\n SB -->|ID Request| DB\n SC -->|ID Request| DB\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nWhile simple, this centralized approach comes with significant trade-offs.\n\n\n### Pros\n\n- **Guaranteed Uniqueness:** The database enforces uniqueness by design.\n- **Strict Ordering:** IDs are monotonically increasing, which makes sorting and indexing straightforward.\n- **Simplicity:** Easy to implement and maintain, ideal for small-scale applications.\n\n### Cons\n\n- **Single Point of Failure (SPOF):** If the database fails, the entire ID generation process stops.\n- **Scalability Bottleneck:** All ID requests go to one server, limiting horizontal scalability.\n- **High Latency:** Each ID request requires a network round trip to the central database.\n- **Limited Throughput:** The database can only handle a limited number of writes per second, which caps the rate of ID generation.\n\n\n\n> **Verdict - Bad**\n>\n> This approach works fine for small, monolithic systems but fails to meet the needs of **large-scale, distributed environments**. It introduces a **bottleneck** and a **single point of failure**, violating both scalability and availability requirements.\n\n\n### Adapting Auto-Increment for Distributed Systems\n\nTo overcome the limitations of a single database, you can adapt the auto-increment strategy for a multi-node environment using two common techniques.\n\n#### 1. Range-Based ID Allocation\n\nIn this model, each database node is pre-assigned a unique and non-overlapping **range of IDs**. This allows each node to generate IDs independently without communicating with others.\n\n\n```mermaid\nflowchart TB\n subgraph RANGES[\"ID Allocation Ranges\"]\n direction LR\n N1[(DB Node-1
1 - 100,000)]:::green ~~~ N2[(DB Node-2
100,001 - 200,000)]:::green ~~~ N3[(DB Node-3
200,001 - 300,000)]:::green\n end\n\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nFor example, in a three-node setup:\n\n- Node 1 can use IDs from 1 to 100000.\n- Node 2 can use IDs from 100001 to 200000.\n- Node 3 can use IDs from 200001 to 300000.\n\n##### Limitations of Range-Based Allocation\n\n1. **Range Exhaustion**: High-traffic nodes may exhaust their assigned range quickly, requiring reallocation or range expansion.\n2. **Complex Management**: As nodes are added or removed, reassigning and managing ranges can become complex.\n3. **Waste of ID Space**: Uneven traffic across nodes may leave some ranges underutilized.\n\n#### 2.Step-Based Auto-Increment\n\nIn this approach, each node generates IDs using a common **step size** equal to the number of nodes. Each node is also given a unique starting offset. This creates an \"interleaving\" pattern of IDs.\n\nFor example, if the step size is 3:\n\n- Node 1 starts at `1` and generates IDs: 1, 4, 7, 10, ...\n- Node 2 starts at `2` and generates IDs: 2, 5, 8, 11, ...\n- Node 3 starts at `3` and generates IDs: 3, 6, 9, 12, ...\n\nThis method ensures uniqueness but makes it difficult to add new nodes, as it would require changing the step size and offsets across the entire cluster.\n\n---\n\n## Approach 2: UUID\n\nA **UUID** is a 128-bit value designed to be unique across space and time without requiring any coordination between systems.\n\nUnlike centralized or database-based approaches, UUIDs can be generated **independently on any machine** while still maintaining near-zero probability of collision.\n\nThere are multiple versions of UUIDs, but the two most commonly discussed are **UUID v1** and **UUID v4**.\n\n### UUID v1 (Time + MAC-based)\n\nUUID v1 combines a **timestamp** (down to 100-nanosecond precision) and the machine's **MAC address**.\n\nThis combination ensures **global uniqueness** since MAC addresses are unique per device, and timestamps prevent collisions within the same machine.\n\n#### Example\n\nA UUID v1 value encodes both a high-precision timestamp and the MAC address of the generating machine, making the structure readable if you know where each segment begins and ends:\n\n\n```shell\n6ba7b810-9dad-11d1-80b4-00c04fd430c8\n```\n\n\nHere, the time component `6ba7b810-9dad-11d1` represents a specific point in time, and the node component `00c04fd430c8` is derived from the machine's MAC address.\n\nUUID v1 is roughly time-sortable because it embeds the timestamp, but it also exposes the MAC address and generation time posing potential privacy risks.\n\n### UUID v4 (Random-based)\n\nThis is the most common version today. It's generated using **122 bits of cryptographically secure randomness**. Only 6 bits are used for static version and variant information.\n\n#### Example\n\nA UUID v4 value is visually indistinguishable from a random string of hex characters, with only the version digit (the `4` at the start of the third segment) identifying it as a v4 UUID:\n\n\n```shell\n550e8400-e29b-41d4-a716-446655440000\n```\n\n\nHere, the `4` in `41d4` indicates that it's a v4 UUID, and all other parts are generated randomly.\n\nThe probability of two UUID v4 values colliding is so infinitesimally small it's considered negligible for all practical purposes.\n\n\n### Pros\n\n- **Simple and Decentralized:** No coordination or central service is required. Every node can generate IDs independently.\n- **No Network Latency:** ID generation happens locally and instantly.\n- **Collision-Free in Practice:** Astronomically low probability of duplicates, even across billions of nodes.\n- **Mature and Standardized:** Supported natively in most programming languages and databases.\n\n### Cons\n\n- **Not K-Sortable (v4):** Randomly distributed IDs destroy index locality, causing **fragmented B-tree indexes** and **slower inserts** in databases.\n- **Not Numeric:** UUIDs are 128 bits and typically represented as **36-character strings**, which take more space and memory to store and index.\n- **Potential Security Risks (v1):** Since UUID v1 encodes both the **MAC address** and **timestamp**, it can potentially expose **system-level and temporal information**.\n- **Higher Storage and Bandwidth Overhead:** Compared to compact 64-bit numeric IDs, UUIDs consume twice the space and are less cache-friendly.\n\n\n\n> **Verdict - Good**\n>\n> UUIDs are an excellent choice for **logging**, **trace IDs**, **correlation identifiers**, or **temporary tokens** where decentralization and ease of generation matter most.\n>\n> However, for a system that requires **sortable**, **numeric**, and **compact 64-bit IDs** (like those used in databases or distributed message queues), UUIDs are **suboptimal**. They break index locality and can degrade write performance as the dataset grows.\n\n\n### UUID v7 (Time-based + Random)\n\n**UUID v7** is a **new emerging standard** that combines the **time-ordering of Snowflake** with the **simplicity and decentralization of traditional UUIDs**.\n\n#### Structure of UUID v7\n\n- **48 bits:** Unix timestamp (in milliseconds)\n- **4 bits:** Version (`7`)\n- **76 bits:** Cryptographically secure random data\n\nThe leading timestamp ensures that IDs are chronologically sortable (K-sortable). The large random portion guarantees uniqueness with an extremely low probability of collision, even when millions of nodes are generating IDs in the same millisecond.\n\nUUID v7 is poised to become the new standard for primary keys in distributed systems, but it's important to understand its trade-offs.\n\n\n### Pros\n\n- **K-Sortable by Default:** Excellent for database index locality and write performance.\n- **Fully Decentralized:** No coordination or worker ID assignment is needed.\n- **Simple Generation:** Can be generated locally without network calls.\n- **Globally Unique:** The random component makes collisions practically impossible.\n\n### Cons\n\n- **Size:** At **128 bits**, it's twice the size of a 64-bit Snowflake ID, consuming more storage and index space.\n- **Adoption:** As an emerging standard, it is not yet natively supported in all databases or frameworks.\n\n\n---\n\n## Approach 3: Ticket Server\n\nThe **Ticket Server** is a clever evolution of the centralized database model. Instead of hitting the database for every single ID, application servers fetch a **block (or range) of IDs** in one go and then dispense them from local memory.\n\nThis method was **famously used by Flickr** and later adopted by several large-scale systems before distributed ID generation algorithms (like Snowflake) became popular.\n\n### How It Works\n\nThe architecture introduces a dedicated, lightweight service (the Ticket Server) that acts as the single source of truth for ID blocks.\n\n\n```mermaid\nflowchart TB\n subgraph APPS[\"App Servers\"]\n direction LR\n A1[App Server 1
Caches ID Block]:::primary ~~~ A2[App Server 2
Caches ID Block]:::primary\n end\n\n subgraph CENTRAL[\"Central Service\"]\n direction TB\n TS[Ticket Server]:::orange\n DB[(Database
Single Counter)]:::green\n TS -->|1. Fetches next block| DB\n end\n\n A1 -->|2. Request ID Block| TS\n A2 -->|2. Request ID Block| TS\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n1. A central **Ticket Server** manages the allocation of ID ranges.\n2. It uses a database for persistence, storing only a single counter for the next available ID.\n3. An **Application Server** requests a block of IDs (e.g., a block of 1,000) from the Ticket Server.\n4. The Ticket Server makes a single, **atomic** call to the database to reserve the next block.\n5. It returns the reserved range (e.g., `[1001, 2000]`) to the Application Server.\n6. The Application Server then serves IDs from this range in-memory, requiring no further network calls until its block is exhausted.\n\nThis architecture dramatically reduces the load on the database, as it's now only contacted once per block instead of once per ID.\n\nThe sequence diagram below shows the detailed interaction:\n\n\n```mermaid\nsequenceDiagram\n participant A as App Server\n participant T as Ticket Server\n participant D as Database\n\n Note over A: Needs a new ID, but
local block is empty.\n A->>T: Request new ID block (size=1000)\n T->>D: Atomically update and get next block start\n D-->>T: Return new start_id: 5001\n T-->>A: Here is your block: [5001, 6000]\n Note over A: Serves IDs 5001, 5002, ...
from local memory.\n```\n\n\nTo atomically reserve a block, the Ticket Server can run a single atomic SQL command:\n\n\n```sql\n-- Reserve a block of 1000 IDs and return the new starting ID of the block.\nUPDATE tickets SET id = LAST_INSERT_ID(id + 1000);\nSELECT LAST_INSERT_ID();\n```\n\n\n\n### Pros\n\n- **Numeric and K-Sortable:** IDs are sequential, making them efficient for indexing and range queries.\n- **Reduced Database Load:** Only occasional requests are made to the database (once per block).\n- **Low Latency:** Most IDs are served directly from memory, eliminating per-request round trips.\n- **Simple Scaling for Read-Heavy Workloads:** By increasing block sizes or caching strategies, you can achieve very high throughput.\n\n### Cons\n\n- **Single Point of Failure (SPOF):** The Ticket Server becomes a bottleneck and a single dependency. If it goes down, no new IDs can be allocated.\n- **Operational Complexity:** Clients must handle local block exhaustion gracefully and fetch new blocks efficiently.\n- **High Availability Setup is Non-Trivial:** Making the ticket server highly available (e.g., using leader election or primary-secondary replication) adds configuration and coordination complexity.\n- **Potential ID Gaps:** If a server crashes before using up its allocated range, some IDs in that range are permanently lost (which may or may not be acceptable).\n\n\n\n> **Verdict - Good**\n>\n> The Ticket Server is a **solid, battle-tested approach** that offers a pragmatic balance between simplicity and performance. It’s significantly better than a direct database-based generator and is **still used in many production systems** today.\n>\n> However, it’s not fully decentralized. It depends on a **centralized (though optimized) service** for coordination.\n\n\n---\n\n## Approach 4: Snowflake-like Service\n\nThe **Snowflake algorithm**, originally developed by **Twitter** (now X), is a **decentralized and highly scalable** approach for generating globally unique, time-ordered 64-bit IDs.\n\nIt is widely considered the **gold standard** for distributed ID generation balancing **uniqueness**, **ordering**, **performance**, and **fault tolerance** without relying on a single coordination point at runtime.\n\n### How It Works\n\nEach generated **64-bit ID** is composed of multiple parts, each serving a specific purpose. The design cleverly encodes time, machine identity, and per-millisecond sequencing into a single compact number.\n\n\n```mermaid\nflowchart LR\n SIGN[\"1 bit
0
(Sign)\"]:::orange\n TS[\"41 bits
Timestamp
(milliseconds)\"]:::primary\n DC[\"5 bits
Datacenter ID\"]:::teal\n MID[\"5 bits
Machine ID\"]:::green\n SEQ[\"12 bits
Sequence Number\"]:::orange\n\n SIGN --- TS --- DC --- MID --- SEQ\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n#### 1. Sign Bit (1 bit)\n\nThis bit is always set to **0** so the generated number stays **positive**. That keeps the ID inside the signed 64-bit integer range used by most databases.\n\n#### 2. Timestamp (41 bits)\n\nThis field holds the **number of milliseconds since a custom epoch** (e.g., `2020-01-01 00:00:00 UTC`). Using a custom epoch rather than the Unix epoch (1970) extends the usable lifespan. A 41-bit timestamp can represent `2^41milliseconds ≈ 69 years`.\n\n#### 3. Datacenter ID (5 bits)\n\nThis field identifies the **data center or region** where the ID was generated. It supports up to `2^5 = 32` data centers, which helps maintain uniqueness in multi-region deployments.\n\n#### 4. Machine ID (5 bits)\n\nThis field identifies the **worker or node** within the data center and supports `2^5 = 32` machines per data center. Together, the datacenter and machine bits provide `2^10 = 1024` unique workers globally.\n\n#### 4. Sequence Number (12 bits)\n\nThis is a **counter** that increments for each ID generated within the same millisecond **on the same machine**, and resets to 0 when the millisecond changes. It supports up to `2^12 = 4096` unique IDs per millisecond per machine.\n\nThis allows a single machine to generate millions of IDs per second with virtually no contention. Each field is bit-shifted and combined into a single 64-bit integer using bitwise operations.\n\n#### Example (Pseudocode)\n\nThe final ID is assembled by left-shifting each field to its correct bit position and combining the three values with a bitwise OR:\n\n\n```python\nid = ((timestamp - custom_epoch) << 22) | (machine_id << 12) | sequence_number\n```\n\n\nThe result is a compact, globally unique, **time-ordered ID**.\n\n#### Advantages\n\n- **Globally Unique:** No collisions across time, machines, or processes.\n- **K-Sortable:** IDs are roughly ordered by time, aiding database indexing and time-based queries.\n- **High Throughput:** Generates millions of IDs per second per node without coordination.\n- **Low Latency:** All logic runs locally, with no network dependency.\n- **Horizontally Scalable:** Add more machines to increase capacity linearly.\n- **Compact:** Fits neatly within 64 bits (unlike UUIDs).\n\n#### Potential Challenges\n\n- **Clock Drift:** If system clocks move backward, duplicate IDs can be generated.\n - Mitigation: Detect backward jumps and **pause ID generation** until the clock catches up.\n- **Machine ID Coordination:** Requires a reliable way to assign and track unique machine IDs.\n - Common solutions include **Zookeeper**, **Etcd**, or **central registry services**.\n- **Time Dependency:** When the 69-year window expires, a new epoch and migration strategy are needed.\n\n\n> **Verdict - Great**\n>\n> The **Snowflake-like service** meets all the key requirements:\n>\n> - Globally unique\n> - 64-bit numeric\n> - K-sortable (time-ordered)\n> - Highly performant and scalable\n> - No runtime central coordination\n>\n> This makes it the **most balanced and production-ready approach** for distributed ID generation. Many large-scale systems, including **Twitter**, **Instagram**, **Discord**, and **Netflix** have used variations of this design.\n\n\n---\n\n# 3. Detailed Design\n\nNow that we understand the Snowflake algorithm conceptually, let’s design the **architecture** and **implementation details** for a Snowflake-based ID generation service that can scale horizontally and operate reliably under real-world distributed conditions.\n\n### Architecture Overview\n\nAt a high level, the **ID Generator Service** consists of a cluster of **stateless nodes**. Each node can independently generate unique IDs once it acquires a **unique worker ID** during startup.\n\n\n```mermaid\nflowchart TB\n subgraph CLIENTS[\"Clients\"]\n direction LR\n C1[App Server 1]:::primary ~~~ C2[App Server 2]:::primary ~~~ C3[App Server 3]:::primary\n end\n\n LB[LoadBalancer]:::orange\n\n subgraph IDGEN[\"ID Generator Service\"]\n direction LR\n N1[Node
worker_id=1]:::green ~~~ N2[Node
worker_id=2]:::green ~~~ N3[Node
worker_id=3]:::green\n end\n\n subgraph COORD[\"Coordination\"]\n ZK[Zookeeper]:::orange\n end\n\n CLIENTS -->|HTTP Request| LB\n LB --> IDGEN\n N1 -->|Register on startup| ZK\n N2 -->|Register on startup| ZK\n N3 -->|Register on startup| ZK\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Worker ID Assignment\n\nThe **most critical requirement** for this design is ensuring that **no two nodes share the same worker ID** (10 bits total: 5 bits for datacenter + 5 bits for machine).\n\nIf two nodes accidentally share the same worker ID, they could produce duplicate IDs violating the system’s core guarantee.\n\nWe use a **coordination service like ZooKeeper or etcd** to assign unique worker IDs dynamically.\n\n#### How It Works\n\n- On startup, each generator node creates an **ephemeral sequential znode** under a path such as `/workers/id-`.\n- ZooKeeper automatically appends a **monotonically increasing sequence number**, ensuring uniqueness.\n - Node 1 → `/workers/id-0000000001`\n - Node 2 → `/workers/id-0000000002`\n - Node 3 → `/workers/id-0000000003`\n- The node parses its sequence number and uses it as its **worker ID**.\n- If a node fails or disconnects, its ephemeral znode is automatically deleted, making its worker ID reusable.\n\nThis mechanism guarantees **automatic registration, uniqueness, and fault recovery** without human intervention.\n\n### Clock Synchronization\n\nThe **timestamp** component of the Snowflake ID makes the system sensitive to **clock drift** across servers.\n\nIf a node’s system clock moves backward, it could generate IDs that overlap with previously issued ones.\n\n##### Example\n\nSuppose a node’s clock jumps backward by 50 ms. The node now thinks it’s in an earlier time than the last generated ID, so if it continues generating IDs, they could **collide** with older ones, violating global uniqueness.\n\n### Solution\n\n##### 1. NTP Synchronization\n\nAll nodes should run **Network Time Protocol (NTP)** daemons that synchronize their clocks with a trusted central source (e.g., a stratum 1 time server).\n\n#### 2. In-Service Detection\n\nThe generator should track the last timestamp used. If the current system time is **less than the last recorded timestamp**, it must:\n\n- **Option 1 (Safer):** Reject ID generation requests with an error, prompting clients to retry later.\n- **Option 2 (Lenient):** Spin-wait until the system clock catches up.\n\n##### 3. Trade-Offs\n\nThe **spin-wait** method adds latency and can block threads. The **reject** method offloads retry logic to the client but ensures no duplicate IDs are ever emitted.\n\nIn practice, **rejecting** is preferred in **safety-critical systems**, while **spin-wait** is acceptable in **low-latency internal tools**.\n\n### Implementation\n\nBelow is a simplified **thread-safe implementation** of the core Snowflake ID generator logic.\n\n\n```java\nimport java.time.Instant;\n\npublic class SnowflakeGenerator {\n private final long workerId;\n private final long epoch = 1577836800000L; // Custom epoch: 2020-01-01T00:00:00Z\n\n private long lastTimestamp = -1L;\n private long sequence = 0L;\n\n // Bit layout constants\n private static final int WORKER_ID_BITS = 10;\n private static final int SEQUENCE_BITS = 12;\n private static final long MAX_WORKER_ID = (1L << WORKER_ID_BITS) - 1;\n private static final long SEQUENCE_MASK = (1L << SEQUENCE_BITS) - 1;\n\n public SnowflakeGenerator(long workerId) {\n if (workerId < 0 || workerId > MAX_WORKER_ID) {\n throw new IllegalArgumentException(\"Worker ID must be between 0 and \" + MAX_WORKER_ID);\n }\n this.workerId = workerId;\n }\n\n public synchronized long nextId() {\n long currentTimestamp = System.currentTimeMillis();\n\n // Clock moved backwards, wait until it catches up.\n if (currentTimestamp < lastTimestamp) {\n // Option 1: Throw exception (safer for critical systems)\n throw new IllegalStateException(\"Clock moved backwards. Refusing to generate ID for \" + (lastTimestamp - currentTimestamp) + \" milliseconds\");\n // Option 2: Wait (can add latency)\n // while (currentTimestamp < lastTimestamp) {\n // currentTimestamp = System.currentTimeMillis();\n // }\n }\n\n if (currentTimestamp == lastTimestamp) {\n sequence = (sequence + 1) & SEQUENCE_MASK;\n if (sequence == 0) {\n // Sequence overflowed, wait for the next millisecond\n currentTimestamp = waitUntilNextMillis(lastTimestamp);\n }\n } else {\n // New millisecond, reset sequence\n sequence = 0L;\n }\n\n lastTimestamp = currentTimestamp;\n\n return ((currentTimestamp - epoch) << (WORKER_ID_BITS + SEQUENCE_BITS)) |\n (workerId << SEQUENCE_BITS) |\n sequence;\n }\n\n private long waitUntilNextMillis(long lastTimestamp) {\n long timestamp = System.currentTimeMillis();\n while (timestamp <= lastTimestamp) {\n timestamp = System.currentTimeMillis();\n }\n return timestamp;\n }\n}\n```\n\n```python\nimport threading\nimport time\n\nclass SnowflakeGenerator:\n # Bit layout constants\n WORKER_ID_BITS = 10\n SEQUENCE_BITS = 12\n MAX_WORKER_ID = (1 << WORKER_ID_BITS) - 1\n SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1\n\n def __init__(self, worker_id: int, epoch: int = 1577836800000):\n \"\"\"\n :param worker_id: Unique ID for this worker (0 <= worker_id <= 1023)\n :param epoch: Custom epoch in milliseconds (default: 2020-01-01T00:00:00Z)\n \"\"\"\n if worker_id < 0 or worker_id > self.MAX_WORKER_ID:\n raise ValueError(f\"Worker ID must be between 0 and {self.MAX_WORKER_ID}\")\n\n self.worker_id = worker_id\n self.epoch = epoch\n self.last_timestamp = -1\n self.sequence = 0\n self.lock = threading.Lock()\n\n def _current_time(self) -> int:\n \"\"\"Return current time in milliseconds.\"\"\"\n return int(time.time() * 1000)\n\n def _wait_until_next_millis(self, last_timestamp: int) -> int:\n \"\"\"Wait until the next millisecond.\"\"\"\n timestamp = self._current_time()\n while timestamp <= last_timestamp:\n timestamp = self._current_time()\n return timestamp\n\n def next_id(self) -> int:\n \"\"\"Generate the next unique Snowflake ID (thread-safe).\"\"\"\n with self.lock:\n current_timestamp = self._current_time()\n\n # Handle clock rollback\n if current_timestamp < self.last_timestamp:\n raise RuntimeError(\n f\"Clock moved backwards. Refusing to generate ID for \"\n f\"{self.last_timestamp - current_timestamp} milliseconds\"\n )\n\n # Same millisecond → increment sequence\n if current_timestamp == self.last_timestamp:\n self.sequence = (self.sequence + 1) & self.SEQUENCE_MASK\n if self.sequence == 0:\n # Sequence overflow → wait for next millisecond\n current_timestamp = self._wait_until_next_millis(self.last_timestamp)\n else:\n # New millisecond → reset sequence\n self.sequence = 0\n\n self.last_timestamp = current_timestamp\n\n # Bit-shift and combine fields\n return (\n ((current_timestamp - self.epoch) << (self.WORKER_ID_BITS + self.SEQUENCE_BITS))\n | (self.worker_id << self.SEQUENCE_BITS)\n | self.sequence\n )\n\n# Example usage\nif __name__ == \"__main__\":\n generator = SnowflakeGenerator(worker_id=1)\n for _ in range(5):\n print(generator.next_id())\n time.sleep(0.001) # Sleep 1 ms between calls\n```\n\n\n---\n\n# 4. Summary and Wrap-Up\n\nWe designed a distributed unique ID generator based on the Snowflake algorithm. This approach is performant and scalable because it requires no runtime coordination between nodes.\n\n#### Key Takeaways\n\n- **Composition over Coordination:** The ID's uniqueness comes from its structure (timestamp + worker_id + sequence) rather than from a central authority.\n- **Worker ID is Critical:** The most important design decision is how to reliably assign unique worker IDs. ZooKeeper is an excellent tool for this.\n- **Time Matters:** Relying on system clocks introduces challenges that must be handled gracefully, primarily through NTP and defensive service logic.\n\n\n> **SUCCESS**\n>\n> #### **Interview Checklist:**\n>\n> 1. **Requirements:** Start by defining the properties of the ID (unique, numeric, sortable).\n> 2. **Compare Approaches:** Discuss the pros and cons of databases, UUIDs, and ticket servers.\n> 3. **Propose Snowflake:** Introduce the Snowflake concept as the ideal solution.\n> 4. **Break Down the ID:** Explain the bit-level composition of a Snowflake ID.\n> 5. **Design the System:** Detail the architecture, focusing on worker ID assignment and clock synchronization.\n> 6. **Discuss Trade-offs:** Acknowledge the reliance on NTP and the limits of the design (e.g., the 69-year lifespan).\n\n\n---\n\n# Quiz","pageType":"system-design-interviews"}

Get Premium