公司黑客松 - 实时发号系统方案

背景

• 公司每日新增设备百万级 周新增接近亿级
• 要给每一个设备都发一个唯一 id 且需要一个合适的偏移量避免漏号和发重
• 每个 id 对应唯一且最大的 offset

ID 格式：

UUID+ 一位类型

场景描述

每天最大十亿级的日志，日活亿级的设备数，其中百万级的新增

比赛要求

业务：

目前 ID 量 90 多亿，每天日活 2 亿左右，每天新增 600 万左右。
设计实时发号系统。其中 id 长 33 位（ 1magicNumber + 32 位 MD5），offset 整数、依次递增。

【服务的功能性要求】:

• 输入 id，输出 offset
• QPS = 600 w /( 12 * 60 * 60 ) = 138

参考资料:

1. Leaf——美团点评分布式ID生成系统

2. EWAHCompressedBitmap -google
3. javaEWAH: https://github.com/lemire/javaewah
4. https://www.chainnews.com/articles/555869220376.htm id 查询服务,作为其中一个环节
5. 雪花算法 https://segmentfault.com/a/1190000011282426?utm_source=tag-newest

整体流程:

分工:

技术调研记录:

1.测试数据生成，验证程序

import java.io.*;
import java.util.UUID;

public class UUIDGenerator {
    private String getId() {
        UUID uuid = UUID.randomUUID();
        return uuid.toString().replace("-", "");
    }
    public static void main(String[] args) {
        File f = new File("path");
        long startTime = System.currentTimeMillis();
        Writer out = null;
        try {
            int i = 100000000;
            BufferedWriter bw = new BufferedWriter(new FileWriter("path"));
            bw.write(i);
            bw.newLine();
            for (i = 1; i <= 100000000; i++) {
                String uid = "h" + new UUIDGenerator().getId();
                bw.write(uid);
                bw.newLine();
            }
            bw.flush();
            bw.close();
        } catch (IOException e) {
        e.printStackTrace();
        }
        long endTime = System.currentTimeMillis();
        System.out.println("time: " + (endTime - startTime) / 1000 + " s");
    }
}

http 性能测试

wrk

https://juejin.im/post/5a59e74f5188257353008fea
lua 自定义压测用例，包括数据量，新旧数据，重复数据比例

Siege

一款开源的压力测试工具，可以根据配置对一个 WEB 站点进行多用户的并发访问，记录每个用户所有请求过程的相应时间，并在一定数量的并发访问下重复进行。

Siege 官方：http://www.joedog.org/
Siege 下载：http://www.joedog.org/pub/siege/siege-latest.tar.gz

Siege 解压并安装：
tar -zxvf siege-latest.tar.gz
cd siege-latest/
./configure
make
make install

Siege 使用:
siege -c 100 -r 10 -f site.url
-c 是并发量，-r 是重复次数。
url 文件就是一个文本，每行都是一个 url，它会从里面随机访问的。

site.url 内容:
http://www.qixing318.com/
http://www.zendsns.com/
http://www.qixing.info/

Transactions: 550 hits // 完成 550 次处理
Availability: 55.00 % // 55.00 % 成功率
Elapsed time: 31.32 secs // 总共用时
Data transferred: 1.15 MB // 共数据传输 1.15 MB
Response time: 3.04 secs // 显示网络连接的速度
Transaction rate: 17.56 trans/sec // 均每秒完成 17.56 次处理：表示服务器后
Throughput: 0.04 MB/sec // 平均每秒传送数据
Concurrency: 53.44 // 实际最高并发数
Successful transactions: 433 // 成功处理次数
Failed transactions: 450 // 失败处理次数
Longest transaction: 15.50 // 每次传输所花最长时间
Shortest transaction: 0.42 // 每次传输所花最短时间

2.服务

主流程:

根据 id 查询旧的 offset
存在,直接返回
不存在,分配新的 offset
获取新的 offset
保存 id 和 offset 的映射关系

1.发号器:号段-减少 db 压力

https://tech.meituan.com/2017/04/21/mt-leaf.html
每次获取一个 segment(step 决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。

原来获取 ID 每次都需要写数据库，现在只需要把 step 设置得足够大，比如 1000。那么只有当 1000 个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从 1 减小到了 1/step，大致架构如下图所示：

2.发号器:双 buffer 优化

对于第二个缺点，Leaf-segment 做了一些优化，简单的说就是：
Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的 ID 下发时间取决于下一次从 DB 取回号段的时间，并且在这期间进来的请求也会因为 DB 号段没有取回来，导致线程阻塞。如果请求 DB 的网络和 DB 的性能稳定，这种情况对系统的影响是不大的，但是假如取 DB 的时候网络发生抖动，或者 DB 发生慢查询就会导致整个系统的响应时间变慢。
为此，我们希望 DB 取号段的过程能够做到无阻塞，不需要在 DB 取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的 TP999 指标。详细实现如下图所示：

3.Nginx:配置 url_hash 负载均衡策略

Nginx负载均衡－如何自定义URL中的hash key_慕课手记

4.读写锁:

其中,Nginx 配置 url_hash 负载均衡策略 +tdid 级别读写锁,保证数据严格一对一

5.依赖的存储层接口

1. 根据 id 查询 offset
2. 获取当前值,并自增指定步幅(保证原子性)
3. 设置 id,offset

3.存储

1. 大规模数据判重：

redis modules 插件 BoolmFilter https://github.com/RedisBloom/RedisBloom
api: https://oss.redislabs.com/redisbloom/Quick_Start
2. tdid-> offset 映射：2 亿存储 10G 数据。 60 亿 300G 数据

ssdb
考虑映射关系读写很频繁，计划使用 nosql 数据库 ssdb, 是对 leveldb 存储引擎的 redis 兼容协议封装，其性能可和 redis 比肩,有待验证效率。而且可以把存储不下的持久化到硬盘，解决 Redis 容量有限问题。
官网：http://ssdb.io/zh_cn/
api: http://ssdb.io/docs/zh_cn/commands/index.html
别人的读写测试： https://www.cnblogs.com/lulu/p/4231810.html

1. 读写逻辑

测试场景:
每天最大 60 亿日的日志，日活 2 亿的设备数，其中 600w 是新增
100% 新数据(发号)
0% 数据(查询)
极端情况:并发新增

性能测试

1.bloom Filter

1000w 测试， 325M ，bloom 配置（容量 1000w, 0.001% 错误率）,内存占用 33M
a.写 395700ms = 395s，插入 QPS = 1000W /400 = 2.5W/s
1 亿 4000s = 66.7min , 平均一亿一小时。 够了，每天新增用户才 500W-600W , 最快半小时插入布隆过滤器，而且请求不会很集中

b.正向读（存在数据） 378456ms = 378s = 6.3min ，QPS = 1000w/400 = 2.5w/s
c.反向读（不存在数据）402886ms = 400s，QPS = 1000w/400 = 2.5w/s

1000w 测试， 325M ，bloom 配置（容量 1000w, 0.1% 错误率）,内存占用 11.4M
读写速率和上面类似

1000w 测试， 325M ，bloom 配置（容量 1 亿 , 0.1% 错误率）,内存占用 63M

1000w 测试， 325M ，bloom 配置（容量 10 亿 , 0.1% 错误率）,内存占用 1000M
1000000000 =10 亿

1000w 测试， 325M ，bloom 配置（容量 20 亿 , 0.1% 错误率）,内存占用 2000M
20 亿已经很大了，再大需要拆分过滤器，取 hash % number = filter index
100 亿需要 4 个过滤器 = 4 * 2 = 8G 内存

结论
1.相同数据，误判率越低，占用内存越大;
2.相同数据，bloomFilter 容量越大，占用内存越大，且容量在初始化时已经确定，add 数据不会改变；
3.bloomFilter 容量有上线，30 亿左右，再大的量需要多个过滤器分片了。
4.读写速度基本和容量、错误率无关。
5.读写 QPS 均为 2.5w/s ，关键优势内存占用很少。

2.ssdb

单线程，读写速度相似。 1000w 数据 325M ，内存占用几十 M，空间占用 100M ,leveldb 有压缩
写 120000ms = 1200s = 20 min QPS = 0.83W/s
读 123500ms = 1235s = 20.6 min QPS = 0.8W/s

3.redis

1000w 测试
写 1021980 ms = 1022s QPS = 0.97W/s
正向读 949310 ms =949s QPS =1.05W/s
反向读 935231 ms =935s QPS = 1.07W/s

结论
性能比较 ssdb 提升不大，缓存作用不明显。

联调性能

测试要点

！！！！每次测试开始必须保证全新环境！！！！！

1.初始化新的布隆过滤器

1. 命令行 BF.RESERVE {bloom_key} {error_rate} {capacity} 误差率是小数，不是百分比

Parameters:¶

• key: The key under which the filter is to be found
• error_rate: The desired probability for false positives. This should be a decimal value between 0 and 1. For example, for a desired false positive rate of 0.1% (1 in 1000), error_rate should be set to 0.001. The closer this number is to zero, the greater the memory consumption per item and the more CPU usage per operation.
• capacity: The number of entries you intend to add to the filter. Performance will begin to degrade after adding more items than this number. The actual degradation will depend on how far the limit has been exceeded. Performance will degrade linearly as the number of entries grow exponentially.

1. 客户端, 需要 maven 引入

Client client = new Client("localhost", 6379);
client.createFilter("Filter3", 10_000_000, 0.1); 过滤器名称，容量，误差率（百分比值）

2.ssdb flushdb 清空存储

测试场景

初始化:
想 ssdb 中插入 2 亿条数据

正常测试:

全新
全旧
保证数据严格一对一:并发新加,并发新增,并检测返回值

可优化的点
双 buffer
web 容器线程池
连接池
非阻塞式
jvm 参数
ssdb 参数
setnx http://ssdb.io/docs/zh_cn/commands/setnx.html 替换所有的代码
nginx 参数
将 long 转成 base64 编码,然后存到 redis 中

TODOList:
验证 url_hash 是否正确
验证读取文件的 wrk 和不读取的 wrk 差异

压力测试

!!!!使用 siege 注意
手动打乱顺序
使用 siege 进行压力测试要注意！
他的随机访问文件中的 URL，是会重复访问到同一个 url 且不会停止。
siege 参数 -c * -r == wc -l nohup.log

脚本可用测试 1000 条
siege -c 5 -f test_v1_1000.txt -i
Transactions: 161418 hits
Availability: 100.00 %
Elapsed time: 74.98 secs
Data transferred: 0.77 MB
Response time: 0.00 secs
Transaction rate: 2152.81 trans/sec
Throughput: 0.01 MB/sec
Concurrency: 4.41
Successful transactions: 161418
Failed transactions: 0
Longest transaction: 3.02
Shortest transaction: 0.00

服务自测试场景

14w 写库 siege -c 100 -r 1400 -f test_v1_140w_aa
2000w 总量 新增 60w 旧数据 140w 100 并发 请求十次 重复 1800w

Transactions: 140000 hits
Availability: 100.00 %
Elapsed time: 11.49 secs
Data transferred: 0.70 MB
Response time: 0.01 secs
Transaction rate: 12184.51 trans/sec
Throughput: 0.06 MB/sec
Concurrency: 93.64
Successful transactions: 140000
Failed transactions: 0
Longest transaction: 0.05
Shortest transaction: 0.00

140w 写库 siege -c 100 -r 14000 -f test_v1_140w.txt
Transactions: 1400000 hits
Availability: 100.00 %
Elapsed time: 115.59 secs
Data transferred: 8.29 MB
Response time: 0.01 secs
Transaction rate: ** 12111.77 trans/sec**
Throughput: 0.07 MB/sec
Concurrency: 96.01
Successful transactions: 1400000
Failed transactions: 0
Longest transaction: 0.09
Shortest transaction: 0.00

1000w 验证
2000w 总量 新增 60w 旧数据 140w 重复 1800w
1000w 140w 旧 60w 新 800w 重复
siege -c 100 -r 200000 -f test_v1_2000w_shuf.txt
siege -c 200 -r 50000 -f test_v1_1000w_shuf.txt
Transactions: 10000000 hits
Availability: 100.00 %
Elapsed time: ** 789.79 secs = 13min **
(由此推算，1 亿请求 130min 2h10min , 2 亿请求 260min 4h 20min.)
Data transferred: 61.46 MB
Response time: 0.01 secs
Transaction rate: 12661.59 trans/sec
Throughput: 0.08 MB/sec
Concurrency: ** 179.90**
Successful transactions: 10000000
Failed transactions: 0
Longest transaction: 1.04
Shortest transaction: 0.00

v2
cp test_v2_140w.txt test_v2_200w.txt
siege -c 100 -f test_v2_140w.txt -i
tail -f nohup.out | head -n 10
140w 写库
布隆过滤器判重服务与 redis 请求数量过多会超时 无法完成写库
nohup siege -c 100 -r 14000 -f test_v2_140w.txt &

1000w 验证

nohup siege -c 200 -r 50000 -f test_v2_1000w_shuf.txt &

[2650008, 2650007, 2650012, 2650009, 2650010, 2650013, 2650011, 2650014]

演示数据

28w 写库
40w 5 = 验证 28w 旧 + 12w 新 +160w 重复(12w4 + 28*4)
预计 运行时间 6 分钟 接口时间 2 分 40s
124 /home/hadoop/data/show_case/show_200w_shuf.txt
写库
nohup siege -c 100 -r 2800 -f show_28w.txt &
验证
nohup siege -c 200 -r 10000 -f show_200w_shuf.txt &
siege -c 200 -r 10000 -f show_200w_shuf.txt
wrk -t4 -c1000 -d30s -T5s --script=get.lua --latency XXXXXXX(请求地址)

最后

文章还没有详细干货化整理，只是把竞赛时的思路记录下来，有什么问题可以评论留言，看到可能就回复了哈哈。
感谢我杰哥宇哥，刚进公司有领路人真的是非常幸运的事情。
祝大家工作顺利，生活愉快。