常见算法
一：UUID：因为是本地生成，性能极高，但是生成的ID太长，16字节128位，通常需要字符串类型存储，且无序，所以很多场景不适用，也不适用于作为MySQL数据库的主键和索引（MySql官方建议，主键越短越好；对于InnoDB引擎，索引的无序性可能会引起数据位置频繁变动，严重影响性能）。
二：数据库自增ID：每次获取ID都需要DB的IO操作，DB压力大，性能低。数据库宕机对外依赖服务就是毁灭性打击，不过可以部署数据库集群保证高可用。
三：数据库号段算法：对数据库自增ID的优化，每次获取一个号段的值。用完之后再去数据库获取新的号段，可以大大减轻数据库的压力。号段越长，性能越高，同时如果数据库宕机，号段没有用完，短时间还可以对外提供服务。（美团的Leaf、滴滴的TinyId）
四：雪花算法：Twitter开源的snowflake，以时间戳+机器+递增序列组成，基本趋势递增，且性能很高，因为强依赖机器时钟，所以需要考虑时钟回拨问题，即机器上的时间可能因为校正出现倒退，导致生成的ID重复。（百度的uid-generator、美团的Leaf）
雪花算法
条件
数据库分库分表是一贯的垂直水平做法，但是需要一个全局唯一ID标识一条数据或者MQ消息，数据库id自增就显然不能满足要求了。因为场景不同，分布式ID需要满足以下几个条件：
一：全局唯一性，不能出现重复的ID。
二：趋势递增，在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上应该尽量使用有序的主键保证写入性能。
三：单调递增，保证下一个ID一定大于上一个ID。例如分布式事务版本号、IM增量消息、排序等特殊需求。
四：信息安全，对于特殊业务，如订单等，分布式ID生成应该是无规则的，不能从ID上反解析出流量等敏感信息。
定义
snowflake原理其实很简单，生成一个64bit（long）的全局唯一ID，标准元素以1bit无用符号位+41bit时间戳+10bit机器ID+12bit序列化组成，其中除1bit符号位不可调整外，其他三个标识的bit都可以根据实际情况调整：
41bit-时间可以表示（1L<<41）/(1000L*3600*24*365)=69年的时间。
10bit-机器可以表示1024台机器。如果对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器
12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s
都是从0开始计数
优点
毫秒数在高位，自增序列在低位，整个ID都是趋势递增的
可以不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高
可以根据自身业务特性分配bit位，非常灵活
缺点
强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务处于不可用状态
Java实现
41bit给时间戳，5bit给IDC，5bit给工作机器，12bit给序列号，代码中是写死的，如果某些bit需要动态调整，可在成员属性定义。计算过程需要一些位运算基础
public class SnowflakeIdGenerator {
public static final int TOTAL_BITS = 1 << 6;
private static final long SIGN_BITS = 1;
private static final long TIME_STAMP_BITS = 41L;
private static final long DATA_CENTER_ID_BITS = 5L;
private static final long WORKER_ID_BITS = 5L;
private static final long SEQUENCE_BITS = 12L;
/**
* 时间向左位移位数 22位
*/
private static final long TIMESTAMP_LEFT_SHIFT = WORKER_ID_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS;
/**
* IDC向左位移位数 17位
*/
private static final long DATA_CENTER_ID_SHIFT = WORKER_ID_BITS + SEQUENCE_BITS;
/**
* 机器ID 向左位移位数 12位
*/
private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
/**
* 序列掩码，用于限定序列最大值为4095
*/
private static final long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS);
/**
* 最大支持机器节点数0~31，一共32个
*/
private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
/**
* 最大支持数据中心节点数0~31，一共32个
*/
private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);
/**
* 最大时间戳 2199023255551
*/
private static final long MAX_DELTA_TIMESTAMP = -1L ^ (-1L << TIME_STAMP_BITS);
/**
* Customer epoch
*/
private final long twepoch;
private final long workerId;
private final long dataCenterId;
private long sequence = 0L;
private long lastTimestamp = -1L;
/**
*
* @param workerId 机器ID
* @param dataCenterId IDC ID
*/
public SnowflakeIdGenerator(long workerId, long dataCenterId) {
this(workerId, dataCenterId, null);
}
/**
*
* @param workerId 机器ID
* @param dataCenterId IDC ID
* @param epochDate 初始化时间起点
*/
public SnowflakeIdGenerator(long workerId, long dataCenterId, Date epochDate) {
if (workerId > MAX_WORKER_ID || workerId < 0) {
throw new IllegalArgumentException("worker Id can't be greater than "+ MAX_WORKER_ID + " or less than 0");
}
if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
throw new IllegalArgumentException("datacenter Id can't be greater than {" + MAX_DATA_CENTER_ID + "} or less than 0");
}
this.workerId = workerId;
this.dataCenterId = dataCenterId;
if (epochDate != null) {
this.twepoch = epochDate.getTime();
} else {
//2010-10-11
this.twepoch = 1286726400000L;
}
}
public long genID() throws Exception {
try {
return nextId();
} catch (Exception e) {
throw e;
}
}
public long getLastTimestamp() {
return lastTimestamp;
}
/**
* 通过移位解析出sequence，sequence有效位为[0,12]
* 所以先向左移64-12，然后再像右移64-12，通过两次移位就可以把无效位移除了
* @param id
* @return
*/
public long getSequence2(long id) {
return (id << (TOTAL_BITS - SEQUENCE_BITS)) >>> (TOTAL_BITS - SEQUENCE_BITS);
}
/**
* 通过移位解析出workerId，workerId有效位为[13,17], 左右两边都有无效位
* 先向左移 41+5+1，移除掉41bit-时间，5bit-IDC、1bit-sign，
* 然后右移回去41+5+1+12，从而移除掉12bit-序列号
* @param id
* @return
*/
public long getWorkerId2(long id) {
return (id << (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
* 通过移位解析出IDC_ID，dataCenterId有效位为[18,23]，左边两边都有无效位
* 先左移41+1，移除掉41bit-时间和1bit-sign
* 然后右移回去41+1+5+12，移除掉右边的5bit-workerId和12bit-序列号
* @param id
* @return
*/
public long getDataCenterId2(long id) {
return (id << (TIME_STAMP_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
* 41bit-时间，左边1bit-sign为0，可以忽略，不用左移，所以只需要右移，并加上起始时间twepoch即可。
* @param id
* @return
*/
public long getGenerateDateTime2(long id) {
return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch;
}
public long getSequence(long id) {
return id & ~(-1L << SEQUENCE_BITS);
}
public long getWorkerId(long id) {
return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
}
public long getDataCenterId(long id) {
return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
}
public long getGenerateDateTime(long id) {
return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + twepoch;
}
private synchronized long nextId() throws Exception {
long timestamp = timeGen();
// 1、出现时钟回拨问题，直接抛异常
if (timestamp < lastTimestamp) {
long refusedTimes = lastTimestamp - timestamp;
// 可自定义异常类
throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", refusedTimes));
}
// 2、时间等于lastTimestamp，取当前的sequence + 1
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & SEQUENCE_MASK;
// Exceed the max sequence, we wait the next second to generate id
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 3、时间大于lastTimestamp没有发生回拨， sequence 从0开始
this.sequence = 0L;
}
lastTimestamp = timestamp;
return allocate(timestamp - this.twepoch);
}
private long allocate(long deltaSeconds) {
return (deltaSeconds << TIMESTAMP_LEFT_SHIFT) | (this.dataCenterId << DATA_CENTER_ID_SHIFT) | (this.workerId << WORKER_ID_SHIFT) | this.sequence;
}
private long timeGen() {
long currentTimestamp = System.currentTimeMillis();
// 时间戳超出最大值
if (currentTimestamp - twepoch > MAX_DELTA_TIMESTAMP) {
throw new UnsupportedOperationException("Timestamp bits is exhausted. Refusing ID generate. Now: " + currentTimestamp);
}
return currentTimestamp;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) throws Exception {
SnowflakeIdGenerator snowflakeIdGenerator = new SnowflakeIdGenerator(1,2);
long id = snowflakeIdGenerator.genID();
System.out.println("ID=" + id + ", lastTimestamp=" + snowflakeIdGenerator.getLastTimestamp());
System.out.println("ID二进制：" + Long.toBinaryString(id));
System.out.println("解析ID:");
System.out.println("Sequence=" + snowflakeIdGenerator.getSequence(id));
System.out.println("WorkerId=" + snowflakeIdGenerator.getWorkerId(id));
System.out.println("DataCenterId=" + snowflakeIdGenerator.getDataCenterId(id));
System.out.println("GenerateDateTime=" + snowflakeIdGenerator.getGenerateDateTime(id));
System.out.println("Sequence2=" + snowflakeIdGenerator.getSequence2(id));
System.out.println("WorkerId2=" + snowflakeIdGenerator.getWorkerId2(id));
System.out.println("DataCenterId2=" + snowflakeIdGenerator.getDataCenterId2(id));
System.out.println("GenerateDateTime2=" + snowflakeIdGenerator.getGenerateDateTime2(id));
}
}
流程图
时钟回拨问题
机器本地时钟可能会因为各种原因发生不准的情况，网络中提供了NTP服务来做时间校准，做校准的时候就会发生时钟的跳跃或者回拨的问题。
时钟回拨问题，可通过手动调整电脑上的时钟进行模拟测试。
因为雪花算法强依赖机器时钟，所以难以避免受到时钟回拨的影响，有可能产生ID重复。原标准实现代码中是直接抛异常，短暂停止对外服务，这样在实际生产中是无法忍受的。所以要尽量避免时钟回拨带来的影响，解决思路有两个：
一：不依赖机器时钟驱动，就没时钟回拨的事儿了。即定义一个初始时间戳，在初始时间戳上自增，不跟随机器时钟增加。时间戳何时自增？当序列号增加到最大时，此时时间戳+1，这样完全不会浪费序列号，适合流量较大的场景，如果流量较小，可能出现时间断层滞后
二：依然依赖机器时钟，如果时钟回拨范围较小，如几十毫秒，可以等到时间回到正常；如果流量不大，前几百毫秒或者几秒的序列号肯定有剩余，可以将前几百毫秒或者几秒的序列号缓存起来，如果发生时钟回拨，就从缓存中获取序列号自增
参考：https://blog.csdn.net/weixin_36586120/article/details/118018414
短ID生成器
优劣势
- 在高并发情况下并发度没有雪花算法并发度高
- 在突发情况下会比雪花算法并发度高
- id短，可以用int类型接收，避免前端long值精度丢失问题(js无法接收64位长度的数字)
思路
雪花算法思路：
- 雪花算法使用当前时间戳 + 机器ID + 自增位来保证不重复
- 不同毫秒生成id 时间戳 + 机器ID 即可保证不重复
- 同一毫秒生成ID时对自增位 + 1 操作，如果达到自增位上线，则休眠1毫秒来保证不重复
短ID生成思路：
- 雪花算法每次生成ID都是拿当前毫秒值进行生成， 当前生成的ID和上一次生成的ID可能已经过去一段时间了， 呐这段时间没有进行生成过ID，这一段时间的时间戳是不是就浪费了呢？能不能把它利用起来呢？ （借用过去的时间）
- ID 使用 (“自增”时间戳 + 机器ID) 保证不重复
- 时间戳本身很长，用int是装不下的，因为 机器生成的 时间戳是从 1900年(貌似吧，忘了)到现在时间的一个long型ID，那我们让时间戳不用1900年开始算，比如 2000 年开始到现在的时间戳就可以用int装下，这样就解决了时间戳 int 类型装不下的问题(还要给机器ID预留空间哦)
Java实现
package com.bjjb.bidding.common.manager.id.impl;
import com.bjjb.bidding.common.manager.id.IdGenerator;
import lombok.SneakyThrows;
import org.apache.commons.lang3.StringUtils;
import org.springframework.stereotype.Component;
import org.springframework.util.StopWatch;
import java.lang.management.ManagementFactory;
import java.util.HashSet;
@Component
public class TianAiShortIdGenerator {
public static final String ID = "ShortId";
/**
* 时间起始标记点，作为基准，一般取系统的最近时间（一旦确定不能变动）.
*/
private final long twepoch = 1622601218000L;
/** 上一个最后的时间戳. */
private long lastTimeMillis;
/** 机器ID. */
private long workerId;
public TianAiShortIdGenerator() {
// 一般取系统最近一次启动的时间
lastTimeMillis = System.currentTimeMillis();
// 这里设置最大 5个bit的机器ID， 也就是最多可以部署 32台服务器，可以根据业务变动
workerId = getMaxWorkerId(5);
}
/**
* 获取机器ID ,copy至mybatis-plus
* @param maxWorkerId
* @return
*/
protected static long getMaxWorkerId(long maxWorkerId) {
StringBuilder mpid = new StringBuilder();
String name = ManagementFactory.getRuntimeMXBean().getName();
if (StringUtils.isNotBlank(name)) {
/*
* GET jvmPid
*/
mpid.append(name.split("@")[0]);
}
/*
* MAC + PID 的 hashcode 获取16个低位
*/
return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}
@SneakyThrows
public synchronized int doGenerateId() {
long currentTimeMillis;
while (lastTimeMillis + 1 >= (currentTimeMillis = System.currentTimeMillis())) {
Thread.sleep(1);
lastTimeMillis = currentTimeMillis - 1;
}
lastTimeMillis++;
int res = Math.abs((int) ((lastTimeMillis - twepoch) << 5 | workerId));
return res;
}
public static void main(String[] args) {
// 这个测试不准确，只是个例子，它的并发度取决于 最近一次生成ID的时间和当前时间的差值
// 过去浪费的时间越多，它的并发度越强
// 也就是说 System.currentTimeMillis() - lastTimeMillis = 这个值越大，并发越强
TianAiShortIdGenerator shortIdGenerator = new TianAiShortIdGenerator();
HashSet<Integer> hashSet = new HashSet<>(1000000);
StopWatch stopWatch = new StopWatch();
stopWatch.start();
for (int i = 0; i < 1000; i++) {
hashSet.add(shortIdGenerator.doGenerateId());
}
stopWatch.stop();
int size = hashSet.size();
System.out.println(hashSet.iterator().next());
System.out.println("耗时:" + stopWatch.getTotalTimeMillis() + ",添加数量:" + size);
}
}
引用：https://blog.csdn.net/qq_26083119/article/details/117463381