14第一讲商用搜索引擎的架构与原理分布式搜索

1、1分布式搜索引擎v 并行抓取策略v 分布式v 分布式索引v 分布式检索分布式搜索引擎的v 分布的信息的获取、计算和数据统一§ 爬虫/或者相应的数据获取机制的分布§ 对信息进行的统一处理v 数据处理后的分布式和管理§ 文件（索引）的准确定位§ 更新（增加、删除、移制v 前端搜索服务的分布§ 处理大规模并发请求时的分发机制搜索引擎的结构与组成网 页预处理 文 档 建立倒 倒排索引抓 取分 词 服务器 排索引 排序检索服务器（分析、结果融合）搜索引擎是一个海量的数据系统v 如何实现？§ 一台超级计算机实现§ 多台普通计算机组成一个

2、集群v 分布式集群系统§ 节约成本§ 扩展性强§ 高容错性搜索引擎技术基础主讲：清http /内容提要搜索引擎的前世今生搜索引擎结构与组成搜索引擎质量评估搜索引擎排序策略分布式搜索引擎2文档服务器文档服务器DocID ->字段->内容Doc1 ->field1->content->field2->content->field3->content Doc2 ->field1->content->field2->content->field3->content Doc3 ->fi

3、eld1->content->field2->content->field3->content索引和文档存放索引和文档存放Index ServersDocuments ServersAd ServerSpell CheckerWeb Server分布式搜索引擎v 并行抓取策略v 分布式v 分布式索引v 分布式检索并行抓取v 动态策略§ 利用一台URL Server作为URL的提供者§ 动态地将URL列表分发到每个Crawler上v 静态策略§ 将URL按照既定的策略分配到某台上 按站点方式 URL Hash方式 Site Hash方式

4、 Hierarchical方式并行抓取v 优点§ 可扩展性§ 的负载均衡§ 减少流量 压缩、去重、获取统计量v§ 重复抓取§ 分布环境下的质量§ 需要额外的通信带宽来进行同步3分布式搜索引擎v 并行抓取策略v 分布式v 分布式索引v 分布式检索分布式v 需要考虑§ 分发§ 节点的物理结构§ 更新策略v 可能的选择：§ hash、log、hashed-log文档服务器中缓存的作用客户端端将结果返DocID缓存命中回客户端直接返回缓存服务器内容contentDocID->Content将结果加

5、入缓存未命中缓存检索文档服务器文档服务器对索引服务器实施缓存客户端如果命中户端直接返回Term (DocID)缓存服务器没有命中进行搜索Term->DocIDDocIDTermTerm->DocID索引服务器将结果加入缓存并返回给客户端文档服务器缓存机制如果命中缓存则直接返回服务器检索器缓存（存放次 数多的数据）文档服务器的分布式处理主节点DocID ->位置Doc1 ->Node1 Doc2 ->Node2 Doc3 ->Node3 Doc4 ->Node1 Node1 Node2 Node3Doc1 ->field1->content-

6、>field2->content Doc2 ->field1->content Doc3 ->field1->contentDoc4 ->field1->content->field2->content->field2->content->field2->content4-分布式搜索引擎v 并行抓取策略v 分布式v 分布式索引v 分布式检索Term-Document视图分布式索引v 本地倒排§ 按照doc分配所有的(term,doc)信息§ 优缺点是什么？v 全局倒排§ 按照ter

7、m分配所有的(term, doc)信息§ 优缺点是什么？检索过程-内存硬盘Number of DocIDDocIDScoreDocIDScore-DocIDScoreNumber of DocID文件2文件1-文件1起始位置1003文件2起始位置365Term1Term2内存中词典的逻辑结构索引项指针项-文件名起始位置Term2文件名起始位置Term1倒排所索引的逻辑结构索引项倒排表-DocIDScoreDocIDScoreTerm2DocIDScoreDocIDScoreTerm15分布式元搜索引擎Node4分词生成倒排表倒排表内容： Term->DocID b->D4

8、Node3分词生成倒排表倒排表内容： Term->DocID a->D3b->D3 c ->D3Node2分词生成倒排表倒排表内容： Term->DocID a->D2d->D2 e->D2Node1分词生成倒排表倒排表内容： Term->DocID a->D1b->D1 c->D1 d->D1M（主节点）分布式元搜索引擎DocIDTermD1a b a c dD2a d e aD3b c a bD4b分布式元搜索引擎主节点M索引服务器索引服务器索引服务器索引服务器Node1Node2Node3Node4分布式搜索引

9、擎分类v 分布式元搜索引擎v 散列式分布搜索引擎v P2P分布搜索引擎v 局部遍历型搜索引擎分布式检索架构图1. 提交2.分析 3. 检索 4. 结果返回 5. 结果合并服务器Q3R2R1R3Q2Q1分布式检索架构图QueryServer索引QueryUserAdvancedServer索引InterfaceServer用户索引Query Server6改进：加入Fancy List-减少通信流量v 可以改进主节点的性能，减轻v 无法减少通信流量§ 无论如何改进主节点、子节点与任务分配器， 对索引服务器的次数并没有减少§ 如何改进？改进：加入任务分配器-减轻主节点v 任务分

10、配策略§ 按搜分配§ 按用户分配Node1Node2Node3Node4子节点C2子节点C1任务分配器BrokerM分布式元搜索的特点v 优点§ 结构简单§ 强健壮性，任何一个单元可以被随时摘掉并不影响太大，出现“搜不到”，只会出现“结果变少”v 缺点§ 主节点大，无法应对大规模并发、抗压能力差§ 多台服务器同时检索，带来巨大的通信流量§ 扩展能力有一定限制，适合小型和中型的搜索引擎分布式元搜索引擎的功能分布客户端数据源检索服务器接收新文档分词生成倒排文件检索服务器接收新文档分词生成倒排文件检索服务器接收新文档分词生成倒排文

11、件检索服务器接收新文档分词生成倒排文件检索主节点文档分配器向所有检索服务 器进行广播，检 索，并撮合结果。将文档按DocID 平均分配给检索服务器。分布式元搜索的检索过程输入：a AND cNode4倒排表内容： Term->DocID b->D4Node3倒排表内容： Term->DocID a->D3b->D3 c ->D3Node2倒排表内容： Term->DocID a->D2d->D2 e ->D2Node1倒排表内容： Term->DocID a->D1b->D1 c ->D1 d->D1主节

12、点M第一遍搜索：a 经过节点 1 2 3 4结果：D1 D2 D3第二遍搜索：c 经过节点 1 2 3 4 结果：D1 D3进行交集运算结果: D1 D3 Node1、2、3、4均被检索2次7功能分布客户端数据源检索服务器-3接收新Term 生成倒排文件c->D1,D2,D3检索服务器-2接收新Term 生成倒排文件b->D1,D3,D4检索服务器-4接收新Term 生成倒排文件d->D1,D2检索服务器-1接收新Term 生成倒排文件a->D1,D2,D3文档器分词检索Term所在位置分配DocID到检索服务器词 典Term->索引服务器a->Node1

13、b->Node2 c->Node3 d->Node4检索节点检索Term所在的位置，到检索服务器检索，撮合结果散列式分布式搜索Node1Node2Node3Node4倒排表内容：Term->DocID倒排表内容：Term->DocID倒排表内容：Term->DocID倒排表内容：Term->DocIDa->D1,D2,D3b->D1,D3,D4c ->D1,D2,D3d->D1,D2M（主节点）散列式分布式搜索正排表倒排表TermDocIDaD1 D2 D3bD1 D3 D4cD1 D2 D3dD1 D2DocIDTermD1a

14、 b a c dD2a d c aD3b c a bD4b散列式分布式搜索v 根据Term对索引服务器和文档服务器进行散列v 对任何的索引词准确地定位到具体的索引服务器， 从而定位到正确的文档服务器分布式搜索引擎分类v 分布式元搜索引擎v 散列式分布搜索引擎v P2P分布搜索引擎v 局部遍历型搜索引擎改进效果v 通过Fancy List可以少一些倒排表，而且读出的都是有价值的v§ 当索引服务器的数量非常大时，流量还是巨大的§ 无法根本解决，这是元搜索引擎的本质决定的8改进：词典备份客户端数据源v 文档器：新文档无法v 检索节点：无法提供检索服务文档器词典缓存Ter索引器a-

15、>No b->Noc->3d->N de4词 典Term->索引服务器a->Node1 b->Node2 c->Node3 d->Node4检索节点词典 存Te器a->N b->Nc- 3d- >N de4改进：词典备份v 词典的解决§ 词典备份 可以提高健壮性 多节点间词典的同步改进：词典备份新词的传递方向文档器词典缓存Term->索引服务器a->Node1b->Node2 c->Node3 d->Node4词 典Term->索引服务器a->Node1 b->No

16、de2 c->Node3 d->Node4检索节点词典缓存Term->索引服务器a->Node1 b->Node2 c->Node3 d->Node4改进：词典备份客户端数据源文档器词典缓存Term->索引服务器a->Node1b->Node2 c->Node3 d->Node4词 典Te务器a->N b->Nc- >d- > de4检索节点词典缓存Term->索引服务器a->Node1 b->Node2 c->Node3 d->Node4散列式分布式搜索v 优点

17、67; 设计简单§ 抗压能力强v 缺点§ 对于单个索引服务器或者文档服务器的容量等动态调整较§ 性差 如果某台索引服务器，必然会有“一部分词（Term）搜不到了” 如果存放词典的服务器，只能绕过词典，将搜广播到所有服务器，使通信突然升高检索过程a AND dNode3c->D1,D2,D3Node2b->D1,D3,D4Node4d->D1,D2Node1a->D1,D2,D3检索节点得到检索结果a->D1,D2,D3 d->D1,D2两者做与运算结果为： D1,D2结果返回给用户接收a和d到词典其所在位置a到Node1d到No

18、de4结果a->D1,D2,D3 d->D1,D2词 典Term->索引服务器a->Node1 b->Node2 c->Node3 d->Node49散列式分布式搜索的特点v 优点§ 搜索一个词时，不必所有索引服务器都激活§ 如果用户输入的词平均3-5个，那么同时提供服务的索引服务器超过5个v 缺点§ 提供热门词的索引服务器大，如何解决？ 缓存策略§ 如果某台索引服务器，必然会有“一部分词（Term）搜不到了，如何解决？ 备份 混合索引改进：直接取余、取消词典客户端数据源检索服务器-2接收新Term 生成倒排文件

19、检索服务器-4接收新Term 生成倒排文件检索服务器-3接收新Term 生成倒排文件检索服务器-1接收新Term 生成倒排文件位置=hash(Term)MOD 4改进：直接取余、取消词典v 直接取余，取消词典 Term通过Hash算法转换成一个整数M POS（索引节点位置）=M mod N(节点数)改进：检索与索引节点功能与直接同步客户端数据源文档器词 典检索功能（检索节点的）索引功能检索节点词 典索引功能（文档器的）检索功能改进：检索与索引节点功能与直接同步客户端数据源文档器词 典检索功能（检索节点的）索引功能检索节点词 典索引功能（文档器的）检索功能改进：检索与索引节点功能与直接同步客户端

20、数据源直接同步文档器词 典检索功能（检索节点的）索引功能检索节点词 典索引功能（文档器的）检索功能10局部遍历型搜索引擎网 球足 球篮 球体育用品运动体育体 育教 育军 事科 技分布式搜索引擎分类v 分布式元搜索引擎v 散列式分布搜索引擎v P2P分布搜索引擎v 局部遍历型搜索引擎P2P分布式搜索DHT在P2P检索系统中的位置分布式搜索引擎分类v 分布式元搜索引擎v 散列式分布搜索引擎v P2P分布搜索引擎v 局部遍历型搜索引擎混合式搜索引擎v 综合分布式元搜索和散列分布式搜索的特点§ 限制每个节点倒排表的长度§ 兼顾了系统的健壮性，又可以使节点的激活率保持在一个较低的水平

21、v 举例：§ “根叔”的倒排索引表很长§ 分布在多个节点其他a AND dNode3c->D1,D2,D3Node4d->D1,D2Node2b->D1,D3,D4Node1a->D1,D2,D3检索节点得到检索结果a->D1,D2,D3 d->D1,D2两者做与运算结果为： D1,D2结果返回给用户接收a和d到词典其所在位置a到Node1d到Node4结果a->D1,D2,D3 d->D1,D2词 典Term->索引服务器a->Node1 b->Node2 c->Node3 d->Node411

22、参考文献Arasu 2001Searching the WebBrin 1998 8The anatomy of a large-scale hypertextual web search engine Brode 2000.11Graph structure in the webDean 1999.22Finding related pages in the World Wide Web Kleinberg 1999 38Authoritative Sources in a Hyperlinked EnvironmentCho 2001Crawling the Web: Discovery and Maintenance of Large