双buffer分布式id生成器

双buffer分布式id生成器

关注我们获得更多内容

一

背景

在互联网行业很多业务场景都需要基于业务的id生成器,来生成各个业务数据的业务主键,很多传统企业或者小众业务会直接拿数据库的自增主键当做业务主键,当然这样能够解决大部分问题,但是在流量比较大的业务场景中,一般会考虑分库分表,那么自增主键的优势就荡然无存了,因为每张表的自增主键对于上层业务来说无法做到唯一性(或者说扩展性不好)。

那么我们就需要一种能够支持分布式唯一性的id生成规则(或者id生成器)来生成分布式唯一的业务主键。

二

常见ID生成规则

在介绍常见的id生成规则之前,我们简单看一下分布式id有哪些特性:

• 唯一性：确保生成的ID是全局唯一的,或者说至少是业务领域内唯一的。
• 有序递增性：确保生成的ID是对于某个用户或者业务模块是按一定的趋势有序递增的。
• 高可用性：确保任何时候都能正确的生成ID,或者说在业务可用期间保证ID生成规则可用。
• 带业务含义：ID里面包含时间或者业务属性，能够很直观的看出来是哪天、哪个业务领域的数据。

目前常用的分布式id生成方案主要有:uuid,数据库自增ID,Redis生成ID,雪花算法,UidGenerator,Leaf等等以及其他衍生方案,简单分析下每种方案的优缺点。

1：UUID

UUID是jdk自带的一个工具类,是结合机器的网卡、当地时间、一个随记数来生成一个唯一字符串。

• 优点：jdk自带,使用和生成简单易用，性能好
• 缺点：长度过长，且无序不可读，没有业务含义

2：数据库自增主键

使用数据库的自增策略，比如MySQL的auto_increment。并且可以使用多台数据库分别设置初始值和步长,生成不重复ID的策略来实现高可用,比如db1设置auto_increment_offset初始值1,auto_increment_increment步长2,db2设置auto_increment_offset2,,auto_increment_increment步长2,那么最终出现db1生成的id是1,3,5,7...,而db2生成的id是2,4,6,8...,从而实现了生成不重复ID的高可用。

• 优点：数据库生成的ID趋势递增,高可用实现方式简单
• 缺点：需要独立部署数据库,成本高,有性能瓶颈,添加机器要重新设置步长,n个db要设置步长是n,自增初始值是1到n

3：基于数据库批量生成id

由于单个获取自增id,在并发流量比较大的情况下对db压力比较大,可以采用批量获取多个id方式来提升性能,其原理是从db批量生成id,然后放到jvm缓存中,用完之后再从db申请。

• 优点：避免了每次生成ID都要访问数据库长时间占用数据库连接,从而提高了性能,也降低了db压力
• 缺点：存在单点故障,服务重启造成ID不连续

4：基于Redis生成id

redis的所有命令都是单线程,并提供incr和increby这样的自增原子命令,所以能保证生成的ID肯定是唯一有序的。

• 优点：不依赖于数据库,灵活方便,性能优于数据库;数字型ID天然排序。
• 缺点：如果系统中没有Redis,还需要引入新的组件,增加系统复杂度和外部依赖;对于基础服务层需要增加外部组件依赖并需要开发配置成本。

5：雪花算法

snowflake是Twitter开源的一种分布式id生成方案,组成部分如下图:

1位符号位基本不用;41位时间戳位,存储当前时间到开始时间的差值(开始时间可以理解为该策略上线可用时间),(1 << 41) / (1000x60x60x24x365) = 69年;10位机器数据位,这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 s个节点,超过这个数量,生成的ID就有可能会冲突;12位毫秒内序列位,这 12 位计数支持每个节点每毫秒（同一台机器，同一时刻）最多生成 1 << 12 = 4096个ID,如果毫秒内并发超过4096则等到下一时间单位生成。

• 优点：高性能,低延迟,时间趋势递增,一般不会造成ID碰撞
• 缺点：需要独立的开发和部署,强依赖于机器时钟,一旦机器时钟回拨,就可能出现id碰撞

还有一些其他的基于雪花算法思想的分布式id生成规则实现,比如百度的UidGenerator和美团的Leaf等等,这里不再做描述。

三

基于业务DB双buffer分布式id生成器

前面讲述了我们对id生成规则的诉求,以及目前比较常见的id生成方案,那么切合自己的业务特性,我们打算开发一款简单易用的分布式id生成器,需要满足一下诉求:

• 分布式唯一:并发生成保证全局或者业务领域唯一
• 不引入额外依赖:作为基础服务层,除了DB之外不想引入其他外部组件依赖
• 高性能:生成id速度快,并对底层DB压力可控
• 趋势递增和业务属性:生成的id从时间维度趋势递增,并且能够看出哪个业务领域哪个时间段生成的id

接下来我们的主角就要登场了,也就是基于业务DB的双buffer分布式id生成器,名字比较长,在展开介绍之前先介绍一下概念:

业务db:也就是我们业务领域底层数据存储层

双buffer:buffer是缓冲的意思,buffer里边存储的是待使用的候选id,双buffer是其中一个工作另外一个闲置备用,等到其中一个buffer使用完或者即将使用完的时候,填充另外一个buffer备用,然后用完的时候双方切换角色,长此以往下去。

1：业务架构

从图中我们可以看到,应用启动后,每台机器会生成两个buffer,buffer里边存储从业务db申请的id序列,当客户端请求生成id的时候应用层从命中的buffer缓存中获取id。

2：流程

在应用启动的时候,从db批量申请id并填充到buffer1中,然后设置buffer1为命中buffer;consumer请求生成id时,代理层从命中buffer获取可用buffer,并检查命中buffer是否达到扩容位点和切换buffer位点,在达到扩容位点时(80%)通过事件模式通知扩容buffer2(闲置buffer),如果buffer1(命中buffer)中id用完则触发命中buffer自动切换,此时buffer2变成命中buffer,buffer1变成闲置buffer,然后循环这个逻辑。

3：具体实现分析

我们先看一下核心类ProxyIdBuffer的依赖关系:

• 实现PropertyChangeListener接口:充当一个属性变更事件的监听者
• 实现InitializingBean接口:在应用启动时做一些初始化动作
• 实现IdGenerator接口:实现目标接口作为目标实现类(IdBuffer)的静态代理类

然后再看一下id生成器门面类DoubleBufferIdWorker的依赖关系:

• 实现InitializingBean接口:在类实例化后做一些初始化
• 实现IdWorker:作为idWorker接口的默认实现,并留出扩展实现(比如snowflake)

在上边的时序图中我们看出各个实现类之间的依赖和调用关系,按照图中的调用顺序逐个做一下分析:

1. 客户端发起生成id请求(可能是外部也可能是内部)
2. 获取申请时间当天的年月日(yyyymmdd),为了提高性能,利用双检锁缓存当天年月日字符串
3. 调用代理IdBuffer申请生成数字型id
4. 代理层维护双buffer的扩容和自动切换,调用命中IdBuffer生成数字id
5. 最后DoubleBufferIdWorker加入业务含义并返回特定格式的id

4：测试验证

编写测试代码:

    @Autowired
    private IdWorker idWorker;
    ExecutorService executorService = Executors.newFixedThreadPool(20);
    @Test
    public void batchGetNextId() {
        List<Future<String>> list = new ArrayList<>(10);
         for(int i = 0;i < 10;i ++) {
             list.add(this.executorService.submit(() -> idWorker.nextId("SON",123)));
         }
         list.forEach(item -> {
             String id = null;
             try {
                 id = item.get();
             }catch (Exception e) {
                 log.error("thread={} getId occur error",Thread.currentThread().getName(),e);
             }
             log.info("thread={},id={}",Thread.currentThread().getName(),id);
         });
    }

开启多线程并发生成10个id。执行看结果:

我们设置步长是5,自动扩容阈值时0.8(命中buffer的id使用80%时触发闲置buffer扩容),从执行结果截图中我们看到,初始命中是buffer1,生成四个id之后到达扩容阈值触发buffer2自动批量加载id,生成第5个id时buffer1中存储的id已经用完,触发命中buffer自动切换到buffer2,中间使用到80%的时候又会触发buffer1自动批量获取id,循环运行下去。

5：优势与缺点

一种优秀的解决方案是最切合某种特定业务的方案,当然每一种方案拉平到通用来说都会有其优缺点,基于业务DB的双buffer分布式id生成规则也不例外,优点和缺点也比较明显:

• 优点: 全局唯一

趋势递增

包含业务属性和userId基因,分库分表无缝支持

长度可自定义

999亿的容量,基本支持所有业务增量,线上加预发假如10台机器每天部署100次,每天业务增量是10万,每台机器每次申请5000步长,999 亿/5000/20/10/100/365≈91年,所以不用担心是否够用

• 缺点

每次机器重启或者应用部署,最多浪费n * step个容量单位(每次机器重启都会去数据库拿step个容量单位)

强依赖业务库

需要说明的是,基于业务库双buffer的id生成规则强依赖业务库,如果业务库挂了,id生成规则也就不可用(考虑过降级为idWorker雪花算法, 但是强依赖全局时钟),反过来讲,如果业务库挂了,业务也就挂了,生成了id也没有什么意义。