常见 ID 生成算法
分布式系统中，经常需要使用 ID 作为数据唯一标识，这时数据库自增就无法满足需求。常见的解决方案有：
- UUID：实现简单，但 32 位无序字符串，性能较差
- 分库起始步长：严重依赖数据库
- SnowFlake：无依赖，64 bit 标识，有序递增
SnowFlake
SnowFlake 是 Twitter 公司所采用的的一种算法，目的是在分布式系统中生成全局唯一且趋势递增的 ID。
SnowFlake 生成的 ID 一共可分为 4 部分：
- 符号位
1 bit，始终为 0； - 时间戳
41 bit，精确到毫秒，总共可容纳约 69 年的时间； - 工作机器 ID
10 bit，启动高 5 bit 是数据中心 ID（datacenterId），低 5 bit 是工作节点 ID（workerId），最多可以容纳 1024 个节点； - 序列号
12 bit，同一毫秒同一节点多次执行该算法，从 0 开始依次递增，对多可以累加至 4095；
同一毫秒内可生成全剧唯一 ID 数量：1024 * 4096 = 4194304。
代码实现
import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.concurrent.TimeUnit;
public class SnowFlakeUtils {
private static final int SERIAL_BIT = 12;
private static final int DATA_CENTER_BIT = 5;
private static final int WORK_BIT = 5;
private static final int TIME_STAMP_BIT = 41;
/**
* 对比时间点 2019-05-20 时间戳
*/
private static long timePoint = LocalDateTime.of(2019, 5, 20, 0, 0, 0).toInstant(ZoneOffset.of("+8")).toEpochMilli();
/**
* 1 bit: 符号位
*/
private static long flag = 0;
/**
* 41 bit: 时间戳（毫秒）
*/
private static long lastTimeStamp = -1L;
/**
* 5 bit: 工作机器 ID
*/
private static long dataCenterId = 1;
/**
* 5 bit: 工作机器 ID
*/
private static long workId = 1;
/**
* 12 bit: 序列号
*/
private static long serial = 0;
/**
* 序列号 mask，防止溢出
*/
private static final long SERIAL_MASK = ~(-1L << SERIAL_BIT);
public static synchronized long uniqueId() {
long currentTimeStamp = System.currentTimeMillis() - timePoint;
if (lastTimeStamp == currentTimeStamp) {
// 同一毫秒，序列号递增
long temp = (serial + 1) & SERIAL_MASK;
if (temp == 0) {
// 当前毫秒内序列已满，重新获取
sleep();
return uniqueId();
}
serial = temp;
} else {
lastTimeStamp = currentTimeStamp;
serial = 0L;
}
return serial
| (workId << SERIAL_BIT)
| (dataCenterId << SERIAL_BIT + WORK_BIT)
| (lastTimeStamp << (SERIAL_BIT + WORK_BIT + DATA_CENTER_BIT))
| (flag << (SERIAL_BIT + WORK_BIT + DATA_CENTER_BIT + TIME_STAMP_BIT));
}
private static void sleep() {
try {
TimeUnit.MILLISECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
注意序列号生成防止溢出，使用了 SERIAL_MASK，当序列值当前毫秒已经使用满时，手动休眠 1 毫秒后重复获取即可。
