Lucene Hack之通过缩小搜索结果集来提升性能 (1)

作者：caocao（网络隐士），http://www.caocao.name，http://www.caocao.mobi
转载请注明来源：http://www.iteye.com/topic/78884

一、缘起
Lucene在索引文件上G之后的搜索性能下降很严重，随便跑个搜索就要上0.x秒。如果是单线程搜索那么性能尚可，总可以在0.x秒返回结果，如果是Web式的多线程访问，由于Lucene的内部机制导致数据被大量载入内存，用完后立即丢弃，随之引起JVM频繁GC，性能极其低下，1-10秒的长连接比比皆是。这也是世人为之诟病的Lucene应用瓶颈问题，那么是否有解决方法呢？

二、思路
我们来观察Google, Baidu的搜索，有一个总体的感觉就是搜索结果多的关键词耗时比较少，结果少的关键词耗时反而多，且结果多的时候会说“约******个结果”。隐士猜测Google, Baidu的算法是找到前n个结果后停止扫描索引，根据前n个结果来推断总共有多少个结果，此猜想可由Google, Baidu翻页限制而得到部分验证。
再看Lucene，其Hits.length()返回的总是精确的结果，如果可以让Lucene也返回模糊的结果，那么索引文件就算是10G也可以轻松应对了。

三、探索
隐士带着这个问题访名山、觅高人，可惜没有找到前人的成果，可能是隐士走的路不够勤，如有类似的解决方案，隐士不吝赐教。
无奈之下，隐士详细研究了Lucene 2.1.0源码，准备重新发明轮子。
一般来说大多数搜索应用中的Query都会落在BooleanQuery上，隐士就拿它开刀。一路看来，BooleanScorer2里的一个method吸引了隐士，代码如下：

  public void score(HitCollector hc) throws IOException {
    if (countingSumScorer == null) {
      initCountingSumScorer();
    }
    while (countingSumScorer.next()) {
      hc.collect(countingSumScorer.doc(), score());
    }
  }

在while循环里嵌入写日志代码可证结果集有多大，此处就循环了多少次。countingSumScorer.next()的意思是找到下一个符合boolean规则的document，找到后放入HitCollector，这HitCollector后面会换个马甲放在大家熟悉的Hits里面。
如果可以在这个while循环里嵌一个break，到一定数量就break出来，性能提升将相当明显。这个代码相当简单，果然大幅提高了性能，带来的副作用是结果不太准，这个可以通过调整业务模型、逻辑来修正。毕竟这是一条提升Lucene性能的有效方法。
细细想来，正是由于这个break会导致结果集大的关键词提前出来，搜索时间少，结果集小的关键词不可避免会走完整个索引，相应的搜索时间会长一点。

四、效果
由于具体嵌入代码的过程极其繁琐，隐士将在第二回详细讲解。这第一回先来个Big picture。
历尽千辛万苦，隐士终于搞定了这套程序，效果可以从隐士做的视频搜索http://so.mdbchina.com/video/%E7%BE%8E%E5%A5%B3看出。
这个关键词“美女”可以找到18万个视频，平均0.5秒返回结果，现在用上了新算法，只要0.06x秒返回结果，而且返回结果足够好了，估算的8.5万个结果虽然离18万有很大差距，不过由于是估算的，差2-3倍应属可以接受的。
由算法的特性可知，while里面的hc.collect总可以在常量时间内完成，循环次数又是<=常量，该算法的时间复杂度只和BooleanQuery的复杂程度相关，和索引文件大小以及命中的Document在索引文件内的分布密度没有关系，因为BooleanQuery的复杂程度决定了countingSumScorer.next()需要经过多少次判断、多少次读取索引文件，countingSumScorer.next()正是整个算法中耗时不定的部分。
现在这个视频搜索的索引文件接近3G，热门关键词可以在0.0x秒返回结果，隐士相信即使以后索引文件上到10G，依然可以在0.0x秒返回结果。

(注：这个视频搜索实际使用效果会打折扣，因为后台索引也在这台机器上，以后会分服务器，现在暂时在一起。)

呵呵，不知不觉写了那么多，下一回(http://www.iteye.com/topic/80073)将上代码，敬请关注。

评论

8 楼 active1001 2007-09-06  

不过hc上面花的时候和其他的部分比起来，还是比较少的。

7 楼 geszJava 2007-06-03  

不错的思路,我打算引入我们的搜索引擎中,不过想请问下楼主,改动需要多少时间呢?

6 楼 cherami 2007-05-12  

个人感觉使用代码覆盖工具辅助查找性能瓶颈是比较有用的，时间是一个指标，执行的总次数也是一个很重要的指标。

5 楼 shaucle 2007-05-12  

"先纯看代码看到这里觉得是瓶颈才动手测试的"

强!

先理论,再实践,再理论...

4 楼 caocao 2007-05-11  

shaucle 写道

其它的地方也一样可打印时间差啊,hc在后续处理过程一样

俺都这样解决好几个performance issue了.

agree, 我也这么做过实验，然后总结出来限制hc的大小是行之有效的方法，不过我是先纯看代码看到这里觉得是瓶颈才动手测试的，呵呵

3 楼 shaucle 2007-05-11  

其它的地方也一样可打印时间差啊,hc在后续处理过程一样

俺都这样解决好几个performance issue了.

2 楼 caocao 2007-05-11  

shaucle 写道

在
#   while (countingSumScorer.next()) { 
#     hc.collect(countingSumScorer.doc(), score()); 
#   }
前后打印个时间差
其它的地方也一样，不就都能看出来了？

呵呵，hc在后续处理过程中还要排序，hc的大小也相当影响性能，性能瓶颈并非单在这一处，不过在这里限制hc的大小就可以使后续排序过程的时间永远小于某一常量。
还有多线程耗尽内存引发的JVM频繁GC也是重要因素，减小hc可以减少内存的耗用，减少GC次数。
这些貌似无法简单通过打印时间差来测量。

1 楼 shaucle 2007-05-11  

在
#   while (countingSumScorer.next()) { 
#     hc.collect(countingSumScorer.doc(), score()); 
#   }
前后打印个时间差
其它的地方也一样，不就都能看出来了？