分布式ID——雪花算法

朱雀 2023-06-30 15:53 154阅读 0赞

### 背景 ###

随着现在业务量的越来越大，数据库的划分也变的越来越细，分库分表的理念也渐渐的落地，自增主键或者序列之类的主键id生成方式已经不再满足需求，所以分布式ID的生成就应运而生，总的来说就是生成规则更加负责，减少重复的概率。

### 一、雪花算法 ###

雪花算法的原始版本是[scala版][scala]，用于生成分布式ID（纯数字，时间顺序）,订单编号等。

> 自增ID：对于数据敏感场景不宜使用，且不适合于分布式场景。  
> GUID：采用无意义字符串，数据量增大时造成访问过慢，且不宜排序。

![format_png][]

**算法描述：**

*  最高位是符号位，始终为0，不可用。
 *  41位的时间序列，精确到毫秒级，41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。
 *  10位的机器标识，10位的长度最多支持部署1024个节点。
 *  12位的计数序列号，序列号即一系列的自增id，可以支持同一节点同一毫秒生成多个ID序号，12位的计数序列号支持每个节点每毫秒产生4096个ID序号。

###  二、时间部分 ###

时间部分的逻辑起始很简单，就是规定一个起始时间戳，然后用当前时间戳减去起始时间戳，这两个数的差就是我们要的结果，但是有一个问题如果系统的时间出错了怎么办，毕竟我们正常取的都是服务器的时间，所以需要校验

//如果当前时间小于上次ID生成的时间，说明系统回退过抛出异常
            if (now < LAST_TIME_STAMP) {
                log.info("系统时间异常，请检查！");
                throw new RuntimeException("系统时间异常！");
            }

### 三、机器信息部分 ###

机器信息，占10位。我们这里把机器信息分成两部分，一部分是数据中心id，占5位，一部分是机器id，占5位。这两个id可以在部署项目的时候根据不同的机器自定义不同的id，这样能人为的保障每个id都不同。jdk库中，有api可以获取本地机器的hostname和hostaddress，可以把hostname的信息作为数据中心id，把hostaddress的信息作为机器id，如何把两个字符串改为两个数字id呢？其实很简单。获取字符串的字节数组，然后把数组的每个数字相加，对节点数的最大值取余。因为都是5位，所以最大值是31，需要对32取余。那么雪花算法可以部署的机器总数就是32\*32=1024个，这是机器信息的限制。

private static int getDataId() {
            try {
                return getHostId(Inet4Address.getLocalHost().getHostName(), DATA_MAX_NUM);
            } catch (UnknownHostException e) {
                return new Random().nextInt(DATA_RANDOM);
            }
        }
    
        private static int getWorkId() {
            try {
                return getHostId(Inet4Address.getLocalHost().getHostAddress(), WORK_MAX_NUM);
            } catch (UnknownHostException e) {
                return new Random().nextInt(WORK_RANDOM);
            }
        }
    
    
        private static int getHostId(String str, int max) {
            byte[] bytes = str.getBytes();
            int sums = 0;
            for (int b : bytes) {
                sums += b;
            }
            return sums % (max + 1);
        }

### 四、毫秒内序列 ###

毫秒内的序列。什么意思呢？我们在生成时间部分获取时间戳的时候，使用 long now = System.currentTimeMillis(); 获取，是个毫秒级的时间戳，但是即使是这么短的时间，对于电脑来说也足够生成很多个id，所以很多id可能会在同一个毫秒内生成，也就是时间部分的数值一样。这个时候就要让同一个毫秒内生成的id加上数字序列标识，就是第三部分的序列。第三部分占的长度是12位，转成整数值就是4095，所以最后一部分的范围就是4095到0之间的数字。如果毫秒内访问的数量超过了这个限制怎么办？没法解决，只能强制等到下一毫秒再生产id。

### 五、实战 ###

上面的讲述我们基本可以写出方法了，但是考虑到多线程，我们需要加锁保证。下面是完整代码。

@Slf4j
    public class SnowflakeUtil {
        /**
         * 时间部分所占长度
         */
        private static final int TIME_LEN = 41;
        /**
         * 数据中心id所占长度
         */
        private static final int DATA_LEN = 5;
        /**
         * 机器id所占长度
         */
        private static final int WORK_LEN = 5;
        /**
         * 毫秒内序列所占长度
         */
        private static final int SEQ_LEN = 12;
        /**
         * 定义起始时间 2015-01-01 00:00:00
         */
        private static final long START_TIME = 1420041600000L;
        /**
         * 上次生成id的时间戳
         */
        private static long LAST_TIME_STAMP = -1L;
        /**
         * 时间部分向左移动的位数 22
         */
        private static final int TIME_LEFT_BIT = 64 - 1 - TIME_LEN;
        /**
         * 自动获取数据中心id（可以手动定义0-31之间的任意数）
         */
        private static final long DATA_ID = getDataId();
        /**
         * 自动获取机器id（可以手动定义0-31之间的任意数）
         */
        private static final long WORK_ID = getWorkId();
        /**
         * 数据中心id最大值 31
         */
        private static final int DATA_MAX_NUM = ~(-1 << DATA_LEN);
        /**
         * 机器id最大值 31
         */
        private static final int WORK_MAX_NUM = ~(-1 << WORK_LEN);
        /**
         * 随机获取数据中心id的参数 32
         */
        private static final int DATA_RANDOM = DATA_MAX_NUM + 1;
        /**
         * 随机获取机器id的参数 32
         */
        private static final int WORK_RANDOM = WORK_MAX_NUM + 1;
        /**
         * 数据中心id左位移数 17
         */
        private static final int DATA_LEFT_BIT = TIME_LEFT_BIT - DATA_LEN;
        /**
         * 机器id左位移数 12
         */
        private static final int WORK_LEFT_BIT = DATA_LEFT_BIT - WORK_LEN;
        /**
         * 上一次毫秒内序列值
         */
        private static long LAST_SEQ = 0L;
        /**
         * 毫秒内序列的最大值 4095
         */
        private static final long SEQ_MAX_NUM = ~(-1 << SEQ_LEN);
        private final Object object = new Object();
    
        public synchronized static long getId() {
            long now = System.currentTimeMillis();
    
            //如果当前时间小于上次ID生成的时间，说明系统回退过抛出异常
            if (now < LAST_TIME_STAMP) {
                log.info("系统时间异常，请检查！");
                throw new RuntimeException("系统时间异常！");
            }
    
            if (now == LAST_TIME_STAMP) {
                LAST_SEQ = (LAST_SEQ + 1) & SEQ_MAX_NUM;
                if (LAST_SEQ == 0) {
                    now = nextMillis(LAST_TIME_STAMP);
                }
            } else {
                LAST_SEQ = 0;
            }
    
            LAST_TIME_STAMP = now;
    
            return ((now - START_TIME) << TIME_LEFT_BIT) | (DATA_ID << DATA_LEFT_BIT) | (WORK_ID << WORK_LEFT_BIT) | LAST_SEQ;
        }
    
    
        private static long nextMillis(Long lastMillis) {
            long now = System.currentTimeMillis();
            while (now <= lastMillis) {
                now = System.currentTimeMillis();
            }
            return now;
        }
    
        private static int getDataId() {
            try {
                return getHostId(Inet4Address.getLocalHost().getHostName(), DATA_MAX_NUM);
            } catch (UnknownHostException e) {
                return new Random().nextInt(DATA_RANDOM);
            }
        }
    
        private static int getWorkId() {
            try {
                return getHostId(Inet4Address.getLocalHost().getHostAddress(), WORK_MAX_NUM);
            } catch (UnknownHostException e) {
                return new Random().nextInt(WORK_RANDOM);
            }
        }
    
    
        private static int getHostId(String str, int max) {
            byte[] bytes = str.getBytes();
            int sums = 0;
            for (int b : bytes) {
                sums += b;
            }
            return sums % (max + 1);
        }
    
    
        public static void main(String[] args) {
    //        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    //        try {
    //            long time = dateFormat.parse("2015-01-01 00:00:00").getTime();
    //            System.out.println(time);
    //        } catch (ParseException e) {
    //            e.printStackTrace();
    //        }
    
    
            for (int i = 0; i <10 ; i++) {
                new Thread(new Runnable() {
                    @Override
                    public void run() {
                        System.out.println("-------------");
                        System.out.println(getId());
                    }
                }).start();
            }
    
        }
    }

学习专题：[雪花算法（07）雪花算法最终版][07]

[https://www.cnblogs.com/Hollson/p/9116218.html][https_www.cnblogs.com_Hollson_p_9116218.html]

[scala]: https://github.com/twitter/snowflake/releases/tag/snowflake-2010
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTM3NDIyLzIwMTgwNi8xMzc0MjItMjAxODA2MDEwMDU3MzczOTItMTk4MTE2NTk3My5qcGc?x-oss-process=image/format,png
[07]: https://www.cnblogs.com/guos/p/11357422.html
[https_www.cnblogs.com_Hollson_p_9116218.html]: https://www.cnblogs.com/Hollson/p/9116218.html