Design a Distributed Unique ID Generator

1. Problem Statement & Scope Clarification

System Mission

Design a distributed, highly available, low-latency 64-bit unique ID generation service (similar to Twitter Snowflake / Instagram ID generator) capable of generating globally unique, roughly time-sortable 64-bit numeric IDs across multiple data centers and AWS regions with zero runtime inter-node network coordination.

Functional Requirements

1. Global Uniqueness: Zero ID collisions across all AWS regions, availability zones, and worker instances over a 70-year operating horizon.
2. 64-bit Integer Representation: Must fit inside a standard 64-bit signed integer (int64 / BIGINT in SQL databases) to minimize primary key index bloat and fit cache lines efficiently.
3. Roughly Time-Ordered (K-Ordered): Chronologically sortable by generation timestamp to prevent database B-Tree index fragmentation and random page splits on insertion.
4. High Throughput & Low Latency: Support $> 500,000\text{ IDs/sec}$ aggregate throughput per cluster with sub-millisecond ($P99 < 1\text{ ms}$) generation latency.
5. Batch Generation: Support atomic batch requests (up to 1,000 IDs per call) for high-throughput transactional ingest pipelines.

Non-Functional Requirements (SLAs & SLOs)

• Availability: $99.9999\%$ ("six nines") uptime SLA — ID generation is in the critical path of every write request in an enterprise architecture.
• Latency: $P50 < 0.2\text{ ms}$, $P99 < 1.0\text{ ms}$, $P99.9 < 3.0\text{ ms}$.
• Clock Drift Safety: Absolute monotonicity within individual worker processes; graceful wait-or-reject semantics if system hardware clock steps backward.
• Client JSON Compatibility: Safe serialization as string for 64-bit unsigned integers to avoid IEEE-754 double precision truncation in JavaScript clients (Number.MAX_SAFE_INTEGER = 2^{53} - 1).

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Traffic & Generation Scale

• Global Average Write QPS: $100,000\text{ IDs/sec}$.
• Peak Write QPS ($3\times$ multiplier): $300,000\text{ IDs/sec}$.
• Annual ID Volume: $300,000\text{ IDs/sec} \times 86,400\text{ sec/day} \times 365.25\text{ days/year} \approx 9.47 \times 10^{12}\text{ IDs/year}$
• Data Footprint for Generated IDs: $9.47 \times 10^{12}\text{ IDs/year} \times 8\text{ bytes} \approx 75.76\text{ TB/year}$

Bit-Space Longevity & Allocation Proof

A 64-bit integer is structured into 4 discrete bitfields:

1. Sign Bit (1 bit): Fixed to 0 to keep the integer strictly positive in signed 64-bit systems.
2. Timestamp (41 bits): Milliseconds elapsed since a custom epoch (e.g., 2026-01-01T00:00:00Z = $1767225600000\text{ ms}$). $\text{Max Lifespan} = \frac{2^{41} - 1}{1000 \times 60 \times 60 \times 24 \times 365.25} \approx \frac{2,199,023,255,551\text{ ms}}{31,557,600,000\text{ ms/year}} \approx \mathbf{69.68\text{ Years}}$ The service remains operational until year $2026 + 69 = 2095\text{ AD}$.
3. Data Center ID (5 bits): $2^5 = 32$ unique data center / AWS region partitions (e.g., 0 = us-east-1, 1 = us-west-2, 2 = eu-west-1, etc.).
4. Worker Machine ID (5 bits): $2^5 = 32$ unique worker nodes per data center. Total possible concurrent generator instances globally $= 32 \times 32 = 1,024\text{ nodes}$.
5. Sequence Number (12 bits): $2^{12} = 4,096$ unique IDs per millisecond per individual worker node.

Peak Theoretical Generation Capacity

$\text{Max Throughput per Node} = 4,096\text{ IDs/ms} = 4,096,000\text{ IDs/sec/node}$ $\text{Global Maximum Capacity (1,024 nodes)} = 1,024 \times 4,096,000 = \mathbf{4.194 \times 10^9\text{ IDs/sec}}$ This capacity exceeds the $300,000\text{ QPS}$ peak requirement by over $13,900\times$, providing massive headroom for multi-tenant enterprise growth.

3. High-Level Architecture & AWS Component Mapping

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

4. API Interface Design & ID Structure

64-bit Bitfield Layout

textCopy
 0 (1 bit)   1...........................41 (41 bits)    42......46 (5 bits)  47......51 (5 bits)  52..........63 (12 bits)
+----------+------------------------------------------+---------------------+--------------------+-------------------------+
| Sign (0) | Milliseconds Since Custom Epoch (69 yrs) | DataCenter ID (0-31)| Worker ID (0-31)   | Sequence Counter (0-4095)|
+----------+------------------------------------------+---------------------+--------------------+-------------------------+

gRPC Service Protocol (id_generator.proto)

protobufCopy
syntax = "proto3";

package hispeeddesign.idgen.v1;

service IdGeneratorService {
  // Generates a single 64-bit unique ID
  rpc GenerateId (GenerateIdRequest) returns (GenerateIdResponse);
  
  // Generates a batch of unique IDs atomically
  rpc GenerateIdBatch (GenerateIdBatchRequest) returns (GenerateIdBatchResponse);
}

message GenerateIdRequest {
  string caller_service = 1;
}

message GenerateIdResponse {
  int64 id = 1;              // Signed 64-bit representation
  string id_str = 2;          // String representation for JS safe integer parsing
  int64 timestamp_ms = 3;    // Milliseconds since Unix epoch extracted from ID
  int32 datacenter_id = 4;
  int32 worker_id = 5;
}

message GenerateIdBatchRequest {
  int32 count = 1;           // Max batch size: 1,000
  string caller_service = 2;
}

message GenerateIdBatchResponse {
  repeated int64 ids = 1;
  repeated string ids_str = 2;
  int64 epoch_offset_ms = 3;
}

5. Data Model & Worker Node Coordination Schema

Worker nodes dynamically acquire a (datacenter_id, worker_id) pair on startup via DynamoDB leases to prevent static configuration drift or duplicate assignments during Kubernetes / ECS auto-scaling.

DynamoDB Schema: WorkerNodeRegistryTable

Worker Node Lease Acquisition Algorithm

1. On container boot, the node discovers its AWS Region and sets datacenter_id (e.g., us-east-1 = 1).
2. It loops through worker_id from 0 to 31, attempting a conditional PutItem:

   jsonCopy
   {
     "TableName": "WorkerNodeRegistryTable",
     "Item": {
       "PK": {"S": "DC#01"},
       "SK": {"S": "WORKER#04"},
       "instance_id": {"S": "arn:aws:ecs:us-east-1:123456789:task/worker-04"},
       "ip_address": {"S": "10.0.4.182"},
       "lease_expiry_ts": {"N": "1767225630"},
       "version": {"N": "1"}
     },
     "ConditionExpression": "attribute_not_exists(PK) OR lease_expiry_ts < :now"
   }

3. Once claimed, a background daemon heartbeats every 10 seconds, extending lease_expiry_ts by 30 seconds.
4. If the worker crashes, its lease automatically expires in 30 seconds, allowing a replacement container to reclaim the slot.