使用Bitmap优化倒排索引的存储空间

ゝ一世哀愁。 2023-10-08 23:28 15阅读 0赞

## 简介 ##

使用`RoaringBitMap`代替`java.util.BitSet`或`HashSet`，作为倒排索引key-value键值对中的value，减少内存占用，提高取交集的效率。

## 背景介绍 ##

文章默认我们已经知道了倒排索引，倒排索引相关详见本人另一篇文章：[浅谈索引与搜索 - 掘金 (juejin.cn)][- _ _juejin.cn]。

广告单元拥有很多兴趣标签，如下：

id=1的广告单元的兴趣标签：游泳、射箭、溜冰
    id=2的广告单元的兴趣标签：游泳
    id=3的广告单元的兴趣标签：射箭、编程
    复制代码

构建倒排索引，如下：

游泳：1、2
    射箭：2、3
    溜冰：1
    编程：3
    复制代码

很自然我很会用一个`Map`维护`游泳 -> {1, 2}`这样一个映射关系，key为string，那么value是什么呢？我们也会很自然想到使用Set存储广告单元的id。所以我们的倒排索引的数据类型就是下面这样的了：

private static final Map<String, Set<Long>>
    复制代码

想想这样有什么问题？

我们的广告单元的id是Long类型的，如果数据量非常大呢？

我们都知道java中基础数据类型long的大小是8字节，但是Long对象的大小是24字节。

> #### 4.Long占用几个字节 ####
> 
> 答案：占用24个字节。 其中对象头12字节，实例数据long占用8字节，对齐填充4字节（必须是8的整数倍）。
> 
> [各种Java对象占用内存大小 - 简书 (jianshu.com)][Java_ - _ _jianshu.com]

如果我们有1亿广告单元，仅仅存储1亿个Long类型的id就需要2个多GB的内存，这还不算因为不同广告单元有相同的标签，所以id肯定会重复。所以在1亿数据量的情况下，仅仅存储id的内存消耗就会大于2GB。

## 改进 ##

如何改进呢？

如果你使用过Redis，你应该听说过`Bitset`（位图）这种数据类型。如果你还不了解，可以看本人这篇文章：[Reids的使用 | 社区项目 - 掘金 (juejin.cn)][Reids_ _ _ - _ _juejin.cn]，经典在Redis中使用位图统计DAU。

在java有位图的原生实现，即`java.util.BitSet`类。我们使用`BitSet`代替`HashSet`存储广告单元id，倒排索引的数据类型就像下面这样了：

private static final Map<String, BitSet>
    复制代码

--------------------

但是其实还有进一步的优化空间，那就是使用`RoaingBitmap`。

> 为了减少内存缓存所消耗的内存空间大小，ElasticSearch 没有使用单纯的数组和 bitset 来存储 posting list，而是使用要压缩效率更高的 Roaring Bitmap。
> 
> [为什么ElasticSearch比MySQL更适合全文索引 - 腾讯云开发者社区-腾讯云 (tencent.com)][ElasticSearch_MySQL_ - _-_ _tencent.com]

> Bitmap 比较适用于数据分布比较稠密的存储场景中，对于原始的 Bitmap 来说，若要存储一个 uint32 类型数据，这就需要 2 ^ 32 长度的 bit 数组，通过计算可以发现(2 ^ 32 / 8 bytes = 512MB)，一个普通的 Bitmap 需要耗费 512MB 的存储空间。如果我们只存储几个数据的话依然需要占用 512M 的话，就有些浪费空间了，因此我们可以采用对位图进行压缩的 RoaingBitmap，以此减少内存和提高效率。
> 
> [巧用RoaringBitMap处理海量数据内存diff问题\_Java\_得物技术\_InfoQ写作社区][RoaringBitMap_diff_Java_InfoQ]

既然这样，说明我们还有进一步的优化空间。别的先不说，我直接引入依赖：

<dependency>
        <groupId>org.roaringbitmap</groupId>
        <artifactId>RoaringBitmap</artifactId>
        <version>0.9.39</version>
    </dependency>
    复制代码

使用起来也很简单，跟java原生的位图可以无缝切换。这样我们的倒排索引就变成了下面这样：

private static final Map<String, RoaringBitmap>
    复制代码

到目前为止，我们所做的其实只是将倒排索引的key-value键值对中的value的数据类型，从`Set<Long>`升级为了`RoaringBitmap`，却为我们节约了大量的内存空间。但是其实好处还不只于此。

## 取交集 ##

在背景介绍中，我们提到过广告单元有兴趣标签，比如：游泳、射箭、溜冰、编程。但是其实广告单元还有地域标签，广告主们肯定希望自己的广告能够精准投放给自己的店所在的城市。这样就有如下倒排索引：

游泳：1、2
    射箭：2、3
    溜冰：1
    编程：3
    复制代码

北京：1、2、3
    上海：2、3
    深圳：3
    杭州：2、3
    复制代码

我们有一个用户，ta是一名喜欢游泳的杭州人，请问应该给ta推荐哪一条广告。

根据游泳拿到1、2两条广告，根据杭州拿到2、3两条广告，取交集后我们决定给该用户推送2号广告。

--------------------

因为使用了`Map`作为倒排索引，我们能以O(1)的时间复杂度拿到通过标签拿到广告单元id，但是因为有不同的标签类型的存在，所以我们还需要对通过不同标签拿到的广告单元id的集合取交集。

如果是我们之前使用`Set<Long>`的时候，取交集的时间消耗也不是个小数目。我们需要遍历集合大小较小的那一个`set`，时间复杂度为O(m)，其中m < n，核心代码如下：

for (Integer id : set1) {
        if (set2.contains(id)) {
            res.add(id);
        }
    }
    复制代码

而我们的`java.util.BitSet`取交集的源码如下：

public void and(BitSet set) {
        if (this == set)
            return;
    
        while (wordsInUse > set.wordsInUse)
            words[--wordsInUse] = 0;
    
        // Perform logical AND on words in common
        for (int i = 0; i < wordsInUse; i++)
            words[i] &= set.words[i];
    
        recalculateWordsInUse();
        checkInvariants();
    }
    复制代码

可以看到也需要遍历位，但是别忘了位图是位运算，效率巨高，几乎是碾压，测试代码如下：

Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    Set<Integer> res = new HashSet<>();
    BitSet bitSet1 = new BitSet();
    BitSet bitSet2 = new BitSet();
    for (int i = 0; i < 10000000; i++) {
        set1.add(i);
        set2.add(i);
        bitSet1.set(i);
        bitSet2.set(i);
    }
    
    long l1 = System.currentTimeMillis();
    for (Integer id : set1) 
        if (set2.contains(id)) 
            res.add(id);
    
    long l2 = System.currentTimeMillis();
    bitSet1.and(bitSet2);
    long l3 = System.currentTimeMillis();
    System.out.println("Set取交集："+  (l2 - l1));
    System.out.println("BitSet取交集："+  (l3 - l2));
    复制代码

在1千万的数据量下，`Set`取交集是秒级，而`java.util.BitSet`是毫秒级。

--------------------

如果我们使用`RoaringBitmap`，那会比`java.util.BitSet`更快。

> 对于 RoaingBitmap 本质上是将大块的 Bitmap 分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，RoaingBitmap 只需要去计算存在的一些块而不需要像 Bitmap 那样对整个大的块进行计算。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
> 
> [巧用RoaringBitMap处理海量数据内存diff问题\_Java\_得物技术\_InfoQ写作社区][RoaringBitMap_diff_Java_InfoQ]

## 小问题 ##

写到这我有个小问题，如何把`java.util.BitSet`的数据转存到List中进行后续的操作呢？

没关系，我们不会有人会，问问chat-GPT吧。

> 可以使用Java中的`BitSet`类来存储数字，并使用循环将其转换为`List<Integer>`。下面是一个示例代码：
> 
>     import java.util.*;
>     
>     public class BitSetToList {
>        public static void main(String[] args) {
>            BitSet bitSet = new BitSet(10);
>            bitSet.set(0);
>            bitSet.set(2);
>            bitSet.set(5);
>            bitSet.set(8);
>     
>            List<Integer> list = new ArrayList<>();
>            for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i+1)) {
>                list.add(i);
>            }
>            System.out.println(list);
>        }
>     }
>     复制代码
> 
> 在上面的代码中，我们创建了一个`BitSet`对象，并将其第0、2、5和8位设置为1。然后，我们通过循环将设置为1的位转换为整数，并将其添加到`List`对象中。使用`BitSet`的`nextSetBit()`方法可以获取下一个设置为1的位的索引。当返回值为-1时，表示没有更多的设置为1的位。最后，我们将`List`对象打印出来以查看结果。
> 
> 运行上述代码，将得到以下输出：
> 
>     [0, 2, 5, 8]
>     复制代码
> 
> 上述代码将4个设置为1的位转换为了一个整数列表，并打印输出。您可以根据自己的需求修改代码以适应您的应用程序。
> 
> [New chat (openai.com)][New chat _openai.com]

没毛病，完全满足了我们的要求。

--------------------

然后还有一个小问题。因为我们刚才提到id的类型是Long，但是`BitSet`和`RoaringBitmap`只提供了支持存储int类型的数据，我也没找到其他支持long类型的位图，也就是说咱们的id存不进去，人家只要int。有没有什么好方法呢？

我们都知道在java中int是32位，long是64位，那么2个int就是一个long了。我们可以使用2个int，一个存储long的高32位，一个存储long的低32位。我们使用`RoaringBitmap`举个例子，如果你想使用`BitSet`是一样的，代码如下：

RoaringBitmap highBits = new RoaringBitmap();
    RoaringBitmap lowBits = new RoaringBitmap();
    
    // 添加 long 类型的数
    long value = 123456789L;
    int high = (int) (value >>> 32);
    int low = (int) value;
    highBits.add(high);
    lowBits.add(low);
    
    // 判断某个 long 类型的数是否存在于位图中
    long checkValue = 987654321L;
    int checkHigh = (int) (checkValue >>> 32);
    int checkLow = (int) checkValue;
    boolean exist = false;
    
    if (highBits.contains(checkHigh) && lowBits.contains(checkLow)) {
        exist = true;
    }
    
    if (exist) {
        System.out.println("存在");
    } else {
        System.out.println("不存在");
    }
    复制代码

至此，我们倒排索引的数据类型就变成了下面的这个样子：

static final Map<String, List<RoaringBitmap>>
    复制代码

其中`List<RoaringBitmap>`只会存储两个`RoaringBitmap`，一个负责存储广告单元id的高32位，一个负责存储低32位。

作者：带姬仔  
链接：https://juejin.cn/post/7216915438298841146

[- _ _juejin.cn]: https://juejin.cn/post/7194865074073239589#heading-5
[Java_ - _ _jianshu.com]: https://link.juejin.cn?target=https%3A%2F%2Fwww.jianshu.com%2Fp%2F11aa390a2e97
[Reids_ _ _ - _ _juejin.cn]: https://juejin.cn/post/7119122261604302862#heading-7
[ElasticSearch_MySQL_ - _-_ _tencent.com]: https://link.juejin.cn?target=https%3A%2F%2Fcloud.tencent.com%2Fdeveloper%2Farticle%2F1789751
[RoaringBitMap_diff_Java_InfoQ]: https://link.juejin.cn?target=https%3A%2F%2Fxie.infoq.cn%2Farticle%2F716e7ec905e2f069b301c71a7
[New chat _openai.com]: https://link.juejin.cn?target=https%3A%2F%2Fchat.openai.com%2Fchat