Redis如何存储和计算一亿用户的活跃度

1

前段时间,在网上看到一道面试题:

若何用redis存储统计1亿用户一年的上岸情形,并快速检索随便时间窗口内的活跃用户数目。

觉得很有意思,就仔细想了下 。并做了一系列实验,自己模拟了下 。照样有点收获的,现整理下来。和人人一起分享。

Redis是一个内存数据库,接纳单线程和事宜驱动的机制来处置网络请求。现实生产的QPS和TPS单台都能到达3,4W,读写性能异常棒。用来存储一些对焦点营业弱影响的用户状态信息照样异常不错的。

对于这题,有2个主要的点需要思量:

1.若何用合适的数据类型来存储1亿用户的数据,用通俗的字符串来存储一定不行。经由查看一个最简朴的kv(key为aaa,value为1)的内存占用,发现为48byte。

Redis如何存储和计算一亿用户的活跃度

假设每个用户天天上岸需要占有1对KV的话,那一亿就是(48*100000000)/1024/1024/1024=4.47G。这照样一天的量。

2.若何知足搜索,redis是一个键值对的内存结构,只能凭据key来举行定位value值,无法做到像elastic search那样对文档举行倒排索引快速全文检索。

redis实在有这种数据结构的,可以以很少的空间来存储大量的信息。

2

在redis 2.2.0版本之后,新增了一个位图数据,实在它不是一种数据结构。现实上它就是一个一个字符串结构,只不外value是一个二进制数据,每一位只能是0或者1。redis单独对bitmap提供了一套下令。可以对随便一位举行设置和读取。

bitmap的焦点下令:

SETBIT

语法:SETBIT key offset value

例如:

setbit abc 5 1 —-> 00001

setbit abc 2 1 —-> 00101

GETBIT

语法:GETBIT key offset

例如:

getbit abc 5 —-> 1

getbit abc 1 —-> 0

bitmap的其他下令另有bitcount,bitcount,bitpos,bitop等下令。都是对位的操作。

由于bitmap的每一位只占有1bit的空间 ,以是行使这个特征我们可以把每一天作为key,value为1亿用户的活跃度状态。假设一个用户一天内只要登录了一次就算活跃。活跃我们就记为1,不活跃我们就记为0。把用户Id作为偏移量(offset)。这样我们一个key就可以存储1亿用户的活跃状态。

Redis如何存储和计算一亿用户的活跃度

我们再来算下,这样一个位图结构的值工具占有若干空间。每一个位是1bit,一亿用户就是一亿bit。8bit=1Byte

100000000/8/1024/1024=11.92M

我用测试工程往一个key里通过lua塞进了1亿个bit,然后用rdb tools对内存举行统计,实测如下:

Redis如何存储和计算一亿用户的活跃度

一天1亿用户也就消耗12M的内存空间。这完全相符要求。1年的话也就4个G。几年下来的话,redis可以集群部署来举行扩容存储。我们也可以用位图压缩算法对bitmap举行压缩存储。例如WAH,EWAH,Roaring Bitmaps。这个以后可以单独拉出来聊聊。

我们把每一天1亿用户的上岸状态都用bitmap的形式存进了redis,那要获取某一天id为88000的用户是否活跃,直接使用getbit下令:

getbit 2020-01-01 88000 [时间复杂度为O(1)]

若是要统计某一天的所有的活跃用户数,使用bitcount下令,bitcount可以统计1的个数,也就是活跃用户数:

bitcount 2019-01-01 [时间复杂度为O(N)]

浏览器如何执行JS

若是要统计某一段时间内的活跃用户数,需要用到bitop下令。这个下令提供四种位运算,AND(与)(OR)或XOR(亦或)NOT(非)。我们可以对某一段时间内的所有key举行OR(或)操作,或操作出来的位图是0的就代表这段时间内一次都没有上岸的用户。那只要我们求出1的个数就可以了。以下例子求出了2019-01-01到2019-01-05这段时间内的活跃用户数。

bitop or result 2019-01-01 2019-01-02 2019-01-03 2019-01-04 2019-01-05 [时间复杂度为O(N)]

bitcount result

从时间复杂度上说,无论是统计某一天,照样统计一段时间。在现实测试时,基本上都是秒出的。相符我们的预期。

3

bitmap可以很好的知足一些需要纪录大量而简朴信息的场景。所占空间十分小。通常来说使用场景分2类:

1.某一营业工具的横向扩展,key为某一个营业工具的id,好比纪录某一个终端的功效开关,1代表开,0代表关。基本可以无限扩展,可以纪录2^32个位信息。不外这种用法由于key上带有了营业工具的id,导致了key的存储空间大于了value的存储空间,从空间使用角度上来看有一定的优化空间。

2.某一营业的纵向扩展,key为某一个营业,把每一个营业工具的id作为偏移量纪录到位上。这道面试题的例子就是用此法来举行解决。十分巧妙的行使了用户的id作为偏移量来找到相对应的值。当营业工具数目跨越2^32时(约等于42亿),还可以分片存储。

看起来bitmap完善的解决了存储和统计的问题。那有没有比这个加倍省空间的存储吗?

谜底是有的。

4

redis从2.8.9之后增加了HyperLogLog数据结构。这个数据结构,凭据redis的官网先容,这是一个概率数据结构,用来估算数据的基数。能通过牺牲准确率来削减内存空间的消耗。

我们先来看看HyperLogLog的方式

PFADD 添加一个元素,若是重复,只算作一个

PFCOUNT 返回元素数目的近似值

PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog

这很好明白,是不是。那我们就来看看同样是存储一亿用户的活跃度,HyperLogLog数据结构需要若干空间。是不是比bitmap加倍省空间呢。

我通过测试工程往HyperLogLog里PFADD了一亿个元素。通过rdb tools工具统计了这个key的信息:

Redis如何存储和计算一亿用户的活跃度

只需要14392 Bytes!也就是14KB的空间。对,你没看错。就是14K。bitmap存储一亿需要12M,而HyperLogLog只需要14K的空间。

这是一个很惊人的效果。我似乎有点不敢相信使用云云小的空间竟能存储云云大的数据量。

接下来我又放了1000w数据,统计出来照样14k。也就是说,无论你放若干数据进去,都是14K。

查了文档,发现HyperLogLog是一种概率性数据结构,在标准误差0.81%的前提下,能够统计2^64个数据。以是 HyperLogLog 适合在好比统计日活月活此类的对精度要不不高的场景。

HyperLogLog使用概率算法来统计聚集的近似基数。而它算法的最本源则是伯努利历程。

伯努利历程就是一个抛硬币实验的历程。抛一枚正常硬币,落地可能是正面,也可能是反面,二者的概率都是 1/2 。伯努利历程就是一直抛硬币,直到落地时泛起正面位置,并纪录下投掷次数k。好比说,抛一次硬币就泛起正面了,此时 k 为 1; 第一次抛硬币是反面,则继续抛,直到第三次才泛起正面,此时 k 为 3。

对于 n 次伯努利历程,我们会获得 n 个泛起正面的投掷次数值 k1, k2 … kn , 其中这里的最大值是k_max。

凭据一顿数学推导,我们可以得出一个结论: 2^{k_ max} 来作为n的估计值。也就是说你可以凭据最大投掷次数近似的推算出举行了几回伯努利历程。

5

虽然HyperLogLog数据类型这么牛逼,但终究不是正确统计。只适用于对精度要求不高的场景。而且这种类型无法得出每个用户的活跃度信息。究竟只有14K嘛。也不可能存储下那么多数目的信息。

总结一下:对于文章开头所提到的面试题来说,用bitmap和HyperLogLog都可以解决。

bitmap的优势是:异常平衡的特征,精准统计,可以获得每个统计工具的状态,秒出。瑕玷是:当你的统计工具数目十分十分伟大时,可能会占用到一点存储空间,但也可在接受范围内。也可以通过分片,或者压缩的分外手段去解决。

HyperLogLog的优势是:可以统计夸张到无法想象的数目,而且占用小的夸张的内存。 瑕玷是:建立在牺牲准确率的基础上,而且无法获得每个统计工具的状态。

我做了一个演示工程redis-bit,放在Gitee上,工程包罗了初始化大容量的数据。和划分使用bitmap和HyperLogLog举行用户活跃度的统计。最后通过http的方式举行输出。

工程接纳springboot+redisson客户端。所有的参数支持设置

Redis如何存储和计算一亿用户的活跃度

6

微信关注「jishuyuanren」获取更多干货,或者扫描以下二维码

Redis如何存储和计算一亿用户的活跃度

本文由博客群发一文多发等运营工具平台 OpenWrite 公布

原创文章,作者:admin,如若转载,请注明出处:https://www.2lxm.com/archives/23389.html