告别内存浪费！利用Roaring Bitmap解决Redis稀疏数据处理

在介绍Roaring Bitmap之前，先看看bitmap的大致原理以及利用bitmap存储数据存在什么问题。

BitMap作为redis四种特殊的数据类型之一，常用于二值状态（也就是要么是0，要么是1，只有两种状态 ）统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；

BitMap原理概述：

Bitmap，即位图，是一串连续的二进制数组（0和1），可以通过偏移量（offset）定位元素。BitMap通过最小的单位bit来进行0/1的设置，表示某个元素的值或者状态。

Bitmap不是一个独立的数据结构，底层其实是一个字符串，利用字符串进行位操作。而String 类型是会保存为二进制的字节数组，所以，Redis 就把字节数组的每个 bit 位利用起来，用来表示一个元素的二值状态，你可以把 Bitmap 看作是一个 bit 数组。因此，在BitMap中存储数据只需要根据数据值大小得到偏移量，再把对应偏移位置元素置为1即可。

而在redis中，字符串最大长度为512MB，因此BitMap的最大偏移量（offset）就是：8 * 1024 * 1024 * 512 -1= 2^32-1。

所以，决定BitMaps实际占用空间的就是BitMap中偏移量的最大值！占用字节数计算：(max_offset/8)+1

这里为什么要+1 ？如下图，如果偏移量为8，那么实际会占用2个字节，因此要+1。

（1byte=8bit, 1kb=1024byte, 1MB=1024kb）

所以可以发现，如果我们想使用BitMap表示用户的登录状态或者一个帖子的用户点赞结合，就会以用户ID作为偏移量存储至BitMap，那么当用户ID很大而BitMap内数据又很稀疏，比如一个BitMap就存储了一个用户ID为10000的数据，就占用了((10000/8)+1)字节=1.22kb这么大的内存！这是极其浪费的！

因此，Roaring Bitmap就是为了解决这个问题而来的。RoaringBitmap是一种高效压缩位图，在2016年提出。

Roaring Bitmap实现思路：

简单来说，就是将32位的int类型数据进行高16位、低16位划分，高16位就被划分成2^{16=65536个大桶，低16位也被划分成2}16=65536个小桶。当我们要存储或者查询某个数k时，就可以根据k的高16位定位到其中一个大桶，然后利用低16位定位到这个大桶的某一个小桶。

但是小桶也有三种不同类型：

• arraycontainer(数组容器)

  就是直接采用数组来存储低16位数据。在java中直接使用short数组存储（为什么用short，因为高16位已经在大桶中表示了呀，小桶只需用2字节存储即可）。由于short数据类型占用2字节，因此n个数据就占用 2*n字节。而ArrayContainer规定最大存储数据量为4096，因此ArrayContainer存满了就会占用4096 * 2byte = 8kb的内存。

• bitmapcontainer(位图容器)

  bitmapcontainer其实也很简单，顾名思义，其实他就是一个BitMap，用来存储低16位数据，因此最多站哟个2*16 bit=8kb的内存。所以当数据量小于4096时，使用ArrayContainer比较合适，当数据量大于等于4096时，使用BitMapContainer更佳。

• runcontainer(行程步长容器)

  runContainer中的Run指的是行程长度压缩算法(Run Length Encoding)，对连续数据有比较好的压缩效果。它的原理是，对于连续出现的数字，只记录初始数字和后续数量。即：

  对于数据集：5，会压缩位5, 0

  对于数据集：5, 6, 7, 8, 9, 10，会压缩位5, 5

  对于数据集：5, 7, 9, 11, 12，会压缩位5, 0, 7, 0, 9, 0, 11, 1

  所以，对于低16位的存储，最理想的情况就是所有数据都连续，那就只需要存储2个short类型数据，只占用4字节。最坏的情况就是0~65535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个short，128kb。

所以不同小桶占用内存为：

Roaring Bitmap测试

这里直接引入RoaringBitmap以及redis依赖，也可以在redis中安装RoaringBitmap。

    <dependency>
        <groupId>org.roaringbitmap</groupId>
        <artifactId>RoaringBitmap</artifactId>
        <version>0.9.16</version>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis</artifactId>
    </dependency>

配置redis:

spring:
  redis:
    host: 127.0.0.1
    port: 6379
    database: 0
    password: 密码

创建 RedisTemplate Bean：

@Configuration
public class RedisConfig {

    @Bean
    public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory connectionFactory) {
        RedisTemplate<String, Object> template = new RedisTemplate<>();
        template.setConnectionFactory(connectionFactory);
        template.setKeySerializer(new StringRedisSerializer());
        template.setValueSerializer(new GenericJackson2JsonRedisSerializer());
        return template;
    }
}

测试分别在BitMap和RoaringBitmap中存储10000个0~10000000之间的随机数，他们分别占用多大空间：

@SpringBootTest
class DemoApplicationTests {

    @Autowired
    private RedisTemplate redisTemplate;

    @Test
    void test()  {
        String key = "bitmapKey";
        RoaringBitmap roaringBitmap = new RoaringBitmap();
        for(int i=0; i<10000; i++){
            int num = new Random().nextInt(10000000);
            // 添加到roaringBitmap
            roaringBitmap.add(num);
            // 同样添加到Bitmap，进行对比
            redisTemplate.opsForValue().setBit(key, num, true);
        }
        int total = roaringBitmap.getSizeInBytes();
        System.out.println("RoaringBitmap 大小：" + total/1024 + "kb");
    }
}

RoaringBitmap占用：20kb

BitMap占用：1835064 / 1024 = 1792kb

RoaringBitmap缩小了将近90倍的占用空间。

总结

• Bitmap 是“简单粗暴”的解决方案，适合小范围密集数据。
• Roaring Bitmap 通过分桶和动态容器设计，在稀疏数据场景下实现内存和性能的平衡，是海量数据处理的更优选择。