分布式唯一ID生成方式

青旅半醒 2023-10-03 11:48 19阅读 0赞

### Snowflake算法 ###

给每台机器分配一个唯一标识，然后通过时间戳+标识+自增实现全局唯一ID。

Snowflake 算法采用 41bit 毫秒时间戳，加上 10bit 机器ID，加上 12bit 序列号，理论上最多支持1024台机器每秒生成4096000个序列号。

### springBoot 整合自定义的雪花算法 ###

#### 1 配置pom文件 ####

# 雪花算法配置数据中心和机器编号，不同机器组合不能重复
    snowflake:
      datacenterId: 1
      machineId: 2

#### 2 编写配置文件 ####

SnowFlakeFactory.java

package com.un.framework.snowflack;
    
    import java.util.Map;
    import java.util.concurrent.ConcurrentHashMap;
    import java.util.concurrent.TimeUnit;
    import java.util.concurrent.locks.LockSupport;
    
    /**
     * 雪花算法，解决时间回拨问题
     * 整合业务，需要根据业务编号生成id
     *
     * @author shiye
     * @date 2020-05-27 15:41
     */
    public class SnowFlakeFactory {
        
    
        /**
         * 起始的时间戳
         * 2020-01-01 00:00:00  毫秒
         */
        private final static long START_STMP = 1577808000000L;
    
        /**
         * 每一部分占用的位数
         */
        private final static long SEQUENCE_BIT = 12; //序列号占用的位数
        private final static long MACHINE_BIT = 5;   //机器标识占用的位数
        private final static long DATACENTER_BIT = 5;//数据中心占用的位数
    
        /**
         * 每一部分的最大值
         * MAX_DATACENTER_NUM = 31
         * MAX_MACHINE_NUM = 31
         * MAX_SEQUENCE = 4095
         */
        private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
        private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
        private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    
        /**
         * 每一部分向左的位移
         */
        private final static long MACHINE_LEFT = SEQUENCE_BIT;
        private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
        private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
    
        private long datacenterId = 0;  //数据中心
        private long machineId = 0;     //机器标识
        private long sequence = 0L; //序列号
        private long lastStmp = -1L;//上一次时间戳
    
        /**
         * 最大容忍时间, 单位毫秒, 即如果时钟只是回拨了该变量指定的时间, 那么等待相应的时间即可;
         * 考虑到sequence服务的高性能, 这个值不易过大
         */
        private static final long MAX_BACKWARD_MS = 5;
    
        //最大扩展字段
        private long maxExtension = 2L;
        /**
         * 保留machineId和lastTimestamp, 以及备用machineId和其对应的lastTimestamp
         */
        private static Map<Long, Long> machineIdLastTimeMap = new ConcurrentHashMap<>();
    
        /**
         * 初始化数据中心位，和机器标识
         * 0 < datacenterId < MAX_DATACENTER_NUM 31
         * 0 < machineId < MAX_MACHINE_NUM 31
         *
         * @param datacenterId
         * @param machineId
         */
        public SnowFlakeFactory(long datacenterId, long machineId) {
        
            if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
        
                throw new IllegalArgumentException(" datacenterId 必须介于[0,31] ");
            }
            if (machineId > MAX_MACHINE_NUM || machineId < 0) {
        
                throw new IllegalArgumentException(" machineId 必须介于[0,31] ");
            }
            this.datacenterId = datacenterId;
            this.machineId = machineId;
            //初始化时间 machineIdLastTimeMap
            machineIdLastTimeMap.put(machineId, getNewstmp());
        }
    
        /**
         * 产生下一个ID
         *
         * @return
         */
        public synchronized String nextId(BRStyle brStyle) {
        
            //现存的扩展字段
            long extension = 0L;
            //获取当前时间毫秒数
            long currStmp = getNewstmp();
            //lastStmp = currStmp + 100;
            if (currStmp < lastStmp) {
        
                //throw new RuntimeException("时钟向后移动,拒绝生成id");
    
                // 如果时钟回拨在可接受范围内, 等待即可
                long offset = lastStmp - currStmp;
                //如果回拨时间不超过5毫秒，就等待相应的时间
                if (offset <= MAX_BACKWARD_MS) {
        
                    try {
        
                        //睡（lastTimestamp - currentTimestamp）ms让其追上
                        LockSupport.parkNanos(TimeUnit.MILLISECONDS.toNanos(offset));
    
                        currStmp = getNewstmp();
                        //如果时间还小于当前时间，那么利用扩展字段加1
                        //或者是采用抛异常并上报
                        if (currStmp < lastStmp) {
        
                            //扩展字段
                            extension += 1;
                            if (extension > maxExtension) {
        
                                //服务器时钟被调整了,ID生成器停止服务.
                                throw new RuntimeException(String.format("时钟向后移动。拒绝生成的id %d 毫秒", lastStmp - currStmp));
                            }
                        }
                    } catch (Exception e) {
        
                        e.printStackTrace();
                    }
                } else {
        
                    //扩展字段
                    extension += 1;
                    if (extension > maxExtension) {
        
                        //服务器时钟被调整了,ID生成器停止服务.
                        throw new RuntimeException(String.format("时钟向后移动，超出扩展位，拒绝生成的id %d 毫秒", lastStmp - currStmp));
                    }
                    //获取可以用的workid，对应的时间戳，必须大于当前时间戳
                    tryGenerateKeyOnBackup(currStmp);
                }
            }
    
            if (currStmp == lastStmp) {
        
                //相同毫秒内，序列号自增
                sequence = (sequence + 1) & MAX_SEQUENCE;
                //同一毫秒的序列数已经达到最大
                if (sequence == 0L) {
        
                    currStmp = getNextMill();
                }
            } else {
        
                //不同毫秒内，序列号置为0
                sequence = 0L;
            }
    
            lastStmp = currStmp;
    
            long id = (currStmp - START_STMP) << (TIMESTMP_LEFT - extension)   //时间戳部分
                    | datacenterId << DATACENTER_LEFT                       //数据中心部分
                    | machineId << MACHINE_LEFT                             //机器标识部分
                    | sequence;                                             //序列号部分
            //如果时间戳回拨就让时间少移动一位
            return brStyle.getCode() + id;
        }
    
        /**
         * 自旋锁获取当前时间戳
         *
         * @return
         */
        private long getNextMill() {
        
            long mill = getNewstmp();
            while (mill <= lastStmp) {
        
                mill = getNewstmp();
            }
            return mill;
        }
    
        /**
         * 获取当前时间毫秒数
         *
         * @return
         */
        private long getNewstmp() {
        
            return System.currentTimeMillis();
            //测试时间回拨
            //return 53501026489350000l;
        }
    
        /**
         * 尝试在machineId的备份machineId上生成
         * 核心优化代码在方法tryGenerateKeyOnBackup()中，BACKUP_COUNT即备份machineId数越多，
         * sequence服务避免时钟回拨影响的能力越强，但是可部署的sequence服务越少，
         * 设置BACKUP_COUNT为3，最多可以部署1024/(3+1)即256个sequence服务，完全够用，
         * 抗时钟回拨影响的能力也得到非常大的保障。
         *
         * @param currentMillis 当前时间
         */
        private long tryGenerateKeyOnBackup(long currentMillis) {
        
            // 遍历所有machineId(包括备用machineId, 查看哪些machineId可用)
            for (Map.Entry<Long, Long> entry : machineIdLastTimeMap.entrySet()) {
        
                this.machineId = entry.getKey();
                // 取得备用machineId的lastTime
                Long tempLastTime = entry.getValue();
                lastStmp = tempLastTime == null ? 0L : tempLastTime;
    
                // 如果找到了合适的machineId，返回合适的时间，
                if (lastStmp <= currentMillis) {
        
                    return lastStmp;
                }
            }
    
            // 如果所有machineId以及备用machineId都处于时钟回拨, 那么抛出异常
            throw new IllegalStateException("时钟在向后移动，当前时间是 " + currentMillis + " 毫秒，machineId映射 = " + machineIdLastTimeMap);
        }
    
    }

定义一个枚举，主要是为了为特定业务生成特定的id

package com.un.framework.snowflack;
    
    /**
     * @author shiye
     * @date 2020-05-27 15:46
     */
    public enum BRStyle {
        
        CO("CO", "社区模块"),
        ;
        private final String code;
        private final String info;
    
        BRStyle(String code, String info) {
        
            this.code = code;
            this.info = info;
        }
    
        public String getCode() {
        
            return code;
        }
    
        public String getInfo() {
        
            return info;
        }
    }

容器初始化的时候加载到内存中

package com.un.framework.snowflack;
    
    import org.springframework.boot.context.properties.ConfigurationProperties;
    import org.springframework.context.annotation.Bean;
    import org.springframework.context.annotation.Configuration;
    
    /**
     * @author shiye
     * @date 2020-05-27 15:54
     */
    @Configuration
    @ConfigurationProperties(prefix = "snowflake")
    public class IDGenderConfig {
        
    
        //数据中心[0,31] 配置文件中不配置就是0
        private long datacenterId;
    
        //机器标识[0,31] 配置文件中不配置就是0
        private long machineId;
    
        @Bean
        public SnowFlakeFactory getSnowFlakeFactory() {
        
            SnowFlakeFactory snowFlakeFactory = new SnowFlakeFactory(datacenterId,machineId);
            return snowFlakeFactory;
        }
    
        public long getDatacenterId() {
        
            return datacenterId;
        }
    
        public void setDatacenterId(long datacenterId) {
        
            this.datacenterId = datacenterId;
        }
    
        public long getMachineId() {
        
            return machineId;
        }
    
        public void setMachineId(long machineId) {
        
            this.machineId = machineId;
        }
    }

#### 3 测试 ####

package com.un.project.tool.snowflake;
    
    import com.un.framework.snowflack.BRStyle;
    import com.un.framework.snowflack.SnowFlakeFactory;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.web.bind.annotation.GetMapping;
    import org.springframework.web.bind.annotation.RequestMapping;
    import org.springframework.web.bind.annotation.RestController;
    
    import java.time.LocalDateTime;
    import java.util.*;
    import java.util.concurrent.ExecutionException;
    import java.util.concurrent.ExecutorService;
    import java.util.concurrent.Executors;
    import java.util.concurrent.Future;
    
    /**
     * @author shiye
     * @date 2020-05-27 16:04
     */
    @RestController
    @RequestMapping("/snowflake")
    public class SnowFlakeController {
        
    
        @Autowired
        private SnowFlakeFactory snowFlakeFactory;
    
        /**
         * 雪花算法测试
         *
         * @return
         */
        @GetMapping("/getCOID")
        public String genSnowFlake() {
        
            return snowFlakeFactory.nextId(BRStyle.CO);
        }
    
        /**
         * 批量生成id
         * 开始时间2020-05-27T17:01:34.176
         * 结束时间2020-05-27T17:01:34.463
         * 200000
         * 结论：300ms生成 20w个无重复的id
         * @return
         */
        @GetMapping("/batchCreateID")
        public Set batchCreateID() throws ExecutionException, InterruptedException {
        
            int count = 200000;
    
            System.out.println("开始生成id......");
            ExecutorService executor = Executors.newCachedThreadPool();
    
            List countList = new ArrayList();
            //测试生成20w个id
            for (int i = 0; i < 200000; i++) {
        
                countList.add(i);
            }
    
            //使用set测试是否有重复，结果没有任何重复
            Set list = Collections.synchronizedSet(new HashSet<>());
            System.out.println("开始时间" + LocalDateTime.now());
            countList.parallelStream().forEach((i) -> {
        
                Future<String> futureTask = executor.submit(() -> {
        
                    return snowFlakeFactory.nextId(BRStyle.CO);
                });
                String id = null;
                try {
        
                    id = futureTask.get();
                } catch (Exception e2) {
        
                    e2.printStackTrace();
                }
                list.add(id);
            });
            System.out.println("结束时间" + LocalDateTime.now());
            System.out.println(list.size());
            return list;
        }
    }