作者：铂赛东\
链接：https://www.jianshu.com/p/ee7...
1
前段时间，在网上看到一道面试题：
如何用redis存储统计1亿用户一年的登陆状况，并疾速检索任意工夫窗口内的沉闷用户数量。
觉得很有意思，就认真想了下 。并做了一系列试验，本人模仿了下 。还是有点播种的，现整顿下来。和大家一起分享。
Redis是一个内存数据库，采纳单线程和事件驱动的机制来解决网络申请。理论生产的QPS和TPS单台都能达到3,4W，读写性能十分棒。用来存储一些对外围业务弱影响的用户状态信息还是十分不错的。
对于这题，有2个重要的点须要思考：
1.如何用适合的数据类型来存储1亿用户的数据，用一般的字符串来存储必定不行。通过查看一个最简略的kv(key为aaa，value为1)的内存占用，发现为48byte。
假如每个用户每天登陆须要占据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亿用户的沉闷状态。
咱们再来算下，这样一个位图构造的值对象占据多少空间。每一个位是1bit，一亿用户就是一亿bit。8bit=1Byte
100000000/8/1024/1024=11.92M
我用测试工程往一个key里通过lua塞进了1亿个bit，而后用rdb tools对内存进行统计，实测如下：
一天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)]
如果要统计某一段时间内的沉闷用户数，须要用到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的信息：
只须要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的劣势是：能够统计夸大到无奈设想的数量，并且占用小的夸大的内存。 毛病是：建设在就义准确率的根底上，而且无奈失去每个统计对象的状态。
另外，关注公众号Java技术栈，在后盾回复：面试，能够获取我整顿的 Redis 系列面试题和答案，十分齐全。
近期热文举荐：
1.Java 15 正式公布， 14 个新个性，刷新你的认知！！
2.终于靠开源我的项目弄到 IntelliJ IDEA 激活码了，真香！
3.我用 Java 8 写了一段逻辑，共事直呼看不懂，你试试看。。
4.吊打 Tomcat ，Undertow 性能很炸！！
5.《Java开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞+转发哦！