转载

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

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

背景

一天,产品来到我的面前,对我说,“拿铁啊,你给我实现一个功能,在亿级用户情况下,根据用户id,过滤出这个人是否在我们的指定人群下面,不同人群组合,有大概1000个左右,并且性能一定要够好哦。”   7 what???亿级?过滤?这么大的数据,怎么存,存了,怎么用,你倒是提完需求,拍拍屁股走人了,留下我自己在电脑前凌乱。我个人宣布,我要与产品势不两立!!! 言归正传,亿级用户已经是很大的挑战了,还要满足如此多的限制与要求,当时的我是一个脑袋两个大,这可如何是好呢?   8 产品一句话,研发跑断腿,根据沟通,最终确认有几个关键点一定要满足
  • 数据人群庞大,每个指定人群下面可能都有千万级甚至亿级用户。
  • 并发请求量极大,需要满足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等语言都有支持。 github.com/RoaringBitm…

内存策略

因为我们选用了RoaringBitmap,所以我们数据需要放在内存中,因为数据量比较大,上千个RoaringBitmap在内存中,使用的数据量也是很大的,这种我们一般有两种结局方案
  1. 采用Hash分片,不同的人群根据Hash放在不同的机器上,这样可以保证单机器量的内存使用较小。但处理起来较为麻烦,还要解决请求时的负载问题。
  2. 单机器全量存储,操作简单,数据全量加载进内存即可,但对机器配置有要求,单实例使用内存在20G左右。
采用分片的方式,要处理的过多,还要处理分片的分流逻辑。我最终选择了第二个方案,即全量加载。

集群部署&负载均衡

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

容错与备份

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

写在最后

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