lucene基础概念

内容简介：lucene基础概念

1. base

lucene是一个高性能、可扩展的信息检索（IR）工具库 ;
搜索质量：查准率(precision)、查全率(recall)
搜索理论模型（详见我的另一篇文章 Information Retrieval Models ）

（1）纯布尔模型

文档不会评分，匹配文档与评分不相关、也是无序的

（2）向量空间模型

查询语句和文档都是高维空间的向量模型，这里每一个项都是一个维度。查询语句和文档之间的相关性或者相似性由各个向量之间的距离计算得到

（3）概率模型

采用全概率方法来计算文档和查询语句的匹配概率
索引过程的核心类：
1. IndexWriter
2. Directory
3. Analyzer
4. Document
5. Field
搜索过程的核心类:
1. IndexSearcher
2. Term
3. Query
4. TermQuery
5. TopDocs
6. QueryParser
倒排索引的数据结构
索引段
域选项
1. 索引选项
2. 存储选项
3. 项向量选项
norm加权基准
特里结构（trie structure） lucene索引数字
索引文件的并发访问
1. 任意数量的只读属性的IndexReader类都可以同时打开一个索引；
2. 对一个索引来说，一次只能打开一个Writer；
3. IndexReader对象甚至可以在IndexWriter对象正在修改索引时打开；
4. 任意多个线程都可以共享同一个IndexReader类或者IndexWriter类
近实时功能
1. indexWriter.getReader
索引锁机制 – 文件锁
索引的缓冲和刷新
索提交过程
索引indexWriter的两阶段提交
索引段合并
lucene评分
1. similarity
Levenshtein距离算法 – 搜索类似项
Queryparser

2. 底层数据结构

词典和倒排表

词典的数据结构

数据结构	优缺点
排序列表	实现简单，性能差
哈希表	性能高，内存消耗大
跳跃表	占用内存小，且可调，丹对模糊查询支持不好
B树	磁盘索引，更新方便，但检索速度慢，数据库应用多
字典树	查询效率只和字符串长度有关，但只适合英文词典
双数组字典树	可做中文词典，内存占用小，分词工具应用多
Finite State Transducers（FST）	共享前缀，内存消耗小，但要求输入有序，更新不易

其中可用的 B+树、跳跃表、fst 。

B+树，

理论基础：平衡多路查找树

优点：外存索引、可更新

缺点：空间大、速度不够快

跳跃表：

优点：结构简单、跳跃间隔、级数可控，Lucene3.0之前使用的也是跳跃表结构，后换成了FST，但跳跃表在Lucene其他地方还有应用如倒排表合并和文档号索引。

缺点：模糊查询支持不好

FST:

理论基础: 《Direct construction of minimal acyclic subsequential transducers》，通过输入有序字符串构建最小有向无环图。

优点：内存占用率低，压缩率一般在3倍~20倍之间、模糊查询支持好、查询快

缺点：结构复杂、输入要求有序、更新不易

Lucene里有个FST的实现，从对外接口上看，它跟Map结构很相似，有查找，有迭代：

String inputs={ “abc” , “abd” , “acf” , “acg” }; //keys

long outputs={ 1 , 3 , 5 , 7 }; //values

FST<Long> fst= new FST<>();

for ( int i= 0 ;i<inputs.length;i++)

{

fst.add(inputs[i],outputs[i])

}

//get

Long value=fst.get( “abd” ); //得到3

//迭代

BytesRefFSTEnum<Long> iterator= new BytesRefFSTEnum<>(fst);

while (iterator.next!= null ){…}

因此一个合格的词典结构要求有：

1. 查询速度。

2. 内存占用。

3. 内存+磁盘结合。

Lucene经多年演进优化，现在的一个索引文件结构如图所示，基本可以分为三个部分： 词典、倒排表、正向文件 。

目前根据lucene 4.10版本分析

索引结构

Lucene现在采用的数据结构为FST，它的特点就是：

1、词查找复杂度为O(len(str))

2、共享前缀、节省空间

3、内存存放前缀索引、磁盘存放后缀词块

我们往索引库里插入四个单词abd、abe、acf、acg,看看它的索引文件内容。

tip部分，每列一个FST索引，所以会有多个FST，每个FST存放前缀和后缀块指针，这里前缀就为a、ab、ac。tim里面存放后缀块和词的其他信息如倒排表指针、TFDF等，doc文件里就为每个单词的倒排表。

所以它的检索过程分为三个步骤：

1. 内存加载tip文件，通过FST匹配前缀找到后缀词块位置。

2. 根据词块位置，读取磁盘中tim文件中后缀块并找到后缀和相应的倒排表位置信息。

3. 根据倒排表位置去doc文件中加载倒排表。

这里就会有两个问题，第一就是前缀如何计算，第二就是后缀如何写磁盘并通过FST定位，下面将描述下Lucene构建FST过程:。已知FST要求输入有序，所以Lucene会将解析出来的文档单词预先排序，然后构建FST，我们假设输入为abd,abd,acf,acg，那么整个构建过程如下

1. 插入abd时，没有输出。

2. 插入abe时，计算出前缀ab，但此时不知道后续还不会有其他以ab为前缀的词，所以此时无输出。

3. 插入acf时，因为是有序的，知道不会再有ab前缀的词了，这时就可以写tip和tim了，tim中写入后缀词块d、e和它们的倒排表位置ip_d,ip_e，tip中写入a，b和以ab为前缀的后缀词块位置(真实情况下会写入更多信息如词频等)。

4. 插入acg时，计算出和acf共享前缀ac，这时输入已经结束，所有数据写入磁盘。tim中写入后缀词块f、g和相对应的倒排表位置，tip中写入c和以ac为前缀的后缀词块位置。

最小后缀数。Lucene对写入tip的前缀有个最小后缀数要求，默认25，这时为了进一步减少内存使用。如果按照25的后缀数，那么就不存在ab、ac前缀，将只有一个跟节点，abd、abe、acf、acg将都作为后缀存在tim文件中。我们的10g的一个索引库，索引内存消耗只占20M左右。
前缀计算基于byte，而不是char，这样可以减少后缀数，防止后缀数太多，影响性能。如对宇(e9 b8 a2)、守(e9 b8 a3)、安(e9 b8 a4)这三个汉字，FST构建出来，不是只有根节点，三个汉字为后缀，而是从unicode码出发，以e9、b8为前缀，a2、a3、a4为后缀，如下图：
倒排表
倒排表就是文档号集合，但怎么存，怎么取也有很多讲究，Lucene现使用的倒排表结构叫 Frame of reference
,它主要有两个特点：

1. 数据压缩，可以看下图怎么将6个数字从原先的24bytes压缩到7bytes。

详细查看： Frame of Reference and Roaring Bitmaps )
跳跃表加速合并，因为布尔查询时，and 和or 操作都需要合并倒排表，这时就需要快速定位相同文档号，所以利用跳跃表来进行相同文档号查找。

正向文件
正向文件指的就是原始文档，Lucene对原始文档也提供了存储功能，它存储特点就是分块+压缩，fdt文件就是存放原始文档的文件，它占了索引库90%的磁盘空间，fdx文件为索引文件，通过文档号（自增数字）快速得到文档位置，它们的文件结构如下

fnm中为元信息存放了各列类型、列名、存储方式等信息。

fdt为文档值，里面一个chunk就是一个块，Lucene索引文档时，先缓存文档，缓存大于16KB时，就会把文档压缩存储。一个chunk包含了该chunk起始文档、多少个文档、压缩后的文档内容。

fdx为文档号索引，倒排表存放的时文档号，通过fdx才能快速定位到文档位置即chunk位置，它的索引结构比较简单，就是跳跃表结构，首先它会把1024个chunk归为一个block,每个block记载了起始文档值，block就相当于一级跳表。

所以查找文档，就分为三步：

第一步二分查找block，定位属于哪个block。

第二步就是根据从block里根据每个chunk的起始文档号，找到属于哪个chunk和chunk位置。

第三步就是去加载fdt的chunk，找到文档。这里还有一个细节就是存放chunk起始文档值和chunk位置不是简单的数组，而是采用了平均值压缩法。所以第N个chunk的起始文档值由 DocBase + AvgChunkDocs * n + DocBaseDeltas[n]恢复而来，而第N个chunk再fdt中的位置由 StartPointerBase + AvgChunkSize * n + StartPointerDeltas[n]恢复而来。

从上面分析可以看出，lucene对原始文件的存放是行是存储，并且为了提高空间利用率，是多文档一起压缩，因此取文档时需要读入和解压额外文档，因此取文档过程非常依赖随机IO，以及lucene虽然提供了取特定列，但从存储结构可以看出，并不会减少取文档时间。

3.lucene 性能瓶颈分析

性能瓶颈

Lucene索引结构：内存+磁盘，打开索引库时只有tip和fdx文件会被加载到内存中，tip为FST的前缀索引，fdx为正向文件索引，其他文件tim、doc、fdt都放在硬盘，一次完整的检索过程与索引文件的交互过程如图：

整个流程至少发生三次随机IO：

1. 读后缀词块

2. 读倒排表

3. 取文档（如果文档号跳跃性很大或者因为打分完全乱序，那么会发生更多次随机IO，极端情况就是取多少文档就发生多少次随机IO）

当前机械硬盘随机IO响应时间平均在10ms左右，远大于CPU+内存计算时间，而且这只是针对一个查询条件，若多个查询条件、跨多列、甚至模糊查询，随机IO请求更多，因此Lucene查询性能瓶颈主要集中磁盘IO性能上，尤其随机IO性能。所以我们的优化方向就是：

1. 减少IO请求 。

2. 顺序IO代替随机IO 。

lucene代码结构

Lucene从4.0版本后，代码全面模块化，并开放了很多接口，包括索引格式接口Codec、打分接口Similarity、文档收集接口Collector，开发者想基于Lucene再开发，不再需要侵入式修改源代码，而是基于接口，插件式修改。我们结合业务场景和开放接口自定义了Lucene检索模式。

Lucene检索大致时序图：

1. APP解析用户查询生成查询条件Query。

2. IndexSearcher重写Query并生成Weight。

3. Weight会生成Scorer，Scorer创建相应查询条件的倒排表迭代器。

4. 调用scoreALl()，遍历所有文档ID，依次传给传给Collector。

5. Collector得到文档ID后，调用打分模块Similarity得到文档分值，并根据分值和文档收集器具体实现决定是否返回。Lucene默认的收集器TopScoreDocCollector，会根据用户定义的文档数如100，返回分值前100的文档ID。

我们对Lucene的修改主要在图中标红的文档收集过程，一是屏蔽打分，二是修改文档收集模式

针对情景优化

通过上面的分析，我们知道什么是必须优化的，那就是IO!!!

1 单盘优化

解决问题：

硬盘随机IO性能低。

解决方案：

1. 将原先的Raid5拆分，改用单盘，因为Raid5随机读写性能 < n*单盘。

2. 将索引文件tim、doc使用固态硬盘SSD存放，正向文件fdt使用机械硬盘，这样综合了SSD随机读写性能高，机械硬盘成本低、存储空间大的优点。

3. 对同一磁盘上索引库进行统一管理，单线程处理对同一硬盘上索引库的检索请求，防止同一硬盘多库之间同时访问降低磁盘性能。这里可以根据实际测试情况调整具体线程数，但线程数不宜过多。

2布隆过滤器

解决问题：

有些单词不在索引库里，但还需要进索引库查询，发起不必要的IO请求。

解决方案：

使用布隆过滤器，预先判断单词是不是在该索引库里。布隆过滤器原理很简单，对一单词哈希，并映射到相应bit，设置为1，判断时同样做哈希，并去相应bit位取值，若为1，则可能存在，进库查询，若为0，则肯定不存在，不需进库查询。

对Lucene实现布隆过滤器有两种方式：

1. 在应用层，Lucene之外实现。

2. 改写Lucene的Codec接口，添加布隆过滤器功能，使用布隆过滤器预先过滤查询条件。

后来我们经过测试，选用了第一种方案，因为布隆过滤器十分消耗内存、加载时间很长，而且我们同一索引库为提高性能，复制到多个硬盘上，所以如果布隆过滤器放在Lucene里，相同过滤器会被加载多次，会浪费相当多的内存，所以我们在Lucene之外做了布隆过滤器，同一索引库共享一个布隆过滤器，节约了内存。

3 屏蔽打分/排序机制

解决问题：

一次测试发现，同样的条件，精确查询速度还没有模糊查询速度快

研究源代码发现，Lucene会对分词列的精确查询条件进行打分。打分是搜索引擎重要一部分，倒排索引只能回答是不是的问题，打分能够评判查询条件和文档的匹配度，提高检索质量。Lucene打分过程集成了多种经典模型，如TF-IDF、VSM，如图：

几个基本原则：

1. 一个文档符合的查询条件越多分越高。

2. 一个文档关键词出现次数越多分越高，文档内容越多分越低。

3. 一个查询词出现文档数越多权重越低。

解决方案：

1. 实现EmptySimilarity，去掉所有计算过程，打分过程完全为空。

public class EmptySimilarity extends Similarity {

private static long ZERO= 0 ;

@Override

public long computeNorm (FieldInvertState state) {

return ZERO;

}

@Override

public SimWeight computeWeight ( float queryBoost,

CollectionStatistics collectionStats, TermStatistics… termStats) {

return new EmptySimWeight();

}

@Override

public SimScorer simScorer (SimWeight weight, AtomicReaderContext context)

throws IOException {

return new EmptyScorer();

}

public class EmptySimWeight extends SimWeight {

@Override

public float getValueForNormalization () {

return ZERO;

}

@Override

public void normalize ( float queryNorm, float topLevelBoost) {

}

public static class EmptyScorer extends SimScorer {

@Override

public float score ( int doc, float freq) {

return ZERO;

}

@Override

public float computeSlopFactor ( int distance) {

return ZERO;

}

@Override

public float computePayloadFactor ( int doc, int start, int end,

BytesRef payload) {

return ZERO;

}

自定义Collector，结果数满足了抛异常退出，防止读入多余倒排表。

public class SimpleCollector extends Collector implements Iterable < Integer > {

private final List<Integer> hitList;

private final int numHits;

private int docBase;

public SimpleCollector ( int numHits) {

if (numHits< 0 )

throw new IllegalArgumentException( “numHits should > 0” );

this .numHits = numHits;

this .hitList = new ArrayList<Integer>(numHits);

}

@Override

public void collect ( int doc) throws IOException {

if (hitList.size()<numHits)

{

hitList.add(docBase+doc);

}

else {

//若结果满了抛异常退出

throw new HitListFullException();

}

public int size (){

return hitList.size();

}

@Override

public void setScorer (Scorer scorer) throws IOException {

//ignore scorer

}

@Override

public void setNextReader (AtomicReaderContext context) throws IOException {

//因为是分段的，所以需要记载每个段起始文档号

this .docBase=context.docBase;

}

@Override

public boolean acceptsDocsOutOfOrder () {

//接受乱序，提高性能，因为最后要自己排序

return true ;

}

@Override

public Iterator<Integer> iterator () {

Collections.sort(hitList);

return hitList.iterator();

}

public static class HitListFullException extends RuntimeException {

public HitListFullException ()

{

super ( “HitList already full” );

}

应用：

IndexSearcher indexSearcher = new IndexSearcher(

DirectoryReader.open(FSDirectory

.open( new File( “/index/lucene_test” ))));

//使用空打分器

indexSearcher.setSimilarity( new EmptySimilarity());

SimpleCollector simpleCollector= new SimpleCollector( 2 );

try {

indexSearcher.search(query, simpleCollector);

} catch (HitListFullException e) {

//e.printStackTrace();

// ignore

}

System.out.println(simpleCollector.size());

//遍历文档号

for ( int hit:simpleCollector)

{

indexSearcher.doc(hit);

}

indexSearcher.getIndexReader().close();

4 取结果优化

解决问题：

上面的测试条件还有一个问题，就是他们取同样数量的文档数，时间却差了很多。

原因就是因为模糊查询不打分，所以文档ID是顺序的，为顺序IO读方式，而打分后文档ID完全乱序，为随机IO读方式。

解决方案：

1. 自定义Collector，按文档ID升序排序且结果数满足立即退出。

2. 多任务合并取结果操作，这样相同ID的文档只会取一次。

5 解决Query被转成Filter

解决问题：

我们有一个组合条件：

sql select * from indexdb where Time > 20170104 AND Time < 20170105 AND Protocol = ‘TCP’ AND Content =’not exist’

这里需要合并多个查询条件的倒排表，Lucene在合并倒排表时，并不会一次性读出所有倒排表，而是将倒排表抽象成迭代器，延迟获取，而且如果有一个AND条件查询结果为空，它就直接返回，不会读任一倒排表。这里Content查询结果为空，但这个查询还是很久才返回，debug跟踪Lucene源代码发现，Lucene会对Query查询重写来优化性能，这里的Time条件因为匹配到词数太多，而被Lucene改写成Filter，Filter一个特点就是会读出符合查询条件的所有倒排表，并做成BitSet，所以查询时间都消耗在了读倒排表上。

解决方案：

1. 去掉了CapTime条件，改由应用层去做，按时间预先分库。

2. 调整子查询顺序，将匹配结果更少的放前面。

3. 留心Lucene的重写机制，有时候重写过的查询条件不一定符合我们预期。

6索引库大小性能比较

解决问题：

Lucene一个索引库多大合适？

解决方案：

这里涉及到Lucene索引结构设计：Lucene是分段的。分段是指Lucene接收到索引请求后，会先放缓存，缓存满后才会写到磁盘中去，变成一个Segment，Segment创建好了之后就不会再修改，每个Segment相当于一个功能完整的小索引库，它包含之前说的所有索引文件。当然这样会导致索引库中有很多段，所以Lucene后台会有合并线程定期去合并小的段。

段数越少，检索时随机IO次数请求就越少，段结果合并操作越少。如果只有一个段，那么一个查询条件就需要加载一个后缀词块，但有10个段，就需要分别加载10个段的后缀词块和倒排表，再合并10个段的查询结果。分库本质上跟分段是一样的，调整库大小，减少库数量，就是减少段数来提高性能。

库大小测试结果：

总共575G的索引库，我们分为6个100g的库和71个10g的库来分别测试

库类型打开时间(s) 库内存占用(g)

大库 11 1.3

小库 18 2.2

查询测试

库类型查询条件查询时间(ms)

大库 content=’trump’ 1100

小库 content=’trump’ 5700

可以看出大库相比小库不管再打开时间、内存占用、查询效率上都有着很大优势，所以在条件允许下，尽量把库调大。但也需注意两个问题：

1. 合并大库是有成本的。