共计 3563 个字符，预计需要花费 9 分钟才能阅读完成。
作者：铂赛东 \
链接：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 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！
