🔒 This is a Hidden Post If you have landed here, wow!

This may also be a draft, share feedback, reachout to me!

ABSTRACT

在Web搜索引擎中处理查询需要有效地使用硬件资源来应对用户流量的规模和动态。本文重点讨论了多线程处理查询，这些查询需要访问大型反向索引数据结构以获取一组文档，通过执行WAND运算符对它们进行排名，以获得前K个最相关的文档。以及在执行查询的同时解决在反向索引上插入新文档的问题。 我们提出了一种高效的策略来为查询和索引更新操作分配线程，这种策略适合于在查询处理的同时支持索引的更新。 我们提案的核心是一种简单的分类技术，旨在快速为查询操作分配线程。

Introduction

Web搜索引擎中最耗时的任务是对用户查询的大量潜在答案的排名。其成本与在支持搜索引擎服务的处理器的分布式存储器集群中保持索引和压缩的Web样本的（通常是巨大的）大小成比例。每个处理器都保存一小部分Web样本，该样本在称为倒置文件或索引的数据结构中索引。基本上，反向文件由词汇表组成，该词汇表包含Web示例中找到的所有相关术语，并且对于每个术语，存在包含该术语的Web文档的列表以及诸如术语文档内频率的额外数据。该索引可以快速检索包含所有查询项的文档以及计算这些文档的分数所需的额外数据。分数越高，文档对于给定查询越相关。然后通过选择具有最高分数的K个文档来产生查询的答案。有几种方法可以为Okapi BM25 等文档分配分数。

WAND运算符通过将与文档评分（例如，BM25）相关联的昂贵计算限制为仅几个文档，同时跳过没有机会进入前K个的文档，使得能够有效地执行文档排序过程。这使得文档评分成为一个进程，其运行时间成本是不可预测的，并且在查询中变化很大。不可能假设其成本与所涉及的文档列表的长度成比例。因此，在运行时以及在很短的几分之一秒内确定分配给WAND操作的线程数变成了一个非常重要的问题，因为总执行成本仅在查询完全已知时才知道在处理器中解决了。

多线程查询处理的实用方法是让每个活动查询由单个线程顺序处理。由于Web搜索引擎始终包含大量活动查询，因此在不需要支持倒置文件中的并发更新时，这种方法在实践中非常有效。但是，当需要支持在倒置文件中插入新文档时，这种方法效率不高。在这种情况下，必须修改许多文档列表，并且由于人们倾向于在文档和查询中使用一组非常流行的术语，因为在处理查询和线程更新文档列表的线程之间的冲突读写操作可能会降低性能。

[4]中提出的解决方案允许所有线程一次参与一个查询或索引更新的并行处理。由于传入的查询/更新请求是按顺序处理的，因此不会发生读取和写入冲突。当文档包含足够大的术语时，此策略是合适的，并且可以有效地使用所有线程来解析每个查询。但是，在许多情况下，WAND需要一些线程来使用处理器中可用的所有线程所需的时间大约相同（甚至更短）。因此，这种方法不能扩展WAND查询，并且通常，它不能扩展到支持高效执行大量线程的处理器。

请注意，在生产搜索引擎中，我们应该期望在索引更新之间使用可变大小的用户查询序列来处理工作负载。我们研究了几种利用这一事实的方法。例如，除了使用每个查询/更新操作的单个线程和锁定以防止读/写冲突的简单但效率低的策略之外，我们可以累积足够的更新操作以在索引更新期间保持所有线程忙，并快速处理批处理通过将一个或多个线程正确分配给单个查询来使查询保持繁忙，以便尽快使用每个批处理。在这种情况下，特别是对于小批量，每个查询分配一个线程不是一个好主意，因为查询解决方案时间的差异可能非常高，从而产生空闲线程，并且在许多情况下，顺序查询解决方案时间可能超过预先定义的时间作为设计要求对搜索引擎施加的查询响应时间的上限。

在本文中，我们提出了一个有效解决WAND查询批处理问题的解决方案，每个WAND查询都有适当数量的线程来快速解决它们并避免在每个批处理结束时空闲线程。我们的解决方案基于工作单元中的查询分解，这些查询放在队列中，线程从这些队列中完成下一个工作。为了完成查询分解，我们提出了一种新的分类方案，该方案非常快速并且达到了合理的精度。根据该方案，我们提出了一种更新倒排文件的策略，该策略将处理并发查询/更新操作的整个任务转换为比以前的方法更有效的方法。

本文的结构如下。第2节介绍相关工作。第3节描述了我们用于查询和文档插入的线程分配技术，以及我们的分类技术。第4节介绍绩效评估研究，第5部分介绍结论。

Related work

现代搜索引擎使用倒排索引来加速文档搜索过程。倒排索引是一种简单的结构，它存储文档数据，允许快速查找和排列包含某些查询术语的集合的文档[10]。在倒排索引中，我们存储表示单个术语的倒排列表以及包含该特定术语的所有文档。文档由数字文档标识符（docID）表示，并且通常还存储每个特定文档中术语的频率（特定术语的该文档中出现的次数）。还可以存储附加信息，例如每个文档中术语的各个位置。还有许多压缩技术[9,3,2]用于以高效的方式存储倒排索引，这其中的许多压缩技术存储越来越多的docID，以便只有delta（docID和前一个之间的差异）存储。

确定可在docID有序索引中使用的前K个（top-K）文档的一种有效方法是WAND [5]。WAND算法将查询术语列表按每个查询术语的当前docID排序。该方法使用每个文档的分数的上限通过列表前进，并丢弃其分数不大于当前top-K文档中的最不相关候选者的那些，其得分是查询的当前阈值。因此，该算法仅计算那些不能被丢弃的候选者的完整分数，减少了为每个查询执行的计算总量。通过跳过整个发布列表块[6]和并行化[8]的处理来改进这种技术。

WAND使用基于文档的两级评估的排名。在第一级，它使用每个文档的分数的上限来尝试丢弃尽可能多的文档。在第二级，它计算通过第一级测试的文档的真实分数。为了使这个过程高效，它使用堆数据结构来存储到目前为止找到的最好的top-K文档。堆中排名最低的文档的分数被用作第一级评估的阈值，以丢弃不能作为最终前K文档的一部分的文档。这样可以实现高效的丢弃过程，确保在此过程中不会丢失相关文档。这意味着实现多线程WAND的两种方法。其中一个是使用本地堆（LH），每个线程一个，另一个是使用共享堆（SH）。在LH方案中，每个线程处理索引的一部分，同时保持本地堆与当前特定线程找到的当前top-K文档。在该过程结束时，每个线程的结果必须合并到一个结果集中。在SH方案中，每个线程处理索引的一部分并将文档存储在共享堆中。

在共享堆方案中，不需要合并，并且丢弃过程往往更有效（因为具有更高分数的文档往往在堆上）。但是，必须通过原始锁(lock primitive,就这么翻译了)来控制对堆的访问。我们在第4节中描述的实验设置下进行了测试以比较两种方法的平均时间和效率，我们发现SH WAND通常对多线程WAND更有效[8]，见图1。所以我们选择了共享堆WAND在我们的实验中使用。

PROPOSAL

Threads Management

我们将倒排索引分区以通过为单个查询分配多个线程来执行多线程查询处理。为实现这一目标，我们将每个术语的列表划分为多个独立列表。分区数等于处理器中允许的最大线程数。要解析具有一定数量线程的查询，我们在参与线程之间分配不同的部分。但是，如果我们启动将解析单个查询的线程并等待它们在为其分配处理其他查询之前结束其工作，则会有空闲线程等待参与线程完成其工作，如图2所示。

相反，我们建议通过在我们称之为工作单元的分解查询处理来增加维持所有线程忙于执行有用工作的机会，如图3所示。为此，我们将查询划分为多个独立单元，这些单元等于分配的线程数，并将这些单元存储在共享队列中。一旦线程完成其当前的工作单元，它就会从队列中获取下一个工作单元。对队列的访问由简单的锁定机制控制。这是可以接受的，因为我们感兴趣的是优化系统的查询吞吐量（每单位时间的查询），前提是单个查询响应时间不大于给定的边界。

用于确定任何到达查询的工作单元数的分类方案是使我们的方案正常工作的关键参与者，因为查询处理时间可以显着地相互影响。在我们的方案中，可以使用大量线程来解决要求严格的查询以减少其处理时间，而需要很少工作的查询可以被调度为共享队列中的单个单元。问题是事先不知道查询的实际工作量。我们的分类方案设计用于预测运行时任何查询的不同线程数所需的工作量。它必须是在很短的时间内提供合理预测的快速方法。

A Simple and Fast Classification Technique

我们提出了一种简单的策略来确定分配给每个查询的正确线程数。与更复杂和精确的方法相比，该方法在查询时非常有效并产生了良好的结果（比较研究见第4节）。我们的分类方法背后的概念是，没有必要花费大量资源来预测查询运行时间，以估计查询的适当线程数。预测的目标实际上并不是知道真实的查询时间，而只是知道适当数量的线程。

请注意，当使用太多线程来处理给定查询时，会出现显著的开销，特别是考虑到多线程WAND的平均效率对于大量线程而言往往较低（我们定义效率为最大线程工作除以平均线程工作）。通常，由于需要少量计算，因此可以处理大量快查询，因此无需使用多个线程来解决它们。此外，由于需要解析大量计算，因此处理的慢查询数量相对较少。查询分类的目标是识别慢查询以分配更多资源来解决它们。

实现此识别的一种方法是使用机器学习技术来预测处理查询的成本。这可能涉及使用预测技术，范围从简单的线性模型到使用大量特征进行更精确预测的模型，甚至使用人工神经网络和其他复杂的机器学习技术。然而，这将需要预测每个不同数量的线程的查询时间，这可能导致需要为每个案例训练模型并且在查询到达时间对每个模型执行预测计算。然后，在查询时有效使用处理器线程的低成本启发式方法是为查询选择最小的线程数，以确保整个查询响应时间的上限。

但是，对于慢查询，它必须至少引用与查询术语相关联的大型发布列表所代表的许多文档。即使其他方面影响查询成本，例如每个文档发布列表上的术语频率分布，以及查询术语之间的关系，但是查询引用许多文档是必要条件。考虑到这一事实，在我们的方法中，我们只使用查询项的数量和各个发布列表的长度总和来执行设置要分配给查询的线程数所需的分类。

我们的技术首先确定查询中的术语数量，因为它是影响查询时间的重要因素。例如，在我们的实验数据（第4节）的示例中，我们发现，当使用一个线程顺序处理时，只有4.8％的具有2个术语的查询花费超过160毫秒，而具有5个术语的35％的查询需要类似时间。这部分是因为具有更多术语的查询往往需要审阅更多文档，但是由于他们使用包含所评估文档的所有相关术语的数据，因此计算得分的成本也更高。

在每种情况下，我们独立地计算查询项列表长度的总和，并使用它们来确定应该分配给查询的线程数。这是通过使用之前在训练阶段确定的截止值（或阈值）来实现的。计算截止值，以便它们倾向于分配足够的线程，以确保查询花费的时间小于上限。这个界限可以定义为训练数据集中查询的平均连续运行时间的一到两倍之间的值。这种方法比上面描述的方法更不灵活，它包括测试几个线程，直到达到不超过上限的最小数量为止。在我们的案例中，在训练时确定了界限及其各自的界限值。但是，我们的方法比其他方法快了几个数量级，只给实际查询执行时间增加了几纳秒。

为了确定适当的截止值，我们使用训练查询的样本，并计算每个线程数的实际执行时间。为了简单起见，我们只使用2的幂作为分配给查询的潜在线程数。因此，例如，对于一个高效地支持16个线程执行的处理器，我们有5类查询，根据1、2、4、8或16个线程是否实现了确保查询时间小于上限的最小线程数。

在准备阶段，我们根据术语的数量分离训练查询，并且在每种情况下，我们独立地按列表的长度总和对它们进行排序。因此，我们获得了一组对（文档总数，线程数ID）按文档总和排序，并且类ID等于所用线程数。对于此集合中文档总和的4个cuto ff值，我们可以将查询分为5个类，用于前一个支持16个线程的处理器示例。这可以扩展到任意数量的处理器线程（类），因为这些总和在实际Web样本中往往是非常大的值。

为了确定cuto ff值，我们执行搜索过程以找到最大的F-Score的值。对于增加cuto ff值的任意初始化来定义每个类的限制，我们通过根据正确分类的查询数量计算True Positive案例，False Positive案例和False Negative案例来确定所选择的cuto ff值集合的好坏程度。每节课。如前所述，当相关联的线程数是产生低于上限的查询执行时间的最小线程数时，认为查询被正确分类。通过这些计数，我们计算精度（真阳性除以真阳性和假阳性的总和）和召回（真阳性除以真阳性和假阴性的总和）。通过这种方式，平均F-Score被定义为Precision和Recall指标的调和平均值，因此我们只需寻找最大化类集平均F-Score的cuto ff值。

网络搜索引擎用户倾向于使用极少数条款提交查询。我们通过定义由1,2,3,4,5和5个以上术语的查询组成的训练集来利用这一事实。对于每组，我们用上述方法获得cuto ff值的矢量。然后在查询运行时选择右侧集。

Dynamic Indexing

我们研究的重点是优化处理节点的性能，该处理节点使用多个线程解析查询，并且还在主存中保持倒排索引更新。该节点必须允许向Web文档索引集中添加新文档。在标准实践中，我们假设docID是增加的整数，其中索引列表通过增加docID来保持排序，以实现其高效压缩[2]。

在我们的实验中，我们省略了文档删除的情况，因为压缩索引列表的实现面临的困难超出了本文范围。 一种粗略但实用的方法是定期重建受影响的索引列表，并跟踪无效的docID，以便在查询的文档排名过程中省略它们。

WAND同时处理查询中涉及的所有索引列表。 因此，在解决查询之前必须锁定所有这些索引列表。以相同的方式，如果正在修改查询中涉及的任何索引列表，则必须等待修改完成以继续处理查询。有几种方法可以处理潜在的读/写冲突。在下文中，我们描述了我们在应用领域中发现的最有效的策略。注意，通过使用数据库和操作系统文献中提出的并发控制策略（例如，读和写锁）来同时处理查询和索引更新的方法已经在[4]中进行了测试。

我们设计了三种策略来解决新文档的插入问题，并根据不同的文档到达率评估它们的性能。我们称之为直接插入的第一种方法是安排将每个新文档作为工作单元插入队列中。任何空闲线程都可以使用此工作单元并在涉及的索引列表上执行插入过程。通过迭代新文档的每个术语，请求对要修改的列表的独占访问锁定，并在释放锁定并移动到下一个索引列表之前插入具有相应术语频率的新文档docID来解决插入。

第二种方法，我们称之为批量插入，首先收集一定数量的新文档，然后构建临时子倒排索引。 在这种情况下，主索引中的插入过程比直接插入中的插入过程更有效，因为在新文档中出现多次的术语将具有在子倒排索引中具有多个文档的索引列表。 然后，将子索引插入类型工作单元插入队列中。 因此，当空闲线程占用该工作单元时，它仍然在插入所涉及的每个索引列表的文档，而其他线程继续同时解决查询。

第三种方法类似于第二种方法，在临时子索引中为其组织收集了一定数量的文档，但是不是生成单个工作单元，而是将子索引术语加上它们各自的索引列表分布到多个工作单元中，这样所有线程都可以并行处理插入。 我们称这种方法为分布式批量插入(Distributed Batch Insertion)，它有望改进以前的方案，因为它可以消除来自查询和索引列表更新的独占访问锁之间的冲突。当所有线程在处理当前批次查询的同时完成所有线程时，实际上消除了冲突。

在第二种和第三种情况下，插入过程比第一种情况要快得多，因为涉及的发布列表保持锁定在主索引中。 这是因为大部分处理时间都花费在构建子倒排索引上，因此一旦子发布列表准备插入，它们在相应主索引发布列表末尾的位置就会非常快速地执行，因为它需要的计算量要少得多。

EXPERIMENTAL EVALUATION

我们使用来自TREC GOV2 Collection的2500万个文档中的16个线程来评估解决WAND查询的不同方法，并在每个实验中解决50,000个查询。 我们构建了一个倒排索引，其发布列表分为16个部分，可以在查询时分配给线程。使用Simple 9 [1]作为代表性技术压缩索引，压缩比和解压缩速度之间具有良好的平衡。 所有实验均使用两个四核英特尔（R）Xeon（R）CPU E5620 @ 2.40GHz处理器和96GB RAM进行。 我们使用C ++实现了这些技术，并使用优化选项-O3使用g ++ 4.4.5编译了代码。

在实验中，我们使用主内存中的完整索引执行固定数量的查询（50,000）。在查询解决的同时，在索引中插入可变数量的文档，从50到50,000个文档。我们评估了处理文档插入（直接插入，批量插入和分布式批量插入）的三种技术的性能，并结合4种技术来确定每个查询使用的单位数。我们使用（a）每个查询1个单元（即用一个线程顺序解决每个查询），（b）完美估计器，其中查询时间事先已知，并且之前已用于确定满足条件的最小线程数查询响应时间的上限，（c）WAND查询[7]中提出的多变量线性估计器，它估计我们使用它的顺序查询时间，如完全估计器的情况，以及（d）我们的简单分类器方法训练使用一组与实验中使用的查询不同的查询。

在每种情况下，我们都测量了系统解决所有查询和插入所有文档所需的总时间。 图4,5,6和7显示了每种技术解决插入所花费的总时间，并结合了为查询分配单元的每种方法。图8显示了分布式批量插入的每个单元分配技术的总时间，因为它可以获得最佳结果。这个图省略了每个查询1个单元的情况，因为它没有达到良好的性能。结果表明，通过Simple Classifier结合Distributed Batch Insertion进行多线程处理是最佳选择。

搜索引擎的设计要求是实现高吞吐量，其在先前的图中由完成该组操作所需的总时间表示。 另一个相关的设计要求是各个响应时间低于给定上限时间的查询的百分比。 在下文中，我们评估查询的90Percentile和99-Percentile时间限制值。 也就是说，我们显示最小时间限制值，以确保在比相应绑定值更短的时间内完全处理90％和99％的查询。

如图9和10所示，通过使用每个查询1个单元的方法实现的查询时间限制值远远高于使用替代工作单元分配技术观察到的值。这进一步证明，这种方法虽然易于实施，但并不像其他替代方案那样有效，因此我们将其丢弃。

图11至图16显示简单分类器策略在99-百分位查询约束时间内具有竞争性，其中简单分类器和多线性估计技术之间的差异相当小。然而，当考虑如图8所示的总执行时间时，简单分类器优于多线性估计器，因为它引入查询处理的累积开销要低得多。

CONCLUSIONS

本文重点讨论了在Web搜索引擎的倒排索引中执行更新的同时处理多线程查询的问题。我们已经提出了一种有效的策略来动态地分配线程，以根据它们的特定特征处理各个查询。我们将查询处理分解为多个工作单元，这些工作单元可以由多个线程并行处理。我们设计了一种简单的分类方法来确定每个查询的工作单元数，这种方法足够精确且比其他查询时间估计策略快得多。根据该方案，我们建议在执行实际索引更新并在所有线程之间分发整个插入任务之前，在子索引中预处理文档。总的来说，提出的方法是以两步方式进行，其中（1）通过在查询级别应用并行性使用所有线程处理一批待处理查询，随后（2）处理一组待处理发布列表更新。批量使用并行的所有线程。实验表明，这两步策略对搜索引擎查询吞吐量有积极影响，并确保查询时间的竞争上限。

REFERENCE

[1] V. N. Anh and A. Moffat. Inverted index compression using word-aligned binary codes. Inf. Retr., 8(1):151–166, 2005.

[2] D. Arroyuelo, S. Gonz´alez, M. Oyarzu´n, and V. Sepulveda. Document identifier reassignment and run-length-compressed inverted indexes for improved search performance. In SIGIR, pages 173–182, 2013.

[3] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval: The Concepts and Technology behind Search (ACM Press Books). Addison-Wesley Professional, 2011.

[4] C. Bonacic, C. Garc´ıa, M. Marin, M. Prieto-Matias, and F. Tirado. Building efficient multi-threaded search nodes. In CIKM, pages 1249–1258, 2010.

[5] A. Z. Broder, D. Carmel, M. Herscovici, A. Soffer, and J. Zien. Efficient query evaluation using a two-level retrieval process. In CIKM, pages 426–434, 2003.

[6] S. Ding and T. Suel. Faster top-k document retrieval using block-max indexes. In SIGIR, pages 993–1002, 2011.

[7] C. Macdonald, N. Tonellotto, and I. Ounis. Learning to predict response times for online query scheduling. In SIGIR, pages 621–630, 2012.

[8] O. Rojas, V. Gil-Costa, and M. Marin. Efficient parallel block-max wand algorithm. In Euro-Par, pages 394–405. 2013.

[9] H. Yan, S. Ding, and T. Suel. Inverted index compression and query processing with optimized document ordering. In WWW, pages 401–410, 2009.

[10] J. Zobel and A. Moffat. Inverted files for text search engines. ACM Comput. Surv., 38(2), July 2006.