RoaringBitmap介绍（中文翻译）

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

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

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

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

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>

0 0 投票数

文章评分