如何设计搜索引擎百亿级网页计算关键技术(组图)

　　

如何设计搜索引擎百亿级网页计算关键技术(组图)

　　

　　背景

　　360搜索是360的重要产品，目前拥有数万台服务器，每天抓取的网页数量高达10亿，引擎收录的优质网页数量超过数十个数十亿。

　　通过本文，360搜索技术团队将向您介绍如此强大的搜索引擎是如何设计的，涉及到哪些关键技术点。

　　360 搜索概览

　　

　　目前，360搜索每天抓取的网页数量高达10亿。已经收录的网页基本上是万亿级的网页集合，实际可搜索的网页在百亿级的网页集合。

　　目前，360搜索的日流量为1亿pv。我们目前的线上线下集群有几万台服务器来维护如此大量的计算。

　　主要内容

　　本文的分享将主要围绕百亿网站搜索引擎架构的一些核心模块的理论设计。本次分享内容分为以下四个模块：

　　如何设计搜索引擎百亿网络计算关键技术、网络索引组织模式、网络搜索与相关性 01 如何设计搜索引擎

　　从如何设计搜索引擎开始。

　　基本搜索

　　用户请求后，整个搜索引擎的工作流程大致如下：

　　

　　首先使用分词组件进行分词，将query分成多个词，然后多个词会从我们的倒排索引中得到倒排拉链。在倒拉链的基础上，进行交点计算。转到所有命中的文档列表。拿到文档列表后，我们希望能够向用户反馈高质量的网页。这时候我们还需要做rank计算。排名计算是取倒排中的一些位置索引信息，包括前排的一些排名属性特征信息进行评分，最后将得分较高的Top N结果反馈给用户。当然，在展示前端网页时，需要从前排提取摘要信息展示给用户。这是整个检索过程。

　　基本索引

　　整个搜索过程涉及两个库。第一个是正向索引，另一个是倒排索引。我给大家简单介绍一下这两个库。

　　

　　什么是正指数？我们从互联网上爬取的网页收录了很多信息，包括页眉、标题、文本、标签等，我们首先从网页中提取文章和文章相关特征的主体。当然，我们也会输入一些挖掘信息，然后再做一些分词。在这个过程中，我们为整个网页生成了两部分数据。第一部分是属性。所谓属性就是这些网站的一些特征，比如网站classification信息，网站rank相关信息等，二是对文本进行分词的结果。

　　整个前向索引是一个以doc为key，attributes和wordlist为value的结构。由于用户在搜索时使用word作为key，我们希望将前向索引转化为适应用户搜索的结构，所以我们将前向索引转换为word为key，doclist为key。一种价值结构，可以为用户提供高效的检索。这就是我们所说的倒排索引。

　　搜索模型

　　以上简单介绍了搜索引擎的工作过程和基本概念，接下来我们来谈谈如何从用户检索的角度来设计一个搜索引擎，它的检索模型是什么？

　　

　　第一步，查询分析

　　首先要做的是分析用户输入的查询。查询分析主要包括三点：确定检索粒度、词条属性分析、查询需求分析。

　　所谓确定的搜索粒度，就是分词的粒度。我们将提供标准的分词，以及短语和复合词。不同分词粒度返回的网页集合是不同的。标准分割的粒度越小，返回的结果越多，从中获得高质量结果的能力越低。词组和复合词本身就是一个准确的搜索组合，获得的网页集合的质量会更高。

　　本节主要涉及两点。

　　第一点是查询中每个词的词项权重。权重有什么用？每个用户的查询都有自己的焦点。比如查询“北京长城”，当用户输入这个词进行搜索时，实际上是想搜索长城。北京只是长城的预选赛。所以在计算词重时，以长城为主词。来推荐。即使查询只搜索长城，也会返回符合用户预期的结果，但如果只搜索北京，则不可能返回用户预期的结果。

　　第二个是术语本身的接近程度。紧密度表示用户输入的查询的某种关联关系。举个明显的例子，有些查询是定向的，比如北京到上海的机票怎么买？多少钱？这本身就是定向语义。

　　用户分析查询本身的意图是什么？当然，它还包括一些对时间敏感的功能。例如，“If You Are the One”这个词，它有电影和综艺节目。

　　

　　

　　如果我们能分析出用户是想看电影还是看综艺，我们会反馈更好的结果给用户，满足用户的需求。

　　查询分析这里我主要做一个简单的介绍。查询分析中涉及到的一些算法方面的东西可能以后有机会再分享。这里就不介绍了。

　　第二步，查询策略

　　查询策略涵盖的工具是我们整个引擎架构需要做的工作。查询策略主要包括四个方面的工作：检索资源、确定相关网页的集合、计算结果的相关性、重新检查策略。

　　所谓的搜索资源，就是我们从互联网上获取的网页。可以从互联网上获得的网页大约有数万亿美元。如果我们把所有的网页都拿来，建立一个数据库进行索引，在用户层面进行搜索，从量级上来说是不现实的。因为它需要大量的机器资源，包括一些服务资源，我们从这么大的集合中选择满足用户需求的数据，成本也非常高。因此，我们将减少整个检索资源，这意味着我们将对互联网上所有抓取的网页进行质量筛选。

　　质量筛选结果后，我们还会对网页进行分类。当我们遇到不熟悉的网页时，我们会根据其网站的权威性和网站本身的内容质量进行评分。然后我们会对网页进行分类，标记优质网页、普通网页和时效性网页。这样，当用户搜索时，我们会优先选择优质的网页返回给用户。当然，从另一个维度，我们也会从内容上进行分类，即每个网页的title和qanchor信息，即锚文本信息，是对整个文章的描述，也代表文章的主体。如果我们将标题和锚点信息作为用户回忆的相关 URL 的集合进行优先排序，其准确性将高于从文本中获得的结果的质量。当然，我们也会保留这些信息来增加它的召回量。这是准备检索的检索资源。

　　这部分基本上可以分为两点。

　　一个是整个查询被拆分后命中的词条。能够命中查询当然是非常好的，因为可以反映相关数据。正常情况下网站与用户查询的相关性非常高。

　　但是也会出现这样的问题。所有查询完整命中可能返回网站 不够。这时候我们就需要对词partial hits做一些策略。在前面的查询分析中提到了词重的概念。我们可以选择一些词权重更重要的词作为召回结果的词条。整个确定相关网页集合的过程就是一个计算交集的过程，后面会详细介绍。

　　拿到相关网页后，我们会打分。分数就是所谓的结果的相关性计算。我在这里列出了两个最基本的计算。首先是基础权重的计算，基于每个term与文章本身的相关信息。第二个是termcompactness计算，也就是文章中term在整个查询中的分布。

　　之所以有复查策略，是因为用户搜索过程中返回的结果可能比较少，或者返回给用户的结果质量可能较低。最糟糕的是结果不符合用户的真实意图。我们可以通过以下三种方式来解决这个问题。一是增加搜索资源以获得更多结果；但是为了通过更小粒度的词条得到更多的结果，减去一些不重要的词条，我们也可能会做一些查询重写和查询扩展来满足用户的意图。

　　从整个检索模型可以看出，我们首先要做的就是查询分析；其次，我们需要提前准备好检索资源，也就是所谓的索引；第三点，在一个查询到来后，我们通过交集计算确定相关网页集合，然后通过相关计算将优质集合返回给用户。最后，如果结果不符合用户的要求，我们可以重新检查。

　　此检索模型是我们 360 度搜索设计的基础。

　　02 百亿网络计算的关键技术

　　给大家介绍一下360搜索的关键技术，一个百亿网页的搜索引擎。这里主要介绍离线建库和在线检索两个核心模块。

　　

　　离线建库与在线检索

　　线下图书馆建设

　　首先，要离线构建数据库，我们需要有一些基础设施，主要有Hbase/HDFS、Map-reduce和Storm/Kaka三部分。

　　第一个是Hbase和HDFS。我们的网页非常重要。我们会把网上所有的网页抓取到Hbase库中，我们也会把我们提供给检索的网页存储在Hbase库中。为什么要使用 Hbase？因为Hbase是分布式的，支持列存储。支持列存储对我们来说非常重要，因为在我们所有网页的爬取过程中，包括同学的排名计算过程，都会做一些局部更新，也就是根据自己需要的数据进行更新。列存储可以轻松满足我们的需求。 HDFS 主要用于构建索引和存储输出索引文件。这些都是登陆数据，开始与在线更新链接的作用（在线从HDFS拉取数据）。

　　当然，我们的搜索引擎也会涉及到时效问题，尤其是突发时效性，这可能也需要实时计算模型。我们现在的话也是基于Storm，当然也有一些我们内部在做的实时开发项目。

　　整个线下图书馆建设的三个主要核心点。

　　第一个是索引划分。所谓的索引划分，我们不可能用一个数据库来表达数百亿个网页。即使我们能稍微表达一下，也没有这么大的机器提供这么大的磁盘来存储这些数据，因为索引大概是几个P级的。因此，我们需要将索引划分为小网页集合，然后为小网页集合构建索引库，并基于小网页集合与在线在线服务进行一一对应。

　　第二点是创建索引。索引的创建基本上是基于 Map-reduce 运行的批处理任务。因为如果我们数百亿的网页需要运行下去，可能需要大量的资源，时间也会很长。 Map-reduce 本身提供了一种分布式计算机制，可以满足我们的需求。

　　第三点是索引更新。这一块主要涉及到第一是我们每天抓取的新数据；二是rank学生需要在线做特征或者一些属性的迭代计算，需要在线更新。因此，百亿数据的索引更新也会涉及。

　　在线搜索

　　在线搜索的基础架构包括三部分：分布式服务、请求广播和负载均衡。

　　在线搜索最底层的两个核心模块是交集计算和基础相关计算。

　　架构

　　我会通过下图给大家大致了解一下搜索引擎的整体结构。

　　

　　首先，我们先从官网抓取网页，抓取到的网页会存储在基于Hbase的网页库中。这是一个万亿规模的网页库。下一步是质量筛选，然后我们将通过质量筛选的网页放入我们索引的网页库中。所有的数据库建设，包括排名计算，以及所有与搜索引擎相关的部分，都依赖于下面的网络索引库。我们在建立索引的时候会做一个分片的过程，分片机制采用区间划分。那么区间划分基本都是以md5为key，md5本身就是一个64位整数，64位整数的范围作为区间划分。从 URL 转换来看，md5 本身是均匀分布的，所以我们的 shard 会按照这个间隔平均分配。其实我们划分的每个索引节点的大小也是相等的。

　　分片后，我们将基于 Map-reduce 为每个分片运行以生成索引。索引主要包括上述的正向索引和倒排索引。然后索引会被推送到下面的在线服务推荐，每个在线服务推荐负责一个索引库。在这里你可以看到，我们还根据网页的类型划分了索引库，比如重要的网页索引库和普通的网页索引库。

　　还有一个问题。如果我们每天添加的新网站超过我们的实时网页，我们该怎么办？在这种情况下，我们将经历另一个过程。网页被抓取后，还会有一个质量过滤器。这种质量过滤器有两个过程。第一个是实时计算，通过我们刚才提到的Storm集群，包括我们目前公司内部的Titan集群进行实时计算，生成实时索引。二是我们会对每天更新的数据进行批量计算，并基于Map-reduce生成相互索引，从而可以及时覆盖所有时间点。

　　整个离线建库基本上就是这样一个过程。下面介绍在线检索模块。检索到用户后，我们首先进行查询分析。然后我们将查询分析的结果丢给分布式服务的一个请求节点，这个请求节点会通过广播的方式将请求广播给这几个索引库。一些交集计算将在索引库中完成。第二步，我们将计算基本相关性，然后将高质量结果的Top N返回给上层服务请求节点。服务请求节点也会实现一些策略，比如用户的一些特定需求，包括一些机器学习的排序，最终返回给用户的网页基本在几百个左右。

　　整个架构流程就是这样一个模型。接下来，我将详细谈谈我们的一些关键核心模块的设计。

　　03 网页索引组织方式

　　先说一下web索引的组织方式，即正向索引和倒排索引是如何组织的。

　　前索引

　　

　　如果要使用正向索引，首先要考虑的问题是如何支持独立更新？独立更新的原因是，当我们的排名同学在做任何数据挖掘，包括一些特征计算时，每天都会出现新的迭代。在这种情况下，他需要正指数来支持这种日级别的更新。它甚至支持每小时更新。所以我们希望前向索引可以设计得足够简单，足够独立。我们所有的设计主要依赖于每个索引库的 URL 列表。它在url列表中的位置代表的是doc id，数据属性的存储会以定长数据块的形式存放在数据文件中。数据块的下方是其对应的doc id信息。这样，在更新和搜索的过程中，我们只需要知道它的doc id，就很容易找到它的位置了。这样做的第一个好处是容易生成索引文件；二是可以根据自己的需求进行更新。

　　我们还要考虑另外一个问题，就是算法资源挖出来的一些特征，并没有收录所有的信息。比如有一些团购网站，美食介绍网站，会有一些位置信息，但是这些都是稀疏信息，不可能按照这个固定长度，每个url都会分配一个数据块，其中会造成很多资源的浪费。所以这里我们要为这个稀疏属性做一个变长的数据块，但是它的结构发生了变化，并且有一个头信息。头信息主要用于存储其在数据文件中的位置信息。整个头部信息和url列表是一一对应的。属性信息存储在它本身中。这种情况下，我们可以直接通过他的doc id Offset找到它，然后通过offset就很容易找到它的属性了。

　　倒排索引

　　

　　倒排索引，我们还需要考虑两个问题。第一个问题是从正向索引变为倒排索引。数据量会急剧增加，因为我们面对的是一个词对应的doc list，而且doc list的重复度非常高，这种情况下我们需要对倒排索引进行一次压缩。

　　我们压缩的原则基本上是压缩比越大越好；解压越快越好。这就需要对整个倒排表进行结构化设计。我们采取的做法是将整个倒排表分成多个块，通过一些压缩算法对每个块进行压缩。整个倒表分块后，查找时需要按照这种分块方式进行解压，只要解压后的分块满足用户的需要，后面的分块就不需要解压了。在这种情况下，可以降低减压成本。

　　在用户搜索请求到来后，我们希望搜索能够尽快，所以我们希望提供范围搜索。我们会设置一个segment，每个segment会记录每个动态表块的最小id和最大id来表示范围。在这种情况下，在检索倒排表的过程中，我们可以先检索段，通过段找到它在哪个块中，然后进行检索。整个倒排索引形成了四级结构。第一个是它自己的词汇，第二个是段信息，第三个是倒排列表，第四个是针对某个文档中的每个单词。位置信息，该信息主要用于基础相关计算。

　　04 网络搜索和相关性

　　交叉口模型

　　我们来谈谈在检索过程中如何计算交集？

　　

　　Intersection 是一个非常核心的检索模块，也是一个对检索性能要求非常高的模块。简单的给大家举个例子，告诉大家intercommunity模块的设计。

　　例如，用户查询由三个词组成。在求交的过程中，首先从这三个词中选择拉链最短的词。因为用最短的拉链与其他拉链相交，相交的次数会减少。

　　第二步，我们得到最短的zipper后，比如现在word 1的zipper是最短的，那么我们依次构建word 1的倒排zipper，从里面获取每个doc id和其他倒排线倒拉链。拉链的 doc id 是为交叉点计算的。我将使用 doc id=11 向您解释请求的具体步骤。例如，倒拉链中有11字。在倒拉链中，我们首先需要找到的是它的段信息。我们发现它在第二段，可以清楚的知道它在word 2的第二个倒拉链数据块中。找到这个块后，我们会做一个二分查找，因为我们在做索引，里面的信息文档列表是有序的。做一个二分查找得到它是比较稳定的。

　　当然，在二分查找的过程中，我们也会做一些优化处理，也就是一些步长策略。什么是阶梯策略？让我举个例子，如果我们想找到 6 倍的 doc id。如果我们只做二分搜索，我们需要做大约 4 次查询搜索才能找到这个 doc id。所以我们希望一些策略可以弥补二分查找的不足。这就是阶梯策略。在第一步中，我们首先进行搜索。比如找到6的doc id会分布在1到7的范围内，那么我们就利用1和7的边界信息进一步计算它到6的距离，通过计算可以看到7到 6 是一个步长，1 到 6 是五个步长。在这种情况下，我们将改变策略，即一步找到6的信息。当然，这是一个非常极端的例子。我想用这个例子来说明，只要到它的边界的距离比较近，我们就会切换这个步长策略来提高查询搜索的性能。

　　基本相关性

　　让我简单介绍一下基本的相关性。这也是整个检索的核心部分，也是一个耗时的检索模块。相关性计算 不可能计算出很多策略相关的信息，会影响底层数据采集的性能。我们这里主要做了两方面的工作，一是基础赋权，二是compactness计算。

　　一、基础赋能

　　

　　什么是基本授权？就是解决query中每个term及其对应的文章的权重计算。

　　首先介绍TF和IDF这两个概念。

　　技术模型是 TF*IDF。但在实际应用中，不会这么简单，会出现很多问题。例如文章很长，所以它的TF不会太准确。现在业界也有一个模型叫BM25，主要是结合了文章length和这个词的term weight的一些概念。

　　如果我们想要取得更好的结果，那么我们必须在数据挖掘方面做一些工作。比如我们需要挖掘出每个文章主题的信息，关键词，以及关键词的一些限定词，这样我们就可以对词条进行分类，得到词性信息，这样可以更容易并且更准确地将这个词的权重信息描述给文章。

　　二、接近度计算

　　

　　所谓贴近度计算，是指用户查询过来后对查询进行的分词。一是文章中相邻词的分布有多接近；另一个是跨词条的信息，即方向信息。

　　可以简单的理解为我要计算的是距离问题。我在这里列出了一个简单的具体模型。我们首先选择query中的一个词作为中心点，比如B。然后我们从文本文本的位置信息中减去query的位置信息，然后通过计算中心点来计算出它的相对位置。比如词条A本身就有一个像位置1这样的距离。当然，在计算A跟在他后面的距离的过程中，你会发现因为在B的后面，他的距离可能会被拉长。在这种情况下，它解决了方向性问题。 （参考：接近距离）

　　A 后面的距离大约是 4。因此，我们会针对增加的距离做一些抑制。基本相关性是检索的基础。当然，在基础相关性的基础上，我们会把优质网页的集合带到上层，上层也会做一些排名计算。你可能会理解，比如这个LTR模型是用来做一些排序计算的，当然也会有一些针对用户的策略，包括一些针对用户意图评分的策略。最后，一个丰富的结果集返回给用户。

　　其他相关技术要点

　　前面我基本介绍了360搜索的核心模块和关键技术。当然，搜索还涉及到很多其他的技术点，比如：