Understanding Distributed Unique Identifiers

In distributed systems, generating globally unique identifiers is a common requirement. These IDs typically serve as unique markers for data records in search functionality and storage systems. Use cases include unique order numbers, coupon codes, and similar scenarios where duplication would constitute a critical failure. Imagine the chaos if two separate orders shared the same order number—this would be an absolute disaster for any business.

Generating unique IDs in a single-node environment is trivial. A single application running on one machine can leverage atomic increment operations through a singleton pattern. However, in distributed architectures spanning multiple applications, data centers, and machines, ensuring uniqueness across all nodes requires careful architectural decisions.

In essence, distributed unique IDs provide data with a definitive, conflict-free identifier.

Key Characteristics of Distributed Unique IDs

While uniqueness remains the core requirement, a robust global ID solution typically exhibits additional properties:

• Global Uniqueness: No duplicates—this is the fundamental requirement
• Roughly Sequential or Monotonically Increasing: Self-incrementing behavior benefits search operations, sorting, and range queries
• High Performance: ID generation must be fast with minimal latency
• High Availability: Since the ID generation service supports critical business operations, downtime would cripple dependent services, making redundancy essential
• Ease of Integration: API-friendly design that developers can adopt quickly
• Security Considerations: Sequential IDs can be predictable, potentially enabling adversarial activities—this requires careful evaluation based on business context

Common ID Generation Strategies

Direct UUID Generation

Developers familiar with Java have likely used the UUID class for generating random identifiers as unique request markers in logging systems:

String uniqueKey = UUID.randomUUID().toString();

UUID stands for "Universally Unique Identifier" (also known as GUID - Globally Unique Identifier). The underlying structure is a 128-bit binary integer typically displayed as 32 hexadecimal characters. The combinatorial space is astronomical—approximately 2^128 possibilities.

According to technical specifications, UUID composition includes:

• Time-dependent first portion—if generated several seconds apart, the first section differs
• Clock sequence component
• Globally unique IEEE machine identifier (MAC address if available, otherwise generated through alternative methods)

The sole theoretical vulnerability involves two identical virtual machines with matching boot times and random seeds generating UUIDs simultaneously—extremely improbable, making practical duplicates virtually impossible.

UUID advantages include excellent performance, no network dependencies since generation occurs locally, and guaranteed uniqueness across different machines. However, significant drawbacks exist: no ordering guarantee prevents efficient sorting, the 36-character string consumes substantial storage (particularly problematic for database indexes), and the identifier carries no business semantics—it is merely a string of numbers.

Some developers attempt improvements such as converting UUID to 64-bit integers:

ByteBuffer buffer = ByteBuffer.wrap(UUID.randomUUID().toByteArray());
return buffer.getLong();

Alternative approaches include the NHibernate Comb algorithm, which preserves the first 20 characters of a UUID while replacing the last 12 characters with timestamp data, creating approximate ordering.

Assessment: UUID excels as a log or context identifier but becomes problematic when used as order numbers due to length and lack of semantic meaning.

Database Auto-Increment Sequences

Single-Node Database Configuration

Database primary keys naturally support auto-increment behavior. By configuring ID as an auto-incrementing primary key, inserting a record automatically generates and returns the corresponding ID:

CREATE DATABASE IF NOT EXISTS test;
USE test;
CREATE TABLE id_registry (
    id BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT, 
    description VARCHAR(50) NOT NULL DEFAULT '',
    PRIMARY KEY (id)
) ENGINE=InnoDB;

Insert operations:

INSERT INTO id_registry(description) VALUES ('sample_record');

Advantages include simplicity, speed on a single node, inherent self-incrementing behavior with atomic guarantees, and numeric IDs that facilitate sorting, searching, and pagination. The critical weakness is obvious: a single-node setup becomes a single point of failure. Additionally, one machine cannot handle massive concurrent loads.

Database Clustering Approach

Clustering multiple database nodes solves high availability and concurrency concerns. However, multiple masters generating IDs independently would produce duplicates. The solution involves assigning distinct starting values and step sizes to each node.

For example, with three nodes A, B, and C:

-- Node A configuration
SET @@auto_increment_offset = 1;
SET @@auto_increment_increment = 3;

-- Node B configuration
SET @@auto_increment_offset = 2;
SET @@auto_increment_increment = 3;

-- Node C configuration
SET @@auto_increment_offset = 3;
SET @@auto_increment_increment = 3;

Resulting sequences:

A: 1, 4, 7, 10...
B: 2, 5, 8, 11...
C: 3, 6, 9, 12...

This architecture handles high concurrency when sufficient master nodes exist, and slave nodes can take over during master failures through replication, significantly reducing per-machine load.

Limitations remain:

• Replication lag may cause duplicate ID generation if a master fails and a slave takes over
• Pre-configured offset and increment values create scaling challenges—adding nodes often requires service interruption and reconfiguration

Segmented Database ID Allocation

Frequent database round-trips become problematic under high concurrency. A more efficient approach pre-allocates ID ranges into application memory, requesting new ranges only when exhausted. This preserves cluster advantages while dramatically reducing database load:

Node A: Range 1-1000, Range 3001-4000...
Node B: Range 1001-2000, Range 4001-5000...
Node C: Range 2001-3000, Range 5001-6000...

Even single-node deployments benefit from batch allocation. Here's a representative table design:

CREATE TABLE id_allocation (
    segment_id INT NOT NULL,
    current_max BIGINT(20) NOT NULL COMMENT 'Maximum ID in current segment',
    allocation_step INT(20) NOT NULL COMMENT 'Segment size',
    version INT(20) NOT NULL COMMENT 'Optimistic lock version',
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    modified_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
    PRIMARY KEY (segment_id)
);

Allocation logic uses an optimistic lock pattern—when a segment exhausts, only one concurrent request successfully acquires the next segment:

UPDATE id_allocation 
SET current_max = current_max + allocation_step, 
    version = version + 1 
WHERE version = #{currentVersion};

Key implementation aspects:

• Batch acquisition minimizes database round-trips
• Optimistic locking ensures data consistency
• Background scheduled tasks can automatically refresh segments when counts fall below thresholds

Redis Atomic Increment

Redis provides the atomic INCR command for self-incrementing operations. Redis operates in-memory, delivering exceptional throughput:

127.0.0.1:6379> SET counter 100
OK
127.0.0.1:6379> INCR counter
(integer) 101

Single-node concerns are addressed through clustering. Using INCRBY with initial values and step sizes across multiple machines handles high concurrency effectively.

Advantages include in-memory speed and natural ordering that benefits sorting and searching. Disadvantages involve step size constraints limiting horizontal scaling, plus added system complexity for persistence and availability management.

Persistence challenges require careful consideration. RDB periodic snapshots may lose data if a node crashes before persistence completes, risking duplicate IDs after restart. AOF every-command persistence impacts performance; configuring one-second persistence means potential one-second data loss and slower recovery. This represents a fundamental trade-off between performance and durability.

Zookeeper-Based ID Generation

Zookeeper can technically generate unique IDs via sequential znode versioning, producing 32 or 64-bit sequential numbers. How ever, this aproach sees minimal adoption due to performance constraints. High contention scenarios require distributed locking, making this solution inefficient for demanding workloads.

Meituan Leaf Framework

Leaf was developed with specific architectural goals:

1. Global uniqueness guaranteeing no duplicates, with overall increasing trends
2. High availability with distributed architecture—database outages are tolerated temporarily
3. High concurrency and low latency—achieving over 50,000 QPS with P99 under 1ms on CentOS 4C8G VMs
4. Simple integration via RPC or HTTP interfaces

Leaf implements two distinct versions:

Version 1: Pre-distributed ID Allocation

This approach follows the segmented allocation pattern described earlier, pre-fetching ID ranges for local use. A notable weakness involves update latency during segment refresh and unavailability during replication lag or failover.

Optimizations include:

• Double Buffer Strategy: Two segments enable asynchronous pre-refresh—when the active segment reaches 10% consumption, background processing begins fetching the next segment
• Dynamic Segment Sizing: Fixed segment sizes may not match varying traffic patterns; adaptive sizing adjusts allocation sizes based on observed demand

Version 2: Leaf-Snowflake Implementation

Leaf provides a Java implementation that minimizes dependency on Zookeeper for machine ID assignment. Even if Zookeeper encounters issues, the service continues operating. On initial startup, Leaf retrieves workerID from Zookeeper and caches it locally in the filesystem. This ensures continued operation during Zookeeper unavailability or machine restarts, achieving weak dependency on third-party components and improving overall service level agreements.

Snowflake Algorithm

Snowflake originated from Twitter's internal distributed systems, achieving widespread adoption after open-sourcing. It generates 64-bit Long identifiers structured as:

• 1 bit: Unused—highest bit in binary representation indicates negative numbers, but unique IDs must be positive, so this bit remains 0
• 41 bits: Timestamp in milliseconds—supports approximately 69 years ($2^{41}-1$ milliseconds converted to years)
• 10 bits: Worker machine identifier—represents either machine ID or datacenter ID plus machine ID combination
• 12 bits: Sequence number—allows up to 4096 concurrent ID generations per millisecond per machine

Each machine generates IDs following this structure, ensuring trend-wise ordering as timestamps advance. The design remains simple without requiring distributed coordination.

A critical consideration involves clock regression—if system time moves backward due to bugs, restarts, or NTP adjustments, ID generation faces challenges. Solutions include:

• Blocking until Valid Time: When detecting a smaller timestamp than the previous one, continuously poll until time advances appropriately
• Extended Bits for Regression: For significant clock regression, blocking becomes impractical. Alternative approaches either reject service requests exceeding a regression threshold or extend the ID structure to accommodate regression offsets by incrementing extended bits

A practical Java implementation:

public class DistributedIdGenerator {

    private final long machineIdentifier;
    private final long zoneIdentifier;
    private long currentSequence;
    private long lastGeneratedTimestamp = -1;

    private static final long START_EPOCH = 1609459200000L; // 2021-01-01
    private static final long ZONE_BITS = 5L;
    private static final long MACHINE_BITS = 5L;
    private static final long SEQUENCE_BITS = 12L;
    
    private static final long MAX_MACHINE_ID = ~(-1L << MACHINE_BITS);
    private static final long MAX_ZONE_ID = ~(-1L << ZONE_BITS);
    private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);
    
    private static final long MACHINE_SHIFT = SEQUENCE_BITS;
    private static final long ZONE_SHIFT = SEQUENCE_BITS + MACHINE_BITS;
    private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + MACHINE_BITS + ZONE_BITS;

    public DistributedIdGenerator(long machineId, long zoneId) {
        this(machineId, zoneId, 0);
    }

    public DistributedIdGenerator(long machineId, long zoneId, long initialSequence) {
        if (machineId > MAX_MACHINE_ID || machineId < 0) {
            throw new IllegalArgumentException("Machine ID exceeds valid range");
        }
        if (zoneId > MAX_ZONE_ID || zoneId < 0) {
            throw new IllegalArgumentException("Zone ID exceeds valid range");
        }
        
        this.machineIdentifier = machineId;
        this.zoneIdentifier = zoneId;
        this.currentSequence = initialSequence;
    }

    public synchronized long generate() {
        long currentTime = System.currentTimeMillis();

        if (currentTime < lastGeneratedTimestamp) {
            throw new IllegalStateException("Clock regression detected");
        }

        if (currentTime == lastGeneratedTimestamp) {
            currentSequence = (currentSequence + 1) & SEQUENCE_MASK;
            if (currentSequence == 0) {
                currentTime = waitForNextMillisecond(currentTime);
            }
        } else {
            currentSequence = 0;
        }

        lastGeneratedTimestamp = currentTime;

        return ((currentTime - START_EPOCH) << TIMESTAMP_SHIFT) |
               (zoneIdentifier << ZONE_SHIFT) |
               (machineIdentifier << MACHINE_SHIFT) |
               currentSequence;
    }

    private long waitForNextMillisecond(long baseTimestamp) {
        long timestamp;
        do {
            timestamp = System.currentTimeMillis();
        } while (timestamp <= baseTimestamp);
        return timestamp;
    }

    public static void main(String[] args) {
        DistributedIdGenerator generator = new DistributedIdGenerator(1, 1);
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            generator.generate();
        }
        System.out.println("Generation completed in: " + (System.currentTimeMillis() - start) + "ms");
    }
}

Baidu Uid-Generator

Baidu's uid-generator provides another Snowflake variant with customizable bit allocations for each ID component. The project documentation highlights several optimizations:

UidGenerator is a Java-based unique ID generator implementing the Snowflake algorithm. It functions as a component within application projects, supporting configurable workerId bit lengths and initialization strategies, making it suitable for containerized environments with automatic restarts and instance migrations. UidGenerator leverages future timestamps to overcome inherent sequence limitations, employs RingBuffer for caching generated UIDs to parallelize production and consumption, and utilizes cache line padding to avoid hardware-level "false sharing" issues. Published benchmarks report up to 6 million QPS on a single machine.

Summary

Regardless of the chosen ID generation mechanism, ensuring uniqueness remains the primary objective. Once this foundation is established, optimization for performance and availability becomes relevant. Solutions generally fall into two categories:

• Centralized Approaches: Depend on external systems like MySQL, Redis, or Zookeeper to coordinate ID generation

  • Advantages: Naturally ordered sequences
  • Disadvantages: Increased architectural complexity, typically requires clustering and pre-configured step sizes

• Decentralized Approaches: Generate IDs locally using algorithms like Snowflake or UUID

  • Advantages: Simplicity, no performance bottlenecks
  • Disadvantages: Longer identifier strings, weaker ordering guarantees

No solution represents a perfect choice for all scenarios. The appropriate strategy depends on business requirements and current system scale. Within technical architecture, there rarely exists an absolute optimal solution—only solutions better suited to specific contexts.