发号器

为什么使用发号器

  • 复杂分布式架构系统中,需要保证生成ID全局唯一
  • 适用兼容Kubernetes弹性扩容,自动重启等场景,无需维护现在雪花算法中使用的的WorkerID
  • 对于以后业务可扩展强,可以为所有业务提供全局唯一ID

方案一

美团LEAF发号器Leaf-segment数据库方案(业务中不可接受出现连续ID可跳过)

缺点

  • ID号码不够随机,能够泄露发号数量的信息,不太安全
  • 数据库I/O趋势图会出现尖刺,出现在多个实例发号器的号段使用完后,去数据库查询更新号段信息时出现(可以查看后面重点SQL
  • 强依赖数据库,DB宕机会造成整个系统不可用,有做缓存号段优化(双buffer优化

优点

  • Leaf服务可以很方便的线性扩展,性能完全能够支撑大多数业务场景
  • 容灾性高:Leaf服务内部有号段缓存,即使DB宕机,短时间内Leaf仍能正常对外提供服务(双buffer优化
  • 可以自定义max_id的大小,非常方便业务从原有的ID方式上迁移过来

方案说明

在架构中允许多个发号器实例,使用同一个库中的分配表biz_tag用来区分业务,max_id表示该biz_tag目前所被分配的ID号段的最大值,step表示每次分配的号段长度。原来获取ID每次都需要写数据库,现在只需要把step设置得足够大,比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step

image

双buffer优化

对于第二个缺点,Leaf-segment做了优化,Leaf 取号段的时机是在号段消耗完的时候进行的,也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间,并且在这期间进来的请求也会因为DB号段没有取回来,导致线程阻塞。如果请求DB的网络和DB的性能稳定,这种情况对系统的影响是不大的,但是假如取DB的时候网络发生抖动,或者DB发生慢查询就会导致整个系统的响应时间变慢。

为此,我们希望DB取号段的过程能够做到无阻塞,不需要在DB取号段的时候阻塞请求线程,即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。详细实现如下图所示

image

采用双buffer的方式,Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时,如果下一个号段未更新,则另启一个更新线程去更新下一个号段。当前号段全部下发完后,如果下个号段准备好了则切换到下个号段为当前segment接着下发,循环往复。

  • 每个biz-tag都有消费速度监控,通常推荐segment长度设置为服务高峰期发号QPS的600倍(10分钟),这样即使DB宕机,Leaf仍能持续发号10-20分钟不受影响。
  • 每次请求来临时都会判断下个号段的状态,从而更新此号段,所以偶尔的网络抖动不会影响下个号段的更新。

验证(结果汇总)

Leaf现状

Leaf在美团点评公司内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。目前Leaf的性能在4C8G的机器上QPS能压测到近5w/s,TP999 1ms,已经能够满足大部分的业务的需求。每天提供亿数量级的调用量,作为公司内部公共的基础技术设施,必须保证高SLA和高性能的服务,我们目前还仅仅达到了及格线,还有很多提高的空间。

测试方法调用

测试代码

    @PostMapping("test")
    public BaseResponse<Boolean> test() {
        ConcurrencyTester tester = ThreadUtil.concurrencyTest(10, () -> {
            ConcurrentHashSet<String> set = new ConcurrentHashSet<>();
            TimeInterval timer = DateUtil.timer();
            // 测试的逻辑内容
            for (int i=0; i<10000; i++) {
                int r = RandomUtil.randomInt(6);
                String s = HttpUtil.get("http://10.0.20.150:909" + r + "/api/segment/get/saving-test");
                set.add(s);
            }
            long l = timer.intervalRestart();
            log.info("{} test finished , time:{}ms , set size:{}", Thread.currentThread().getName(), l, set.size());
        });
        // 获取总的执行时间,单位毫秒
        log.warn("总执行时间:{}ms", tester.getInterval());
        return ResponseUtil.returnSuccess(Boolean.TRUE);
    }

代码输出

20:16:25.381 pool-5-thread-4 test finished , time:34346ms , set size:10000
20:16:25.465 pool-5-thread-9 test finished , time:34430ms , set size:10000
20:16:25.497 pool-5-thread-6 test finished , time:34462ms , set size:10000
20:16:25.511 pool-5-thread-10 test finished , time:34476ms , set size:10000
20:16:25.520 pool-5-thread-5 test finished , time:34485ms , set size:10000
20:16:25.569 pool-5-thread-7 test finished , time:34534ms , set size:10000
20:16:25.573 pool-5-thread-1 test finished , time:34538ms , set size:10000
20:16:25.580 pool-5-thread-2 test finished , time:34545ms , set size:10000
20:16:25.606 pool-5-thread-3 test finished , time:34571ms , set size:10000
20:16:25.623 pool-5-thread-8 test finished , time:34588ms , set size:10000
20:16:25.623 总执行时间:34599ms
测试结果
  • 多实例: 约等于12044qps

在本地开发机6U32G启动6个发号器实例,9090,9091,9092测试中进行随机调用

3台机器1500线程并发压测:4038+3795+4211=12044qps(未压到上限仅供参考)

  • 单实例:约等于8469qps(设置固定请求9090实例)

(设置固定请求9090实例,在14虚拟机2U4G配置上运行)

4台机器压测:1493+2357+2425+2194=8469qps

业务场景模拟DB操作

测试环境本机测试,启动6个发号器实例

9090,9091,9092,9093,9094,9095

在下面测试中进行随机调用

测试代码

@PostMapping("test")
    public BaseResponse<Boolean> test() {
        BasicLoginInfo basicLoginInfo = new BasicLoginInfo();
        basicLoginInfo.setTenantId(9);
        ThreadLocalContext.set(basicLoginInfo);
        ConcurrencyTester tester = ThreadUtil.concurrencyTest(10, () -> {
            // 测试的逻辑内容
            for (int i=0; i<10000; i++) {
                TimeInterval timer = DateUtil.timer();
                int r = RandomUtil.randomInt(6);
//                String s = HttpUtil.get("http://10.0.20.150:909" + r + "/api/snowflake/get/test");
                String s = HttpUtil.get("http://10.0.20.150:909" + r + "/api/segment/get/saving-test");
                log.info(s);
                MemberDBO memberDBO = MemberDBO.builder().build();
                memberDBO.setId(Long.valueOf(s));
                memberMapper.insert(memberDBO);
                long l = timer.intervalRestart();//返回花费时间,并重置开始时间
                log.info("tcp消耗时间:{}ms", l);
            }
            log.info("{} test finished", Thread.currentThread().getName());
        });
        // 获取总的执行时间,单位毫秒
        log.warn("总执行时间:{}ms", tester.getInterval());
        return ResponseUtil.returnSuccess(Boolean.TRUE);

十个线程每个循环执行1w次,总执行10w获取ID并且模拟插入用户数据,总执行时间

  • 第一次:121472ms
  • 第二次:107789ms
  • 第二次:120809ms

未出现重复ID,入库数据10W条,主键ID全唯一

测试结果

模拟业务中约等于854qps

方案二

美团发号器Leaf-snowflake方案雪花ID算法

image

缺点

  • 弱依赖ZooKeeper,需要维护多一个中间件,使用其的持久有序节点,进行分配workerID用于进行生成雪花算法(ZooKeeper挂了后,不影响id生成,并且每3秒循环重连机制)
  • 强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态,已解决,使用Zookeeper的持久有序节点,进行了时间校验
  • 受到workerID限制最大维度下存在1024台发号器

优点

  • 生成ID安全性强
  • 性能相比号段模式不用查询更新步数高些,本地代码生成,毫秒数在高位,自增序列在低位,整个ID都是趋势递增的

解决时钟问题

因为这种方案依赖时间,如果机器的时钟发生了回拨,那么就会有可能生成重复的ID号,需要解决时钟回退的问题。

image

参见上图整个启动流程图,服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点:

  1. 若写过,则用自身系统时间与leaf_forever/${self}节点记录时间做比较,若小于leaf_forever/${self}时间则认为机器时间发生了大步长回拨,服务启动失败并报警。
  2. 若未写过,证明是新服务节点,直接创建持久节点leaf_forever/${self}并写入自身系统时间,接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确,具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP:Port,然后通过RPC请求得到所有节点的系统时间,计算sum(time)/nodeSize
  3. abs( 系统时间-sum(time)/nodeSize ) < 阈值,认为当前系统时间准确,正常启动服务,同时写临时节点leaf_temporary/${self}维持租约。
  4. 否则认为本机系统时间发生大步长偏移,启动失败并报警
  5. 每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}

由于强依赖时钟,对时间的要求比较敏感,在机器工作时NTP同步也会造成秒级别的回退,建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE,等时钟追上即可。或者做一层重试,然后上报报警系统,更或者是发现有时钟回拨之后自动摘除本身节点并报警,如下:

 //发生了回拨,此刻时间小于上次发号时间
 if (timestamp < lastTimestamp) {
            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try {
                	//时间偏差大小小于5ms,则等待两倍时间
                    wait(offset << 1);//wait
                    timestamp = timeGen();
                    if (timestamp < lastTimestamp) {
                       //还是小于,抛异常并上报
                        throwClockBackwardsEx(timestamp);
                      }    
                } catch (InterruptedException e) {  
                   throw  e;
                }
            } else {
                //throw
                throwClockBackwardsEx(timestamp);
            }
        }
 //分配ID       

验证(结果汇总)

Leaf现状

Leaf在美团点评公司内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。目前Leaf的性能在4C8G的机器上QPS能压测到近5w/s,TP999 1ms,已经能够满足大部分的业务的需求。每天提供亿数量级的调用量,作为公司内部公共的基础技术设施,必须保证高SLA和高性能的服务,我们目前还仅仅达到了及格线,还有很多提高的空间。

测试方法调用

测试代码

    @PostMapping("test")
    public BaseResponse<Boolean> test() {
        ConcurrencyTester tester = ThreadUtil.concurrencyTest(10, () -> {
            ConcurrentHashSet<String> set = new ConcurrentHashSet<>();
            TimeInterval timer = DateUtil.timer();
            // 测试的逻辑内容
            for (int i=0; i<10000; i++) {
                int r = RandomUtil.randomInt(6);
                String s = HttpUtil.get("http://10.0.20.150:909" + r + "/api/snowflake/get/test");
                set.add(s);
            }
            long l = timer.intervalRestart();
            log.info("{} test finished , time:{}ms , set size:{}", Thread.currentThread().getName(), l, set.size());
        });
        // 获取总的执行时间,单位毫秒
        log.warn("总执行时间:{}ms", tester.getInterval());
        return ResponseUtil.returnSuccess(Boolean.TRUE);
    }

代码输出

20:08:26.019 pool-5-thread-2 test finished , time:29172ms , set size:10000
20:08:26.036 pool-5-thread-7 test finished , time:29189ms , set size:10000
20:08:26.101 pool-5-thread-1 test finished , time:29254ms , set size:10000
20:08:26.117 pool-5-thread-5 test finished , time:29270ms , set size:10000
20:08:26.126 pool-5-thread-10 test finished , time:29279ms , set size:10000
20:08:26.151 pool-5-thread-6 test finished , time:29304ms , set size:10000
20:08:26.185 pool-5-thread-4 test finished , time:29338ms , set size:10000
20:08:26.194 pool-5-thread-8 test finished , time:29347ms , set size:10000
20:08:26.201 pool-5-thread-9 test finished , time:29354ms , set size:10000
20:08:26.219 pool-5-thread-3 test finished , time:29372ms , set size:10000
20:08:26.220 总执行时间:29382ms
测试结果
  • 多实例: 约等于9997qps

在本地开发机6U32G启动3个发号器实例,9090,9091,9092测试中进行随机调用

3台机器1500线程并发压测:3326+3631+3040=9997qps (未压到上限仅供参考)

  • 单实例:约等于13559qps

(设置固定请求9090实例,在14虚拟机2U4G配置上运行)

4台机器1500线程并发压测:945+3131+5732+3751=13559qps

业务场景模拟DB操作

测试环境本机测试,启动6个发号器实例

9090,9091,9092,9093,9094,9095

在下面测试中进行随机调用

测试代码

@PostMapping("test")
public BaseResponse<Boolean> test() {
    BasicLoginInfo basicLoginInfo = new BasicLoginInfo();
    basicLoginInfo.setTenantId(9);
    ThreadLocalContext.set(basicLoginInfo);
    ConcurrencyTester tester = ThreadUtil.concurrencyTest(10, () -> {
        // 测试的逻辑内容
        for (int i=0; i<10000; i++) {
            TimeInterval timer = DateUtil.timer();
            int r = RandomUtil.randomInt(6);
            String s = HttpUtil.get("http://10.0.20.150:909" + r + "/api/snowflake/get/test");
            log.info(s);
            MemberDBO memberDBO = MemberDBO.builder().build();
            memberDBO.setId(Long.valueOf(s));
            memberMapper.insert(memberDBO);
            long l = timer.intervalRestart();//返回花费时间,并重置开始时间
            log.info("tcp消耗时间:{}ms", l);
        }
        log.info("{} test finished", Thread.currentThread().getName());
    });
    // 获取总的执行时间,单位毫秒
    log.warn("总执行时间:{}ms", tester.getInterval());
    return ResponseUtil.returnSuccess(Boolean.TRUE);
}

十个线程每个循环执行1w次,总执行10w获取ID并且模拟插入用户数据,总执行时间

  • 第一次:117733ms
  • 第二次:112027ms
  • 第二次:109745ms

未出现重复ID,入库数据10W条,主键ID全唯一

测试结果

模拟业务中约等于885qps

方案三

百度uid-generator

使用的也是雪花算法,利用DB分配WorkerID

因为与美团发号器的雪花方案相似,和使用未来时间进行借用,还会产生节点使用时长限制,放弃选择

GitHub:https://github.com/baidu/uid-generator

方案四

滴滴tinyid

采取的是在美团发号器号段模式进行了改进实现

因为与美团号段模式相似,放弃选择

GitHub:https://github.com/didi/tinyid

方案测试报告

Leaf现状

Leaf在美团点评公司内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。目前Leaf的性能在4C8G的机器上QPS能压测到近5w/s,TP999 1ms,已经能够满足大部分的业务的需求。每天提供亿数量级的调用量,作为公司内部公共的基础技术设施,必须保证高SLA和高性能的服务,我们目前还仅仅达到了及格线,还有很多提高的空间。

测试环境

测试接口--多实例测试环境——在本地开发机6U32G启动3个发号器实例,9090,9091,9092测试中进行随机调用

测试接口--单实例测试环境——(设置固定请求9090实例,在14虚拟机2U4G配置上运行)4台机器1500线程并发压测

模拟DB操作--多实例——十个线程每个循环执行1w次,总执行10w获取ID并且模拟插入用户数据

报告汇总

方案一(Leaf-segment数据库方案)方案二(Leaf-snowflake雪花方案)
测试接口--多实例12044qps9997qps
测试接口--单实例8469qps13559qps
模拟DB操作--多实例854qps885qps

PS:多实例数据仅供参考

参考

@author Saving
@date 2021.07.14