[01372127]基于Hadoop的大数据索引和连接优化研究

我们迎来了大数据时代。为了从数据中发现知识并加以利用,指导人们的决策,必须对数据进行深入的分析,而不是仅仅生成简单的报表。这些复杂的分析必须依赖于复杂的分析模型,很难用SQL来进行表达,统称为深度分析（deep analysis）。数据分析的趋势和挑战是：（i）数据量的膨胀;（ii）数据深度分析需求的增长;（iii）数据类型不断多样化,包括各种非结构化、半结构化数据,对这些类型多样的数据进行管理和分析也是数据处理技术所面临的挑战。本项目围绕基于Hadoop的大数据索引和连接优化问题,提出了一种基于分层式HBase非主键索引的查询模型和方法,首先建立基于HBase的持久性索引,然后进一步提出了一种索引热点数据缓存技术和一种高效的热度累积缓存替换策略,以降低对HBase索引表的磁盘访问开销。进一步,我们提出了一种基于数据的热度标识数据的关联性,并按照数据的关联性将数据划分成块的数据管理方法。对于热数据分片,我们采用更精细的粒度以追求高的拟合精度和灵敏度,而对于冷数据,我们的分片粒度相对较大,以降低查询开销和搜索成本。在自适应分片数据管理方法的基础上,我们提出负载平衡的数据连接方法,将数据均匀地分布到集群各节点上,使得各个节点上分布的数据在空间开销和热度上都保持基本平衡。项目的考核指标是在国内外高水平学术期刊和国际会议上发表论文3-4篇,其中3篇以上被EI,SCI,ISTP检索。项目完成时,项目负责人作为第一作者或通讯作者发表高水平论文2篇以上。 项目实施期间,项目组成员实际完成技术指标情况如下： 在国内外高水平学术期刊和国际会议上发表论文7篇,其中6篇被EI检索,1篇为中文核心期刊。项目负责人作为第一作者发表论文3篇,均被EI检索; 获授权的发明专利1项,受理的发明专利2项;本课题研究提出了一种基于分层式的非主键索引的查询模型,该模型首先建立基于HBase的持久性索引。然后,为了利用内存提升查询性能,进一步提出了一种索引热点数据缓存技术,以降低对HBase索引表的磁盘访问开销。热点数据缓存克服了最近最少使用（LRU）算法的局限性。最近最少使用算法只关注数据最近一次访问时间、不关注数据访问频繁程度不同的局限性。因此,提出了一种考虑数据访问的累积热度,并对早前时间的热度累积进行指数衰减,从而更准确地捕获数据访问特征的热点数据缓存方法。同时在缓存空间未满的时候,采用“访问即插入”的缓存插入策略,保证缓存空间得到充分利用,缓存命中率在数据加载阶段可以得到快速提升并趋于稳定。而当缓存充满以后,热度累积的缓存替换策略会根据记录的热度累积评分选择“牺牲者”淘汰出内存,选择获得热度高分的记录保存在缓存中。为了使索引热点数据缓存内存层具有良好的可扩展性,设计了一种适应Hadoop集群环境的分布式缓存协议,支持高效的基于非主键的查询。 本课题研究提出了一种提高海量数据查询性能的正交多哈希映射索引方法,包括如下步骤： 1)在海量数据的查询属性上做第一层哈希映射,所有的数据记录经过第一层哈希函数映射后都被分配到特定的哈希桶中; 2)在第一层哈希的值空间上建立B+树,原线性搜索时间复杂度为O（n）,优化为树搜索,树搜索时间复杂度为O（log n）,优化对哈希映射值的搜索; 3)通过第二层哈希函数对第一层哈希桶进行再次哈希映射,即把第一层哈希桶进行再次划分,以降低哈希桶内数据容量; 4)在相邻两层哈希桶之间建立指针连接,下一层哈希是对上一层哈希桶的再次划分,多次的正交哈希形成树状的索引层次结构,哈希桶是否再划分取决于哈希桶目前的数据量,当哈希桶个数超过指定的预警阈值后就停止划分,正交多哈希索引建立完成。