Hadoop云存储中基于Ordinal Bloom filter的多维索引关键技术研究

The current research of auxiliary multi-dimensional Cloud storage index based on hash data structure is not enough. This project intends to propose a new probabilistic data structure called ordinal bloom filter(OBF) and analyze its performance, so that it can adapt to the dynamic changes in Cloud storage. Then we will investigate how to setup an auxiliary multi-dimensional Cloud storage index in Hadoop, and how to comprehensively integrate the multi-dimensional index into Hadoop's MapReduce framework. This index can enhance the Hadoop search performance and should be easy to maintain. Furthermore, This project also attempts to establish an evaluation model (cost model), based on which different research works (such as index compression, performance, space utilization etc.) will be carried out. This project aims to put forward new theories, methods and solutions for Hadoop multi-dimensional index. The key technologies breakthrough will have great significance for the future of Cloud storage index and mass data filtering, as well as some important theoretical issues, such as how the probabilistic data structures contribute to the Cloud storage dynamical adaptability.

针对当前云存储辅助多维索引中基于哈希结构的索引研究不足的现状,本项目拟研究并提出新型概率数据结构Ordinal bloom filter(OBF)，并对其性能进行建模分析与评价,使其能适应云存储动态变化的需求。以此为基础，在Hadoop存储系统中研究构建多维索引结构，该结构能够和Hadoop中MapReduce框架有效整合，提高Hadoop的检索效率，并便于维护。除此之外，本项目还尝试建立一套相对完整的评价模型（cost model），将这一模型作为后面一系列优化工作的基石。再针对不同的索引优化目标（如：索引的压缩、性能，空间利用率 等等）来开展研究工作。本课题针对Hadoop云环境下辅助多维索引的特性，提出新的理论、方法和解决方案。其关键技术的突破，对于未来云存储索引效率提高和海量数据过滤，以及一些重要理论问题，如概率哈希数据结构对云存储的动态适应性等做出有意义的提示。

随着大数据时代的到来，hadoop成为海量云存储的重要基础平台，对云存储辅助多维索引中的研究亟待加强。本项目综合深入探讨了新型概率哈希结构（Ordinal Bloom filter）、多维索引结构与hadoop数据存储的有效整合机制、多维索引的优化手段和机制。1）在全面总结、分析现有哈希结构设计方法的基础上，依据动态调整的原则，首次提出了新型数据结构Ordinal Bloom filter，为同类结构设计提供了可参考依据。 设计了该结构的插入、删除、查询算法。证明了错误率。进行了严格测试。并在网络上开源该项目源代码。2）深入研究了多维索引与Hadoop的整合机制，探索了多维索引结构与Hadoop运行框架的融合问题，明确了在整合框架中多维索引与Hadoop的层次关系，以及它们之间的交互关系和交互顺序，通过层次设计、接口规范等约束条件来保证多维索引与Hadoop的整合。3）在此基础上，深入研究了索引应用环境的参数配置和形式化描述机制，通过设计一套符号语言用来描述潜在的各种应用场景（即profile），使其能够对参数空间、环境空间、中间交互空间等进行相应描述。研究并设计索引分析器，以索引环境Profile为分析对象，构建机器学习模型，实现索引的自动化分析和优化。