雪花算法详解-蒲公英云

雪花算法详解

雪花算法介绍

SnowFlake 算法，是 Twitter 开源的分布式 id 生成算法。其核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id

1位，不用。二进制中最高位为1的都是负数，但是生成的id都是正数，所以这个最高位固定是0
41位，用来记录时间戳（毫秒）。
- 41位可以表示241-1个数字，
- 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 241 - 1，减1是因为可表示的数值范围是从0开始算的，而不是1。
- 也就是说41位可以表示241 - 1个毫秒的值，转化成单位年则是241 - 1 / (1000 * 60 * 60 * 24 * 365) = 69年
10位，用来记录工作机器id。
- 可以部署在210 = 1024个节点，包括5位datacenterId和5位workerId
- 5位（bit）可以表示的最大正整数是25 - 1 = 31，即可以用0、1、2、3、….31这32个数字，来表示不同的datecenterId或workerId
12位，序列号，用来记录同毫秒内产生的不同id。
- 12位（bit）可以表示的最大正整数是212 - 1 = 4095，即可以用0、1、2、3、….4095这4096个数字，来表示同一机器同一时间截（毫秒)内产生的4096个ID序号，减1是因为可表示的数值范围是从0开始算的，而不是1。

同一毫秒：0-4095 4096，因为这一毫秒生产的ID数已经满了，因此需要让CPU空转，使得毫秒数增加1，那么此时这一毫秒的ID生成应该从0重新开始

算法实现

package com.qf.electronic.util;
/**
 * 雪花算法
 */
public class SnowFlake {
    /**
     * 这里需要记录最后一次生成ID的时间，因为同一毫秒内，可能会生成多个ID，记录后可以用来做比对
     */
    private long lastTime = -1L;
    /**
     * 初始时间，因为时间占41位，所以可以从这个时间开始，差不多使用69年
     */
    private long startTime = System.currentTimeMillis();
    /**
     * 机房ID，占5位，因此最多能够对32个机房有效
     */
    private long dataCenterId;
    /**
     * 机器ID，占5位，因此最多能够对32个机器有效
     */
    private long workId;
    /**
     * 序列号，占12位，因此在一毫秒内最多生成2^12 = 4096个序列号
     */
    private long sequence;
    public SnowFlake(long dataCenterId, long workId, long sequence){
        //机房ID最小值为0,最大值为31
        if(dataCenterId > 31 || dataCenterId < 0){
            throw new IllegalArgumentException("机房ID必须>=0且<=31，当前使用机房ID：" + dataCenterId);
        }
        if(workId > 31 || workId < 0){
            throw new IllegalArgumentException("机器ID必须>=0且<=31，当前使用机器ID：" + workId);
        }
        this.dataCenterId = dataCenterId;
        this.workId = workId;
        this.sequence = sequence;
    }
    public long generateId(){
        long time = System.currentTimeMillis(); //获取系统当前时间
        if(time < lastTime){//防止时间回拨，必须手动将时间拨回
            throw new RuntimeException("时间回拨");
        }
        if(time == lastTime){//同一时间段内，生成多个ID
            //按位与操作符所得结果最大值不会超过参与运算的最小操作数，这里不能超过4096
            sequence = (sequence + 1) & 4095;
            if(sequence == 0){//如果计数重新归0，表示该毫秒内，ID生成的数量已满
                //CPU空转1毫秒
                while ((time = System.currentTimeMillis()) == lastTime);
            }
        } else {
            sequence = 0;
        }
        //时间本身占41位，但是需要向左移动22位才能在指定的位置上
        //机房ID占5位，但是需要向左移动17位才能在指定的位置上
        //机器ID占5位，但是需要向左移动12位才能在指定的位置上
        long id = (time - startTime) << 22 | dataCenterId << 17 | workId << 12 | sequence;
        lastTime = time;
        return id;
    }
}