对用于分布式抓取的搜索空间进行分区的方法和装置

摘要

本发明涉及一种对用于分布式抓取的搜索空间进行分区的方法和装置。用于对抓取空间进行分区的计算机实现的过程的一个示例性实施例包括：计算事件集合中的每个事件的事件标识符以形成标识后的事件集合；将所述标识后的事件集合划分成多个分区；为节点集合中的每个节点分配一个分区；以及由相应节点执行每个分配的分区中的每个事件。响应于判定发现新状态，向其它节点通知所述新状态，其中将与所述新状态关联的信息添加到每个节点处的相应分配的事件ID集合。响应于判定不存在更多通知，所述计算机实现的过程判定是否存在更多待处理事件，以及响应于判定不存在更多待处理事件，所述计算机实现的过程终止。

说明书

技术领域

本公开一般地涉及在数据处理系统中索引Web页面，更具体地说，涉 及在数据处理系统中对用于分布式抓取的抓取空间进行分区。

背景技术

近二十年来，Web应用的分布式抓取已经成为广泛研究的主题[Web  Crawling（Web抓取），2010年，作者：Christopher Olston和Marc Najork]。 但是，典型的建议解决方案集中于常规或非AJAX应用的抓取[UbiCrawler: a scalable fully distributed Web crawler（UbiCrawler：可扩展的完全分布 式Web抓取器），2003年1月27日，Paolo Boldi、Bruno Codenotti、 Massimo Santini、Sebastiano Vigna；以及Distributed Web Crawling over  DHTs（通过DHT的分布式Web抓取），2004年，Boon Thau Loo、Owen  Cooper、Sailesh Krishnamurthy]。术语AJAX的使用表示基于Web的技 术的集合。所述技术的各实施例用于实现Web应用，这些Web应用能够 在后台与服务器通信，同时不干扰Web页面的当前状态。AJAX实现通常 包括技术组合，包括具有用于呈现用途的级联样式表的超文本标记语言 （HTML）或可扩展超文本标记语言（XHTML）、用于动态显示数据和 与数据的交互的文档对象模型（DOM）、用于数据定义和交换的可扩展标 记语言（XML）以及用于数据交换的可扩展标记语言（XML）、用于数 据转换的可扩展样式表语言转换（XSLT）、提供异步通信能力的可扩展 标记语言超文本传输协议请求（XMLHttpRequest）对象，以及提供用于 组合各技术的胶水（glue）语言的JavaScript。

在非AJAX应用中，在文档对象模型（DOM）的状态和对应的统一 资源定位符（URL）之间存在一对一对应。因此，传统的抓取器通常使用 主要利用URL的矩阵对搜索空间进行分区[Design and Implementation of  a High-Performance Distributed Web Crawler（高性能分布式Web抓取器 的设计和实现），2002年，Vladislav Shkapenyuk、Torsten Suel]。使用 所述框架，每个抓取器负责一组特定的URL，其中特定的抓取器负责转到 原始URL，并获得有关使用原始URL定位的新URL的信息。当新发现 的URL落入分配给另一个抓取器节点的URL集合时，第一节点与第二节 点通信，以便向第二节点通知由第一节点新发现的URL。

随着交互式和基于AJAX的JavaScript库的使用增加，支持AJAX的 富互联网应用（RIA）的数量迅速增加。在RIA型应用中，在DOM的状 态和URL之间不像在非AJAX应用中那样存在一对一对应。因此，传统 抓取器中使用的技术通常在此类应用中不能工作或不能很好地工作。例如， 抓取器不能仅通过发送URL到达所有状态，搜索空间的分区也不能继续 基于URL。

当处理RIA型应用时，需要抓取器以执行事件以便物化新页面，这与 典型的传统应用形成对照，在传统应用中，抓取器可以简单地查看目的地 URL并标识负责该URL的节点。此外，当处理非AJAX应用时，到达传 统Web站点中的页面的成本通常不变，因为在任何点处，抓取器可以简单 地跳转到具有该URL的任何页面。但是，当处理RIA时成本有所变化， 因为要到达某一状态，通常执行一系列事件，其后通常产生增加的可变成 本。对于与覆盖范围和覆盖范围时效性关联的抓取器性能矩阵，与抓取 Web页面关联的成本函数是一个重要因素。

发明内容

根据一个实施例，一种用于对抓取空间进行分区的计算机实现的过程 包括：计算事件集合中的每个事件的事件标识符以形成标识后的事件集合； 将所述标识后的事件集合划分成多个分区；为节点集合中的每个节点分配 一个分区，以便由相应节点执行每个分配的分区中的每个事件。响应于判 定发现新状态，向其它节点通知所述新状态，其中将与所述新状态关联的 信息添加到每个节点处的相应分配的事件ID集合。响应于判定不存在更 多通知，所述计算机实现的过程判定是否存在更多待处理事件，以及响应 于判定不存在更多待处理事件，所述计算机实现的过程终止。

根据另一个实施例，一种用于对抓取空间进行分区的计算机程序产品 包括计算机可读型存储介质，所述介质包含在其上存储的计算机可执行程 序代码。所述计算机可执行程序代码包括：用于计算事件集合中的每个事 件的事件标识符以形成标识后的事件集合的计算机可执行程序代码；用于 将所述标识后的事件集合划分成多个分区的计算机可执行程序代码；用于 为节点集合中的每个节点分配一个分区的计算机可执行程序代码；用于由 相应节点执行每个分配的分区中的每个事件的计算机可执行程序代码；用 于判定是否发现新状态的计算机可执行程序代码；响应于判定发现所述新 状态，用于向其它节点通知所述新状态的计算机可执行程序代码；用于将 与所述新状态关联的信息添加到每个节点处的相应分配的事件ID集合的 计算机可执行程序代码；用于判定是否存在更多的通知的计算机可执行程 序代码；响应于判定不存在更多的通知，用于判定是否存在更多的待处理 事件的计算机可执行程序代码；以及响应于判定不存在更多的待处理事件， 用于终止的计算机可执行程序代码。

根据另一个实施例，一种用于对抓取空间进行分区的装置包括：通信 光纤通道网络；与所述通信光纤通道网络相连的存储器，其中所述存储器 包含计算机可执行程序代码；与所述通信光纤通道网络相连的通信单元； 与所述通信光纤通道网络相连的输入/输出单元；与所述通信光纤通道网络 相连的显示器；以及与所述通信光纤通道网络相连的处理器单元。所述处 理器单元执行所述计算机可执行程序代码以引导所述装置执行以下操作： 计算事件集合中的每个事件的事件标识符以形成标识后的事件集合；将所 述标识后的事件集合划分成多个分区；为节点集合中的每个节点分配一个 分区；由相应节点执行每个分配的分区中的每个事件；判定是否发现新状 态；以及响应于判定发现新状态，向其它节点通知所述新状态。所述处理 器单元还执行所述计算机可执行程序代码以引导所述装置执行以下操作： 将与所述新状态关联的信息添加到每个节点处的相应分配的事件ID集合； 判定是否存在更多通知；响应于判定不存在更多通知，判定是否存在更多 待处理事件；以及响应于判定不存在更多待处理事件而终止。

附图说明

为了更全面地理解本发明，现在结合附图和具体实施方式参考下面的 简单描述，其中相同的参考标号表示相同的部件，这些附图是：

图1是可操作以用于本公开的各实施例的示例性网络数据处理系统的 框图；

图2是可操作以用于本公开的各实施例的示例性数据处理系统的框 图；

图3是可操作以用于本公开的各实施例的分区系统的框图；

图4是可操作以用于本公开的各实施例的图3的分区系统中的数据流 的框图；

图5是根据本公开的一个实施例的图3的分区系统中使用的过程的流 程图；

图6是跨可操作以用于本公开的各实施例的图3的分区系统中的所有 节点使用的过程的流程图；以及

图7提供在可操作以用于本公开的各实施例的图3的分区系统的备选 模式中使用的过程的流程图。

具体实施方式

尽管下面提供了一个或多个实施例的示例性实现，但是所公开的系统 和/或方法可以使用任意多种技术实现。本发明不应被限于下面示出的示例 性实现、附图和技术，其中包括此处示出的示例性设计和实现，而是可以 在所附权利要求及其完整范围等价物的范围内进行修改。

所属技术领域的技术人员知道，本发明的各方面可以实现为系统、方 法或计算机程序产品。因此，本发明的各方面可以具体实现为以下形式， 即：完全的硬件实施方式、完全的软件实施方式（包括固件、驻留软件、 微代码等），或硬件和软件方面结合的实施方式，这里可以统称为“电路”、 “模块”或“系统”。此外，本发明的各方面还可以实现为在一个或多个 计算机可读介质中的计算机程序产品的形式，该计算机可读介质中包含计 算机可读的程序代码。

可以采用一个或多个计算机可读数据存储介质的任意组合。计算机可 读数据存储介质例如可以是—但不限于—电、磁、光、或半导体的系统、 装置或器件，或者任意以上的组合。计算机可读数据存储介质的更具体的 例子（非穷举的列表）包括：便携式计算机盘、硬盘、随机存取存储器 （RAM）、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪 存)、便携式紧凑盘只读存储器(CD-ROM)、光存储设备或者磁存储设备、 或者上述的任意合适的组合。在本文件中，计算机可读数据存储介质可以 是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或 者器件使用或者与其结合使用。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的 数据信号，其中承载了计算机可读的程序代码。这种传播的信号可以采用 多种形式，包括—但不限于—电磁信号、光信号或上述的任意合适的组合。 计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可 读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、 装置或者器件使用或者与其结合使用的程序。

计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括 —但不限于—无线、有线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言的任意组合来编写用于执行本发明的 各方面操作的计算机程序代码，所述程序设计语言包括面向对象的程序设 计语言—诸如Smalltalk、C++等，还包括常规的过程式程序设计 语言—诸如“C”语言或类似的程序设计语言。Java和所有基于Java的商 标和图标都为Oracle和/或其关联公司在美国、其它国家或者美国以及其 它国家的商标。程序代码可以完全地在用户计算机上执行、部分地在用户 计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在 远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程 计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN) 或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机（例 如利用因特网服务提供商来通过因特网连接）。

下面将参照根据本发明实施例的方法、装置（系统）和计算机程序产 品的流程图和/或框图描述本发明的各方面。应当理解，流程图和/或框图 的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机程序指 令实现。

这些计算机程序指令可以提供给通用计算机、专用计算机或其它可编 程数据处理装置的处理器，从而生产出一种机器，使得这些计算机程序指 令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现 流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。

也可以把这些计算机程序指令存储在计算机可读介质中，这些指令使 得计算机或其它可编程数据处理装置以特定方式工作，从而，存储在计算 机可读介质中的指令就产生出包括实现流程图和/或框图中的一个或多个 方框中规定的功能/动作的指令的制造品（article of manufacturer）。

也可以把计算机程序指令加载到计算机或其它可编程数据处理装置 上，使得在计算机或其它可编程数据处理装置上执行一系列操作步骤，以 产生计算机实现的过程，从而使得在计算机或其它可编程装置上执行的指 令能够提供实现流程图和/或框图中的一个或多个方框中规定的功能/动作 的过程。

现在参考附图，具体参考图1-2，提供了其中可实现示例性实施例的 数据处理环境的示例性图。应该理解，图1-2仅作为示例，并非旨在断言 或暗示对其中可以实现不同实施例的环境的任何限制。可做出对所示环境 的许多修改。

图1示出其中可实现对抓取空间进行分区的示例性实施例的网络数据 处理系统的图形表示。网络数据处理系统100是其中可实现示例性实施例 的计算机的网络。网络数据处理系统100包含网络102，该网络是用于提 供在网络数据处理系统100内连接在一起的各种设备与计算机之间的通信 链路的介质。网络102可以包括诸如有线、无线通信链路或光缆之类的连 接。

在所示实例中，服务器104和服务器106连同存储单元108一起与网 络102相连。此外，客户机110、112和114与网络102相连。客户机110、 112和114例如可以是个人计算机或网络计算机。在所示实例中，服务器 104将诸如引导文件、操作系统映像及应用之类的数据提供给客户机110、 112和114。客户机110、112和114在该实例中是服务器104的客户机。 网络数据处理系统100可以包括其它服务器、客户机以及未示出的其它设 备。

在所示实例中，网络数据处理系统100是因特网，同时网络102代表 全球范围内使用传输控制协议/网际协议（TCP/IP）协议集来相互通信的 网络和网关的集合。在因特网的核心是主节点或主机之间的高速数据通信 线路的主干，它包括数以千计的商业、政府、教育以及其它路由数据和消 息的计算机系统。当然，网络数据处理系统100也可以实现为许多不同类 型的网络，例如内联网、局域网（LAN）或广域网（WAN）。图1旨在 作为一个实例，并非旨在作为对不同示例性实施例的体系结构限制。

参考图2，提供了可操作以用于本公开的对抓取空间进行分区的各实 施例的示例性数据处理系统的框图。在该示例性实例中，数据处理系统 200包括通信光纤通道网络（fabric）202，其在处理器单元204、存储器 206、永久性存储装置208、通信单元210、输入/输出（I/O）单元212和 显示器214之间提供通信。

处理器单元204用于执行可以被载入存储器206的软件的指令。处理 器单元204可以是包含一个或多个处理器的集合或者可以是多处理器核 心，具体取决于特定实现。进一步，处理器单元204可以使用一个或多个 异构处理器系统来实现，其中在单个芯片上同时存在主处理器与辅助处理 器。作为另一个示例性实例，处理器单元204可以是包含同一类型的多个 处理器的对称多处理器系统。

存储器206和永久性存储装置208是存储设备216的实例。存储设备 是任何能够存储信息的硬件，所述信息例如包括但不限于数据、功能形式 的程序代码和/或其它合适的临时性和/或持久性信息。在这些实例中，存 储器206例如可以是随机存取存储器或任何其它合适的易失性或非易失性 存储设备。永久性存储装置208可以采取各种形式，具体取决于特定实现。 例如，永久性存储装置208可以包含一个或多个组件或设备。例如，永久 性存储装置208可以是硬盘驱动器、闪存、可重写光盘、可重写磁带或上 述各项的某种组合。永久性存储装置208使用的介质也可以是移动的。例 如，可移动硬盘驱动器可以用于永久性存储装置208。

在这些实例中，通信单元210提供与其它数据处理系统或设备的通信。 在这些实例中，通信单元210是网络接口卡。通信单元210可以通过使用 物理和无线通信链路两者之一或全部来提供通信。

输入/输出单元212允许使用其它可以连接到数据处理系统200的设备 来输入和输出数据。例如，输入/输出单元212可以通过键盘、鼠标和/或 某种其它合适的输入设备来提供连接以实现用户输入。进一步，输入/输出 单元212可以将输出发送到打印机。显示器214提供用于向用户显示信息 的机构。

用于操作系统、应用和/或程序的指令可以位于存储设备216中，存储 设备216通过通信光纤通道网络202与处理器单元204通信。在这些示例 性实例中，指令以功能形式位于永久性存储装置208中。这些指令可以被 加载到存储器206以便由处理器单元204运行。处理器单元204可以使用 计算机实现的指令（可以位于存储器（例如存储器206）中）执行不同实 施例的过程。

这些指令被称为程序代码、计算机可用程序代码或计算机可读程序代 码，它们可以由处理器单元204中的处理器读取和执行。在不同的实施例 中，程序代码可以包含在不同的物理或有形计算机可读存储介质（例如存 储器206或永久性存储装置208）中。

程序代码218以功能形式位于选择性地可移动的计算机可读存储介质 220中，并可以被加载或传输到数据处理系统200以便由处理器单元204 执行。在这些实例中，程序代码218和计算机可读存储介质220形成计算 机程序产品222。在一个实例中，计算机可读存储介质220可以采取有形 形式，例如光盘或磁盘，光盘或磁盘被插入或放置到属于永久性存储装置 208的一部分的驱动器或其它器件中，以便传输到属于永久性存储装置208 的一部分的存储设备（例如硬盘驱动器）。在有形形式中，计算机可读存 储介质220还可以采取永久性存储装置的形式，例如连接到数据处理系统 200的硬盘驱动器、拇指驱动器或闪存。有形形式的计算机可读存储介质 220也被称为计算机可记录存储介质。在某些情况下，计算机可读存储介 质220可能不可移动。

备选地，可以通过到通信单元210的通信链路和/或到输入/输出单元 212的连接，将程序代码218从计算机可读存储介质220传输到数据处理 系统200。在所述示例性实例中，通信链路和/或连接可以是物理或无线的。 计算机可读介质还可以采取非有形介质的形式，例如包含程序代码的通信 链路或无线传输。

在某些示例性实施例中，可以通过网络将程序代码218从另一个设备 或数据处理系统下载到永久性存储装置208，以便在数据处理系统200中 使用。例如，可以通过网络将存储在服务器数据处理系统内的计算机可读 存储介质中的程序代码从该服务器下载到数据处理系统200。提供程序代 码218的数据处理系统可以是服务器计算机、客户端计算机，或者能够存 储和传输程序代码218的某种其它设备。

使用图2的数据处理系统200作为实例，提供用于对抓取空间进行分 区的计算机实现的过程。处理器单元204在从存储设备216检索的文档对 象模型中，计算事件集合中的每个事件的事件标识符，以便形成标识后的 事件集合。处理器单元204将标识后的事件集合划分成多个分区，并为节 点集合中的每个节点分配一个分区。处理器单元204启动由相应节点执行 每个分配的分区中的每个事件。响应于判定发现新状态，处理器单元204 使用通信单元210向其它节点通知新状态，其中将与新状态关联的信息添 加到每个节点处的相应分配的事件ID集合。响应于判定不存在更多的通 知，处理器单元204判定是否存在更多的待处理事件，并且响应于判定不 存在更多的待处理事件，处理器单元204结束分区过程。

参考图3，提供了可操作以用于本公开的各实施例的分区系统的框图。 分区系统300是用于对富互联网应用的抓取空间进行分区以实现分布式抓 取的系统的一个实例。

分区系统300利用底层数据处理系统（例如图1的网络数据处理系统 100中的服务器106或图2的数据处理200）的支持。分区系统300包括多 个功能组件，包括DOM302、事件集合304、事件标识器306、事件分区 器308、事件分配器310、节点集合312和节点消息传送器314。分区系统 300的组件可以实现为一组单独的组件（如在图3中），或者以某种功能 组合实现而不丢失能力。

DOM302提供定义事件集合304的能力，事件集合304包括富互联网 应用的对象表示的不同状态。DOM302是表示一组不同状态和关联的 JavaScript事件的数据结构。

事件集合304定义一组JavaScript事件，这些JavaScript事件在相应 的文档对象模型数据结构（例如DOM302）中定义。事件是可以由 JavaScript检测的操作。在Web页面上使用的每个元素具有一个或多个关 联的特定事件，这些事件可以触发JavaScript。例如，与按钮元素关联的 onclick事件用于指示当用户选择（单击）按钮时执行功能。典型的事件包 括单击元素、页面完成加载、图像完成加载、鼠标光标在元素上移动、输 入字段进行输入、提交表单和执行键击。

事件标识器306提供唯一标识与DOM302的特定实例关联的每个 JavaScript事件的能力。事件标识器306表示使用选定标识方法在文档对 象模型中标识事件的一组能力。例如，一种标识方法可以包括将事件索引 与文档对象模型一起使用，或者可以使用特定事件的XML路径语言路径 （XPath）作为事件标识符。XML路径语言是一种查询语言，其使用路径 表达式在XML文档中浏览以便从XML文档选择节点，并提供语法以便 定义XML文档的各部分。

事件分区器308提供将使用事件标识器306标识的事件划分成预定段 或分区的能力。事件分区器308提供一组能力，包括可选择的分区方法。 分区方法包括将分区定义为每个节点的特定数量的事件、每个节点的某一 百分比的事件、通过除以节点数量确定的某一数量的分区后的事件，以及 与每个节点的处理能力成比例的某一数量的分区后的事件。选择用于分区 的方法还可以取决于用于标识事件的方法。

事件分区器308可以实现为所有单独节点都可以调用的功能。在一个 实施例中，事件分区器308可以实现为单独抓取器的模块，其分散节点集 合，从而在事件属于相应节点时，使节点能够识别而无需其它通信。在另 一个实施例中，事件分区器308可以实现为管理所有节点的集中单元模块， 其中在节点和中央单元之间需要附加通信以便同步信息。

事件分配器310提供将事件分区器308的结果分配或分派给节点集合 312中的每个节点的能力。事件分配器310能够将事件作为JavaScript事 件列表分配给节点集合312中的节点，或者包括适用于节点集合312中的 特定节点的数组或数据库表项的其它数据结构。

节点集合312提供处理事件集合中的已分配事件的能力，该事件先前 分配给节点集合312中的特定节点。每个节点是负责处理所有分配的事件 的工作集合或池中的工作单元，其中每个已分配事件表示一个工作单位。 在处理事件期间，节点可以发现其它新状态。响应于发现新状态，节点使 用节点消息传送器314向所有其它节点通知或通告发现。节点消息传送器 314可以是现有通信网络或节点集合312的专用通信机构。通信包括广播、 令牌传递以及张贴到公共站点，其中其它节点定期查看张贴以便标识附加 工作项目。作为接收有关新发现状态的通知的结果，其它节点添加新发现 的状态以及到达该状态所需的JavaScript操作序列。

参考图4，提供可操作以用于本公开的各实施例的分区系统中的数据 流的框图。流程400是用于对富互联网应用的抓取空间进行分区以实现分 布式抓取的系统的逻辑单元之间的过程流程的一个实例（如在图3的分区 系统300中）。

并非如在当前技术中进行URL分区，所公开的分区系统的实施例使 用JavaScript事件执行RIA分区。所公开的框架的实施例包括节点集合， 这些节点具有以下能力：发现DOM的新状态和不同状态；交换状态的信 息，并且每个节点在每个DOM中执行分配的事件。

文档对象模型402是包括一组JavaScript事件的数据结构。文档对象 模型402中的每个JavaScript事件被处理以分配唯一的ID，以便形成标识 后的事件404。可以使用各种已知方法之一计算事件标识符。例如，使用 第一方法，将使用关联的DOM中的事件的索引。可以通过使用宽度优先 搜索从根朝向叶遍历关联的DOM来计算索引。使用该方法，第一个遇到 的JavaScript事件具有索引0，并且接下来遇到的JavaScript事件具有索 引1，依此类推，直到遇到并索引所有的JavaScript事件。在第二方法中， 将JavaScript事件的XPath视为事件ID。还可以使用其它方法以便针对 每个待处理JavaScript事件生成唯一标识符。

不管计算事件ID的方法为何，计算事件ID之后，使用利用事件分区 器（例如，图3的事件分区器308）的分区事件406的过程将事件ID集合 分为组、段或分区。如前所述，事件分区器也可以在单独节点上托管，而 不是在集中站点处托管，因为文档对象模型的分区功能将一致地划分搜索 空间。当事件分区器是集中式的时，可以按需更新或替换分区方法以便跨 所有节点使用。

分区事件406的输出采取分区后的事件1408、分区后的事件2410到 分区后的事件n412的形式。分区数量取决于以节点（例如节点1414、节 点2416到节点n418）形式提供的处理资源。为节点集合中的每个节点分 配一个或多个范围的ID（分区后的事件）。分区和分配确保在单独节点的 搜索空间中没有重叠，因此将特定事件定向到每个节点以便执行。在相应 节点中处理事件期间，可以发现新状态，如在发现的状态420中。当发现 新状态时，在节点之间共享信息以便确保完全覆盖任何关联的事件。

通常，代表RIA的相应DOM中的事件数量远高于状态数量。执行在 相应DOM中定义的所有事件，以便确保不会丢失与相应DOM关联的状 态。通过使用JavaScript事件对搜索空间进行分区，当在处理分配的事件 期间发现新事件时，通常仅需要节点之间的通信，同时允许节点执行分配 的事件而无需与其它节点通信，并且在搜索空间中没有重叠。因此，所公 开的过程的实施例通常需要节点之间的最少通信，同时确保执行相应 DOM中的所有事件，从而使能全面抓取所表示的RIA。

因为使用和分配唯一事件标识符，所以单独节点通常不探索同一搜索 空间，并且不需要在节点之间发送许多消息以便执行搜索空间分区。所公 开的分区系统的固有特性是一个事件不会被分配给两个或更多节点，因此 两个或更多节点从不为了发现状态而执行同一事件。

参考图5，提供了可操作以用于本公开的各实施例的分区系统中使用 的过程的流程图。过程500是使用用于对富互联网应用的抓取空间进行分 区以实现分布式抓取的系统的过程的一个实例（如在图3的分区系统300 中）。

过程500开始（步骤502），并接收包括事件集合的文档对象模型 （DOM）（步骤504）。如前所述，事件集合是代表富互联网应用（RIA） 的一组JavaScript事件。所接收的DOM可以根据需要包括一个或多个 DOM以便表示特定RIA。

过程500计算事件集合中的每个事件的事件ID以便形成标识后的事 件集合（步骤506）。每个事件标识符是针对在DOM中定义的相应事件 集合计算的一组标识符中的唯一值。

过程500将标识后的事件集合划分成或分为多个分区（步骤508）。 分区数量通常取决于可用于处理标识的事件的节点数量，并与可用节点数 量成比例。当资源限制较少时，可以通过分配更多的节点以便处理标识后 的事件集合（而不是分配较少的节点），获得增加的并行性。

过程500为节点集合中的每个节点分配一个分区（步骤510）。在某 些情况下，可以使用所公开的过程为节点分配一个或多个分区而不丧失功 能。将多个分区分配给节点只是延长该节点处的处理时间，因为处理额外 事件需要额外工作。

将事件划分成分区取决于用于计算事件标识符的方法。使用前面的标 识符计算实例，当使用第一方法时，可以使用范围和模数函数实现事件标 识符的划分。例如，当两个节点可用时，为第一节点分配所有偶数事件， 为第二节点分配所有奇数事件。概括该实例然后得出，对于n个节点，每 个节点接收1/n的事件集合。对于每个事件，标识符模数n提供负责执行 与事件标识符关联的特定事件的节点的索引。

当使用第二方法时，可以使用相应DOM的树结构并将不同分支分配 给不同节点来完成划分。

过程500确保所有节点接收初始种子URL以便启动处理（步骤512）。 每个节点执行每个分配的分区中的每个事件（步骤514）。在每个节点上 处理分配的事件期间，过程500判定是否发现潜在的新状态（步骤516）。

响应于判定未发现潜在的新状态，在特定节点处，过程500向前跳到 步骤522。响应于判定发现潜在的新状态，在特定节点处，过程500向其 它节点通知潜在的新状态（步骤518）。可以以多种格式完成通知。通知 方法包括通过以下操作传送信息：节点广播，或者使用令牌环，或者传送 先前未被广播的新发现状态的其它手段，所述信息包括到达新状态所需的 JavaScript操作序列。

发现新状态或者从其它节点接收新状态时，每个节点将与新状态关联 的信息添加到分配的事件标识符集合的相应待办事项（to do list）列表（步 骤520）。

过程500判定是否存在更多通知（步骤522）。响应于判定存在更多 通知，过程500循环返回以便如先前那样执行步骤518。响应于判定不存 在更多通知，过程500判定是否存在更多待处理事件（步骤524）。响应 于判定存在更多待处理事件，过程500循环返回以便如先前那样执行步骤 514。响应于判定不存在更多待处理事件，过程500终止（步骤526）。

公开了一种用于对富互联网应用的抓取空间进行分区以实现分布式抓 取的过程。所公开的过程包括在文档对象模型（DOM）中标识事件集合中 的事件的事件标识符，其中使用以下各项之一分配标识符：第一计算，其 在DOM中使用事件索引，其中通过使用宽度优先搜索从根开始向外朝向 叶遍历DOM来计算索引，其中为第一个遇到的JavaScript事件分配索引 值0，并且为接下来的每个JavaScript事件分配从前一个JavaScript事件 递增1的索引值；以及第二计算，其中所标识事件的XPath形成事件标识 符。

所公开的过程还在节点之间划分标识的事件标识符，其中根据用于计 算事件标识符的方法确定划分，其中当使用第一计算时，事件标识符的划 分使用范围和模数函数，其中对于n个节点，每个节点将获得1/n的事件 集合，并且对于每个事件，标识符模数n提供负责执行该特定事件标识符 的节点的索引，并且其中当使用第二计算时，使用DOM的树结构确定划 分，并将不同分支分配给不同节点。

响应于使每个节点知晓关联的事件，所有节点使用所公开的过程接收 初始种子统一资源定位符（URL），并且每个节点执行分配给每个节点的 事件，以便发现潜在的新状态。

响应于发现新状态，所公开的过程的节点将以前未告知的新发现状态 连同到达新发现状态所需的JavaScript操作序列一起传送到其它节点。响 应于发现新状态或者从其它节点接收新状态中的至少一个，每个节点将新 状态添加到关联的待办事项。

所公开的过程还判定节点是否具有要广播的任何事物或者要执行的任 何事件，并且响应于判定节点没有要广播的任何事物或者要执行的任何事 件，所公开的过程终止。

参考图6，提供了跨可操作以用于本公开的各实施例的分区系统中的 所有节点使用的过程的流程图。过程600是使用用于对富互联网应用的抓 取空间进行分区以实现分布式抓取的系统的过程的一部分的一个实例（如 在图3的分区系统300中）。

过程600表示过程500的一部分，其适用于参与分区过程的所有节点。

参考图7，提供了可操作以用于本公开的各实施例的分区系统的备选 模式中使用的过程的流程图。每个备选模式是图5的过程500的一部分的 实例，其使用用于对富互联网应用的抓取空间进行分区以实现分布式抓取 的系统（如在图3的分区系统300中）。

第一实例表示图5的过程500的一部分，其适用于分区过程的集中实 现。当分区是集中式的时，需要所有节点和其它处理模块以便与集中单元 通信，从而增加消息业务以及控制。使用分区的集中实现将图5的过程500 的步骤510实现为变型510A。

第二实例表示图5的过程500的一部分，其适用于分区过程的分散实 现。当分区分散并在所有节点上托管时，节点和其它处理模块之间的通信 比使用集中单元需要的通信减少，从而减少消息业务以及控制。使用分区 的分散实现将图5的过程500的步骤510实现为变型510B，其将分区分配 给当前节点。

因此，在一个示例性实施例中提供了一种用于对抓取空间进行分区的 计算机实现的过程。所述计算机实现的过程计算事件集合中的每个事件的 事件标识符以便形成标识后的事件集合，将标识后的事件集合划分成多个 分区，向节点集合中的每个节点分配一个分区，并且由相应节点执行每个 分配的分区中的每个事件。响应于判定发现新状态，向其它节点通知新状 态，其中将与新状态关联的信息添加到每个节点处的相应分配的事件ID 集合。响应于判定不存在更多的通知，计算机实现的过程判定是否存在更 多的待处理事件，并且响应于判定不存在更多的待处理事件，计算机实现 的过程结束。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法 和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程 图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述 模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的 可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功 能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际 上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及 的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和 /或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬 件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

以下的权利要求中的对应结构、材料、操作以及所有功能性限定的装 置或步骤的等同替换，旨在包括任何用于与在权利要求中具体指出的其它 单元相组合地执行该功能的结构、材料或操作。所给出的本发明的描述在 于示意和描述，并非是穷尽性的，也并非将本发明限定到所公开的形式。 在不偏离本发明的范围和精神的情况下，对于本领域的普通技术人员而言， 许多修改和变化都将是显而易见的。实施例的选择和描述，旨在最好地解 释本发明的原理、实际应用，当适合于所构想的特定应用时，可使本技术 领域的普通技术人员理解本发明带有各种修改的各实施例。

本发明可以采取完全的硬件实施方式、完全的软件实施方式或同时包 含硬件和软件元素的实施例的形式。在一个优选实施例中，本发明在软件 中实现，其中包括但不限于固件、驻留软件、微代码，以及本领域的技术 人员识别的其它软件介质。

重要的是指出，虽然在功能完备的数据处理系统上下文中描述了本发 明，但是本领域的普通技术人员将理解，本发明的过程能够以计算机可读 数据存储介质的形式分发，所述计算机可读数据存储介质上以各种形式存 储计算机可执行指令。计算机可读数据存储介质的实例包括可记录型介质， 例如软盘、硬盘驱动器、RAM、CD-ROM、DVD-ROM。所述计算机可 执行指令可以采取编码格式的形式，这些代码格式在特定数据处理系统中 针对实际使用进行解码。

适合于存储和/或执行计算机可执行的指令的数据处理系统将包括至 少一个通过系统总线直接或间接连接到存储元件的处理器。所述存储元件 可以包括在程序代码的实际执行期间采用的本地存储器、大容量存储装置 以及提供至少某些程序代码的临时存储以减少必须在执行期间从大容量存 储装置检索代码的次数的高速缓冲存储器。

输入/输出或I/O设备（包括但不限于键盘、显示器、指点设备等）可 以直接或通过中间I/O控制器与系统相连。

网络适配器也可以被连接到系统以使所述数据处理系统能够通过中间 专用或公共网络变得与其他数据处理系统或远程打印机或存储设备相连。 电话调制解调器、电缆调制解调器和以太网卡只是几种当前可用的网络适 配器类型。