lucene内部的合并策略

原文链接：http://java.dzone.com/news/merge-policy-internals-solr?mz=33057-solr_lucene
solr(or lucene)内部的合并策略是怎样的呢？

选择哪些段(segment)需要被合并，是基于名为MergePolicy的抽象类决定的。这个类创建了一个合并规则类MergeSpecification：由OneMerge对象组成的一个列表集合。其中的每一个代表了一个单独的合并操作；被指定的所有段都将被合并为一个新的段。

在索引改变之后，IndexWriter会调用MergePolicy来获取一个MergeSpecification；然后开始调用MergeScheduler，该类负责合并任务的执行。MergeScheduler主要有两个实现类：ConcurrentMergeScheduler为并行合并的线程类(多线程)，SerialMergeScheduler则会将所有的合并操作在当前线程进行(单线程)。当合并的时间到了，IndexWriter会将合并的任务交给SegmentMerger来做。

所以，如果想了解什么时候段会被合并、为什么有些段被合并了而有些没有、或者起来类似的一些问题，我们都应该了解一下MergePolicy。

MergePolicy有很多的实现，我们来看一下它的默认实现类LogByteSizeMergePolicy。MergePolicy定义了三个抽象方法来构造MergeSpecification：
     1. findMerges() 将会在索引被改变时被调用
     2. findMergesForOptimize() 在optimize操作时被调用
     3. findMergesToExpungeDeletes() 在删除操作时被调用

Step by step
下面先对合并策略作一个简短的概念性描述，请看下图：
1. 将段按name排序
2. 将已存在的段分组(level)，每个组(level)都是连续段的集合
3. 对于每个组，确定将要被合并的段


Parameters
下面来说明一下在合并索引时需要用到的一些参数：
1. mergeFactor： 这个参数有多种含义，比如有多少段将被合并为新段；每个组的最大段数和每个段的跨度，可以在solrconfig.xml里设置
2. minMergeSize：小于该值的所有段将会被归于一个组中，固定值
3. maxMergeSize：大于该值的所有段将不会被合并，固定值
4. maxMergeDocs：所有文档数大于该值的段将不会被合并，以上参数均在solrconfig.xml中定义

Constructing the levels
让我们看一下组(level)是如何被构造的。为确定第一个组，算法会查询最大合并段大小，我们叫它levelMaxSize。如果这个值小于minMergeSize，那么所有的段都会被归为一个组。否则，levelMaxSize的值将为：

这个算法的大致含义为：levelMaxSize的值大约为levelMaxSize除以mergeFactor的0.75次方(如果1被使用则替代0.75)，但是如果算出的值小于minMergeSize，则用minMergeSize代替。

通过这个计算，算法将会选择哪些段属于当前的组。首先，它讲找一个大于或等于levelMinSize的段，如果其他旧的段都比它小，则被归为一个组。下一个组也会使用相同的方式，但是会找比上一个段更新的段作为比较段。

下面举个例子，设mergeFactor=10 and minMergeSize=1.6MiB.

首先取第一个段200M，得出levelMaxSize为36M，那么只有I比它大；分为一组，继续选择8.9M得出levelMaxSize为1.6M，计算后与6.5M分为一组……

但是，如果你不了解算法本身，它会构造出你无法预料的组。举个例子，下面的表中，依然设置mergeFactor=10 and minMergeSize=1.6MiB.

Segment 	Size
a 	200 MiB
l 	88 MiB
m 	8.9 MiB
n 	6.5 MiB
o 	1.4 MiB
p 	842 KiB
q 	842 KiB
r 	842 KiB
s 	842 KiB
t 	842 KiB
u 	842 KiB
v 	842 KiB
w 	842 KiB
x 	160 MiB

会有多少组呢？来看一下：最大的段大小为200M，则levelMinSize为36M；最新的比levelMinSize 大的段是x，所以第一个组包括x并且所有的段都比它旧。那么，这将只有一个组！

Choosing which segments to merge
在定义完组之后，MergePolicy将会选择哪些段会被合并：单独的分析每个组，如果一个组小于mergeFactor 个段，那么该组会被忽略(不合并)。否则，所有在该组中的段都将被合并为一个新的段；如果组中有大于maxMergeFactor或maxMergeDocs的段，则该段被忽略。

回到第2个例子中，当只有一组段需要合并时，合并结果为：

Segment 	Size
u 	842 KiB
v 	842 KiB
w 	842 KiB
x 	160 MiB
y 	311 MiB

minMergeSize and maxMergeSize
这个说说这两个参数。目前这两个值在lucene中是硬编码的，他们的值为：
   minMergeSize：1.6M 所有比1.6M小的段都将被归为1组
   maxMergeSize：2G   所有大于2G的段都不会再被合并

Conclusion
其实这个算法并不复杂，如果想知道在你的索引添加多个文档时发生了什么，了解其内部机制是有必要的。同时，了解合并策略是如何工作的，更能帮助你设定一些参数的值(如mergeFactor和maxMergeDocs)。