关于java:基于Redis分布式BitMap的应用

一、序言

在理论开发中经常遇到如下需要：判断以后元素是否存在于已知的汇合中，将已知汇合中的元素保护一个 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]。

// 测试 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);
}

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

如果汇合中最大值为 100000000 , 则所占用的内存空间为 11MB
如果汇合中最大值为 500000000 , 则所占用的内存空间为 59MB
如果汇合中最大值为 1000000000, 则所占用的内存空间为 119MB
如果汇合中最大值为 2147483647, 则所占用的内存空间为 255MB

当汇合中数据增长到 10 亿 条时，应用 BItMap 最大占用内存约为255MB，而应用 HashSet 增长到3.8GB。

2、命令行操作 BitMap

应用 Redis 命令行可间接操作 BitMap，将 offset 地位的值标注为 1，则示意以后数据存在。默认状况下未标注的地位值为 0。

# 默认位不赋值为 0，当数据存在于汇合中，将对应位赋值为 1
SETBIT key offset value
# 查看对应位数据是否存在（1 示意存在，0 示意不存在）GETBIT key offset

3、客户端操作 BitMap

这里提供一个 SpringBoot 生态的 RedisUtils 工具类，外部封装操作 Redis BitMap 的工具办法。

// 将以后地位标记为 true
RedisUtils.setBit(BIT_MAP_KEY, orderId, true);
// 获取指定地位的值（对应数值是否存在）RedisUtils.getBit(BIT_MAP_KEY, orderId)

上述工具类的依赖如下，如果找不到 Jar 包，请间接应用 Maven 原始仓库源，阿里云尚未同步实现。

<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 站，本文珍藏在博客天地。