海量结构化数据存储检索系统-中科院计算所-吴广
第 卷 计 算 机 研 究 与 发 展 Vol. , Supp .20XX 年X 月 JOURNAL OF CO
第 卷 计 算 机 研 究 与 发 展 Vol. , Supp .
20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
海量结构化数据存储检索系统
吴广君1 王树鹏1 陈明2 李超3
1(中国科学院计算技术研究所 北京 100190)
2(北京邮电大学 100786)
3(国家计算机网络应急技术处理协调中心 北京100029) ;
摘要 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)
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 Data 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).
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1引言
Big Data 是近年在云计算领域提出的对数据的加载效率、存储规模以及数据的检索效率有很高要求的应用场合，通常数据的加载效率在Mb/s甚至Gb/s量级，数据的存储规模在TB 甚至PB 规模，本文称这种模式为“大数据集”管理。大数据集的一类重要应用针对结构化数据的存储与检索。典型的应用如海量日志、网络报文以及web2.0框架下的SNS ，电子商务，数据挖掘等应用场合。传统的RDBMS 由于数据一致性的约束，在管理大规模数据集存储条件下，在数据更新、局部数据失效以及系统扩展性等方面工作效率低下[1][2]。目前的解决思路是：通过放宽对于数据一致性的要求，取消复杂的关联查询，结合具体的应用场景，提高系统的可用性。但是由于大量的记录存放于同一个表空间中，会达到数十亿条甚至上百亿条记录的规模。在如此大规模数据存储条件下，如何高效的实现数据的存储、检索都面临着新的挑战。
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
加载机集群：整个系统的数据加载端。可以以进程为单位，在多台设备上同时建立多个并发数据加载客户端，通过并发加载提高系统整体加载效率。在MDSS 中，加载机集群同时缓存近期入库的数据，经过固定的时间周期，把缓存数据通过Gb Ethernet 写到数据存储管理装置中。
查询机集群：用户在查询机上发出查询指令，查询机根据元数据节点集群保存的元数据信息，向存储节点分发查询任务，最后汇总多个存储节点返回的查询结果，提交给用户；
存储节点集群：持久存储长期保存的历史数据。把数据源进行分块存储，通常把一次或几次从加载机刷新到集群中的数据作为数据分块。
元数据节点集群：用来协调整个集群的工作，查询子任务的并发执行，保存整个系统工作所需的元数据信息。元数据节点集群存储的元数据包括：系统节点状态信息；索引分片具体的存储位置信息；表空间元数据、每个表空间的一些辅助信息以及系统的工作日志等。MDSS 系统主要支持分布式的数据存储和检索，具体数据查询流程如图2所示。
图2 MDSS系统检索工作原理示意图
①用户在查询机上提交查询请求；
②查询机根据具体的查询任务，向元数据节点查询对应表空间元数据和检索所需的元数据信息；
③元数据节点集群根据查询条件，提供检索所需的元数据，例如：对应的表空间结构数据，索引分块与节点的映射关系等；
④查询机根据元数据信息，建立查询规划，决定向哪些存储节点发送查询命令。某些查询可以利用元数据信息优化查询过程。由于加载机会缓存有近期的数据，针对近期数据的查询会发送到加载机；
⑤数据存储节点根据检索条件，检索符合条件的数据集，并发回给查询机，查询机对查询结果进行最后的汇总、统计，以及必要的后期数据处理工作；
⑥查询机对结果集按照用户指定的格式封装，返回给查询用户，完成一次完整的数据查询过程。
在上述检索过程，涉及两个核心的问题是：存储系统采用何种数据存储模型以及针对复杂查询条件的具体的任务分解方法，下面分别在第3部分介绍MDSS 采用的数据模型；在第4部分介绍复杂查询条件的任务分解机制。
3
MDSS 中数据模型与存储结构
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);
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
其中：DOMAIN 字段是INDEX 类型，记录域名字符串数据；VALUE 记录域名对应的IP 地址，使用IPFIELD 字段；COUNT 记录一段时间内域名被解析总的次数，采用整数表示；TIME 表示记录产生的时间戳，使用定长的字符串表示。向DNS_TABLE表空间加载一条记录可以使用如下命令：
INSERT
INTO
DNS_TABLE
VALUES
(‘www.xx.com’,‘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 配置规则，实
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
现元数据容错以及节点失效处理，此处不再详细介绍。
索引分片数据作为基本的调度和计算单位，持久存储到存储节点上。当数据从加载机刷新到存储节点集群时，根据设置的副本冗余度和集群存储节点列表，按序选择可用的存储节点，写入数据。当设置副本冗余度时，加载机会选择不同的节点分别写入数据。
在数据检索时，一个索引分片检索结果如果超过返回时间限制，可以选择对应的索引分片的副本重新执行检索操作，实现数据容错功能。限于篇幅，关于数据详细的组织方式不再详述。
4. MDSS数据检索方法
MDSS 执行复杂查询条件的基本原则是对查询条件划分成查询子任务，每个子任务在分布式环境下的不同层次上并发实现。查询条件的分解和查询子任务的划分，既要保证查询语义的正确性，同时需要充分考虑分布式环境下影响数据检索的多种因素，充分发挥分布式环境下并发、并行的计算能力。
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查询子任务的并发执行与数据汇总
在分布式环境下，可以把一个具体的复杂查询任务按照上述分类方法分解成三类基本查询条件，每类查询条件对应一种查询子任务，利用分布式环境下的不同层次执行具体的查询子任务。其中分区类查询条件结合元数据信息在具体的存储节点上进行索引文件级别的查询；过滤类查询条件针对目标索引文件内的具体记录进行过滤，这两类条件在多数据存储节点中并发执行。统计分析类查询条件在查询机上，针对过滤类查询条件返回的结果集进行汇总后再进行统一计算处理，保证查询语义的正确性。
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
MDSS 采用时间属性作为分区类检索条件，根据检索条件中的时间属性可以直接检索到符合条件的目标索引分片，加速检索过程。这一点与目前的No-SQL 数据库不同，目前No-SQL 数据库通常按照关键字进行数据块分裂，并涉及到新老数据块的迁移、合并等操作。MDSS 采用时间属性作为分区条件简化了数据管理策略，同时符合日志类数据，流数据的应用场景。
统计分析类查询条件主要针对具有分组，排序，数值分析，以及TOPK 类的检索条件进行具体操作。这类查询操作需要根据全部的结果集进行统计后才能给出正确的查询结果。
统计分析类查询条件，如分组与排序等操作主要放在查询机上实现，为了加速数据分组，去重计算过程，引入Bloom Filter算法，快速判断一条记录是否属于同一个分组或快速去重。
MDSS 针对部分查询做了特殊优化处理。比如仅对字段属性进行简单统计的分组、排序、去重等查询，如SELECT DOMAIN „ GROUP BY(ORDER BY) DOMAIN ；SELECT DISTINCT *„，尽管具有统计分析函数标识，但是由于在存储节点上进行计算不会影响最后查询结果的正确性，MDSS 会选择放到底层存储节点上同过滤类查询条件一起并行执行。此时返回的子查询结果集是已经分好组、排好序或去重后的结果集，最后的数据汇总阶段只做一次对应的统计操作，会大大提高数据汇总阶段的执行效率。一个具体的查询条件分层次执行示意图如图6所示。
图6 数据检索与合并流程
不同的查询机对应的查询条件，要求的响应时间都各不相同。MDSS 主要采用两类查询机制满足不同的查询需求：在线查询机制和离线查询机制。
在线查询是指对数据查询响应时间要求较高，在数秒甚至1秒钟内返回查询结果，主要用于C/S或B/S框架下的界面展示中，用户可以在线等待查询结果；离线查询是指在数据挖掘、统计分析等应用场合中，要求的数据查询模式相对复杂，有时需要针对全部数据进行统计、分析计算后才能得出查询结果，一般使用定制的ETL 工具实现，能够容忍较长的数据查询响应时间。上述两种数据查询机制在海量结构化数据管理系统中普遍存在。为了综合考虑两种检索应用背景，引入了分批返回机制，即在执行子查询中，设置子查询检索结果集的阈值，如果检索到结果集超过阈值，返回当前的检索结果，同时存储节点保存当前的检索状态、缓存剩余的结果集以及对应的SessionID 。在线检索应用中需要展现的结果集数据较少，一个批次可以满足要求。当下次使用新的查询语句建立新的查询请求时，存储节点会放弃缓存的信息，同时建立新的查询请求。对于离线检索机制，往往进行大数据量的统计与分析，需要建立在检索全部结果集基础上实现此时可以继续使用同一个SessionID ，继续上次的检索操作，循环检索，直到检索完满足条件的所有记录为止。分批次异步检索机制充分考虑了两类检索应用的不同场景，目前每个批次默认设置为70万查询结果集，根据具体的应用可以进行配置。
5. 实验结果与分析
为了测试系统的具体性能，针对某运营商DNS 访问记录进行落地存储。实验环境为：加载机为两个节点, 配置为AMD Opteron 2378 8核800MHz 8G内存X 2；查询机一个节点，配置为AMD Opteron 2378 8核800MHz 16G 内存；元数据集群一个节点，具体配置为AMD Opteron 2378 8核800Mhz 16G 内存。四个存储节点，具体配置为AMD Opteron 8380 4核800MHz X 4。存储节点加载磁盘阵列，每个节点加载5T 磁盘空间，集群提供20T 的磁盘存储空间。
系统连续运行50天左右，平均每天入库数据量4-5亿条记录，保存DNS 记录230亿条左右，占用的存储空间14TB 。在当前数据规模条件下进行具体的实验测试。
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
首先给出不同的检索时间间隔对检索效率的影响。针对2011-07-01:00:00:00到2011-07-01:24:00:00期间内，连续24个小时的数据进行实验分析。该时间段内的保存的记录数目为510335051条。具体的检索条件包括下列条件：
⏹ 模糊检索条件：DOMAIN=www.*.com.cn； ⏹ 精确匹配属性检索：TYPE=A； ⏹ 分区检索条件：TIME=T；
设检索时间为T 为参数，当T 取不同时间间隔时，检索效率与具体的时间关系如图7所示。
从图示可以看出检索效率基本上与检索条件的时间间隔成线性增长。在数据库规模为230亿记录存储空间为14TB 四个存储节点条件下，对24个小时内的数据进行多属性检索时，检索时间在140s 左右返回查询结果。该结果远远高于传统数据库的查询效率。其主要时间消耗在查询机从元数据节点查询元数据信息以及多查询节点间的数据通信和汇总上。
)
S ( 间时索检时间间隔T (h)
图7 不同检索时间间隔对应的检索效率
为了进一步分析影响分布式系统的主要因素，分别考察返回查询结果集数目以及检索条件数目两
个因素对查询时间的影响。
图8给出了MDSS 检索效率与返回结果集数目的之间的关系，从图示中可以看出，MDSS 检索效率与返回的结果集有关。当结果集过大时，不仅传输数据、数据汇总占用更多的时间，在使用列存储结构，重构整条原始记录都会占用更多的时间。
图9给出，当使用多个逻辑条件组合时，检索条件通过OR 或AND 进行连接，检索效率与多检索条件个数之间的关系。通过图示可以看出，逻辑条
件的个数增加时（实验中增加到32个检索条件），检索时间基本不发生变化。主要原因是
由于过滤类检索条件在分布式存储节点上并发执行, 每个节点针对具体的索引分片启动多线程检索，同时MDSS 索引分片采用列存结构，适于应用在大数据集、复杂检索条件的分析应用中。
结合上述两个实验，可以得出MDSS 具体的查询效率主要与检索结果集数目有关，当结果集过大，由分布式系统的数据通信、查询机上的数据汇总等操作会占用较多的时间，进而导致系统检索效率下降。对于相对复杂的检索条件可以根据具体索引结构、数据存储组织方式进行具体的优化。目前MDSS 系统可以有效解决多属性数据检索需求，而对于更复杂的关联查询，正在进一步的研究设计中。
)
S ( 间时索检结果集数目
图8 检索效率与返回的结果集数目关系
)
S ( 间时索检条件个数
图9 检索效率与过滤类检索条件的关系
,第 卷 计 算 机 研 究 与 发 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
6结束语
本文结合了传统关系型数据库设计思想并借鉴了云存储中常用的数据管理方式，建立面向结构化数据的海量数据存储检索系统。系统支持结构化数据的高效加载、分布存储与复杂条件的查询功能。在具体设计、开发过程中得到如下的经验和结论： （1）结合具体的应用，综合利用分区索引条件、列存储结构等技术，会显著提高海量结构化数据的查询效率；
（2）充分利用、挖掘分布式环境下的并发、并行计算能力，是提高面向大数据集、复杂查询条件查询效率的主要途径。
MDSS 系统在查询效率方面有待进一步改进主要的改进方向包括，如何提高元数据的管理、访问效率；如何建立分布式环境下面向复杂条件的高效查询规划，减少中间结果集的传递、结果集汇总等时间消耗，都是进一步提高系统查询效率的主要方面。
参 考 文 献
[1] Bernstein, P.A., and Goodman, N. An algorithm for
concurrency control and recovery in replicated distributed databases. ACM Trans. on Database Systems, 9(4):596-615
[2] Lindsay, B.G., et. al., “Notes on Distributed
Databases”, Research Report RJ2571(33471), IBM Research, July 1979
[3] Chang, F., et al., Bigtable: A distributed storage
system for structured data. Acm Transactions on Computer Systems, 2008. 26(2)
[4] DeCandia, G ., et al., Dynamo: amazon's highly
available key-value store, in Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles. ACM: Stevenson, Washington, USA, 2007:205-220
[5] Lakshman, A. and P. Malik, Cassandra: a
decentralized structured storage system. ACM SIGOPS Operating Systems Review, 2010, 44 (2): 35-40.
[6] Cooper, B.F., et al. PNUTS: Yahoo!'s hosted data
serving platform. in Proceedings of the VLDB Endowment, 2008: 1277-1288 [7] [8] http://hypertable.org/
[9] Chen, G ., et al. A Framework for Supporting
DBMS-like Indexes. in Very Large Data Bases (VLDB), Seatle, WA. 2011
吴广君（1981-），男，辽宁省辽阳人，博士，中国科学院计算技术研究所 助理研究员，主要研究方向：海量数据存储，数据容灾，信息安全。
王树鹏（1980-），男，山东省济南人，博士，中国科学院计算技术研究所 助理研究员，主要研究方向：海量数据存储与安全、数据灾备。
陈明 (1983-)，男，河南驻马店人，博士研究生，主要研究方向: 重复数据删除、信息安全。
李超，男，1982年生，博士研究生，主要研究方向为信息安全。