应对海量数据检索：分布式局部索引的架构

张滇 岳磅 江小燕 毛睿

摘 要： 通过理论分析对全局和分布式索引架构进行了比较，分析了分布式全局索引架构所能够应对的数据规模的上界和分布式局部索引架构在特定数据规模下相应最优的机群规模等。可以证明，在海量数据背景条件下，由于需要求交集的查询结果数据量过大，会导致全局索引架构在查询结果求交集阶段处理时间过长，以致信息检索系统不能满足用户对系统响应时间的需求，因此局部索引架构会成为在面对海量数据时信息检索系统的必然选择。

关键词： 分布式索引； 局部索引； 全局索引； 海量数据

中图分类号：TP392 文献标志码：A 文章编号：1006-8228（2013）08-01-04

0 引言

信息检索系统（IRS：Information Retrieval System）已成为人们日常生活和学习中经常会使用到的工具（如文献检索、网页检索等）。随着数据规模的增大，信息检索系统开始采用分布式系统架构来解决所面临的大数据问题。由此而引出的索引如何在分布式系统之中组织与分布的问题即是分布式索引架构问题。全局索引架构（Global Index）与局部索引架构（Local Index）是两种最主要的分布式索引架构，几十年以来，大量的研究和实验对它们的优缺点进行了详细分析与比较。

全局索引架构针对整个数据集建立一个统一的索引，然后根据索引关键字的顺序将索引切分成多个索引片段，每个索引片段存放在一个单独的索引节点上。全局索引架构在执行一个检索时所需要访问的索引节点相对较少，但这也导致其每次读取的数据量较大；由于数据的处理需要集中在中间节点上进行，全局索引架构网络传输的数据量更大；所有的数据处理操作集中在中间节点上执行，在面对海量数据时这将成为全局索引架构不能满足用户需求的关键瓶颈；由于是针对整个数据集建立倒排索引，因此在全局索引架构在面对索引的更新与增量时相比局部索引架构难度更大。

分布式局部索引架构即是将大的数据集随机或者按照一定的规则划分成多个小数据集，针对每个小数据集建立单独的索引块，一般一个索引块会存放在一个单独的索引节点上。局部索引架构的每个索引节点独立的完成检索，因此具有较好的容灾容错性能；在索引更新及增量时，由于其每个索引节点相互独立，因此更新与增量的影响范围较小；由于索引节点返回给中间节点的数据都是经过处理的，因此相比全局索引架构而言局部索引架构网络传输的数据量更小。局部索引架构的缺点在于检索的开销较大，其每一个检索条件都会被发送到所有索引节点上去执行。

混合索引架构结合了全局索引架构与局部索引架构的优点，但高度的数据冗余造成了极大的数据膨胀，在大多数的应用当中这一点通常无法被用户接受；同时副本数量过多也导致数据的更新与增量难度更大。由于混合索引架构的明显缺陷，我们在后面的文章中将不再对其进行分析。

1 相关工作

分布式索引架构的研究从上世纪九十年代初开始，但早期有关分布式索引架构[1，2，5，7，9]的研究由于存在数据量较少、硬件环境限制、应用场景不同等问题，导致大家的研究结果有很大的分歧，对于当前海量数据背景下分布式索引架构研究的参考意义不大。Cambazoglu等在2006年通过实验结果[8]说明局部索引架构有较快的响应速度，而全局索引架构的吞吐率较好，这和我们的观点是一致的，但实验的结果是在较少的数据集上取得的（30GB），因此没有说明全局索引架构在响应时间上问题的严重性。

文献[3，4，7]等都是针对全局索引架构进行优化，他们或者考虑如何减少网络传输的数据量[3，6]，或者使用新的数据处理方式[4]，但都没有从根本上解决全局索引架构的时间延迟问题，而且用于实验的数据量都相对偏小，没有以海量数据为应用背景。

2 理论及分析

在介绍本文方法之前，先说明将用到的数据结构。倒排索引记录是Key-Value结构的，其中Key是检索关键字，Value是由数据项组成的有序集合。数据项的格式为（ID，score），其中ID表示某个检索对象的编号（例如文档编号），该检索对象中含有检索关键字Key，Value中的数据项都是依据ID排序的；score表示检索关键字Key在该检索对象中相关性的大小。实际应用之中检索关键字在一个检索对象中的相关性信息比较复杂，我们在模拟实验中简单的使用一个浮点型的非负数值score表示。

2.1 实现全局索引的关键步骤

在全局索引架构下对用户检索的处理步骤如下。

⑴ 用户提交检索条件，检索条件中含有一个或多个检索关键字Key，中间节点分析检索条件并将各个不同的检索关键字Key发到其相对应的索引节点；

⑵ 收到检索关键字Key的索引节点即在倒排索引中检索对应的倒排记录并将检索结果返回给中间节点，检索结果即是倒排记录中Value；

⑶ 中间节点会收到多个检索结果（Value），这些检索结果都是以ID排序的数据项集合，中间节点以ID对这些数据项集合求交集，交集中数据项的相关性值（score）是原来各个集合中有相同ID的数据项的相关性值（score）之和；

⑷ 检索对象返回给用户时一般需要分页，中间节点依据相关性值（score）的大小对交集中的数据项进行排序，相关性值（score）大的数据项对应的检索对象会先返回给用户，具体返回的检索对象需要依据数据项中的ID查找得到。

磁盘读取、网络传输等不是本文研究的重点。本文主要的关注点在于数据的处理过程，全局索引架构对数据的处理主要是在中间节点上完成的。假设：

A.在一个用户检索里面会有m个检索关键字（k1、k2…km）；

B.每个关键字ki所对应的Value是由ni个数据项组成的串，设；

C.最终的交集里面有R个数据项。

根据假设，可知中间节点上求交集过程的计算操作次数约为n。如果对交集依据相关性大小进行全排序的话，其时间复杂度为o（Rlog2R），但是一般情况下R较大，而用户可能只需要查看最相关的几个文档，这样我们既可以将相关性值（score）大的结果找出来并先返回给用户，而不需要对全部的结果集进行排序。具体操作上可以在求交集的过程中将相关性值（score）大于某个阈值的数据项存在一个桶里，求交集完成后只要先将桶里面的数据项依据其相关性值（score）的大小进行排序即可，桶里面的数据项数量是应用通过阈值控制的，一般远小于R。阈值一般由数据的规模和每次返回给用户的检索对象数量决定。

假设：

D.桶里面等待排序的数据项数量为R'。

则可以将全局索引架构中间节点的计算操作次数tgm表示为：tgm=m+n+R'log2R'。

关键字的个数m大多数情况下都是个位数，相比较而言可以忽略不计；在海量数据背景下，n的大小可能是几千万、几亿，而存在桶里等待排序的数据项的个数一般只有几百、几千，因而n要远大于R'log2R'，因此也可以简单地认为：tgm≈n。

2.2 实现局部索引的关键步骤

局部索引架构对用户检索的处理过程相比全局索引架构而言，在求交集等关键步骤上实现了并行化，其具体的处理过程如下。

⑴ 用户提交检索条件，中间节点将检索条件发到每一个索引节点上；

⑵ 局部索引架构索引节点所执行的操作与全局索引架构整个系统所执行的操作相同，包括检索条件的分析、检索关键字查询、检索结果求交集、根据相关性值（score）对交集排序等，只不过这些操作都是本地执行，最后索引节点将按相关性值排序后的检索结果返回给中间节点；

⑶ 中间节点接收各个索引节点的检索结果，这些检索结果都是以相关性值大小排序后的数据项集合，中间节点依据相关性值（score）的大小对这些数据项集合进行归并排序，同样，相关性值大的数据项对应的检索对象将优先返回给用户。

除使用2.1小节的假设条件外，这里再补充两个假设：

E.分布式信息检索系统中有N个索引节点；

F.每次返回给用户的结果集中数据项的个数为M。

这里需要说明的一点是，M的值并不是分页后一个页面所展示的检索对象的数量，一般而言M是一个页面所展示检索对象数量的倍数，比如10倍，用于应对用户可能的翻页，而且M小于R'。

局部索引架构索引节点所执行的操作与全局索引架构整个系统所执行的操作相同，参考2.1小节的分析，可以将局部索引架构索引节点的计算操作次数tli表示如下：

该表达式不一定准确，因为不可能每个索引节点在处理检索时的时间复杂度都是一样的，实际上由于局部索引架构中数据的划分是随机的，具有较好的负载均衡，虽然会有偏差，但是可以接受。

与全局索引架构一样，局部索引架构的索引节点也可以设置阈值，从而只需对桶里的R'个数据项进行排序，索引节点在给中间节点返回数据时，不必返回全部R'个数据项，只需返回前M个相关性值（score）较大的数据项即可。中间节点会收到N个数据项集合，每个集合M个元素，同样，中间节点也只需归并求出前M个相关性值（score）较大的数据项即可。

中间节点使用二路归并算法对N个数据项集合进行归并排序，因为多线程并行处理时二路归并是最优的。局部索引架构中间节点的计算操作次数tlm1可以表示如下：

tlm1的计算表达式是在线程并发度足够大的情况下取得的，实际的线程并发度是由中间节点CPU总的核心线程数目决定的，假设：

G.中间节点核心线程数目为L。

中间节点共需要运行N-1个线程，则更为精确计算操作次数tlm2可以表示如下：

在实际计算中，计算处理程序独占整个CPU是最优的情况，这种情况很难达到，所以tlm2的表达式中增加了一个系数eL和一个常数因子bL，并且有eL?1成立。具体eL和bL的值可以通过实验数据计算得到。

由于系统吞吐率、数据到达中间节点有先后等因素，可以考虑在中间节点上不使用多线程并行，而只是简单的串行执行即可，这样得到的中间节点计算操作次数tlm3可以表示如下：

tlm3=M*（N-1）

由于索引节点对检索的处理都是并行的，因此只需考虑单个索引节点即可，结合中间节点上计算操作的执行次数，则局部索引架构下整个计算过程的计算操作次数tltx可表示如下：

tltx=eltxtli+tlmx+bltx（x=1，2，3）

当tli=tlmx时，即中间节点与索引节点的计算操作次数相同时，但是由于二者计算过程的具体实现不同导致实际测得的计算时间是不同的，因此引入上述表达式中的平衡因子elt以及常数blt。平衡因子elt及常数blt可以结合实际的测量数据，利用线性回归模型求出来，在2.3小节有更为详细的分析。

分析比较全局索引架构与局部索引架构的计算操作，可以发现在海量数据背景条件下，局部索引架构明显优于全局索引架构。同时也应该看到，针对同一个检索，局部索引架构使用的索引节点更多，一般情况下局部索引架构相比全局索引架构在处理一个检索时的开销更大。

2.3 分析局部索引的簇的大小

将局部索引架构的计算操作次数tlt看成N的函数，即：

以执行时间复杂度最小值为目标，对于给定的n值（数据规模），可以求出最优的N值（机群规模），该结论对于在具体应用当中确定分布式机群的规模有参考价值。

对于平衡因子eltx（x=1，2，3）需要结合试验数据利用线性回归模型求解，这里先给出具体的回归模型。实验时取tlmx=tli（x=1，2，3），即局部索引架构索引节点与中间节点的计算操作次数相同，分别将二者的实际执行时间记为tlmx（x=1，2，3）和Tli，elmx是Tlmx与tlmx的相关系数（x=1，2，3），eli是Tli与tli的相关系数，bli和blmx（x=1，2，3）都是常数因子，则回归模型可表示如下（x=1，2，3）：

根据条件tlmx=tli（x=1，2，3），由上面的数学模型可得：

计算机的实际计算时间和算法时间复杂度的关系是线性的，所以文章中使用的是线性回归模型。

2.4 数据扩展和索引架构的选择

仅就计算的执行时间分析，可以看出在海量数据背景下（即n的值较大时），局部索引架构在计算执行时间上相对于全局索引架构有明显的优势；但当数据量较小时（即n的值较小时），这个优势并不明显；可以预见当n变小到一定程度时，全局索引架构与局部索引架构的执行时间数据就会相同，这时n的值对于根据数据规模的大小决定采用哪一种索引架构具有一定的参考价值；当n的值再变小时，局部索引架构的表现可能会比较差。

以上分析看似合情合理，但从另一个角度来考虑的话，就会发现问题并非如此。我们把局部索引架构索引节点的个数N考虑进来，那么关于执行时间Y的方程就有两个自变量（n与N）。由于局部索引架构索引节点的计算操作与全局索引架构中间节点的计算操作相同，取N为最优值，那么当数据规模变小（n的值变小）到一定的曾度时，N一定会变为1，那么此时因为只有一个索引节点，全局索引架构与局部索引架构就完全的相同了，因此计算的执行时间也必然相同。

通过上面的分析可以发现，在N取最优值的情况下，当全局索引架构与局部索引架构的执行时间相同时，局部索引架构就会退化为全局索引架构。

实际应用之中的情况可能会不同，计算执行时间的最优值并不是用户最为重要的目标，由于全局索引架构相对比较节省资源，所以在满足应用需求的情况下用户可能更愿意使用全局索引架构。

3 结束语

本文以海量数据为背景条件，研究了信息检索系统中分布式索引组织架构问题。通过分析说明了面对海量数据时分布式局部索引架构是信息检索系统的必然选择，分布式全局索引架构由于不可接受的时间延迟问题而被排除。本文对海量数据背景下分布式索引架构问题的研究成果不仅仅适用于一般信息检索系统，对于数据库的多条件联合查询、相似性搜索中的度量空间索引等也有一定的参考意义，虽然应用环境与具体的问题都不相同，但索引的分布式架构组织问题是相同的。未来的工作我们希望可以在完善的实验环境下将分布式索引架构的其他关键因素纳入考虑范围，例如磁盘读取、网络传输等。由于全局索引架构在检索成本上占有优势，我们下一步的工作还包括优化全局索引架构的处理模式，目标是通过优化满足用户的需求。本文所有的讨论与实验都是基于现有的软、硬件环境，相信在未来，随着计算机软、硬件技术的发展，我们解决这些问题将会更加的便利。

参考文献：

[1] RIBEIRO-NETO， B. AND BARBOSA， R. Query performance for tightly coupled distributed digital libraries.In Proceedings of the ACM Digital Libraries， Pittsburgh， PA， I. Witten， R. Akscyn， and F. M. S. III， Eds. 1998. ACM Press，182-190

[2] A. MacFarlane， J. McCann， and S. Robertson. Parallel search using partitioned inverted files. In Proceedings of the 7th International Symposium on String Processing and Information Retrieval， pages 209-220， La Coruna， Spain， September 2000. IEEE Computer Society.

[3] Zhang J， Suel T. Optimized inverted list assignment in distributed search engine architectures[C]. Parallel and Distributed Processing Symposium， 2007. IPDPS 2007. IEEE International. IEEE，2007：1-10

[4] Moffat A， Webber W， Zobel J， et al. A pipelined architecture for distributed text query evaluation[J]. Information Retrieval，2007.10（3）：205-231

[5] Badue C， Baeza-Yates R， Ribeiro-Neto B， et al. Distributed query processing using partitioned inverted files[C]. Proc. SPIRE，2001：10-20

[6] Kayaaslan E， Aykanat C. Efficient query processing on term-based-partitioned inverted indexes[R]. Technical Report BU-CE-1102， Bilkent University， Computer Engineering Department， 2011. Also available at： http：//www. cs. bilkent. edu. tr/tech-reports，2011.

[7] Xi W， Sornil O， Luo M， et al. Hybrid partition inverted files：Experimental validation[M]. Research and Advanced Technology for Digital Libraries. Springer Berlin Heidelberg，2002：422-431

[8] Cambazoglu B B， Catal A， Aykanat C. Effect of inverted index partitioning schemes on performance of query processing in parallel text retrieval systems[M] Computer and Information Sciences-ISCIS 2006. Springer Berlin Heidelberg，2006：717-725

[9] Tomasic A， Garcia-Molina H. Performance of inverted indices in shared-nothing distributed text document information retrieval systems[C].Parallel and Distributed Information Systems， 1993. Proceedings of the Second International Conference on. IEEE，1993：8-17