IndexTank全文检索引擎设计分析

一、    简介

IndexTank是一个托管的搜索基础服务。他主要有以下几个特点(从官网介绍翻译过来的):

索引更新实时生效

地理位置搜索

支持多种客户端语言
Ruby, Rails, Python, Java, PHP, .NET & more!

支持灵活的排序与评分控制

支持自动完成

支持面搜索(facet search

支持匹配高亮

支持海量数据扩展(Scalable from a personal blog to hundreds of millions of documents!

支持动态数据

IndexTank201110月被Linkedin收购,其原有提供的搜索托管服务将在20124月终止。目前Linkedin已经把IndexTank的索引引擎代码以及部分上层服务的代码开源。


二、    设计分析

由于IndexTank是一个开源不久的项目,官方公布的设计相关的资料以及网上对其分析测试可以说是几乎没有,对其内部实现分析都是通过分析代码得出,由于目前只是大致看了一下代码,部分细节分析可能有误。

索引数据结构

IndexTank在底层索引倒排表是基于lucene实现的,但是其索引数据的整体设计与lucene有较大的区别。其基本思想为把索引数据分成三大类:倒排表数据、动态数据、原始文档数据。

倒排表数据

这部分数据主要通过lucene封装实现,底层文件数据结构与lucene完全相同,但是与lucene对外暴露docId不同,在倒排表获取的docId 会被转换为全局唯一不变的id,这点类似于ZOIE,但是实现上有所区别,具体看后文实现分析。倒排表数据为了支持实时搜索分成文件倒排和内存倒排两部分数据

动态数据

这部分数据是保存文档中会经常动态修改的数据,主要包括用于计算评分的数据、facet search字段等。该部分数据通过全局唯一的主键进行访问,数据完全加载在内存中,定时dump到文件系统。

原始文档数据

这部分数据是保存文档中不会动态修改的原始数据,主要用于在检索时获取原始文档内容生成摘要等。该部分数据通过全局唯一的主键进行访问。目前开源部分的 IndexTank-engine代码只定义了一个DocumentStorage的接口,并没有提供实现,用户可以自己实现所需的存储控制器(如基于数据库等)。


代码分析

索引引擎的代码结构如下图:


上图为IndexTank中索引引擎IndexEngine中的主要类结构,各主要类的设计如下:

LargeScaleIndex

大 规模数据倒排索引封装类,用于存储持久化到文件系统中的索引数据,底层通过lucene实现。该类对外提供建索引文档的插入、删除以及查找制定查询对象匹 配的记录的接口,这些接口都与lucene无关,是IndexTank自己封装的接口,主要可以抽象为以下几个接口(其中findMatches为该类的 内部类中提供,为解析方便抽象出来一起介绍):

void add(String docId, Document document);

void del(String docId);

// 注意下面的TopMatchesQuery并非lucene中的,而是IndexTank自行封装的

TopMatches findMatches(Query query, int limit, int scoringFunctionIndex);

可以看出,LargeScaleIndexluceneIndexWriterIndexReader不同,提供的接口都是以全局唯一且不变的docId为依据进行操作的,而不是使用lucene内部生成且会变化的docId

在 建索引的时候会多建立一个特殊的字段,字段名和值都固定,并在payload中保存该文档对应的全局唯一不变的docId,从而形成一个按lucene内 部docId连续排序的倒排表,其中每项payload中保存对应的全局唯一不变docId,通过这种方式保存lucene docId与全局docId的映射关系,实现方式与zoie相同。另外,所有字段在通过lucene建索引时参数都是分词+不保存原值+不保存 TermVector+文本类型的字段。

在 检索的时候,首先通过lucene IndexReader的底层接口获取TermPositions封装生成匹配结果的迭代器,用于获取所有匹配Query对象的docId、位置偏移等信 息。然后遍历该迭代器,并在迭代过程中通过payload字段获取匹配记录对应的全局docId,然后通过 DynamicDataFacetingManager统计分类信息,通过BoostsScorer计算最终文档评分,最终转换生成TopMatches 返回。


RealTimeIndex

实 时索引数据管理类,用于保存最近加入的文档的索引,数据保存在内存中,用于在数据刷写到文件系统前通过内存索引提供实时检索支持。内部保存两份倒排表数 据,分别为markedIndexindex,所有新数据进入index,然后在LargeScaleIndex开始刷写新数据的时候对 RealTimeIndex进行标记(mark),此时index数据放到markedIndex中,index新开一份空间用于保存新数据,在刷写完毕 的时候丢弃markedIndex,刷写过程中检索数据同时读取两份倒排数据进行合并。每份倒排数据类似于通过一个Map<String, List<Integer>>的结构保存所有倒排数据,以及DocId[]保存原始id与全局DocId的映射关系。该类提供了跟 LargeScaleIndex一样的接口。检索时重用了LargeScaleIndex的大部分代码。


DynamicDataManager

用 于保存文档动态数据的管理类,保存如推荐数等容易发生变化的数据,另外facet search中使用的分类信息(可选值数量比较小的字符串)也通过该类保存,在访问该类时,通过全局唯一不变docId定位文档。相关数据全部保存在内存 中并定时dump到文件系统,在保存分类信息的时候,会对分类字符串值进行类似哈弗曼编码以数值进行保存,避免重复保存相同的字符串占用内存。


DynamicDataFacetingManager

处理面搜索相关逻辑的管理器,在检索过程中被Blender调用统计匹配结果中不同类别的记录数,底层通过DynamicDataManager获取记录的分类信息。


BoostsScorer

记录评分计算器,内部保存各种用户评分计算接口实例,在计算记录评分的时候,通过计算接口对象从DynamicDataManager获取动态数据计算最终评分。


UserFunctionsManager

评 分接口管理类,IndexTank定义了一套评分函数,UserFunctionsManager负责对用户设置的评分函数字符串进行解析,并动态生成继 承评分计算接口(ScoreFunctionjava.class对象进行加载并保存到BoostsScorer中。


IndexEngineParser

保存分词器并用于解析用户查询条件字符串。

Dealer

IndexEngine 中用于处理建索引请求的对象,在建索引的时候,会把同一个请求通过LargeScaleIndexRealTimeIndex进行处理。其中 LargeScaleIndex只有在刷写新加数据到文件系统中才能够被检索出来,新加记录通过RealTimeIndex进行检索。


Blender

IndexEngine 中用于处理检索请求的对象,在检索的时候,会通过LargeScaleIndexRealTimeIndex进行处理,其中 LargeScaleIndex获取老数据,RealTimeIndex获取新加记录,由Blender负责把两部分进行合并。


DocumentStorage

负责保存文档不变字段的原始内容,在访问该类时,通过全局唯一不变docId定位文档。IndexTank并没有开源DocumentStorage的实现,只给出了其接口定义,由使用者自行定义实现。


Suggester

实现自动完成的相关功能,内部在内存通过类似Tri Tree的数据结构保存相关自动数据,并定时dump到文件系统。


重要流程分析

实时索引

IndexTank的实时索引的实现方式与ZOIELuceneNRT都不同,其原理如下:

首先通过RealTimeIndex建立内存中的反向索引,该部分数据直接通过javamaplist等内存对象结构存储,没有通过luceneRamDirectory实现,没有数据压缩。

然后把相同的文档通过LargeScaleIndex内部的lucene IndexWriter再次建一份反向索引,但是IndexWritercommit,相当与只是在内存中进行了反向表的相关编码等,还没有写到文件系统。

在 调用Dealer对象的dump接口的时候,会通过LargeScaleIndexIndexWritercommit方法把内存中的数据刷到文件系 统,并根据合并策略进行merge操作。这个过程有可能会比较长,为了让实时索引保持正常,会对RealTimeIndex进行mark操作,原来的内存 Map对象的反向数据会保存到markIndex引用中,并新开一个Map对象保存新记录的反向索引,而LargeScaleIndex的新记录会缓存到 一个队列中等合并完毕在进行处理。这段时间内所有检索都要同时通过LargeScaleIndex中的老IndexReader RealTimeIndex中通过两个Map保存的方向索引数据进行检索并合并。等merge操作完成后,会同步reopen LargeScaleIndex中的IndexReader并丢弃RealTimeIndex中的markIndex。设计思想与ZOIE类似。


建立索引

在建立索引使用者需要首先把索引文档字段划分为三类:需要建反向索引的静态字段、需要存储的静态字段、不需要反向索引的动态字段。

通过IndexEngine获取DocumentStorage对象,通过其接口保存需要存储的静态字段

通过IndexEngine获取Dealer对象,通过updateBoostsupdateCategories保存动态的评分字段与分类信息字段

通过Dealer对象add接口对给需要建反向索引的静态字段建立反向索引

定时调用Dealer对象的dump接口把内存中的实时反向索引数据、动态字段数据、自动完成数据持久化到文件系统


检索记录

IndexEngine中获取Blender对象,通过search接口传入query对象进行检索直接获取匹配结果的DocId与动态字段数据,具体处理步骤如下:

通过LargeScaleIndexRealTimeIndex获取与query对象匹配的文档记录的迭代器

在 上一步生成的遍历迭代器基础上封装TopMatches迭代器,该迭代器在迭代的时候,通过DynamicDataManager获取需要的动态数据,由 DynamicDataFacetManager统计facet search的结果,由BoostsScorer计算文档评分

遍历上一步生成的迭代器获取所有匹配文档记录,在遍历的同时,根据制定获取的动态字段列表,从DynamicDataManager获取该文档的动态字段值。最终返回匹配结果。

IndexEngine中获取DocumentStorage对象,根据需要获取文档的原始记录


数据恢复

IndexTank在建立文档索引的时候会记录操作日志

IndexTank会定时把内存中的数据(包括实时反向索引、自动完成数据、动态字段数据等)dump到文件系统

如果系统崩溃,IndexTank会首先加载最后一次dump到文件系统的数据,然后在根据操作日志从dump的时间点开始重建索引数据。恢复的原理跟数据库类似。


三、    IndexTank的优势

IndexTank的索引结构确实是一个挺有意思的设计,通过把整个索引划分为三种类型分别处理能够带来一定的优势。


加快Merge

由于把文档原始记录与动态变化数据独立于倒排表数据,通过全局不变的唯一DocId进行联系,所以在每次merge数据的时候,只涉及lucene的倒排表部分,数据量相对较小,可以加快Merge速度。

减少IndexReaderreopen操作

ZOIELuceneNRT中,对外提供索引访问都是通过IndexReader实现的,为了实现实时索引的功能,需要经常调用IndexReader reopen操作(或新建IndexReader),因为在lucene的设计思想中IndexReader在构建之后,其能读取的数据就不会变化。然而IndexReader的构建与reopen是一个不算太简单的操作,其内部需要合并计算各个SegmentdocId映射为对外的docId delete文档bitVector缓存等等,会占用cpu并加大gc负担。然而,在IndexTank中反向索引结构并非通过IndexReader对 外提供访问,只有LargeScaleIndex的内部实现中通过IndexReader实现反向索引读取,那部分数据只有在dump的时候才需要 reopen IndexReader,频率相当低,而RealTimeIndex中数据保存在支持同步修改、访问的Map结构中,能够直接访问当前最新的索引数据。通 过这种设计,从根本上解决了IndexReader需要频繁构建与reopen的问题。

提高索引的实时性

IndexTank的实时索引本质上是通过一个线程安全的Map来实现的,处理相对比较简单,不需要像ZOIELuceneNRT那样经过大量的编码以及零散索引合并还有reopen的过程,实时建索引的效率更加高,缺点是数据没有经过压缩,内存占用更大。

解决缓存失效问题

Lucene中,在排序、自定义评分的时候,需要通过倒排表缓存所有文档的相关字段的值,然而这种缓存是跟IndexReader关联的,因为是通过内部 docId进行访问,docId会伴随segment的合并发生变化,因此经常会发生缓存失效需要重新加载的情况。而IndexTank把所有动态数据单 独保存,通过全局docId进行关联,使缓存不会经常失效。

减少原始文档查询数量

在处理分布式检索的时候我们的SearchDispatcher是从多个IndexStore中获取,由于目前原始文档记录是在lucene索引中保存,只能在发往IndexStore的请求中同时查询分片的所有匹配记录的完整文档信息,然而,在最终结果中,只有其中一部分有效,导致了大量的无用查询。如果 像IndexTank那样把原始文档单独存储并通过全局DocId进行关联,可以在IndexStore的查询中只返回匹配相关信息(如全局docId、 匹配评分等),在SearchDispatcher合并抽取出最终返回的记录集合之后在通过全局DocId查询原始记录,最终输出给用户。

隐藏内部Lucene DocId

IndexTank的设计中,Lucene内部的DocId只有LargeScaleIndex知道,对外的接口都是通过全局DocId进行关联,把Lucene内部实现隐藏掉了,设计上更加优雅,也更方便维护扩展其他功能。



网易云新用户大礼包:https://www.163yun.com/gift

本文来自网易实践者社区,经作者何卓斌授权发布。