树叶算法

2615字约9分钟

2025-03-07

世界上没有两片相同的树叶

自从雪花算法公开发布以来，各个厂家均对其作了一些优化和定制，但核心思想没有变，发展到今天，作为分布式ID，应该具有以下特点

唯一性：ID这个词本身就代表了唯一性，强制等级S 有序性：如果是使用B+树作为底层数据库，保证有序性对性能有极大好处，除非特定业务，否则强制等级为A 吞吐量/性能：如果作为大型系统的分布式ID生成算法，是要求极高的，但对绝大部分中小型公司，吞吐量并不会成为系统瓶颈，强制等级B 稳定性：ID生成为基础服务，稳定性要求极高，强制等级S 自治性：没有外部依赖，强制等级A 可用性：不用说，强制等级S 适应性：强制等级A 存储空间：强制等级B

这里我发明了一种SnowflakeId的Plus版本，规避缺点满足要求

应该说雪花算法满足了大部分公司的要求，但是还是存在一些缺陷：

原版雪花算法通过10bit的机器ID保证唯一性，也就是1024台机器，应该说1024这个能满足几乎所有企业的要求，但是如果发生时钟回拨就会产生重复ID 在很多方案里，这里会禁止发号，但是会导致服务不可用，违反了可用性和唯一性
由于采用了低位占用了10+12bit，所有雪花算法的值通常会很大，导致很容易就超过53bit导致JavaScript无法识别，必须转化为字符串
对于大部分公司来讲，其实用不到1024台机器，所以10bit的有点儿浪费
12bit的序号位，可保证409.6W的并发量，应该说，推特都够用，大部分公司肯定也足够了，会有一点儿浪费
雪花算法的机器ID是需要主动去设置的，如果不去管理，实际上就是0，不仅会浪费10bit的机器位，还会有重复的风险
雪花算法的12bit位，如果采用序号，会导致尾部很多0，如果采用随机号，则存在重复风险，且会导致单调递增被破坏
大部分公司优化雪花算法的方法就是采用引入第三方依赖，引入依赖确实能克服以上种种缺点，但是会导致他的自治性降低，同时也会带来更高的复杂性

针对以上问题，我提出了我的优化思路：

把10bit的机器位压缩到8bit，也就是最多容纳256台机器，因为对于大部分中小企业来说，微服务的规模不会超过这个数，且C类IP地址最多可分配254个地址，可用机器所在的IP地址，解决了需要人工设置机器ID的烦恼
对于时钟回拨，采用临时分配机器ID为0这样一个标志位来代替，并发出日志警告提醒。当恢复后重新设置为原来的机器ID，解决重号和服务不可用风险
低位采用4bit，可保证单机1.6W/S的并发量，对于中小公司足够使用
用一个最大长度为16的包含[0-15]数字的有序队列，去发号，用完则重新初始化，可解决尾部始终为0和重复风险
完全去掉第三方依赖，确保即使第三方依赖挂掉，也能保证发号
总共53bit，号小，足够使用69年（几乎接近人类平均寿命，不会有系统使用这么长时间的），前端JavaScript不用格式化为字符串，非常友好
53bit并不是强制要求，实际可用为63bit，也就是说可以用71489年，那时候地球都毁灭了吧

针对上述优化点，我们来给这个算法打分（这个算法主要针对中小型公司）

唯一性：S

只有两种例外，其一，当局域网内多台机器发生时钟回拨时，会有重号风险（因为机器ID都设置为0），其二：当局域网内多台机器拿不到局域网IP地址，机器ID被设置为255，会有重号风险

当然这种概率极低，因为当前都是使用云计算厂商提供的云服务，他们的软硬件设施都保证了时钟回拨的可能性很小（除非你自己手欠），而且还需要多台同时发生时钟回拨，概率极低。41位毫秒级的时间戳和4位随机的序号也能进一步降低这个几率

拿不到局域网IP地址，这时说明网络配置错误，或者本身已处于离线状态，这时服务本身已不可用，数据根本进不到数据库，何况还要同时发生，概率同样极低

有序性：S

41位的时间戳来保证

吞吐量/性能：S

对于中小型企业单机1.6W/S的并发足以，而且现如今都是每台服务器的配置不高，通过多台服务去支持，这个ID生成算法的整体并发性能为409.6W/S，和单机的雪花算法相当

稳定性：S

单机算法生成非常稳定

自治性：S

没有外部依赖

适应性：S

没有弹性收缩的能力，对于大部分类雪花算法，都会固定以保证统一，而却前面也说了，对于中小公司不会有瓶颈，根本不需要适应性

而且本算法可自由调节位数，可设置机器ID，高度可定制

存储空间：S

53bit的数字，占用64bit空间，优于UUUD等字符ID

这是专为中小型企业而设计的算法。各方面几乎完美，使用起来也极为方便，即使唯一需要动手设置位C类IP地址也不做强制要求，因为即使不改，那么机器ID发生重复的概率极低

即使重复了，毫秒级别的时间戳和16位的随机数也能进一步降低几率，中小型企业的并发本来就小，这个概率无限低

最后，如果觉得41：8：4的配比不满足要求，可自行设定

比如说我觉得咱系统最多能用10多年，那么可以设置为39：8：6，tips：40是34年，39是17年，38是8年比如说咱们系统也就几台机器（自己指定IP），那么可以设置为41：5：7 或者说我觉得34年足够满足软件的整个生命周期了，而且我想提高下并发的承载，那么可以设置为40：5：8

下面则是实现代码

package icu.congee.qs.core.utils;

// 导入必要的Java类
import java.net.InetAddress;
import java.net.UnknownHostException;
import java.time.Instant;
import java.util.ArrayDeque;
import java.util.Deque;

// Leaf算法的雪花ID生成器实现类
public class SnowflakeIdGenerator {
    private final int timestampBits; // 时间戳占用的位数
    private final int machineIdBits; // 机器ID占用的位数
    private final int sequenceBits; // 序列号占用的位数

    private final long epoch; // 自定义纪元时间戳
    private final long maxMachineId; // 最大机器ID值
    private final long maxRandom; // 最大随机序列号
    private final long maxTimestamp; // 最大时间戳值
    private final long lastMachineId = -1; // 上一次使用的机器ID，初始化为-1
    private long machineId; // 当前机器ID
    private long lastTimestamp = -1L; // 上一次生成ID的时间戳，初始化为-1
    private Deque<Long> deque; // 存储随机序列号的双端队列

    // 带参数的构造函数
    public SnowflakeIdGenerator(int timestampBits, int machineIdBits, int sequenceBits, Instant customEpoch) {
        if (timestampBits + machineIdBits + sequenceBits >= 64) { // 检查总位数是否超过64位
            throw new IllegalArgumentException("最大为63位的正整数");
        }
        this.timestampBits = timestampBits; // 初始化时间戳位数
        this.machineIdBits = machineIdBits; // 初始化机器ID位数
        this.sequenceBits = sequenceBits; // 初始化序列号位数

        this.epoch = customEpoch.toEpochMilli(); // 设置自定义纪元时间
        this.maxMachineId = (1L << machineIdBits) - 1; // 计算最大机器ID
        this.maxRandom = (1L << sequenceBits) - 1; // 计算最大随机序列号
        this.maxTimestamp = (1L << timestampBits) - 1; // 计算最大时间戳

        this.machineId = getLocalMachineId(); // 获取并设置当前机器ID
        this.deque = generateRandomDeque(); // 生成随机序列号队列
    }

    // 默认构造函数
    public SnowflakeIdGenerator() {
        this(41, 8, 4, Instant.parse("2024-01-01T00:00:00.00Z")); // 使用默认参数调用带参构造函数
    }

    // 生成随机序列号队列
    private Deque<Long> generateRandomDeque() {
        Deque<Long> deque = new ArrayDeque<>(); // 创建新的双端队列
        for (long i = 0; i <= maxRandom; i++) { // 填充队列，从0到最大随机数
            deque.add(i);
        }
        return deque; // 返回生成的随机序列号队列
    }

    // 同步方法生成下一个唯一ID
    public synchronized long nextId() {
        long timestamp = currentTimestamp(); // 获取当前时间戳
        if (timestamp < lastTimestamp) { // 检查是否发生时间回拨
            machineId = 0; // 检测到回拨，将机器ID设置为0
        } else if (timestamp > lastTimestamp && machineId == 0) {
            machineId = lastMachineId; // 恢复正常，重置机器ID
        }
        checkAndResetMachineId(); // 检查并重置机器ID

        if (timestamp == lastTimestamp) { // 如果时间戳相同
            if (deque.isEmpty()) { // 检查随机数队列是否为空
                timestamp = waitForNextMillis(lastTimestamp); // 等待到下一毫秒
            }
        } 
        lastTimestamp = timestamp; // 更新上一次时间戳
        

        long seq = deque.isEmpty() ? generateRandomDeque().pop() : deque.pop(); // 从队列中取出一个随机数
        return (timestamp << (machineIdBits + sequenceBits)) | (machineId << sequenceBits) | seq; // 组合生成最终ID
    }

    // 获取基于自定义纪元的当前时间戳
    private long currentTimestamp() {
        return System.currentTimeMillis() - epoch; // 返回当前时间与起始时间的差值
    }

    // 基于IPv4地址获取本地机器ID
    private long getLocalMachineId() {
        try {
            InetAddress ip = InetAddress.getLocalHost(); // 获取本地主机的IP地址
            byte[] ipAddress = ip.getAddress(); // 获取IP地址的字节数组
            long ipNum = 0;
            for (byte b : ipAddress) { // 将IP地址转换为长整型
                ipNum = (ipNum << 8) | (b & 0xFF);
            }
            return ipNum % maxMachineId; // 返回IP地址对最大机器ID取模的结果
        } catch (UnknownHostException e) {
            return maxMachineId; // 如果无法解析IP，则返回最大机器ID
        }
    }

    // 检查机器ID并在必要时重置
    private void checkAndResetMachineId() {
        if (machineId == maxMachineId) { // 如果当前机器ID达到最大值，则重新获取
            machineId = getLocalMachineId();
        }
    }

    // 等待直到下一毫秒
    private long waitForNextMillis(long lastTimestamp) {
        long timestamp = currentTimestamp();
        while (timestamp <= lastTimestamp) {
            timestamp = currentTimestamp();
        }
        return timestamp;
    }
}