Hi，大家好，我是东东拿铁，一名 95 后奶爸程序员。

背景

一天，产品来到我的面前，对我说，“拿铁啊，你给我实现一个功能，在亿级用户情况下，根据用户 id，过滤出这个人是否在我们的指定人群下面，不同人群组合，有大概 1000 个左右,并且性能一定要够好哦。”

what？？？亿级？过滤？这么大的数据，怎么存，存了，怎么用，你倒是提完需求，拍拍屁股走人了，留下我自己在电脑前凌乱。我个人宣布，我要与产品势不两立！！！

言归正传，亿级用户已经是很大的挑战了，还要满足如此多的限制与要求，当时的我是一个脑袋两个大，这可如何是好呢？

产品一句话，研发跑断腿，根据沟通，最终确认有几个关键点一定要满足

• 数据人群庞大，每个指定人群下面可能都有千万级甚至亿级用户。

• 并发请求量极大，需要满足 10w QPS 的并发量。

• 性能要求高，处理时间不得高于 30ms。

关键点分析

1. 人群数据量庞大，且用户的 id 为 long 类型，long 类型在 go 语言中，需要占据 8 个字节，我们以 1000w 个用户举例，那么 10000000*8/1024/1024 约等于 76MB。也就是说，我们单单存储这 1000w 个用户 id 信息，在最理想的情况下，就需要用到 76MB 的内存大小。

2. 并发量较高，既然如此，数据必须要放在内存中，或者使用 Redis 等分布式内存服务。并且单机很难满足我们的要求，我们需要使用集群部署。

3. 性能要求高，如此低时延的要求，我们尽量使用内存，使用本机处理。减少第三方中间件依赖，尽可能的减少网络请求次数。

带大家分析完关键点，我是如何分析并解决的，从以下四个方面来进行处理。

数据存储与优化

判断一个值，是否存在，最常见的两种思路

• 使用 list，循环遍历，list 如果查询我们的指定值，时间复杂度 O(n),对于千万级数据来说，开销太大了，如果使用这个方案，明天可能就因为左脚先进公司而被辞退了。

• 使用 map，直接 get 即可。map，上面提到，单独某一个人群，就有 76MB，1000 个人群，数据量会使用到惊人的 74GB 左右，单单用户信息的内存使用量，就是我们无法接受的。

BitMap

排除上述两种数据结构，我天然的会想到，使用 BitMap 来去处理，在我的印象中，BitMap，位图，基本原理就是用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素，每个用户只占用一个 bit，那我 1000w 用户，才区区占用 10000000/8/1024/1024 约等于 1.2MB 左右，这点内存占用，和不占用有什么区别，我真是个天才！

看到这里，你是不是就觉着已经结束了？完全没有含金量！这个年头，谁还不会用 BitMap！

但当我拿出这个用户 id，阁下如何应对？id:6740413579666840。

没看懂？来，我们假设，这个就是我们 id 的最大值，也就是说，我们需要用到这么多 bit 来存储我们的数据，那这个数据是多少呢？6740413579666840/8/1024/1024 约等于 803519914MB。

是的，我一开始的假设，是指我这 1000w 用户，id 从 1 开始且连续的情况下，只需要 1MB 左右，就能够完成数据存储了。

然而现在我们的数据，大部分 id 都已经是 long 类型，长度已经非常大了，传统的位图完全没有办法支持我们这种量级的数据去存储。

RoaringBitmap

下面请出主角吧，RoaringBitmap，压缩位图，简称 RBM。

压缩位图的原理实现比较复杂，不是本文的讨论主题。实现思路大概是这样

1. 将 32bit int（无符号的）类型数据 划分为 2^16 个桶，即最多可能有 216=65536 个桶，论文内称为 container。用 container 来存放一个数值的低 16 位

2. 在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）

选好了数据结构，把千万数据放入 RoaringBitmap 中，大概只需要几十 MB 左右即可。

具体可参考 github 中 RoaringBitmap 的实现，对 Java、Go 等语言都有支持。

https://github.com/RoaringBitmap/roaring

内存策略

因为我们选用了 RoaringBitmap，所以我们数据需要放在内存中，因为数据量比较大，上千个 RoaringBitmap 在内存中，使用的数据量也是很大的，这种我们一般有两种结局方案

1. 采用 Hash 分片，不同的人群根据 Hash 放在不同的机器上，这样可以保证单机器量的内存使用较小。但处理起来较为麻烦，还要解决请求时的负载问题。

2. 单机器全量存储，操作简单，数据全量加载进内存即可，但对机器配置有要求，单实例使用内存在 20G 左右。

采用分片的方式，要处理的过多，还要处理分片的分流逻辑。我最终选择了第二个方案，即全量加载。

集群部署 &负载均衡

这里不在过多阐述，为了保证服务稳定性，我们需要使用集群部署，流量的负载均衡使用公司现有的方案即可。

容错与备份

我们提到数据是存放在内存中，因此会面临服务发布，服务器重启的情况，因此数据需要有可靠的构建逻辑，数据源存放需要可靠，做好持久化，方便服务的随时加载。

我的方案是，人群的具体数据存放在 clickhouse 中，构建逻辑由定时任务，根据业务关键字触发，根据需要的数据去查询、构建好，再由我的服务器去进行加载。

写在最后

最终，服务如期上线，过滤逻辑完美运行。可是服务上线之后，面临的 SLA 问题，多个 RoaringBitmap 需要交并集的业务计算问题，都还在等着我。如果大家有兴趣，我在后面再和大家慢慢道来吧,有问题随时可以和我评论区交流。

新人码字不易，欢迎点赞评论与转发，不胜感激！