论文部分内容阅读
[摘要] 针对当前传统数据库技术对大数据进行分析时系统性能严重下降、查询效率受限的问题，本文研究分布式文件系统中数据读取关键技术。在分布式系统中，数据的存储结构直接影响着大数据的存储效率和处理性能，本文基于行列存储结构的特点，综合比较不同存储的模式在大数据应用中的优劣，展望未来研究与应用方向。
[关键词] 大数据；列存储；MapReduce；
1 引言
在信息化技术高度发展的今天，大数据应用变得日渐普及而且非常重要。鉴于传统关系型数据库在大数据应用领域应用时遇到的困难，基于分布式的海量数据管理是当前的研究热点，这就包括如何有效地存储和处理这些增长迅速的海量数据。
一半而言大数据的数据规模可以达到PB级，这就对存储空间和计算能力提出了很高的要求，大数据存储的数据类型多，复杂度高。大数据环境下，对数据存储的组织和管理提出了更高的要求。本文在分析列存储技术和分布式存储系统HDFS 局限性基础上，重点研究了数据存放结构，综述了各项关键技术当前的研究现状，分析了现有技术存在的问题探讨如何使用列存储技术提升大数据存储和处理的性能以提升大数据查询的效率，并展望了未来研究的发展方向。
2 列存储技术
2.1 列存储方式
自SIGMOD85会议论文A Decomposition Storage Model [ ] 提出了DSM概念以来， 经历30年的发展，在Stonebraker 、Abadi、 Boncz 等为首的一批数据库专家的大力提倡下， 列存储相关技术及应用快速得到了快速发展， 这种技术的特点是对复杂数据的查询效率高， 读取磁盘少， 存储空间占用少。这些特点使其大数据和OLAP应用存储的理想结构。
列存储是相对于行存储而言的，列存储最核心的技术就是基于垂直分区的存储设计和访问模式。列存储系统将数据库完全划分为多个独立的列的集合进行存储，图1展示了行存储和列存储的在物理存储设计上的本质区别，展示了3种数据库的存储方式，其中图 1（a） 和图 1（b））是两种列存储的方式，每一列单独保存Sales表中的每个属性数据对象，图1（c）是行存储形式。
列存储数据库只需查询读取涉及关系中某些数据列，避免无关列的提取，不像行存储那样需要从磁盘读取整行信息并去除不需要的属性信息，从而减少I/O和内存带宽的占用，提高查询效率。而且，同一列数据属性相同，可以使用针对性的压缩算法，因此压缩效率高。C-Store[ ]和Monet DB[ ]是其中有影响力的代表性成果，它们在存储结构、查询优化、压缩等方面进行了很多技术创新，使得列存储相比较行存储而言更适合大规模的访问和查询。
2.2 列存储关键技术
（1）压缩技术
Abadi D J [ ]在SIGMOD06会议上提出列存储的主要压缩方法有：行程编码算法、词典编码算法、位向量编码算法。
①行程编码算法（Run-length Encoding-RLE）
行程编码算法用一个三元组记录数据值。这个三元组记录包括数据出现的起始位置和持续长度（ 即行程） ，目的在于压缩原始数据的长度，适用于相同数据连续存储的情况，三元组描述为（ X，Y，Z） ，X 表示数据的值，Y 表示数据起始位置，Z 表示长度。举例而言假如在一个列中初始的50个元素中包含值‘W’，则这50个元素可以表示为三元组（‘W’， 1， 50）。
该技术适用于重复数据较多的的数据列，具有较好的压缩效果，缺点是对列值的重复性及排序要求较高。
②词典编码算法（Dictionary Compression）
词典编码算法将原始值转换成替代值存储在系统中，所以会产生 “原始值-替代值”对照词典，替代值的长度大大小于原始值的长度，从而达到压缩存储空间的目的。如图2 所示， 可以用简单的两位数字代替原始字符串， 从而缩短所需存储空间。
该算法对于数据类型要求较低，不要求数据排序，缺点是要创建词典表，维护成本高，如果数据重复性不高则词典表会过于庞大。
③位向量编码算法（Bit-Vector Encoding）
位向量编码是为每一个不同的取值生成一个位向量， 根据位向量（串）中不同的位置取值0或1 来对应并确定不同的原始值。位向量编码算法是轻量级的编码算法，可以直接在压缩数据上进行操作，可以降低CPU 成本。例如对以下的列存储数据：
该算法对数据类型要求不高，在有些情况下查询效率甚至高于词典编码，缺点是位置数据会因为取值空间的太大或者重复性低导致空间占用较大。
对于列存储主要应用的海量数据查询分析领域，有效压缩是一个十分重要的优势。
（2）延时物化
延时物化的主要优点在于允许对压缩态的列存储数据进行高性能操作，具备高效的压缩传输数据开销，通过延迟元组物化，尽可能少的进行元组物化，尽可能地避免了不必要的实际数据传输开销。
元组物化是将常用元组从实际物理存储的状态生成为实体化的元组， 即物化存储在内存中。在以后的查询中， 方便直接读取已物化元组， 从而提高查询效率。物化有提前物化和延时物化两种，提前物化在提交查询之前物化元组； 延时物化是推迟物化元组时间， 在查询最后时刻物化元组。对于列存储数据库而言， 提前物化需要解压压缩数据，时间和空间的开销都很大，而提前物化会涉及到很多不必要的列。
Abadi D J在文献[ ] 中， 详细介绍了两种物化方式的实验过程，证明延时物化许多性能上的潜力只有在列存储数据库中才能发挥。文献[ ]比较了提前物化和延时物化的优劣，在延时物化引入横向信息传递技术应用，有效解决了溢出连接产生的性能下降问题。
3 列存储技术在大数据分析中的 3.1 大数据分析的存储
国际数据中心（IDC）在2011 年的报告[ ]中定义了大数据： “大数据技术描述了一个技术和体系的新时代， 被设计于从大规模多样化的数据中通过高速捕获、发现和分析技术提取数据的价值”。 这个定义刻画了大数据的4 个显著特点， 即容量（volume）、多样性variety）、速度（velocity） 和价值（value）。大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化和软件系统开源化的特点。
现有大数据处理技术主要有对称多处理机架构（SMP）和大规模并行处理架构（MPP）两大类。在数据量极速增长的大数据背景下，计算分布和存储分布的MPP架构成为主流。MapReduce[ ]分布式并行计算是MPP架构的代表。Hadoop[ ]是MapReduce分布式计算框架的实现，为大数据处理大型分布式集群，通过分布式存储系统HDFS（ Hadoop Distributed File System）[ ]来管理海量数据。如何在HDFS 中设计一个高效的数据存储结构来组织大数据遇到了一系列的困难，而影响大数据查询分析性能的关键因素是能够满足充分利用MapReduce 计算特性来处理大数据。
3.2 大数据分析中的数据存储
基于Hadoop系统的数据仓库中，数据存储格式是影响数据仓库性能的一个重要因素，它直接影像如何高效的存储、管理和使用这写数据。在Hadoop运行环境中，数据的存储格式要满足以下几个特点： 数据加载数据要快、数据查询处理要快、 高效的数据存储空间利用率、适应高强度的动态负载模式。
对比图3中行列存储方式的不同，基于行存储的数据结构：优点是具备快速数据加载和动态负载的高适应能力，因为行存储保证了相同记录的所有域都在同一个集群节点；但是它不太满足快速的查询响应时间的要求，特别是在当查询仅仅针对所有列中的少数几列时，它就不能直接定位到所需列而跳过不需要的列，由于混合着不同数据值的列，行存储不易获得一个极高的压缩比，行存储不易获得一个较高的压缩比。
在面向列的文件存储结构中，列A和列B存储在同一列组，而列C和列D分别存储在单独的列组。这种结构使得在查询时能够直接读取需要的列而避免不必要列的读取，并且对于相似数据也可以有一个更好的压缩比。但是他的缺点也很明显，那就是由于元组重构的较高开销，它并不能提供基于Hadoop系统的快速查询处理，也不能保证不能保证同一记录的所有列都存储在同一集群节点之上，也适应高度动态的数据负载模式。
基于行列混合存储的RCFile[ ]，如图4所示，它即满足快速数据加载和动态负载高适应的需求外，也解决了数据查询处理的瓶颈。该存储结构遵循的是“先水平划分，再垂直划分”的设计理念。先将数据按行水平划分为行组，这样一行的数据就可以保证存储在同一个集群节点；然后在对行进行垂直划分。RCFile具备相当于行存储的数据加载速度和负载适应能力，在读数据时可以在扫描表格时避免不必要的列读取，它比其他结构拥有更好的性能，使用列维度的压缩能够有效提升存储空间利用率。
通过设计一个分布式文件存储格式（MapReduce column-store file，MCF），基于列存储的大数据分析系统物化策略，在MapReduce分布式并行处理环境中结合列存储技术对物化策略进行优化执行。
在数据加载中，利用列存储的特点提出数据存储的协同定位策略来优化数据的存储，在数据加载过程中进行数据的预处理，通过构建MapReduce早期物化策略、MapReduce延迟物化策略和MapReduce混合的物化策略，结合利用自适应物化集合调整策略避免物化集合的恶性膨胀。通过实验证明，物化策略和自适应物化集合调整策略有效地减少MapReduce过程的中间数据、网络带宽占用和不必要的I/O开销，较大提高大数据分析效率。
4 结束语
通过本文研究发现，行存储结构在数据加载的效率上优于列存储，但在数据压缩的效率很低，不能有效地提高磁盘利用率。列存储结构在数据压缩上有很好的压缩效果，因为跨数据节点访问使得数据加载及重构的时间较长，对系统I/O要求较高。行列相结合的数据存储结构可以结合行存储的高效数据加载和列存储的高效数据压缩效果，在大数据分布式系统中，行列数据存储结构极大地提高了大数据存储及处理性能，SAP HANA和HP VERTICAL等都是很好的商用系统的例子。
基于列存储的物化策略可以有效减少大数据调用过程中的中间数据为和元组重构的开销，减少网络带宽和I/0占用，极大提升大数据的查询效率。
研究同时发现在应用中应该着重于适用与不同数据类型的大数据压缩方法以及直接对压缩数据的直接访问及列存储的MapReduce 连接索引技术研究，进一步优化大数据查询性能。
[关键词] 大数据；列存储；MapReduce；
1 引言
在信息化技术高度发展的今天，大数据应用变得日渐普及而且非常重要。鉴于传统关系型数据库在大数据应用领域应用时遇到的困难，基于分布式的海量数据管理是当前的研究热点，这就包括如何有效地存储和处理这些增长迅速的海量数据。
一半而言大数据的数据规模可以达到PB级，这就对存储空间和计算能力提出了很高的要求，大数据存储的数据类型多，复杂度高。大数据环境下，对数据存储的组织和管理提出了更高的要求。本文在分析列存储技术和分布式存储系统HDFS 局限性基础上，重点研究了数据存放结构，综述了各项关键技术当前的研究现状，分析了现有技术存在的问题探讨如何使用列存储技术提升大数据存储和处理的性能以提升大数据查询的效率，并展望了未来研究的发展方向。
2 列存储技术
2.1 列存储方式
自SIGMOD85会议论文A Decomposition Storage Model [ ] 提出了DSM概念以来， 经历30年的发展，在Stonebraker 、Abadi、 Boncz 等为首的一批数据库专家的大力提倡下， 列存储相关技术及应用快速得到了快速发展， 这种技术的特点是对复杂数据的查询效率高， 读取磁盘少， 存储空间占用少。这些特点使其大数据和OLAP应用存储的理想结构。
列存储是相对于行存储而言的，列存储最核心的技术就是基于垂直分区的存储设计和访问模式。列存储系统将数据库完全划分为多个独立的列的集合进行存储，图1展示了行存储和列存储的在物理存储设计上的本质区别，展示了3种数据库的存储方式，其中图 1（a） 和图 1（b））是两种列存储的方式，每一列单独保存Sales表中的每个属性数据对象，图1（c）是行存储形式。
列存储数据库只需查询读取涉及关系中某些数据列，避免无关列的提取，不像行存储那样需要从磁盘读取整行信息并去除不需要的属性信息，从而减少I/O和内存带宽的占用，提高查询效率。而且，同一列数据属性相同，可以使用针对性的压缩算法，因此压缩效率高。C-Store[ ]和Monet DB[ ]是其中有影响力的代表性成果，它们在存储结构、查询优化、压缩等方面进行了很多技术创新，使得列存储相比较行存储而言更适合大规模的访问和查询。
2.2 列存储关键技术
（1）压缩技术
Abadi D J [ ]在SIGMOD06会议上提出列存储的主要压缩方法有：行程编码算法、词典编码算法、位向量编码算法。
①行程编码算法（Run-length Encoding-RLE）
行程编码算法用一个三元组记录数据值。这个三元组记录包括数据出现的起始位置和持续长度（ 即行程） ，目的在于压缩原始数据的长度，适用于相同数据连续存储的情况，三元组描述为（ X，Y，Z） ，X 表示数据的值，Y 表示数据起始位置，Z 表示长度。举例而言假如在一个列中初始的50个元素中包含值‘W’，则这50个元素可以表示为三元组（‘W’， 1， 50）。
该技术适用于重复数据较多的的数据列，具有较好的压缩效果，缺点是对列值的重复性及排序要求较高。
②词典编码算法（Dictionary Compression）
词典编码算法将原始值转换成替代值存储在系统中，所以会产生 “原始值-替代值”对照词典，替代值的长度大大小于原始值的长度，从而达到压缩存储空间的目的。如图2 所示， 可以用简单的两位数字代替原始字符串， 从而缩短所需存储空间。
该算法对于数据类型要求较低，不要求数据排序，缺点是要创建词典表，维护成本高，如果数据重复性不高则词典表会过于庞大。
③位向量编码算法（Bit-Vector Encoding）
位向量编码是为每一个不同的取值生成一个位向量， 根据位向量（串）中不同的位置取值0或1 来对应并确定不同的原始值。位向量编码算法是轻量级的编码算法，可以直接在压缩数据上进行操作，可以降低CPU 成本。例如对以下的列存储数据：
该算法对数据类型要求不高，在有些情况下查询效率甚至高于词典编码，缺点是位置数据会因为取值空间的太大或者重复性低导致空间占用较大。
对于列存储主要应用的海量数据查询分析领域，有效压缩是一个十分重要的优势。
（2）延时物化
延时物化的主要优点在于允许对压缩态的列存储数据进行高性能操作，具备高效的压缩传输数据开销，通过延迟元组物化，尽可能少的进行元组物化，尽可能地避免了不必要的实际数据传输开销。
元组物化是将常用元组从实际物理存储的状态生成为实体化的元组， 即物化存储在内存中。在以后的查询中， 方便直接读取已物化元组， 从而提高查询效率。物化有提前物化和延时物化两种，提前物化在提交查询之前物化元组； 延时物化是推迟物化元组时间， 在查询最后时刻物化元组。对于列存储数据库而言， 提前物化需要解压压缩数据，时间和空间的开销都很大，而提前物化会涉及到很多不必要的列。
Abadi D J在文献[ ] 中， 详细介绍了两种物化方式的实验过程，证明延时物化许多性能上的潜力只有在列存储数据库中才能发挥。文献[ ]比较了提前物化和延时物化的优劣，在延时物化引入横向信息传递技术应用，有效解决了溢出连接产生的性能下降问题。
3 列存储技术在大数据分析中的 3.1 大数据分析的存储
国际数据中心（IDC）在2011 年的报告[ ]中定义了大数据： “大数据技术描述了一个技术和体系的新时代， 被设计于从大规模多样化的数据中通过高速捕获、发现和分析技术提取数据的价值”。 这个定义刻画了大数据的4 个显著特点， 即容量（volume）、多样性variety）、速度（velocity） 和价值（value）。大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化和软件系统开源化的特点。
现有大数据处理技术主要有对称多处理机架构（SMP）和大规模并行处理架构（MPP）两大类。在数据量极速增长的大数据背景下，计算分布和存储分布的MPP架构成为主流。MapReduce[ ]分布式并行计算是MPP架构的代表。Hadoop[ ]是MapReduce分布式计算框架的实现，为大数据处理大型分布式集群，通过分布式存储系统HDFS（ Hadoop Distributed File System）[ ]来管理海量数据。如何在HDFS 中设计一个高效的数据存储结构来组织大数据遇到了一系列的困难，而影响大数据查询分析性能的关键因素是能够满足充分利用MapReduce 计算特性来处理大数据。
3.2 大数据分析中的数据存储
基于Hadoop系统的数据仓库中，数据存储格式是影响数据仓库性能的一个重要因素，它直接影像如何高效的存储、管理和使用这写数据。在Hadoop运行环境中，数据的存储格式要满足以下几个特点： 数据加载数据要快、数据查询处理要快、 高效的数据存储空间利用率、适应高强度的动态负载模式。
对比图3中行列存储方式的不同，基于行存储的数据结构：优点是具备快速数据加载和动态负载的高适应能力，因为行存储保证了相同记录的所有域都在同一个集群节点；但是它不太满足快速的查询响应时间的要求，特别是在当查询仅仅针对所有列中的少数几列时，它就不能直接定位到所需列而跳过不需要的列，由于混合着不同数据值的列，行存储不易获得一个极高的压缩比，行存储不易获得一个较高的压缩比。
在面向列的文件存储结构中，列A和列B存储在同一列组，而列C和列D分别存储在单独的列组。这种结构使得在查询时能够直接读取需要的列而避免不必要列的读取，并且对于相似数据也可以有一个更好的压缩比。但是他的缺点也很明显，那就是由于元组重构的较高开销，它并不能提供基于Hadoop系统的快速查询处理，也不能保证不能保证同一记录的所有列都存储在同一集群节点之上，也适应高度动态的数据负载模式。
基于行列混合存储的RCFile[ ]，如图4所示，它即满足快速数据加载和动态负载高适应的需求外，也解决了数据查询处理的瓶颈。该存储结构遵循的是“先水平划分，再垂直划分”的设计理念。先将数据按行水平划分为行组，这样一行的数据就可以保证存储在同一个集群节点；然后在对行进行垂直划分。RCFile具备相当于行存储的数据加载速度和负载适应能力，在读数据时可以在扫描表格时避免不必要的列读取，它比其他结构拥有更好的性能，使用列维度的压缩能够有效提升存储空间利用率。
通过设计一个分布式文件存储格式（MapReduce column-store file，MCF），基于列存储的大数据分析系统物化策略，在MapReduce分布式并行处理环境中结合列存储技术对物化策略进行优化执行。
在数据加载中，利用列存储的特点提出数据存储的协同定位策略来优化数据的存储，在数据加载过程中进行数据的预处理，通过构建MapReduce早期物化策略、MapReduce延迟物化策略和MapReduce混合的物化策略，结合利用自适应物化集合调整策略避免物化集合的恶性膨胀。通过实验证明，物化策略和自适应物化集合调整策略有效地减少MapReduce过程的中间数据、网络带宽占用和不必要的I/O开销，较大提高大数据分析效率。
4 结束语
通过本文研究发现，行存储结构在数据加载的效率上优于列存储，但在数据压缩的效率很低，不能有效地提高磁盘利用率。列存储结构在数据压缩上有很好的压缩效果，因为跨数据节点访问使得数据加载及重构的时间较长，对系统I/O要求较高。行列相结合的数据存储结构可以结合行存储的高效数据加载和列存储的高效数据压缩效果，在大数据分布式系统中，行列数据存储结构极大地提高了大数据存储及处理性能，SAP HANA和HP VERTICAL等都是很好的商用系统的例子。
基于列存储的物化策略可以有效减少大数据调用过程中的中间数据为和元组重构的开销，减少网络带宽和I/0占用，极大提升大数据的查询效率。
研究同时发现在应用中应该着重于适用与不同数据类型的大数据压缩方法以及直接对压缩数据的直接访问及列存储的MapReduce 连接索引技术研究，进一步优化大数据查询性能。