DocValues 压缩算法

DocValues 用于根据 docId 快速获取字段值，往往整个字段值都存于内存中，因此，需要采用压缩算法来减少内存占用。压缩算法往往要兼顾压缩率和解压速度，为了追求最大的压缩率和最大的解压速度，往往不同的数据会使用不同的压缩算法。DocValues 就是这样，根据不同的数据特点以及用户选择，融合的多种压缩算法。我们以 NumericDocValues 为例详细讲解 DocValues 的压缩算法，代码参见 Lucene54DocValuesConsumer 和 Lucene54DocValuesProducer 两个类

压缩算法

预处理

首先，初始化两个输出文件流 meta 和 data，meta 用于存放元数据，data 存放实例数据。

然后，在确定采用什么压缩算法前，压缩程序会对数据进行一个评估，得到几个参数

• count：值个数

• minValue：最小值

• maxValue：最大值

• gdc：最大公约数

• missingCount：缺失值个数

• zeroCount：零值个数

• uniqueValues：唯一值列表（收集过程中大于 255 个则清空掉，不在收集）

具体算法

压缩格式

根据预处理得到的参数可以确定采用什么压缩格式，并在 meta 中记录下来，目前有以下几种

• CONST_COMPRESSED：

只有一个常量值和空值的情况下采用这种格式。这里的常量值不能为 0，因为，这里空值用 0 来代替了。

这种格式很简单，直接把该常量值写入 meta 中，解压时，直接读取 meta 中的常量即可。

• SPARSE_COMPRESSED

值比较稀疏的时候（missingCount / count >= 0.99）采用这种格式。

这种格式，把存在值的 docId 写到 meta 中，然后把过滤掉了空值的值列表当成一个字段进行压缩(递归调用压缩函数，重新进行预处理，采用合适的压缩算法进行压缩)

• TABLE_COMPRESSED

唯一值小于等于 256 个，且需要的位数比 DELTA_COMPRESSED 少则采用这种格式。

这种格式，把这些唯一值放到一个数组中，排好序，然后把唯一值写到 meta 中，把每个文档的值在数组中的下标写到 data 中即可。

为什么唯一值小于等于 256 个才采用这种格式呢，原因是 256 在一个 byte 的数值范围内，

综合考虑 meta 中要记录的唯一值不能太多，以及 data 解压速度，大于 256 个值采用这种格式不太合适。

• GCD_COMPRESSED

最大公约数不等于 1，且需要的位数比 DELTA_COMPRESSED 少则采用这种格式。

这种格式，把最小值、公约数写到 meta 中，然后用差值压缩，差值除于公约数，减小值的大小，再写到 data 中。

解压时，差值乘以公约数，加上最小值即可得到原始值。

• DELTA_COMPRESSED

差值格式，上面几种压缩方式不满足，则采用这种格式。

这种格式，把最小值写到 meta 中，用值减去最小值，得到差值，写到 data 中。

data 的压缩算法

上面各种格式中，写到 data 的无论是差值、数组下标，都需要进行压缩存储。

在 lucene 中是用 packing integers 来压缩的，简单来说就是初始化一个 long 数组，根据要存储的值的大小，把每个

long 拆成多个固定大小的合适的块，每块存一个数值。比如要存储的一组数的最大值为 18，二进制是 10010，占 5 个 bit，

则一个 long(64bit)就可以拆分为 12 个块，可以存储 12 个值。而用计算机的固定数据类型，就算用最小的数据类型 byte，

64 个 bit 的代价，也只能存储 8 个值。一个 long 拆分为 12 个块，也还有 4 个 bit 浪费掉了，还有一种实现方式，块不限制在一个 long 里面，

这种方式没有存储的浪费，但是解压性能会差一些，如图，i3、i7 这两个块不在一个 long 里面。