基于Hadoop的行列混合存储模型研究

发布时间：2019-05-31 17:50

【摘要】：信息技术的发展日新月异,随着互联网规模的扩大和PC机、移动设备、通讯终端的不断加入,每天产生的数据量以TB级甚至PB级的规模增长,整个世界已经进入了“大数据时代”。庞大的数据量给生产应用带来了新的机遇和挑战,也同时给科研工作者带来了更多的研究课题,如何对大规模的数据进行有效存储和快速查询便是其中的两个研究热点。Hadoop作为一种处理大数据的开源框架,能够实现海量数据的分布式存储和并行查询,被拥有大量用户群体的知名公司广泛使用,同时也受到了科研工作者的普遍青睐。现有的研究结果表明,数据存储模型是影响数据访问速度的关键因素,在Hadoop框架下的大数据查询处理中显得更加重要。目前已有几种基于Hadoop的分布式数据库系统,它们分别使用不同的存储模型管理不同类型的数据。这些存储模型能够有效地支持复杂的数据类型,支持半结构化甚至无结构化的数据的存储和查询,但是对于结构化数据的访问性能反而不如单机下的关系数据库。最常用的关系型数据存储模型分为三种:行存储、列存储和行列混合存储。行存储模型适用于以写操作为优先的事务型数据,它的优点在于数据导入速度快并且不需要元组重构,缺点是无法避免全表扫描,并且数据压缩性能低下;列存储模型适用于以读操作为优先的分析型数据,它的优点在于能够按照查询需求读取指定的列,并且具有较高的压缩性能,缺点在于数据导入速度较慢,实时更新效率低下,尤其在Hadoop下的元组重构操作将带来额外的网络传输开销;行列混合存储模型同时吸取了行存储和列存储的优点,而且回避了这两种存储模型的大多数缺点,虽然在查询处理方面达到了比较理想的性能,但是它仍然有可以改进之处,例如它无法实现数据的快速定位,影响随机读写性能和索引技术的应用。本文设计了一种Hadoop下的页式行列混合存储结构PageFile,并结合索引技术、多表连接优化技术和数据压缩技术进行了深入研究并取得了多方面的研究成果,进一步提升了在分布式环境下大数据的查询处理性能。本文的研究成果主要包含以下几个方面:(1)针对Hadoop下现有的行存储、列存储以及混合存储模型各自的优缺点,本文提出了一种页式行列混合存储模型,以及它在Hadoop下的存储结构PageFile,并为此设计了数据导入算法和元组重构算法,实现了单表查询功能。该模型继承了传统关系数据库使用页式存储的特性,把每个数据文件均匀地划分成固定大小的页。同时,它又采用了混合存储模型“先水平划分成行、后垂直划分成列”的原则,把关系表的水平划分存放在同一个数据文件,每个文件内部以属性列的形式垂直划分。这样,每个页的内部存放属于同一列的数据。该模型具有页式存储的快速定位优点,即能根据页的编号能够迅速查找到对应数据的取值,解决了随机读写的问题,弥补了当前hadoop下混合存储结构无法创建索引的不足;同时,行列混合存储模型本身的数据划分思想使得它既能够在查询时避免扫描与查询无关的列,又能够在元组重构时避免额外的网络开销。因此,该存储模型能够有效提高查询处理的速度。实验结果显示,本文的页式行列混合存储模型与现有的行列混合存储模型相比,不但占用更少的数据存储空间,而且数据导入速度几乎不变,具有更优的单表查询性能。(2)使用索引技术可以跳过无效数据的访问,快速定位到所需要的记录位置,既节省了扫描时间又减少了磁盘i/o,从而提高查询速度。目前hadoop下关于索引的研究非常少,在仅有的两个研究成果中,在索引的创建阶段都需要预先知道关系表之间的连接信息,并且索引的作用域非常小,具有一定的局限性。本文引入了单机下的rb+树结构和用于范围查找的哈希桶结构,结合pagefile的页式分布存储特性,提出了“多rb+树索引”和“多范围哈希索引”的思想,分别实现了它们的创建和查询算法,并对这些算法的性能进行了理论评估。多索引的思想首先使得任意属性列上都可以拥有多个rb+树或者多个范围查找哈希文件,不再局限于特定的属性。其次,它在索引创建时把输入数据划分成多份同时进行创建,在索引查询时对多个索引同时进行查找,充分发挥了hadoop并行性的特点。最后,各索引之间互相独立,当关系表发生数据追加操作时,只需要为对应属性列上的新数据创建新索引,不影响已有索引中的内容和结构,节省了索引维护的开销。此外,在多rb+树索引中,索引的作用域被扩展到文件级,这样可以跳过扫描与查询无关的文件。但是,使用多索引进行查询需要额外的mapreduce作业,根据算法性能的理论评估,多索引查询性能与扫描的索引文件数目和字节数有关,而属性列的选择率是其中的根本因素。实验结果显示,当选择率小于5%,甚至是等值查询时,多rb+树索引的性能更优;当选择率大于5%并且小于30%时,多范围哈希索引性能更优。(3)查询优化是提高数据处理速度的重要因素,其中多表连接查询最为常用。在hadoop框架下,一个复杂的多表连接查询通常由包含大量i/o操作的多个mapreduce作业组成或者仅由包含大量网络传输开销的单个mapreduce作业组成,并且查询产生的中间结果随着查询的结束而即时删除,不能被将来的查询利用。因此,生成合理的查询执行计划,尽可能地减少作业数目和作业内部的操作复杂度,使得由于重复读写、读取无效数据、网络传输等开销造成的代价达到最小,是查询优化的目标。每个多表连接查询能够表示成一个连接关系图,根据图中顶点和边的各项属性值可以把连接查询类型分为星型连接、链式连接和混合连接。本文提出了一种基于pagefile的自适应的多表连接策略amjo,它包含两个方面:首先,它能够根据不同的连接模式选取不同的连接算法,并把其中复杂的混合连接模式分解成多个简单的星型连接模式和链式连接模式,进而建立代价模型确定最优执行顺序,并以此生成最优执行计划。其次,它针对Hadoop下的复杂查询需要多个作业的特点,能够对已有的查询中间结果进行重用,并生成最优重用方案,简化复杂的连接模式,减少作业数目和冗余操作。实验结果显示,AMJO生成的查询执行计划要优于Hadoop下的同类产品,并且使用索引技术能够在低选择率的过滤属性下发挥巨大的作用,同时使用中间结果重用方案能够显著地节省查询时间,提升查询性能。(4)数据压缩是数据库管理系统中的关键技术,其主要作用是节省磁盘空间和提高查询效率,尤其是在分布式环境下,对大数据进行有效的压缩显得尤为重要。当前Hadoop下的数据压缩方法简单直接,即使用某种重量级压缩算法对整个数据文件进行压缩,虽然压缩性能较高,但是不能直接在压缩数据上进行查询,并且解压缩速度较慢,最终影响查询性能。因此,不同类型的数据应该适合于不同的压缩方法,对于同一属性列中的数据,其数据分布特征也能够显著影响压缩效果。本文研究了现有的轻量级压缩算法和Hadoop下压缩技术的应用现状,提出了一种启发式的区级压缩策略(HDCE),选择PageFile下的区为粒度对数据进行压缩,即根据区内属性值的数据类型和分布情况选择合适的轻量级压缩算法,并且能够在压缩数据上直接进行查询操作。在压缩数据的存储方面,本文详细介绍了压缩数据的存储格式和压缩数据导入时生成HDCE决策树的过程;在压缩数据的查询方面,本文具体描述对压缩数据中过滤属性、连接属性和选择属性的处理算法,包括过滤属性的直接运算和判断、连接属性和选择属性的按需实时解压。实验结果显示,HDCE产生的压缩数据虽然在存储性能上不如Hadoop下的部分重量级压缩算法,但是在查询性能上能够体现显著的优势。
[Abstract]:......
【学位授予单位】：东华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13

【相似文献】