详解分布式ID实践

引言

分布式ID，所谓的分布式ID，就是针对整个系统而言，任何时刻获取一个ID，无论系统处于何种情况，该值不会与之前产生的值重复，之后获取分布式ID时，也不会再获取到与其相同的值，它是一个绝对意义上的全局唯一值。

那么，究竟什么情况下需要用到分布式ID呢？

最经典的场景是分库分表，还是以用户数据来举例子，之前只有一张用户表，所以设置表ID自增后，每新增一条数据都会自增ID值，从而确保了ID永远不会重复。
此刻用户表被分成了十张，如果再依靠数据库本身的自增机制来分配ID，显然会导致ID重复，这时分布式ID就派上了用场。除开分库分表外，通常还会用到分布式ID的场景有：

链路ID：分布式链路中，需要通过全局唯一的traceId来串联所有日志；
请求ID：幂等性处理时，需要通过唯一的ID来判断是否为重复请求；
消息标识：MQ需要基于唯一的msgID来区分数据，确保数据不重复或丢失；
短链码：生成短链接时，需要获取一个全局唯一的值作为Code避免重复；

下面将阐述怎么在项目中实践，为我们的对象生成一个分布式ID

UUID生成

String uuid = UUID.randomUUID().toString();
System.out.println(uuid);

/*
* 输出结果：
*   b2c2ec5d-efb9-44c7-b2c8-9cef367c8b3f
* */

通过JDK提供的UUID工具类，一行代码就能生成一个UUID，并且得到的UUID不会重复，怎么保障的呢？UUID的底层，会基于硬件地址（MAC地址）、时间戳和随机因子来生成ID。
世界上没有两片完全相同的叶子，者如这句话一般，世界上也没有两台完全相同的机器，这时硬件地址自然不同，再加上正常情况下不可逆转的时间戳，以及一定范围的随机数，就能确保产生的UUID，其全球唯一性。

雪花算法

雪花算法生成的分布式ID，在Java中会使用Long类型来承载，Long类型占位8bytes，也就正好对应上述这张图的64个比特位，这64bit会被分为四部分：

符号位（1bit）：永远为零，表示生成的分布式ID为正数。
时间戳位（2~42bit）：会将当前系统的时间戳插入到这段位置。
工作进程位（43~53bit）：在集群环境下，每个进程唯一的工作ID。
序列号位（54~64bit）：该序列是用来在同一个毫秒内生成不同的序列号。

/*
* 雪花算法实现类
* */
public class Snowflake implements Serializable {
    private static final long serialVersionUID = 1L;
    // 雪花算法的起始时间纪元
    public static long DEFAULT_TWEPOCH = 1288834974657L;
    public static long DEFAULT_TIME_OFFSET = 2000L;
    
    // 机器标识所占的位数
    private static final long WORKER_ID_BITS = 5L;
    // 数据中心标识所占的位数
    private static final long DATA_CENTER_ID_BITS = 5L;
    // 毫秒内的自增位数
    private static final long SEQUENCE_BITS = 12L;
    // 机器ID最大值
    private static final long MAX_WORKER_ID = 31L;
    // 数据中心ID最大值
    private static final long MAX_DATA_CENTER_ID = 31L;
    // 机器ID左移12位
    private static final long WORKER_ID_SHIFT = 12L;
    // 数据中心左移17位
    private static final long DATA_CENTER_ID_SHIFT = 17L;
    // 毫秒时间戳左移22位
    private static final long TIMESTAMP_LEFT_SHIFT = 22L;
    private static final long SEQUENCE_MASK = 4095L;
    // 雪花ID相关组成部分的定义
    private final long twepoch;
    private final long workerId;
    private final long dataCenterId;
    private final boolean useSystemClock;
    private final long timeOffset;
    private final long randomSequenceLimit;
    private long sequence;
    // 最近一次生产ID的时间戳
    private long lastTimestamp;

    public Snowflake() {
        this(IdUtil.getWorkerId(IdUtil.getDataCenterId(31L), 31L));
    }

    public Snowflake(long workerId) {
        this(workerId, IdUtil.getDataCenterId(31L));
    }

    public Snowflake(long workerId, long dataCenterId) {
        this(workerId, dataCenterId, false);
    }

    public Snowflake(long workerId, long dataCenterId, boolean isUseSystemClock) {
        this((Date)null, workerId, dataCenterId, isUseSystemClock);
    }

    public Snowflake(Date epochDate, long workerId, long dataCenterId, boolean isUseSystemClock) {
        this(epochDate, workerId, dataCenterId, isUseSystemClock, DEFAULT_TIME_OFFSET);
    }

    public Snowflake(Date epochDate, long workerId, long dataCenterId, boolean isUseSystemClock, long timeOffset) {
        this(epochDate, workerId, dataCenterId, isUseSystemClock, timeOffset, 0L);
    }

    public Snowflake(Date epochDate, long workerId, long dataCenterId, boolean isUseSystemClock, long timeOffset, long randomSequenceLimit) {
        this.sequence = 0L;
        this.lastTimestamp = -1L;
        this.twepoch = null != epochDate ? epochDate.getTime() : DEFAULT_TWEPOCH;
        this.workerId = Assert.checkBetween(workerId, 0L, 31L);
        this.dataCenterId = Assert.checkBetween(dataCenterId, 0L, 31L);
        this.useSystemClock = isUseSystemClock;
        this.timeOffset = timeOffset;
        this.randomSequenceLimit = Assert.checkBetween(randomSequenceLimit, 0L, 4095L);
    }

    public long getWorkerId(long id) {
        return id >> 12 & 31L;
    }

    public long getDataCenterId(long id) {
        return id >> 17 & 31L;
    }

    public long getGenerateDateTime(long id) {
        return (id >> 22 & 2199023255551L) + this.twepoch;
    }

    public synchronized long nextId() {
        long timestamp = this.genTime();
        // 解决时钟回拨问题
        if (timestamp < this.lastTimestamp) {
            if (this.lastTimestamp - timestamp >= this.timeOffset) {
                throw new IllegalStateException(StrUtil.format("Clock moved backwards. Refusing to generate id for {}ms", new Object[]{this.lastTimestamp - timestamp}));
            }

            timestamp = this.lastTimestamp;
        }

        if (timestamp == this.lastTimestamp) {
            long sequence = this.sequence + 1L & 4095L;
            if (sequence == 0L) {
                timestamp = this.tilNextMillis(this.lastTimestamp);
            }

            this.sequence = sequence;
        } else if (this.randomSequenceLimit > 1L) {
            this.sequence = RandomUtil.randomLong(this.randomSequenceLimit);
        } else {
            this.sequence = 0L;
        }

        this.lastTimestamp = timestamp;
        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;
        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() {
        return this.useSystemClock ? SystemClock.now() : System.currentTimeMillis();
    }
}

上面代码可以直接引用来作为我们的雪花算法工具类

由于原始版雪花算法存在的问题，出现了许多改良版算法，但其核心还是前面聊到的雪花算法，比如百度的Uid-Generator算法、美团的Leaf算法-雪花模式、阿里的Seata框架里的雪花算法实现等等，感兴趣的小伙伴可以自行翻阅源码。

以上就是最常用的实践方式欢迎大家补充