Java教程

分布式唯一ID之雪花算法(Snowflake)原理分析

本文主要是介绍分布式唯一ID之雪花算法(Snowflake)原理分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

先来看看雪花算法生成的唯一ID的结构:

image

如上图所示,雪花算法生成的ID一共64bit。共分为4个组成部分来保证唯一性,分别是:

  • 1bit:不使用,默认为0
  • 41bit:单位毫秒,时间戳 = 当前系统时间 - 系统上线时间
  • 10bit:机器ID,可同时部署的机器节点数 210-1=1023
  • 12bit:序列号,当时间戳和机器ID相同时,此值递增保证唯一性。即同一机器同一毫秒可生成的唯一ID数为212-1

下面通过Hutool提供的雪花算法工具类源码来学习一下:

public class Snowflake implements Serializable {
    private static final long serialVersionUID = 1L;
    /** 起始时间戳 */
    private final long twepoch;
    /** 机器ID的位数 */
    private final long workerIdBits;
    /** 数据中心ID的位数 */
    private final long dataCenterIdBits;
    /** 机器ID的最大值 */
    private final long maxWorkerId;
    /** 数据中心ID的最大值 */
    private final long maxDataCenterId;
    /** 序列号位数 */
    private final long sequenceBits;
    /** 机器ID偏移量 */
    private final long workerIdShift;
    /** 数据中心ID偏移量 */
    private final long dataCenterIdShift;
    /** 时间戳偏移量 */
    private final long timestampLeftShift;
    /** 序列码,用来计算序列号 */
    private final long sequenceMask;
    /** 机器ID */
    private final long workerId;
    /** 数据中心ID */
    private final long dataCenterId;
    /** 是否使用Hutool提供的系统时钟 */
    private final boolean useSystemClock;
    /** 序列号 */
    private long sequence;
    /** 上一次生成ID的时间戳 */
    private long lastTimestamp;

    public Snowflake(long workerId, long dataCenterId) {
        // 默认不使用Hutool提供的时间戳
        this(workerId, dataCenterId, false);
    }

    public Snowflake(long workerId, long dataCenterId, boolean isUseSystemClock) {
        // 默认起始时间戳 2010-11-04 09:42:54
        this((Date)null, workerId, dataCenterId, isUseSystemClock);
    }

    public Snowflake(Date epochDate, long workerId, long dataCenterId, boolean isUseSystemClock) {
        // 默认机器ID位数 5,同一数据中心可部署的机器节点为 2的5次方-1
        this.workerIdBits = 5L;
        // 默认数据中心ID位数为 5,可部署的数据中心为 2的5次方-1
        this.dataCenterIdBits = 5L;
        // 默认最大的机器ID为 31
        this.maxWorkerId = 31L;
        // 默认最大的数据中心ID为 31
        this.maxDataCenterId = 31L;
        // 默认序列号位数为 12
        this.sequenceBits = 12L;
        // 机器ID的偏移量为 12,即序列号的位数
        this.workerIdShift = 12L;
        // 数据中心的偏移量为 17,即机器ID的偏移量 + 机器ID的位数
        this.dataCenterIdShift = 17L;
        // 时间戳的偏移量为 22,即数据中心的偏移量 + 数据中心的位数
        this.timestampLeftShift = 22L;
        // 序列码默认为 2的12次方-1 = 4095,用来计算序列号,即同一机器每毫秒可生成4095个唯一ID
        this.sequenceMask = 4095L;
        // 默认序列号为 0
        this.sequence = 0L;
        // 默认上一次生成ID的时间戳为 -1
        this.lastTimestamp = -1L;
        if (null != epochDate) {
            // 得到自定义日期的时间戳作为起始时间戳
            this.twepoch = epochDate.getTime();
        } else {
            // 默认的起始时间戳 2010-11-04 09:42:54
            this.twepoch = 1288834974657L;
        }
        // 校验机器ID的大小和数据中心ID的大小,[0,31]
        if (workerId <= 31L && workerId >= 0L) {
            if (dataCenterId <= 31L && dataCenterId >= 0L) {
                this.workerId = workerId;
                this.dataCenterId = dataCenterId;
                this.useSystemClock = isUseSystemClock;
            } else {
                throw new IllegalArgumentException(StrUtil.format("datacenter Id can't be greater than {} or less than 0", new Object[]{31L}));
            }
        } else {
            throw new IllegalArgumentException(StrUtil.format("worker Id can't be greater than {} or less than 0", new Object[]{31L}));
        }
    }

    /**
     * 核心方法:生成唯一ID
     * 加锁,保证线程安全
     */
    public synchronized long nextId() {
        // 获取当前时间戳
        long timestamp = this.genTime();
        // 如果当前时间戳小于上次生成ID的时间戳
        if (timestamp < this.lastTimestamp) {
            // 当前时间戳与上次生成ID的时间戳差值 超过 2秒,拒绝生成ID,提示:时钟向后移动
            if (this.lastTimestamp - timestamp >= 2000L) {
                throw new IllegalStateException(StrUtil.format("Clock moved backwards. Refusing to generate id for {}ms", new Object[]{this.lastTimestamp - timestamp}));
            }
            // 将上次生成ID的时间戳 赋值给 当前时间戳
            timestamp = this.lastTimestamp;
        }
        // 如果当前时间戳 等于 上次生成ID的时间戳
        if (timestamp == this.lastTimestamp) {
            // 首先将序列号递增
            this.sequence = this.sequence + 1L & 4095L;
            // 如果序列号为 0,即序列号递增后达到最大值,重新从 0开始
            if (this.sequence == 0L) {
                // 此时无法使用序列号递增保证唯一性,则将时间戳推移到下一毫秒
                timestamp = this.tilNextMillis(this.lastTimestamp);
            }
        } else {
            // 如果当前时间戳 不等于 上次生成ID的时间戳,则序列号从 0 开始
            this.sequence = 0L;
        }
        // 将本次时间戳 赋值为 最后一次生成ID的时间戳变量
        this.lastTimestamp = timestamp;
        // 将各个组成部分加起来,组成一个唯一ID,使用效率最高的 二进制位运算,或运算类似于十进制的加法
        // 公式:(当前时间戳 - 起始时间戳)左移 时间戳的偏移量 
        //         | 数据中心ID 左移 数据中心ID的偏移量
        //         | 机器ID 左移 机器ID的偏移量
        //         | 序列号
        return timestamp - this.twepoch << 22 | this.dataCenterId << 17 | this.workerId << 12 | this.sequence;
    }

    public String nextIdStr() {
        return Long.toString(this.nextId());
    }

    /**
     * 得到下一毫秒的时间戳
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp;
        // 类似于CAS算法,循环直到下一毫秒
        for(timestamp = this.genTime(); timestamp == lastTimestamp; timestamp = this.genTime()) {
        }
        // 如果计算得到的下一毫秒的时间戳 反而比 传入的参数还小了,则发生了时钟回退,抛出异常
        if (timestamp < lastTimestamp) {
            throw new IllegalStateException(StrUtil.format("Clock moved backwards. Refusing to generate id for {}ms", new Object[]{lastTimestamp - timestamp}));
        } else {
            // 返回下一毫秒的时间戳
            return timestamp;
        }
    }

    /**
     * 获取当前时间戳
     */
    private long genTime() {
        // 默认使用 System.currentTimeMillis() 生成时间戳
        return this.useSystemClock ? SystemClock.now() : System.currentTimeMillis();
    }
}
这篇关于分布式唯一ID之雪花算法(Snowflake)原理分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!