Snowflake 雪花算法

分布式系统中ID生成方案，比较简单的是UUID（Universally Unique Identifier，通用唯一识别码），但是其存在两个明显的弊端：一、UUID是128位的，长度过长；二、UUID是完全随机的，无法生成递增有序的UUID。而现在流行的基于 Snowflake 雪花算法的ID生成方案就可以很好的解决了UUID存在的这两个问题

原理

Snowflake 雪花算法，由Twitter提出并开源，可在分布式环境下用于生成唯一ID的算法。该算法生成的是一个64位的ID，故在Java下正好可以通过8字节的long类型存放。所生成的ID结构如下所示

• 符号位

最高位是符号位，为保证生成的ID是正数，故不使用，其值恒为0

• 时间戳

用来记录时间戳的毫秒数。一般地，我们会选用系统上线的时间作为时间戳的相对起点，而不使用JDK默认的时间戳起点（1970-01-01 00:00:00）。41位长度的时间戳可以保证使用69年。对于一般的项目而言，这个时间长度绝对是够用了

• 数据中心ID、机器ID

数据中心（机房）ID、机器ID一共10位，用于标识工作的计算机，在这里数据中心ID、机器ID各占5位。实际上，数据中心ID的位数、机器ID位数可根据实际情况进行调整，没有必要一定按1:1的比例分配来这10位

• 序列号

最低的12位为序列号，可用于标识、区分同一个计算机在相同毫秒时间内的生产的ID

综上所述，Snowflake 雪花算法生成的ID不是随机的，而是按时间顺序升序排列的；且可以保证在分布式高并发环境下生成的ID不会发生重复

Java实现

这里使用Java来实现一个基于 Snowflake 雪花算法的ID生成器

/**
 * Snowflake 基于雪花算法的ID生成器
 */
public class SnowflakeIdGenerator {

    /**
     * ID中41位时间戳的起点 (2020-01-01 00:00:00.00)
     * @apiNote 一般地，选用系统上线的时间
     */
    private final long startPoint = 1577808000000L;

    /**
     * 序列号位数
     */
    private final long sequenceBits = 12L;

    /**
     * 机器ID位数
     */
    private final long workerIdBits = 5L;

    /**
     * 数据中心ID位数
     */
    private final long dataCenterIdBits = 5L;

    /**
     * 序列号最大值, 4095
     * @apiNote 4095 = 0xFFF,其相当于是序列号掩码
     */
    private final long sequenceMask = -1L^(-1L<<sequenceBits);

    /**
     * 机器ID最大值, 31
     */
    private final long maxWorkerId = -1L^(-1L<<workerIdBits);

    /**
     * 数据中心ID最大值, 31
     */
    private final long maxDataCenterId = -1L^(-1L<<dataCenterIdBits);

    /**
     * 机器ID左移位数, 12
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 数据中心ID左移位数, 12+5
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;

    /**
     * 时间戳左移位数, 12+5+5
     */
    private final long timeStampShift = sequenceBits + workerIdBits + dataCenterIdBits;

    /**
     * 数据中心ID, Value Range: [0,31]
     */
    private long dataCenterId;

    /**
     * 机器ID, Value Range: [0,31]
     */
    private long workerId;

    /**
     * 相同毫秒内的序列号, Value Range: [0,4095]
     */
    private long sequence = 0L;

    /**
     * 上一个生成ID的时间戳
     */
    private long lastTimeStamp = -1L;

    /**
     * 构造器
     * @param dataCenterId  数据中心ID
     * @param workerId 机器中心ID
     */
    public SnowflakeIdGenerator(Long dataCenterId, Long workerId) {
        if(dataCenterId==null || dataCenterId<0 || dataCenterId>maxDataCenterId
            || workerId==null || workerId<0 || workerId>maxWorkerId) {
            throw new IllegalArgumentException("输入参数错误");
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    /**
     * 获取ID
     * @return
     */
    public synchronized long nextId() {
        long currentTimeStamp = System.currentTimeMillis();
        //当前时间小于上一次生成ID的时间戳，系统时钟被回拨
        if( currentTimeStamp < lastTimeStamp ) {
            throw new RuntimeException("系统时钟被回拨");
        }

        // 当前时间等于上一次生成ID的时间戳,则通过序列号来区分
        if( currentTimeStamp == lastTimeStamp ) {
            // 通过序列号掩码实现只取 (sequence+1) 的低12位结果，其余位全部清零
            sequence = (sequence + 1) & sequenceMask;
            if(sequence == 0) { // 该时间戳下的序列号已经溢出
                // 阻塞等待下一个毫秒,并获取新的时间戳
                currentTimeStamp = getNextMs(lastTimeStamp);
            }
        } else {    // 当前时间大于上一次生成ID的时间戳,重置序列号
            sequence = 0;
        }

        // 更新上次时间戳信息
        lastTimeStamp = currentTimeStamp;

        // 生成此次ID
        long nextId = ((currentTimeStamp-startPoint) << timeStampShift)
                | (dataCenterId << dataCenterIdShift)
                | (workerId << workerIdShift)
                | sequence;

        return nextId;
    }

    /**
     * 阻塞等待,直到获取新的时间戳(下一个毫秒)
     * @param lastTimeStamp
     * @return
     */
    private long getNextMs(long lastTimeStamp) {
        long timeStamp = System.currentTimeMillis();
        while(timeStamp<=lastTimeStamp) {
            timeStamp = System.currentTimeMillis();
        }
        return timeStamp;
    }
}

上述代码比较简单，这里对其中涉及到的位运算部分作解释说明

1. 计算X位Bit能表示的最大值

计算X位Bit能表示的最大值，最简单的是 Math.pow(2,X)-1，不过还可以通过位运算来提高速度，即 -1^(-1<<X)。这里以X等于3为例作图解说明

Note:

在计算机的二进制下 -1 使用全1进行表示

2. 判定某个值是否大于X位Bit所能表示的最大值

判定一个数num是否大于X位Bit所能表示的最大值maxNum，可以直接用关系运算符进行比较。但是由于maxNum的低X位均为1，故我们还可以将其看作是一个掩码，用于将num中除低X位外的其余位全部清零。在num从1逐渐递增的过程中，当 num&maxNum 的结果恰好为0时，则表明num已经开始大于maxNum。这里以X等于3为例作图解说明