360搜索的百亿级网页搜索引擎的架构设计与实现( 四 ) _360搜索

整个架构流程是就是这样的模式。下面我会具体讲一下我们重点的一些核心模块的设计。
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查找的性能。