How to write code to implement snowflake algorithm in Java

1. Introduction

SnowFlow algorithm is a distributed ID generation algorithm launched by Twitter. The main core idea is to use 64-bit long type numbers as global IDs. It is often used in distributed systems, and the concept of timestamp is added to the ID, which basically keeps it non-repeating and continues to increase in an upward manner.

In these 64 bits, the first bit is not used, and then 41 bits are used as milliseconds, 10 bits are used as the working machine ID, and 12 bits are used as the serial number. The details are as shown in the figure below Represents:

The first part: 0, this is a sign bit, because if the first bit in binary is 1, then it is a negative number, but we generate These ids are all positive numbers, so the first bit is basically 0

The second part: 41 bits, represents a timestamp, 41 bits can represent up to $2^{41 } $-1, can also represent 2^{41}-1 millisecond value, which is basically almost 69 years.

The third part: 5 bits represent the computer room ID.

The fourth part: 5 bits represent the machine ID.

The fifth part: 12 bits represent the computer room id, and the serial number represented is the serial number of the id generated simultaneously on a certain machine in a certain computer room within this millisecond, 0000 00000000, if it is the same millisecond , then the snowflake value will be incremented

Simply put, if one of your services wants to generate a globally unique id, then you can send a request to a system that deploys the SnowFlake algorithm. This SnowFlake algorithm system to generate a unique id.

This algorithm can guarantee that a unique ID is generated on a machine in a computer room within the same millisecond. Multiple IDs may be generated within one millisecond, but they are distinguished by the last 12 bits of the sequence number.

Let’s take a brief look at the code implementation part of this algorithm.

In short, it is to use each bit position in a 64-bit number to set different flags

2. Code implementation

package com.lhh.utils;

/**
 * @author liuhuanhuan
 * @version 1.0
 * @date 2022/2/21 22:33
 * @describe Twitter推出的分布式唯一id算法
 */
public class SnowFlow {
    //因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。

    //机器ID  2进制5位  32位减掉1位 31个
    private long workerId;
    //机房ID 2进制5位  32位减掉1位 31个
    private long datacenterId;
    //代表一毫秒内生成的多个id的最新序号  12位 4096 -1 = 4095 个
    private long sequence;
    //设置一个时间初始值    2^41 - 1   差不多可以用69年
    private long twepoch = 1585644268888L;
    //5位的机器id
    private long workerIdBits = 5L;
    //5位的机房id；。‘
    private long datacenterIdBits = 5L;
    //每毫秒内产生的id数 2 的 12次方
    private long sequenceBits = 12L;
    // 这个是二进制运算，就是5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 这个是一个意思，就是5 bit最多只能有31个数字，机房id最多只能是32以内
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    // -1L 二进制就是1111 1111  为什么？
    // -1 左移12位就是 1111  1111 0000 0000 0000 0000
    // 异或  相同为0 ，不同为1
    // 1111  1111  0000  0000  0000  0000
    // ^
    // 1111  1111  1111  1111  1111  1111
    // 0000 0000 1111 1111 1111 1111 换算成10进制就是4095
    private long sequenceMask = -1L ^ (-1L << sequenceBits);
    //记录产生时间毫秒数，判断是否是同1毫秒
    private long lastTimestamp = -1L;
    public long getWorkerId(){
        return workerId;
    }
    public long getDatacenterId() {
        return datacenterId;
    }
    public long getTimestamp() {
        return System.currentTimeMillis();
    }


    public SnowFlow() {
    }

    public SnowFlow(long workerId, long datacenterId, long sequence) {

        // 检查机房id和机器id是否超过31 不能小于0
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(
                    String.format("worker Id can&#39;t be greater than %d or less than 0",maxWorkerId));
        }

        if (datacenterId > maxDatacenterId || datacenterId < 0) {

            throw new IllegalArgumentException(
                    String.format("datacenter Id can&#39;t be greater than %d or less than 0",maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    // 这个是核心方法，通过调用nextId()方法，
    // 让当前这台机器上的snowflake算法程序生成一个全局唯一的id
    public synchronized long nextId() {
        // 这儿就是获取当前时间戳，单位是毫秒
        long timestamp = timeGen();
        // 判断是否小于上次时间戳，如果小于的话，就抛出异常
        if (timestamp < lastTimestamp) {

            System.err.printf("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(
                    String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
                            lastTimestamp - timestamp));
        }

        // 下面是说假设在同一个毫秒内，又发送了一个请求生成一个id
        // 这个时候就得把seqence序号给递增1，最多就是4096
        if (timestamp == lastTimestamp) {

            // 这个意思是说一个毫秒内最多只能有4096个数字，无论你传递多少进来，
            //这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
            sequence = (sequence + 1) & sequenceMask;
            //当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }

        } else {
            sequence = 0;
        }
        // 这儿记录一下最近一次生成id的时间戳，单位是毫秒
        lastTimestamp = timestamp;
        // 这儿就是最核心的二进制位运算操作，生成一个64bit的id
        // 先将当前时间戳左移，放到41 bit那儿；将机房id左移放到5 bit那儿；将机器id左移放到5 bit那儿；将序号放最后12 bit
        // 最后拼接起来成一个64 bit的二进制数字，转换成10进制就是个long型
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) | sequence;
    }

    /**
     * 当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
     * @param lastTimestamp
     * @return
     */
    private long tilNextMillis(long lastTimestamp) {

        long timestamp = timeGen();

        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    //获取当前时间戳
    private long timeGen(){
        return System.currentTimeMillis();
    }

    /**
     *  main 测试类
     * @param args
     */
    public static void main(String[] args) {
//        System.out.println(1&4596);
//        System.out.println(2&4596);
//        System.out.println(6&4596);
//        System.out.println(6&4596);
//        System.out.println(6&4596);
//        System.out.println(6&4596);
        SnowFlow snowFlow = new SnowFlow(1, 1, 1);
        for (int i = 0; i < 22; i++) {
            System.out.println(snowFlow.nextId());
//		}
        }
    }
}

3. Algorithm advantages and disadvantages

Advantages:

(1) High performance and high availability: it does not depend on the database when generated, and is completely generated in memory.

(2) Large capacity: millions of self-increasing IDs can be generated per second.

(3) ID auto-increment: stored in the database, with high indexing efficiency.

Disadvantages:

Depends on the consistency with the system time. If the system time is called back or changed, it may cause ID conflicts or duplications (ID duplication problems caused by clock replay)

The above is the detailed content of How to write code to implement snowflake algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!