PackedInts(二)

  本文承接PackedInts(一),继续介绍剩余的内容。

压缩实现

  在上一篇文章中,我们介绍了Lucene 7.5.0中PackedInts提供的几种压缩实现,如下所示:

表1:

数据分布 是否有填充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

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

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

什么是可接受的开销acceptableOverheadRatio

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

数组一:

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

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

为什么要使用acceptableOverheadRatio

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

图1:

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

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

acceptableOverheadRatio的取值范围是什么

  Lucene提供了以下几种取值:

表2:

acceptableOverheadRatio源码中的描述
7At most 700% memory overhead, always select a direct implementation.
0.5At most 50% memory overhead, always select a reasonably fast implementation
0.25At most 25% memory overhead
0No 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来了解其中的一个实现。

结语

  

点击下载附件