当前位置：首页 > article >正文

高性能分布式全局ID生成器-雪花算法实现

article 2025/2/11 15:20:59

概述

1.定义

一种分布式系统下用来生成全局唯一 ID 的工具

2.特点

唯一性，满足优惠券需要唯一的 ID 标识用于核销
高可用，随时能够生成正确的 ID
高性能，生成 ID 的速度很快，每台机器 400w/s
递增性，生成的 ID 是逐渐变大的，有利于数据库形成索引
安全性，生成的 ID 无明显规律，可以避免间接泄露信息
生成量大，可满足优惠券订单数据量大的需求

3.ID组成部分

代码实现

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author LiJianhong
 * @Title 雪花算法实现
 * @date 2025/2/7
 */
public class SnowflakeIdGenerator {

    /**
     * 基准纪元值：2025-01-01 08:00:00
     */
    private final long epoch = 1735689600000L;


    /**
     * 锁
     * */
    private Lock lock = new ReentrantLock();


    // 机器ID
    private final long workerId;
    // 机器ID的最大bit位长度
    private final long workerIdBits = 5L;
    // 最大的机器ID值，十进制数为为31
    private final long maxWorkerId = ~ (-1L << workerIdBits);


    // 数据中心ID
    private final long datacenterId;
    // 数据中心ID的最大bit位长度
    private final long datacenterIdBits = 5L;
    // 最大的数据中心ID值，十进制数为为31
    private final long maxDatacenterId = ~ (-1L << datacenterIdBits);


    // 自增序列号
    private long sequence = 0;
    // 序列号的最大bit位长度
    private final long sequenceBits = 12L;
    // 机器ID需要左移的位数12
    private final long workerIdShift = sequenceBits;
    // 数据中心ID需要左移的位数 = 12 + 5
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    // 时间戳需要左移的位数 = 12 + 5 + 5
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits ;
    // 序列号的掩码，十进制数为4095
    private final long sequenceMask = ~(-1L << sequenceBits);
    //最新时间戳快照
    private long lastTimestamp = -1L;
    // 时钟回拨最大容忍度，超过则抛异常
    private final long maxBackwardTime = 1000L;
    //
    private final long minBackwardTime = 100L;


    public SnowflakeIdGenerator(long workerId, long datacenterId) {
        this.workerId = workerId;
        this.datacenterId = datacenterId;
        checkArgs();
    }

    public long nextId() {
        lock.lock();
        try {
            long timestamp = timeGen();
            // 时钟回拨处理
            if (timestamp < lastTimestamp) {
                handleClockBackward(timestamp);
            }

            if (lastTimestamp == timestamp) {
                //如果自增值达到最大值，则等待至下一毫秒
                sequence = (sequence + 1) & sequenceMask;
                if(sequence == 0){
                    timestamp = untilNextMillis(lastTimestamp);
                }
            } else {
                sequence = 0;
            }

            // 保存当前时间戳，作为方法下次被调用的上一个时间戳的快照
            lastTimestamp = timestamp;

            return ((timestamp - epoch) << timestampLeftShift)
                    | (datacenterId << datacenterIdShift)
                    | (workerId << workerIdShift)
                    | sequence;
        } finally {
            lock.unlock();
        }
    }

    private void checkArgs() {
        if (!(0 <= workerId && workerId <= maxWorkerId)) {
            throw new IllegalArgumentException("worker id must be in [0,31]");
        }
        if (!(0 <= datacenterId && datacenterId <= maxDatacenterId)) {
            throw new IllegalArgumentException("data center id must be in [0,31]");
        }
    }

    private void handleClockBackward(long timestamp) {
        long backstep = lastTimestamp - timestamp;
        if (backstep > maxBackwardTime) {
            throw new ClockBackwardException("Clock moved backwards. Refusing to generate id for " + backstep + " milliseconds");
        }
        // 使用回拨容忍度，增加回拨窗口
        if (backstep > minBackwardTime) {
            timestamp = untilNextMillis(lastTimestamp);
        }
    }


    private long untilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    // 时钟回拨异常
    static class ClockBackwardException extends RuntimeException {
        public ClockBackwardException(String message) {
            super(message);
        }
    } 

}

测试：

public static void main(String[] args) throws InterruptedException {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(23, 17);
        int size = 10000;
        Map<Long,Long> idMap = new ConcurrentHashMap<>();
        CountDownLatch latch = new CountDownLatch(size);           // 定义一个工具类,统计线程执行300次task的进度
        long start0 = System.currentTimeMillis();
        for(int i = 0; i < size; i ++) {
            new Thread(()->{
                long id = idGenerator.nextId();
                idMap.putIfAbsent(id, id);
                latch.countDown();
            }).start();
        }
        latch.await();
        System.out.println("并发测试：并发线程数："+size+"，生成id数量："+idMap.size()+ "，耗时："+(System.currentTimeMillis()-start0)+" ms");

        //压测该算法每秒生成id个数
        long start = System.currentTimeMillis();
        int count = 0;
        while(true){
            long id = idGenerator.nextId();
            long end = System.currentTimeMillis();
            if((end-start)>1000){
                break;
            }
            count ++;
        }
        System.out.println("性能测试：每秒生成id个数："+count );
    }

输出：

并发测试：并发线程数：10000，生成id数量：10000，耗时：729 ms
性能测试：每秒生成id个数：4094779

Process finished with exit code 0

结论：

线程安全&分布式ID不重复：通过并发测试，10000个线程同时并发访问，生成了10000个不同的id，说明id生成是线程安全的，且id无重复。

高效性：理论上，本算法在单台服务器上最多可以生成1000 * 4096 = 4096000 / s，通过本次性能测试可以看出，分布式ID生成速率约为400w/s，值得注意的是，这仅仅是单台服务器的每秒生成率，而分布式集群的每个服务器都能达到该速率，根据算法入参workerId、datacenterId组合，可以算出最多能集群32×32=1024台机器，可通过调整集群机器数来缓解高并发生成ID的问题。

查看全文

http://www.kler.cn/a/539239.html