Chapter 27: Distributed ID Generation

Why Distributed IDs

Auto-increment primary keys fail in distributed systems. When data is sharded across multiple databases, each shard generates its own sequence, causing ID collisions. Distributed ID generation solves this by creating globally unique identifiers without coordination.

Requirements

Why Auto-Increment Fails

Both shards generate ID=1, causing collisions when aggregating data.

UUID (Universally Unique Identifier)

128-bit identifiers standardized in RFC 4122. Multiple versions with different generation strategies.

UUID Versions

Example UUIDs

v1: 6ba7b810-9dad-11d1-80b4-00c04fd430c8
v4: 550e8400-e29b-41d4-a716-446655440000
v7: 017f22e2-79b0-7cc3-98c4-dc0c0c07398f

When to Use

• v4: Client-side ID generation (offline-first apps), no ordering needed
• v7: Database primary keys where time-ordering improves insert performance

Twitter Snowflake

64-bit ID scheme designed by Twitter for high-volume distributed ID generation. Generates roughly time-sorted IDs without coordination.

Structure

Properties

• Capacity: 4096 IDs per millisecond per machine = 4.096M IDs/sec/machine
• Scalability: 1024 machines (32 DC × 32 machines) = 4.2B IDs/sec globally
• Ordering: Roughly time-sorted (same timestamp = same prefix)
• Lifetime: 41-bit timestamp lasts 69 years from custom epoch

Generation Algorithm

class SnowflakeIDGenerator {
    private long epoch = 1288834974657L;  // Custom epoch
    private long datacenterIdBits = 5L;
    private long machineIdBits = 5L;
    private long sequenceBits = 12L;

    private long datacenterId;
    private long machineId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public synchronized long nextId() {
        long timestamp = currentTimeMillis();

        // Clock moved backward - reject
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards");
        }

        // Same millisecond - increment sequence
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & 4095; // Mask to 12 bits
            if (sequence == 0) {
                // Sequence overflow - wait for next ms
                timestamp = waitNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L; // New millisecond - reset
        }

        lastTimestamp = timestamp;

        return ((timestamp - epoch) << 22)
             | (datacenterId << 17)
             | (machineId << 12)
             | sequence;
    }
}

Clock Skew Handling

If system clock moves backward (NTP correction), Snowflake rejects ID generation to prevent duplicate IDs. Alternative: wait until clock catches up, but adds latency.

ULID (Universally Unique Lexicographically Sortable Identifier)

128-bit identifier designed for time-sorting and readability. Encoded in Crockford Base32 (no ambiguous characters like 0/O, 1/I/l).

Structure

Example

01ARZ3NDEKTSV4RRFFQ69G5FAV
|----------|-----------|
 Timestamp   Randomness
 (10 chars)  (16 chars)

ULID vs UUID v7

When to Use

• APIs where IDs are exposed as strings (URLs, JSON)
• Need case-insensitive, unambiguous encoding
• Time-sortable without binary parsing

Database Sequences

Traditional approach: database auto-increment. Works for single databases, fails in distributed systems. Solutions add complexity.

Single Database Auto-Increment

CREATE TABLE users (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(255)
);

Problem: Single point of failure, coordination bottleneck, doesn't scale horizontally.

Flickr's Ticket Server

Two MySQL databases configured with different auto-increment offsets generate non-overlapping IDs.

Configuration

-- DB 1
SET @@auto_increment_offset = 1;
SET @@auto_increment_increment = 2;

-- DB 2
SET @@auto_increment_offset = 2;
SET @@auto_increment_increment = 2;

Pros and Cons

Pre-allocating ID Ranges

Optimization: allocate ranges (e.g., 1000 IDs at a time) to each app server, generate locally.

-- Server 1 claims 1-1000
-- Server 2 claims 1001-2000
-- Server 3 claims 2001-3000

Trade-off: Gaps in sequences if server crashes before using all IDs.

MongoDB ObjectID

12-byte (96-bit) identifier used as MongoDB's default _id. Combines timestamp, machine identifier, process ID, and counter.

Structure

Example

507f1f77bcf86cd799439011
|-------|-----|---|------|
Timestamp Machine PID Counter
(8 hex)  (6 hex) (4)  (6 hex)

Properties

• Time-sorted: Leading timestamp ensures rough ordering
• Compact: 12 bytes vs 16 for UUID
• Coordination-free: Machine+Process+Counter ensures uniqueness
• Limitation: 1-second granularity (vs millisecond for Snowflake/ULID)

Instagram's Approach

Instagram generates 64-bit IDs using PostgreSQL schemas per shard. Embeds shard ID in the identifier for routing.

Structure

PostgreSQL Schema

CREATE SCHEMA insta5; -- Shard 5

CREATE SEQUENCE insta5.table_seq;

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1314220021721;
    seq_id bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_seq') % 1024 INTO seq_id;
    result := (EXTRACT(EPOCH FROM clock_timestamp()) * 1000 - our_epoch) << 23;
    result := result | (shard_id << 10);
    result := result | (seq_id);
END;
$$ LANGUAGE PLPGSQL;

Advantages

• Shard-embedded: Extract shard ID from ID itself for routing
• PostgreSQL-native: Leverages existing infrastructure
• Time-sorted: Leading timestamp for chronological ordering

Routing Example

def get_shard_id(id):
    return (id >> 10) & 8191  # Extract 13-bit shard ID

photo_id = 1234567890123456
shard = get_shard_id(photo_id)  # 5
# Query shard 5 directly

Clock Skew

Time-based ID generation relies on synchronized clocks. Clock drift or NTP corrections cause issues.

Problems

Snowflake's Approach

if (timestamp < lastTimestamp) {
    // Clock moved backward - reject
    throw new RuntimeException(
        "Clock moved backwards. Refusing to generate ID"
    );
}

Trade-off: Availability hit (service errors until clock catches up) to prevent duplicate IDs.

Alternative: Wait for Clock

if (timestamp < lastTimestamp) {
    // Spin until clock catches up
    while (currentTimeMillis() <= lastTimestamp) {
        Thread.sleep(1);
    }
    timestamp = currentTimeMillis();
}

Trade-off: Adds latency (blocks ID generation).

Google Spanner's TrueTime

Uses GPS and atomic clocks to bound clock uncertainty. API returns time interval [earliest, latest].

TT.now() = [t_earliest, t_latest]
uncertainty = t_latest - t_earliest  // Typically < 10ms

Spanner waits out uncertainty before committing transactions to ensure external consistency.

Practical Mitigations

• NTP: Keep clocks synchronized (ntpd, chrony). Monitor drift.
• Monotonic clocks: Use system monotonic clock (doesn't go backward) for intervals, wall clock for timestamps
• Hybrid clocks: Combine physical and logical clocks (Hybrid Logical Clocks in CockroachDB)

Comparison Matrix

Performance Comparison

Choosing the Right Strategy

Decision Framework

Anti-Patterns

• UUID v4 for high-write DB PKs: Random IDs fragment B-tree indexes, killing insert performance
• Single DB sequence for distributed system: Coordination bottleneck, single point of failure
• Snowflake without clock monitoring: Clock skew causes ID generation failures or duplicates
• Exposing internal auto-increment IDs: Leaks info (creation order, total count), enumeration attacks

Migration Strategy

Migrating from auto-increment to distributed IDs:

1. Change ID column type (INT → BIGINT for Snowflake, CHAR(26) for ULID)
2. Dual-write: generate both old and new IDs during transition
3. Update foreign keys to reference new IDs
4. Backfill old records with new IDs (or keep old IDs as legacy)
5. Switch reads to new IDs
6. Drop old ID column