SnowFlake算法

hiriki2022-10-112022-10-11

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。

其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

具体介绍

雪花算法是 64 位的二进制，一共包含了四部分：

1位是符号位，也就是最高位，始终是0，没有任何意义，因为要是唯一计算机二进制补码中就是负数，0才是正数。
41位是时间戳，具体到毫秒，41位的二进制可以使用69年，因为时间理论上永恒递增，所以根据这个排序是可以的。
10位是机器标识，可以全部用作机器ID，也可以用来标识机房ID + 机器ID，10位最多可以表示1024台机器。
12位是计数序列号，也就是同一台机器上同一时间，理论上还可以同时生成不同的ID，12位的序列号能够区分出4096个ID。

snowflake

package cn.ray.domain.support.ids;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author Ray
 * @date 2022/10/12 16:18
 * @description 雪花算法生成随机ID
 */

public class SnowFlake {

    private Logger logger = LoggerFactory.getLogger(SnowFlake.class);

    /**
     * 数据中心(机房)ID
     */
    private long dataCenterId;
    /**
     * 机器ID
     */
    private long workerId;
    /**
     * 同一时间的序列号
     */
    private long sequence;

    /**
     * 开始时间戳:2020-05-20 08:00:00 +0800 CST
     */
    private final long twepoch = 1589923200000L;
    /**
     * 机房ID所占位数 5bit 最大:11111(二进制)-->31(十进制)
     */
    private final long dataCenterIdBits = 5L;
    /**
     * 机器ID所占位数 5bit 最大:11111(二进制)-->31(十进制)
     */
    private final long workerIdBits = 5L;
    /**
     * 同一时间的序列号所占位数 12bit 最大:111111111111(二进制)-->4095(十进制)
     */
    private final long sequenceBits = 12L;
    /**
     * 5 bit最多只能有31个数字，即机房id数量最多只能是32以内
     */
    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    /**
     * 5 bit最多只能有31个数字，即机器id数量最多只能是32以内
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    /**
     * 序列号掩码(0b111111111111==>0xfff==>4096)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    /**
     * 机器ID偏移量
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 机房ID偏移量
     */
    private final long dataCenterIdShift = workerIdBits + sequenceBits;
    /**
     * 时间戳偏移量
     */
    private final long timestampLeftShift = dataCenterIdBits + workerIdBits + sequenceBits;
    /**
     * 最近一次时间戳
     */
    private long lastTimestamp = -1L;

    public SnowFlake(long dataCenterId, long workerId) {
        this(dataCenterId,workerId,0);
    }

    public SnowFlake(long dataCenterId, long workerId, long sequence) {
        if ( dataCenterId>maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("机房ID 大于最大值 %d 或者 小于 0",maxDataCenterId));
        }
        if ( workerId>maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("机器ID 大于最大值 %d 或者 小于 0",maxWorkerId));
        }
        logger.info("机器启动中: 时间戳偏移量:{},机房ID占位:{},机器ID占位:{},序列号占位:{},机器ID:{}",
                timestampLeftShift,dataCenterIdBits,workerIdBits,sequenceBits,workerId);
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
        this.sequence = sequence;
    }

    /**
     * 获取机房ID
     * @return 机房ID
     */
    public long getDataCenterId() {
        return dataCenterId;
    }

    /**
     * 获取机器ID
     * @return 机器ID
     */
    public long getWorkerId() {
        return workerId;
    }

    /**
     * 获取最新的时间戳
     * @return 上一次生成ID的时间戳
     */
    public long getLastTimestamp() {
        return lastTimestamp;
    }

    /**
     * 获取下一个随机ID
     * @return 随机ID
     */
    public synchronized long nextId(){
        long currentTimestamp = System.currentTimeMillis();

        if (currentTimestamp < lastTimestamp) {
            logger.error("时间回退,最新时间戳:{}",lastTimestamp);
            throw new RuntimeException(String.format("时间回退,拒绝生成ID,实际相差: %d",lastTimestamp - currentTimestamp));
        }

        // 去重
        if (currentTimestamp == lastTimestamp) {
            sequence = (sequenceMask+1) & sequenceMask;

            // 如果 sequence 序列号 大于 4095
            if(sequence == 0) {
                currentTimestamp = nextTimestamp(lastTimestamp);
            }
        } else {
            // 如果是当前时间第一次生成ID,就初始化为0
            sequence = 0;
        }

        // 记录最新时间戳
        lastTimestamp = currentTimestamp;

        // 偏移计算生成随机ID
        return ((currentTimestamp - twepoch) << timestampLeftShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    private long nextTimestamp(long lastTimestamp) {
        long currentTimestamp = System.currentTimeMillis();

        // 如果当前时间戳小于等于 序列号已经超过4095 那个时间戳
        // 继续获取最新时间戳
        if (currentTimestamp <= lastTimestamp) {
            currentTimestamp = System.currentTimeMillis();
        }

        return currentTimestamp;
    }
}

snowflake_shift

最后将三部分(时间戳、机器ID、序列号)按照偏移量进行移位操作，然后按位或将其组合即可得到随机生成的唯一ID

优化

由于41位是时间戳，我们的时间计算是从1970年开始的，只能使用69年，为了不浪费，其实我们可以用时间的相对值，也就是以项目开始的时间为基准时间，往后可以使用69年。获取唯一ID的服务，对处理速度要求比较高，所以我们全部使用位运算以及位移操作，获取当前时间可以使用System.currentTimeMillis()。
时间回拨问题
在获取时间的时候，可能会出现时间回拨的问题，时间回拨其实就是服务器上的时间突然倒退到之前的时间。
1. 人为原因，把系统环境的时间改了。
2. 有时候不同的机器上需要同步时间，可能不同机器之间存在误差，那么可能会出现时间回拨问题。
解决方案
1. 回拨时间小的时候，不生成 ID，循环等待到时间点到达。
2. 上面的方案只适合时钟回拨较小的，如果间隔过大，阻塞等待，肯定是不可取的，因此要么超过一定大小的回拨直接报错，拒绝服务，或者有一种方案是利用拓展位，回拨之后在拓展位上加1就可以了，这样ID依然可以保持唯一。但是这个要求我们提前预留出位数，要么从机器id中，要么从序列号中，腾出一定的位，在时间回拨的时候，这个位置 +1。

SnowFlake算法

SnowFlake算法

具体介绍

优化

时间回拨问题

相关问题

1. 第一位为什么不使用?

2.机器位怎么用？

3. twepoch表示什么？

4. -1L ^ (-1L << x) 表示什么？

5.时间戳比较

6.前端直接使用发生精度丢失

hiriki