阅读 279

Redis bitmaps

认真写文章,用心做分享。

个人网站:yasinshaw.com

公众号:xy的技术圈

前面的文章介绍了Redis的五种最常用的对象及其底层的数据结构。这篇文章主要介绍一下一个不那么常用,却非常适用于一些特殊场景的对象:bitmaps。

面临的问题

先考虑几个常见的场景:

  • 查询今天登陆的用户数量
  • 查询今天有哪些用户登录了
  • 查询某个用户是否点赞过某篇文章
  • 查询某个用户是否连续两天都登陆
  • 查询点赞过文章A且点赞过文章B的用户

这些需求可以使用数据库来实现,使用一些日志表,再通过SQL查询出来。但这样会浪费大量的磁盘空间,而且性能还很低。在数据量比较大的情况下,使用数据库来查询分析会非常慢。

这里要感谢我们计算机的科学家大佬们,发明了一种数据结构可以用来解决这类问题。它就是BitMap。也就是这篇文章主要介绍的Redis bitmaps底层使用的数据结构。

《编程珠玑》中第一篇讲的就是使用BitMap来排序大文件里面的数据。在一些面试里也会有类似的题目。

面试题目:一个10G的文件,里面全部是自然数,一行一个,乱序排列,对其排序。在32位机器上面完成,内存限制为2G。

LeetCode上有一个算法题,也是可以使用BitMap来解决:

算法题目:从0到n之间取出n个不同的数,找出漏掉的那个。注意:你的算法应当具有线性的时间复杂度。你能实现只占用常数额外空间复杂度的算法吗?

BitMap原理

BitMap其实是一个数据结构,它是利用了位运算的高性能,来存储和计算一些信息。接下来我们来介绍一下BitMap的原理。

BitMap是基于bit位的位置来记录信息的。比如我们现在有一个8位的BitMap。最开始时,所有位上都是0。

0, 0, 0, 0, 0, 0, 0, 0

然后有这么一个需求:假设今天有id为1,2,4,7这四个用户登录了我们的系统,我们想要把这个登录信息记录下来,就只需要在相应的位置标记为1就行了:

1, 1, 0, 1, 0, 0, 1, 0

这个时候,你想知道id为7的用户今天是否登录过系统,就只需要去看这个BitMap里面第7位是不是1就可以了。

可以看到,如果你使用一个list或者set来存的话,如果一个id是一个byte,占8位(真实情况可能是long类型,占64位),那8个id就要占64位,而使用BitMap只需要占用8位。同理,如果我们的id字段占了64位,那就可以节省64倍的空间。而且,可以利用位运算的特性,来快速实现统计、并集、交集等操作。

看过文章A的人有:1, 2, 4, 7:

1, 1, 0, 1, 0, 0, 1, 0

看过文章B的人有:1, 3, 4, 8:

1, 0, 1, 1, 0, 0, 0, 1

看过文章A且看过文章B的人有:

1, 1, 0, 1, 0, 0, 1, 0

&

1, 0, 1, 1, 0, 0, 0, 1

=

1, 0, 0, 1, 0, 0, 0, 0

得到看过文章A且看过文章B的人有:1, 4

上面的例子只能放8位,如果我的id是9怎么办?

BitMap是一个一个上面这样的数据来组成的。你可以使用一个可以扩容的整数数组来做,比如long数组。所以可以无限扩展。

如果id比较稀疏怎么办?

比如我要存入的id可能是1,101,1001这种比较稀疏的,如果用BitMap就会浪费一些空间。虽然现在开源的一些实现可以通过记录偏移量来解决这个问题,但也会因为频繁的分裂影响性能。这种场景下,其实不建议使用BitMap

有兴趣的同学可以了解一下谷歌开源的EWAHCompressedBitMap,它解决了输入稀疏的问题。

BitMap实现

因为笔者主要熟悉Java语言,所以介绍一下Java语言对BitMap的实现。

JDK提供了一个BitMap的实现,叫BitSet,位于java.util包下。其底层使用的是一个long类型的数组,一个long代表一个word。但BitSet没有解决上面提到的输入稀疏的问题。谷歌开源的EWAHCompressedBitMap解决了输入稀疏的问题。

Redis提供了bitmaps对象。其实是使用的string对象,底层使用了我们上篇文章提到的SDS。所以会有512M的最大限制,即最多能存2^32个数据。如果你的id是long类型的,占64位,那可以使用两个bitmaps来存

由SDS的底层实现可知,它是可以扩容和缩容的,但是如果输入比较稀疏,仍然会浪费大量的内存。所以如果输入很稀疏,也不建议使用Redis的bitmaps。

Redis bitmaps基本操作

carbon 6.png

总结

Redis提供了bitmaps对象。它在某些场景下可以节省空间,并显著提升性能。但如果输入比较稀疏(比如网站注册用户有1亿,但每天只有10万用户登录),那还不如使用set。

另外一方面,输入只能是整形。如果是字符串类型的,就没法使用这个数据结构了。

关注公众号:xy的技术圈

关注下面的标签,发现更多相似文章
评论