高维索引的并行化方案设计与实现.pdfVIP

高维索引的并行化

方案设计与实现

高维索引小组

组长：林梓佳

组员：文海龙

.

目标回忆

对外提供可移植性较强、扩展方便的高维索引系统；

针对海量数据索引需求，实现分布式高维索引机制；

提供高维索引机制的调用接口，方便上层调用，并

最终集成到LaSQL引擎中；

提供索引接口的使用文档【javadoc】

.

完成情况

设计并完成基于MapReduce框架的高维索引并行创

立模块

设计并完成基于MPI通信机制的高维索引并行查询

模块，并与创立模块整合成一个相对稳定、高效、

完整、独立、通用的高维索引系统

协助提供了其他小组所需的全部接口

目前数据支撑量为：1000000张图像

.

设计方案

.

高维索引创立模块

稳定性要求极高，实时性要求不是很高

方案：代码重构，MapReduce框架

实验情况：

5台普通PC：2G内存，奔腾E53双核CPU

1M图像，12维特征

耗时：~3小时〔底层伪接口：MySQL〕

实现情况：成熟框架，稳定性高

.

高维索引查询模块

实时性要求极高，稳定性要求也很高

方案：MapReduce框架无法满足实时要求，采取

MPI通信机制，需自行设计方案与消息体系，工作

量大

实验情况：

5台普通PC：2G内存，奔腾E5300双核CPU

1M图像，120维特征

未进行HybridSpillTree参数优化

批量查询相比单次查询耗时增幅小

.

查询模块方案特点

高度并行化，查询高效，精确度较高

两层次并行化：节点间的并行化，子进程间的并行化

高效的MPI通信机制

HybridSpillTree的冗余查询与结果聚合提升了精确度

系统可靠、稳定

对等结构：动态中心节点，减少瓶颈

智能调度：根据节点可用内存大小、负载能力分配索引

块，减少OutOfMemory等异常

引入监控节点用于协调索引块的更新、去重、补全等工

作，主进程与子进程间的相互监控，减少内存泄露

经测试，能对抗常规出现的异常情况，诸如各类节点宕

机、进程异常退出、索引检测出现异常等；.

查询模块方案特点

良好的可伸缩性和可扩展

支持动态增删各类节点机器，系统内部自动维护各类节点

的信息和集群信息【包括使用提供的外部命令进行节点变

动，和异常因素导致的机器宕机等】

HybridSpillTree的快速查询特点，以及方案的并行化特

点导致原那么上对机器数量和数据量没有过多限制

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

监控节点的引入，实时监测索引更新情况，当前索引的分

配情况与使用情况等，并提供报告

站点间的注册、注销和信息同步机制

智能调度，索引块的分配、去重与补全

平衡节点的引入，分配查询主站点，负载软均衡.

查询模块方案特点

接口通用，配置方便，独立性强

独立系统，不依赖于底层存储和上层应用

接口通用