Lucene 源码系列—— LogMergePolicy

   本篇文章介绍索引文件的合并策略,某次提交(commit)或者刷新(flush)的所有索引文件属于一个新的段(Segment),所以也可以称为段合并(Segment Merge)。当 IndexWriter 索引中的数据有任意修改动作,它会调用 findMerges(...)方法通过某个合并策略(MergePolicy)来找出需要合并的段集,如果需要合并,那么合并策略会返回一个 oneMerge 的集合,oneMerge 的个数描述了 IndexWriter 需要执行合并的次数,单个 oneMerge 中包含了需要合并为一个新段(New Segment)的段集合。
Lucene4 版本开始,默认的合并策略为 TieredMergePolicy,之前是 LogMergePolicy,根据实际的业务需要,某些场景需要用到 LogMergePolicy,故本篇文章先介绍这种策略。

LogMergePolicy 的一些参数

DEFAULT_NO_CFS_RATIO

   默认值为 0.1,如果我们的索引文件设置为复合文件(compound file ),那么.doc、.pos、.fdx 等等索引文件在执行段合并后会生成一个复合文件,这个文件可能会很大,所以在合并前会判断将要生成的复合文件的大小是否会超过总的索引文件的 10%,如果超过,那么合并后就不会生成复合文件。

mergeFactor(可配置)

   mergeFactor 描述了 IndexWriter 执行一次合并操作的段的个数,即上文中提到的单个 oneMerge 中段集合大小。

level

   合并过程中根据策略(后面会介绍)会将连续的段分为不同的层级(level),遍历每一个层,然后在每一层中继续遍历每一个段,找到 mergeFactor 个段作为一个 oneMerge(前提是满足合并条件,下文会介绍)。

  • 根据策略找到第一层

图 1:
1.png

  • 在第一层中遍历找到 mergeFactor 个段,当前例子中 mergeFactor 的值为 2,段 1 跟段 2 作为一个 oneMerge,这里称为 oneMerge1。由于第一层中的只有一个段 3,所以无法生成一个 oneMerge。

图 2:
2.png

  • 同理根据策略(后面会介绍)找到第二层、第三层。并且生成 5 个 oneMerge,这些 oneMerge 就会交给 IndexWriter,IndexWriter 会执行 5 次合并操作。

图 3:
3.png

所以上面是两层遍历,时间复杂度为O(n^2)

minMergeSize、maxMergeSize(可配置)

  • maxMergeSize:某个段超过该值,这个段永远不会被合并。
  • minMergeSize:该值用来分层,关键的作用是处理数量很多的小段。如果 minMergeSize 设置的比较大,那么会导致划分很多的层,很多层意味着性能的降低,因为找出 oneMerge 是O(n^2)的时间复杂度,如果这个值设置的较为合适,那么会将许多的小段划分为一层,意味着两层循环的外层循环次数会减少,那么就能有效的将这些小段生成一个 oneMerge。

maxMergeDocs(可配置)

   默认值为 Integer.MAX_VALU,如果段中的文档数超过这个值,那么该段永远不会被合并。

calibrateSizeByDeletes(可配置)

   该值描述了是否要标记段中的被删除的文档,如果该值为 true,那么被删除的文档的个数或大小不会作为该段的一部分。

段的大小(Segment Size)

   有两种方式来描述一个段的大小

  • 文档数量:一个段中的文档数量可以用来描述段的大小,根据 calibrateSizeByDeletes 的值判断被删除的文档号是否也作为段的大小的一部分,例如 LogDocMergePolicy 就使用了该方法来计算段的大小
  • 索引文件大小:一个段中包含的所有的索引文件大小总和,在 Lucene7.5.0 版本中除了 LogDocMergePolicy,其他的合并策略都使用该方法

流程图

图 4:
4.png

   LogByteSizeMergePolicy 跟 LogDocMergePolicy 两种合并策略都属于 LogMergePolicy,他们使用相同的逻辑执行段的合并,差别在于对 Segment Size 有不同的定义,上文中已经介绍,下文中以 LogDocMergePolicy 来作为例子进行介绍,即 Segment Size 描述了一个段中包含的文档个数

开始

图 5:
5.png

   当 IndexWriter 对索引有任意的更改都会调用合并策略。

段集

图 6:
6.png

   IndexWriter 会提供一个段集(段的集合)给合并策略。

计算 log 值

图 7:
7.png

   由于每个段中的文档号数量各不相同,最小值跟最大值可能相差很大,使用 MergePolicy 可能使得永远无法进行合并操作(看完下文中的合并策略就明白为什么啦),所以计算 log 值作为一个平滑操作,故我们需要的并不是每个段的真实大小值,而是段之间的相对大小值,类似归一化处理。
   计算公式如下:

log(Segment Size) / (mergeFactor)\qquad

   SegmentSize 跟 mergeFactor 在上文中已经介绍了。

划分出一个分层?

图 8:
8.png

   在上文中介绍 level 时,我们知道了段集会被划分为多个层级,这里会介绍如何划分出一个层级,划分规则依据两个参数:

  • maxLevel:该值即未处理过的段集中 log 最大值。
  • LEVEL_LOG_SPAN:默认值为 0.75,该值不可配置,你要是问我为什么是 0.75,而不是其他值,我也不知道~ 😅
  • levelBottom:该值为一个差值:maxLevel - LEVEL_LOG_SPAN

   选出一个层级的逻辑分为三个步骤:



  • 步骤一:找出未处理的段集中的 maxLevel
  • 步骤二:从最后一个段集开始往前遍历,找到第一个大于等于 levelBottom,遍历到 maxLevel 停止
  • 步骤三:未处理的段集中第一个段到 levelBottom 所在的段的区间范围内的所有段处理为一个层级

例子

下面的例子中,颜色为蓝色的柱状为未处理的段集\color{#1E90FF}{下面的例子中,颜色为蓝色的柱状为未处理的段集}
图 9:
9.png

第一层

  • 步骤一

   找出未处理的段集(段 1~段 12)中的 maxLevel:即段 2。

  • 步骤二

   从后往前遍历,找到第一个大于 levelBottom:即段 2。

levelBottom = (maxLevel - LEVEL_LOG_SPAN), levelBottom = (7.3 - 0.75),即levelBottom = 6.55
  • 步骤三

   未处理的段集中第一个段(段 1)到 levelBottom 所在的段的区间范围内的所有段集为一个层级:段 1~段 2。
图 10:
10.png


   当划分出一个层级以后就可以进入下一步流程了,但是这里我们直接将其他所有的层级都先标记出来吧


第二层

  • 步骤一

   找出未处理的段集(段 3~段 12)中的 maxLevel:即段 4。

  • 步骤二

   从后往前遍历,找到第一个大于 levelBottom:即段 6。

levelBottom = (maxLevel - LEVEL_LOG_SPAN), levelBottom = (6.4 - 0.75),即levelBottom = 5.65
  • 步骤三

   未处理的段集中第一个段(段 3)到 levelBottom 所在的段的区间范围内的所有段集为一个层级:段 3~段 6。
图 11:
11.png

第三层

  • 步骤一

   找出未处理的段集(段 7~段 12)中的 maxLevel:即段 8。

  • 步骤二

   从后往前遍历,找到第一个大于 levelBottom:即段 12。

levelBottom = (maxLevel - LEVEL_LOG_SPAN), levelBottom = (5 - 0.75),即levelBottom = 4.25
  • 步骤三
       未处理的段集中第一个段(段 7)到 levelBottom 所在的段的区间范围内的所有段集为一个层级:段 7~段 12。
    图 12:
    12.png

层内段集数量 ≥ mergeFactor?

图 13:
13.png

   mergeFactor 定义了每次合并需要的段的个数,如果如果当前层内的段子集数量小于该值,那么就不用进行层内遍历了。

取出层内未处理的 mergeFactor 个段

图 14:
14.png

   当前层内的段子集个数不小于 mergeFactor,那么顺序遍历层内的段子集,每次取出 mergeFactor 个段,并处理为一个 merge,某些层内可以取出多个 merge。

例子

下面是当 MergeFactor = 3 时,每一层可以取出的的 merge:
图 15:
15.png

   在第一层中,由于层内段子集个数小于 MergeFactor,所以无法生产一个 merge,同理在第二层中,可以获得一个 merge,即 merge1,并且段 6 无法生成新的 merge,同理在第三层中可以生成 2 个 merge,即 merge2、merge3。
   注意的是,这里的 merger1、merge2、merge3 并不是最后的允许合并的段,即不是 oneMerge。

是否允许合并?

图 16:
16.png

   在上面的流程中,我们在一个层级内获得一个或多个 merge,需要继续判断这些 merge 是否允许生成 oneMerge,即真正提供给 IndexWriter 执行合并的段集。
   当 IndexWriter 获得一个 oneMerge 后,会使用后台线程对 oneMerge 中的段进行合并,那么这时候索引再次发生更改时,IndexWriter 会再次调用 MergePolicy,可能会导致某些已经正在合并的段被处理为一个新的 oneMerge,为了防止重复合并,在生成新的 oneMerge 前需要判断某些段是否允许合并。
   判断的方法有下面几个步骤:

  • 步骤 1:后台合并的线程会将正在合并的段添加到 Set 对象中,在 IndexWriter 调用合并策略时传入
  • 步骤 2:MergePolicy 在层内取出 mergeFactor 个段的过程中,会逐个判断每一个段是否在 Set 对象中(相同的引用),接着还要判断一个段的大小是否大于等于 maxMergeSize,正如上文中介绍的,超过 maxMergeSize 的段是不需要合并的,并且这个 merge 中的段集此次都会被认为是不允许合并的

保存为一个 oneMerge

图 17:
17.png

   在上一步流程中一个 merge 被认为是允许合并后,那么这个 merge 处理为一个 oneMerge。如果上一步流程中所有的 merge 都允许合并,那么这些 merge 就会分别处理为一个 oneMerge。
图 18:
18.png

结束

图 19:
19.png

   每个层级生成的多个 oneMerge 添加到一个集合中,将这个集合交给 IndexWriter,IndexWriter 会开启一个后台线程去执行合并操作。

结语

   本篇文章介绍了段的合并策略 LogMergePolicy,LogMergePolicy 并不负责段的合并,而是找出可以合并的段集,然后 IndexWriter 会开启后台线程合并这些段集,而这个后台线程在源码中即 MergeScheduler,在后面的文章中会介绍 MergeScheduler 是如何实现段的合并。
   另外在 MergePolicy 中,还有一些其他的方法,例如 findForcedMerges(...)、findForcedDeletesMerges(...)等等方法,在以后介绍 IndexWriter 时,会详细介绍。


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