Lucene 源码系列—— PackedInts

原文地址: https://www.amazingkoala.com.cn/Lucene/yasuocunchu/2019/1217/118.html

  为了能节省空间,Lucene 使用 PackedInts 类对 long 类型的数据进行压缩存储,基于内存使用率(memory-efficient)跟解压速度(读取速度),提供了多种压缩方法,我们先通过类图预览下这些压缩方法。

图 1:

1.png

  图 1 中 MutableImpl 类是 PackedInts 的内部类,其中 Packed64SingleBlock 是一个抽象类,它的实现如下所示:

图 2:

2.png

预备知识

  在介绍 PackedInts 提供的压缩方法前,我们先介绍下几个预备知识。

数据类型压缩

  根据待处理的数据的取值范围,选择占用字节更小的数据类型来表示原数据类型。

数组一:

    long[] oldValues = {10, 130, 7};

  long 类型的数组,每个数组元素都占用 8 个字节,压缩前存储该数组需要 24 个字节(只考虑数组元素的大小),即三个数组元素的占用字节总数,它们的二进制表示如下所示:

表一:

数组元素 二进制
10 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00001010
102 00000000_00000000_00000000_00000000_00000000_00000000_00000000_01100110
130 00000000_00000000_00000000_00000000_00000000_00000000_00000000_10000010

  从表一可以看出,这三个值有效的数据位最多只在低 8 位,故可以使用字节数组来存储这三个数据:

数组二:

    byte[] newValues = {10, 130, 7};

  那么压缩后的数组只需要占用 3 个字节。

固定位数按字节存储

  在数据类型压缩的前提下,待处理的数据集使用相同的固定的 bit 位存储,bit 位的个数由数据集中的最大值,它的数据有效 bit 位决定,例如有如下的数组:

数组三:

    long[] oldValues = {10, 290, 7};

  三个数组元素的二进制表示如下所示:

表二:

数组元素 二进制
10 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00001010
290 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00100010
7 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000111

  上表中,最大的数组元素是 290,它的有效数据位为低 16 位,它是所有数组元素中有效数据位占用 bit 位最多的,那么在进行数据类型压缩后,新的数据类型既要保证数值 290 的精度,同时还要使得占用字节最小,故只能选择 short 类型的数组,并且数组元素 10、7 都需要跟 290 一样,需要存储 2 个字节的大小,尽管它们两个只需要 1 个字节就可以表示:

数组四:

   short[] newValues = {10, 290, 7};

  压缩后的数组只需要占用 6 个字节。

为什么要选用固定字节

  能让所有数据用同一种数据类型表示,并且任何数据不会出现精度缺失问题,尽管压缩率不是最高,但是读取速度是非常快的。

固定位数按位存储

  上文中,数组三在使用了 固定位数按字节存储 以及 数据类型压缩 之后,生成了数组四,此时三个数组元素的二进制表示如下所示:

表三:

数组元素 二进制
10 00000000_00001010
290 00000001_00100010
7 00000000_00000111

  表三中,我们可以发现,在使用 固定位数按字节存储 的前提下,仍然有高 7 个 bit 位是无效数据,那么可以通过固定位数按位存储的方式来进一步提高压缩率,该方法不会使用数据类型的压缩,只是将所有数据的有效数据位进行拼接,当拼接后的 bit 位达到 64 位时,即生成一个 long 值,剩余的有效数据继续拼接并生成一个新的 long 值,例如我们有下面的数组:

数组五:

    long[] oldValues = {10, 290, 7, 18, 32, 23, 45, 35, 89, 291};

  在使用固定位数按位存储之后,生成的新的数组如下所示:

数组六:

    long[] newValues = {380695872922475610, 2534621417262022656};

图 3:

3.png

  图 3 中,由于数组五中的最大值为 291,它的有效数据占用 9 个 bit 位,所以其他的数组元素也使用 9 个 bit 位表示,那么就可以使用一个 long 类型的来表示 7 个完整的数值,由于 7 个数值一共占用 7*9 =63 个 bit 位,剩余的 1 个 bit 位为数组元素 35 的最高位 0(红色虚线左侧的 0),35 的低 8 位只能存放到第二个 long 值中,故在读取阶段,需要读取两个 long 才能得到 35 这个数值,那么原本需要 10*8=80 个字节存储,现在只需要 2*8=16 个字节。

block

  block 在源码中用来描述一块数据区域,在这块数据可以存放一个或多个数值,block 使用数组来实现,也就是说数组的一个数组元素称为一个 block,并且这个数组元素可以存放一个或多个数值。

  例如上文中的数组三,它是一个 short 类型的数组,它有三个 block,并且每一个 block 中存放了一个数值,而在数组六中,它有两个 block,第一个 block 存放了 7 个完整的数值,以及 1 个不完整的数值(7*9 + 1),第二个 block 最多可以存放 6 个完整的数值,以及 2 个不完整的数值(8 + 6*9 + 2 = 64)。

压缩实现

  图 1 跟图 2 展示的是 PackedInts 提供的所有压缩实现,我们先对这些实现进行分类:

表 4:

数据分布 是否有填充bit 是否单block单值 实现类
一个block Direct8
Direct16
Direct32
Direct64
Packed64SingleBlock1
Packed64SingleBlock2
Packed64SingleBlock3
Packed64SingleBlock4
Packed64SingleBlock5
Packed64SingleBlock6
Packed64SingleBlock7
Packed64SingleBlock8
Packed64SingleBlock9
Packed64SingleBlock10
Packed64SingleBlock12
Packed64SingleBlock16
Packed64SingleBlock21
Packed64SingleBlock32
两个block Packed64
三个block - Packed8ThreeBlocks
Packed16ThreeBlocks

  我们先对表 4 的内容做一些介绍:

  • 数据分布:该列名描述的是一个数值的信息是否可能分布在不同的 block 中,例如图 3 中的数值 35,它用 9 个 bit 位来描述,其中最高位存储在第一个 block,而低 8 位存储在第二个 block 中,又比如上文中的数组二跟数组四,每个数值都存储在一个 block 中
  • 是否有填充 bit:例如图 3 中的数值 35,在第一个 block 中存储了 7 个完整的数据后,该 block 仅剩余 1 个 bit 位,如果该 bit 位不存储数值 35 的最高位,那么该 bit 位就是填充 bit,也就是说,如果使用了填充 bit,那么一个 block 中不会有不完整的数值,当然内存使用率会降低
  • 是否单 block 单值:该列描述的是一个 block 中是否只存储一个数值,例如数组 4,每一个 block 只存储一个 short 类型的数值,例如数组六,第一个 block 存储了 7 个完整的数值以及一个不完整的数值

  接下来我们先介绍下每种实现中使用哪种数据类型来存储数据,然后再介绍下为什么 Lucene 提供这么多的压缩,以及如何选择,最后再介绍几个例子

Direct

  该系列分别使用不同的数据类型来实现一个 block 存储一个数值,它们属于上文中提到的 固定位数按字节存储

  • Direct8:使用 byte[]数组存储
  • Direct16:使用 short[]数组存储
  • Direct32:使用 int[]数组存储
  • Direct64:使用 long[]数组存储

Packed8ThreeBlocks、Packed16ThreeBlocks

  该系列使用三个 block 来存储一个数值:

  • Packed8ThreeBlocks:使用 byte[]数组存储
  • Packed16ThreeBlocks:使用 short[]数组存储

Packed64SingleBlock

  该系列使用一个 block 来存储一个或多个数值,并且可能存在填充 bit,它们属于上文中提到的 固定位数按位存储,所有的实现使用 long[]数组存储。

Packed64

  Packed64 使用一个 block 来存储一个或多个数值,不会存在填充 bit,它属于上文中提到的 固定位数按位存储,使用 long[]数组存储。

为什么 Lucene 提供这么多的压缩实现:

  这些压缩实现分别提供不同的内存使用率以及解压速度(读取速度),下面几张图是 Lucene 的核心贡献者 Adrien Grand 提供的测试数据,它使用了三台机器来测试压缩实现的压缩性能以及解压性能:

  测试一:

图 4:



4.png

图 5:

5.png

  测试二:

图 6:

6.png

图 7:

7.png

  测试三:

图 8:

8.png

图 9:

9.png

  图中的曲线对应的压缩实现如下所示:

  • 蓝色曲线 Packed:Packed64
  • 红色曲线 Single:Packed64SingleBlock*
  • 黄色曲线 Three:Packed8ThreeBlocks、Packed16ThreeBlocks
  • 黄色曲线 Direct:Direct*

  我们先观察下 Direct*与 Packed64 的读取速度,这两种压缩实现无论在哪一台都表现出两个极端,即 Packed64 读取最慢,而 Direct*读取最快,而从表 4 我们可以看出,Packed64 使用连续的 bit 位存储数据,待存储的数据如果没有突兀的数据,那么相对于 Direct*能有很高的压缩率,例如存储连续递增的文档号,并且只存储文档差值,那么只需要 1 个 bit 位就能表示一个文档号。

  在 Lucene 4.0.0 版本之前,只有 Direct8、Direct16、Direct32、Direct64、Packed64、Packed32(该压缩算实现考虑的是对 32 位平台,我们这里不作介绍)可供选择,在这个版本中,当计算出待处理的数据集中最大值的数据有效位的 bit 个数后,我们称之为 bitsPerValue,如果 bitsPerValue 为 8,那么选择 Direct8,如果 bitsPerValue 为 32,那么选择 Direct32,以此类推,即如果 bitsPerValue 不是 8、16、32、64,那么就选择 Packed64。

  也就说在 Lucene 4.0.0 版本之前,只有 bitsPerValue 是 8、16、32、64 时,才能使用 Direct*,我们考虑这么一种假设,如果 bitsPerValue 的值是 21,并且使用 Direct32 存储,那么我们就能获得较好的性能,但是这么做会造成(32-21)/ 32 = 35% 的空间浪费,故 Adrien Grand 使用 long 类型数组来存储,那么 64 个 bit 位的 long 类型可以存放 3 个 bitsPerValue 为 21 的数值,并且剩余的一个 bit 位作为填充 bit,该填充 bit 不存储有效数据,那么我们只要读取一个 block,就能读取/写入一个数值,而 Packed64 需要读取两个 block,因为读取/写入的数值可能分布在两个 block 中,那么自然性能比 Packed64 好,而这正是空间换时间的设计,每存储 3 个 bitsPerValue 为 21 的数值,需要 1 个 bit 额外的空间开销,即每个数值需要 1/3 个 bit 的额外开销。

  上述的原内容见:https://issues.apache.org/jira/browse/LUCENE-4062

  上述方式即 Packed64SingleBlock*压缩实现,bitsPerValue 为 21 的数值即对应 Packed64SingleBlock21,同样 Adrien Grand 基于这种方式做了测试,他通过 10000000 个 bitsPerValue 为 21 的数值使用 Packed64SingleBlock21 进行压缩存储,相比较使用 Packed64,额外空间开销为 2%,但是速度提升了 44%,故使用了 Packed64SingleBlock*之后,bitsPerValue 不为 8、16、32、64 的部分 bitsPerValue 通过空间换时间的思想,提高了性能,在图 4~图 9 中也能通过曲线看出来。

为什么只有部分 bitsPerValue 实现了 Packed64SingleBlock*压缩

  从表 4 中可以发现,只有 bitsPerValue 为 1,2,3,4,5,6,7,8,9,10,12,16,21,32 实现了 Packed64SingleBlock*压缩,我们通过一个 block 可存放的数值个数来介绍原因:

  • 1 个数值:bitsPerValue 为 64 才能使得额外空间开销最小,每个数值的空间开销为(64-64*1)/(1)= 0,它其实就是 Direct64
  • 2 个数值:bitsPerValue 为 32 才能使得额外空间开销最小,每个数值的空间开销为(64-32*2)/(2)= 0
  • 3 个数值,bitsPerValue 为 21 才能使得额外空间开销最小,每个数值的空间开销为(64-21*3)/(3)= 0.33
  • 4 个数值,bitsPerValue 为 16 才能使得额外空间开销最小,每个数值的空间开销为(64-16*4)/(4)= 0
  • 5 个数值,bitsPerValue 为 12 才能使得额外空间开销最小,每个数值的空间开销为(64-12*5)/(5)= 0.8
  • 6 个数值,bitsPerValue 为 10 才能使得额外空间开销最小,每个数值的空间开销为(64-10*6)/(6)= 0.66
  • 7 个数值,bitsPerValue 为 9 才能使得额外空间开销最小,每个数值的空间开销为(64-9*7)/(7)= 0.14
  • 8 个数值,bitsPerValue 为 8 才能使得额外空间开销最小,每个数值的空间开销为(64-8*8)/(8)= 0
  • 。。。 。。。

  可以看出那些实现了 Packed64SingleBlock*压缩的 bitsPerValue 都是基于空间开销下的最优解。

压缩实现

我们接着介绍如何选择这些压缩实现:

  在源码中 Lucene 会根据使用者提供的三个参数来选择其中一种压缩实现,即 PackedInts 类中的 getMutable(int valueCount, int bitsPerValue, float acceptableOverheadRatio)方法,参数如下所示:

  • valueCount:描述待处理的数据集的数量
  • bitsPerValue:描述待处理的数据集中的最大值,它的有效数据占用的 bit 个数
  • acceptableOverheadRatio:描述可接受的开销

什么是可接受的开销 acceptableOverheadRatio

  • bitsPerValue 描述了每一个数值占用的 bit 位个数,acceptableOverheadRatio 则是每一个数值额外的空间开销的比例,允许使用比 bitsPerValue 更多的 bit 位,我们称之为 maxBitsPerValue,来存储每一个数值,计算公式如下所示:
    int maxBitsPerValue = bitsPerValue + (int)(bitsPerValue * acceptableOverheadRatio)

  例如我们有以下的数据集:

数组一:

    long[] values = {3, 8, 7, 12, 18};

  该数组的 bitsPerValue 为 5,如果此时 acceptableOverheadRatio 的值为 7,那么 maxBitsPerValue = 5 + 5*7 = 40,即允许使用 40 个 bit 位来存储数组一。

  当然 Lucene 并不会真正的使用 40 个 bit 来存储一个数值,maxBitsPerValue 只是用来描述使用者可接受的额外开销的程度

为什么要使用 acceptableOverheadRatio

  使得在使用者可接受的额外开销前提下,尽量使用读写性能最好的压缩来处理,我们先看下源码中的部分代码截图:

图 1:

1.png

  先说明下上图的一些内容,actualBitsPerValues 的值在后面的逻辑中用来选择对应的压缩实现,actualBitsPerValues 与压缩实现的对应关系如下:

  • 8:Direct8
  • 16:Direct16
  • 32:Direct32
  • 64:Direct64
  • 24:Packed8ThreeBlocks
  • 48:Packed16ThreeBlocks
  • 随后先考虑是否能用 Packed64SingleBlock*(红框表示),最后才考虑使用 Packed64

  在第 250 行的 if 语句判断中,如果 bitsPerValues 的值小于等于 8,并且 maxBitsPerValue 大于等于 8,那么就使用 Direct8 来处理,在文章 PackedInts(一)中我们知道,Direct*的压缩实现是读写性能最好的,可以看出来 acceptableOverheadRatio 是空间换时间的设计思想,并且压缩实现的选择优先级如下所示:

    Direct* > Packed*ThreeBlocks > Packed64SingleBlock* > Packed64

acceptableOverheadRatio 的取值范围是什么

  Lucene 提供了以下几种取值:

表 2:

acceptableOverheadRatio 源码中的描述
7 At most 700% memory overhead, always select a direct implementation.
0.5 At most 50% memory overhead, always select a reasonably fast implementation
0.25 At most 25% memory overhead
0 No memory overhead at all, but the returned implementation may be slow.

acceptableOverheadRatio 的值为 7

  如果 acceptableOverheadRatio 的值为 7,那么不管 bitsPerValue 是区间[1, 64]中的哪一个值,总是会选择 Direct*压缩实现。例如 bitsPerValue 的值为 1,那么 maxBitsPerValue = 1 + 1*7 = 8,那么根据图 1 中第 250 行的判断,就会使用 Direct8 来处理,意味着每一个数值使用 8 个 bit 位存储,由于每一个数值的有效数据的 bit 位个数为 1,那么每个数值的额外开销为 7 个 bit,即表 2 中描述的 At most 700% memory overhead。

acceptableOverheadRatio 的值为 0.5

  如果 acceptableOverheadRatio 的值为 0.5,那么总能保证选择除了 Packed64 的其他任意一个压缩实现,它们是比较快(reasonably fast)的实现。

acceptableOverheadRatio 的值为 0.25

  相对 acceptableOverheadRatio 的值为 0 的情况获得更多的非 Packed64 的压缩实现。

acceptableOverheadRatio 的值为 0

  没有任何额外的空间开销,虽然读写性能慢,但是因为使用了固定位数按位存储,并且没有填充 bit(见 PackedInts(一)),所以有较高的压缩率。

Packed64 的实现

  表 4 中的所有压缩实现,除了 Packed64,其他的实现逻辑由于过于简单就不通过文章介绍了,而 Packed64 的实现核心是 BulkOperation,BulkOperation 中根据 bitsPerValue 从 1 到 64 的不同取值一共有 64 种不同的逻辑,但他们的实现原理是类似的,故感兴趣的同学可以看文章 BulkOperationPacked 来了解其中的一个实现。


本文地址:https://www.6aiq.com/article/1586653737632
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出