带着几个关注点去研读源码
- 算法设计的整体逻辑是什么，核心点是什么？
- 算法是如何达到高并发的？
- 算法的高并发能力极限？
- 既然是生成ID，那么生成的可用量有多大，可用的时间为多少，ID的存储方式？
- 算法是否有缺陷，如何避免或者改进？
- 算法是否可自由拓展或改造，以契合当前项目需求？
SnowFlake源码：
/**
* Twitter_Snowflake
* SnowFlake的结构(每部分用-分开):
* 0-00000000000000000000000000000000000000000-00000-00000-000000000000
* 第一部分：
* 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，ID要是正数，最高位是0
* 第二部分：
* 41位毫秒数，不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 自定义起始时间截)，
* 自定义起始时间戳即人为指定的算法起始时间，当前时间即生成ID时的时间戳
* 41位的时间截，可以使用约69年， (1L << 41) / (365 * 24 * 3600 * 1000）≈ 69
* 第三、四部分：
* 10位的数据机器位，可以部署在1024(1L<<10)个节点，包括5位datacenterId（机房）和5位workerId（机器号）
* 第五部分：
* 12位序列，每毫秒可生成序列号数，共4096(1L<<12)个ID序号
* 以上5部分总64bit，即需要一个Long整型来记录
* SnowFlake的优点：
* - 整体按时间自增排序
* - Long整型ID，存储高效，检索高效
* - 分布式系统内无ID碰撞（各分区由datacenterId和workerId来区分）
* - 生成效率高，占用系统资源少，理论每秒可生成1000 * 4096 = 4096000个
* SnowFlake的缺点：
* - 时钟回拨问题，尤其在高并发中，时钟回拨可能会生产出重复的ID
*/
public class SnowFlakeIdWorker {
/**
* 指定起始时间戳 (2021-05-21 00:00:00)
*/
private final long twepoch = 1621440000000L;
/**
* 数据中心/机房标识所占bit位数
*/
private final long datacenterIdBits = 5L;
/**
* 机器标识所占bit位数
*/
private final long workerIdBits = 5L;
/**
* 每毫秒下的序列号所占bit位数
*/
private final long sequenceBits = 12L;
/**
* 数据中心掩码，即最大支持32个机房
*/
private final long maxDatacenterId = ~(-1L << datacenterIdBits);
/**
* 机器掩码，即最大支持32个机器
*/
private final long maxWorkerId = ~(-1L << workerIdBits);
/**
* 每毫秒序列号的掩码
*/
private final long sequenceMask = ~(-1L << sequenceBits);
/**
* 机器ID表示的bit在long中位置，需要左移的位数（12）
*/
private final long workerIdShift = sequenceBits;
/**
* 数据中心ID表示的bit在long中的位置，需要左移的位数(12+5)
*/
private final long datacenterIdShift = sequenceBits + workerIdBits;
/**
* 时间截部分需要左移的位数(5+5+12)
*/
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/**
* 机器ID(0~31)
*/
private long workerId;
/**
* 数据中心ID(0~31)
*/
private long datacenterId;
/**
* 每毫秒内序列(0~4095)
*/
private long sequence = 0L;
/**
* 最后一次生成ID时的时间截
*/
private long lastTimestamp = -1L;
/**
* 构造函数
*
* @param workerId 机器ID (0~31)
* @param datacenterId 数据中心ID (0~31)
*/
public SnowFlakeIdWorker(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
/**
* 获得下一个ID，synchronized同步的，此处必须同步
*
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
// 若当前时间戳小于最后一次生成ID时的时间戳，说明系统时钟回退过，此时无法保证ID的唯一性，算法抛异常退出
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// 若当前时间戳等于最后一次生成ID时的时间戳（同一毫秒内），则进行序列号累加
if (lastTimestamp == timestamp) {
// 此操作可获得的最大值是4095，最小值是0，在溢出时为0
sequence = (sequence + 1) & sequenceMask;
// 毫秒内序列溢出
if (sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 若当前时间戳大于最后一次生成ID时的时间戳，则序列号需要重置到0
sequence = 0L;
}
// 更新记录本次时间戳
lastTimestamp = timestamp;
// 位运算，获得最终的ID并返回
return ((timestamp - twepoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| sequence;
}
/**
* 阻塞到下一个毫秒，直到获得新的时间戳
*
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒为单位的当前时间戳
*
* @return 当前时间(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
/**
* 测试
*/
public static void main(String[] args) {
SnowFlakeIdWorker idWorker = new SnowFlakeIdWorker(0, 0);
for (int i = 0; i < 10; i++) {
long id = idWorker.nextId();
System.out.println(id);
}
}
}
源码中的注释分析已经很详尽，再贴一张直观的图看看：
- 1bit保留，最高位有符号标识，Long为正数
- 41bit为时间戳差值，可用时长约69年
- 5bit用于标识机房，取值：0~31
- 5bit用于标识机器，取值：0~31
- 12bit用于区分同一毫秒内请求的序列号，取值：0~4095
在研读源码后对一开始几个问题的回答：
- 算法以时间戳为生成源作为生成ID核心，使用一个Long整型来记录ID，并对Long的64位进行分割设计为：保留位+时间戳+机房+机器+序列号，其中时间戳为核心，序列号进一步提高了并发量；
- 算法的高并发主要是毫秒级的时间戳和每毫秒的序列化计数，调整这两个值即可调整并发量；
- 单台机器并发理论值为：4096 * 1000 = 4096000ID/秒；
- 时间维度上，算法的可用时间由41个bit时间戳锁定了，约69年，极限总量约为：69 * 365 * 24 * 3600 * 4096000 * 1024
- 机器的时钟回拨可能导致生成重复ID，需要额外手段保持时钟同步；
- 算法的5个部分中时间戳是核心，时间戳bit可增减，其他部分可合并或重新分割为更多或更少的部分，且不一定非要用一个Long整型来生成ID，在保留时间戳这个核心点之外的部分都可以自由设计，以满足项目的需求；
对于获取毫秒时间的效率问题：
// 直接调用原生Java api
System.currentTimeMillis();
查阅资料，一堆的复制粘贴文章说直接这样调用api在高并发时有性能问题，搜索关键词：“System.currentTimeMillis()的性能问题”，主要的两个链接:
- os层和cpu层的效率分析：http://pzemtsov.github.io/2017/07/23/the-slow-currenttimemillis.html
- Oracle相关问题，及官方回复：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8185891
简要概括下Orcale官方的观点：此问题级别太低，且超出了jvm范围，慢是os或cpu本身的问题，不在jvm生态内，所以不是bug，问题定级为低，不予处理。
既然官方这样回复，说明直接调用api的效率在Java本身生态系统内是没有问题的，那么直接调用即可。
本人在实际项目中的改造案例
项目中的原有的id生成逻辑是这样的：
- 记录一个起始long值，作为计数值，每次获取的时候+1，该值每次记录到文件，系统启动时读取上次记录的值；
- 把long处理为byte数组，并进行位操作乱序（类似hashcode操作）；
- 获取当前日期，年月日每个部分为一个byte；
- 把两个byte数组前后拼接并转为16进制的字符串，总32长度；
旧有逻辑也不知道谁写的… 反正记录到文件这个就挺不靠谱，还要多个文件管理，文件不见了又是个问题，现在需求要求不要依赖文件，重新写一个生成ID效率高且仍然是16进制的32长度的字符串；
基于SnowFlake改造后的ID生成方案：
- 保留时间自增的核心；
- 因为最终要生成16进制的字符串，所以不再局限Long，实际设计为32长度16进制共128bit；
- 考虑一个4位IP地址需要32bit记录；
- 整个ID设计为：32bit记录k8s的主机IP + 32bit记录pod的IP + 52bit时间戳 + 12bit序列号
简单讲就是，保留原有的生成时间戳和序列号的部分，共占64bit，剩余64bit用来记录两个IP地址（暂未从项目找到其他固定可用标识了），总计128bit。
即：
- 128bit = 32bit + 32bit + 52bit + 12bit = 8hex + 8hex + 13hex + 3hex = 32hex
改造后的源码：
/**
* @author zhoujie
* @date 2021/5/17 下午5:10
* @description: 基于SnowFlake改造的32长度hex进制的ID生成方案
* 总128bit长度，32hex长度：
* <p>
* 32bit记录k8s的主机IP + 32bit记录pod的IP + 52bit时间戳 + 12bit序列号
* <p>
* 128bit = 32bit + 32bit + 52bit +12bit = 8hex + 8hex + 13hex + 3hex = 32hex
*/
public class SnowFlakeIdUtil {
/**
* 指定起始时间戳 (2021-05-21 00:00:00)
*/
private static final long twepoch = 1420041600000L;
/**
* 每毫秒下的序列号所占bit位数
*/
private static final long sequenceBits = 12L;
/**
* 每毫秒序列号的掩码
*/
private static final long sequenceMask = ~(-1L << sequenceBits);
/**
* 每毫秒内序列(0~4095)
*/
private static long sequence = 0L;
/**
* 最后一次生成ID时的时间截
*/
private static long lastTimestamp = -1L;
/**
* HOST_IP
*/
private static final String HOST_IP = "222.222.222.222";
/**
* POD_IP
*/
private static final String POD_IP = "111.111.111.111";
/**
* ip的处理后16进制表示的部分
*/
private static String IP_HEX_PART = null;
/**
* 静态工具类，构造器私有化
*/
private SnowFlakeIdUtil() {
}
/**
* 获得下一个ID，synchronized同步的，此处必须同步
*
* @return SnowflakeId
*/
public static synchronized long nextId() {
long timestamp = timeGen();
// 若当前时间戳小于最后一次生成ID时的时间戳，说明系统时钟回退过，此时无法保证ID的唯一性，算法抛异常退出
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// 若当前时间戳等于最后一次生成ID时的时间戳（同一毫秒内），则进行序列号累加
if (lastTimestamp == timestamp) {
// 此操作可获得的最大值是4095，最小值是0，在溢出时为0
sequence = (sequence + 1) & sequenceMask;
// 毫秒内序列溢出
if (sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 若当前时间戳大于最后一次生成ID时的时间戳，则序列号需要重置到0
sequence = 0L;
}
// 更新记录本次时间戳
lastTimestamp = timestamp;
// 位运算，此处拼接时间戳和序列号一并返回是为了效率，后面处理时还是需要拆开各自处理
return (timestamp - twepoch) << sequenceBits | sequence;
}
/**
* @author zhoujie
* @date 2021/5/17 下午5:15
* @description: 改造后的生成ID方案，生成32长度16进制的ID：
* <p>
* host_ip + pod_ip + 时间戳 + 序列号
* <p>
* 8hex + 8hex + 13hex +3hex
*/
private static String getMsgId() {
long nextId = nextId();
long seq = nextId & sequenceMask;
long unixTime = nextId >> sequenceBits;
StringBuilder msgIdBuffer = new StringBuilder(32);
// 末3位hex为序列号
msgIdBuffer.append(Long.toHexString(seq));
while (msgIdBuffer.length() < 3) {
msgIdBuffer.insert(0, "0");
}
// 中间13位hex为时间戳
msgIdBuffer.insert(0, Long.toHexString(unixTime));
while (msgIdBuffer.length() < 16) {
msgIdBuffer.insert(0, "0");
}
// IP为环境信息，只需要初始化一次
if (IP_HEX_PART == null) {
IP_HEX_PART = ipToHexString(HOST_IP) + ipToHexString(POD_IP);
}
// 前16位为环境相关的两个IP地址
return msgIdBuffer.insert(0, IP_HEX_PART).toString().toUpperCase();
}
/**
* @return java.lang.String
* @author zhoujie
* @date 2021/5/17 下午5:25
* @param: ip
* @description: 把ip转为16进制字符串表示
*/
private static String ipToHexString(String ip) {
if (ip == null) {
return "00000000";
}
String[] ipPort = ip.split("\\.");
if (ipPort.length < 4) {
return "00000000";
}
StringBuilder ipBuffer = new StringBuilder(8);
for (String s : ipPort) {
String s1 = Integer.toHexString(Integer.parseInt(s));
ipBuffer.append(s1.length() > 1 ? s1 : "0" + s1);
}
return ipBuffer.toString();
}
/**
* @return java.lang.String
* @author zhoujie
* @date 2021/5/17 下午5:36
* @param: msgId
* @description: 反解析msg获取信息
*/
private static Map<String, String> parseMsgIdInfo(String msgId) {
if (msgId == null) {
return null;
}
int len = msgId.length();
if (len != 32) {
return null;
}
// 项目用的json对象存储并返回json字符串对象，简化import，此处使用map，意会即可
HashMap<String, String> msgIdInfo = new HashMap<>();
msgIdInfo.put("msgId", msgId);
msgIdInfo.put("host_ip", hexStrToIp(msgId.substring(0, 8)));
msgIdInfo.put("pod_ip", hexStrToIp(msgId.substring(8, 16)));
msgIdInfo.put("sequence", new BigInteger(msgId.substring(30), 16).toString());
long timestamp = Long.parseLong(msgId.substring(16, 29), 16) + twepoch;
msgIdInfo.put("dateTime", LocalDateTime.ofInstant(Instant.ofEpochMilli(timestamp), ZoneId.systemDefault()).toString());
return msgIdInfo;
}
/**
* @return java.lang.String
* @author zhoujie
* @date 2021/5/18 下午3:19
* @param: hexIpStr
* @description: 把16进制的字符串ip转为常规显示
*/
private static String hexStrToIp(String hexIpStr) {
int step = 2;
StringBuilder ipBuffer = new StringBuilder(17);
for (int i = 0; i < hexIpStr.length(); i += step) {
String ipPart = hexIpStr.substring(i, i + step);
ipBuffer.append(new BigInteger(ipPart, 16).toString()).append(".");
}
ipBuffer.setLength(ipBuffer.length() - 1);
return ipBuffer.toString();
}
/**
* 阻塞到下一个毫秒，直到获得新的时间戳
*
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected static long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒为单位的当前时间戳
*
* @return 当前时间(毫秒)
*/
protected static long timeGen() {
return System.currentTimeMillis();
}
/**
* 测试
*/
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(SnowFlakeIdUtil.getMsgId());
}
String msgId = SnowFlakeIdUtil.getMsgId();
Map<String, String> stringStringMap = parseMsgIdInfo(msgId);
for (Map.Entry<String, String> entry : stringStringMap.entrySet()) {
System.out.println(entry.getKey() + "-" + entry.getValue());
}
}
}
改造后的问题：
- 原有生成是Long类型，现在是String类型，对数据库索引不友好，但当前项目用作记录多，暂不涉及搜索；
- 原有仅生成Long并返回，效率很高，现在在原有基础上增加了一些字符串的处理，对效率略有影响；
改造后生成的是数字字母字符串，所以UUID也能完成这个需求，但是UUID生成的是完全无意义字符，当前对SnowFlake的改造能携带有用信息，且在以后可以按需求再改造扩展。
其他分布式ID的解决方案及优劣分析
生成分布式ID的一些要求：
- 全局唯一：最基本要求；
- 高性能：低延迟，生成速度快，不能成为业务瓶颈；
- 高可用：99.99…%可用，9越多越好；
- 易接入：最好是插件式使用，与项目低耦合，易于后续替换/拓展；
- ID友好：一般最好是数字型ID且趋势递增，能更好贴合业务属性，利于项目开发；
常见分布式ID生成解决方案及优缺点：
UUID
优点：
- 简单，一行代码搞定，且能保证唯一性，效率很高；
缺点：
- 生成的字符无序无意义；
- 长度偏长，存储查询性能不好；
数据库ID
优点：
- 实现简单，ID单调递增，生成及查询速度快；
- 可设计为号段模式，降低压力；
缺点：
- 数据库本身性能将成为生成ID的性能上限；
- 数据库本身的可用性成为生成ID的可用性；
- 单机数据库能力有限，集群模式可一定程度提高能力，但缺点仍存在；
Redis生成ID
优点：
- Redis天然的单线程能保证线程安全，生产的ID全局唯一；
- Redis为内存数据库，效率能保证；
- 依赖于Redis的INCR命令，能高效实现自增ID；
- ID为数字型，数据库存储查询友好效率高；
缺点：
- 需要搭建维护额外的Redis生成ID系统，增加系统复杂度；
- 增加了Redis网络请求，占用网络资源，性能比本地生成要慢；
- Redis可能宕机，可用性也低于本地生成；
SnowFlake雪花算法
优点：
- 代码少且简单，无需额外依赖，本地生成；
- 生成效率高；
- Long型ID，趋势递增，对项目友好；
- 对Long的64bit分段设计，且可根据项目需求重新设计，可塑性高；
缺点：
- 强依赖时间的准确性，时钟回拨可能生成重复ID；
百度uid-generator，基于SonwFlake的二次开发
优点：
- 使用了Atom原子类计数替换了获取时间戳，解决了时钟回拨问题（正常回拨误差在毫秒级）；
- 序列号增加1bit到13bit，共8092个序列号，算是弥补毫秒到秒级的缺失；
- 使用RingBuffer缓存提前生成的ID，提高并发时抗压能力；
缺点：
- 原有时间戳被替换为秒级且使用的缓存，很早生成的ID可能很久之后才用到，其实问题不大；
美团Leaf，基于SnowFlake的二次开发
优点：
- 早期Leaf的号段+双buffer模式已经解决了大部分问题；
- 使用zk持久模式顺序生成workId，且本地缓存，启动时先从本地缓存恢复，没有时请求zk获取新的workId并缓存；
- 解决时钟回拨问题：在判断时间落后时等待2倍的落后差时间重新获取时间戳，以等待并重新尝试的方式解决正常NTP（Network Time Protocol）时间同步时的误差问题，若时间差太多或等待后时间差仍存在则抛异常终止，此时时钟落后问题需要人工介入解决；
- 初始序列号每次不是从0开始，而是nextInt(100)，避免0的情况过多，利于DB的分库分表；
缺点：
- 号段模式提供的ID可能是不连续的，buffer的存在使得系统的重启后存在ID的浪费；
滴滴TinyId
优点：
- 与美团的Leaf类似，采用号段的模式生成ID；
- 提供http和rest两种接入方式；
缺点：
- 号段模式提供的ID可能是不连续的，buffer的存在使得系统的重启后存在ID的浪费；
总结
综合以上的分析学习研究，当前分布式ID还是以SnowFlake雪花算法为模板，结合项目实际需求进行设计的方案为最优，大厂都是采用了号段模式或自我改造雪花算法的方案，号段模式可以说是对ID生成本身的拆分--分布式思想；雪花算法因其本身的效率已经足够高，而其唯一缺陷是时钟回拨问题，使用前需要关注解决。
