发号器

• 发号器
  • 为什么使用发号器
  • 方案一
    • 美团LEAF发号器Leaf-segment数据库方案(业务中不可接受出现连续ID可跳过)
      • 缺点
      • 优点
      • 方案说明
      • 双buffer优化
      • 验证(结果汇总)
        • 测试方法调用
          • 测试结果
        • 业务场景模拟DB操作
          • 测试结果
  • 方案二
    • 美团发号器Leaf-snowflake方案雪花ID算法
      • 缺点
      • 优点
      • 解决时钟问题
      • 验证(结果汇总)
        • 测试方法调用
          • 测试结果
        • 业务场景模拟DB操作
          • 测试结果
  • 方案三
    • 百度uid-generator
  • 方案四
    • 滴滴tinyid
  • 方案测试报告
    • 测试环境
    • 报告汇总
  • 参考

为什么使用发号器

• 复杂分布式架构系统中，需要保证生成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。

双buffer优化

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

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

采用双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算法

缺点

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

优点

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

解决时钟问题

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

参见上图整个启动流程图，服务启动时首先检查自己是否写过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雪花方案）
测试接口--多实例	12044qps	9997qps
测试接口--单实例	8469qps	13559qps
模拟DB操作--多实例	854qps	885qps

PS：多实例数据仅供参考

参考

• Leaf——美团点评分布式ID生成系统
• Leaf
• uid-generator
• tinyid

@author Saving
@date 2021.07.14