360 搜索的百亿级网页搜索引擎架构实现

主要内容

我今天的分享的主要会侧重于百亿级网站搜索引擎架构的一些核心模块的理论设计。本次分享内容分为以下四个模块：

如何设计搜索引擎
百亿级网页计算关键技术
网页索引组织模式
网页检索和相关性

01 如何设计搜索引擎

首先从如何设计一个搜索引擎讲起。

基础检索

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

首先用切词组件做分词，把 query 分成多个 word，然后多个 word 会从我们的倒排索引里面获取倒排拉链，在倒排拉链的基础上，会做求交计算来拿到所有命中的 doc list。拿到 doc list 之后，我们希望能够把优质的网页反馈给用户，这时候我们还需要做 rank 计算。rank 计算就是拿倒排里面的一些位置索引信息，包括在正排里面拿一些 rank 的属性特征信息做打分，最终会把分数比较高的 Top N 结果反馈用户。当然在前端 web 页面展示的时候，需要从正排中提取摘要信息，展示给用户。这就是整个的检索过程。

基础索引

整个检索过程涉及到两个库。第一个是正排索引，另一个是倒排索引，我这里针对这两个库给大家做一个简单的介绍。

什么是正排索引？我们从互联网上抓取的网页包含很多信息，包括网页头信息、标题、正文、标签等。我们首先从网页中把文章的正文以及文章相关的特征提取出来，当然也输入一些挖掘的信息，然后做一些分词处理。这个过程，我们是把整个的网页生成了两部分数据，第一部分就是属性，所谓属性就是针对这些网站的一些特征，比如说网站分类信息、网站 rank 相关信息等。第二个是针对的正文的分词的结果。

整个的正排索引，就是以 doc 为 key，以属性和 word 列表为 value 的一种结构。因为用户在检索时是以 word 为 key 来做检索的，我们希望能够把正排索引转化成一种结构，来适应用户的检索，所以我们把正排索引转化成了以 word 为 key，以 doclist 为 value 的一种结构，这个结构能够给用户提供高效的检索。这就是我们所谓的倒排索引。

检索模型

上面简单地介绍了搜索引擎的工作过程及基本概念，那下面我们讲一下，站在用户检索的角度来说，如何来设计一个搜索引擎，它的检索模型是什么样的？

1 query 分析

首先要做的就是针对用户输入的 query 进行 query 分析。query 分析基本包涵三点：确定检索的粒度、Term 属性分析、Query 需求分析。

确定检索的粒度

所谓确定检索粒度，就是分词的粒度。我们会提供标准的分词，以及短语、组合词。针对不同的分词粒度返回的网页集合是不一样的。标准分词粒度越小，返回的结果越多，从中拿到优质结果的能力就越低。而短语和组合词本身就是一个精准的检索组合，相对的拿到的网页集合的质量就会高一些。

Term 属性分析

这一块主要是涉及到两个点。

第一个点就是 query 中每一个词的 term weight（权重）。权重是用来做什么的？每一个用户的 query 它本身都有侧重点。举个例子，比如“北京长城”这个 query，用户输入这个词搜索的时候其实他想搜的是长城，北京只是长城的一个限定词而已，所以说在 term weight 计算的时候，长城是作为一个主词来推荐的。即使 query 只搜长城也会返回一个符合用户预期的结果，但是如果只搜北京的话，是不可能返回用户预期的结果的。

第二个就是 term 本身的一些紧密性。紧密性代表用户输入的 query 的一些关联关系。举个明显的例子，有些 query 是具有方向性的，比如说北京到上海的机票怎么买？多少钱？这本身是有方向性的语义。

Query 需求分析

针对 query 本身我们要分析用户的意图是什么？当然也包括一些时效性的特征。举个例子，比如说“非诚勿扰”这个词，它有电影也有综艺节目。

如果说能够分析出用户本身他是想看电影还是看综艺节目，我们就会给用户反馈一个更优质的结果，来满足用户的需求。

query 分析这里我主要做了一个简单的介绍，query 分析涉及到的一些算法的东西，可能以后有机会再具体分享，这里先不做介绍。

2 查询策略

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

检索资源

所谓检索资源就是我们从互联网上拿到的网页。从互联网上能拿到的网页，大概是万亿规模，如果说我们把所有网页拿过来，然后做建库做索引，在用户层面检索，从量级上来说是不太现实的。因为它需要很多的机器资源，包括一些服务资源，另外我们从这么大一个集合里面来选取符合用户需求的数据，代价也是很大的。所以说我们会对整个检索资源做一个缩减，也就是说我们会针对互联网上所有的抓取过的网页，做一个质量筛选。

质量筛选出结果之后，我们还会对网页做一个分类。我们拿到陌生的网页，会根据它本身的站点的权威性，网站本身的内容质量做打分。然后我们会对网页分类，标记高质量的网页，普通网页，时效性的一个网页，这样的话在用户检索的时候我们会优先选择高质量的网页返回给用户。当然从另外一个维度来讲，我们也会从内容上进行分类，就是说每个网页的 title 和 qanchor 信息，也就是锚文本信息，是对整篇文章的一个描述信息，也代表文章的主体。如果我们优先拿 title 和 anchor 信息作为用户的召回的一个相关 url 集合，那它准确性要比从正文拿到的结果质量要高。当然我们也会保留这种信息来提升它的召回的量。这是检索要准备的检索资源这一块。

确定相关网页集合

这一块的话基本上可以分为两点。

一个是整个 query 切分后的 term 命中，能够命中 query 当然非常好，因为它能够反应相关数据，正常情况下，网站和用户 query 相关性是非常高的。

但是也会存在这样问题，所有的 query 全命中有可能返回网站数量不够，我们这时候就需要做一些 term 部分命中的一些策略。前面 query 分析中讲到了 term weight 的概念，我们可能会选择一些 term weight 比较重要的 term 来作为这次召回结果的一个 term。整个确定相关网页集合的过程，就是一个求交计算的过程，后面我会再详细介绍。

结果相关性计算

我们拿到了相关的网页之后，会做一个打分，打分就是所说的结果相关性计算。我这里列举了两个最基础的计算。第一个是基础权值的计算，针对每个 term 和文章本身的相关性的信息。第二个就是 term 紧密度计算，也就是整个 query 里面的 term 在文章中的分布情况。

重查策略

为什么有重查策略，就是因为在用户检索过程中有可能返回的结果比较少，也有可能返回给用户的结果质量比较低，最差的就是结果不符合用户的真正意图。我们可能通过以下三个方式来解决这个问题，一是增加检索资源来拿到更多的结果；而是通过更小粒度的 term，减掉一些不重要的 term 来拿到的结果，还有我们可能也会做一些 query 的改写以及 query 的扩展，来满足用户的意图。

从整个检索模型可以看到，我们要做的工作首先是 query 分析；第二我们需要把检索资源提前准备好，那就是所谓的索引；第三点是在一个 query 过来之后，我们通过求交计算确定相关的网页集合，然后通过相关性计算，把优质的集合返回给用户，最后如果结果不满足用户要求的话，我们可以做一个重查。

这个检索模型，就是我们 360 搜索设计的一个基础。

02 百亿级网页计算关键技术

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

离线建库和在线检索

1 离线建库

首先离线建库这一块，我们要有一些基础设施，主要有三部分：Hbase/HDFS、Map-reduce、Storm/Kaka。

第一个是 Hbase 和 HDFS。我们的网页量级很大，我们会把互联网上所有的网页抓取过来存到 Hbase 库里，我们也会把我们提供检索的网页存到 Hbase 库里面。为什么用 Hbase 呢，因为 Hbase 是一个面向分布式，并支持列存储的。支持列存储这一点对我们很重要，因为我们所有的网页在抓取的过程中，包括 rank 同学在做 rank 计算的过程中，都会做一些部分更新，就是按照他们所需要的数据进行更新，那列存储就很容易满足我们的需求。HDFS 主要用于建索引和存储产出的索引文件，这些都是落地数据，启动了和线上更新衔接的作用 (线上从 HDFS 拉取数据)。

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

整个离线建库主要的核心点有三个部分：

第一个就是索引划分。所谓索引划分，百亿级的网页我们不可能用一个数据库就表示出来，即使我们能表示出来一点，也没有这么大的机器来提供这样一个磁盘存放这些数据，因为索引大概是几 P 的一个量级。所以说我们需要把索引划分成小的网页集合，然后再针对小的网页集合做索引库，在小的网页集合的基础上和线上的在线服务做一个一一对应的关系。

第二点是索引创建。索引创建这一块基本上是基于 Map-reduce 跑的批量任务。因为我们上百亿的网页需要跑下来的话，可能需要的资源很多，时间也会拉得很长，Map-reduce 本身提供了分布式计算的机制，能够满足我们的需求。

第三点是索引更新。这一块主要涉及到的一是我们每天新抓过来的数据；二是 rank 的同学要做线上特征，或者属性的一些迭代计算，要更新到线上。所以说也会涉及到百亿级别的数据的索引更新。

2 在线检索

在线检索的基础设施有三部分：分布式服务、请求广播、负载均衡。

分布式的服务框架是在线检索的一个基础配件；

在索引划分的时候，我们会把大的网页集合换成小的集合，在提供检索的时候，我们会以广播的方式来广播到各个小的索引单元，收集所有符合预期的网页集合才能够把它做归并排序，选出最优数据；

在线检索服务我们需要考虑更多的还有系统本身的稳定性，这个主要靠负载均衡来保证。

在线检索里面最底层的两个核心模块是求交计算和基础相关性计算。

架构

我会通过下面这个图给大家大概讲解一下搜索引擎整体架构的流程。

首先我们先从官网上抓取网页，抓取的网页会存到基于 Hbase 的网页库里。这个是一个万亿量级的网页库，下一步要做的工作是质量筛选，然后我们会把通过质量筛选的网页放到我们的索引网页库中，所有的建库，包括 rank 计算，以及所有与搜索引擎相关的部分都是依赖于下边的网页索引库进行的。我们在建索引的时候，会做一个分片处理，分片的机制采用了区间划分。那么区间划分基本上我们就是用 md5 作为 Key，本身 md5 是 64 位的整数，按照这 64 位整数的范围作为一个区间划分。从 url 转换上 md5 它本身是均匀分布的，那我们分片按照这个区间划分也会是均匀的，实际上我们划分的各个索引节点的量级也是均等的。进行分片之后，我们会针对每个分片基于 Map-reduce 来跑，生成索引，索引主要包括上面讲的正排索引和倒排索引。然后会把索引推送到下面的在线服务推荐，每个在线服务推荐负责一个索引库。这里可以看到，我们根据网页的类型对索引库也做了一个划分，比如说重要网页索引库和普通网页索引库。

还有一个问题，就是我们每天的新增的网站，超过我们实时的网页怎么办？这种情况我们会走另外一个流程，在网页抓取过来之后，也会有一个质量筛选，这个质量筛选有 2 个流程，第一个是实时计算，通过我们刚才讲到的 Storm 集群，包括我们目前公司内部的 Titan 集群，进行实时计算来生成实时性的索引。第二个是我们会把每天更新的这些数据做批量计算，基于 Map-reduce 生成一个相互索引，这样的话在时间上能够覆盖到所有的时间点。

整个离线建库基本是这样一个流程，下面介绍一下在线检索的模块。用户检索过来之后，我们首先做一个 query 分析。然后我们把 query 分析的结果扔给分布式服务的一个请求节点，这个请求节点通过广播的方式会把请求广播到这几种索引库这里。在索引库内部会做一些求交计算。第二步我们会做基础相关性的计算，然后把优质结果的 Top N 来返回给上层的服务请求节点。服务请求节点还会做一些策略，比如说用户的一些特定需求，包括一些机器学习的排序，最终返回给用户的网页基本上是几百条的一个量级。

整个架构流程是就是这样的模式。下面我会具体讲一下我们重点的一些核心模块的设计。

03 网页索引组织模式

我先讲一下网页索引组织模式，也就是正排索引和倒排索引是怎么组织的。

正排索引

我们要用正排索引，首先要考虑的第一个问题，就是如何支持独立更新？为什么要做独立更新，是因为我们 rank 的同学在做任何数据挖掘，包括一些特征计算的时候，每天都有新的迭代出现，这样的话他就需要正排索引能够支持这种天级的更新，甚至支持小时级的更新。所以我们希望正排索引能够设计得足够简单，也足够独立。我们这块所有的设计依赖的主要是每个索引库的 url 列表。url 列表中它的位置就代表 doc id，数据属性的存储会按照固定长度的数据块存放在数据文件中。数据块的下方位置就是它对应的 doc id 信息。这样在更新和查找的过程中，我们只需要知道它的 doc id，就很容易找到它所在的位置。这样的好处第一是容易生成索引文件；第二个是可以按照自己的要求进行更新。

我们还要考虑另外一个问题，就是有一些算法资源挖出来的特征，并不是包含了所有的信息。比如说有一些团购网站、美食介绍网站里面，会有一些位置信息，但这些是稀疏的信息，不可能按照这种固定长度，每个 url 都会分配一个数据块，这样会造成大量的资源浪费。所以我们这里会针对这种稀疏的属性做一个变长的数据块，但是它在结构上发生了变化，它有一个头信息。头信息主要是用来存储它在数据文件里面的位置信息，整个头信息和 url 列表是一一对应的，本身它里面存的就是属性信息，这样的话我们再通过他的 doc id 直接找到他的偏移，然后通过偏移很容易找到它的属性。

倒排索引

倒排索引我们也需要考虑两个问题，第一个问题，从正排索引转化为倒排，数据量会剧增，因为我们面向的是一个 word 对应的 doc list，doc list 重复度非常高，这样的话我们就需要针对倒排索引进行一个压缩。

压缩的话我们采用的原则基本是压缩比例越多越好；解压时越快越好。这就需要对整个倒排表做一个结构化的设计。我们采取的做法是把整个倒排表划分成多个块，针对每一个块通过一些压缩算法做压缩。整个倒排表划分成块之后，检索的时候，也需要按照这种块的模式来进行解压，所以只要解压到的块能够满足用户的需求，那下面的块就不用再解压了，这样的话就能减少解压的成本。

一个用户检索的请求过来之后，我们希望检索能越快越好，所以我们希望能够提供一个范围查找。我们会设立一个段，每个段会记录每一个动态表块的最小的 id 和最大的 id 来表示范围。那这样的话我们在检索一个倒排 list 的过程中，就先可以先检索段，通过段找到它的在哪个块，再做检索。整个倒排索引组成了一个四级结构，第一个就是它本身的词表，第二个是段信息，第三个是倒排表，第四个是针对每个 word 在某个 doc 里面一些位置信息，这个信息主要是用来做基础相关性计算的。

04 网页检索和相关性

求交模型

我们下面讲一下，在检索的过程中，求交计算是怎么做的？

求交是检索一个非常核心的模块，也是对检索性能提出非常大要求的一个模块。我简单地举一个例子来给大家讲一下整个求交模块的设计。

比如用户 query 是由三个词来组成的，在求交过程中，首先要从这三个 word 中选出拉链最短的一个 word。因为用最短的拉链去和其他拉链求交，会减少求交次数。

第二步，我们拿到最短拉链之后，比如现在 word 1 的拉链是最短的，那我们会依次建立 word 1 的倒排拉链，从倒排拉链中获得每个 doc id 和其他倒排拉链的 doc id 做求交计算。我拿 doc id=11 这个来给大家解释一下求交的具体步骤。比如说倒排拉链里面有 11 这个 word，那在倒排拉链里，我们首先要查找的是它的段信息。我们发现它是在第二个段里面，就能够很明确地知道它在 word 2 的第二个倒排拉链的数据块，找到这个块之后，我们再做二分查找，因为我们在做索引的时候，doc list 的信息有序的。做二分查找来获取它是比较稳定的。

当然我们在做二分查找的过程中，也会做一些优化处理，就是一些步长策略。什么是步长策略？我举个例子，如果我们要查找 6 倍的 doc id。如果我们只做二分查找的话，我们大概要做 4 次 query 查找才能找到这个 doc id。所以我们希望有些策略来补充二分查找的不足，这就是步长策略。第一步我们先做一次查找，比如查找 6 这个 doc id 会分布在 1 到 7 的范围之内。然后我们会通过 1 和 7 的边界信息来进一步计算它到 6 的距离。通过计算我们可以看到 7 到 6 就是一个步长，而 1 到 6 是五个步长。在这种情况下我们会改变策略，也就是我们会通过一个步长就找到 6 这个信息。当然这是一个非常极端的例子。我想通过这个例子说明，只要距离它的边界比较近的时候，我们就会转换这种步长策略，来提升 query 查找的性能。

基础相关性

下面我给大家简单介绍下基础相关性。这也是整个检索的一个核心部分，对检索来说，它也是比较耗时的一个模块。相关性计算它不可能把非常多的策略相关的信息都拿来计算，这样会影响底层收集数据的性能。我们这里主要做了两个方面的工作，一是基础赋权，二是紧密度计算。

1 基础赋权

什么是基础赋权？它是来解决 query 中的每一个 term 和它对应的文章的权重计算。

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

TF：代表承载信息量，即这个 word 在文章中出现的次数；
IDF：代表信息承载能力，即这个 word 在全网的出现次数

一个技术的模型，就是 TF*IDF。但是在实际的应用中不会只有这么简单，还会出现很多问题。比如一篇文章很长，那么它的 TF 就不会太准。现在业界也有一个模型叫 BM25，它主要加入了文章长度，和这个词语的 term weight 的一些概念。

我们如果想达到更好的效果的话，那么就要在数据挖掘上做一些工作。比如说我们需要挖掘出每篇文章的主题、关键词，以及关键词的一些限定词这些信息，这样可以针对 term 做一个分级，拿到词性信息，这样可以更容易、更准确地来描述这个 word 对文章的权重信息。

2 紧密度计算

所谓紧密度计算就是用户的 query 过来之后，针对 query 的分词，一是相邻 word 之间的紧密程度在文章中是怎样的分布；二是跨 term 的信息，那也就是方向的信息。

可以简单理解为我要算的就是一个距离问题。我这里列了一个简单的具体的模型。我们首先在 query 中选一个词作为中心点，比如 B。然后我们拿 text 文本的位置信息减去 query 的位置信息，然后再通过中心点的一个计算，算出它的相对位置。比如说 A 这个 term 本身它的距离像 1 这个位置，当然就是说他后边 A 的距离在算的过程中，你会发现因为它是在 B 的后面，他的距离可能就会拉长，这样的话它解决的是一个方向性的问题。(参考: proximity 距离)

在后面 A 的距离大概是 4。所以针对距离变长的这种情况我们会做一些打压。基础相关性是检索的一个基础。当然在基础相关性的基础上，我们会把优质的网页集合拿到上层，上层也会做一些 rank 的计算。大家可能有的了解比如这种 LTR 模型来做一些排序的计算，当然也会有一些针对用户策略，包括用户意图的一些策略来打分。最终返回用户一个丰富的结果集。