问题描述#

有以下用户订阅关系表

1
CREATE TABLE `template_subscribe` (
2
  `id` bigint NOT NULL COMMENT 'ID主键',
3
  `template_id` varchar(32) COLLATE utf8mb4_general_ci NOT NULL DEFAULT '' COMMENT '模板id',
4
  `user_id` bigint NOT NULL COMMENT '用户主键',
5
  PRIMARY KEY (`id`) USING BTREE,
6
  KEY `idx_user_id_template_id` (`user_id`, `template_id`) USING BTREE
7
);

先给定一个 CSV 文件 和一个 template_id，只包含 userId, 数量预计在百万级别，要求判断 有多少 userId 在 template_subscribe 表中存在

纯数据库方案#

分批次，通过 sql 从数据库中查询,比如每次 1000 个

1
select count(*) from template_subscribe where user_id in (x1,x2,x3 ...) and template_id = y;

100W数据 需要 1000次循环，假设每次查询需要 1s，一共需要 1000 秒，该方案耗费时间太长不可接受，也会对数据库造成压力

bloom filter方案#

基于数据库中的 template_id 做分组，通过定时任务生成每个分组的 bloom filter 数据结构，判断时，循环遍历csv文件中每个userId，判断是否在 bloom filter 中存在。每个id判断时间查找复杂度大概在 O(k) k为hash函数数量，100W约为 100W * k次，但是会有误判率（数据比真实数量大）。

bitmap 方案#

基于数据库中的 template_id 做分组，通过定时任务生成每个分组的 bitmap 数据结构 A1，判断时，通过循环遍历csv文件中每个userId，生成一个 bitmap A2，通过对 A1、A2 取交集原算得到 A3, 直接判断A3 中的数据量即可得到人数

roaringbitmap 方案#

bitmap 方案的升级版本，解决了内存消耗过大的问题

对比总结#

📎 参考文章#

• https://zhuanlan.zhihu.com/p/445396980