大规模网络搜索的设计

大规模搜索引擎的逻辑结构

上图来自1998年Google两个创始人发表的论文。

1. crawler：爬虫，从互联网上获取文档信息
2. index：读取这些信息，并记住哪些单词出现在哪些文档中，称为索引
3. search：使关键词查询成为可能，并对查询结果进行排序
4. Google的独特性在于：使用anchor text描述目标文档，并利用文档之间的链接对文档的重要性排序，这就是PageRank。

Google搜索的主要数据结构

• 将大文件设计为虚拟文件

• 每个页面有三个描述维度：

  1. sync同步码：一个页面数据长度的开始
  2. length：页面字节长度
  3. compressed packet：压缩包，包括docid(文档id)、ecode(编码信息)、url长度、页面长度和页面

索引

1. 根据docid排序
2. 根据URL排序
3. lexicon：词典，是一个查找表。保存在内存中，保存单词以及由指针组成的哈希表。

• 正向索引，如你们所知，barrels会记录文档ID（docID）、单词ID（wordID）和文档中的每个词出现了多少次。在索引末尾，会有所有出现和所有命中。
• 倒排索引，包含与正向索引相似的信息。但是，倒排索引中的信息排列方式不同于正向索引中，倒排索引中的信息是根据单词排序的。因此，如你们所知，单词ID之后跟随着有多少文档中包含了这个单词。然后一些指向这些文档的指针。对于每个文档，倒排索引都会记录在这个文档中命中了多少次。在索引末尾还有命中的列表。

命中

关键字出现在一个页面中称为“Hit(命中)”。Google的Hit存储了命中的类型和位置。
命中分为特殊命中和普通命中。特殊命中是指关键词在标题、URL、元数据和锚文本中命中。

爬虫

网络爬取信息是一个复杂的工作，需要用到分布式爬取、DNS缓存等提高爬取效率。

搜索

一个搜索请求的处理步骤：

1. 查询请求解析
2. 将单词转换为wordIDs。
3. 对短桶中的每个单词都转到文档列表的开始并获得所有文档列表
4. 搜索引擎对每个查询请求计算文档排序
5. 返回排序得分最高的搜索结果

搜索引擎是怎么样在一秒钟之内处理数千次查询请求的？

在现实中，一个商业搜索引擎包括许多集群，每个集群都是一个完整的大规模搜索引擎，会存储所有Web页面。并能够提处理各种查询请求。当用户输入了一个查询时，先由一个基于域名服务的负载均衡系统分配至一个集群。分配时要同时考虑用户与物理集群的距离和可用能力。

这些集群分布在世界各地，它们可能位于不同的城市和不同的国家。对于每个查询请求，只有一个HTTP请求被发送到一个集群上去。现在我们可以计算一下，如果我们的目标是4,000次查询请求每秒。哇！如此之多，但是我们有10个集群，每个集群实际上需要在每秒钟处理400次查询请求。

让我们来看看当一个查询请求到来时，一个集群内部是什么样子的。

• 首先，基于硬件的负载均衡器会把这个查询请求分配给某台Web服务器。

• 然后， 每台Web服务器上都有搜索引擎缓存。如果这个查询请求之前被搜索和缓存过，那么搜索引擎缓存将马上返回搜索结果。

因此，我们的目标是每秒处理400次查询请求，如果其中80%的查询请求都使用缓存中的结果，那么我们只需要在每秒钟处理80次查询请求就可以了。
另外，索引服务器也有很多副本，所以假设每台索引服务器都有3个副本，那么每台索引服务器每秒只需要处理20次查询请求。

这张幻灯片展示的是谷歌的查询服务器的架构。

• 因此，当一个查询请求到来时，谷歌的Web服务器会把这个查询请求发送给一些索引服务器并从索引服务器获得搜索结果列表。如有需要访问文档信息，那么索引服务器会把请求分配给某个文档服务器并获得所需的文档。

搜索引擎还有一个称为拼写检查的模块，这是因为在查询词中经常会存在一些原始错误。如果这些原始错误能够被更正，那么搜索结果就会更好。在索引服务器内部，你们可以看到你们所熟知的倒排索引，我们在第一部分介绍了倒排索引。

例如，让一个查询请求到来时，查询请求包含t1和t2两个词，这两个词汇被发送给索引服务器，索引服务器会从倒排索引中分别获取第一个词的倒序排列表和第二个词的倒序排列表。然后某个模块会合并这两个倒序排列表并为每个文档计算一个相关性分数。

• 最后，搜索引擎返回得分最高的K个文档的文档ID。

现在，我们的目标是让每个索引服务器在每秒钟返回27次查询请求。现在，这个数字并不是很大了。非常幸运，我们还有一些优化性能的方法。例如，我们可以使用动态剪枝算法来计算得分最高的K个文档。这就是说，我们不需要对包含t1和t2的所有文档进行全排序，我们只需要得分最高的K个文档。通常来说，K的取值是10。因此，这样我们就可以做得更好了。当我们为每个查询词加载到排表时，我们能够计算倒序排列表的相交部分，对每个文档进行评估并根据相关性得分排序。

参考文献：
[1] S. Brin and L .Page. The anatomy of a large-scale hypertextual web search engine In Proceedings of the Seventh International World Wide Web Conference, 1998
[2] A. Barroso, J. Dean and U. Hlzle. Web Search for a Planet: The Google Cluster Architecture IEEE Micro, 2003
[3] Sanjay Ghemawat, Howard Gobioff and and Shun-Tak Leung. The Google File System. SOSP’03, 2003
[4] J Dean and S Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. 00104, 2004

探寻搜索的多个维度

//TODO