基于对等结构的分布式高维索引并行查询框架

摘要

本发明提出一种基于对等结构的分布式高维索引并行查询框架，包括索引创建模块、监视器模块、对等站点集群以及负载软均衡模块，索引创建模块用于创建索引并对索引块文件进行存储，监视器模块用于检测所述对等站点集群中的工作站点的可用内存信息以及每个工作站点对应的索引块信息以根据检测结果对每个工作站点进行协调，负载软均衡模块用于对当前工作站点进行负载均衡控制，且定时由监视器模块进行同步以便负载软均衡模块能对当前可用的工作站点列表进行及时的调整和更新。本发明的实施例具有实时的、可靠的、支持动态增减的海量候选对象检索的优点，且查询速度快。

说明书

技术领域

本发明涉及计算机信息检索技术领域，特别涉及一种基于对等结构的分布式高维索引 并行查询框架。

背景技术

基于内容的图像检索、视频检索等技术的迅速发展，使得高维索引技术得到越来越广 泛的发展和应用。高维索引技术的应用，主要是为了加快检索速度，进而提升用户的查询 体验。在目前已有的绝大部分应用中，高维索引的查询实际上就是在语义层面上检索查询 对象的前k个最近邻(k Nearest Neighbors，简称kNN)。

一般而言，基于内容的检索技术首先需要将海量的候选对象(图像、视频等)转化为 高维特征向量，以量化的形式尽可能保存对象本身的特征。然后，需要对提取出来的海量 高维向量进行索引。当用户提交查询对象时，经过量化转化为同等维度的高维特征向量， 并利用高维索引结构，快速检索出其kNN，并将结果返回。在大部分应用场景下，高维索 引的创建是允许离线的，对于实时性没有过高的要求，但对稳定性、可靠性和完整性要求 较高。而对于高维索引的查询，实际应用中的需求十分明确和严格，必须是尽可能精确、 快速、可靠，并且支持动态增减的海量候选对象的检索。这也正是本发明着重思考和解决 的问题。

随着各类应用的推广，高维索引技术在学术界和工业界都引起了广泛的关注，并涌现 了大量提升高维索引创建和查询效率的算法与方案。高维索引的效率提升策略，目前总体 上可以划分为三大类。第一类是以降低kNN精确度的代价来提高效率的，亦即只查询近似 kNN。第二类则是通过改变索引结构提升索引的创建和查询速度，但是经过几十年的研究， 目前尚未发现十分高效的支持上百维甚至更高维度的索引结构。第三类则是从索引系统的 架构上进行改进，通过引入并行索引系统提升创建和查询的速度，然而，目前在实时可靠 并行系统的研究方面，由于技术壁垒的存在，相关技术很难被广泛应用。另外，传统的主 从式索引查询架构缺乏自组织性，并且容易出现性能瓶颈。

发明内容

本发明旨在至少解决上述技术问题之一。

为此，本发明的一个目的在于提出一种基于对等结构的分布式高维索引并行查询框架， 该分布式高维索引并行查询框架基于对等结构，具有实时的、可靠的、支持动态增减的海 量候选对象检索的优点，且查询速度快。

为了实现上述目的，本发明的实施例提出了一种基于对等结构的分布式高维索引并行 查询框架，包括：索引创建模块、监视器模块、对等站点集群以及负载软均衡模块，其中， 所述索引创建模块用于对海量候选对象进行分割并为每个分割部分创建索引以得到多个索 引块文件，并对所述索引块文件进行存储，其中，所述索引块文件包括索引块信息，所述 监视器模块用于检测所述对等站点集群中的工作站点的可用内存信息以及每个工作站点对 应的索引块信息以根据检测结果对每个工作站点所加载的索引块进行协调以及向每个工作 站点发送对等站点列表更新指令，所述对等站点集群中的工作站点根据自身的索引块信息 对相应的索引块文件进行加载或卸载，且根据用户发送的查询请求在相应的索引块文件中 进行查询并将查询结果进行整合和输出，所述负载软均衡模块用于获取所述监视器模块中 的当前工作站点列表以根据所述工作站点列表对当前工作站点进行负载均衡控制，且所述 负载软均衡模块定时由所述监视器模块进行同步以便所述负载软均衡模块对当前可用的工 作站点列表进行调整和更新。

根据本发明实施例的基于对等结构的分布式高维索引并行查询框架采用效率高的索引 结构，具体地，采用Hybrid Spill Tree作为基本的索引结构(高维索引结构)，且采用对等 站点的架构方式，在实时性、可靠性、稳定性、可扩展性、自组织性等方面都做了较为全 面的保障。可以高效进行查询，并且具有较强的可扩展性，可以方便地迁移到各种基于内 容的搜索系统中，且具有查询速度快的优点。另外，该基于对等结构的分布式高维索引并 行查询框架结构清晰，易于实现。

另外，根据本发明上述实施例的基于对等结构的分布式高维索引并行查询框架还可以 具有如下附加的技术特征：

在本发明的一个实施例中，所述索引创建模块进一步包括：索引创建子模块，所述索引 创建子模块采用Map Reduce框架对多个数据分割部分并行创建索引以得到所述多个索引 块文件；分布式存储系统，所述分布式存储系统用于保存所述多个索引块文件。

在本发明的一个实施例中，所述监视器模块还用于在检测到索引块文件更新后对非工 作站点集群发送索引加载指令以使所述非工作站点集群进入工作状态，所述索引块文件加 载完毕后所述监视器模块将进行集群切换，并使用已加载最新索引的工作站点集群，将原 有工作站点集群置于非工作状态。

在本发明的一个实施例中，所述监视器模块根据所述检测结果判断当前的工作站点中 是否存在失效站点，并在检测到存在失效站点时向当前可用的工作站点发送对等站点列表 更新指令。

在本发明的一个实施例中，当有非工作站点加入所述工作站点集群时向所述监视器模 块进行注册，以便所述监视器模块对所述工作站点列表进行更新，并将所述更新后的工作 站点列表发送给所述负载软均衡模块，同时将更新后的对等站点列表发送到所有所述工作 站点。

在本发明的一个实施例中，当所述对等站点集群中的每个工作站点接收到查询请求时， 创建主进程并根据自身的索引块信息创建多个相应的子进程，以使每个子进程从对应的已 加载索引块中进行查询，并将查询结果发送给主进程并通过主进程进行整合发送。

在本发明的一个实施例中，所述主进程还用于响应其它工作站点中分发的查询请求。

在本发明的一个实施例中，所述子进程对主进程进行监测，以便在所述主进程意外退 出时自动关闭。

在本发明的一个实施例中，所述负载软均衡模块包括多个负载软均衡站点，且所述负 载软均衡模块维护所述当前可用的工作站点列表。

在本发明的一个实施例中，所述索引块文件采用Hybird Spill Tree数据结构。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明 显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显 和容易理解，其中：

图1为本发明实施例的基于对等结构的分布式高维索引并行查询框架的示意图；以及

图2为本发明实施例的基于对等结构的分布式高维索引并行查询框架的架构图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同 或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描 述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。

在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“上”、“下”、“前”、 “后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为 基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗 示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对 本发明的限制。此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相 对重要性。

在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、 “连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可 以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以 是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在 本发明中的具体含义。

以下结合附图描述本发明实施例的基于对等结构的分布式高维索引并行查询框架。

参见图1和图2，根据本发明实施例的基于对等结构的分布式高维索引并行查询框架 100包括索引创建模块Builder、监视器模块Monitor、对等站点集群以及负载软均衡模块 Balancer。其中：

索引创建模块Builder用于对海量候选对象进行分割并为每个分割部分创建索引以得 到多个索引块文件，并对所述索引块文件进行存储，其中，索引块文件包括索引块信息。

监视器模块Monitor用于检测所述对等站点集群中的工作站点的可用内存信息以及每 个工作站点对应的索引块信息以根据检测结果对每个工作站点所加载的索引块进行协调以 及向每个工作站点发送对等站点列表更新指令。具体而言，监视器模块Monitor监测、协 调和管理各个工作站点之间的工作。一方面，例如监视器模块Monitor通过类似于心跳包 检测的方式定时获取各个工作站点上的可用内存信息及索引块信息，并根据得到的结果， 分析出是否存在重复索引或者缺失索引，并根据可用内存信息进行智能协调，要求某些工 作站点卸载索引块或加载缺失的索引块，以确保索引块的最低冗余以及完整性。另一方面， 监视器模块Monitor将提供对等站点集群的管理功能，心跳包检测可以发现失效的站点， 并通知其他站点进行对等站点列表的调整，而当新的站点添加之后，也会自动向监视器模 块Monitor进行注册，并由Monitor通知其他工作站点调整对等站点列表，以最大程度上保 证每个站点能近乎实时地知道同一索引集群中的站点信息。此外，监视器模块Monitor负 责与负载均衡模块Balancer之间的同步工作。监视器模块Monitor将自己检测到的当前索 引集群中的有效站点列表同步给负载均衡模块Balancer中的每个负载软均衡站点，以保证 负载均衡设备Balancer能为所有查询选择出有效的可用工作站点。

对等站点集群中的工作站点根据自身的索引块信息对相应的索引块文件进行加载或卸 载，且根据用户发送的查询请求在相应的索引块文件中进行查询并将查询结果进行整合和 输出。

负载软均衡模块Balancer用于获取监视器模块Monitor中的当前工作站点列表以根据 所述工作站点列表对当前工作站点进行负载均衡控制，且负载软均衡模块Balancer将定时 由监视器模块Monitor进行同步以便负载软均衡模块Balancer对当前可用的工作站点列表 进行调整和更新。

根据本发明实施例的基于对等结构的分布式高维索引并行查询框架100采用效率高的 索引结构，具体地，采用Hybrid Spill Tree作为基本的索引结构(高维索引结构)，且采用 对等站点的架构方式，在实时性、可靠性、稳定性、可扩展性、自组织性等方面都做了较 为全面的保障。可以高效进行查询，并且具有较强的可扩展性，可以方便地迁移到各种基 于内容的搜索系统中，且具有查询速度快的优点。另外，该基于对等结构的分布式高维索 引并行查询框架结构清晰，易于实现。

在本发明的一个实施例中，索引创建模块Builder进一步包括索引创建子模块以及分布 式存储系统。其中：

索引创建子模块采用Map Reduce框架对多个数据分割部分并行创建索引以得到所述 多个索引块文件。分布式存储系统用于保存所述多个索引块文件。

具体而言，考虑到索引创建允许离线进行，对于实时性要求不高，而对于可靠性和稳 定性要求较为严格，所以直接采用成熟的Map Reduce框架，用于并行创建索引，并借助于 分布式存储系统，将底层的存储结构透明化，用于存放索引块文件。

需要理解的是，在索引创建模块Builder中，将海量候选对象分割成多个部分，并为每 一部分创建相应的索引块，可以为后续的分布式并行查询奠定基础。采用Map Reduce框架， 定时高效地并行创建索引，并在新索引创建成功之后，覆盖旧索引文件，以适应候选对象 的变动。

在本发明的一个实施例中，所述监视器模块Monitor还用于在检测到索引块文件更新 后对非工作站点集群发送索引加载指令以使所述非工作站点集群进入工作状态，并在索引 块文件加载完毕后所述监视器模块将进行集群切换，并使用已加载最新索引的工作站点集 群，将原有工作站点集群置于非工作状态，同时向负载软均衡模块发送最新工作站点列表。 也就是说，监视索引文件的变动情况，并且在索引文件变化稳定之后，要求非工作站点进 行索引加载，加载完成之后进行集群切换，使之成为工作站点，替换之前的工作站点。

在本发明的一个实施例中，所述监视器模块根据所述检测结果判断当前的工作站点中 是否存在失效站点，并在检测到存在失效站点时向当前可用的工作站点发送对等站点列表 更新指令。即监视器模块Monitor通过上述实施例的心跳包检测可以发现失效的站点，并 通知其他站点进行对等站点列表的调整。

进一步地，当有非工作站点加入工作站点集群时将向监视器模块Monitor进行注册， 以便监视器模块Monitor对工作站点列表进行更新，并将所述更新后的工作站点列表发送 给所述负载软均衡模块，同时发送指令要求其他工作站点进行对等站点列表的更新。

作为一个具体的示例，当对等站点集群中的每个工作站点接收到查询请求时，创建主 进程并根据自身的索引块信息创建多个相应的子进程，以使每个子进程从对应的已加载的 索引块中进行查询，并将查询结果发送给主进程并通过主进程进行整合发送。进一步地， 主进程还用于响应其它工作站点中分发的查询请求，亦即当某个工作站点接收到用户查询 请求之后将进一步分发查询请求，要求其他站点协助查询的完成。在该示例中，子进程对 主进程进行监测，以便在所述主进程意外退出时自动关闭。

具体而言，工作站点的主进程主要负责三部分的工作。

1、响应监视器模块Monitor的心跳检测，提供当前工作站点可用的内存信息，以及负 责的索引块信息等。因此，当工作站点在启动服务时，应该主动向监视器模块Monitor进 行注册。并且，主进程需要维护索引块信息，当需要加载指定索引块时，创建相应的子进 程对索引块进行管理，而当需要卸载指定索引块时，则是将负责该索引块的子进程进行关 闭。此外，主进程需要对子进程的状态进行监测，当发现子进程失效时，能及时向监视器 模块Monitor反馈索引块缺失情况。

2、响应其他工作站点分发的查询请求，并根据查询请求将请求提交给子进程进行处理， 然后在指定的时间阈值内对子进程返回的结果进行整合，最终返回给分发查询请求的工作 站点。

3、接受用户的查询请求，并行分发给其他的工作站点，最后在指定的时间阈值内对各 个工作站点(包括本身)的返回结果进行二次整合，并返回给用户。

工作站点的子进程负责的工作如下：

1、加载索引块文件，并对索引块文件进行内存展开，映射好特征向量与候选对象之间 的一一对应关系。

2、响应主进程的查询请求，在索引结构中查询指定对象的预定数量的最为相似的查询 结果，并将结果返回给主进程。

3、监测主进程的活动，以保证当主进程意外退出时，能自行关闭，以免占用过多资源。

需要理解的是，本发明实施例中的索引块管理采用的是子进程模式，而非线程模式， 主要是为了保证在内存不足以加载新的索引块的情况下，采用子进程的方式可以避免因为 加载新索引块失败而导致主进程完全崩溃的情况，最终不至于导致所有已经加载完毕的索 引块全部失效。这样也是为了能最大程度上保证系统的稳定性和可靠性。

在本发明的一个实施例中，所述负载软均衡模块包括多个负载软均衡站点。每个负载 软均衡站点的作用为适当调度查询请求，使得各个工作站点的负载总体上达到平衡，以避 免出现某些站点负载过重而另一些站点负载过轻的现象。负载软均衡模块Balancer通过监 视器模块Monitor的同步作用，获取当前索引集群中有效的工作站点列表，并接收查询接 口的请求，选择适当的工作站点返回供查询接口进行查询调用。

需要说明的是，为了保证同步的顺畅，和工作站点类似，负载软均衡站点启动服务时 会主动向Monitor站点进行注册。一般而言，如果各个工作站点的硬件设施情况相近，负 载软均衡站点则可以采取随机选取的方式进行工作站点的选择，并返回给查询接口进行进 一步的查询调用。

本发明的实施例中，还可以具有查询接口模块Searcher，查询接口模块Searcher主要 负责两方面的功能。

1、将查询对象进行量化，转化为具有同等维度的向量，并提交该向量进行查询，然后 将查询结果转化为外部接口所需的形式。

2、将底层的调度关系进行封装，向上屏蔽，以降低架构的耦合性，并提升系统的可扩 展性。实际上，该部分的查询操作可以分为两个步骤：从负载软均衡模块Balancer中获取 有效的工作站点，将查询提交给工作站点并获取相应的结果。

在本发明的一个示例中，为了保证实时性要求，查询部分不适合采用Map Reduce框架， 而是结合MPI等更为高效的信息传递方式来负责站点问的通信与协调。

本发明的实施例具有如下优点：

1、高度并行化，查询高效，实时性较好，并且精确度较高。

采用的是分布式的索引查询架构，并且采用了较为高效的高维索引结构Hybrid Spill Tree，同时结合MPI等高效通信机制，从各个方面都尽可能保证查询的快速响应。此外， 相比于单机环境下的Hybrid Spill Tree，本发明实施例的分布式索引结构能有效提高精确度， 主要原因是每次进行预定数量的近似近邻查询时，采用了冗余策略，并且最终对结果进行 了两阶段的整合与过滤，从而能保证最终返回的结果能覆盖绝大部分的预定数量的精确近 邻。其中第一阶段的整合过滤是工作站点对本地子进程返回的结果进行整合时，滤除了一 部分冗余结果，而第二阶段则是发出全局查询请求的工作站点对其他工作站点返回的结果 进行整合时，进一步滤除冗余结果。另外需要说明的是，Hybrid Spill Tree本身具备参数可 调的特点，可以在实际应用中选择合适的参数，以便在效率与精确度之间获得良好的折中。

2、系统可靠性和稳定性较高。

从架构的模块分析可以看出，本发明引入了监视器模块Monitor用于监测和管理索引 块的加载情况，并对工作站点进行相应的管理，根据站点的内存情况进行智能协调，以尽 可能地保证全局索引的最低冗余和完整性，从而保证查询的可靠性。此外，考虑了多种可 能出现的异常情况，包括宕机、子进程异常退出、主进程异常退出等等，并且针对以上问 题，引入了较为复杂的监测机制和协调机制，从而保证在多种异常发生，甚至并行发生的 情况下，系统依然能较为鲁棒地运转，并保证外部查询的接收和反馈。需要提及的一点是， 从表面上看，本发明引入的监视器模块Monitor与传统主从架构方案中的主站点比较类似， 可能成为整个架构的瓶颈。但实际上，通过分析可以知道，本发明中的监视器模块Monitor， 其负载明显比主从结构中的主站点更低。并且，通过采用传统的热备份或集群等技术，可 以更大程度上保证同一时间都有Monitor站点和Balancer站点能正常运转，从而为系统的 稳定性提供强大的保障。另外，本发明实施例采用的是基于对等结构的架构方案，对于瓶 颈点的依赖更小，即便在Monitor完全失效的情况下，只要有一个Balancer站点和若干个 工作站点能正常工作，系统依然能响应查询。

3、可扩展性、可伸缩性较好。

本发明实施例所提出的高维索引并行查询框架并不针对于某种特定的应用，而是直接 处理特征向量，这使得该框架具有更强的可扩展性，既可以应用于基于内容的图像检索， 还可以应用于视频检索、音频检索等领域中。另外，在本发明中，对于工作站点和负载软 均衡站点，当它们启动服务后，都会主动向Monitor进行注册，而在退出时也都会向Monitor 提交注销申请，并由Monitor进行后续的通知或者同步，这种机制使得动态增加或删除站 点更加方便，无需干预其他站点或者重启系统，只需配置好被增删的站点即可。这些都反 映出本发明所提出的框架在系统的动态伸缩方面具备较强的适应能力。另外，本发明实施 例提出的基于对等结构的高维索引并行查询框架中，任一工作站点都可以作为全局查询的 负责站点，同时也可以作为全局查询的协助站点，操作更加灵活。

4、自组织性、智能管理能力较强

本发明所提出的基于对等结构的分布式高维索引并行查询框架在站点的管理和协调上 做了双向的保障。一方面，工作站点或者负载软均衡站点的启动或退出都会向Monitor站 点进行注册或注销，并由Monitor站点进行通知和同步等后续工作；另一方面，Monitor站 点本身维护着全部负载软均衡站点列表，同时维护着所有对等站点集群信息以及当前使用 的对等站点集群(索引集群)中的全部工作站点信息，并对这些站点进行协调和管理(包 括索引块的去重、补缺等等)。另外，本发明实施例提出的查询框架支持异构站点的组合， 并且能根据各个站点的可用内存情况，智能地进行索引块的分配及其他调度、协调工作， 使得系统的资源能得到充分、恰当的利用。并且，负载软均衡站点的引入也从软均衡的层 面上对各个工作站点的负载进行调整。上述均反映了本发明所提出的框架具备较强的自组 织性和智能管理能力。

5、支持动态增减的海量数据

本发明结合较为成熟的Map Reduce框架和相应的分布式存储系统，将高维索引的创建 与查询连接了起来。在引入Map Reduce框架对索引创建进行并行化之后，一定程度上解决 了高维索引结构增删代价大的局限性，而是通过快速重建索引的方式进行高维索引的更新。 此外，引入分布式存储系统，可将底层的存储系统透明化，更方便于工作站点中的子进程 进行索引块的读取，而无需进行繁复的配置。以上两方面的结合，为提供海量数据的高维 索引结构创建奠定了基础，并为可行性提供保障。本发明将高维索引的创建与查询通过分 布式存储系统进行连接，高维索引创建模块只负责定时重建索引，以反映数据的变动情况， 而Monitor站点则定时进行索引文件的更新检测，并在检测到稳定更新后，进行索引的加 载和索引集群的切换，使得系统能及时响应海量数据的动态变化情况。

【实施例】

在实际应用中，通过100万张图像的120维特征向量的实际测试，验证了其有效性和 可行性。如下表所示，为基于对等结构的分布式高维索引并行查询框架实验结果。列出了 本发明在实际测试中若干次查询的响应速度情况。需要提及的是，在此次实验过程中，将 所有查询的时间阈值设置为1秒，全部图像被切分为5部分并创建了等同数量的索引块文 件，对等站点集群包含5台异构的普通PC机(其中四台PC的配置为2G内存，奔腾E5300 双核CPU，另外一台配置为4G内存，奔腾E5200双核CPU)。另外，在实验过程中，并 没有对Hybrid Spill Tree的参数进行调优，而采用经验值进行测试，以更全面真实地反映系 统的响应能力。

  查询次数  1   2   3   4   5   6   7   8   9   10   均值   查询耗时(毫秒)  139   121   77   64   88   57   90   66   65   85   85.2

表1

从表1可以看出，查询时间存在一定的波动现象，但总体响应时间都还是非常短的， 平均响应时间为85.2毫秒，基本能满足实际应用中的检索需求。而且，可以展望的是，在 对Hybrid Spill Tree进行参数调优，引入更强劲的服务器，设定更小的查询时限等条件下， 查询时间将会有更进一步的缩减，从而使系统更加高效实用。

基于对等结构的分布式高维索引并行查询框架的更为具体实现方式，如下：

索引创建模块的实现(高维索引创建模块Builder)的实现：

高维索引创建模块主要负责的工作是定时对海量的候选对象进行索引的重建，以保证 及时反映候选对象的变动情况。该模块由于对实时性要求不高，而对稳定性和可靠性要求 较为严格，在该实施例中，借助于相对成熟稳定的Map Reduce框架实现，并且结合分布式 存储系统对索引创建的过程进行高度并行化，以保证重建索引的高效和可靠。

因此，Builder模块的实现一方面集中于较为成熟的开源框架的搭建以及分布式存储系 统的搭建，另一方面则是集中于设置定时任务，对指定的海量候选对象定时进行恰当的数 据分块，并通过Map Reduce任务进行索引的并行化创建，最终将各个索引块文件存储在透 明的分布式存储系统中。

此外，Builder模块还需要负责索引块文件的维护，具体而言，就是在新索引全部创建 成功后，移除旧的索引块文件，并将新索引块文件全部移动到分布式存储系统中指定的路 径下，以便被Monitor模块监测到。需要说明的一点是，这里覆盖索引块文件的时间差不 会导致出现监测出错的情况，因为Monitor模块中的监测功能并非第一次发现变动后立即 开始新索引的加载和切换，而是会继续对新索引文件进行若干次的跟踪，并且只有在判断 出索引文件基本稳定的情况下才执行索引的切换。而且，即便出现了异常的过早加载的情 况，随着后续索引文件的改动，系统将会重新加载，最终保证索引切换的准确性。

监视器模块(Monitor)的实现：

Monitor模块所负责的工作主要包括三部分：索引文件的更新监测，工作站点(Peer站 点)的监测、协调与管理，以及同步负载软均衡站点(Balancer站点)。而Monitor模块与 其他模块、站点之间的通信，以及其他模块之间、站点之间的通信，在该实施例中，都主 要依赖于Java语言的高效通信接口RMI(Remote Method Invocation，MPI的Java实现， 广泛应用于并行环境的开发中)。根据RMI的实现特点，Monitor模块在执行上述三部分工 作的过程中，既是RMI服务的被调用方，同时又是RMI服务的调用方(Peer站点、子进 程等也类似)。

作为RMI服务的被调用方，Monitor需要提供的服务接口包括如下这些： registerClusterPeer，registerBalancer，unregisterClusterPeer，unregisterBalancer。其中 registerClusterPeer和registerBalancer服务接口主要用于Peer站点和Balancer站点的注册， 其中Peer站点的注册需要指明所属的对等站点集群，而unregisterClusterPeer和 unregisterBalancer服务接口则主要用于Peer站点和Balancer站点的注销请求。通过以上四 个服务接口，Monitor站点自身维护着所有对等站点集群的Peer站点信息和所有Balancer 站点信息。

作为RMI服务的调用方，Monitor执行其所负责的工作时主要依赖于调用其他模块或站 点的服务接口，从而实现相应的功能。

在索引文件的更新监测方面，Monitor站点需要启动定时线程用于每隔一段时间对索引 文件进行检测，并通过比对确认索引文件的变动情况。并且，在首次发现变动之后，Monitor 站点将进行进一步的跟踪，直到最终确认索引文件变动稳定之后才启动索引切换任务。索 引的切换实际上是Monitor站点通知闲置对等站点集群进行新索引块的加载，并按照预定 的策略判断是否加载成功。在加载成功的情况下，直接将当前索引集群切换到新的集群上， 并同步Balancer站点。

在工作站点的检测、协调与管理方面，Monitor站点同样需要维护定时线程，用于监测 当前索引集群中所有Peer站点的可用内存、索引块情况等，并根据指定的策略将多次没响 应的站点认定为失效站点，报告给管理人员。此外，当Monitor站点提供的四个服务接口 被调用时，Monitor站点本身也需要在内存中维护相应的Peer站点列表和Balancer站点列 表，并通知给其他站点。特别是，当某个Peer站点注册或者注销时，Monitor站点响应请 求后，会通知同一对等站点集群中的其他站点更新其对等站点列表信息。另外，Monitor 会根据各个Peer站点反馈回来的可用内存信息和索引块信息，从中发现重复的索引块或者 是缺失的索引块，并根据Peer站点的可用内存信息，智能地选择合适的站点进行索引块的 卸载或加载，以保证整个索引的最低冗余和完整性。

在同步负载软均衡方面，实际上是Monitor站点启动定时线程，并通过直接调用Balancer 站点提供的服务，将其所维护的当前索引集群的可用站点列表信息同步给所有的Balancer 站点，使之能及时反映索引变动的情况，并与Monitor站点保持一致，从而能为查询接口 模块提供合适的Peer站点作为查询主站点。

需要说明的一点是，Monitor模块的实现需要有相应的外部配置文件，以对Monitor模 块进行初始化。其中最为重要的配置内容包括：索引监测时间间隔，Peer站点监测时间间 隔，索引文件在分布式存储系统中的存放路径，可用的对等站点集群及其内部的Peer站点 信息(包括IP地址、RMI服务端口等)，全部Balancer站点信息，以及跟RMI或者协调策 略相关的一些配置项等。

对等站点中主进程的实现：

对等站点主进程是查询服务的主要提供方，该进程主要负责三方面的功能：响应Monitor 站点的监测请求并维护对等站点列表信息和本地索引块信息，响应其他站点的全局检索请 求并整合子进程的查询结果，向其他对等站点分发全局检索请求并整合各个对等站点返回 的查询结果。

在响应Monitor站点的监测请求和维护本地索引块方面，Peer站点需要在启动的时候向 Monitor进行注册，以告知Monitor，进而告知同一对等站点集群下的其他对等站点，这是 Peer站点作为RMI服务调用方的地方之一。启动之后，Peer站点需要针对Monitor至少提 供如下服务：Ping，addFederal，removeFederal，loadIndex，unloadIndex。其中Ping服务接口用 于返回Peer站点本身的可用内存信息和正在管理的索引块信息；addFederal和 removeFederal服务接口用于添加和删除Peer站点内存中维护的对等站点列表中的某个对等 站点信息，以保证全局检索请求的准确分发；loadIndex和unloadIndex服务接口用于加载 和卸载指定的索引块，实际实现中，loadIndex是由主进程启动一个负责管理该索引块的子 进程，而unloadIndex则是直接将相应的子进程强行进行关闭，以从内存中卸载相应的索引。 与此同时，主进程会始终保持对子进程的监测，当发现某个子进程符合指定的失效策略(诸 如连续若干次响应超时等)时，直接认定其为失效子进程，并反馈给Monitor站点。相对 应地，主进程需要为子进程启动PingForChildProcess服务，以响应子进程的监测请求，从 而维持子进程的运行状态。

在响应其他站点的全局检索请求并整合子进程的查询结果方面，每一个Peer站点需要 为其他对等站点开启search服务，以接收其他对等站点的全局检索请求。当接收到其他站 点的全局检索请求后，Peer站点将调用子进程的服务接口，并把检索请求进一步提交给自 己维护的所有子进程。在获取到各个子进程返回的查询结果后，Peer站点将负责对结果按 照精确度从高到低进行整合，并去除冗余部分，然后返回给分发全局查询请求的对等站点。

在向其他对等站点分发全局检索请求并整合各个对等站点返回的查询结果方面，Peer 站点需要提供globalSearch服务供查询接口模块调用。当接收到查询接口模块的查询请求 时，Peer站点将通过多个线程，进一步派发检索请求给同一对等站点集群中的其他Peer站 点，同时自己也启动本地的检索，提交检索请求给本地维护的所有子进程。Peer站点在发 出全局检索请求后，既需要整合本地子进程的检索结果，又需要整合其他对等站点返回的 检索结果。整合的过程需要按照精确度从高到低的顺序，并且需要去除冗余，最终将结果 返回给查询接口模块。

Peer站点同样需要外部配置文件进行初始化的设置，其中主要的配置项包括：子进程 可用的RMI服务端口范围，查询时间限制，本地RMI服务相关配置项(IP地址和服务端 口号等)，启动子进程相关的参数(运行参数、子进程的监测时间间隔等)，同一索引集群 的Peer站点信息(IP地址、RMI服务端口号等)，以及Monitor站点信息(IP地址、RMI 服务端口号等)等。

对等站点子进程(Child Process)的实现：

对等站点子进程所涉及的实际上是由对等站点主进程启动的子进程，每个此类子进程 单独负责一个索引块的管理与查询。因此，单个Peer站点可能有多个子进程，同时对多个 索引块进行管理和查询。

对等站点子进程被主进程创建并启动时，由主进程指定RMI服务的端口、索引块文件 在分布式存储系统中的路径，以及主进程的服务端口号等。在子进程启动后，将通过分布 式存储系统的接口获取相应的索引块文件，并将其在内存中展开，映射好查询对象与特征 向量之间的关系，为后续的查询做准备。

作为RMI服务的调用方，子进程主要是通过调用主进程的RMI服务，对主进程进行心 跳检测，以保证当主进程异常退出时能自行关闭，避免占用过多的资源。

而作为RMI服务的被调用方，子进程主要提供的是search服务接口，实际上就是接受 主进程赋予的查询向量及相关请求，在内存中的Hybrid Spill Tree索引结构中进行查询，并 将最终的结果返回给主进程，由主进程进行结果整合和发送。

子进程的配置部分实际上是由主进程通过进程参数传进来的，无需外部配置文件。

负载软均衡模块(Balancer)的实现：

负载软局衡模块在系统中所承担的工作主要包括两部分，分别是接受Monitor站点的同 步要求，和为查询接口模块提供合适的可用的Peer站点，作为查询的主站点。

作为RMI服务的调用方，Balancer站点主要是在启动服务之后，通过调用Monitor站 点的服务进行注册，以告知Monitor站点开始接受Peer站点列表同步。

而作为RMI服务的被调用方，Balancer站点提供的服务接口主要包括： SynchronizeCluster和getAProperPeer。其中SynchronizeCluster服务接口主要被Monitor站 点调用，从而实现当前索引集群中有效Peer站点列表的同步功能；而getAProperPeer服务 接口则由查询接口调用，返回当前索引集群中可用的Peer站点。

Balancer站点的配置信息主要包括：Monitor站点信息(包括IP地址和RMI服务端口 等)，以及Balancer站点本身启动RMI服务相关的一些参数等。

查询接口模块(Searcher)的实现：

查询接口所负责的工作是接受外部查询请求，并将查询对象量化为特征向量，从 Balancer站点获取可用的Peer站点，作为搜索的入口，并将最终的搜索结果转化为外部接 口所需的形式。查询接口模块是上层应用与底层调度之间的连接部分，通过封装底层的通 信与调用关系，为上层应用的开发提供便捷的接口。因此，该部分模块实际上可以作为链 接库或者第三方包，提供给上层开发人员进行进一步的开发。

具体而言，查询接口模块需要实现四部分的功能：接受并量化查询对象，调用Balancer 站点获取可用的Peer站点，调用Peer站点执行搜索，以及搜索结果的处理。

查询接口的配置主要涉及Balancer站点的信息(包括Balancer站点的IP地址和服务端 口等)。

系统的连接与整体运作：

本发明所提出的基于对等结构的分布式高维索引并行查询框架具有较强的自组织性和 智能管理能力，对于系统各个模块的启动顺序并没有严格的顺序要求。但一般而言，建议 先运作索引创建模块，然后启动Monitor模块、Balancer模块和对等站点集群，最后启动查 询接口模块开始接受外部查询请求。另外，在系统连接方面，建议先进行集群的规划，并 且对各个模块的配置文件进行正确的配置，以保证系统能在启动后以较快的速度稳定下来， 并完成索引的加载等工作，以响应外部查询请求。

系统全部模块启动之后，需要对系统的整体运行情况进行较为全面的测试，特别是对 各种可能存在的异常情况的测试，以衡量系统的可靠性和稳定性。经过实际测试分析，本 发明提供的框架在可靠性和稳定性方面做得比较完善，能较好地抵抗多种宕机、主进程异 常退出、子进程异常退出等异常，整体运作情况良好。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个 或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分， 并且本发明的优选实施方式的范围包括另外的实现，这应被本发明的实施例所属技术领域 的技术人员所理解。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实 施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或 固件来实现。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可 以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中， 该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本发明各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各 个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既 可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以 软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读 取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、 或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包 含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定 指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的 一个或多个实施例或示例中以合适的方式结合。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解 在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变 型，本发明的范围由所附权利要求及其等同限定。