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

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

图 1：

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

图 2：

预备知识

  在介绍 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 中，由于数组五中的最大值为 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：

图 5：

  测试二：

图 6：

图 7：

  测试三：

图 8：

图 9：

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

• 蓝色曲线 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：

  先说明下上图的一些内容，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来了解其中的一个实现。