Redis去重计数的四种实现方式
前言
博客还是要写的, 知识还是要整理的. 不常用的东西不整理, 到最后就只剩下一个名词.
正文
日常开发经常是有计数功能, 譬如统计一个商品的访问次数 访问人数等, 那就来聊聊实现计数的 Redis 的实现方法.
计数分为去重以及非去重两种, 非去重计数没有太多可谈的, 直接使用 incr 指令, 简单高效.
这里用商品访问人数的列子详细说下去重计数.
-
Set集合
利用集合的去重功能,存入用户 ID, 使用 sCard 来返回人数.
优点: 拓展性强. 可以同时实现记录商品的访问人的ID, 以及计算访问相同商品的用户等需求. 毕竟的产品的想法就是小孩子的脸和六月份的天, 给自己留条后路
缺点: 太过耗费空间. -
HyperLogLog
Redis 在 2.8.9 版本添加了 HyperLogLog 结构. 它使用基数统计算法, 最多占用 12kb 的存储空间就可以完成海量的去重统计.
但是它是模糊计数, 牺牲了准确度, 误差率约为 0.81%. 很多场景不能使用.
这里附上两个链接, 对 HyperLogLog 实现原理感兴趣的话可以看一看
HyperLogLog算法论文
外国技术大佬做的HyperLogLog的视图工具
优点: 极其节省空间
缺点: 不精准 -
位图(bitmap)
位图可以使用一个位来表示一个用户ID, 如果一个用户ID是4字节，那么使用位图就只需要占用 1/32 的空间就可以完成精确计数.
但位图只能使用连续的整数 ID, 假如用户 ID 是字符串组成, 那么必须建立一个映射. 但也是值得的, 完成映射之后, 接下来的其它统计都可以使用, 数字做统计, 无疑是比字符串要方便.
而且位图还可以使用 AND 来计算两个商品的访问人数, 来替代 Set, 非常推荐使用位图.
位图虽然好, 但也不是没有缺点. 它是密集位图. 假如某个商品, 只有一个新用户访问(新用户一般 ID 很大), 那这个位图只有最后一位是 1, 前面全是 0, 但它依然会占用全部的内存空间.
优点: 精准计数, 节省空间, 可拓展性强
缺点: 密集位图, 如果商品访问量差别悬殊, 访问量低的位图浪费空间 -
咆哮位图(RoaringBitmap)
咆哮位图是稀疏位图, 就是解决密集位图可能出现的浪费空间的情况.
所谓的稀疏位图, 就是把大位图分块, 如果整个块都是 0, 那么就不用存了. 而且整个块只有极少数的 1, 只需要存储所有位是 1 的偏移量, 也就是一个整数列表, 只有块的位 1超过一定的阈值, 才会转为密集存储.
同时还可以提升 AND OR 运算的效率. 毕竟之前是需要计算整个位图, 现在只需要计算部分块. 甚至快特别稀疏, 计算的只是一个很小的整数列表. 这就是利用代码逻辑的复杂度, 同时换取了空间和时间.
除此之外, 因为块的大小是 8kb, 所以能完美利用 CPU 的一级缓存, 效率很高.
但是原生 Redis 不支持咆哮位图, 想使用只能自己安装这个拓展.
附上链接: 咆哮位图拓展.
里面还有一些性能对比, 即使不打算安装, 也可以进去看一下
优点: 稀疏存储下, 空间相比位图更加节省, 计算效率更高
缺点: 密集存储下, 划分太多的块, 反而减低了效率.
end.