针对爬虫获取的海量数据#xff0c;如何高效地进行数据管理#xff1b;当用户输入搜索词的时候#xff0c;如何快速查找包含搜索词的网页…一、内容分析

我们准备开发一个针对全网内容的搜索引擎产品名称为“Bingoo”。

针对爬虫获取的海量数据如何高效地进行数据管理当用户输入搜索词的时候如何快速查找包含搜索词的网页内容如何对搜索结果的网页内容进行排序使排在搜索结果列表前面的网页正好是用户期望看到的内容。

12.1

一个完整的搜索引擎包括分布式爬虫、索引构造器、网页排名算法、搜索器等组成部分Bingoo的系统架构如下。

分布式爬虫通过存储服务器将爬取的网页存储到分布式文件集群HDFS为了提高存储效率网页将被压缩后存储。

存储的时候网页一个文件挨着一个文件地连续存储存储格式如下。

每个网页被分配得到一个8字节长整型docIDdocID之后用2个字节记录网页的URL的长度之后4个字节记录压缩后网页内容数据的长度所有存储的网页的头14个字节都是同样的格式。

之后存储URL字符串和压缩后的网页内容数据。

读取文件的时候先读14个字节的头信息根据头信息中记录的URL长度和数据长度再读取对应长度的URL和网页内容数据。

搜索引擎能够快速查找的核心就是利用索引根据用户的查询内容查找匹配的索引根据索引列表构建结果页面。

索引的构造主要通过索引构造器完成索引构造器读取HDFS中的网页内容解压缩后提取网页中的单词构建一个“docID-单词列表”的正排索引。

然后索引构造器再根据这个正排索引构建一个“单词-docID列表”的倒排索引“docID列表”就是包含了这个单词的所有网页列表。

利用这个倒排索引搜索器可以快速获得用户搜索词对应的所有网页。

网页中所有的单词构成了一个词典实际上词典就是一个Hash表key就是单词value就是倒排索引的网页列表。

虽然互联网页的内容非常庞大但是使用到的单词其实是非常有限的。

根据Google的报告256M内存可以存放1400万个单词这差不多就是英文单词的全部了。

在构建索引的过程中因为要不断修改索引列表还要进行排序所以有很多操作是需要进行加锁同步完成的。

对于海量的互联网页的计算这样的索引构建速度太慢了。

因此我们设计了64个索引桶根据docID取模将不同网页分配到不同的桶中在每个桶中分别进行索引构建通过并行计算来加快索引处理速度。

索引构造器在读取网页内容、构造索引的时候还会调用URL提取器将网页中包含的URL提取出来构建一个链接关系表。

链接关系表的格式是“docID-docID”前一个docID是当前网页的docID后一个docID是当前网页中包含的URL对应的docID。

一个网页中会包含很多个URL也就是会构建出很多个这样的链接关系。

后面会利用这个链接关系表使用PageRank排名算法对所有网页进行打分排名当索引器得到查找的网页列表时利用PageRank值进行排名最终呈现给用户保证用户最先看到的网页是最接近用户期望的结果页面。

12.2

一个运行良好的搜索引擎的核心技术就是索引和排名所以我们将分别说明这两种技术要点。

12.2.1

索引构造器从HDFS读取网页内容后解析每个页面提取网页里的每个单词。

如果是英文那么每个单词都用空格分隔比较容易如果是中文需要使用中文分词器才能提取到每个单词比如“高并发架构”使用中文分词器得到的就是“高并发”、“架构”两个词。

首先索引构造器将所有的网页都读取完构建出所有的“docID-单词列表”正排索引。

然后遍历所有的正排索引再按照“单词→docID列表”的方式组织起来就是倒排索引了。

我们这个例子中只有两个单词、7个网页。

事实上Bingoo数以千亿的网页就是这样通过倒排索引组织起来的网页数量虽然庞大但是单词数却是比较有限的。

所以整个倒排索引的大小相比于网页数量要小得多。

Bingoo将每个单词对应的网页列表存储在硬盘中而单词则存储在内存的Hash表也就是词典中词典示例

对于部分热门的单词整个网页列表也可以存储在内存中相当于缓存。

在词典中每个单词记录下硬盘或者内存中的网页列表地址这样只要搜索单词就可以快速得到对应的网页地址列表。

Bingoo根据列表中的网页编号docID展示对应的网页信息摘要就完成了海量数据的快速检索。

如果用户的搜索词正好是一个单词比如“高并发”那么直接查找词典得到网页列表就完成查找了。

但是如果用户输入的是一个句话那么搜索器就需要将这句话拆分成几个单词然后分别查找倒排索引。

这样的话得到的就是几个网页列表还需要对这几个网页列表求交集才能得到最终的结果列表。

比如用户输入“高并发架构”进行搜索那么搜索器就会拆分成两个词“高并发”、“架构”得到两个倒排索引

高并发-2,3,5,7

需要对这两个倒排索引求交集也就是同时包含“高并发”和“架构”的网页才是符合搜索要求的结果最终的交集结果应该是只有一篇网页即docID为2的满足要求。

列表求交集最简单的实现就是双层for循环但是这种算法的时间复杂度是O(n^2)我们的网页列表长度n可能有千万级甚至更高这样的计算效率太低。

一个改进的算法是拉链法我们将网页列表先按照docID的编号进行排序得到的就是这样两个有序链表

同时遍历两个链表如果其中一个链表当前指向的元素小于另一个链表当前指向的元素那么这个链表就继续向前遍历如果两个链表当前指向的元素相同该元素就是交集元素记录在结果列表中依此继续向前遍历直到其中一个链表指向自己的尾部nil。

拉链法的时间复杂度是O(2n)远优于双层循环。

但是对于千万级的数据而言还是太慢。

我们还可以采用数据分片的方式进行并行计算以实现性能优化。

1万亿)区间而每个倒排索引链表平均包含1千万个docID。

我们把所有的docID按照1千亿进行数据分片就会得到10个区间[0,

1千亿)[1千亿2千亿)……[9千亿1万亿)。

每个倒排索引链表大致均匀分布在这10个区间我们就可以依照这10个区间范围将每个要遍历的链表切分为10片每片大约包含1百万个docID。

两个链表只在自己对应的分片内求交集即可因此我们可以启动10个线程对10个分片进行并行计算速度可提高10倍。

事实上两个1千万长度的链表求交集最终的结果可能不过几万也就是说大部分的比较都是不相等的。

比如下面的例子。

第一个链表遍历到自己的最后一个元素才和第二个链表的第一个元素相同。

那么第一个链表能不能跳过前面那些元素呢很自然我们想到可以用跳表来实现如下图。

跳表实际上是在链表上构建多级索引在索引上遍历可以跳过底层的部分数据我们可以利用这个特性实现链表的跳跃式比较加快计算速度。

使用跳表的交集计算时间复杂度大约是O(log(n))。

此外虽然搜索引擎利用倒排索引已经能很快得到搜索结果了但搜索引擎应用还会使用缓存对搜索进行加速将整个搜索词对应的搜索结果直接放入缓存以减少倒排索引的访问压力以及不必要的集合计算。

12.2.2

Bingoo使用PageRank算法进行网页结果排名以保证搜索结果更符合用户期待。

PageRank算法会根据网页的链接关系给网页打分。

如果一个网页A包含另一个网页B的超链接那么就认为A网页给B网页投了一票。

一个网页得到的投票越多说明自己越重要越重要的网页给自己投票自己也越重要。

PageRank算法就是计算每个网页的PageRank值最终的搜索结果也是以网页的PageRank值排序展示给用户。

事实证明这种排名方法非常有效PageRank值更高的网页确实更满足用户的搜索期望。

B网页包含了A、D两个页面的超链接相当于B网页给A、D每个页面投了一票如果初始的时候所有页面都是1分那么经过这次投票后B给了A和D每个页面1/2分B包含了A、D两个超链接所以每个投票值1/2分自己从C页面得到1/3分C包含了A、B、D三个页面的超链接每个投票值1/3分。

而A页面则从B、C、D分别得到1/21/31分。

用公式表示就是

\(\\small

\\frac{PRB}{2}\\frac{PRC}{3}\\frac{PRD}{1}\)

等号左边是经过一次投票后A页面的PageRank分值等号右边每一项的分子是包含A页面超链接的页面的PageRank分值分母是该页面包含的超链接数目。

这样经过一次计算后每个页面的PageRank分值就会重新分配重复同样的算法过程经过几次计算后根据每个页面PageRank分值进行排序就得到一个页面重要程度的排名表。

根据这个排名表将用户搜索出来的网页结果排序排在前面的通常也正是用户期待的结果。

但是这个算法还有个问题如果某个页面只包含指向自己的超链接其他页面不断给它送分而自己一分不出随着计算执行次数越多它的分值也就越高这显然是不合理的。

这种情况就像下图所示的A页面只包含指向自己的超链接。

解决方案是设想浏览一个页面的时候有一定概率不是点击超链接而是在地址栏输入一个URL访问其他页面表示在公式上就是

\(\\small

\\alpha(\\frac{PRB}{2}\\frac{PRC}{3}\\frac{PRD}{1})\\frac{1-\\alpha}{4}\)

上面\(\\small

1-\\alpha\)就是跳转到其他任何页面的概率通常取经验值0.15(即\(\\small

\\alpha\)

为0.85)因为有一定概率输入的URL是自己的所以加上上面公式最后一项其中分母4表示所有网页的总数。

\(\\small

M(P_{i})}^{}{\\frac{PageRank(P_{j})}{L(P_{j})}}

公式中\(\\small

P_{j}\)页面包含的超链接数N表示所有的网页总和。

由于Bingoo要对全世界的网页进行排名所以这里的N是一个万亿级的数字。

计算开始的时候将所有页面的PageRank值设为1带入上面公式计算每个页面都得到一个新的PageRank值。

再把这些新的PageRank值带入上面的公式继续得到更新的PageRank值如此迭代计算直到所有页面的PageRank值几乎不再有大的变化才停止。

二、粉丝福利

我根据我从小白到架构师多年的学习经验整理出来了一份50W字面试解析文档、简历模板、学习路线图、java必看学习书籍