SnowFlake雪花算法源码分析&灵活改造，常见分布式ID生成解决方案

带着几个关注点去研读源码

1. 算法设计的整体逻辑是什么，核心点是什么？
2. 算法是如何达到高并发的？
3. 算法的高并发能力极限？
4. 既然是生成ID，那么生成的可用量有多大，可用的时间为多少，ID的存储方式？
5. 算法是否有缺陷，如何避免或者改进？
6. 算法是否可自由拓展或改造，以契合当前项目需求？

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

在研读源码后对一开始几个问题的回答：

1. 算法以时间戳为生成源作为生成ID核心，使用一个Long整型来记录ID，并对Long的64位进行分割设计为：保留位+时间戳+机房+机器+序列号，其中时间戳为核心，序列号进一步提高了并发量；
2. 算法的高并发主要是毫秒级的时间戳和每毫秒的序列化计数，调整这两个值即可调整并发量；
3. 单台机器并发理论值为：4096 * 1000 = 4096000ID/秒；
4. 时间维度上，算法的可用时间由41个bit时间戳锁定了，约69年，极限总量约为：69 * 365 * 24 * 3600 * 4096000 * 1024
5. 机器的时钟回拨可能导致生成重复ID，需要额外手段保持时钟同步；
6. 算法的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。
即：

• 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生成本身的拆分–分布式思想；雪花算法因其本身的效率已经足够高，而其唯一缺陷是时钟回拨问题，使用前需要关注解决。