`
longgangbai
  • 浏览: 7339838 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

限制lucene的遍历结果.

阅读更多

Lucene Hack之通过缩小搜索结果集来提升性能
作者: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());
}
}

<script>render_code();</script>



在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秒返回结果。

五、原则
1、不改动lucene-core的代码
肆意改动lucene-core的代码实在是很不道德的事情,而且会导致后期维护升级的大量问题。如果真的有这等迫切需求,还不如加入lucene开发组,尽一份绵薄之力。看官说了,隐士你怎么不去啊,唉,代码比较丑陋,没脸去人家那里,后文详述。
2、不改动lucene索引文件格式
道理同上。
3、替换常规搜索的接口尽量少
这样可以方便来回切换标准搜索和这个搜索,减小代码修改、维护的成本。
4、命名规范
所有增加的类名均以Inaccurate开头,其余遵循lucene命名规范。

六、限制
1、隐士只做了BooleanWeight2的替代品,如果Weight不是BooleanWeight2,则等同于常规搜索。
2、如果搜索结果集小于等于最大允许的结果集,则等同于常规搜索。

七、文件


代码
org.apache.lucene.search
InaccurateBooleanScorer2.java // BooleanScorer2的替代品
InaccurateBooleanWeight2.java // BooleanWeight2的替代品
InaccurateHit.java // Hit的替代品
InaccurateHitIterator.java // HitIterator的替代品
InaccurateHits.java // Hits的替代品
InaccurateIndexSearcher.java // IndexSearcher的替代品
org.apache.lucene.util
InaccurateResultAggregation.java // 放搜索统计信息的value object

<script>render_code();</script>


八、实战
1、InaccurateIndexSearcher
InaccurateIndexSearcher extends IndexSearcher,结构很简单,增加了两个成员变量:maxNumberOfDocs和inaccurateResultAggregation,以及几个methods。
丑陋的部分来了:


代码
public void search(Weight weight, Filter filter, final HitCollector results, boolean ascending) throws IOException {
...
if (weight.getClass().getSimpleName().equals("BooleanWeight2")) { // hook BooleanWeight2
InaccurateBooleanWeight2 inaccurateBooleanWeight2 = new InaccurateBooleanWeight2(
this, weight.getQuery());
float sum = inaccurateBooleanWeight2.sumOfSquaredWeights();
float norm = this.getSimilarity().queryNorm(sum);
inaccurateBooleanWeight2.normalize(norm); // bad smell
InaccurateBooleanScorer2 inaccurateBooleanScorer2 = inaccurateBooleanWeight2
.getInaccurateBooleanScorer2(reader, maxNumberOfDocs);
if (inaccurateBooleanScorer2 != null) {
inaccurateResultAggregation = inaccurateBooleanScorer2
.getInaccurateTopAggregation(collector, ascending);
}
} else {
Scorer scorer = weight.scorer(reader);
if (scorer != null) {
scorer.score(collector);
}
}
...
}

<script>render_code();</script>
由于BooleanWeight2被lucene-core给藏起来了,instanceof都不能用,只好丑陋一把用weight.getClass().getSimpleName().equals("BooleanWeight2")。
把BooleanWeight2替换为InaccurateBooleanWeight2后代码老是搜不到任何结果,经过千辛万苦地调试才发现BooleanWeight2初始化后并不算完,需要拿到sum、norm,然后normalize一把,有点bad smell。
接着从InaccurateBooleanWeight2里拿到InaccurateBooleanScorer2,调用getInaccurateTopAggregation搜一把,这里ascending并没有发挥作用,原因相当复杂,隐士引入ascending的本意是调整lucene扫描索引的方式,docID小->大或docID大->小,后来调整了建索引的方式就不需要这个了,所以隐士只是留这个接口以后用,万一以后lucene-core支持双向扫描索引即可启用。
2、InaccurateHits
InaccurateIndexSearcher里面调用search其实是调用new InaccurateHits(this, query, null, sort, ascending)。getMoreDocs会反向调用新写的search方法。
上代码:

代码
...
TopDocs topDocs = (sort == null) ? searcher.search(weight, filter, n,
ascending) : searcher
.search(weight, filter, n, sort, ascending);
length = topDocs.totalHits;
InaccurateResultAggregation inaccurateResultAggregation = searcher
.getInaccurateResultAggregation();
if (inaccurateResultAggregation == null) {
totalLength = length;
} else {
accurate = inaccurateResultAggregation.isAccurate();
if (inaccurateResultAggregation.isAccurate()) {
totalLength = inaccurateResultAggregation
.getNumberOfRecordsFound();
} else {
int maxDocID = searcher.maxDoc();
totalLength = 1000 * ((int) Math
.ceil((0.001
* maxDocID
/ (inaccurateResultAggregation.getLastDocID() + 1) * inaccurateResultAggregation
.getNumberOfRecordsFetched()))); // guessing how many records there are
}
}
...

<script>render_code();</script>
代码没什么特别的,除了一个猜测记录总数的算法。lucene从docID小向大的扫,由于上回说了扫到一半会跳出来,那么由最后扫到的lastDocID和maxDocID的比例可以猜测总共有多少条记录,虽然不是很准,但是数量级的精度是可以保证的,反正一般用户只能看到前1000条记录,具体有多少对用户来说不过是过眼云烟。
3、InaccurateBooleanWeight2
InaccurateBooleanWeight2没什么好说的,就是个拿到InaccurateBooleanScorer2的跳板。
4、InaccurateBooleanScorer2
InaccurateBooleanScorer2的代码均来自BooleanScorer2,由于BooleanScorer2从设计上来说并不准备被继承,隐士只好另起炉灶,bad smell啊。隐士没有修改任何从BooleanScorer2过来的代码,只加了getMaxNumberOfDocs、getInaccurateTopAggregation、getAccurateBottomAggregation。getInaccurateTopAggregation是扫描到maxNumberOfDocs后立即跳出来,所以结果会有所不准,getAccurateBottomAggregation总是保留最后maxNumberOfDocs个结果,结果也会有所不准,但是统计值是准的,因为每次都走完了所有索引。由两者差异可知getAccurateBottomAggregation性能会差一点,准确性和性能不可兼得啊。

代码
public InaccurateResultAggregation getInaccurateTopAggregation(
HitCollector hc, boolean ascending) throws IOException {
// DeltaTime dt = new DeltaTime();
if (countingSumScorer == null) {
initCountingSumScorer();
}
int lastDocID = 0;
boolean reachedTheEnd = true;
int numberOfRecordsFetched = 0;
while (countingSumScorer.next()) {
lastDocID = countingSumScorer.doc();
float score = score();
hc.collect(lastDocID, score);
numberOfRecordsFetched++;
if (numberOfRecordsFetched >= maxNumberOfDocs) {
reachedTheEnd = !countingSumScorer.next();
break;
}
}
// System.out.println(dt.getTimeElasped());
/*
* This method might cast the rest away. So it might be inaccurate.
*/
return new InaccurateResultAggregation(lastDocID, ascending,
reachedTheEnd, numberOfRecordsFetched, numberOfRecordsFetched);
}

public InaccurateResultAggregation getAccurateBottomAggregation(
HitCollector hc, boolean ascending) throws IOException {
// DeltaTime dt = new DeltaTime();
if (countingSumScorer == null) {
initCountingSumScorer();
}
LinkedList resultNodes = new LinkedList();
boolean isFull = false;
int lastDocID = 0;
int index = 0;
int numberOfRecordsFound = 0;
while (countingSumScorer.next()) {
lastDocID = countingSumScorer.doc();
float score = score();
resultNodes.add(new ResultNode(lastDocID, score));
if (isFull) {
resultNodes.removeFirst();
}
index++;
numberOfRecordsFound++;
if (index >= maxNumberOfDocs) {
isFull = true;
index = 0;
// break;
}
}
for (ResultNode resultNode : resultNodes) {
hc.collect(resultNode.getDoc(), resultNode.getScore());
}
// System.out.println(dt.getTimeElasped());

/*
* Since this method runs full scan against all matched docs, it's
* accurate at all.
*/
return new InaccurateResultAggregation(lastDocID, ascending, true,
resultNodes.size(), numberOfRecordsFound);
}

<script>render_code();</script>


九、总结
代码已经打包上传了,有隐士写的简略注释,调用方式写在readme.txt里面,只需要替换几行代码即可。
总的来说只要
1、将Searcher searcher = new IndexSearcher(reader);替换为InaccurateIndexSearcher searcher = new InaccurateIndexSearcher(reader, 5000);
2、将Hits hits = searcher.search(query);替换为InaccurateHits hits = searcher.search(query, sort, ascending);
就行了。欢迎大家试用,如果有什么改进,请务必把改进后的代码也开源给大家,互相学习,互相促进。
由于代码里面有几处有bad smell,隐士实在没脸去lucene开发组那里喊一嗓子。

分享到:
评论

相关推荐

    基于智能温度监测系统设计.doc

    基于智能温度监测系统设计.doc

    搜广推推荐系统中传统推荐系统方法思维导图整理-完整版

    包括userCF,itemCF,MF,LR,POLY2,FM,FFM,GBDT+LR,阿里LS-PLM 基于深度学习推荐系统(王喆)

    2023-04-06-项目笔记 - 第三百五十五阶段 - 4.4.2.353全局变量的作用域-353 -2025.12.22

    2023-04-06-项目笔记-第三百五十五阶段-课前小分享_小分享1.坚持提交gitee 小分享2.作业中提交代码 小分享3.写代码注意代码风格 4.3.1变量的使用 4.4变量的作用域与生命周期 4.4.1局部变量的作用域 4.4.2全局变量的作用域 4.4.2.1全局变量的作用域_1 4.4.2.353局变量的作用域_353- 2024-12-22

    和美乡村城乡融合发展数字化解决方案.docx

    和美乡村城乡融合发展数字化解决方案.docx

    CNN基于Python的深度学习图像识别系统

    基于Python的深度学习图像识别系统是一个利用卷积神经网络(CNN)对图像进行分类的先进项目。该项目使用Python的深度学习库,如TensorFlow,构建和训练一个模型,能够自动识别和分类图像中的对象。系统特别适合于图像处理领域的研究和实践,如计算机视觉、自动驾驶、医疗影像分析等。 项目的核心功能包括数据预处理、模型构建、训练、评估和预测。用户可以上传自己的图像或使用预定义的数据集进行训练。系统提供了一个直观的界面,允许用户监控训练进度,并可视化模型的性能。此外,系统还包括了一个模型优化模块,通过调整超参数和网络结构来提高识别准确率。 技术层面上,该项目使用了Python编程语言,并集成了多个流行的机器学习库,如NumPy、Pandas、Matplotlib等,用于数据处理和可视化。模型训练过程中,系统会保存训练好的权重,以便后续进行模型评估和预测。用户可以通过简单的API调用,将新的图像输入到训练好的模型中,获取预测结果。

    拳皇97.exe拳皇972.exe拳皇973.exe

    拳皇97.exe拳皇972.exe拳皇973.exe

    基于python和协同过滤算法的电影推荐系统

    基于python和协同过滤算法的电影推荐系统 基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法的电影推荐系统基于python和协同过滤算法

    DEV-CPP-RED-PANDA

    DEV-CPP-RED-PANDA

    Python语言求解旅行商(TSP)问题,算法包括禁忌搜索、蚁群算法、模拟退火算法等

    Python语言求解旅行商问题,算法包括禁忌搜索、蚁群算法、模拟退火算法等。

    pdfjs2.5.207和4.9.155

    pdfjs 用于在浏览器中查看/预览/打印pdf。 pdfjs 2.5.207 支持firefox/chrome/edge/ie11以上版本。 如果需要支持旧版本浏览器,可以使用这个,是未修改过的原版,支持打印和下载按钮。亲测有效。 pdf 4.9.155分两个包: pdfjs-4.9.155-dist.zip pdfjs-4.9.155-legacy-dist.zip

    建设项目现场高温人员中暑事故应急预案.docx

    建设项目现场高温人员中暑事故应急预案

    数据结构上机实验大作业-线性表选题.zip

    数据结构上机实验大作业-线性表选题.zip

    基于高德地图的校园导航全部资料+详细文档+高分项目.zip

    【资源说明】 基于高德地图的校园导航全部资料+详细文档+高分项目.zip 【备注】 1、该项目是个人高分项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(人工智能、通信工程、自动化、电子信息、物联网等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!

    全自动批量建站快速养权重站系统【纯静态html站群版】:(GPT4.0自动根据关键词写文章+自动发布+自定义友链+自动文章内链+20%页面加提权词)

    【静态站群程序视频演示,只有视频,不含程序,下载须知】【静态站群程序视频演示,只有视频,不含程序,下载须知】全自动批量建站快速养权重站系统【纯静态html站群版】:(GPT4.0自动根据关键词写文章+自动发布+自定义友链+自动文章内链+20%页面加提权词)

    9.30 SWKJ 男头7张+女头2张.zip

    9.30 SWKJ 男头7张+女头2张.zip

    基于java+springboot+vue+mysql的技术交流和分享平台 源码+数据库+论文(高分毕业设计).zip

    项目已获导师指导并通过的高分毕业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 包含:项目源码、数据库脚本、软件工具等,该项目可以作为毕设、课程设计使用,前后端代码都在里面。 该系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用价值。 项目都经过严格调试,确保可以运行!可以放心下载 技术组成 语言:java 开发环境:idea、vscode 数据库:MySql5.7以上 部署环境:maven 数据库工具:navicat

    一个通过单片机在各种屏幕上显示中文的解决方案.7z

    一个通过单片机在各种屏幕上显示中文的解决方案.7z

    Halcon模板匹配图像包

    图像

    线上辅导班系统-JAVA-基于springboot的线上辅导班系统的开发与设计(毕业论文)

    一、用户管理功能 用户注册与登录 学生注册:学生可以通过手机号、邮箱、社交账号等方式注册,填写个人信息(如姓名、年龄、学校等)。 家长/监护人账户:支持家长/监护人注册并管理学生账户,查看学习进度和成绩。 教师账户:教师可以注册并设置个人资料,上传资质认证文件。 管理员账户:管理员负责整个系统的管理,包括用户管理、课程管理、平台设置等。 用户权限管理 角色权限:系统根据用户类型(学生、家长、教师、管理员)分配不同权限,确保信息安全。 家长监督:家长可以查看子女的学习进度、成绩和教师反馈,参与学习监督。 个人资料管理 用户可以在个人中心更新基本信息,设置个人头像、联系方式、密码等。 支持学籍信息的维护,例如学生的年级、班级、课程历史等。 二、课程管理功能 课程设置 课程创建与编辑:教师或管理员可以创建和编辑课程内容,上传课件、视频、文档等教学材料。 课程分类:根据学科、年级、难度等维度进行课程分类,方便学生浏览和选择。 课程排课:管理员可以设置课程的时间表、教学内容和授课教师,并调整上课时间和频率。 课程安排与通知 课程预约:学生可以在线选择并预约感兴趣的课程,系统根据学生的时

    英特尔2021-2024年网络连接性和IPU路线图

    内容概要:本文档介绍了英特尔2021年至2024年的网络连接性产品和智能处理单元(IPU)的战略和技术路线图。涵盖了从10GbE到200GbE的不同系列以太网适配器的特性、性能和发布时间。详细列出了各个产品的关键功能,如PCIe接口、安全特性、RDMA支持等。同时,介绍了IPU的发展计划,包括200G、400G和800G的不同代次产品的性能提升和新的功能特点。 适合人群:从事网络工程、数据中心管理、IT架构设计的专业技术人员。 使用场景及目标:本文档主要用于了解英特尔未来几年在以太网适配器和IPU领域的技术和产品规划,帮助企业在采购和部署网络设备时做出决策。同时,为研究人员提供最新技术发展趋势的参考。 其他说明:文档内容涉及的技术细节和时间表可能会有变动,请以英特尔官方发布的最新信息为准。

Global site tag (gtag.js) - Google Analytics