吴广君1王树鹏 1 陈明2李超3
1(中国科学院计算技术研究所北京 100190)
2(北京邮电大学100786)
3(国家计算机网络应急技术处理协调中心北京100029)
wuguangjun@software.ict.ac;
摘要Big Data是近年在云计算领域中出现的一种新型数据管理模式，具有存储数据量大、检索效率高等需求特点。传统关系型数据库系统在数据存储规模、检索效率等方面不再适用。目前的分布式No-SQL数据库可以提供分布式数据存储环境，但是无法支持多属性检索、数值统计等复杂查询功能。本文结合Hadoop框架，设计并实现分布式海量结构化数据存储检索系统（MDSS）。系统采用列存储结构，结合全文索引技术和分布式B+ Tree索引技术管理结构化数据源。在此基础上讨论复杂查询条件的查询任务分解机制，支持大数据的多属性检索、模糊检索以及统计、分析等查询功能。MDSS可以有效解决海量结构化流数据存储与数据多属性检索等问题。实验结果表明，本文提出的分布式结构化数据管理技术和查询任务分解机制可以显著提高分布式条件下大数据集的查询效率，适合应用在日志类数据，流记录数据 等海量结构化数据的存储应用场合，并为进一步研究云存储中“大数据”的存储，检索等相关问题提供理论和实验基础。
关键词 Big data; Hadoop；数据检索；No-SQL数据库; 海量数据存储
中图法分类号 TP393
Massive Structured Data Oriented Storage and Retrieve System
单晶硅生产工艺WU guang-jun1 WANG shu-peng 1 CHEN ming2 LI chao3
1(Institute of Computing Technology Chinese Academy of Sciences, BeiJing, 100190)
700755
2（BeiJing University of Posts and Telecommunications,BeiJing,100786）
3(National Computer network Emergency Response technical Team/Coordination Center of China, Beijing, 100029)
Abstract Big Data has emerged as a new type of data in the cloud computing. It stores large amounts of data with high query efficiency. The traditional RDBMS is no longer fit to manage Big Dat
a in face of the large storage size and high query efficiency. Currently, the No-SQL(Not Only SQL) DB can provide distributed storage environment, but it is in the limitation of query capability. We design and implement distributed Massive Data Storage System (MDSS) for structured data based on Hadoop. MDSS adopt column-based storage structure and use full-text indexing and distributed B+ tree to manage data source. The query planning mechanism was built for multi-attributes query, fuzzy query and data statistics query based on MDSS. MDSS can resolve query capability problems for massive structured data storage. The experiment results exposed that the techniques for distributed structured data and query planning methods can improve Big Data query efficiency significantly. MDSS is suitable to manage massive structured data, such as log-structured data, streaming data etc. and the most important is that MDSS provide valuable knowledge for further research on the storage and retrieve techniques for massive structured data in cloud storage.
Key words：Big Data; Hadoop; Data Query; No-SQL DB; Massive Storage
投稿日期: 2011-07-17；修改日期:
基金项目：国家自然科学基金项目 (61003260)；“八六三”高技术研究发展计划项目（863计划）(2009AA01A403, 2007AA010501, 2007AA01Z467, 2007AA01Z474)。
Foundation Items: The National Natural Science Foundation of China(61003260);The National High Technology Research and Development Program of China(863 Program)(2009AA01A403, 2007AA010501, 2007AA01Z467, 2007AA01Z474).
1引言
驳接头Big Data是近年在云计算领域提出的对数据的加载效率、存储规模以及数据的检索效率有很高要求的应用场合，通常数据的加载效率在Mb/s甚至Gb/s量级，数据的存储规模在TB甚至PB规模，本文称这种模式为“大数据集”管理。大数据集的一类重要应用针对结构化数据的存储与检索。典型的应用如海量日志、网络报文以及web2.0框架下的SNS，电子商务，数据挖掘等应用场合。传统的RDBMS由于数据一致性的约束，在管理大规模数据集存储条件下，在数据更新、局部数据失效以及系统扩展性等方面工作效率低下[1][2]。目前的解决思路是：通过放宽对于数据一致性的要求，取消复杂的关联查询，结合具体的应用场景，提高系统的可用性。但是由于大量的记录存放于同一个表空间中，会达到数十亿条甚至上百亿条记录的规模。在如此大规模数据存储条件下，如何高效的实现数据的存储、检索都面临着新的挑战。
Google对这一问题进行深入分析，结合Google 的业务背景，提出Bigtable数据管理方法[3]，建立列存储数据结构，提供基于Row-Key的数据检索接口。此后，业界也纷纷提出分布式结构化数据存储管理
模型，也称为No-SQL（Not Only Sql）数据库。典型的No-SQL数据库包括Dynamo[4]，Cassandra[5], PNUTS[6]，Hbase[7]以及Hypertable[8]等：Dynamo是Amazon提出的基于DHT的分布式数据存储与检索系统，数据存储与检索通过DHT算法实现，重点解决电子商务中数据的实时更新问题，即使在发生分区节点失效时仍然能够保证数据的写可用性，数据的冲突处理放到数据读操作时解决。Hbase和Hypertable是根据Bigtable思想实现开源分布式结构化数据存储管理系统。采用稀疏列存储结构，数据组织成有序表结构，对外提供基于Key的单条记录查询和基于Key区间批量记录查询功能。Yahoo！的PNUTS结合了上述两种方法，实现了有序表和分布式hash两种数据管理策略，并提供具有跨地域数据容错、副本容灾等管理机制。
但是目前的海量结构化数据管理系统对于数据检索的多属性支持较弱，通常仅提供基于Key的读取GET和写入PUT操作，不具备多属性查询，数值统计、分析等复杂的查询功能。当需要检索多字段属性构成的检索条件时，都需要转化为对于主键的查询或者是通过扫描记录再结合谓词过滤方法。这类技术在实现相对复杂的查询条件时，数据检索效率低、查询延迟大。目前部分公司已经开始研究基于No-SQL数据库的数据组织问题[9]，提高数据的检索效率。
目前基于Hadoop提出的数据仓库工具HIVE、PIG等，可以支持复杂的查询条件，但是不适用于流数据的高效存储与检索。如HIVE仅支持文本文件的批量导入，不支持流数据在线频繁加载操作。在复杂条件的检索过程中HIVE会把查询条件分解成多个MapReduce任务，每个Map过程以及Reduce结果都
要把文件写入到集文件系统中进行缓存，导致系统检索效率低，不适用于流数据的高效存储与查询。
针对该问题，本文基于Hadoop建立面向结构化流数据提出具有在线数据加载和快速检索的分布式数据存储系统MDSS(Massive Data Storage System)，建立二维表空间数据管理模型，重点解决数据的分布存储与复杂条件的快速查询问题。
2 MDSS系统工作原理
数据加载
数据查询
图1 MDSS系统结构图
伸缩杆“大数据集”要求较高的数据加载效率、数据存储效率以及数据检索效率，目前主要的解决思路是利用多机协同的分布式存储环境提高系统的处理效率。MDSS分布式系统结构如图1所示，系统包括三个部分：加载机集、查询机集、元数据节点集以及存储节点集。
加载机集：整个系统的数据加载端。可以以进程为单位，在多台设备上同时建立多个并发数据加载客户端，通过并发加载提高系统整体加载效率。在MDSS中，加载机集同时缓存近期入库的数据，经过固定的时间周期，把缓存数据通过Gb Ethernet写到数据存储管理装置中。
查询机集：用户在查询机上发出查询指令，查询机根据元数据节点集保存的元数据信息，向存储节点分发查询任务，最后汇总多个存储节点返回的查询结果，提交给用户；
存储节点集：持久存储长期保存的历史数据。把数据源进行分块存储，通常把一次或几次从加载机刷新到集中的数据作为数据分块。
烟花生产元数据节点集：用来协调整个集的工作，查询子任务的并发执行，保存整个系统工作所需的元数据信息。元数据节点集存储的元数据包括：系统节点状态信息；索引分片具体的存储位置信息；表空间元数据、每个表空间的一些辅助信息以及系统的工作日志等。MDSS系统主要支持分布式的数据存储和检索，具体数据查询流程如图2所示。
图2 MDSS系统检索工作原理示意图
①用户在查询机上提交查询请求；
②查询机根据具体的查询任务，向元数据节点查询对应表空间元数据和检索所需的元数据信息；
③元数据节点集根据查询条件，提供检索所需的元数据，例如：对应的表空间结构数据，索引分块与节点的映射关系等；
④查询机根据元数据信息，建立查询规划，决定向哪些存储节点发送查询命令。某些查询可以利用元数据信息优化查询过程。由于加载机会缓存有近期的数据，针对近期数据的查询会发送到加载机；
⑤数据存储节点根据检索条件，检索符合条件的数据集，并发回给查询机，查询机对查询结果进行最后的汇总、统计，以及必要的后期数据处理工作；
⑥查询机对结果集按照用户指定的格式封装，返回给查询用户，完成一次完整的数据查询过程。
在上述检索过程，涉及两个核心的问题是：存储系统采用何种数据存储模型以及针对复杂查询条件的具体的任务分解方法，下面分别在第3部分介绍MDSS采用的数据模型；在第4部分介绍复杂查询条件的任务分解机制。
3MDSS中数据模型与存储结构
3.1数据模型
MDSS为用户提供二维表空间数据管理模型。一行代表一条记录，每行内包含多个字段或属性。表空间利用表结构描述字段类型。目前表结构支持的数据类型包括：INTEGER(或INT)，IPFIELD，INDEX，TIMESTAMP和STORE五种数据类型。INTEGER是整数类型，支持大于，小于，等于数学比较运算；支持SUM，AVG，MAX，MIN等统计运算。IPFIELD存储IP类型字段，支持子网查询，区间查询；进一步分为IPV4_ADDR和IPV6_ADDR两种数据格式，分别用来保存IPV4的地址和IPV6的地址。INDEX存储字符类数据源，支持精确匹配，模糊匹配等查规则。TIMESTAMP存储时间类型字段，支持精确查。STORE直接存储数据，不支持基于内容的查询，通常存储BLOB类型数据源。
数据类型由表结构元数据文件描述。表结构文件在创建表空间时生成，保持到元数据节点集中。针对一条DNS访问记录，创建的表空间以及使用的语句如下；
CREATE TABLE DNS_TABLE (DOMAIN INDEX, VALUE IPFIELD, COUNT INTEGER, TIME TIMESTAMP);
其中：DOMAIN 字段是INDEX 类型，记录域名字符串数据；VALUE 记录域名对应的IP 地址，使用IPFIELD 字段；COUNT 记录一段时间内域名被解析总的次数，采用整数表示；TIME 表示记录产生的时间戳，使用定长的字符串表示。向DNS_TABLE 表空间加载一条记录可以使用如下命令：
INSERT
INTO
DNS_TABLE
VALUES
(‘’,‘192.16.18.10’,‘10’, ‘20110628101010’);
在数据加载过程中，需要根据存储的表结构进行字段类型的判断，符合表结构的字段类型加载到数据库中，否则提示错误信息，直接返回。
图3基本数据模型
MDSS 支持的基本功能如表1所示，目前MDSS 不支持UPDATE 操作。
表1 MDSS 基本操作方法描述
3.2数据存储组织结构
数据存储格式主要分为两种类型：STORE 类型和字符类型。STORE 类型直接存储文件信息，对数据内容的解析由用户完成。字符类型存储方式把数据源以字符方式分块存储。字符存储方式可以在异构存储环境中自由的迁移，具有更大的灵活性。字符类型可以处理数据类型包括：INDEX ，IPFIELD ，TIMESTAMP 以及INTEGER 等，在数据加载时根据表结构定义的数据类型进行数据转换。比如整数10在字符类型中需要存储00000010。这部分的转换工作在加载机上实现。
数据在存储节点上采用列存储结构，把字段值按照字典序排序存储，不同字段分别保存到文件的不同位置，一定长度的数据作为一个单独的文件保存，称为索引分片，索引分片是并发检索和分布存储的基本单位，目前通常以加载机一次或几次刷新到集中的数据源作为一个索引分片单位。
在每个索引分片内部引入块内索引，用来标记索引分块内部不同字段属性数据的具体存储位置。索引块的大小通常使用固定大小空间存储，便于一次性加载到内存中进行数据统计，目前是4K 大小。索引分片在存储节点上采用gzip 压缩算法进行数据压缩，由于内容相同的字段根据字典序排序后相邻存储，因此引入压缩技术会显著提高数据的存储效率。
在日志、流记录等应用场合，时间属性是最常
用的检索属性，MDSS 采用时间属性对数据进行分区管理，索引分片之间保持时间有序。同时建立基于时间属性的分布式B+ Tree ，加快分区数据的检索过程。B+ Tree 的叶节点保存每个索引分片对应的最大时间属性和索引分片的存储节点的位置。分布式B+ Tree 保存在元数据节点集中。具体结构如图4所示。
图4 数据组织结构图
分布式存储系统都面临着数据容错，负载均衡等问题。MDSS 利用副本实现数据容错功能，在数据加载时进行数据负载均衡处理。元数据节点集基于zookeeper 建立，根据zookeeper 配置规则，实
现元数据容错以及节点失效处理，此处不再详细介绍。
索引分片数据作为基本的调度和计算单位，持久存储到存储节点上。当数据从加载机刷新到存储节点集时，根据设置的副本冗余度和集存储节点列表，按序选择可用的存储节点，写入数据。当设置副本冗余度时，加载机会选择不同的节点分别写入数据。
在数据检索时，一个索引分片检索结果如果超过返回时间限制，可以选择对应的索引分片的副本重新执行检索操作，实现数据容错功能。限于篇幅，关于数据详细的组织方式不再详述。
4. MDSS 数据检索方法
MDSS 执行复杂查询条件的基本原则是对查询条件划分成查询子任务，每个子任务在分布式环境下的不同层次上并发实现。查询条件的分解和查询子任务的划分，既要保证查询语义的正确性，同时需要充分考虑分布式环境下影响数据检索的多种因素，充分发挥分布式环境下并发、并行的计算能力。KU波可调电衰减器
4.1查询条件分解
为了支持二维表空间的相关操作，实现结构化数据的统计与检索，MDSS 设计了一种针对单表空间内面向流记录的数据统计与分析语言，语法规则与标准的SQL 相同，但是取消了标准SQL 中关联查询，嵌套查询，视图等复杂的检索功能，本文简称为MQL 语言，具体支持的查询功能如下：
表2 MQL 支持的基本功能
具体的查询任务可以是由上述多种子查询语句构成的具体查询条件，为了快速执行相对复杂的查询计划，MDSS 把具体的查询条件分解为三类基本条件，每类基本条件作为一类查询子任务。
分区查询条件：分区查询条件直接定位于满足查询条件的目标索引文件，大大缩小海量数据的查询范围。是最先执行的查询条件。这类条件的特点是每个表空间只能设置一种分区查询条件，相当于关系型数据库的聚簇索引。MDSS 选择时间属性作为分区查询条件；
过滤查询条件：结构化数据每条记录由多个字段组成，每个字段可以独立设置查询条件。字符类属性支持模糊查询，数字类的支持比较查询等。多个过滤查询条件之间通过逻辑运算符号AND OR NOT 进行连接，构成多个逻辑组合查询条件。AND OR NOT 之间满足基本的集合运算关系；
统计分析查询条件：统计分析类查询条件主要用于经过分区查询条件、过滤查询条件后返回的结果集，实现面向全局数据集的统计、分析操作。具体的查询条件包括：数据分组操作（GROUP BY ），
数据排序操作（ORDER BY ），TOP-K ，以及统计函数，如SUM ，AVG ，MAX ，MIN 等。这类条件的特点是需要建立在获得全部符合条件的数据集基础上实现的数据统计、分析后获得正确结果。具体查询任务的分解流程如下图所示。
图5 查询条件分解流程
4.2查询子任务的并发执行与数据汇总
在分布式环境下，可以把一个具体的复杂查询任务按照上述分类方法分解成三类基本查询条件，每类查询条件对应一种查询子任务，利用分布式环境下的不同层次执行具体的查询子任务。其中分区类查询条件结合元数据信息在具体的存储节点上进行索引文件级别的查询；过滤类查询条件针对目标索引文件内的具体记录进行过滤，这两类条件在多数据存储节点中并发执行。统计分析类查询条件在查询机上，针对过滤类查询条件返回的结果集进行汇总后再进行统一计算处理，保证查询语义的正确性。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议