什么是雪花算法?

时间:2024-01-27 10:05:18

在集群高并发情况下如何保证分布式全局唯一ID生成?

 

分布式ID生成规则硬性要求:

1、全局唯一:不能出现重复的ID号,既然是唯一标识,这是最基本的要求。

2、趋势递增:MySQL中InnoDB引擎使用的是聚集索引。多数RDBMS使用Btree的数据结构来存储索引数据,在主键的选择上尽量选择有序的主键保证写入性能。

3、单调递增:保证下一个ID号一定大于上一个。

4、保证安全:ID号需要无规则性,不能让别人根据ID号猜出我们的信息和业务数据量,增加恶意用户扒取数据的难度。

5、含时间戳。

 

分布式ID生成可用性要求:

1、高可用:发布一个获取分布式ID的请求,服务器就要保证99.999%的情况下给创建一个全局唯一的分布式ID。

2、低延迟:发布一个获取分布式ID的请求,要快,急速。

3、高QPS:假如并发一口气10万个创建分布式ID请求同时杀过来,服务器要顶得住并且成功创建10万个分布式ID。

 

生成主键方案有哪些:

1、UUID。

2、数据库自增主键。

3、基于Redis生成全局ID策略。

4、雪花算法,Twitter的分布式自增ID算snowflake。

5、百度UidGenerator算法(基于雪花算法实现自定义时间戳)。

6、美团Leaf算法(依赖于数据库,ZK)。

 

1、UUID的优缺点:

优点:性能非常高,JDK自带本地生成,无网络消耗。

缺点:(1)只保证了唯一性,趋势递增。(2)无序,无法预测他的生成规则,不能生成递增有序的数字。(3)mysql官方推荐主键越短越好,UUID包含32个16位进制的字母数字,每一个都很长。(4)B+树索引的分裂。主键是包含索引的,mysql的索引是通过B+树来实现的,每一次新的UUID数据插入,为了查询优化,因为UUID是无序的,都会对索引底层的B+树进行修改。插入无序,不但会导致一些中间节点产生分裂,也会白白创造很多不饱和的节点,大大降低了数据库插入的性能。

 

2、数据库自增主键的优缺点:

优点:简单方便易用。

缺点:(1)要设置增长步长,系统水平扩展比较困难。(2)每次获取ID都得读写一次数据库,数据库压力大,非常影响性能,不符合分布式ID里低延迟和高QPS的规则。

 

3、基于Redis生成全局ID策略优缺点:

优点:满足分布式ID生成要求,并且已有成功落地案例。

缺点:(1)要设置增长步长,同时key一定要设置有效期。(2)为了一个分布式ID,要搞一个Redis集群,维护成本大。

 

4、雪花算法,Twitter的分布式自增ID算snowflake优缺点:

优点:(1)经测试snowflake每秒能生成26万个自增可排序的ID。(2)snowflake生成的ID结果是一个64bit大小的整数,为一个Long型 (转换成字符串后长度最多19)。(3)分布式系统内不会产生ID碰撞(datacenter和workerId作区分)并且效率高。

 

雪花算法的几个核心组成:

 

主要分为 5 个部分:

是 1 个 bit:0,这个是无意义的。
是 41 个 bit:表示的是时间戳。
是 10 个 bit:表示的是机房 id,0000000000,因为我传进去的就是0。
是 12 个 bit:表示的序号,就是某个机房某台机器上这一毫秒内同时生成的 id 的序号,0000 0000 0000。

1 bit,是无意义的:

  因为二进制里第一个 bit 为如果是 1,那么都是负数,但是我们生成的 id 都是正数,所以第一个 bit 统一都是 0。

41 bit:表示的是时间戳,单位是毫秒。

  41 bit 可以表示的数字多达 2^41 - 1,也就是可以标识 2 ^ 41 - 1 个毫秒值,换算成年就是表示 69 年的时间,从1970年到2039年9月7日。

10 bit:记录工作机器 id,代表的是这个服务最多可以部署在 2^10 台机器上,也就是 1024 台机器。

  但是 10 bit 里 5 个 bit 代表机房 id,5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房(32 个机房),每个机房里可以代表 2 ^ 5 个机器(32 台机器),这里可以随意拆分,比如拿出4位标识业务号,其他6位作为机器号。可以随意组合。

12 bit:这个是用来记录同一个毫秒内产生的不同 id。

  12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096,也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。也就是同一毫秒内同一台机器所生成的最大ID数量为4096

   简单来说,你的某个服务假设要生成一个全局唯一 id,那么就可以发送一个请求给部署了 SnowFlake 算法的系统,由这个 SnowFlake 算法系统来生成唯一 id。这个 SnowFlake 算法系统首先肯定是知道自己所在的机器号,(这里姑且讲10bit全部作为工作机器ID)接着 SnowFlake 算法系统接收到这个请求之后,首先就会用二进制位运算的方式生成一个 64 bit 的 long 型 id,64 个 bit 中的第一个 bit 是无意义的。接着用当前时间戳(单位到毫秒)占用41 个 bit,然后接着 10 个 bit 设置机器 id。最后再判断一下,当前这台机房的这台机器上这一毫秒内,这是第几个请求,给这次生成 id 的请求累加一个序号,作为最后的 12 个 bit。

 

雪花算法源码demo:

package com.example.demo;

import java.net.Inet4Address;
import java.net.UnknownHostException;
import java.util.Random;

public class SnowflakeIdWorker {

    /** 时间部分所占长度 */
    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 = 14200041600000L;
    /** 上次生成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);

    /**
     * 获取字符串S的字节数组,然后将数组的元素相加,对(max+1)取余
     * @param s 本地机器的hostName/hostAddress
     * @param max 机房/机器的id最大值
     * @return
     */
    private static int getHostId(String s, int max) {
        byte[] bytes = s.getBytes();
        int sums = 0;
        for (int b : bytes) {
            sums += b;
        }
        return sums % (max + 1);
    }

    /**
     * 根据 host address 取余, 发送异常就返回 0-31 之间的随机数
     * @return 机器ID
     */
    private static int getWorkId() {
        try {
            return getHostId(Inet4Address.getLocalHost().getHostAddress(), WORK_MAX_NUM);
        } catch (UnknownHostException e) {
            return new Random().nextInt(WORK_RANDOM);
        }
    }

    /**
     * 根据 host name 取余, 发送异常就返回 0-31 之间的随机数
     * @return 机房ID(数据中心ID)
     */
    private static int getDataId() {
        try{
            return getHostId(Inet4Address.getLocalHost().getHostName(), DATA_MAX_NUM);
        }catch(Exception e){
            return new Random().nextInt(DATA_RANDOM);
        }
    }

    /**
     * 获取下一不同毫秒的时间戳
     * @param lastMillis
     * @return 下一毫秒的时间戳
     */
    private static long nextMillis(long lastMillis) {
        long now = System.currentTimeMillis();
        while (now <= lastMillis) {
            now = System.currentTimeMillis();
        }
        return now;
    }

    /**
     * 核心算法,需要加锁保证并发安全
     * @return 返回唯一ID
     */
    public synchronized static long getUUID() {
        long now = System.currentTimeMillis();

        // 如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过,此时因抛出异常
        if (now < LAST_TIME_STAMP) {
            throw new RuntimeException(String.format("系统时间错误! %d 毫秒内拒绝生成雪花ID", START_TIME));
        }

        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;
        }

        // 上次生成ID的时间戳
        LAST_TIME_STAMP = now;

        return ((now - START_TIME) << TIME_LEFT_BIT | (DATA_ID << DATA_LEFT_BIT) | (WORK_ID << WORK_LEFT_BIT) | LAST_SEQ);
    }

    /**
     * 主函数测试
     * @param args
     */
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int num = 300000;
        for (int i = 0; i < num; i++) {
            System.out.println(getUUID());
        }
        long end = System.currentTimeMillis();

        System.out.println("共生成 " + num + " 个ID,用时 " + (end - start) + " 毫秒");
    }

}