带着几个关注点去研读源码
- 算法设计的整体逻辑是什么，核心点是什么？
- 算法是如何达到高并发的？
- 算法的高并发能力极限？
- 既然是生成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 apiSystem.currentTimeMillis();查阅资料，一堆的复制粘贴文章说直接这样调用api在高并发时有性能问题，搜索关键词："System.currentTimeMillis()的性能问题"，主要的两个链接:
- os层和cpu层的效率分析 id="本人在实际项目中的改造案例">本人在实际项目中的改造案例
项目中的原有的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。
即：- 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> * 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(10)).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生成本身的拆分--分布式思想；雪花算法因其本身的效率已经足够高，而其唯一缺陷是时钟回拨问题，使用前需要关注解决。
原文转载：http://www.shaoqun.com/a/750803.html
cares：https://www.ikjzd.com/w/1302
pat：https://www.ikjzd.com/w/1079
带着几个关注点去研读源码算法设计的整体逻辑是什么，核心点是什么？算法是如何达到高并发的？算法的高并发能力极限？既然是生成ID，那么生成的可用量有多大，可用的时间为多少，ID的存储方式？算法是否有缺陷，如何避免或者改进？算法是否可自由拓展或改造，以契合当前项目需求？SnowFlake源码：/***Twitter_Snowflake*SnowFlake的结构(每部分用-分开):*0-000000000
tradekey：https://www.ikjzd.com/w/1630
epc：https://www.ikjzd.com/w/488
modcloth：https://www.ikjzd.com/w/1271
全球降息大幕拉开？中国央行或不会立即跟进降息：https://www.ikjzd.com/home/103030
邮件写作技巧：https://www.ikjzd.com/tl/107477
亚马逊欲购买印度零售公司Future Retail10%的股份：https://www.ikjzd.com/home/104410
没有评论:
发表评论