转载

千万用户的人群过滤，做好这几个点，竟然支持亿级流量

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

背景

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

what？？？亿级？过滤？这么大的数据，怎么存，存了，怎么用，你倒是提完需求，拍拍屁股走人了，留下我自己在电脑前凌乱。我个人宣布，我要与产品势不两立！！！言归正传，亿级用户已经是很大的挑战了，还要满足如此多的限制与要求，当时的我是一个脑袋两个大，这可如何是好呢？

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

数据人群庞大，每个指定人群下面可能都有千万级甚至亿级用户。
并发请求量极大，需要满足10w QPS的并发量。
性能要求高，处理时间不得高于30ms。

关键点分析

人群数据量庞大，且用户的id为long类型，long类型在go语言中，需要占据8个字节，我们以1000w个用户举例，那么10000000*8/1024/1024约等于 76MB。也就是说，我们单单存储这1000w个用户id信息，在最理想的情况下，就需要用到76MB的内存大小。
并发量较高，既然如此，数据必须要放在内存中，或者使用Redis等分布式内存服务。并且单机很难满足我们的要求，我们需要使用集群部署。
性能要求高，如此低时延的要求，我们尽量使用内存，使用本机处理。减少第三方中间件依赖，尽可能的减少网络请求次数。

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

数据存储与优化

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

使用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。压缩位图的原理实现比较复杂，不是本文的讨论主题。实现思路大概是这样

将 32bit int（无符号的）类型数据划分为 2^16 个桶，即最多可能有216=65536个桶，论文内称为container。用container来存放一个数值的低16位
在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）

选好了数据结构，把千万数据放入RoaringBitmap中，大概只需要几十MB左右即可。具体可参考github中RoaringBitmap的实现，对Java、Go等语言都有支持。 github.com/RoaringBitm…

内存策略

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

采用Hash分片，不同的人群根据Hash放在不同的机器上，这样可以保证单机器量的内存使用较小。但处理起来较为麻烦，还要解决请求时的负载问题。
单机器全量存储，操作简单，数据全量加载进内存即可，但对机器配置有要求，单实例使用内存在20G左右。

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

集群部署&负载均衡

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

容错与备份

我们提到数据是存放在内存中，因此会面临服务发布，服务器重启的情况，因此数据需要有可靠的构建逻辑，数据源存放需要可靠，做好持久化，方便服务的随时加载。我的方案是，人群的具体数据存放在clickhouse中，构建逻辑由定时任务，根据业务关键字触发，根据需要的数据去查询、构建好，再由我的服务器去进行加载。