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 投票数
文章评分

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

原文链接:https://lrting.top/backend/10734/

(0)
上一篇 2022-11-08 22:24
下一篇 2022-11-09 22:23

相关推荐

订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x