Distributed Unique ID Generation

Generating Unique IDs at Scale

In a single-server setup, AUTO_INCREMENT is perfect. Independent shards can generate overlapping local sequences unless ranges, worker identifiers, or coordination separate them.

The Challenge: How do you generate globally unique, sortable, compact IDs across hundreds of servers without a centralized coordinator?

Requirements

A good distributed ID system must satisfy:

• Globally Unique: Choose a collision model: coordinated uniqueness under stated assumptions, or a sufficiently low probabilistic risk plus a uniqueness constraint.
• Sortable: Approximate time ordering can improve locality. Wall-clock timestamps do not establish global causal order across unsynchronized machines.
• Compact: 64-bit integers are better for database indexing than 128-bit strings.
• High Availability: ID generation cannot be a single point of failure (SPOF).
• High Performance: Must generate millions of IDs per second across the cluster.

Approach 1: UUID (Universally Unique Identifier)

A 128-bit number usually displayed as hex string: 123e4567-e89b-12d3-a456-426614174000.

UUID v4 (Random)

122 random bits plus fixed version/variant bits, generated with suitable randomness.

import uuid

id = uuid.uuid4()
print(id)  # e.g., '3c9f1b7a-4f3e-4e1a-9c2b-8d7e6f5a4b3c'

Pros:

• Can be generated offline by the client
• Zero coordination needed
• Extremely low collision probability (~0% for practical purposes)

Cons:

• Not sortable: Random ordering
• Database unfriendly: Indexing random UUIDs causes B-Tree page fragmentation
• Large size: 128 bits = 16 bytes (vs 8 bytes for int64)

Performance Impact:

-- Sequential IDs: New rows go to the end (fast)
INSERT INTO posts (id, ...) VALUES (1001, ...), (1002, ...);

-- Random UUIDs: New rows scattered everywhere (slow, fragmentation)
INSERT INTO posts (id, ...) VALUES (uuid(), ...), (uuid(), ...);

UUID v7 (Time-Ordered) ⭐

Modern UUID standard (RFC 9562) that embeds timestamp for sortability.

Structure:

• 48 bits: Unix timestamp in milliseconds
• 12 bits: Randomized sequence
• 62 bits: Random data
• 6 bits: Version and variant markers

// UUIDv7 layout with cryptographic randomness; no same-millisecond ordering.
function uuidv7() {
  const bytes = crypto.getRandomValues(new Uint8Array(16));
  let timestamp = BigInt(Date.now());
  if (timestamp < 0n || timestamp >= (1n << 48n)) {
    throw new RangeError("Timestamp does not fit UUIDv7");
  }
  for (let i = 5; i >= 0; i--) {
    bytes[i] = Number(timestamp & 255n);
    timestamp >>= 8n;
  }
  bytes[6] = (bytes[6] & 15) | 0x70;
  bytes[8] = (bytes[8] & 63) | 0x80;
  const hex = Array.from(bytes, b => b.toString(16).padStart(2, "0")).join("");
  return `${hex.slice(0, 8)}-${hex.slice(8, 12)}-${hex.slice(12, 16)}-${hex.slice(16, 20)}-${hex.slice(20)}`;
}

For production, prefer a maintained implementation with documented clock and monotonicity behavior. A UUID is not an authorization token.

Pros:

• Approximately time-ordered by its timestamp; events within a millisecond or across skewed clocks need not preserve insertion order
• Database friendly (sequential writes)
• No coordination needed

Cons:

• Still 128-bit (2x larger than int64)
• Requires storing as string or binary in most databases

Use Case: Ideal for databases that don't support custom ID generation but need sortability.

Approach 2: Central Ticket Server (Flickr Strategy)

Use a centralized database just to hand out IDs.

MySQL Implementation:

CREATE TABLE Tickets64 (
  id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
  stub CHAR(1) NOT NULL DEFAULT '' UNIQUE
);

-- Get next ID
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

Python Client:

def get_next_id():
    cursor.execute("REPLACE INTO Tickets64 (stub) VALUES ('a')")
    cursor.execute("SELECT LAST_INSERT_ID()")
    return cursor.fetchone()[0]

Pros:

• Simple to implement
• Guarantees sequential numbers
• Works with existing infrastructure

Cons:

• Single Point of Failure: If this DB dies, you can't create anything
• High latency: Network roundtrip for every ID (slow!)
• Limited throughput: Measure round-trip and allocator capacity under the chosen durability settings

Multi-Master Variant:

-- Server 1: IDs 1, 3, 5, 7, 9...
SET @@auto_increment_increment = 2;
SET @@auto_increment_offset = 1;

-- Server 2: IDs 2, 4, 6, 8, 10...
SET @@auto_increment_increment = 2;
SET @@auto_increment_offset = 2;

Reduces SPOF but IDs are no longer sequential.

Approach 3: Snowflake-style IDs

A 64-bit integer composed of bit-packed fields. Worker IDs, epochs, and bit allocations are deployment choices.

Bit Structure

Total: 64 bits (fits in a BIGINT)

Bit-field capacity, not measured implementation throughput:

• Per Machine: 4,096 IDs per millisecond = 4,096,000 IDs/sec
• Per Datacenter: 32 machines × 4M = 131M IDs/sec
• Total Cluster: 32 datacenters × 131M = 4.2 billion IDs/sec

Python teaching implementation

Worker IDs must be unique among active generators. This class protects threads within one process but does not coordinate another process using the same worker ID or persist the last timestamp across restarts.

import time
import threading

class SnowflakeIDGenerator:
    def __init__(self, datacenter_id, machine_id, custom_epoch=1609459200000):
        # Validation
        if datacenter_id < 0 or datacenter_id > 31:
            raise ValueError("Datacenter ID must be 0-31")
        if machine_id < 0 or machine_id > 31:
            raise ValueError("Machine ID must be 0-31")
        
        self.datacenter_id = datacenter_id
        self.machine_id = machine_id
        self.custom_epoch = custom_epoch  # Jan 1, 2021
        
        self.sequence = 0
        self.last_timestamp = -1
        self.lock = threading.Lock()
    
    def _current_millis(self):
        return int(time.time() * 1000)
    
    def _wait_next_millis(self, last_timestamp):
        timestamp = self._current_millis()
        while timestamp <= last_timestamp:
            timestamp = self._current_millis()
        return timestamp
    
    def generate_id(self):
        with self.lock:
            timestamp = self._current_millis()
            
            # Clock moved backwards!
            if timestamp < self.last_timestamp:
                raise Exception(f"Clock moved backwards. Refusing to generate ID for {self.last_timestamp - timestamp}ms")
            
            # Same millisecond - increment sequence
            if timestamp == self.last_timestamp:
                self.sequence = (self.sequence + 1) & 0xFFF  # 12-bit mask
                
                # Sequence overflow - wait for next millisecond
                if self.sequence == 0:
                    timestamp = self._wait_next_millis(self.last_timestamp)
            else:
                # New millisecond - reset sequence
                self.sequence = 0
            
            if not 0 <= timestamp - self.custom_epoch < (1 << 41):
                raise OverflowError("Timestamp does not fit the chosen epoch field")
            self.last_timestamp = timestamp
            
            # Build the ID
            id = ((timestamp - self.custom_epoch) << 22) | \
                 (self.datacenter_id << 17) | \
                 (self.machine_id << 12) | \
                 self.sequence
            
            return id

# Usage
generator = SnowflakeIDGenerator(datacenter_id=1, machine_id=3)

for _ in range(5):
    print(generator.generate_id())
    
# Output (example):
# 7045391791689121792
# 7045391791689121793
# 7045391791689121794
# 7045391791689121795
# 7045391791689121796

Decoding Snowflake IDs

def decode_snowflake(id, custom_epoch=1609459200000):
    timestamp = ((id >> 22) + custom_epoch) / 1000
    datacenter = (id >> 17) & 0x1F  # 5-bit mask
    machine = (id >> 12) & 0x1F
    sequence = id & 0xFFF
    
    import datetime
    dt = datetime.datetime.fromtimestamp(timestamp)
    
    return {
        'timestamp': dt.isoformat(),
        'datacenter_id': datacenter,
        'machine_id': machine,
        'sequence': sequence
    }

print(decode_snowflake(generator.generate_id()))
# Timestamp and decoded fields depend on the generated value and epoch.

The Clock Synchronization Problem

Snowflake relies on wall-clock time. What if the server's clock moves backward (NTP sync, leap seconds)?

Problem

10:00:00.100 → Generate ID: 123456
10:00:00.095 ← Clock goes backwards!
10:00:00.095 → Generate ID: 123455 (COLLISION!)

Solutions

Solution 1: Refuse to Generate (Strict)

if timestamp < self.last_timestamp:
    raise Exception(f"Clock moved backwards. Refusing to generate ID")

Pros: Guarantees uniqueness
Cons: Service downtime during clock skew

Solution 2: Wait Until Clock Catches Up

if timestamp < self.last_timestamp:
    # Wait up to 5ms for clock to catch up
    for _ in range(5):
        time.sleep(0.001)
        timestamp = self._current_millis()
        if timestamp >= self.last_timestamp:
            break
    else:
        raise Exception("Clock skew too large")

Solution 3: Use Sequence Bits as Buffer

if timestamp < self.last_timestamp:
    # Use extra sequence bits for small skews (< 1ms)
    if self.last_timestamp - timestamp < 10:
        timestamp = self.last_timestamp
        # Continue with sequence increment
    else:
        raise Exception("Clock skew too large")

Clock and worker safeguards

Reserve worker IDs without overlap, define behavior when time moves backwards, and prevent restart from reusing an already-issued (timestamp, worker, sequence) tuple. Monitor sequence exhaustion and epoch range. Time synchronization reduces drift but is not itself a uniqueness protocol. Use a consistent leap-second policy across the fleet.

Production Examples

Twitter Snowflake

• Original implementation: Powers tweet IDs, user IDs, DM IDs
• Bit-field capacity, not measured implementation throughput: 10,000+ IDs per second per machine
• Scale: Billions of tweets since 2010

Example Tweet ID:

1749823749823700000

This encodes:

• When it was tweeted
• Which datacenter
• Which server
• Sequence within that millisecond

Instagram Snowflake

Instagram uses a modified Snowflake with:

• 41 bits: timestamp
• 13 bits: shard ID (8,192 database shards)
• 10 bits: sequence (1,024 per ms per shard)

Discord Snowflake

Discord uses Snowflake for message IDs, channel IDs, user IDs:

// Extract timestamp from Discord message ID
const timestamp = (messageId >> 22) + 1420070400000;
const date = new Date(timestamp);

MongoDB ObjectId

Similar concept but 96-bit:

• 4 bytes: Unix timestamp
• 5 bytes: Random value
• 3 bytes: Incrementing counter

const ObjectId = require('mongodb').ObjectId;
const id = new ObjectId();
console.log(id.getTimestamp());  // Embedded timestamp!

Comparison Table

Interview Tips 💡

When discussing ID generation in interviews:

• Start with requirements: "Are IDs time-sortable? What's the expected QPS?"
• Compare approaches: "UUID v7 is simple but 128-bit. Snowflake is 64-bit and sortable but needs clock sync."
• Explain Snowflake: "41-bit timestamp, 10-bit worker ID, 12-bit sequence = 4M IDs/sec per machine"
• Mention clock skew: "We must handle clock going backwards. Strict mode refuses, graceful mode waits."
• Real example: "Twitter generates tweet IDs using Snowflake - 64-bit, sortable, billions created daily"
• Trade-offs: "UUID v7 is stateless (works anywhere). Snowflake needs assigned machine IDs but is more compact."

Common Pitfalls

⚠️ Using AUTO_INCREMENT in distributed databases: Leads to gaps and coordination overhead

⚠️ UUID v4 for primary keys: Causes index fragmentation and poor query performance

⚠️ Ignoring clock skew: Can generate duplicate IDs if system clock jumps backwards

⚠️ Hardcoding epoch: Choose an epoch far enough in the past to avoid offset issues

⚠️ Not monitoring ID generation: Track sequence overflows and clock skew events

Related Concepts

• Consistent Hashing — Distributing keys across nodes
• Database Sharding — Horizontal partitioning strategies
• Distributed Transactions — ACID in distributed systems
• Leader Election — Choosing a coordinator
• CAP Theorem — Trade-offs in distributed systems

Primary reference and validation

IETF RFC 9562 defines UUID variants, v7 layout, randomness, and monotonicity options. Test the version/variant bits, duplicate generation within one millisecond, clock rollback, and process restart. For a 64-bit ID in JavaScript, use BigInt or a decimal string: ordinary numbers cannot exactly represent every 64-bit integer.