使用Bitmap优化倒排索引的存储空间
简介
使用RoaringBitMap代替java.util.BitSet或HashSet，作为倒排索引key-value键值对中的value，减少内存占用，提高取交集的效率。
背景介绍
广告单元拥有很多兴趣标签，如下：
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的整数倍）。
如果我们有1亿广告单元，仅仅存储1亿个Long类型的id就需要2个多GB的内存，这还不算因为不同广告单元有相同的标签，所以id肯定会重复。所以在1亿数据量的情况下，仅仅存储id的内存消耗就会大于2GB。
改进
如何改进呢？
在java有位图的原生实现，即java.util.BitSet类。我们使用BitSet代替HashSet存储广告单元id，倒排索引的数据类型就像下面这样了：
private static final Map<String, BitSet>
但是其实还有进一步的优化空间，那就是使用RoaingBitmap。
为了减少内存缓存所消耗的内存空间大小，ElasticSearch 没有使用单纯的数组和 bitset 来存储 posting list，而是使用要压缩效率更高的 Roaring Bitmap。
Bitmap 比较适用于数据分布比较稠密的存储场景中，对于原始的 Bitmap 来说，若要存储一个 uint32 类型数据，这就需要 2 ^ 32 长度的 bit 数组，通过计算可以发现(2 ^ 32 / 8 bytes = 512MB)，一个普通的 Bitmap 需要耗费 512MB 的存储空间。如果我们只存储几个数据的话依然需要占用 512M 的话，就有些浪费空间了，因此我们可以采用对位图进行压缩的 RoaingBitmap，以此减少内存和提高效率。
既然这样，说明我们还有进一步的优化空间。别的先不说，我直接引入依赖：
<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 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
小问题
写到这我有个小问题，如何把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的位转换为了一个整数列表，并打印输出。您可以根据自己的需求修改代码以适应您的应用程序。
没毛病，完全满足了我们的要求。
然后还有一个小问题。因为我们刚才提到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