Requirements

Functional Requirements

• Generate unique 64-bit integer IDs
• IDs must be globally unique across all nodes
• IDs should be roughly time-ordered (sortable by creation time)
• IDs should be compact (fit in 64 bits)
• Support 10K+ ID generation requests per second per node

Non-Functional Requirements

• Latency: Generate ID in < 1ms
• Availability: ID generation must never be a single point of failure
• Scalability: Support 1000+ nodes generating IDs concurrently
• Durability: Generated IDs must never be lost or reused

Back-of-the-Envelope Estimation

ID Generation Strategies

Snowflake ID Structure

UUID Structure

Database Auto-Increment with Range Allocation

Twitter Snowflake Implementation

class SnowflakeGenerator:
    EPOCH = 1288834974657  # Custom epoch (Nov 4, 2010)
    
    TIMESTAMP_BITS = 41
    MACHINE_BITS = 10
    SEQUENCE_BITS = 12
    
    MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1  # 4095
    MAX_MACHINE = (1 << MACHINE_BITS) - 1    # 1023
    
    def __init__(self, machine_id):
        self.machine_id = machine_id & self.MAX_MACHINE
        self.sequence = 0
        self.last_timestamp = -1
    
    def next_id(self):
        timestamp = self._current_millis()
        
        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & self.MAX_SEQUENCE
            if self.sequence == 0:
                timestamp = self._wait_next_millis()
        else:
            self.sequence = 0
        
        self.last_timestamp = timestamp
        
        return ((timestamp - self.EPOCH) << (self.MACHINE_BITS + self.SEQUENCE_BITS)) | \
               (self.machine_id << self.SEQUENCE_BITS) | \
               self.sequence

Practice Exercises

1. Design: How would you handle clock synchronization issues in a Snowflake ID generator? What happens if a machine's clock goes backward?

2. Scale: If you need to generate 10 million IDs per second, how many machines are needed with Snowflake (12-bit sequence)? What if you use 8-bit sequence instead?

3. Trade-offs: Compare Snowflake IDs and UUID v4 for a URL shortener. What are the trade-offs in terms of ID length, ordering, and uniqueness guarantees?

4. Edge Case: How would you ensure uniqueness if a Snowflake node crashes and restarts with the same machine ID? Design a recovery mechanism.

What to Learn Next