Mastering the Snowflake Algorithm: Generate Distributed Unique IDs in Java

Snowflake Algorithm Overview

The Snowflake algorithm is a widely used method for generating unique identifiers in distributed systems, designed to ensure that IDs produced by different nodes at different times never collide.

Inspired by the structure of a snowflake, each generated ID is unique and monotonically increasing.

Key Characteristics

Uniqueness : IDs are unique across time and nodes, allowing traceability to the generating node and timestamp.

Orderliness : IDs increase over time, facilitating easy sorting and range queries.

Distribution : Multiple nodes can generate IDs concurrently without conflicts.

High Performance : The algorithm relies on bitwise operations and simple logic, enabling fast ID generation.

Algorithm Structure

The 64‑bit ID consists of four parts: a sign bit, a 41‑bit timestamp, a 10‑bit node identifier, and a 12‑bit sequence number.

1. Sign Bit (1 bit)

Always set to 0, indicating a positive integer ID.

2. Timestamp (41 bits)

Stores the millisecond difference between the current time and a custom epoch. This range supports about 69 years of timestamps, ensuring IDs are time‑ordered.

3. Node ID (10 bits)

Identifies the machine or process generating the ID. With 10 bits, up to 1024 distinct nodes can be distinguished, providing the algorithm’s distributed nature.

4. Sequence Number (12 bits)

Allows up to 4096 IDs to be generated per node within the same millisecond. When the limit is reached, the generator waits for the next millisecond.

Java Implementation

The following Java class demonstrates a simple Snowflake ID generator. It defines the epoch, bit allocations, maximum values, and shift amounts, and provides methods to generate IDs, obtain the current timestamp, and wait for the next millisecond when necessary.

public class Snowflake {
    // Custom epoch (e.g., project start time)
    private final long twepoch = 1288834974657L;
    // Bit lengths for each component
    private final long timestampBits = 41L;
    private final long workerIdBits = 10L;
    private final long sequenceBits = 12L;
    // Maximum values
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private final long maxSequence = -1L ^ (-1L << sequenceBits);
    // Shift amounts
    private final long workerIdShift = sequenceBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits;
    // Node identifier (0‑1023)
    private long workerId;
    // Sequence within the same millisecond
    private long sequence = 0L;
    // Last timestamp used
    private long lastTimestamp = -1L;

    public Snowflake(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("Worker ID can't be greater than " + maxWorkerId + " or less than 0");
        }
        this.workerId = workerId;
    }

    public synchronized long generateId() {
        long timestamp = timeGen();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate ID for " + (lastTimestamp - timestamp) + " milliseconds");
        }
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & maxSequence;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        return ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    public static void main(String[] args) {
        Snowflake snowflake = new Snowflake(0);
        for (int i = 0; i < 10; i++) {
            long id = snowflake.generateId();
            System.out.println("Generated ID: " + id);
        }
    }
}

Conclusion

The Snowflake algorithm offers a practical, high‑throughput solution for generating unique IDs in distributed environments. When deploying it, ensure proper node ID allocation and clock synchronization across machines to maintain the expected uniqueness and ordering guarantees.