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}$
• Downstream Primary-Key Footprint (the generator itself stores nothing; this is what consumers pay to index the IDs, and it is why 8-byte IDs beat 16-byte UUIDs): $9.47 \times 10^{12}\text{ IDs/year} \times 8\text{ bytes} \approx 75.8\text{ TB/year of key columns}$ (vs. 151.5 TB with 128-bit UUIDs)

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

Synthesizing vector architecture diagram...

Start with the clients in the "Client Applications & Ingestion Pipelines" panel. API gateways and the order service call the generator fleet over gRPC through an internal NLB, while the high-volume event stream skips the network entirely and embeds the generator as a library (dotted arrow). In the "ID Generator Fleet" panel, each worker creates IDs locally; to stay unique, it must own a worker ID nobody else uses. That is the job of the "Worker ID Lease Coordination Tier" panel: each worker holds a lease in DynamoDB, renewed every 30 s, so a crashed worker's ID frees up only after its lease expires, and it syncs its clock to Amazon Time Sync. Uniqueness depends on two things only: no shared worker IDs (the lease) and a clock that never goes backward (time sync plus a monotonic check).

Data Flow Walkthrough

1. Zero-Coordination ID Ingress: Upstream clients (or embedded libraries) issue GenerateId requests via internal L4 NLB over persistent multiplexed gRPC connections to local ECS Fargate workers.
2. Atomic In-Memory Assembly: The worker evaluates the local monotonic clock ($T_{\text{curr}}$). If within the same millisecond as previous generation, it atomically increments its 12-bit sequence counter. It bit-shifts timestamp, datacenter ID, worker ID, and sequence into a single 64-bit integer in $< 0.1\text{ ms}$ with zero network coordination.
3. Lease Coordination & Fencing: Each worker dynamically maintains a 30-second lease in DynamoDB. A background thread heartbeats every 10 seconds. If a heartbeat is delayed within 5 seconds of lease expiration, the generator trips its fencing buffer and suspends generation before split-brain duplicate allocation can occur.

Concrete Step-by-Step Request Walkthrough: Tracing an ID Generation & Lease Heartbeat

---

4. API Interface Design & ID Structure

64-bit Bitfield Layout

Bits are numbered from 0 (the most significant bit) to 63 (the least significant bit).

The five fields add up to 1 + 41 + 5 + 5 + 12 = 64 bits. Because the timestamp sits in the most significant bits after the sign bit, an ID made in a later millisecond is always larger than an ID made in an earlier millisecond, so the IDs sort by creation time. Within one millisecond, the data center, the worker and the sequence counter make each ID unique.

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;
}

gRPC Status Codes & Error Contracts

---

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 with an incremented fencing_epoch:

   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": "1767225630000"},
       "fencing_epoch": {"N": "104"},
       "version": {"N": "1"}
     },
     "ConditionExpression": "attribute_not_exists(PK) OR lease_expiry_ts < :now_ms",
     "ExpressionAttributeValues": { ":now_ms": {"N": "1767225600000"} }
   }

3. Once claimed, a background daemon heartbeats every 10 seconds, extending lease_expiry_ts by 30 seconds.
4. Lease Safety Margin: Worker nodes verify that current_time < lease_expiry_ts - 5000ms. If network latency or a GC pause delays the heartbeat within 5 seconds of expiry, the worker proactively suspends ID generation before the lease expires, eliminating split-brain collision windows.
5. If the worker crashes, its lease expires, allowing a replacement container to reclaim the slot with an incremented fencing_epoch.

---