Distributed ID Generation: UUID vs auto-increment vs Snowflake, sortability tradeoffs

Every record needs a unique ID. In a single database, auto-increment is simple. In a distributed system with multiple writers, you have tradeoffs.

Auto-Increment

Database 1: increment counter, return ID
  INSERT user (id=1, name="Alice") ...

Database 2: increment counter, return ID
  INSERT user (id=2, name="Bob") ...

Simple, sortable by time, dense (no gaps).

Pros:

• Sortable: id=1 is first, id=2 is second.
• Dense: no gaps, easy to count.
• Small: single 64-bit integer.

Cons:

• Single point of failure: one database increments counter. If it's down, can't generate IDs.
• Hot shard: counter is a bottleneck (contention, all writes to one node).
• Coordination required: distributed auto-increment is complex (consensus, two-phase commit).

Use: Single database, or read replicas (writes on one leader, ID generated on leader).

---

UUID (Universally Unique Identifier)

UUID v4: random 128-bit number
  "550e8400-e29b-41d4-a716-446655440000"

No coordination needed. Any node can generate.

Pros:

• Decentralized: any node generates independently, no coordination.
• Collision-free: probabilistically (2^122 possible values, collision only in extreme cases).
• No single point of failure.

Cons:

• Large: 128 bits (16 bytes) vs 64 bits for auto-increment.
• Non-sortable: "550e..." is not ordered by time.
• Database inefficiency: non-monotonic inserts cause index fragmentation (B-tree thrashing).

Use: Small-scale, non-time-ordered data, or when you don't care about insertion order.

UUID v1 (Time-based)

UUID = timestamp + mac_address + random

Sortable by time. But: privacy (mac_address exposed).

UUID v7 (Unix Timestamp + Random)

UUID = unix_timestamp_ms (48 bits) + random (80 bits)

Sortable by time, no privacy leak. Modern choice.

---

Snowflake (Twitter's ID Generation)

64-bit ID structure:

[timestamp (41 bits)][worker_id (10 bits)][sequence (12 bits)]

timestamp: milliseconds since epoch (~69 years)
worker_id: 0-1023 (1024 workers)
sequence: counter within same ms (0-4095 per ms)

Example:
  timestamp: "1234567890123"
  worker_id: "42"
  sequence: "7"
  → ID: 0 | 1234567890123 | 42 | 7 (64 bits, unique & sortable)

Pros:

• Sortable: IDs are ordered by timestamp, then worker, then sequence.
• Decentralized: each worker generates independently (no coordination).
• Dense: small 64-bit integers, like auto-increment.
• Fast: worker generates locally, no I/O.

Cons:

• Clock skew risk: if worker's clock jumps backward, duplicate IDs possible (need safeguards).
• Worker ID assignment: need to coordinate which worker is which (or use IP, MAC).
• Requires NTP or clock sync.

Use: High-throughput distributed systems (Twitter, Discord, Uber).

---

Tradeoffs Summary

| Method | Sortable | Size | Decentralized | Collision Risk | Use Case | |--------|----------|------|---------------|---|---| | Auto-increment | Yes | 8 bytes | No (single source) | None | Single DB or leader writes | | UUID v4 | No | 16 bytes | Yes | Negligible | Low-scale, no time order | | UUID v7 | Yes | 16 bytes | Yes | Negligible | Moderate scale, need sort | | Snowflake | Yes | 8 bytes | Yes | Low (clock skew) | High-scale, distributed |

---

Clock Skew Handling in Snowflake

Problem: Worker's clock jumps back 1 second, duplicates IDs.

Solutions:

1. Ignore skew: Accept risk. Very rare if NTP is running.
2. Wait: If clock goes backward, sleep until real time catches up (pause ID generation).
3. Error out: Fail the request if clock skews (retry logic handles it).
4. Monotonic increment: Track last ID; if new timestamp < last, increment sequence without changing timestamp.

long lastId = 0;
long generate() {
  long timestamp = getCurrentTimeMs();
  if (timestamp < lastId >> 12) { // clock went back
    timestamp = lastId >> 12; // use old timestamp
    sequence = (lastId & 0xFFF) + 1; // increment sequence
  }
  lastId = (timestamp << 12) | sequence;
  return lastId;
}

---

In the interview

1. Auto-increment for single DB: "Auto-increment is simple and sortable, but it's a bottleneck in distributed systems. Works fine with one leader."

2. UUID for simplicity: "No coordination, but not sortable and wastes space. Good for small systems."

3. Snowflake for scale: "Small IDs, sortable, decentralized. Workers generate independently. Risk is clock skew, but NTP mitigates it."

4. Discuss tradeoffs: "If I need sorting, Snowflake beats UUID v4. If clock sync isn't reliable, UUID v7. If single database, auto-increment is simplest."

5. Database efficiency: "Sortable IDs are important; non-monotonic inserts (UUID v4) cause B-tree fragmentation and slow queries."