分布式雪花算法ID

szh3117907958

1033人浏览 · 2025-09-17 15:15:11

szh3117907958 · 2025-09-17 15:15:11 发布

做分布式系统的订单 ID 时，最头疼的就是‘既要唯一，又要按时间有序’。我之前跟进的某个工业互联网项目里，架构师先排除了UUID，最终敲定了雪花算法。我询问之后恍然大悟。整理了这篇文章，来拆解雪花算法的原理、实现和落地细节。

为什么UUID不太合适？

首先，我们知道UUID长度是36位，转化成二进制的十六位数表示实际是128位。而雪花ID是64位的二进制长度，比UUID要短得多。但我觉得尤为重要的是UUID一般是无序的，而雪花算法相对来说是有序的。

这时候就有小伙伴儿问了，为啥有序会比无序要好呢？

首先有序最核心的优势是极大优化数据库的存储性能。几乎所有的主流数据库(如MySQL, PostgreSQL等)主键索引默认是B+树结构，而B+树的索引插入对于有序插入效率极高，而无需插入会导致大量性能损耗。(数据库的存储结构可以看我的另一篇关于MySQL的文章)

其次就是提高缓存查询效率。我们知道很多缓存(如Redis)存储是按照键值对存储的。当我们面临“查询近1小时内的订单的时候”，我们可以利用雪花ID直接查询where id > 起始时间戳对应的ID and id < 终止时间戳对应的ID 得到查询结果(这里不懂的可以往下看，会有对应的解释)。

雪花算法的结构

上述图片是雪花算法64位二进制的基本组成，主要包含下列部分：

不使用：1bit, 0正1负，一般固定为0；

41位毫秒级时间戳：表示时间(ms级)，可用2^41 ms大约70年

序列号：分为5位工作机器ID和5位数据中心ID，最多可部署2的(5+5)次方个节点

12位递增序列号：在统一毫秒内，序列号固定时，序列号递增，最多可有4096个序列号。就是说1ms最左右4096个ID生成。

【注】：雪花算法的长度可以根据自己的使用情况来变换，比如希望时间更长久，就可以多增加毫秒级时间戳；希望部署更多节点，就可以将序列号增加更多长度(同样，后边我会带大家看一个示例)。

可能遇见的问题

我们通过雪花算法的结构能看到它的唯一性主要是由时间戳，序列号以及递增序列号决定的。其中我们在给递增序列号的时候都是原子递增，不会出现回退。这里考虑的主要是序列号和时间戳的问题。

1. 时间戳：有人会问了，时间戳怎么会出问题呢？这里就不得不提“时钟回拨”的概念了。我们常使用的Java中的有关时间的API主要依赖的是操作系统的时钟，当操作系统的时钟被手动等原因修改的时候，就可能导致时间从“较晚时间”倒退到“较早时间”。这样假设我们之前生成了时间戳为x的序列号为y的，序列递增号为z的雪花算法，组合起来就是xyz。由于现在发生时钟回拨，现在的时间(x+m)就可能回退到事前的x，那么这时候生成的算法id就可能和他重复了。(这里其实可以发现，不单单是之前时间戳x的递增序列号可能会重复，x到x+m之间的其实都会重复).

那么这一时刻又有老铁问了：兄弟，兄弟，我明白时间戳这一回事儿了，但是序列号是怎么回事儿呢？别急，往下看。

2. 序列号：理想情况下序列号都是不会出现错误。但是当运维人员复制配置文件，忘记修改节点ID；又或者是没有统一的节点ID注册中心，各节点使用的是hash自主生成，就可能导致哈希碰撞造成节点重复。

解决方案

对于上边的两个问题，我们当然有解决方案啦(后续的代码示例也会用到)。

1. 首先最简单的就是时间戳，我们可以定义一个lastTimestamp表示上次记录的时间戳，然后每次获取当前时间戳的时候我们可以比较currentTimestamp与lastTimestamp，如果前者大于后者，那就是发生时钟回拨了，就得提示报错处理了。

2. 序列号问题怎么解决呢？我经过学习之后发现使用动态分配实现方案比较合适。拿Redis举例，当我们服务启动的时候可以去申请标识位，申请之后就更新为下一个可用的。

这里就有聪明的小伙伴儿问了；“那我是不是该考虑ID是全局唯一还是服务内唯一？”为了避免单点问题，我们这里采用的是服务内唯一。（注：全局唯一造成的单点问题就是，所有的微服务都来这个节点申请ID，当这个节点突然出现问题，那么所有服务都不能申请ID了）

那么如何实现动态分配方案呢？

通过上边我们得知，我们需要生成的是工作机器ID和数据中心ID。所以我们要在redis中存储的也是这俩。我先给出一个我的大概思路图，然后再给大家讲解：

首先我们肯定是原子操作的，所以用lua脚本。

由于我们是要复用之前的dataCenterID和workID,而非每次创建，所以需要保存，每次访问需要判断之前是否创建过。

接下来因为我们的dataCenterID和workID2^5个，所以需要判断是否达到最多，当workID达到最多值时，便自增dataCenterID.

知道dataCenterID达到31并且workID也达到31，这时候就循环了。

这里需要说明一下，因为我们定义的是10位标识位，所以最多有1024个节点。当达到临界条件的时候，虽然也可以一直保持31-31，但是这样ID重复概率会蛮大的。保持循环能减少这种概率。

举例应用

看了之前的一些知识点，可能大家还有一些存疑的地方。那么我们就举个例子来看一下吧。

本次示例以订单ID为例，代码中有说明，大家可以参照之前的说明自行观察。

public class IdGenerator {

    // 起始时间戳：2025年9月17日 00:00:00 的毫秒数
    private static final long START_TIMESTAMP = 1758067200000L;
    
    // 节点ID所占的位数
    private static final int NODE_BITS = 5;
    
    // 序列号所占的位数（改为12位）
    private static final int SEQUENCE_BITS = 12;

    // 节点ID
    private final long nodeId;
    
    // 上次生成ID的时间戳
    private long lastTimestamp = -1L;
    
    // 当前序列号
    private long sequence = 0L;

    public IdGenerator(long nodeId) {
        // 验证节点ID是否在有效范围内
        long maxNodeId = (1L << NODE_BITS) - 1;
        if (nodeId < 0 || nodeId > maxNodeId) {
            throw new IllegalArgumentException("节点ID超出范围，允许的范围是 0 到 " + maxNodeId);
        }
        this.nodeId = nodeId;
    }

    public synchronized long generateId() {
        long timestamp = getCurrentTimestamp();
        
        // 如果当前时间戳小于上次生成ID的时间戳，说明系统时钟回退，抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("系统时钟回退，拒绝生成ID。时间差: " + (lastTimestamp - timestamp) + " 毫秒");
        }
        
        // 如果是同一时间戳，则递增序列号
        if (timestamp == lastTimestamp) {
            // 序列号的最大值
            long maxSequence = (1L << SEQUENCE_BITS) - 1;
            sequence = (sequence + 1) & maxSequence;
            
            // 如果序列号溢出，则等待到下一个毫秒
            if (sequence == 0) {
                timestamp = waitUntilNextMillis(lastTimestamp);
            }
        } else {
            // 如果是新的时间戳，重置序列号
            sequence = 0L;
        }
        
        // 更新上次生成ID的时间戳
        lastTimestamp = timestamp;
        
        // 组合生成ID：时间戳 << (节点位数 + 序列号位数) | 节点ID << 序列号位数 | 序列号
        return (timestamp << (NODE_BITS + SEQUENCE_BITS)) 
                | (nodeId << SEQUENCE_BITS) 
                | sequence;
    }

    // 获取当前时间戳（相对于起始时间）
    private long getCurrentTimestamp() {
        return System.currentTimeMillis() - START_TIMESTAMP;
    }

    // 等待到下一个毫秒
    private long waitUntilNextMillis(long lastTimestamp) {
        long timestamp = getCurrentTimestamp();
        while (timestamp <= lastTimestamp) {
            timestamp = getCurrentTimestamp();
        }
        return timestamp;
    }
}

@RequiredArgsConstructor
private final StringRedisTemplate stringRedisTemplate;
    private final RedissonClient redissonClient;
    private static IdGenerator ID_GENERATOR;
    
    // 从IdGenerator类中引入节点位数常量
    private static final int NODE_BITS = IdGenerator.NODE_BITS;

    public static String generateId(long userId) {
        return ID_GENERATOR.generateId() + String.valueOf(userId % 1000000);
    }

    @PostConstruct
    public void initIdGenerator() throws Exception {
        String LOCK_KEY = "id_generator_lock_key";
        RLock lock = redissonClient.getLock(LOCK_KEY);
        lock.lock();
        try {
            String ID_GENERATOR_KEY = "id_generator_config";
            // 为空置0
            long incremented = Optional.ofNullable(
                stringRedisTemplate.opsForValue().increment(ID_GENERATOR_KEY)
            ).orElse(0L);
            
            // 节点最大数量根据节点位数计算得出
            int NODE_MAX = (1 << NODE_BITS) - 1;
            if (incremented > NODE_MAX) {
                incremented = 0;
                stringRedisTemplate.opsForValue().set(ID_GENERATOR_KEY, "0");
            }
            ID_GENERATOR = new IdGenerator(incremented);
        } finally {
            lock.unlock();
        }
    }