【分布式】分布式ID-CSDN博客

前言

分布式场景下一张表可能分散到多个数据结点上。因此需要一些分布式ID的解决方案。

分布式ID需要有几个特点

• 全局唯一必要 在多个库的主键放在一起也不会重复
• 有序必要 避免频繁触发索引重建
• 信息安全ID连续可以根据订单编号计算一天的单量造成信息泄露
• 包含时间戳能够快速根据ID得知生成时间

下面几种方案按推荐顺序排序越推荐使用越靠前。

一、雪花算法snowflake

64 位的 long 类型的唯一 id

1. 组成

11位不用

带符号整数第1位是符号位正数是0ID一般为正数此位不用。

241位毫秒级时间戳

41位存储当前时间截 – 开始时间截得到的差值可以表示$2^{41}$个毫秒的值转化成单位年则是:$\frac{2^{41}}{1000\ast 60\ast 60\ast 24\ast 365}=69年$

注开始时间截由程序指定一般是id生成器开始使用的时间设置好后避免更改。依赖服务器时间服务器时钟回拨时可能会生成重复 id。

310位机器ID

生成ID的服务可以部署在1024台机器上

412位序列号
能够表示4096个序列号。

因此某一毫秒同一台机器最多能生成4096个序号。理论上单机QPS最大为4096*1000=409.6w/s

2. 优缺点

优点

• ID不重复用时间戳+机器+序号生成不重复ID
• 性能高在内存中生成
• 有序

缺点

依赖服务器时间存在时钟回拨的问题。

3. 时钟回拨怎么解决

时钟回拨可能产生重复ID进而影响关联系统。

a. 时钟回拨

什么是时钟回拨 服务器上的时间倒退回之前的时间

哪些情况造成时钟回拨

• 人为修改服务器时间
• 时钟同步后由于机器之间时间不同可能产生时钟回拨

b. 解决方案

算法中会记录当前服务上次生成ID的最后时间只需要保证我下次生成ID的时间大于上次最后时间即可。根据回拨后时间距离上次生成最后时间大小可以有不同的解决方案。

• 相差0~100ms 等待直至当前时间超过上次最后生活时间
• 相差100ms~1s采用等待方式可能导致接口超时。可以记录已生成ID的最大ID在这个基础上++。预留扩展位在扩展位上增加。回拨后又回拨可能有问题
• 相差1s~5s采用最大ID增加的方式时间过长可能导致范围溢出。可以生成ID服务响应异常由调用方例如基于Ribbon调用其他生成ID服务。
• 相差超过5s采用Ribbon循环调用的方式下次访问到时钟回拨的服务可能还没达到上次生成最后时间浪费时间。可以让超过5s的服务主动下线并通知运维人工介入等待时钟正常后再重启。

4. 项目中如何使用

时钟回拨的处理逻辑在nextId()里的if (timestamp < lastTimestamp) 逻辑下。这里直接抛出异常。

public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (2020-01-01) */
    private final long twepoch = 1577808000000L;

    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;

    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;

    /** 支持的最大机器id结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大数据标识id结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;

    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 数据标识id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 时间截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** 生成序列的掩码这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作机器ID(0~31) */
    private long workerId;

    /** 数据中心ID(0~31) */
    private long datacenterId;

    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public  SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        //如果是同一时间生成的则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);

        for (int i = 0; i < 100; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
}

二、基于Redis

三、基于Zookeeper

四、号段模式

数据库中保存号段表每次从数据库获取一个号段范围由服务在内存中自增生成ID直到达到号段范围再去获取。

id	业务类型	最大可用ID	号段长度	版本号
1	xxx	2000	1000	0

update 表 set 最大可用ID = 3000, version = version + 1 where version = 0 and biz_type = xxx

采用乐观锁的方式避免长时间锁表。

优点

• ID有序递增
• 对数据库压力比较小

缺点

• 存在安全问题用ID可以判断数据量
• 存在单点问题集群实现困难

五、指定步长的自增ID

多主集群模式下表主键设置自增ID多节点之间会有重复ID。需要采用指定初始值的自增步长
举例两台数据库AB。A初始值和步长为1,2B初始值和步长为2,2。两张表生成的主键分别为
A1,3,5,7…
B2,4,6,8…

设置方法

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

优点

• 简单、解决单点问题

缺点

• 扩容困难

六、UUID

128位长的字符标识串由32个16进制数字组成用-连接共36个字符。如03425604-5462-11ee-80ad-80fa5b8732b1

生成算法与重复性

• 基于随机数不重复
• 基于MAC地址不重复
• 基于时间戳可能重复

作为分布式ID的优缺点

• 优点本地生成性能高无网络损耗
• 缺点
  • 无序造成索引重建入库性能差
  • 字符串长需要36字符

参考

• UUID会重复吗
• 雪花算法视频
• 9种分布式ID生成方式

六、扩展

• 百度UidGenerator
• 美团Leaf

总结

	优点	缺点
uuid	实现简单	连续性差作为主键每次新增数据都会触发索引重建。 分布式环境中可能重复
雪花算法	性能好有序	依赖服务器时间时钟回拨可能生成重复ID
号段模式
redis/zookeeper	Redis基于INCR 命令生成 分布式全局唯一id zookeeper一种通过节点,一种通过节点的版本号

基因算法