信息检索第8章-并行以及分布式信息检索

第八章并行与分布式信息检索第八章并行与分布式信息检索§8.1.并行计算§82分布式系统§8.2.分布式系统§8.3.并行检索§8.4.分布式检索§85索引分割§8.5.索引分割§8.6.并行与分布式检索§8.1.并行计算§并行计算并行计算：用多个处理器去求解单个问并行计算：用多个处理器去求解单个问题，把单个大问题分解成若干“部分”,每个“部分”采用单个处理器去解决并行计算通过“以成本换时间”的方式并行计算通过以成本换时间的方式来减少求解问题的总时间。总时间取决于时间最长的那个“部分”问题的求解通过并行计算系统具有较好的可伸缩通过并行计算，系统具有较好的可伸缩性§8.1.并行计算并行体系结构：可以将多处理器进行不同组§并行计算并行体系结构：可以将多处理器进行不同组合构成并行体系结构。按照指令(Itti)流和数据(Dt)流的数按照指令(Instruction)流和数据(Data)流的数目，Flynn将并行体系结构分成四类：SISD：单指令流单数据流，如传统的冯.诺依曼计算机依曼计算机SIMD：单指令流多数据流，N个处理器，N个数据流但是多个处理器执行相同的操N个数据流，但是多个处理器执行相同的操作。§8.1.并行计算MISD：多指令流单数据流，N个处理器处§并行计算理共享内存中的单数据流，每个处理器的操作不同，目前MISD结构已经非常少见。MIMD：多指令流多数据流，N个处理器，N个数据流每个处理器处理自己的操作N个数据流，每个处理器处理自己的操作。多处理器可以处理不同任务或者协同处理单个任务前最最流行单个任务。MIMD是目前最通用和最流行的一类并行体系结构。处理器之间交互(通(信)频繁的MIMD系统称为紧耦合系统，反之称为松耦合系统之称为松耦合系统。§8.1.并行计算SISD：结构只有一个处理器，执行一个单一§并行计算SISD：结构只有个处理器，执行个单指令流，操作单一存储器上的数据。对应冯诺依曼结构对应冯.诺依曼结构§8.1.并行计算SIMD：多个处理执行相同的指令，多个数据§并行计算流§8.1.并行计算MISD：多指令流单数据流，N个处理器处理§并行计算MISD：多指令流单数据流，N个处理器处理共享内存中的单数据流，每个处理器的操作不同目前MISD结构已经非常少见不同，目前MISD结构已经非常少见。§8.1.并行计算MIMD：多指令流多数据流，N个处理器，N个§并行计算数据流，每个处理器处理自己的操作。多处理器可以处理不同任务或者协同处理单个任务。器可以处理不同任务或者协同处理单个任务。第八章并行与分布式信息检索第八章并行与分布式信息检索§8.1.并行计算§82分布式系统§8.2.分布式系统§8.3.并行检索§8.4.分布式检索§85索引分割§8.5.索引分割§8.6.并行与分布式检索§8.2.分布式系统Adistributedsystemisoneinwhichcomponents§分布式系统yplocatedatnetworkedcomputerscommunicateandcoordinatetheiractionsonlybypassingmessagescoordinatetheiractionsonlybypassingmessages分布式计算：通过局域网或者广域网将多台计算机连接起来协同处理一个问题机连接起来，协同处理个问题。分布式结构可以看成MIMD并行结构的一个松耦合特例合特例。分布式计算程序是粗粒度的(计算量大通信少)，而并行计算程序是细粒度的(计算量小通信大)。所谓“大小”都只具相对意义。§8.2.分布式系统系统拥有多种通用的物理和逻辑资源，可以动§分布式系统系统拥有多种通用的物理和逻辑资源，可以动态的分配任务，分散的物理和逻辑资源通过计算机网络实现信息交换系统中存在一个以全算机网络实现信息交换。系统中存在一个以全局的方式管理计算机资源的分布式操作系统。分布式系统只有一个模型或范型。在操作系统之上有一层软件中间件(Middleware)负责实现之上有层软件中间件()负责实现这个模型。万维网(WorldWideWeb)是分布式系统在中所有一切看起来好像是一系统，在中，所有一切看起来好像是一个文档(Web页面)一样。§8.2.分布式系统在计算机网络中，不存在这种统一性、模型以及§分布式系统在计算机中不存在种统性模以及其中的软件。用户看到的是实际的机器，计算机网络并没有使这些机器看起来是统一的。如果这网络并没有使这些机器看起来是统的。如果这些机器有不同的硬件或者不同的操作系统，这些差异是完全可见的如果希望在一台远程机器上差异是完全可见的。如果希望在台远程机器上运行一个程序，必须登陆到远程机器上，在那台机器上运行该程序机器上运行该程序。多数分布式系统是建立在计算机网络之上的，所以分布式系统与计算机网络在物理结构上是基本相同的。§8.2.分布式系统区别在于：分布式操作系统的设计思想和网络§分布式系统区别在于：分布式操作系统的设计思想和网络操作系统是不同的，这决定了他们在结构、工作方式和功能上也不同网络操作系统要求网作方式和功能上也不同。网络操作系统要求网络用户在使用网络资源时首先必须了解网络资源网络用户必须知道网络中各个计算机的功源，网络用户必须知道网络中各个计算机的功能与配置、软件资源、网络文件结构等情况，在网络中如果用户要读一个共享文件时，用户必须知道这个文件放在哪一台计算机的哪一个须知个文件放在哪台计算机哪个目录下。§8.2.分布式系统分布式操作系统是以全局方式管理系统资源的§分布式系统分布式操作系统是以全局方式管理系统资源的,可以为用户任意调度网络资源，并且调度过程是“透明”的当用户提交个作业时分布是“透明”的。当用户提交一个作业时，分布式操作系统能够根据需要在系统中选择最合适的处理器，将用户的作业提交到该处理程序，在处理器完成作业后，将结果传给用户。在这传个过程中，用户并不会意识到有多个处理器的存在，这个系统就像是一个处理器一样。存在，这个系统就像是个处理器样。§8.2.分布式系统分布式日志收集系统：FacebookScribe§分布式系统分布式收集系统在facebook内部已经得到大量的应用。Scribe是基于一个使用非阻断C++服务器的Scribe是基于个使用非阻断C++服务器的thrift服务的实现。它能够从各种日志源上收集日志存储到一个中央存储系统(可以是集日志，存储到个中央存储系统(可以是NFS，分布式文件系统等)上，以便于进行集中统计分析处理为日志的“分布式收集中统计分析处理。为日志的“分布式收集，统一处理”提供了一个可扩展的，高容错的方案。§8.2.分布式系统Scribe部署结构§分布式系统部署结构第八章并行与分布式信息检索第八章并行与分布式信息检索§8.1.并行计算§82分布式系统§8.2.分布式系统§8.3.并行检索§8.4.分布式检索§85索引分割§8.5.索引分割§8.6.并行与分布式检索§8.3.并行检索一般检索过程§并行检索检并行检索§8.3.并行检索将“信息检索”拆分成三个子查询同时进行处§并行检索将“信息检索”拆分成三个子查询同时进行处理，然后合并。不进行查询拆分，但是对每个搜索程序只搜索部分数据集(类似于元搜索)，然后合并。索部分数据集(类似于元搜索)，然后合并。查询的拆分在应用层着实不易，现在的操作系统应该实现了这种意义上的并行。后一种方法更加普遍，这是应用程序要做的后种方法更加普遍，这是应用程序要做的工作，需要进行数据分割。第八章并行与分布式信息检索第八章并行与分布式信息检索§8.1.并行计算§82分布式系统§8.2.分布式系统§8.3.并行检索§8.4.分布式检索§85索引分割§8.5.索引分割§8.6.并行与分布式检索§8.4.分布式检索§分布式检索分布式信息检索架构§8.4.分布式检索分布式信息检索将更大范围分布的异构数据§分布式检索联合起来，形成一个逻辑整体，为用户提供强大的信息检索能力强大的信息检索能力。§8.4.分布式检索分布的信息获取、计算和数据统一§分布式检索分布的信息获取、计算和数据统爬虫/数据获取机制的分布对信息进行加工的统一处理数据处理后的分布式存储和管理数据处理后的分布式存储和管理文件（包括索引）的准确定位更新增加删除移动机制更新（增加、删除、移动）机制前端搜索服务的分布前端搜索服务的分布处理大规模并发请求时的分发机制§8.4.分布式检索分类§分布式检索分类分布式元搜索分布式元搜索散列分布搜索搜索Peer2Peer搜索局部遍历型搜索局部遍历型搜索§8.4.分布式检索分布式元搜索§分布式检索分布式元搜索拥有多个单个的搜索引擎，中心搜索拥有多个单个的搜索引擎，中搜索引擎是利用这些分布的单个搜索引擎的结果进行合并得到完整的结果的结果进行合并得到完整的结果。每个搜索服务器存放部分索引，组合起来形成完整的索引。索引分割：按文档进行分割索引分割：按文档进行分割。§8.4.分布式检索§分布式检索分布式元搜索引擎§8.4.分布式检索§分布式检索分布式元搜索引擎§8.4.分布式检索§分布式检索分布式元搜索的检索过程§8.4.分布式检索§分布式检索分布式元搜索引擎的功能分布§8.4.分布式检索分布式元搜索优点§分布式检索优点：设计简单，快速。强健壮性任何个单元可以被随时摘掉并不影强健壮性，任何一个单元可以被随时摘掉并不影响太大，不会出现“搜不到”，只会出现“结果变少”变少”缺点：主节点压力大无法应对大规模并发抗压能力主节点压力大，无法应对大规模并发、抗压能力差多台服务器同时检索，带来巨大的网络通信流量多台服务器同时检索，带来巨大的网络通信流量扩展能力有一定限制，适合小型和中型的搜索引擎擎§8.4.分布式检索分布式元搜索§分布式检索改进：加入任务分配器-减轻主节点压力§8.4.分布式检索问题：可以改进主节点的性能减轻压力§分布式检索可以改进主节点的性能，减轻压力无法减少网络通信流量无论如何改进主节点、子节点与任务分配器，对索引服务器的访问次数并没有减少改进：加入FancyList-减少通信流量§8.4.分布式检索§分布式检索通过FancyList可以少读取一些倒排表，而且读出的都是有价值的且读出的都是有价值的问题当索引服务器的数量非常大时网络流当索引服务器的数量非常大时，网络流量还是巨大的无法根本解决这是元搜索引擎的本质无法根本解决，这是元搜索引擎的本质决定的§8.4.分布式检索散列分布搜索结构和分布式元搜索相似个中心搜索引§分布式检索结构和分布式元搜索相似，一个中心搜索引擎对应多个子搜索引擎。与分布式元搜索不同，实现了索引搜索的分布式。如“中国北京”分词后为“中国”、“北京”使用哈希，hash(中国)=0；hash(北京)=1使用哈希，as(中国)0；as(北京)将“中国”、“北京”发往不同的子检索服务器建立索引务器建立索引。查询时，对查询分词后，发往对应的子检索服务器进行检索服务器进行检索。§8.4.分布式检索散分布搜索§分布式检索散列分布搜索根据Query对索引服务器和文档服务器进行Qy散列做到对于任何的索引词能够准确的定位到做到对于任何的索引词能够准确的定位到具体的索引服务器并从而定位到正确的文档服务器档服务器。通过哈希函数实现索引的分割。§8.4.分布式检索散列分布搜索§分布式检索散列分布搜索§8.4.分布式检索散列分布搜索——功能分布§分布式检索散列分布搜索功能分布§8.4.分布式检索散列分布检索过程§分布式检索散列分布检索过程§8.4.分布式检索散列分布搜索优点抗压能力强设计简单§分布式检索优点：抗压能力强，设计简单。缺点：对于单个索引服务器或者文档服务器的容量等动态的调整较困难。稳定性差如果某台索引服务器崩溃