UUIDs & Unique ID Generation

Metadata

1. Overview

What problem does it solve?

In a single database, generating a unique ID is easy: just use AUTO_INCREMENT (1, 2, 3, 4...).

But in a distributed system with hundreds of databases and thousands of application servers generating millions of records per second, you cannot rely on a single central database to hand out IDs (it would become a massive bottleneck and a single point of failure).

Distributed Unique ID Generation allows thousands of servers to independently generate IDs concurrently with zero coordination, guaranteeing that no two servers ever generate the same ID.

What breaks without it?

• Database collisions: Two users get assigned user_id = 1042. One overwrites the other.
• Performance bottlenecks: All traffic funnels through a single "ID generator" server.
• Security vulnerabilities: Sequential IDs (order_id = 500) allow attackers to guess URLs (/orders/501) and scrape your data (Insecure Direct Object Reference).

2. Motivation

Why was UUID invented?

In the 1990s, the Open Software Foundation needed a way to identify components in a distributed computing environment without requiring central registration. They invented the Universally Unique Identifier (UUID) — a 128-bit number that relies on sheer mathematical probability to avoid collisions.

Why was Twitter Snowflake invented?

UUIDs are great, but they are completely random strings. In 2010, Twitter faced a massive scaling problem with MySQL. They needed to partition their databases, which meant they could no longer use auto-incrementing IDs for Tweets.

They couldn't use standard UUIDs because databases (specifically B-Tree indexes like InnoDB) perform terribly when inserting completely random strings — they prefer sequentially ordered numbers.

Twitter invented Snowflake to generate IDs that are:

1. Generated entirely by distributed worker nodes (no central DB).
2. Guaranteed unique.
3. Time-ordered (roughly sortable by time).
4. Fit in a 64-bit integer (efficient for databases and indexing).

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Twitter Snowflake Format (64-bit)

A Snowflake ID is a 64-bit integer (can fit in a standard BIGINT in SQL). It's composed of 4 sections using bitwise shifts.

 1 bit  │       41 bits               │    10 bits      │     12 bits 
 ───────┼─────────────────────────────┼─────────────────┼───────────────
   0    │ Timestamp (ms since epoch)  │  Machine/Node ID│ Sequence Num  
        │                             │                 │               
Sign bit│ ~69 years of timestamps     │ 1024 unique     │ 4096 IDs per  
(unused)│                             │ servers         │ ms per server 

How it guarantees uniqueness:

• Two servers generating an ID at the exact same millisecond won't collide because they have different Machine IDs.
• A single server generating 1,000 IDs in the exact same millisecond won't collide because of the Sequence Number.

6. Internal Working

6.1 Standard UUIDs (128-bit)

A standard UUID looks like this: 123e4567-e89b-12d3-a456-426614174000 (32 hex characters = 128 bits).

• UUIDv1 (Time-based): Combines MAC address + Timestamp. (Leaks your MAC address!).
• UUIDv4 (Random): 122 bits of pure randomness. The probability of collision is so astronomically small it is considered zero. (Best for API keys, secure tokens).
• UUIDv7 (Time-ordered): A modern standard (RFC 9562) that combines a 48-bit timestamp with 74 random bits. Solves the database insertion problem of UUIDv4 while remaining 128-bit.

6.2 Auto-Incrementing with Offsets (Flickr approach)

Before Snowflake, Flickr solved distributed IDs using two centralized Ticket Servers.

• Ticket Server A generates: 1, 3, 5, 7, 9 (Offset 1, Step 2)
• Ticket Server B generates: 2, 4, 6, 8, 10 (Offset 2, Step 2)

Problem: Hard to scale if you suddenly need 100 ticket servers.

6.3 Why Random UUIDv4 is bad for Database Indexes

In an RDBMS (like MySQL/Postgres), the Primary Key is stored in a B-Tree structure (Block 013).

• If IDs are sequential (1, 2, 3), the database just appends to the right-most page of the tree. Extremely fast.
• If IDs are random (UUIDv4), the database has to insert the new record into the middle of the tree. This causes massive page splitting, disk fragmentation, and random disk I/O, destroying write performance at scale.

7. Implementation

Why Go? Go is heavily used for high-performance infrastructure services. Snowflake relies entirely on bitwise operations, concurrency locks, and millisecond timestamps, which Go handles natively and efficiently.

/*
006 - Twitter Snowflake Implementation
A highly concurrent, lock-safe 64-bit unique ID generator.
Run: `go run snowflake.go`
*/
package main

import (
	"fmt"
	"sync"
	"time"
)

// ── Configuration Constants ──

const (
	// Epoch set to Jan 1, 2024 (Custom epoch to maximize the 69-year limit)
	Epoch int64 = 1704067200000

	// Bit allocations
	NodeBits     uint8 = 10 // Supports 1024 nodes
	SequenceBits uint8 = 12 // Supports 4096 IDs per ms per node

	// Bit shifts
	NodeShift      uint8 = SequenceBits             // 12
	TimestampShift uint8 = SequenceBits + NodeBits  // 12 + 10 = 22

	// Masks to extract values and prevent overflow
	MaxNode     int64 = -1 ^ (-1 << NodeBits)     // 1023
	MaxSequence int64 = -1 ^ (-1 << SequenceBits) // 4095
)

// ── The Snowflake Generator ──

type Snowflake struct {
	mu            sync.Mutex
	lastTimestamp int64
	nodeID        int64
	sequence      int64
}

func NewSnowflake(nodeID int64) (*Snowflake, error) {
	if nodeID < 0 || nodeID > MaxNode {
		return nil, fmt.Errorf("Node ID must be between 0 and %d", MaxNode)
	}
	return &Snowflake{
		lastTimestamp: -1,
		nodeID:        nodeID,
		sequence:      0,
	}, nil
}

func (s *Snowflake) Generate() (int64, error) {
	s.mu.Lock()
	defer s.mu.Unlock()

	currentTimestamp := time.Now().UnixMilli()

	if currentTimestamp < s.lastTimestamp {
		return 0, fmt.Errorf("clock moved backwards. Refusing to generate ID")
	}

	if currentTimestamp == s.lastTimestamp {
		// Same millisecond: increment sequence
		s.sequence = (s.sequence + 1) & MaxSequence
		
		// If sequence overflows (exceeds 4095), wait for next millisecond
		if s.sequence == 0 {
			for currentTimestamp <= s.lastTimestamp {
				currentTimestamp = time.Now().UnixMilli()
			}
		}
	} else {
		// New millisecond: reset sequence
		s.sequence = 0
	}

	s.lastTimestamp = currentTimestamp

	// Calculate offset from our custom epoch
	timeOffset := currentTimestamp - Epoch

	// Bitwise OR the components together
	id := (timeOffset << TimestampShift) | (s.nodeID << NodeShift) | s.sequence

	return id, nil
}

// ── Helper to decode an ID back into components ──

func Decode(id int64) {
	timeOffset := id >> TimestampShift
	timestamp := timeOffset + Epoch
	node := (id >> NodeShift) & MaxNode
	seq := id & MaxSequence

	t := time.UnixMilli(timestamp)
	fmt.Printf("ID: %d\n", id)
	fmt.Printf(" ├─ Time: %s (Offset: %d)\n", t.Format(time.RFC3339), timeOffset)
	fmt.Printf(" ├─ Node: %d\n", node)
	fmt.Printf(" └─ Seq:  %d\n\n", seq)
}

func main() {
	// Initialize a generator for Node 42
	sf, err := NewSnowflake(42)
	if err != nil {
		panic(err)
	}

	fmt.Println("Generating 5 consecutive IDs:")
	for i := 0; i < 5; i++ {
		id, _ := sf.Generate()
		fmt.Printf("Generated: %d\n", id)
	}

	fmt.Println("\nDecoding the last generated ID:")
	lastID, _ := sf.Generate()
	Decode(lastID)
}

Sample Output

$ go run snowflake.go
Generating 5 consecutive IDs:
Generated: 60293145020792832
Generated: 60293145020792833
Generated: 60293145020792834
Generated: 60293145020792835
Generated: 60293145020792836

Decoding the last generated ID:
ID: 60293145020792837
 ├─ Time: 2024-06-15T14:30:02Z (Offset: 14375005)
 ├─ Node: 42
 └─ Seq:  5

Notice how the consecutive IDs increment by exactly 1 at the end, making them perfect for database indexing.

8. Complexity

9. Trade-offs

When to use what?

• Public API tokens / Session IDs: UUIDv4. (You don't want anyone guessing them).
• Database Primary Keys (Massive Scale): Snowflake or UUIDv7. (You need fast inserts and distributed generation).
• TinyURL short links: Base62 encoded Auto-incrementing counters (managed via Redis/ZooKeeper).

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Why did Twitter create Snowflake instead of using UUIDs for Tweets? Hint: UUIDs are 128-bit strings that are completely random. Random inserts destroy B-Tree index performance in MySQL.

2. In a Snowflake generator, what happens if the system clock goes backwards due to NTP synchronization? Hint: If not handled, it will generate duplicate IDs. The system must halt generation until the clock catches up.

3. How do you ensure that two different application servers don't accidentally use the same Node ID? Hint: Node IDs shouldn't be hardcoded. Use ZooKeeper or Redis to reserve a Node ID when the server boots up.

4. If a Snowflake ID is 64 bits, how does Javascript handle it on the frontend? Hint: It doesn't! JS numbers are 64-bit floats, which lose precision on large integers (max safe integer is 53 bits). You MUST cast Snowflake IDs to strings in your JSON API ({"id": "60293145020792832"}).

13. Used By (Downstream Blocks)

• 017 Data Partitioning — IDs are often the partition key. Snowflake's time-ordered nature helps group recent data together.
• 023 Message Queues — Every message needs a unique tracing ID.
• 031 Distributed Locking — Requires unique identifiers for lock owners.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Handle Clock Drift

Modify the Generate() function. Instead of returning an error if the clock moves backward by less than 5 milliseconds, use time.Sleep() to wait for the clock to catch up, then proceed.

Exercise 2: Base62 Encoder (TinyURL prep)

Write a helper function that takes a generated 64-bit Snowflake ID and converts it into a Base62 string (using characters 0-9, a-z, A-Z). This is exactly how URL shorteners compress IDs for display!

Website Metadata