1. Introduction

• Snowflake is an open-source distributed ID generation algorithm from Twitter.
• Core idea: Use a 64-bit long integer as a globally unique ID.

2. Structure

0 - 0001000000 0000010000 0001000100 0000100000 0 - 10001 - 11001 - 000000000000

2.1 Part 1: 1 bit

• 1 bit, unused.
• Reason: If the first bit were 1, the number would be negative. Since all generated IDs are positive, the first bit is always 0.

2.2 Part 2: 41 bits

• 41 bits representing a timestamp.
• Unit: milliseconds.
• Can be used for 69 years.
• Reason: 2^41 - 1 milliseconds ≈ 69 years.

2.3 Part 3: 10 bits

• Records the machine ID. Allows deployment on up to 2^10 = 1024 machines.
• Within these 10 bits, 5 bits represent the data center ID, and 5 bits represent the machine ID. This allows up to 2^5 = 32 data centers, each with up to 2^5 = 32 machines. Adjust according to your company's actual situation.

2.3.1 Subpart 1: 5 bits (data center ID)

• 5 bits for data center ID, e.g., 10001.

2.3.2 Subpart 2: 5 bits (machine ID)

• 5 bits for machine ID, e.g., 11001.

2.4 Part 4: 12 bits

• 12 bits for sequence number.
• Represents the serial number of IDs generated in the same millisecond on the same machine.
• Maximum value: 2^12 = 4096, i.e., 0 to 4095.

3. Summary

3.1 Process of Generating a Unique ID

Suppose a service needs a globally unique ID. It sends a request to the system running the Snowflake algorithm, which generates the ID.

This system knows its own data center and machine IDs, e.g., data center ID = 17, machine ID = 25.

Upon receiving the request, the Snowflake system uses bitwise operations to generate a 64-bit long ID:

1. 1 bit: Set to 0.
2. 41 bits: Use the current timestamp (in milliseconds) to generate 41 bits.
3. 5 bits: Data center ID = 17, generate 5 bits.
4. 5 bits: Machine ID = 25, generate 5 bits.
5. 12 bits: Determine the sequence number for this request within the current millisecond, then increment the counter.

The result is a 64-bit ID that is guaranteed to be unique for a given machine within a given millisecond. If multiple IDs are generated in the same millisecond, the last 12 bits differentiate them.

3.2 Conclusion

By setting different flags in different parts of a 64-bit number, each ID is distinguished.

4. Code Example

package com.example.snowflake.demo1;

public class SnowFlake {

    // Start timestamp: 2016-11-26 21:21:05
    private final static long START_STAMP = 1480166465631L;

    // Number of bits for each part
    private final static long SEQUENCE_BIT = 12; // Sequence number bits
    private final static long MACHINE_BIT = 5;   // Machine ID bits
    private final static long DATA_CENTER_BIT = 5; // Data center ID bits

    // Maximum values for each part
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT); // 31
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); // 31
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); // 4095

    // Left shifts for each part
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

    private long dataCenterId;
    private long machineId;
    private long sequence = 0L;
    private long lastStamp = -1L;

    public SnowFlake(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("Data center ID exceeds maximum or is negative");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("Machine ID exceeds maximum or is negative");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }

    public synchronized long nextId() {
        long currStamp = getNewStamp();
        if (currStamp < lastStamp) {
            throw new RuntimeException("Clock moved backwards, refusing to generate ID");
        }

        if (currStamp == lastStamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0L) {
                currStamp = getNextMill();
            }
        } else {
            sequence = 0L;
        }

        lastStamp = currStamp;

        System.out.println("Timestamp: " + (currStamp - START_STAMP));
        System.out.println("Timestamp left shift: " + TIMESTAMP_LEFT);
        System.out.println("Data center ID: " + dataCenterId);
        System.out.println("Data center ID left shift: " + DATA_CENTER_LEFT);
        System.out.println("Machine ID: " + machineId);
        System.out.println("Machine ID left shift: " + MACHINE_LEFT);
        System.out.println("Sequence: " + sequence);

        long id = (currStamp - START_STAMP) << TIMESTAMP_LEFT
                | dataCenterId << DATA_CENTER_LEFT
                | machineId << MACHINE_LEFT
                | sequence;

        System.out.println("ID binary: " + Long.toBinaryString(id));
        return id;
    }

    private long getNextMill() {
        long mill = getNewStamp();
        while (mill <= lastStamp) {
            mill = getNewStamp();
        }
        return mill;
    }

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

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(3L, 10L);
        System.out.println("Next ID: " + snowFlake.nextId());
    }
}

5. Logic of sequence = (sequence + 1) & MAX_SEQUENCE

5.1 Auto-increment within the same millisecond

• Formula: 1&1=1, 1&0=0, 0&1=0, 0&0=0
• MAX_SEQUENCE is 2^12 - 1 = 4095, binary 1111 1111 1111.
• The operation x & MAX_SEQUENCE preserves the lower 12 bits of x.

5.2 Ensuring sequence stays within range

• Bits beyond the 12th from the right are zeroed out, so the value never exceeds MAX_SEQUENCE.

Test Tool

• Binary Calculator

6. Principal of (currStamp - START_STAMP) << TIMESTAMP_LEFT | dataCenterId << DATA_CENTER_LEFT | machineId << MACHINE_LEFT | sequence

6.1 Why shift currStamp - START_STAMP by 22 bits?

TIMESTAMP_LEFT = 22

6.2 Example

• t = currStamp - START_STAMP, max 2^41 - 1.
• Suppose t = 1000 (binary 41 bits: 0 0000 0000 0000 0000 0000 0000 0000 0011 1110 1000)
• dataCenterId = 3 (binary 5 bits: 0 0011)
• machineId = 10 (binary 5 bits: 0 1010)
• sequence = 0 (binary 12 bits: 0000 0000 0000)

Combined binary:

0000000000000000000000000000000011111010000001101010000000000000

Debug output:

Timestamp: 1000
Timestamp left shift: 22
Data center ID: 3
Data center ID left shift: 17
Machine ID: 10
Machine ID left shift: 12
Sequence: 0
ID binary: 11111010000001101010000000000000
Next ID: 4194738176

7. Pros and Cons

7.1 Advantages

• IDs are sorted by time, no collisions across distributed systems (due to data center + machine ID).
  • Milliseconds are in high bits, sequence in low bits, so IDs are roughly increasing.
• High throughput: theoretically ≈ 409.6w QPS (1000 * 2^12).
• High availability: generation does not depend on a database; it's done entirely in memory.
• Flexible: bit allocation can be adjusted based on business needs.

7.2 Disadvantages

• Strong dependency on machine clock; if the clock rolls back, duplicate IDs may be generated or service may become unavailable.
• Meituan has made improvements: Leaf

8. Distributed Deployment

8.1 Scenario 1

Application A is deployed in containers with 10 pods. A scheduled task inserts 1000 records per second into table T1. All 10 pods running simultaneously may cause primary key conflicts.

Solution: Use the 10-bit part (Part 3) to differentiate pods by asssigning different machine IDs.

The machine ID can be derived by converting the pod IP to a number and taking modulo 32 (since 2^5 = 32 possible machine IDs).