ID作为我们数据的唯一标识,具有不重复 ,算法生成式趋势递增的分布特点 。
如果ID不递增,原理数据插入会有性能问题 ,聊聊这个后面再聊。雪花
从成本及可靠性考虑,雪花算法是最佳之选。
雪花算法其实是对时间戳生成ID的方式的一种改进 ,通过64bit位生成long类型的唯一id,原理如下图 :
雪花算法组成
package com.xiaojiang;nnimport java.util.Set;nimport java.util.TreeSet;nn/**n * @author xiaojiangn * @version 1.0n * @description 雪花算法ID生成器n * @date 2022/6/22n */npublic class SnowflakeIdGenerator { nn // 初始时间戳一般为服务的上线时间n private static final long INIT_EPOCH = 1656169263130L;nn // 最后一次时间戳 ,用来判断是否同一毫秒和服务器时钟回拨判断n private long lastTimeMillis = -1L;nn // 数据中心占用的比特位n private static final long DATA_CENTER_ID_BITS = 5L;n // 数据中心最大值31n // 0000000000000000000000000000000000000000000000000000000000011111n private static final long MAX_DATA_CENTER_ID = ~(-1L << DATA_CENTER_ID_BITS);n // datacenterIdn private long datacenterId;nn // workId占用的位数n private static final long WORKER_ID_BITS = 5L;n // workId占用5个比特位,最大值31n // 0000000000000000000000000000000000000000000000000000000000011111n private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);n // workIdn private long workerId;nn // 最后12位,代表每毫秒内可产生最大序列号 ,即 2^12 - 1 = 4095n private static final long SEQUENCE_BITS = 12L;n // 掩码(最低12位为1,高位都为0),主要用于与自增后的序列号进行位与,如果值为0,则代表自增后的序列号超过了4095n // 0000000000000000000000000000000000000000000000000000111111111111n private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);n // 同一毫秒内的最新序号 ,最大值可为 2^12 - 1 = 4095n private long sequence;nn // workId位需要左移的位数 12n private static final long WORK_ID_SHIFT = SEQUENCE_BITS;n // dataCenterId位需要左移的位数 12+5n private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;n // 时间戳需要左移的位数 12+5+5n private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;nn public SnowflakeIdGenerator(long datacenterId, long workerId) { nn // 检查datacenterId的合法值n if (datacenterId < 0 || datacenterId > MAX_DATA_CENTER_ID) { n throw new IllegalArgumentException(n String.format("datacenterId值必须大于0并且小于%d", MAX_DATA_CENTER_ID));n }nn // 检查workId的合法值n if (workerId < 0 || workerId > MAX_WORKER_ID) { n throw new IllegalArgumentException(String.format("workId值必须大于0并且小于%d", MAX_WORKER_ID));n }nn this.workerId = workerId;n this.datacenterId = datacenterId;n }nn /**n * 通过雪花算法生成下一个id,注意这里使用synchronized同步n *n * @return 唯一idn */n public synchronized long nextId() { nn long currentTimeMillis = System.currentTimeMillis();nn // 当前时间小于上一次生成id使用的时间 ,可能出现服务器时钟回拨问题n if (currentTimeMillis < lastTimeMillis) { n throw new RuntimeException(n String.format("可能出现服务器时钟回拨问题,请检查服务器时间。当前服务器时间戳:%d ,上一次使用时间戳:%d", currentTimeMillis,n lastTimeMillis));n }ntt//还是在同一毫秒内,则将序列号递增1,序列号最大值为4095n if (currentTimeMillis == lastTimeMillis) { nn // 序列号的最大值是4095 ,使用掩码(最低12位为1,高位都为0)n //进行位与运行后如果值为0,则自增后的序列号超过了4095n // 那么就使用新的时间戳n sequence = (sequence + 1) & SEQUENCE_MASK;n if (sequence == 0) { n currentTimeMillis = tilNextMillis(lastTimeMillis);n }nn } else { // 不在同一毫秒内,则序列号重新从0开始 ,序列号最大值为4095n sequence = 0;n }nn // 记录最后一次使用的毫秒时间戳n lastTimeMillis = currentTimeMillis;nn // 核心算法,将不同部分的数值移动到指定的位置,然后进行或运行n return ((currentTimeMillis - INIT_EPOCH) << TIMESTAMP_SHIFT) n ttt| (datacenterId << DATA_CENTER_ID_SHIFT) n ttt| (workerId << WORK_ID_SHIFT) n ttt| sequence;n }nn /**n * 获取指定时间戳的接下来的时间戳,也可以说是下一毫秒n *n * @param lastTimeMillis 指定毫秒时间戳n * @return 时间戳n */n private long tilNextMillis(long lastTimeMillis) { n long currentTimeMillis = System.currentTimeMillis();n while (currentTimeMillis <= lastTimeMillis) { n currentTimeMillis = System.currentTimeMillis();n }n return currentTimeMillis;n }n}
重点讲一下这段代码
// 核心算法 ,将不同部分的数值移动到指定的位置,然后进行或运行n return ((currentTimeMillis - INIT_EPOCH) << TIMESTAMP_SHIFT) n ttt| (datacenterId << DATA_CENTER_ID_SHIFT) n ttt| (workerId << WORK_ID_SHIFT) n ttt| sequence;
举个栗子来说,我需要将9和5合成一个数。
9的二进制表示为1001 ,5的二进制表示为101,我们发现5的二进制占3位,那么需要将9左边3位腾出位置来 ,9左移3位即为1001000,我们知道
0 | 1 = 1
1 | 1 = 1
0 | 0 = 0
9左移其实是用0往右边补齐3位,那么1001000 | 0000101 = 1001101 实现了两数合并,雪花算法同理使用了这种实现了时间戳+数据中心ID+机器ID+自增序列的位数合并 。
(作者:汽车电瓶)