（转） lucene索引结构改进-支持单机十亿级别的索引的检索

术语解释：

Lucene:是apache软件基金会4 jakarta项目组的一个子项目，是一个开放源代码的全文检索引擎工具包，即它不是一个完整的全文检索引擎，而是一个全文检索引擎的架构，提供了完整的 查询引擎和索引引擎，部分文本分析引擎（英文与德文两种西方语言）。Lucene的目的是为软件开发人员提供一个简单易用的工具包，以方便的在目标系统中 实现全文检索的功能，或者是以此为基础建立起完整的全文检索引擎。

二分查找: 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表， 且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比 较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一 步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

倒排索引：（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。

 

单机版的lucene只能应对千万级，或百万级的索引，通过修改索引，能够支持10亿以上索引的检索。

当前lucene首次加载需要读取整个索引文件，如果数据量较大，索引文件也很大，会照成内存瓶颈。

 

 

     Lucene 使用倒排索引进行文档的检索，假设存在三个文档

中华人民共和国

人民英雄

中华美食

     Lucene在创建索引的的过程中，会将三个文档按照分词结果进行倒排，组成一个倒排表tis文件

中华 {1,3}

人民 {1,2}

共和国 {1}

英雄 {2}

美食 {3}

     这样当用户搜索“中华”这个关键词的时候，根据倒排  “中华 {1,3}”就可以知道在文档1和3中含有此关键词，文档1和3就会返回给用户。

     我们通常将倒排表中的每个词语叫做一个term,如果想知道，人民这个term对应那些文档，必须先知道 人民这个term在倒排表中位置，然后才能知道这个term （人民）对应那些文档（{，2}），故首先要进行的是对term的查找，找到term所在的位置

以上述倒排表为例，假设，中华在倒排表中的偏移量为1，人民的偏移量为2，共和国为3，英雄为4，美食为5

这里的偏移量为距离文件起始的位置，知道了偏移量，就可以通过seek操作，将文件指针直接定位到目标term所在的位置，然后就可以读取文档ID，也就是查询的结果了。

另外很重要的一点是，lucene创建索引的时候会保证倒排表的term是有序的。

     Lucene采用128跳跃表的方式创建索引，原理如下

由于lucene索引本身是有序的特点,lucene会在索引文件里存储一些关键term，

 假设倒排表里一共有1280个term,那么第1个term,第129个term,257…,1281 一个11个关键term以及偏移量会存储在索引文件tii中。

在进行term的检索前，lucene会将tii文件中的所有关键term，加载到内 存里，以数组的形式存储，当然也是有序的。当我们要检索一个term，首先会在内存里检索此term会落在那两个关键term之间，因为有序的原因，目标 term肯定会在这两个term之间，然后根据两个关键term中较小的term的偏移量，从倒排表tis文件中的偏移量的位置之后开始查找，由于跳跃表 的间隔是128位，那么最多比较128次就可以查找到这个term了。

     128跳跃表存在的问题

在进行term检索前，索引文件tii要全部加载到内存里，如果term的数量比较 少，那么不会存在问题，但是如果term特别多，比如说10亿，那么也要消耗几十G的内存（视term的长度不同而不同），普通物理机器一般是没有这么大 的内存的，所以导致lucene因程序崩溃而无法进行检索。另外每次加载索引也是很消耗时间的，如果初级开发者，使用不当，每次都是打开与关闭 lucene，那就会导致索引文件被反复重复加载，也是影响检索性能的。

     那怎么解决？

Lucene倒排表tis文件有个显著的特点是，term是有序的，而偏移量是定长的long类型，那么正好适合还用二分查找（折半查找）。

Tii索引文件存储的内容修改为lucene倒排表tis中的每个term的偏移量。根据偏移量我们可以到tis文件中得到对应的term的值。

假设倒排表中一共有1000个term,我们的目标term在第501个term上， 那么二分查找首先会根据中间（折半）位置的term进行比较，也就是根第500个位置的term进行比较，发现目标term应该在500到1000这个区 间内，然后这个区间内在进行折半查找，定位在500~750这个区间，然后进一步定位500~625,500~564，500~532,500~516， 最终找到目标term的偏移量。

 

在这个过程中，索引文件没有加载到内存里，对内存的依赖较少，假设有100亿个term，那么最坏的情况，进行折半的次数为34次。

另外由于折半的特点，1/2,1/4,1/8,1/16…这些点都是高命中的点，可以 根据物理机器的内存多少，也可以预先加载到内存里，但是与128跳跃表相比，这里加载内存里的都是高命中的区域，对内存的使用率会高很多。如果缓存 16384个位置，那么久可以额外减少14次seek，那么100亿仅仅需要20次的文件seek，但是如果跟原先的进行对比的话，旧的128跳跃表最坏 情况下需要128次seek，平均为64次seek，远远高于二分法的seek次数。而且二分法由于可以在高命中点使用cache，可以进一步减少 cache的数量。

 

     存在问题以及细节的优化

随着term数量的增加,折半查找引起的seek的次数会增加，10000个term要进行12次查找，10万要进行15次，100万进行20次，1000万23次，一亿26次，10亿29次，100亿34次。

2. Term压缩方式由原先，存储上一条记录的差异，存储关键点的差异（这样会照成压缩比降低，但是二分法必须这样做）

3.如果索引二分查找文档差异<128则，保留原先链表顺序查找，调用scan方法（这样做尽管读的次数增多，但考虑磁盘的物理特点，操作系统通常有文件缓冲区，连续的数据读取速度会比不断的跳跃的seek快，物理硬盘适合读取连续的数据），这样可以用1~128此的连续seek，来减少约6~7次左右的跳跃性的seek.

4. 由于norms同样非常消耗内存，这里创建索引的时候禁用norms，待以后改进此处，当前lucene也存在此问题，不过也可以采用同样的二分法来解决此问题，禁止全部加载进内存。

 

1.        Lucene TermInfosReader使用的128位的跳跃表,示例如下

 

 

在检索的时候，跳跃表需要加载内存里，在千万级别内的term，检索速度比较理想（但是也需要1~128次的seek），但是如果term数量达到亿的级别，有可能会突破单台机器物理内存的限制，目前业界几乎都是采用分布式，打散成多个索引的方式来减少这个跳跃表的长度，但是单机也是能够支持上十亿key、value的检索（这个地方可以采用定长的数据类型，而且luceneTermInfos这种结构，本身就是有序的，可以支持二分法查找，如果在结合cache，不但不会像跳跃表那样耗费太多的内存,因减少了seek的数量，检索时间也会有所提升，而且支持无限大的term数量，取决于硬盘大小）

    当前lucene首次加载需要读取整个索引文件，一般需要成长连接的方式，对开发者要求较高，采用二分法的索引文件就没有此问题。

 

 

 

下表为对100W~10亿条md5值进行创建索引以及查询的情况

读的时间为查询10W条md5的时间，单位毫秒

写为创建完整索引的时间，单位为毫秒。

 

记录数	读10W记录时间	每条记录时间	创建索引时间	索引总大小	Tii文件大小
一百万	13667	0.13667	14338	87.6 MB	7.62 MB
二百万	14400	0.144	25508	175 MB	15.2 MB
一千万	20234	0.20234	120262	4.26 GB	381 MB
一亿	2289399	22.89399	1360215	8.51 GB	762 MB
五亿	3793413	37.93413	12249876	42.6 GB	3.72 GB
十亿	5063614	50.63614	27365596	85.2 GB	7.45 GB

 

 

Lucene压缩算法简介

Lucene采用压缩的方式进行创建索引

         对于字符串类型

文件链表的第一条记录存储的是完整的信息，第二条记录存储的是跟第一条记录的差异。

举例来说，第一条记录为 abcdefg,如果第二条记录为abcdefh，他们的差异只有h，故第二条记录仅仅会存储一个长度，加上差异的字符，就是存储6+h

对于lucene这种索引结构来说，由于索引是排序过的，故压缩比非常可观。

         数值类型的

常见对于文件偏移量的压缩，与字符串形式的压缩类似，但采用的与前一条记录的差值进行存储，如果第一条记录为8，第二条记录为9，则第二条仅仅存储9-8=1,，lucene存储整形也是变长的索引，lucene通常是以append的方式创建索引，故这种压缩方式很有效。

         新索引对于压缩的改变

由于上述lucene的 压缩方式，在修改成二分法的时候，无法使用，故需要放弃一定的压缩率。我们采取定义关键点的方式来压缩，关键点存储完整数据，后面的点跟关键点比较差异， 这个跟视频图像压缩的关键帧非常相似，关键帧存储完整的图像信息，后面的帧仅仅存储差异，变化。这样可以节省计算差异的时间消耗（对lucene来说这点微不足道，不是这里解决的主要问题），但是压缩比会降低。

评论

1 楼 zhuhuixiao 2014-02-27  

lucene的跳跃表是有层次的