Lucene 源码系列——DirectWriter&&DirectReader

原文:https://www.amazingkoala.com.cn/Lucene/2019/1205/115.html

阅读本篇文章需要前置内容BulkOperationPacked,下文中会列出在文章 BulkOperationPacked 中涉及的代码,但是不会展开介绍。

  DirectWriter&&DirectReader 两个类用来处理 long 类型的数据集(数组类型),其中 DirectWriter 用来在写数据时使用 BulkOperationPacked 将 long 类型的数据转换成 byte 类型,而 DirectReader 则是将 byte 类型的数据恢复成 long 类型。使用 byte 类型数据存储的组件都可以使用 DirectWriter&&DirectReader 实现压缩存储,比如以字节为单位存储索引文件内容的 Directory

压缩实现

  在 BulkOperation 中,根据 bitPerValue 的值,对应的压缩实现不尽相同,但是 DirectWriter 只支持下列的 bitPerValue:

final static int SUPPORTED_BITS_PER_VALUE[] = new int[] {
    1, 2, 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64
};

bitPerValue 是什么

  使用 BulkOperation 提供的压缩实现,要求数据集中的所有数据按照固定位数存储,固定位数即 bitPerValue。

bitPerValue 怎么计算

  选取数据集中的最大值,它的有效数据占用的 bit 位个数为 bitPerValue。

  例如有下面的数据集:

数组一:

    long []values = {2, 278, 23};

  数组一中的元素对应的二进制表示如下所示:

表一:

数组元素 二进制
2 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000010
278 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00010110
23 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00010111

  数组一中的最大值为 278,它的有效数据占用的 bit 位个数如表一中红色标注所示,共 9 位,故 bitPerValue 的值为 9,并且数值 2、23 都使用 9 个 bit 来存储。

待处理的数据集的 bitPerValue 不是 SUPPORTED_BITS_PER_VALUE 中的一员怎么办

  如果待处理的数据集的 bitPerValue 不属于 SUPPORTED_BITS_PER_VALUE 数组中的数组元素之一,那么另下一个比 bitPerValue 大的数组元素作为新的 bitPerValue。例如表一中,bitPerValue 的值为 9,那么重新另 bitPerValue 为 12,即,数值 2、278、23 都使用 12 个 bit 位存储。

为什么只支持 SUPPORTED_BITS_PER_VALUE 中的 bitPerValue

  因为这些 bitPerValue 对应的压缩实现是读写性能最佳的,衡量读写性能的指标如下

  • 写性能:写入一个数值需要涉及的 block 个数,越少性能越高
  • 读性能:读取一个数值对应的 block 的个数,越少性能越高,另外字节对齐的数据读取性能越高,否则需要额外计算字节首地址

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

数组二:

    long []values = { 120, 69, 23, 25};

  数组一中的元素对应的二进制表示如下所示:

表二:

数组元素 二进制
120 00000000_00000000_00000000_00000000_00000000_00000000_00000000_01111000
69 00000000_00000000_00000000_00000000_00000000_00000000_00000000_01000101
23 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00010111
25 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00011001

  表二中,数组二的 bitPerValue 为 7,如果我们使用该 bitPerValue,即每个数值使用 7 个 bit 位存储,那么处理结束后如下所示,同时给出 bitPerValue 为 8 时的结果:

图 1:

  从图 1 可以看出,在读取阶段,如果 bitPerValue 为 7,那么需要两个字节才能读取到 69、23、25 的值,另外需要计算首地址跟偏移才能找到在字节中的起始位置,而如果 bitPerValue 为 8,那么只需要一个字节即可,并且不需要计算偏移地址。很同时也可以看出,这是空间换时间的设计。

  我们再看下写阶段的情况,从图 1 同样能明显看出 bitPerValue 为 7 时,写入一个数值需要跨越 2 个 block,我们从代码中也可以看出其性能差异的原因:

图 2:



2.png

  图 2 截取自 BulkOperationPacked,bitPerValue 为 7 时,相比较 bitPerValue 为 8 时需要执行额外的位移操作,如第 31 行代码所示。更重要的是当处理相同数量的数值时,需要更多的遍历次数,在文章 BulkOperationPacked 中,为了简化介绍 BulkOperationPacked 的原理,我们并没有介绍如何计算遍历次数,只是简单的将待处理的数据集数量作为遍历次数,即图 8 中第 31 行的 values.length,在源码中,图 1 中的第 8 行代码应该是这样的:

图 3:

3.png

  遍历次数是如何计算的

  在后续介绍 PackedWriter 的文章中我们再讲述这个问题,本篇文章中我们只要知道 bitPerValue 为 7 时,相比较 bitPerValue 为 8 在处理相同数量的数据集时,需要更多的遍历次数。

如何选择 bitPerValue 的值作为 SUPPORTED_BITS_PER_VALUE 中的一员

  我们再次列出 SUPPORTED_BITS_PER_VALUE 中的成员:

final static int SUPPORTED_BITS_PER_VALUE[] = new int[] {
    1, 2, 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64
};

  我们先看下 bitPerValue 大于等于 8 的情况,当 bitPerValue 为 8、16、24、32、40、48、56 时,这几个值总能保证待处理的数值能按照字节对齐(8 的倍数)处理,故读写性能是很快的,我们想要了解的是,bitPerValue 的值不是 8 的倍数的情况下,为何还将 12、20、28、48 作为 SUPPORTED_BITS_PER_VALUE 的成员。

  这是一种出于空间使用率与读写性能的折中处理,例如 bitPerValue 的值为 9 时,如果只能选择 16,那么每一个数值的额外空间开销为(16 - 9)/ 16 = 0.4375,故我们需要在(8,16)的区间内找出一个空间开销与读写性能兼顾的 bitPerValue,那么 12 是最好的选择,因为它的读写性能在这个区间内是最佳的,同时额外空间开销降低到 (12 - 9)/ 12 = 0.25。

为什么在区间(8,16)中选取 bitPerValue 的值是 12:

  首先在这个区间内 bitPerValue 的写性能是差不多的,因为它们的值不是 8(一个字节)的倍数,都需要跨 block 存储,所以我们看它们在读性能的差异性,同样地,由于不能保证每个数值都是按照字节对齐存储,故我们只能通过平均读取一个数值需要计算首地址的次数来判断读的性能:

  我们有如下的数据集数组三:

数组三:

    long[] values = {69, 25, 261, 23};

  数组三中的元素对应的二进制表示如下所示:

表三:

数组元素 二进制
69 00000000_00000000_00000000_00000000_00000000_00000000_00000000_01000101
25 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00011001
261 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000101
23 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00010111

  数组三中,最大值为 261,故此时的 bitPerValue 为 9,我们用 bitPerValue 为 9 以及 bitPerValue 为 12 来处理数组三的数据,如下所示:

图 4:

4.png

  从图 4 可见,如果需要读取 261 的数值,在 bitPerValue=9 中,由于 261 对应的首地址没有按照字节对齐,那么需要额外的计算出首地址的值,因为读取 byte[ ]数组总是按字节读取,而在 bitPerValue=12 的情况下,则不需要计算

  • bitPerValue=9:每读取 8 个数值,需要计算 7 次首地址,平均读取一个数值需要计算 0.875 次首地址
  • bitPerValue=12:每读取 2 个数值,需要计算 1 次首地址,平均读取一个数值需要计算 0.5 次首地址

  故当 bitPerValue=12 时,读性能较高。

  如果我们连续读取 byte[ ]数组中的元素,在 bitPerValue=9 的情况下,第一个数值是不需要计算首地址的,而下一个不需要计算首地址的数值是第 9 个,所以每读取 8 个数值,需要计算 7 次首地址。其实我们只需要计算 8 跟 bitPerValue 的最小公约数就能计算出不同的 bitPerValue 对应的平均读取一个数值需要计算首地址的次数。

  下图是在区间(8, 16)之间,各个 bitPerValue 的取值对应的平均读取一个数值需要计算首地址的次数:

表 4:

bitPerValue 平均读取一个数值需要计算首地址的次数
9 7/8 = 0.875
10 3/4 = 0.6
11 7/8 = 0.875
12 1/2 = 0.5
13 7/8 = 0.85
14 3/4 = 0.6
15 7/8 = 0.875

  由表 4 可以看出,当 bitPerValue=12 时,平均读取一个数值需要计算首地址的次数的最少,所以读的性能最高。

结语

  在应用方面,在索引阶段生成索引文件。dvm、dvd 时,就使用这两个类来实现数据压缩。


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