索引文件的生成(十六)之dvm&&dvd(Lucene 8.4.0)
Lu Xugang Lv6

  在文章索引文件的生成(十五)之dvm&&dvd中,我们介绍了在索引(index)阶段收集文档的NumericDocValues信息的内容,随后在flush阶段,会根据收集到的信息生成索引文件.dvd&&.dvm。如果已经阅读了文章NumericDocValues,那么能快的理解本文的内容,注意的是那篇文章中,是基于Lucene 7.5.0,下文中的内容基于Lucene 8.4.0,不一致(优化)的地方会特别说明。

生成索引文件.dvd、.dvm之NumericDocValues的流程图

图1:

准备工作

图2:

  根据在索引阶段收集的文档的NumericDocValuses信息(见文章索引文件的生成(十五)之dvm&&dvd),在当前流程点需要执行一些准备工作,即计算出下面的信息:

  • gcd(greatest common divisor)
  • minMax和blockMinMax
  • uniqueValues
  • numDocsWithValue

  在流程点准备工作中,通过遍历每一个包含NumericDocValues信息的文档来完成上述信息的计算。

gcd(greatest common divisor)

  gcd即最大公约数,获得所有NumericDocValues的域值的最大公约数,根据数学知识可知,最大公约数的最小为1。

  为什么要计算gcd:

  在文章NumericDocValues中已经作出了解释,本文中再详细的介绍一次,其实目的很简单:降低存储开销。

  例如我们有以下的域值集合:

1
{150、140、135}

  上述三个域值的最大公约数为5,即gcd的值为5,按照下面的公式我们计算出编码后的域值:

1
(v - min) / gcd

  上述公式中,v为编码前的域值,min为域值集合中的最小值,在本例子中,min的值为135,编码后的域值集合如下所示:

1
{3, 1, 0}

  可见编码后的域值集合中,最大值为3,当使用固定位数按位存储(见文章PackedInts(一))时,只需要6个bit存储即可,在读取阶段,根据min、gcd的值就可以获得编码前的域值集合。

minMax、blockMinMax

  minMax跟blockMinMax在源码中都是类MinMaxTracker的对象,都是用来收集下面的信息:

  • min:域值集合中的最小值
  • max:域值集合中的最大值
  • numValues:域值集合中的元素数量
  • spaceInBits:存储域值占用的bit数量
    • spaceInBits的计算方式:(bitCount(max - min)) * num,其中num指的是域值的数量,bitCount( )方法描述的是域值占用的有效bit数量,例如bitCount(3) = 2,数值3的二进制为0b00000011,有效的bit数量为2个

  两个信息的区别在于,minMax收集的是域值集合中全量数据下的min、max、spaceInBits,而blockMinMax则是将域值集合分为N个block,每处理4096个域值就作为一个block,每个block单独收集min、max、spaceInBits。

  为什么要计算minMax、blockMinMax

  为了判断出使用单个block和多个block存储域值时,哪一种方式有更低的存储开销。

  例如我们有以下域值集合,为了便于描述,计算blockMinMax时,每处理3个域值就作为一个block。

图3:

  图2中,对于minMax,域值集合的全量数据下的min、max分别为1、18,并且有9个,那么spaceInBits = (bitCount(18 - 1)) * 9,数值17的二进制为0b00010001,有效的bit数量为5个,故spaceInBits的值为5*9 = 45。

图4:

  图3中,对于blockMinMax,域值集合被分为3个block,每个block的spaceInBits的和值作为blockMinMax的spaceInBits,故spaceInBits = (bitCount(2 -1)) * 3 + (bitCount(18 -16)) * 3 + (bitCount(8 -5)) * 3 = 3 + 6 + 9 = 18。

  源码中,如果blockMinMax和minMax的spaceInBits满足下面的条件,那么就使用多个block存储域值:

1
(double) blockMinMax.spaceInBits / minMax.spaceInBits <= 0.9

  显而易见,上述的例子将会使用多个block存储域值。当然了,当前的流程点是准备工作,仅仅判断出存储域值的方式,其具体的存储域值逻辑将在后面的流程中执行。

uniqueValues

  uniqueValues是一个Set<Long>对象,用来统计域值的种类,uniqueValues将在后续的流程点是否使用域值映射存储作为判断的依据,在本文中不展开介绍,我们只需要知道收集域值种类的时机点即可,例如图3中的域值集合,在执行完流程点准备工作后,uniqueValues中的内容如下所示:

1
{1, 2, 3, 5, 8, 16, 17, 18}

numDocsWithValue

  numDocsWithValue用来描述包含当前域名的文档数量,在后面的流程中它将作为一个判断条件,用于选择使用哪种数据结构来存储包含当前域的文档号集合。

写入文档号信息

图5:

  文档号信息包含两个信息:

  • 文档号的值信息:文档号的值将被写入到索引文件dvd中
  • 文档号的索引信息:文档号索引信息将被写入到索引文件.dvm中,在读取阶段根据文档号的索引信息来读取在索引文件.dvd中的文档号的值区间,下文中会详细说明

  另外根据在流程点准备工作中计算出的numDocsWithValue,对应有三种数据结构存储文档号索引信息。

0 < numDocsWithValue < maxDoc

  maxDoc的值为段中的文档数量,在下文中会介绍该值,如果numDocsWithValue的值在区间(0, maxDoc),文档索引信息将会被存储到索引文件.dvm中的DocIdIndex字段,文档号的值信息将被存储到索引文件.dvd中的DocIdData字段:

图6:

   图6中,文档号的索引信息包含offset跟length,它们描述了文档号的值信息在索引文件.dvd中的值区间,其他字段的解释见文章NumericDocValues,我们再看Lucene 8.4.0中的数据结构:

图7:

   在Lucene 8.4.0版本中,DocIdIndex字段中多了jumpTableEntryCount跟denseRankPower两个信息,在读取阶段,通过这两个信息能获得查找表(lookup table)的信息,jumpTableEntryCount跟denseRankPower以及查找表的概念在系列文章IndexedDISI已经介绍,这里不赘述。

numDocsWithValue == 0

  如果numDocsWithValue == 0,那么将固定的信息写入到索引文件.dvm中,固定信息在索引文件.dvm中的位置如下所示:

图8:

  图8中,offset跟length被置为固定信息,在读取阶段,当读取到offset的值为-2时,就知道numDocsWithValue == 0,下面给出Lucene 8.4.0的索引文件.dvm,由于numDocsWithValue == 0,文档号的值信息不用写入到索引文件.dvd中:

图9:

  同样的查找表的信息用固定信息填充。

numDocsWithValue == maxDoc

  如果numDocsWithValue == maxDoc,说明正在执行flush的段中的每篇文档都包含当前域的信息,意味着我们也不用存储文档号的值信息,因为在读取阶段,文档号的值就是 [0, maxDoc]区间内的所有值,故同样只要将固定的信息写入到索引文件.dvm中:

图10:

  在读取阶段,当读取到offset的值为-1时,就知道numDocsWithValue == maxDoc,同样地给出Lucene 8.4.0的数据结构:

图11:

  在写入了文档号信息之后,将域值数量写入到索引文件.dvm中,域值数量在上文中的minMax中numValues获得,如下所示:

图12:

结语

  基于篇幅,剩余的内容将在下一篇文章中展开。

点击下载附件

 Comments