RoaringBitmap介绍（中文翻译）

原地址：https://github.com/RoaringBitmap/RoaringBitmap

Bitsets，也称为bitmaps，通常用作快速数据结构。 不幸的是，它们可能会使用过多的内存。 作为补偿，我们经常使用compressed bitmaps。

Roaring bitmaps是compressed bitmaps，其性能往往优于传统的compressed bitmaps，例如 WAH、EWAH 或 Concise。

Roaring bitmaps在许多重要的应用程序中都能很好地工作，包括：

• Apache Spark,
• Apache Hive,
• Apache Tez,
• Apache Kylin,
• Apache CarbonData,
• Netflix Atlas,
• OpenSearchServer,
• zenvisage,
• Jive Miru,
• Tablesaw,
• Apache Hivemall,
• Gaffer,
• Apache Pinot and
• Apache Druid.

YouTube SQL 引擎 Google Procella 使用 Roaring bitmaps进行索引。 Apache Lucene 使用 Roaring bitmaps，尽管它们有自己独立的实现。 Solr 和 Elastic 等 Lucene 的衍生产品也使用 Roaring bitmaps。 其他平台，如 Whoosh、Microsoft Visual Studio Team Services (VSTS) 和 Pilosa 也将 Roaring bitmaps与他们自己的实现一起使用。 您可以在 InfluxDB、Bleve、Cloud Torrent 等中找到 Roaring bitmaps。

实现之间的互操作性有一个序列化格式规范。 我们有可互操作的 C/C++、Java 和 Go 实现。

此代码在 Apache 许可证 2.0 版 (AL2.0) 下获得许可。

什么时候应该使用bitmap？

集合是软件中的基本抽象。 它们可以以各种方式实现，如哈希集、树等。 在数据库和搜索引擎中，集合通常是索引的一个组成部分。 例如，我们可能需要维护一组满足某些属性的所有文档或行（由数字标识符表示）。 除了从集合中添加或删除元素外，我们还需要快速函数来计算交集、并集、集合之间的差等。

要实现一组整数，一个特别吸引人的策略是位图（也称为位集或位向量）。 使用 n 位，我们可以表示由 [0,n) 范围内的整数组成的任何集合：如果集合中存在整数 i，则第 i 位设置为 1。 商品处理器使用 W=32 或 W=64 位的字。 通过组合许多这样的词，我们可以支持较大的 n 值。 然后可以将交集、并集和差异实现为按位 AND、OR 和 ANDNOT 操作。 更复杂的集合函数也可以实现为按位运算。

当 bitset 方法适用时，它可以比其他可能的集合实现（例如，作为散列集）快几个数量级，同时使用更少的内存。

然而，一个位集，甚至是一个压缩的，并不总是适用的。 例如，如果你有 1000 个看起来很随机的整数，那么一个简单的数组可能是最好的表示。 我们将这种情况称为“稀疏”场景。

什么时候应该使用compressed bitmaps?

未压缩的 BitSet 会占用大量内存。 例如，如果您使用一个 BitSet 并将位置 1,000,000 的位设置为 true，那么您只有 100kB 多一点。 存储一位的位置超过 100kB。 即使您不关心内存，这也是一种浪费：假设您需要计算此 BitSet 与另一个在位置 1,000,001 为真的 BitSet 之间的交集，那么无论您喜欢它与否，您都需要遍历所有这些零。 这会变得非常浪费。

话虽如此，在某些情况下，尝试使用压缩位图确实是一种浪费。 例如，如果你有一个小的宇宙大小。 例如，您的位图表示 [0,n) 中的整数集，其中 n 很小（例如，n=64 或 n=128）。 如果您能够解压缩 BitSet 并且它不会占用您的内存，那么压缩位图可能对您没有用处。 事实上，如果您不需要压缩，那么 BitSet 提供了非凡的速度。

稀疏场景是另一个不应使用压缩位图的用例。 请记住，看起来随机的数据通常是不可压缩的。 例如，如果您有一小组 32 位随机整数，那么从数学上讲，每个整数使用远少于 32 位是不可能的，并且尝试压缩可能会适得其反。

Roaring 与其他替代品相比如何？

Roaring 的大多数替代方案是更大系列的压缩位图的一部分，这些位图是行程编码位图。 它们识别 1 或 0 的长序列，并用标记词表示它们。 如果您有 1 和 0 的本地混合，则使用未压缩的单词。

这个系列有很多格式：

• Oracle 的 BBC（字节对齐位图代码）在这一点上是一种过时的格式：虽然它可能提供良好的压缩，但由于过度分支，它可能比最近的替代方案慢得多。
• WAH（Word Aligned Hybrid）是 BBC 上的一种专利变体，可提供更好的性能。
• Concise 是专利 WAH 的一种变体。 在某些特定情况下，它的压缩效果比 WAH 好得多（最高可达 2 倍），但通常速度较慢。
• EWAH（Enhanced Word Aligned Hybrid）都没有专利，而且比上面所有的都快。 不利的一面是，它的压缩效果也不太好。 它更快，因为它允许某种形式的“跳过”未压缩的单词。 因此，尽管这些格式都不适合随机访问，但 EWAH 比其他格式更好。

这些格式存在一个大问题，但是在某些情况下可能会严重伤害您：没有随机访问。 如果要检查集合中是否存在给定值，则必须从头开始并“解压缩”整个事物。 这意味着如果你想将一个大集合与一个大集合相交，你仍然必须在最坏的情况下解压缩整个大集合……

Roaring解决了这个问题。 它以下列方式工作。 它将数据分成 216 个整数的块（例如，[0, 216)、[216, 2 x 216), …）。 在一个块中，它可以使用未压缩的位图、简单的整数列表或运行列表。 无论它使用什么格式，它们都允许您快速检查任何一个值的存在（例如，使用二进制搜索）。 最终结果是，Roaring 可以比 WAH、EWAH、Concise 等运行长度编码格式更快地计算许多操作……也许令人惊讶的是，Roaring 通常还提供更好的压缩比。

学术文章

• Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O’Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience 48 (4), 2018 arXiv:1709.07821
• Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience 46 (5), 2016.arXiv:1402.6407 This paper used data from http://lemire.me/data/realroaring2014.html
• Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience 46 (11), 2016. arXiv:1603.06549
• Samy Chambi, Daniel Lemire, Robert Godin, Kamel Boukhalfa, Charles Allen, Fangjin Yang, Optimizing Druid with Roaring bitmaps, IDEAS 2016, 2016. http://r-libre.teluq.ca/950/

代码示例

import org.roaringbitmap.RoaringBitmap;

public class Basic {

  public static void main(String[] args) {
        RoaringBitmap rr = RoaringBitmap.bitmapOf(1,2,3,1000);
        RoaringBitmap rr2 = new RoaringBitmap();
        rr2.add(4000L,4255L);
        rr.select(3); // would return the third value or 1000
        rr.rank(2); // would return the rank of 2, which is index 1
        rr.contains(1000); // will return true
        rr.contains(7); // will return false

        RoaringBitmap rror = RoaringBitmap.or(rr, rr2);// new bitmap
        rr.or(rr2); //in-place computation
        boolean equals = rror.equals(rr);// true
        if(!equals) throw new RuntimeException("bug");
        // number of values stored?
        long cardinality = rr.getLongCardinality();
        System.out.println(cardinality);
        // a "forEach" is faster than this loop, but a loop is possible:
        for(int i : rr) {
          System.out.println(i);
        }
  }
}

请查看示例文件夹以获取更多示例，您可以使用 ./gradlew :examples:runAll 运行这些示例，或者使用 ./gradlew :examples:runExampleBitmap64 等运行特定示例。

无符号整数

Java 缺少本机无符号整数，但整数在 Roaring 中仍被认为是无符号的，并根据 Integer.compareUnsigned 进行排序。 这意味着 Java 将对数字进行排序，如 0、1、…、2147483647、-2147483648、-2147483647、…、-1。 要正确解释，您可以使用 Integer.toUnsignedLong 和 Integer.toUnsignedString。

使用内存映射bitmaps

如果你想让你的位图位于内存映射文件中，你可以使用 org.roaringbitmap.buffer 包。 它包含两个重要的类，ImmutableRoaringBitmap 和 MutableRoaringBitmap。 MutableRoaringBitmaps 派生自 ImmutableRoaringBitmap，因此您可以在恒定时间内将 MutableRoaringBitmap 转换（转换）为 ImmutableRoaringBitmap。

不是 MutableRoaringBitmap 实例的 ImmutableRoaringBitmap 由 ByteBuffer 支持，这会带来一些性能开销，但具有额外的灵活性，即数据可以驻留在任何地方（包括 Java 堆之外）。

有时您可能需要使用驻留在磁盘上的位图（ImmutableRoaringBitmap 的实例）和驻留在 Java 内存中的位图。 如果知道位图会驻留在 Java 内存中，最好使用 MutableRoaringBitmap 实例，不仅可以修改，而且速度更快。 此外，由于 MutableRoaringBitmap 实例也是 ImmutableRoaringBitmap 实例，因此您可以编写大部分代码来期待 ImmutableRoaringBitmap。

如果您编写期望 ImmutableRoaringBitmap 实例的代码，而不尝试强制转换实例，那么您的对象将是真正不可变的。 MutableRoaringBitmap 有一个方便的方法 (toImmutableRoaringBitmap)，它是一个简单的转换回 ImmutableRoaringBitmap 实例的方法。从语言设计的角度来看，ImmutableRoaringBitmap 类的实例仅在按照 ImmutableRoaringBitmap 类的接口使用时是不可变的。鉴于该类不是最终的，可以通过其他接口修改实例。因此，我们不以纯粹的方式使用术语“不可变”，而是以实际的方式。

我们将 MutableRoaringBitmap 实例转换为 ImmutableRoaringBitmap 实例的设计动机之一是位图通常很大，或者用于要避免内存分配的上下文中，因此我们避免强制复制。如果需要混合和匹配 ImmutableRoaringBitmap 和 MutableRoaringBitmap 实例，则可以预期副本。

以下代码示例说明了如何从 ByteBuffer 创建 ImmutableRoaringBitmap。 在这种情况下，构造函数仅将元数据加载到 RAM 中，而实际数据是按需从 ByteBuffer 访问的。

        import org.roaringbitmap.buffer.*;

        //...

        MutableRoaringBitmap rr1 = MutableRoaringBitmap.bitmapOf(1, 2, 3, 1000);
        MutableRoaringBitmap rr2 = MutableRoaringBitmap.bitmapOf( 2, 3, 1010);
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        DataOutputStream dos = new DataOutputStream(bos);
        // If there were runs of consecutive values, you could
        // call rr1.runOptimize(); or rr2.runOptimize(); to improve compression
        rr1.serialize(dos);
        rr2.serialize(dos);
        dos.close();
        ByteBuffer bb = ByteBuffer.wrap(bos.toByteArray());
        ImmutableRoaringBitmap rrback1 = new ImmutableRoaringBitmap(bb);
        bb.position(bb.position() + rrback1.serializedSizeInBytes());
        ImmutableRoaringBitmap rrback2 = new ImmutableRoaringBitmap(bb);

或者，我们可以使用 serialize(ByteBuffer) 方法直接序列化为 ByteBuffer。

对 ImmutableRoaringBitmap 的操作，例如与、或、异或、翻转，将生成位于 RAM 中的 RoaringBitmap。 顾名思义，ImmutableRoaringBitmap 本身不能被修改。

这个设计灵感来自Druid。

可以在测试文件 TestMemoryMapping.java 中找到完整的工作示例。

请注意，您不应将 org.roaringbitmap 包中的类与 org.roaringbitmap.buffer 包中的类混用。 它们是不相容的。 然而，它们序列化到相同的输出。 org.roaringbitmap 包中的代码的性能通常是优越的，因为由于使用了 ByteBuffer 实例而没有开销。

Kryo

许多应用程序使用 Kryo 进行序列化/反序列化。 借助自定义序列化程序（Kryo 5），可以有效地将 Roaring 位图与 Kryo 一起使用：

public class RoaringSerializer extends Serializer<RoaringBitmap> {
    @Override
    public void write(Kryo kryo, Output output, RoaringBitmap bitmap) {
        try {
            bitmap.serialize(new KryoDataOutput(output));
        } catch (IOException e) {
            e.printStackTrace();
            throw new RuntimeException();
        }
    }
    @Override
    public RoaringBitmap read(Kryo kryo, Input input, Class<? extends RoaringBitmap> type) {
        RoaringBitmap bitmap = new RoaringBitmap();
        try {
            bitmap.deserialize(new KryoDataInput(input));
        } catch (IOException e) {
            e.printStackTrace();
            throw new RuntimeException();
        }
        return bitmap;
    }

}

64-bit integers (long)

尽管 Roaring Bitmaps 在设计时考虑了 32 位的情况，但我们对 64 位整数进行了扩展。 为此，我们提供了两个类：Roaring64NavigableMap 和 Roaring64Bitmap。

Roaring64NavigableMap 依赖于传统的红黑树。 键是代表最高有效 32 位元素的 32 位整数，而树的值是 32 位 Roaring 位图。 32 位 Roaring 位图表示一组元素的最低有效位。

较新的 Roaring64Bitmap 方法依赖于 ART 数据结构来保存键/值对。 密钥由最重要的 48 位元素组成，而值是 16 位 Roaring 容器。 它的灵感来自 Leis 等人的自适应基数树：主内存数据库的 ARTful 索引。 （ICDE ’13）。

    import org.roaringbitmap.longlong.*;

    // first Roaring64NavigableMap
    LongBitmapDataProvider r = Roaring64NavigableMap.bitmapOf(1,2,100,1000);
    r.addLong(1234);
    System.out.println(r.contains(1)); // true
    System.out.println(r.contains(3)); // false
    LongIterator i = r.getLongIterator();
    while(i.hasNext()) System.out.println(i.next());

    // second Roaring64Bitmap
    bitmap1 = new Roaring64Bitmap();
    bitmap2 = new Roaring64Bitmap();
    int k = 1 << 16;
    long i = Long.MAX_VALUE / 2;
    long base = i;
    for (; i < base + 10000; ++i) {
       bitmap1.add(i * k);
       bitmap2.add(i * k);
    }
    b1.and(bitmap2);

Range Bitmaps

RangeBitmap 是一种支持范围查询的简洁数据结构。 添加到位图中的每个值都与一个增量标识符相关联，并且查询会生成与满足查询的值相关联的标识符的 RoaringBitmap。 添加到位图中的每个值都是单独存储的，因此如果一个值被添加两次，它将被存储两次，如果该值小于某个阈值，则生成的 RoaringBitmap 中将至少有两个整数。

就时间和空间而言，提供最大值更有效。 如果您不知道最大值，请提供 Long.MAX_VALUE。 未签名的订单与图书馆的其他地方一样使用。

var appender = RangeBitmap.appender(1_000_000);
appender.add(1L);
appender.add(1L);
appender.add(100_000L);
RangeBitmap bitmap = appender.build();
RoaringBitmap lessThan5 = bitmap.lt(5); // {0,1}
RoaringBitmap greaterThanOrEqualTo1 = bitmap.gte(1); // {0, 1, 2}
RoaringBitmap greaterThan1 = bitmap.gt(1); // {2}

RangeBitmap 是可以写入磁盘和内存映射的：

var appender = RangeBitmap.appender(1_000_000);
appender.add(1L);
appender.add(1L);
appender.add(100_000L);
ByteBuffer buffer = mapBuffer(appender.serializedSizeInBytes());
appender.serialize(buffer);
RangeBitmap bitmap = RangeBitmap.map(buffer);

序列化格式使用 little endian 字节顺序。

Prerequisites

• Version 0.7.x requires JDK 8 or better
• Version 0.6.x requires JDK 7 or better
• Version 0.5.x requires JDK 6 or better

To build the project you need maven (version 3).

Maven

        <dependencies>
          <dependency>
            <groupId>org.roaringbitmap</groupId>
            <artifactId>RoaringBitmap</artifactId>
            <version>0.9.9</version>
          </dependency>
        </dependencies>

本文为从大数据到人工智能博主「xiaozhch5」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://cloud.tencent.com/developer/article/2165176