前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >基于Redis分布式BitMap的应用

基于Redis分布式BitMap的应用

原创
作者头像
赛先生和泰先生
发布2022-03-04 09:41:28
1.1K0
发布2022-03-04 09:41:28
举报
文章被收录于专栏:Java知识图谱

一、序言

在实际开发中常常遇到如下需求:判断当前元素是否存在于已知的集合中,将已知集合中的元素维护一个HashSet,使用时只需耗时O(1)的时间复杂度便可判断出结果,Java内部或者Redis均提供相应的数据结构。使用此种方式除了占用内存空间外,几乎没有其它缺点。

当数据量达到亿级别时,内存空间的占用显著表现出来,BitMap便是解决此类问题的一种途径。

二、BitMap结构

1、内存消耗分析

Redis BitMap能够存储的数据范围为[0,2^32-1],超过Integer.MAX_VALUE上界值。

为了简化讨论,假设讨论的集合元素的范围为[0,Integer.MAX_VALUE],可以是其中的任何一个数。

使用HashSet数据结构占用内存空间仅与集合中的元素数量(N)相关。当集合中元素数量为N时,所需的内存空间大概为N*4/1024/1024MB,1亿条数据约占内存空间381MB

基于Redis的BitMap所占用的空间大小不与集合中元素数量相关,与集合中元素的最大值直接相关,因此BitMap所占用的内存空间范围为[N / 8 / 1024 / 1024,Integer.MAX_VALUE / 8 / 1024 / 1024]

代码语言:java
复制
// 测试1亿、5亿、10亿、Integer.MAX_VALUE
List<Integer> items = Arrays.asList(100000000, 500000000, 1000000000, Integer.MAX_VALUE);
for (Integer item : items) {
    int size = item / 8 / 1024 / 1024;
    System.out.printf("如果集合中最大值为%-10s,则所占用的内存空间为%3sMB%n",item, size);
}

这里给出了一组测试参考数据

代码语言:text
复制
如果集合中最大值为100000000 ,则所占用的内存空间为 11MB
如果集合中最大值为500000000 ,则所占用的内存空间为 59MB
如果集合中最大值为1000000000,则所占用的内存空间为119MB
如果集合中最大值为2147483647,则所占用的内存空间为255MB

当集合中数据增长到10亿条时,使用BItMap最大占用内存约为255MB,而使用HashSet增长到3.8GB

2、命令行操作BitMap

使用Redis命令行可直接操作BitMap,将offset位置的值标注为1,则表示当前数据存在。默认情况下未标注的位置值为0。

代码语言:shell
复制
# 默认位不赋值为0,当数据存在于集合中,将对应位赋值为1
SETBIT key offset value
# 查看对应位数据是否存在(1表示存在,0表示不存在)
GETBIT key offset
3、客户端操作BitMap

这里提供一个SpringBoot生态的RedisUtils工具类,内部封装操作Redis BitMap的工具方法。

代码语言:java
复制
// 将当前位置标记为true
RedisUtils.setBit(BIT_MAP_KEY, orderId, true);
// 获取指定位置的值(对应数值是否存在)
RedisUtils.getBit(BIT_MAP_KEY, orderId)

上述工具类的依赖如下,如果找不到Jar包,请直接使用Maven原始仓库源,阿里云尚未同步完成。

代码语言:html
复制
<dependency>
    <groupId>xin.altitude.cms</groupId>
    <artifactId>ucode-cms-common</artifactId>
    <version>1.4.3</version>
</dependency>
4、时间与空间复杂度

BitMap的存储与取值时间复杂度为O(1),根据数值可直接映射下标。

BitMap占用内存空间复杂度为O(n),与集合中元素的最大值正相关,不是集合中元素的数量。

三、BitMap应用

1、回避缓存穿透

缓存穿透是指当前请求的数据在缓存中不存在,需要访问数据库获取数据(数据库中也不存在请求的数据)。缓存穿透给数据库带来了压力,恶意缓存穿透甚至能造成数据库宕机。

使用BitMap动态维护一个集合,当访问数据库前,先查询数据的主键是否存在集合中,以此作为是否访问数据库的依据。

BitMap新增数据或者移除数据属于轻量级操作,检查操作的准确度依赖于动态集合维护的闭环的完整性。比如向数据库增加数据时需要向BitMap中添加数据,从数据库中删除数据需要从BitMap中移除数据。如果要求严格的检查可靠性,则可以单独维护一个分布式定时任务,定期更新BitMap数据。

2、与布隆过滤器的区别

布隆过滤器与BitMap有相似的应用场景,但也有一定的区别。给定一个数,BitMap能准确知道是否存在于已知集合中;布隆过滤器能准确判断是否不在集合中,却不能肯定存在于集合中。

BitMap增加或者移除数据时间复杂度为O(1),方便快捷。布隆过滤器新建容易,剔除数据操作比较繁琐。

在一些需要精确判断的场景,优先选择BitMap,比如判断手机号是否已经注册。

四、小结

Redis BitMap不是一种新的数据结构,是利用字符串类型做的一层封装,看起来像一种新型数据结构。BitMap不像一种技术,更像是算法,在时间复杂度和空间复杂度之间寻找平衡点。

BitMap其它应用场景比如签到打卡,统计在线人数等等。


喜欢本文点个♥️赞♥️支持一下,如有需要,可通过微信dream4s与我联系。相关源码在GitHub,视频讲解在B站,本文收藏在博客天地

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、序言
  • 二、BitMap结构
    • 1、内存消耗分析
      • 2、命令行操作BitMap
        • 3、客户端操作BitMap
          • 4、时间与空间复杂度
          • 三、BitMap应用
            • 1、回避缓存穿透
              • 2、与布隆过滤器的区别
              • 四、小结
              相关产品与服务
              云数据库 Redis
              腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档