大规模可扩展索引技术的研究和系统实现.doc
约69页DOC格式手机打开展开
大规模可扩展索引技术的研究和系统实现, 硕士论文 69页共计28835字摘 要随着互联网的发展，原始的数据库系统无法满足大数据量相关性检索的需求。从而基于倒排表的索引系统越来越多的应用在各项服务中。但是索引系统和数据库系统一样，有着较为复杂的内部逻辑和外部行为，如何创建我们需要的索引系统，如何优化我们的索引系统，是困扰很...
内容介绍
此文档由会员 bfxqt 发布
大规模可扩展索引技术的研究和系统实现 硕士论文
69页共计28835字
摘 要
随着互联网的发展，原始的数据库系统无法满足大数据量相关性检索的需求。从而基于倒排表的索引系统越来越多的应用在各项服务中。但是索引系统和数据库系统一样，有着较为复杂的内部逻辑和外部行为，如何创建我们需要的索引系统，如何优化我们的索引系统，是困扰很多索引系统构建者和使用者的难题。
本文的研究范畴是用于信息检索的索引系统，通过一个真实的索引系统——Paradise索引系统，本文从三个方面进行分析和研究：对索引系统进行功能模块上的分析；对索引系统开发和使用中的性能问题的研究和分析；对一个实际系统的系统实现的详细。具体为：
1) 索引系统的模块分析
本文详细分析了作为一个复杂系统的索引系统，其创建和使用都受到很多条件的制约。本文分析了索引系统的常见的需求，比如如何对原始的文档集合进行分析，如何设计索引内部文档的表示能力，索引如何创建，如何存储等，划分了一系列基本的功能模块。
2) 索引系统的性能分析
因为索引系统的目的是快速的响应检索需求，所以效率问题一直是索引技术的核心问题。在模块功能分析的基础之上，本文进一步分析了索引创建和检索中常见的性能问题，提出了基本的解决方案。同时，对于如何对索引系统进行整体的和局部的量化分析，引入了DQ法则，尝试给出一个指导实践的经验公式。
3) Paradise索引系统的实现分析
对于问题的分析，需要一个具体的系统进行实践。在深入研究天网搜索引擎已有的索引系统和相关索引系统基础上，同时在大量阅读了相关专业文献之后，我们进行了分析和研究，设计实现了863课题支持的Paradise项目的索引系统。本文以系统的基本模块和重要接口为核心，分析了系统的基本框架能力以及如何进一步对系统进行扩充。
目录
摘 要 3
Abstract 4
目录 5
第一章 绪 论 6
1.1 索引系统背景 6
1.1.1 互联网服务系统 6
1.1.2 Data / Query 法则 7
1.1.3 需求快速查询的场景 7
1.2 和数据库系统的比较 8
1.2.1 数据库系统的能力 8
1.2.2 索引系统和数据库系统的异同 8
1.3 索引系统的简单用例 9
1.3.1 索引系统基本模块 10
1.3.2 索引系统基本流程 10
1.4 本文的主要工作 11
1.4.1 本文的主要研究点 11
1.4.2 本文的主要创新点 11
1.5 本文组织结构 11
第二章 索引系统分析 12
2.1 索引核心模块分析 12
2.1.1 分析模块 12
2.1.2 文档表示模块 12
2.1.3 存储模块 15
2.1.4 索引创建 15
2.1.5 存储镜像的逻辑视图 18
2.1.6 索引检索 19
2.2 大规模索引专有模块 20
2.2.1 压缩模块 20
2.2.2 缓存模块 26
2.3 动态索引 28
2.3.1 版本控制 29
2.3.2 内存索引 31
2.4 分布式索引 31
2.4.1 可用性和可靠性与DQ法则 32
2.4.2 索引切分和索引冗余 34
2.4.3 针对可用性和效率的解决方案 35
2.4 本章小结 35
第三章 索引优化 36
3.1 索引创建的优化 36
3.1.1 创建时期内存压缩 36
3.1.2 动态索引二路归并的块合并时机 37
3.1.3 大索引多路归并方法 38
3.2 索引检索效率的优化 39
3.2.1 检索时效率分析 39
3.2.2 使用块状压缩和跳查来降低CPU使用 39
3.2.3 使用缓存机制来降低IO 43
3.3 索引常数 44
3.3.1 单机的服务能力上限 44
3.3.2 整体服务优化 45
3.3.3 单机索引常数 46
3.4 本章小结 46
第4章 Paradise索引系统框架 48
4.1 系统目的 48
4.1.1 面向搜索引擎服务 48
4.1.2 可扩展性，可实验性 48
4.2 基本模块详细分析 48
4.2.1 分析模块 49
4.2.2 文档表述模块 50
4.2.3 存储模块 51
4.2.4 压缩模块 52
4.2.5 缓存模块 53
4.2.6 索引模块 54
4.3 索引创建流程用例分析 57
4.4 索引提供的检索接口用例分析 59
第五章 总结和展望 63
5.1 本文总结 63
5.2 进一步工作 63
参考文献 65
致谢 68
关键词：信息检索，索引系统，索引优化，倒排表
参考文献
[1] 彭波. (2004). 搜索引擎检索系统的效率优化与效果评估研究. 北京大学.
[2] Zobel, J. and Moffat, A, Inverted files for text search engines, ACM Computing Surveys (CSUR), 2006, ACM New York, NY, USA
[3] Witten, I. H., Moffat, A. & Bell, T. C. (1999), Managing Gigabytes: Compressing and Indexing Documents and Images, second edn, Morgan Kaufmann, San Francisco, California.
[4] Zhu, M. and Shi, S. and Li, M. and Wen, J.R., Effective top-k computation in retrieving structured documents with term-proximity support, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007, ACM New York, NY, USA
[5] Strohman, T., DYNAMIC COLLECTIONS IN INDRI, Technical report, Center for Intelligent Information Retrieval, 2005
[6] Strohman, T. and Croft, W.B. Low Latency Index Maintenance in Indri, OSIR 2006
[7] Frakes, W.B. and Baeza-Yates, R., Information retrieval: data structures and algorithms, 1992, Prentice-Hall, Inc. Upper Saddle River, NJ, USA
[8] Brown, E.W. and Callan, J.P. and Croft, W.B. Fast incremental indexing for full-text information retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, 1994
[9] Scholer, F. and Williams, H.E. and Yiannis, J. and Zobel, J., Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, 2002, ACM Press New York, NY, USA
[10] Zobel, J. and Moffat, A. Adding Compression to a Full-text Retrieval System, Software - Practice and Experience, 1995
[11] Williams, H.E. and Zobel, J., Compressing Integers for Fast File Access, 1999, Br Computer Soc
[12] Scholer, F. and Williams, H.E. and Yiannis, J. and Zobel, J., Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, 2002, ACM Press New York, NY, USA
[13] Zukowski, M. and Heman, S. and Nes, N. and Boncz, P., Super-Scalar RAM-CPU Cache Compression, Proceedings of the International Conference of Data Engineering (IEEE ICDE), Atlanta, GA, USA, 2006
[14] Baeza-Yates, R. and Gionis, A. and Junqueira, F. and Murdock, V. and Plachouras, V. and Silvestri, F., The impact of caching on search engines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, 2007, ACM Press New York, NY, USA
[15] Long, X. and Suel, T., Three-Level Caching for Efficient Query Processing in Large Web Search Engines, World Wide Web, 2006, Springer
[16] Lempel, R. and Moran, S., Predictive caching and prefetching of query results in search engines, Proceedings of the 12th international conference on World Wide Web, 2003, ACM Press New York, NY, USA
[17] Saraiva, P.C. and de Moura, E.S. and Ziviani, N. and Meira, W. and Fonseca, R. and Riberio-Neto, B., Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, 2001, ACM Press New York, NY, USA
[18] Eric W. Brown, Fast evaluation of structured queries for information retrieval,SIGIR’95:Proceedings of the 18th annual international ACM SIGIRconference onResearch and development in information retrieval (NewYork, NY, USA),ACM Press, 1995, pp. 30–38.A
[19] Nicholas Lester, Justin Zobel, and Hugh E. Williams, In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems, Proceedings of the 27th conference on Australasian computer science, Australian Computer Society, Inc., 2004, pp. 15–23.A
[20] N. Lester, A. Moffat, and J. Zobel, "Fast on-line index construction by geometric partitioning",Proceedings of the ACM CIKM Conference on Information and Knowledge Management, A. Chowdhury, N. Fuhr, M. Ronthaler, H.-J. Schek, and W. Teiken (eds), Bremen, Germany, November 2005. pp. 776-783.
[21] Stefan Büttcher, Charles L. A. Clarke, and Brad Lushman. Hybrid Index Maintenance for Growing Text Collections. Proceedings of the 29th ACM Conference on Research and Development on Information Retrieval (SIGIR 2006). Seattle, USA, August 2006.
[22] Zobel, J., Moffat, A. & Ramamohanarao, K. (1998), “Inverted files versus signature files for text indexing”, ACM Transactions on Database Systems 23(4), 453–490.
[[29] Carmel, D. and Cohen, D. and Fagin, R. and Farchi, E. and Herscovici, M. and Maarek, Y.S. and Soffer, A., Static index pruning for information retrieval systems, 2001, ACM Press New York, NY, USA
[30] Carmel, D. and Amitay, E. and Herscovici, M. and Maarek, Y. and Petruschka, Y. and Soffer, A., Juru at TREC 10-Experiments with Index Pruning, Proceedings of NIST TREC, 2001
[31] S Büttcher, CLA Clarke, A document-centric approach to static index pruning in text retrieval systems, Proceedings of the 15th ACM international conference on Information and knowledge management, 2006, ACM Press New York, NY, USA
[32] Performance of Compressed Inverted List Caching in Search Engines, 2008, World Wide Web.
[33] Brewer, E.A., Lessons from Giant-Scale Services, IEEE INTERNET COMPUTING, 2001
[34] Guo, R. and Cheng, X. and Xu, H. and Wang, B., Efficient on-line index maintenance for dynamic text collections by using dynamic balancing tree, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007
69页共计28835字
摘 要
随着互联网的发展，原始的数据库系统无法满足大数据量相关性检索的需求。从而基于倒排表的索引系统越来越多的应用在各项服务中。但是索引系统和数据库系统一样，有着较为复杂的内部逻辑和外部行为，如何创建我们需要的索引系统，如何优化我们的索引系统，是困扰很多索引系统构建者和使用者的难题。
本文的研究范畴是用于信息检索的索引系统，通过一个真实的索引系统——Paradise索引系统，本文从三个方面进行分析和研究：对索引系统进行功能模块上的分析；对索引系统开发和使用中的性能问题的研究和分析；对一个实际系统的系统实现的详细。具体为：
1) 索引系统的模块分析
本文详细分析了作为一个复杂系统的索引系统，其创建和使用都受到很多条件的制约。本文分析了索引系统的常见的需求，比如如何对原始的文档集合进行分析，如何设计索引内部文档的表示能力，索引如何创建，如何存储等，划分了一系列基本的功能模块。
2) 索引系统的性能分析
因为索引系统的目的是快速的响应检索需求，所以效率问题一直是索引技术的核心问题。在模块功能分析的基础之上，本文进一步分析了索引创建和检索中常见的性能问题，提出了基本的解决方案。同时，对于如何对索引系统进行整体的和局部的量化分析，引入了DQ法则，尝试给出一个指导实践的经验公式。
3) Paradise索引系统的实现分析
对于问题的分析，需要一个具体的系统进行实践。在深入研究天网搜索引擎已有的索引系统和相关索引系统基础上，同时在大量阅读了相关专业文献之后，我们进行了分析和研究，设计实现了863课题支持的Paradise项目的索引系统。本文以系统的基本模块和重要接口为核心，分析了系统的基本框架能力以及如何进一步对系统进行扩充。
目录
摘 要 3
Abstract 4
目录 5
第一章 绪 论 6
1.1 索引系统背景 6
1.1.1 互联网服务系统 6
1.1.2 Data / Query 法则 7
1.1.3 需求快速查询的场景 7
1.2 和数据库系统的比较 8
1.2.1 数据库系统的能力 8
1.2.2 索引系统和数据库系统的异同 8
1.3 索引系统的简单用例 9
1.3.1 索引系统基本模块 10
1.3.2 索引系统基本流程 10
1.4 本文的主要工作 11
1.4.1 本文的主要研究点 11
1.4.2 本文的主要创新点 11
1.5 本文组织结构 11
第二章 索引系统分析 12
2.1 索引核心模块分析 12
2.1.1 分析模块 12
2.1.2 文档表示模块 12
2.1.3 存储模块 15
2.1.4 索引创建 15
2.1.5 存储镜像的逻辑视图 18
2.1.6 索引检索 19
2.2 大规模索引专有模块 20
2.2.1 压缩模块 20
2.2.2 缓存模块 26
2.3 动态索引 28
2.3.1 版本控制 29
2.3.2 内存索引 31
2.4 分布式索引 31
2.4.1 可用性和可靠性与DQ法则 32
2.4.2 索引切分和索引冗余 34
2.4.3 针对可用性和效率的解决方案 35
2.4 本章小结 35
第三章 索引优化 36
3.1 索引创建的优化 36
3.1.1 创建时期内存压缩 36
3.1.2 动态索引二路归并的块合并时机 37
3.1.3 大索引多路归并方法 38
3.2 索引检索效率的优化 39
3.2.1 检索时效率分析 39
3.2.2 使用块状压缩和跳查来降低CPU使用 39
3.2.3 使用缓存机制来降低IO 43
3.3 索引常数 44
3.3.1 单机的服务能力上限 44
3.3.2 整体服务优化 45
3.3.3 单机索引常数 46
3.4 本章小结 46
第4章 Paradise索引系统框架 48
4.1 系统目的 48
4.1.1 面向搜索引擎服务 48
4.1.2 可扩展性，可实验性 48
4.2 基本模块详细分析 48
4.2.1 分析模块 49
4.2.2 文档表述模块 50
4.2.3 存储模块 51
4.2.4 压缩模块 52
4.2.5 缓存模块 53
4.2.6 索引模块 54
4.3 索引创建流程用例分析 57
4.4 索引提供的检索接口用例分析 59
第五章 总结和展望 63
5.1 本文总结 63
5.2 进一步工作 63
参考文献 65
致谢 68
关键词：信息检索，索引系统，索引优化，倒排表
参考文献
[1] 彭波. (2004). 搜索引擎检索系统的效率优化与效果评估研究. 北京大学.
[2] Zobel, J. and Moffat, A, Inverted files for text search engines, ACM Computing Surveys (CSUR), 2006, ACM New York, NY, USA
[3] Witten, I. H., Moffat, A. & Bell, T. C. (1999), Managing Gigabytes: Compressing and Indexing Documents and Images, second edn, Morgan Kaufmann, San Francisco, California.
[4] Zhu, M. and Shi, S. and Li, M. and Wen, J.R., Effective top-k computation in retrieving structured documents with term-proximity support, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007, ACM New York, NY, USA
[5] Strohman, T., DYNAMIC COLLECTIONS IN INDRI, Technical report, Center for Intelligent Information Retrieval, 2005
[6] Strohman, T. and Croft, W.B. Low Latency Index Maintenance in Indri, OSIR 2006
[7] Frakes, W.B. and Baeza-Yates, R., Information retrieval: data structures and algorithms, 1992, Prentice-Hall, Inc. Upper Saddle River, NJ, USA
[8] Brown, E.W. and Callan, J.P. and Croft, W.B. Fast incremental indexing for full-text information retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, 1994
[9] Scholer, F. and Williams, H.E. and Yiannis, J. and Zobel, J., Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, 2002, ACM Press New York, NY, USA
[10] Zobel, J. and Moffat, A. Adding Compression to a Full-text Retrieval System, Software - Practice and Experience, 1995
[11] Williams, H.E. and Zobel, J., Compressing Integers for Fast File Access, 1999, Br Computer Soc
[12] Scholer, F. and Williams, H.E. and Yiannis, J. and Zobel, J., Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, 2002, ACM Press New York, NY, USA
[13] Zukowski, M. and Heman, S. and Nes, N. and Boncz, P., Super-Scalar RAM-CPU Cache Compression, Proceedings of the International Conference of Data Engineering (IEEE ICDE), Atlanta, GA, USA, 2006
[14] Baeza-Yates, R. and Gionis, A. and Junqueira, F. and Murdock, V. and Plachouras, V. and Silvestri, F., The impact of caching on search engines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, 2007, ACM Press New York, NY, USA
[15] Long, X. and Suel, T., Three-Level Caching for Efficient Query Processing in Large Web Search Engines, World Wide Web, 2006, Springer
[16] Lempel, R. and Moran, S., Predictive caching and prefetching of query results in search engines, Proceedings of the 12th international conference on World Wide Web, 2003, ACM Press New York, NY, USA
[17] Saraiva, P.C. and de Moura, E.S. and Ziviani, N. and Meira, W. and Fonseca, R. and Riberio-Neto, B., Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, 2001, ACM Press New York, NY, USA
[18] Eric W. Brown, Fast evaluation of structured queries for information retrieval,SIGIR’95:Proceedings of the 18th annual international ACM SIGIRconference onResearch and development in information retrieval (NewYork, NY, USA),ACM Press, 1995, pp. 30–38.A
[19] Nicholas Lester, Justin Zobel, and Hugh E. Williams, In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems, Proceedings of the 27th conference on Australasian computer science, Australian Computer Society, Inc., 2004, pp. 15–23.A
[20] N. Lester, A. Moffat, and J. Zobel, "Fast on-line index construction by geometric partitioning",Proceedings of the ACM CIKM Conference on Information and Knowledge Management, A. Chowdhury, N. Fuhr, M. Ronthaler, H.-J. Schek, and W. Teiken (eds), Bremen, Germany, November 2005. pp. 776-783.
[21] Stefan Büttcher, Charles L. A. Clarke, and Brad Lushman. Hybrid Index Maintenance for Growing Text Collections. Proceedings of the 29th ACM Conference on Research and Development on Information Retrieval (SIGIR 2006). Seattle, USA, August 2006.
[22] Zobel, J., Moffat, A. & Ramamohanarao, K. (1998), “Inverted files versus signature files for text indexing”, ACM Transactions on Database Systems 23(4), 453–490.
[[29] Carmel, D. and Cohen, D. and Fagin, R. and Farchi, E. and Herscovici, M. and Maarek, Y.S. and Soffer, A., Static index pruning for information retrieval systems, 2001, ACM Press New York, NY, USA
[30] Carmel, D. and Amitay, E. and Herscovici, M. and Maarek, Y. and Petruschka, Y. and Soffer, A., Juru at TREC 10-Experiments with Index Pruning, Proceedings of NIST TREC, 2001
[31] S Büttcher, CLA Clarke, A document-centric approach to static index pruning in text retrieval systems, Proceedings of the 15th ACM international conference on Information and knowledge management, 2006, ACM Press New York, NY, USA
[32] Performance of Compressed Inverted List Caching in Search Engines, 2008, World Wide Web.
[33] Brewer, E.A., Lessons from Giant-Scale Services, IEEE INTERNET COMPUTING, 2001
[34] Guo, R. and Cheng, X. and Xu, H. and Wang, B., Efficient on-line index maintenance for dynamic text collections by using dynamic balancing tree, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007
