雪花算法(snowflake)实现分布式ID的生成

r囧r小猫 2024-04-17 14:29 63阅读 0赞

先分析一下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NIWUxPR08_size_16_color_FFFFFF_t_70][]

雪花算法简单描述：  
一、 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0，是符号位，始终为0，不可用。  
二、41位的时间序列，精确到毫秒级，41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)  
得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L \* 60 \* 60 \* 24 \* 365) = 69  
三、10位的机器标识，10位的长度最多支持部署1024个节点。*包括5位datacenterId和5位workerId*  
四、12位的计数序列号，序列号即一系列的自增id，可以支持同一节点同一毫秒生成多个ID序号，12位的计数序列号支持每个节点每毫秒产生4096个ID序号。

其中，10位器标识符一般是5位IDC+5位machine编号，唯一确定一台机器。

*SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，*

*下面是代码实现：*

public class SnowFlakeGenerator {
    
        // 起始的时间戳    
        private final static long START_STAMP = 1566886337L;
    /**
         * 可分配的位数
         */
        private final static int REMAIN_BIT_NUM = 22;
    
        /**
         * idc编号
         */
        private long idcId;
    
        /**
         * 机器编号
         */
        private long machineId;
    
        /**
         * 当前序列号
         */
        private long sequence = 0L;
    
        /**
         * 上次最新时间戳
         */
        private long lastStamp = -1L;
      
        //idc偏移量：一次计算出，避免重复计算    
        private int idcBitLeftOffset;
       
        //机器id偏移量：一次计算出，避免重复计算     
        private int machineBitLeftOffset;
       
        // 时间戳偏移量：一次计算出，避免重复计算    
        private int timestampBitLeftOffset;
       
        // 最大序列值：一次计算出，避免重复计算     
        private int maxSequenceValue;
    
        public static class Factory {
            //每一部分占用位数的默认值
            private final static int DEFAULT_MACHINE_BIT_NUM = 5;   //机器标识占用的位数
            private final static int DEFAULT_IDC_BIT_NUM = 5;//数据中心占用的位数
    
            private int machineBitNum;
            private int idcBitNum;
    
            public Factory() {
                this.idcBitNum = DEFAULT_IDC_BIT_NUM;
                this.machineBitNum = DEFAULT_MACHINE_BIT_NUM;
            }
    
            public Factory(int machineBitNum, int idcBitNum) {
                this.idcBitNum = idcBitNum;
                this.machineBitNum = machineBitNum;
            }
    
            public SnowFlakeGenerator create(long idcId, long machineId) {
                return new SnowFlakeGenerator(this.idcBitNum, this.machineBitNum, idcId, machineId);
            }
        }
    
      
        private SnowFlakeGenerator(int idcBitNum, int machineBitNum, long idcId, long machineId) {
            int sequenceBitNum = REMAIN_BIT_NUM - idcBitNum - machineBitNum;
    
            if (idcBitNum <= 0 || machineBitNum <= 0 || sequenceBitNum <= 0) {
                throw new IllegalArgumentException("error bit number");
            }
    
            this.maxSequenceValue = ~(-1 << sequenceBitNum);
    
            machineBitLeftOffset = sequenceBitNum;  
            idcBitLeftOffset=machineBitNum+sequenceBitNum;
            timestampBitLeftOffset = idcBitNum + machineBitNum + sequenceBitNum;
    
            this.idcId = idcId;
            this.machineId = machineId;
        }
    
        
          // 产生下一个ID
            public long nextId() {
            long currentStamp = getTimeMill();
            if (currentStamp < lastStamp) {
                throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastStamp - currentStamp));
            }
    
            //新的毫秒，序列从0开始，否则序列自增
            if (currentStamp == lastStamp) {
                sequence = (sequence + 1) & this.maxSequenceValue;
                if (sequence == 0L) {
                    //Twitter源代码中的逻辑是循环，直到下一个毫秒
                    currentStamp = tilNextMillis();
    //                throw new IllegalStateException("sequence over flow");
                }
            } else {
                sequence = 0L;
            }
    
            lastStamp = currentStamp;
    
            return (currentStamp - START_STAMP) << timestampBitLeftOffset | idcId << idcBitLeftOffset | machineId << machineBitLeftOffset | sequence;
        }
    
        private long getTimeMill() {
            return System.currentTimeMillis();
        }
    
        private long tilNextMillis() {
            long timestamp = getTimeMill();
            while (timestamp <= lastStamp) {
                timestamp = getTimeMill();
            }
            return timestamp;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NIWUxPR08_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/2dd345c49dc543c088d910305ae79a47.jpg