李智慧 · 高并发架构实战课
李智慧
同程艺龙交通首席架构师,前 Intel & 阿里架构师,《大型网站技术架构》作者
23286 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 26 讲
李智慧 · 高并发架构实战课
15
15
1.0x
00:00/00:00
登录|注册

10 | 搜索引擎设计:信息搜索怎么避免大海捞针?

中文分词
英文分词
随机跳转概率
自我投票
排序展示
迭代计算
投票机制
跳表
并行计算
数据分片
拉链法
双层for循环
句子拆分
单词搜索
倒排索引
正排索引
单词提取
docID->docID
64个索引桶
单词与倒排索引映射
单词->docID列表
docID->单词列表
docID分配
连续存储格式
压缩存储
并行处理
性能优化
多次迭代
万亿级数据
创造奇迹
王选、王江民、求伯君、雷军
Google的成功
解决方案
算法问题
PageRank值计算
网页链接关系
优化技术
网页列表交集
搜索词处理
索引构建
网页内容解析
链接关系表
并行计算
加锁同步
Hash表
倒排索引
正排索引
网页存储
编程实现
PageRank计算挑战
软件编程
编程英雄
PageRank算法
PageRank排名算法
索引
URL提取器
索引优化
词典
索引构造器
分布式爬虫
思考题
小结
搜索引擎核心技术
Bingoo搜索引擎
搜索引擎设计:信息搜索怎么避免大海捞针?

该思维导图由 AI 生成,仅供参考

你好,我是李智慧。
04 讲中,我们讨论了大型分布式网络爬虫的架构设计,但是网络爬虫只是从互联网获取信息,海量的互联网信息如何呈现给用户,还需要使用搜索引擎完成。因此,我们准备开发一个针对全网内容的搜索引擎,产品名称为“Bingoo”。
Bingoo 的主要技术挑战包括:
针对爬虫获取的海量数据,如何高效地进行数据管理;
当用户输入搜索词的时候,如何快速查找包含搜索词的网页内容;
如何对搜索结果的网页内容进行排序,使排在搜索结果列表前面的网页,正好是用户期望看到的内容。

概要设计

一个完整的搜索引擎包括分布式爬虫、索引构造器、网页排名算法、搜索器等组成部分,Bingoo 的系统架构如下。
分布式爬虫通过存储服务器将爬取的网页存储到分布式文件集群 HDFS,为了提高存储效率,网页将被压缩后存储。存储的时候,网页一个文件挨着一个文件地连续存储,存储格式如下。
每个网页被分配得到一个 8 字节长整型 docID,docID 之后用 2 个字节记录网页的 URL 的长度,之后 4 个字节记录压缩后网页内容数据的长度,所有存储的网页的头 14 个字节都是同样的格式。之后存储 URL 字符串和压缩后的网页内容数据。读取文件的时候,先读 14 个字节的头信息,根据头信息中记录的 URL 长度和数据长度,再读取对应长度的 URL 和网页内容数据。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

搜索引擎设计中的关键技术及PageRank算法的应用是本文的重点。文章详细介绍了Bingoo搜索引擎的系统架构,包括分布式爬虫、索引构造器、网页排名算法和搜索器等组成部分。特别是对索引构造器的工作原理进行了深入解析,包括正排索引和倒排索引的构建,以及利用并行计算和跳表提高搜索效率的方法。此外,文章还探讨了PageRank算法在网页结果排名中的重要性,以及如何解决其中的问题。总的来说,本文深入浅出地解释了搜索引擎设计中的关键技术,为读者提供了全面的概览。值得一提的是,PageRank算法的应用造就了Google的商业帝国,为搜索引擎行业带来了革命性的变革。文章以此引发读者对于搜索引擎技术的思考,并鼓励读者分享对于PageRank算法计算实现的思考,共同进步。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《李智慧 · 高并发架构实战课》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(13)

  • 最新
  • 精选
  • 👽
    再来说说思考题: 首先,大前提。海量数据计算,核心其实还是用算力去堆。分片之后堆足够的算力,也肯定是可以解决的。但是,受限于成本,肯定需要考虑如何效益最大化。 首先,还是利用算力闲置资源,因为这部分的实时性要求并不高。这部分涉及的知识应该是云原生服务编排,资源调度相关的知识点。把这部分算力,用空闲的资源提供计算服务。 具体步骤的话,首先将需要计算的数据先进行分片,使用不同的节点进行计算。其次,将数据的重要性进行排序,优先计算热点数据。比如,算力不足时,优先计算热点数据,算力充足时,再计算普通数据。 具体的本质,每次迭代都能影响PageRank评分,所以其实每一次迭代都能带来一次评分的影响。只不过越来越精确。每一次PageRank迭代过后,数据的可用性,和用户体验都会提升。我个人评估,前几次迭代,PageRank的用户体验已经比较不错了,算力就会侧重于用户体验还不太好的PageRank。 以上是我的整体思路。

    作者回复: 很赞啊,感觉你在不太了解大数据计算框架的前提下推导出大数据计算的核心思路方法。 PageRank的编程实现采用MapReduce之类的大数据计算框架,编程方法可采用图计算或者矩阵计算。归根结底都是如何将数据分片后计算。

    2022-03-14
    12
  • neohope
    补充一些内容: 1、PageRank其实有两层含义,第一层是被越多的网页指向就越重要,第二层是被越重要的网页指向就越重要 2、数据结构优化工作很重要,由于数据量很大,每个结构省下1Byte,【1Byte*网页数量*副本数量】,就能节约大量服务器和存储。 3、网页做NLP分词的时候,有些场景下可以省略一些特殊词【比如介词】。如果不省略,会发现这些词几乎出现在了所有网页里。比如【the,的,了】这种。 4、现在各家搜索引擎其实计数差不多,但付出的成本却不一样,比如大家搜索代码的时候google就很好用,而国内很多搜引擎直接把此类数据排除了,就查不到。 5、用户搜索一整句话的时候,很多引擎也是先分词,对每个词做检索,然后merge结果的。 6、其实搜索引擎也在关注用户行为,用户行为也会逐步的影响搜索结果的排序。 对于课后题: 1、对于索引中网页排名的更新,一种直观但效率不高的方式可以是:在算力较为空闲的时期,用Mapreduce做分布式计算,从而更新排名。MAP时可以用网页ID分组,为其指向的不同URL的ID增加评分;Reduce的时候,按网页ID将评分合并,得到本次迭代结果。由于URL数量众多,需要将结果临时存储到HBase中,并解决好并发问题。整个MR迭代完成后,将索引排名更新为新索引排名。 2、实际计算的时候,可以直接用矩阵运算、并行计算的方式提升计算效率。 3、如何判断本次迭代何时结束呢,迭代是不是一定可以收敛呢,这个可以看下马尔科夫链的相关知识。 4、对于新增的网页,用可以塞到Spark中做流式计算,逐步合并到主倒排索引中。 5、对于新闻类网页,可以用同样的方法,单独做一段时间的新闻网页倒排索引。用户查询时,用较高的权重,与主倒排索引查询的结果合并,最终展示给用户

    作者回复: 非常赞

    2022-05-01
    11
  • peter
    请教老师几个问题: Q1:URL长度字段需要两个字节吗?有这么长的URL吗? Q2:峰值同时在线人数这个指标有意义吗? 在“期中测评:IM系统设计中”,有一个指标是“峰值同时在线人数”,这个指标很重要吗?一般都是说并发数量,峰值同时在线人数会占用系统很多资源吗? Q3:网页中哪些单词会被提取? 一个网页会有很多单词,是全部提取吗?还是选择一部分提取?如果是部分提取,那根据什么选词? Q4:百度的关键字提示是哪里处理的? 用百度搜索。输入一个词,会给出很多提示。这个提示是浏览器实现的?还是后端应用服务器实现的? Q5:PageRank是google,那百度用什么? 如果百度也用PageRank算法,算侵权吗? Q6:现在搜索引擎使用AI了吗?

    作者回复: 1 1个字节才256,超过这个长度的URL应该很常见吧,浏览器对URL长度的限制一般在2000以上 2 这个问题是不跟其他专栏串了,我们还没有期中评测呢~~ 不急,会有的~~~ 3 所有单词 4 根据过往用户搜索进行前缀匹配,服务器实现 5 也用pagerank 6 AI这个词太含糊了,pagerank也算是一种AI,Q4的提示也是一种AI,搜索广告推荐也是AI,AI无处不在

    2022-03-09
    5
  • 丫丫
    请问老师,感觉提取倒排索引和page rank是一个很慢的过程,应该是个离线系统。 但是有些时候,会有一个突发新闻比如微博大瓜,新的关键词的搜索量会突然上升,而且网页每时每刻都有更新,请问如何应对? 我们临时去爬这些内容然后构建page rank和倒排索引吗?如何短时间内提高性能

    作者回复: 搜索引擎索引有全量索引和增量索引两种。新闻类网页采用增量索引,爬虫专门爬新闻类网页,爬取频率高,网页数量少,构建索引速度快。其实就是你说的临时的意思,不过这个临时是永不停歇的临时。

    2022-03-16
    3
  • 超大超
    文中指出使用链表方式进行查找交集:“同时遍历两个链表,如果其中一个链表当前指向的元素小于另一个链表当前指向的元素,那么这个链表就继续向前遍历;如果两个链表当前指向的元素相同,该元素就是交集元素,记录在结果列表中;依此继续向前遍历,直到其中一个链表指向自己的尾部 nil。” 有个疑问:两个链表同事向后进行遍历,且比较元素是否相等,这种情况下,如果像上图中指定的哪种的话,无法找到交集元素2. (两个链表中对应位置的元素不相等)

    作者回复: 两个链表指针不是同时移动啊,移动数据小的那个链表指针

    2022-04-24
    1
  • 学员5
    集合求交用跳表那部分,不是先排序吗?排序的时间复杂度是nlogn?

    作者回复: 跳表是一次写入多次读取的,搜索的时候是读取的过程,写入花费时间不需要考虑。

    2022-04-09
    1
  • 一打七
    数据是挨着存放的,知道docID怎么才能快速定位到数据?顺序遍历吗?

    作者回复: 网页在HDFS存储是为了构建索引和计算PageRank,这个过程是顺序遍历的。 根据docID检索网页内容的场景可以用HBase解决。

    2022-04-07
    1
  • aroll
    可通过类似spark这种分布式计算框架进行计算,将海量数据分段迭代计算,再汇总结果,且可对一些计算过程进行缓存,完成快速高效的计算

    作者回复: 对,可以更具体点吗?输入数据的格式是什么样的?如何分段计算?如何汇总?

    2022-03-14
  • Geek_cd0e40
    思考题PageRank 的计算: 1.全量用hadoop mapreduce 2.增量用spark/flink计算,增量索引跟全量合并
    2022-07-10
    2
  • 👽
    这一篇专栏可以说相当硬核,核心知识点: 1. 正,倒排索引,针对网页包含的关键词与关键词对应的网页的映射; 2. 多个集合查找集合的算法设计+海量数据计算的算法设计; 3. PageRank 模型的搭建思路与实际落地的方案; 除了数据模型这块,实在是吸收不了之外,其他的每一个点都让我受益匪浅。
    2022-03-14
    2
收起评论
显示
设置
留言
13
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部