哪些网站可以做移动端模板,做网站比较好的公司有哪些,南昌网站设计有限公司,排行前十装修公司1前段时间#xff0c;在网上看到一道面试题#xff1a;如何用redis存储统计1亿用户一年的登陆情况#xff0c;并快速检索任意时间窗口内的活跃用户数量。觉得很有意思#xff0c;就仔细想了下 。并做了一系列实验#xff0c;自己模拟了下 。还是有点收获的#xff0c;现整…1前段时间在网上看到一道面试题如何用redis存储统计1亿用户一年的登陆情况并快速检索任意时间窗口内的活跃用户数量。觉得很有意思就仔细想了下 。并做了一系列实验自己模拟了下 。还是有点收获的现整理下来。和大家一起分享。Redis是一个内存数据库采用单线程和事件驱动的机制来处理网络请求。实际生产的QPS和TPS单台都能达到3,4W读写性能非常棒。用来存储一些对核心业务弱影响的用户状态信息还是非常不错的。对于这题有2个重要的点需要考虑1.如何用合适的数据类型来存储1亿用户的数据用普通的字符串来存储肯定不行。经过查看一个最简单的kv(key为aaavalue为1)的内存占用发现为48byte。假设每个用户每天登陆需要占据1对KV的话那一亿就是(48*100000000)/1024/1024/10244.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 ---- 00001setbit abc 2 1 ---- 00101GETBIT语法GETBIT key offset例如getbit abc 5 ---- 1getbit abc 1 ---- 0bitmap的其他命令还有bitcountbitcountbitposbitop等命令。都是对位的操作。因为bitmap的每一位只占据1bit的空间 所以利用这个特性我们可以把每一天作为keyvalue为1亿用户的活跃度状态。假设一个用户一天内只要登录了一次就算活跃。活跃我们就记为1不活跃我们就记为0。把用户Id作为偏移量(offset)。这样我们一个key就可以存储1亿用户的活跃状态。我们再来算下这样一个位图结构的值对象占据多少空间。每一个位是1bit一亿用户就是一亿bit。8bit1Byte100000000/8/1024/102411.92M我用测试工程往一个key里通过lua塞进了1亿个bit然后用rdb tools对内存进行统计实测如下一天1亿用户也就消耗12M的内存空间。这完全符合要求。1年的话也就4个G。几年下来的话redis可以集群部署来进行扩容存储。我们也可以用位图压缩算法对bitmap进行压缩存储。例如WAHEWAHRoaring Bitmaps。这个以后可以单独拉出来聊聊。我们把每一天1亿用户的登陆状态都用bitmap的形式存进了redis那要获取某一天id为88000的用户是否活跃直接使用getbit命令getbit 2020-01-01 88000 [时间复杂度为O(1)]如果要统计某一天的所有的活跃用户数使用bitcount命令bitcount可以统计1的个数也就是活跃用户数bitcount 2019-01-01 [时间复杂度为O(N)]如果要统计某一段时间内的活跃用户数需要用到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从时间复杂度上说无论是统计某一天还是统计一段时间。在实际测试时基本上都是秒出的。符合我们的预期。3bitmap可以很好的满足一些需要记录大量而简单信息的场景。所占空间十分小。通常来说使用场景分2类1.某一业务对象的横向扩展key为某一个业务对象的id比如记录某一个终端的功能开关1代表开0代表关。基本可以无限扩展可以记录2^32个位信息。不过这种用法由于key上带有了业务对象的id导致了key的存储空间大于了value的存储空间从空间使用角度上来看有一定的优化空间。2.某一业务的纵向扩展key为某一个业务把每一个业务对象的id作为偏移量记录到位上。这道面试题的例子就是用此法来进行解决。十分巧妙的利用了用户的id作为偏移量来找到相对应的值。当业务对象数量超过2^32时(约等于42亿)还可以分片存储。看起来bitmap完美的解决了存储和统计的问题。那有没有比这个更加省空间的存储吗答案是有的。4redis从2.8.9之后增加了HyperLogLog数据结构。这个数据结构根据redis的官网介绍这是一个概率数据结构用来估算数据的基数。能通过牺牲准确率来减少内存空间的消耗。我们先来看看HyperLogLog的方法PFADD 添加一个元素如果重复只算作一个PFCOUNT 返回元素数量的近似值PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog这很好理解是不是。那我们就来看看同样是存储一亿用户的活跃度HyperLogLog数据结构需要多少空间。是不是比bitmap更加省空间呢。我通过测试工程往HyperLogLog里PFADD了一亿个元素。通过rdb tools工具统计了这个key的信息只需要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的方式进行输出。工程采用springbootredisson客户端。所有的参数支持配置分享上面是本人在学习路上整理的一些比较干货的java资料如果有需要的兄弟可以先关注我私信我回复【资料】即可。
