大规模分布式并行信息检索技术 1 引言引言 随着计算机的普及和网络的日益发展，数字化信息爆炸式增长。以 WEB 为例，据可靠 估计，WEB 的增长速度可以达到每 6 个月翻一番1。到 2004 年年底，最大的搜索引擎可 以索引到的 WEB 网页的数目大概为 80 亿100 亿左右。而这个数字只占到整个 WEB 网页 数目的很小一部分。 搜索引擎能够搜索到的大部分网页都称为表层页面(surface WEB)。 据研 究，WEB 中的深层页面(也称为 deep WEB，如：需要权限才能进入的网页、对网络数据库 的查询和调用的返回页面、网络上的图像、音频、视频等多媒体文档和各种格式的文档、软 件等等)的大小大概是可见 WEB 页面大小的 400 到 500 倍2。另外，很多大公司的内部 Intranet 甚至个人都拥有大量的电子文档。所有这些数字都说明，WEB 上的数字化信息实在 是大得惊人。一方面，这些地理位置分散的异构数字化信息中包含了大量宝贵的资源，用户 迫切地需要从这些信息中找到所需信息；另一方面，虽然单台计算机的处理能力不断提高， 但是在如此大规模的条件下， 要对这样海量的信息进行检索， 单台计算机的处理能力毕竟有 限，特别需要多台计算机进行“团队作战” 。而并行计算和分布式计算能够利用多台计算机 或者多个处理器的计算或存储资源来解决大规模问题。 因此， 很自然地会想到将并行处理或 者分布式处理技术引入到信息检索当中，产生了分布式并行信息检索技术。 本文的组织如下：第二节介绍并行计算、并行检索的基本概念、原理、方法和相关的进 展；第三节介绍分布式计算、分布式检索的基本概念、原理、方法和相关进展；第四章介绍 了计算所在该领域所做的部分工作；最后是对将来的展望。 2 并行检索并行检索 2.1 并行计算 2.1 并行计算 并行计算指的是，将单个问题划分为多个较小的“子”问题，用多个处理器同时分别处 理这些 “子” 问题来得到单个问题的解。 显然， 由于并行计算能够同时利用多个处理器资源， 所以通常能够减少问题求解的总时间， 从而解决大规模的问题。 多个可以同时工作的处理部 件或处理器构成的计算机系统， 称为并行计算机。 并行计算系统包括并行计算机或多处理机 系统。在并行计算系统中，不同处理器同时运行多个程序或者一个程序的不同进程，从而提 高系统的运算速度。 根据指令和数据流的数目不同， 并行计算的体系结构通常可以分成SISD、 SIMD、 MISD、 MIMD1等四种类型。 其中MIMD是现在最通用和使用最广泛的一种类型。 后面提到的并行检 索也主要基于这种体系结构。MIMD的体系结构如下图所示： 1 S=Single, I=Instruction, D=Data, M=Multiple 内存 处理器 内存 处理器 图 1 MIMD 体系结构示意图 图中，MIMD 并行体系结构主要由多个具有自己的控制单元、处理单元和局部内存的 多个处理器组成，多个处理器之间通过共享内存或者通信网络相连接(图中以粗黑线表示)。 MIMD 可以处理互相独立的多个任务或者协同执行同一个任务。MIMD 体系结构中，如果 处理器之间交互通讯频繁，则称为紧耦合(tightly coupled)系统；反之，则称为松耦合(loosely coupled)系统。 2.2 并行检索 2.2 并行检索 要实现并行检索，首先让我们考察信息检索的一般过程： 查询 搜索程序 代理 结果结果 查询图 2 信息检索的一般过程如图 2 所示，用户提交一条查询，代理程序(broker)对原始查询进行处理(如查询的分析 转换或格式化处理等等)，然后将处理后的查询发给搜索程序，搜索程序找到结果并进行处 理(如排序)后返回给代理，代理经过必要的处理(如结果的归整、合并等)将结果返回给用户。 从以上可以看出，信息检索有并行处理的潜力可以充分挖掘。根据对象的不同，并行检 索总体上可通过以下两种方式实现并行： 1. 多条查询多条查询之之间的并行间的并行处处理理。 一个最自然的想法就是利用 MIMD 结构对多条查询的处理并行化，即每个处理器 处理不同的查询， 每个查询的处理之间相互独立， 最多只对共享内存内的部分代码或者 公有数据实行共享。 这种方法也称为任务级的并行检索。 它可以同时处理多个查询请求，从而提高检索的吞吐量。 图 3 显示了 3 条不同查询在 3 个处理器上的并行处理过程。 每 条查询通过代理(也可同时运行多个代理程序，每个代理分别处理一条查询)发送到不同 搜索程序(每个处理器上运行一个搜索程序)上去执行，每个搜索程序的结果通过代理返 回到不同查询的发起者。 结果 3结果 2结果 1查询 3查询 1查询 2代理搜索程序 3 搜索程序 2 搜索程序 1 查询 结果 图 3 查询间的并行处理过程 如果MIMD由多台具有自身处理器和磁盘的计算机组成， 每台机器执行自己的搜索 程序，并且只访问本地的磁盘，则没有硬件资源访问冲突问题2。但如果多个搜索程序 访问的是相同的磁盘资源， 则可能存在磁盘存取冲突问题。 这时可以通过增加磁盘或采 用类似Raid磁盘阵列的方法来减少冲突，但同时不免加大硬件设备的开销。另外一些可 能的方法包括复制访问频繁的数据到不同磁盘以降低访问冲突、 将数据分割到多个磁盘 等等。 查询间并行化策略是从一般检索升级到并行检索的最简单方法。 简单地说， 就是将 检索系统复制多份(数据可以复制也可以不复制)， 每份分别处理不同的查询请求。 当然， 这种升级硬件资源消耗比较高。 而且， 简单地堆积硬件资源并不一定就可以提高信息检 索的效率，必须考虑硬件资源的访问冲突，设计合理的软件结构和访问策略，才能提高 信息检索的总体性能。 2. 单条查询内部的并行处理。单条查询内部的并行处理。 即对单条查询的计算量进行分割， 分成多个子任务， 并分配到多个处理器上的搜索 进程上去执行。 这种检索也称为进程级并行检索进程级并行检索。 将单条查询分成多个子任务的方法通 常有两种：一种称为数据集分割数据集分割，它是事先将数据集分割成多个子集合，对同一条查询 分别查询多个子集合数据， 然后将每个子集合上的结果合并成最终结果； 另一种称为查 询项分割查 询项分割，它是将查询分解成多个子查询(如将一个多关键词查询分成多个单关键词查 询)，对每个子查询分别查询数据集，得到部分结果，并将部分结果合并成最终结果。 图 4 给出了一个单条查询内部并行处理的示意图： 查询发送给代理程序， 代理程序将一2这是一种简化情形，如果每台计算机有多个处理器分别处理不同查询、或多个处理器处理同一条查询、或者一个处理器同时处理多条查询时，仍然有硬盘访问冲突问题。 条查询划分成多条子查询， 每条子查询分别发送给一个搜索进程进行处理， 各进程返回 的子结果在代理上进行综合，得到最后的总结果返回给用户。 子结果3子结果2子结果1子查询3子查询1子查询2代理 搜索程序 3 搜索程序 2 搜索程序 1 查询 结果 图 4 查询内部的并行处理过程 在进行查询之间的并行时， 信息检索系统中的数据结构通常不需要改变。 而对于单条查 询内部的并行处理， 则需要对原有串行信息检索的数据结构做相应的改变。 在信息检索系统 中通常采用一种称为“倒排表”(inverted file)的索引结构，可以直接从关键词映射到所在文 档。一个典型的倒排表部分结构如下图所示： 文档 4文档 4文档 4文档 3文档 3文档 3文档 2文档 2文档 2文档 1文档 1文档 1文档 1文档 1项表 大规模 文档表 图 5 倒排表结构示意图 技 术 检 索 并 行 分布式 在图 5 中，左边的多个查询项组成项表；每个项指针链出的是其所在文档的相关信息； 每个项所在的所有文档信息称为这个项对应的文档表。 以图 5 为例， 数据集分割就是将不同 的文档分配给不同处理器进行处理(如文档 1 和文档 2 分配给 1 号处理器，文档 3 和文档 4 分配给 2 号处理器)，而查询项分割是将不同的关键词分配给不同的处理器进行处理(如：关 键词“大规模”和“分布式”分配给 1 号处理器，关键词“并行” 、 “检索”和“技术”分配给 2 号处理器来处理)。 并行检索策略采用数据集合分割和查询项分割时， 采用倒排表索引结构的检索系统需要 在原始倒排表基础上做多种转换。下面分别进行介绍。 使用倒排表进行数据集分割数据集分割有两种实现方法： 物理倒排表分割物理倒排表分割方法和逻辑倒排表逻辑倒排表分割方 法。这两者的数据集都在物理上分成多个子集合。仍以图 5 为例，假设系统有 2 个处理机， 则可以将所有文档划分成 2 个子集合(如：将文档 1 和文档 2 划入一个子集合，而文档 3 和 文档 4 划入另一个子集合)。当输入一个查询 “并行 AND 检索” ，系统的 2 个处理机将分 别在 2 个子集合中寻找匹配结果。 物理倒排表分割和逻辑倒排表分割的不同之处在于， 前者不仅将数据集分割， 而且将倒 排索引表也同时进行分割， 每个数据子集拥有自己独立的索引倒排结构。 对于逻辑倒排表分 割，倒排索引表并不物理上进行分割，而是增加一个处理机分配表，整张倒排索引表则被多 个处理器共享使用。 物理倒排表分割后， 每个子集合具有自己独立的倒排表结构， 因此可以供不同的处理器 单独调用，相对比较灵活。但是，由于独立的倒排表没有全局的统计信息(在进行检索时通 常需要全局的统计信息来计算文档和查询的匹配相似度)，所以对每个子集进行检索时必须 要有另外的处理来获得全局信息。方法通常有两种：一种是采用复制的方法，即将全局信息 复制多份分配到每个独立的索引倒排表上去； 另一种是在每个子集合检索时分两步走， 第一 步获取全局信息表，第二步才进行检索。前一种方法比较耗费空间，对索引表的更新也比较 复杂；后一种方法需要较大的通讯开销。总的来说，逻辑倒排表分割方法的通讯开销很小， 因此总体性能会高于物理倒排表分割， 但是必须要对普通倒排表增加额外的数据结构来进行 转换。 而物理分割方法的灵活性比较强， 每个文档子集可以单独检索。 通过物理分割的方法， 很容易将非并行的信息检索系统转换为并行的检索系统。 使用倒排表进行查询项分割方法时， 要将每个关键词项分配到不同处理器上去。 对于倒 排表来说， 就是将关键词项表进行分割(逻辑的或者物理的)， 分别对应到不同的处理器上去。 在进行查询时， 查询项将被分解成多个关键词查询， 每个关键词对应不同的处理器分别进行 处理。处理结果按照查询的语义进行合并。例如，如果是多个关键词布尔表达式查询(如： 查询： “并行”AND “检索”)，则合并的主要工作是进行布尔操作。如果是需要对多个子 结果进行排序，则合并的主要工作是评分归一化并排序。 相对而言，数据集分割方法能够提供更简单的倒排表构建和维护。Jeong 和 Omiecinski 通过实验对这两种方法进行了比较3： 假设每个处理器有自己的 I/O 通道和磁盘， 当关键词 出现在文档和查询中的分布呈偏态分布(skewed)时，采用数据集分割的方法性能较好；而当 关键词在查询中呈均匀(uniform)分布时，查询项分割方法更优越。 除了倒排表以外，信息检索中常用的其他数据结构(如签名文件 signature file、后缀队列 suffix array 等)在应用到并行检索时也需要进行改变。 另外， 当检索系统使用其他并行结构(如 SIMD)时，也需要对数据结构做相应改变。篇幅关系，本文不再叙述，有兴趣的读者可以参 考文献1。 3 分布式检索分布式检索 3.1 分布式计算 3.1 分布式计算 分布式计算可以把地理位置上分布更广的异构文档整合成一个更大的逻辑整体。 分布计算是利用网络连接的多台计算机去求解一个问题。 从广义上说， 分布式计算可以看成 MIMD 并行计算的一个特例。不过所不同的是，分布式计算中的通讯开销比较大，因此最多只能算 是一个松耦合的并行计算系统。另外，它能够