论文部分内容阅读
摘 要：XML（Extensible Markup Language，可扩展标记语言）凭借其简单、跨平台、方便阅读等优点，在当今各个领域得到了广泛的应用。然而，作为数据交换标准的XML面对当今海量数据，由于结构不易拆分等问题，其存储和查询性能并不理想。Hadoop的出现，提供了一种新的解决办法。由于Hadoop本身并不适合类似XML格式的半结构化文件处理，因此本文提出来一种基于Hadoop的海量XML查询的解决方案，充分利用Hadoop的并行性能，同时还引入了高效的索引机制，很好的解决了海量XML存储于查询性能问题，实验证明，该方案能达到良好的效果。
关键词：Hadoop；XML；索引；查询；海量数据
中图分类号：TP311.52
XML是一个万维网联盟（W3C）的建议标准[1]，它被越来越多地用于在不同数据源间进行各种形式的数据交流。在最近几年XML海量应用正在快速增长，互联网上如用户搜索行为记录、数据库历史日志记录、数字图书馆系统等，在科学研究上如对历史天气记录，DNA序列记录等。这些海量XML对我们存储、查询、分析数据提出了更高的挑战。
Hadoop是近几年发展比较成熟的开源云计算平台之一，凭借其可靠、高效、可伸缩的特性在互联网领域得到了广泛的应用，同时也得到了学术界的普遍关注[2]。Hadoop的HDFS（Hadoop distributed file system）分布式文件系统和MapReduce分布式计算框架提供了高可靠性的分布式存储和高速的海量数据计算[3]，使海量存储XML与高效查询XML成为可能。
但由于Hadoop对结构化数据查询分析比较容易，对类似于XML这种半结构化，内容属性可扩展的数据查询检索，Hadoop也略显无力。因此，本文提出了一种对海量XML文件半结构化数据的分割方法，充分利用了已知的XML大致结构，通过MapReduce编程，将海量XML文件并行处理，实现了海量XML查询；同时，引入了索引机制，避免Hadoop扫描整个海量数据，大大减少了查询时间。
1 相关研究
迄今为止，对于XML的存储以及查询的优化算法大部分都是在树结构的基础上提出的。这些算法在单机上实现都能表现出不错的效果，但是，一旦把他们发到分布式集群上，由于树不在完整，将无法应用算法。
1.1 传统XML存储与查询
对于传统XML存储，可直接存放在操作系统的文件系统上即可。
对于传统XML查询，传统的查询数据的做法有：
（1）基于Tree-Based解析：代表有DOM、JDOM、DOM4J，原理是把XML整个以树的形式读入内存，然后查找。优点是可随机多次查找，支持XPATH路径查找，支持读写操作。缺点是需要加载整个XML，资源耗费大。
（2）基于Event-Based计息：代表有SAX，STAX，原理是以流的方式顺序读取XML信息。优点是：不需要加载整个XML，节约内存，节约时间，速度快。缺点是：不支持多次随机查找，不支持XPATH，只读而不能写。
1.2 海量XML存储与查询
由于是海量XML数据，数据量已超过了单台电脑硬盘的容量，因此需要一个特殊的分布式文件系统，本文使用的是Hadoop的HDFS。
HDFS是一个高度容错性的系统，适合部署在廉价的机器上。HDFS能提供高吞吐量的数据访问，非常适合大规模数据集上的应用。它有如下特点[4]：
（1）硬件故障是常态。即硬件故障是常态，而不是异常，HDFS提供了一个很好的故障检测和自动快速恢复的容灾系统。
（2）流式的数据访问。即运行在HDFS之上的应用程序必须流式地访问它们的数据集，这样极大的提高了分布式数据的吞吐量，便于多台机器协同工作。
（3）大数据集。运行在HDFS之上的程序有很大量的数据集。典型的HDFS文件大小是GB到TB的级别。所以，HDFS被调整成支持大文件。
（4）一次写入，多次读出。一个文件一旦创建、写入、关闭之后就不需要修改了。这个假定简单化了数据一致的问题和并使高吞吐量的数据访问变得可能。一个Map-Reduce程序或者网络爬虫程序都可以完美地适合这个模型。
（5）数据本地化运行。在靠近计算数据所存储的位置来进行计算是最理想的状态，尤其是在数据集特别巨大的时候。这样消除了网络的拥堵，提高了系统的整体吞吐量。
对海量XML查询，我们需要对其进行特殊的分割，然后交由分布式环境进行流式计算处理。
2 海量XML文件处理方案
对于海量XML文件处理，因为HDFS分布式文件系统给我们海量XML文件提供了可靠而高效的存储管理，所以，我们不必太过关心XML文件的存储问题。因此下面着重介绍在分割查询XML，以及通过索引提高查询效率上的方案。
2.1 Hadoop的MapReduce处理数据流程
（1）MapReduce框架会对指定目录的文件以用户指定的方式分割成许多inputSplits（输入分片），默认会以64M为单位将文件分割[5]。
（2）每个inputSplit将在分布式并行的环境下，使用用户指定方法分割每个inputSplit具体内容，读取成（key，value）的形式，再交给map（）函数处理。
（3）map（）函数以（key，value）的形式输出处理后的结果，经过“洗牌合并”处理，即相同的key，使它对应的value成为一组，以（key，List（value））的形式交给reduce（）函数处理。
2.2 XML的分割读取方法
根据以上介绍，文件实际上经历了两个分割，第一次分割是将海量文件分割成许多的inputSplit，每个inpuSplit对应于一次Map任务，多个Map任务之间并行处理。第二次分割是针对于每一个inputSplit的具体内容，把内容以某种形式分割成（key，value）的形式，传递给map（）函数处理[6]。 第一次分割Hadoop默认是以64M为大小将海量数据切分成许多小InputSplit；第二次分割Hadoop默认有按行分割，按制表符分割等规则分割函数。
可以看到，上面这些默认分割都无法满足XML属性多变，可扩展的格式要求。这里假设已知XML内容结构，那么可以把海量XML按照每个小部分切分，切分完整后，每个小部分仍然是独立的XML。如对于历史天气的一个XML，根结点下有年月日层次关系，日结点下有天气的属性内容。那么我们可以以日结点为单位切分，切分的每块key为日结点偏移量，value为整个日结点的XML内容。
至于具体切分方法，本文自定义了一个分割类，该类只需指定开始内容与结束内容，运行后，它能够返回开始和结束之间内容作为value和它的偏移量作为key。
2.3 XML的索引查询方法
Hadoop作为大数据处理工具，由于采用的是流式处理方案，因此是没有索引机制的，即只要给定的MapReduce开始运行，就会默认扫描处理整个输入目录或文件，使大XML文件的查询效率极低。
针对上述问题，本文设计了索引机制，主要利用了Hadoop的HDFS文件系统支持随机读写的特性，即知道文件偏移量（offset），能够快速略过前面内容，直接跳到指定偏移量位置开始操作[7]。
3 Hadoop下处理XML具体实现
对于海量XML处理，主要有如下几步：
（1）上传待处理XML文件，对待处理XML运行MapReduce框架建立索引；
（2）查询时，先用MapReduce框架查询索引，取出待查询的偏移量；
（3）根据偏移量，直接读取文件指定部分；
3.1 建立海量XML索引
上传步骤仅仅用Hadoop命令即可完成，这里就不在赘述了，建立索引时，主要通过加入XML分割函数，来把海量数据切分成指定小段XML，再交给map（）函数处理。整体步骤如下：
（1）在MapReduce程序中设置自定义的切割函数。
（2）针对待建索引的字段配置XmlInputFormat类的属性，即指定小片段XML数据的开头标记和结尾标记。
（3）map（）函数接收（key，value），对value即小段XML进行SAX解析，取出我们待建立索引的内容，将取出的数值与偏移量分别作为key和value传递给reduce（）函数。
（4）reduce（）函数把每个偏移量用逗号分隔，写在一行中，与索引内容一起作为输出。
3.2 查询索引和读取偏移量位置内容
查询索引就比较简单了，因为索引是结构化数据，按行排列，因为面对海量数据，索引文件可能依旧很大，所以可以通过Hadoop程序并行查询索引，加快查询，步骤如下：
（1）MapReduce程序中设置按行分割。
（2）TextInputFormat把key为偏移量，value为整行内容的键值对传递给map（）函数。
（3）map（）中截取value第一个逗号以前的内容，对比待查询内容，若相同，这把value值即整行内容传递给reduce（）函数。
（4）reduce（）函数中处理第一个逗号以后的内容，得到一系列待查询的偏移量，利用Hadoop的FSDataInputStream类方法，定位读取指定内容后，作为结果输出。
4 实验结果及分析
4.1 实验环境
硬件环境：3台HP电脑构成的Hadoop集群，每个节点均为双核Intel i3 CPU，频率为3.3GHZ，2GB内存，60GB硬盘，网络环境是百兆以太网。
软件环境：操作系统均为32位 Linux Fedora 14（内核版本为2.6.35），JDK版本为1.6，Hadoop版本为0.202。
3台电脑均参与运算，其中一台兼做主节点。
数据集由XMark中XML生成工具产生，其中XMark是针对XML查询检索性能测量的一套工具，实验结果均是5组后测量时间取的平均值。
4.2 实验结果
（1）上传海量文件。由图4看到相比传统的XML文件直接交给操作系统管理，Hadoop首先要上传海量数据至HDFS，由于HDFS是分布式冗余管理文件，所以上传还是比较耗时的。
图4 文件上传至HDFS耗时
（2）查询时间。从图5时间对比（不包含建立索引时间）可以看出，索引查询在小于500MB时，查询优势还不太明显，当大于500MB后，查询时间依旧能维持在20 s左右，说明，索引查询能很好的提高查询速度，这点在XML数据量较大的查询上显得尤为突出。
（3）考虑建立索引时间。若考虑建立索引时间，且只查询一次，那么索引查询的优势将不存在了，但是考虑到索引能够重复利用，且查询也不可能是一次性的。为了分析索引优势，我们列出如下等式：
非索引查询时间*n=索引查询时间*n+建立索引时间
我们解出n画出图6，这里n代表着查询n次，索引查询的优势时间弥补建立索引时间。当查询次数小于n次，非索引查询总时间较短；当查询次数大于n次，索引查询总时间会较短，且优势在后面会越来越明显。
从图6可以看出，在XML数据比较大的情况，查询两次，即可抵消建立索引的时间开销。
5 结束语
本文从实际需求出发，对比传统方案的缺点，提出了一种更适合海量XML数据处理的解决方案。经小型模拟实验，此方案能够很好的解决某些海量XML存储与查询问题，同时具备良好的性能，在大型hadoop集群上，相信会有更好的表现。当然，该解决方案现阶段只适合一些已知的，结构简单的海量XML，以后的研究目标将把XML树编码加入到索引用以支持更通用的XML结构查询。同时，在建立索引方面，目前正在研究如何在上传时建立索引，若成功，则可大大减少索引查询的总共耗时。
参考文献：
[1]Yang，M.J.XML学习指南[M].北京：机械工业出版社，2008.
[2]Tom White.Hadoop权威指南（2版）[M].周敏奇.北京：清华大学出版社，2011.
[3]Tom White. Hadoop The Definitive Guide 2nd Edition [M].Oreilly，2010.
[4]Apache. Welcome to Apache Hadoop[OL].2011.http：//hadoop.apache.org/.
[5]刘鹏.实战Hadoop—开启通向有云计算的捷径[M].北京：电子工业出版社，2011.
[6]刘鹏.云计算[M].北京：电子工业出版社，2011.
[7]董长春.基于Hadoop的倒排索引技术的研究[D].沈阳：辽宁大学，2011.
[8]付志超.基于Map/Reduce的分布式智能搜索引擎框架研究[D].北京：北京邮电大学，2008.
作者简介：危奇（1989-），男，湖北武汉人，工学硕士，研究方向：云计算；万立（1977-），男，湖北武汉人，副教授，博士，研究方向：神经网络。
作者单位：武汉纺织大学数学与计算机学院，武汉 430073
基金项目：国家自然科学基金项目号11271295，湖北省教育厅科研项目D20131602。
关键词：Hadoop；XML；索引；查询；海量数据
中图分类号：TP311.52
XML是一个万维网联盟（W3C）的建议标准[1]，它被越来越多地用于在不同数据源间进行各种形式的数据交流。在最近几年XML海量应用正在快速增长，互联网上如用户搜索行为记录、数据库历史日志记录、数字图书馆系统等，在科学研究上如对历史天气记录，DNA序列记录等。这些海量XML对我们存储、查询、分析数据提出了更高的挑战。
Hadoop是近几年发展比较成熟的开源云计算平台之一，凭借其可靠、高效、可伸缩的特性在互联网领域得到了广泛的应用，同时也得到了学术界的普遍关注[2]。Hadoop的HDFS（Hadoop distributed file system）分布式文件系统和MapReduce分布式计算框架提供了高可靠性的分布式存储和高速的海量数据计算[3]，使海量存储XML与高效查询XML成为可能。
但由于Hadoop对结构化数据查询分析比较容易，对类似于XML这种半结构化，内容属性可扩展的数据查询检索，Hadoop也略显无力。因此，本文提出了一种对海量XML文件半结构化数据的分割方法，充分利用了已知的XML大致结构，通过MapReduce编程，将海量XML文件并行处理，实现了海量XML查询；同时，引入了索引机制，避免Hadoop扫描整个海量数据，大大减少了查询时间。
1 相关研究
迄今为止，对于XML的存储以及查询的优化算法大部分都是在树结构的基础上提出的。这些算法在单机上实现都能表现出不错的效果，但是，一旦把他们发到分布式集群上，由于树不在完整，将无法应用算法。
1.1 传统XML存储与查询
对于传统XML存储，可直接存放在操作系统的文件系统上即可。
对于传统XML查询，传统的查询数据的做法有：
（1）基于Tree-Based解析：代表有DOM、JDOM、DOM4J，原理是把XML整个以树的形式读入内存，然后查找。优点是可随机多次查找，支持XPATH路径查找，支持读写操作。缺点是需要加载整个XML，资源耗费大。
（2）基于Event-Based计息：代表有SAX，STAX，原理是以流的方式顺序读取XML信息。优点是：不需要加载整个XML，节约内存，节约时间，速度快。缺点是：不支持多次随机查找，不支持XPATH，只读而不能写。
1.2 海量XML存储与查询
由于是海量XML数据，数据量已超过了单台电脑硬盘的容量，因此需要一个特殊的分布式文件系统，本文使用的是Hadoop的HDFS。
HDFS是一个高度容错性的系统，适合部署在廉价的机器上。HDFS能提供高吞吐量的数据访问，非常适合大规模数据集上的应用。它有如下特点[4]：
（1）硬件故障是常态。即硬件故障是常态，而不是异常，HDFS提供了一个很好的故障检测和自动快速恢复的容灾系统。
（2）流式的数据访问。即运行在HDFS之上的应用程序必须流式地访问它们的数据集，这样极大的提高了分布式数据的吞吐量，便于多台机器协同工作。
（3）大数据集。运行在HDFS之上的程序有很大量的数据集。典型的HDFS文件大小是GB到TB的级别。所以，HDFS被调整成支持大文件。
（4）一次写入，多次读出。一个文件一旦创建、写入、关闭之后就不需要修改了。这个假定简单化了数据一致的问题和并使高吞吐量的数据访问变得可能。一个Map-Reduce程序或者网络爬虫程序都可以完美地适合这个模型。
（5）数据本地化运行。在靠近计算数据所存储的位置来进行计算是最理想的状态，尤其是在数据集特别巨大的时候。这样消除了网络的拥堵，提高了系统的整体吞吐量。
对海量XML查询，我们需要对其进行特殊的分割，然后交由分布式环境进行流式计算处理。
2 海量XML文件处理方案
对于海量XML文件处理，因为HDFS分布式文件系统给我们海量XML文件提供了可靠而高效的存储管理，所以，我们不必太过关心XML文件的存储问题。因此下面着重介绍在分割查询XML，以及通过索引提高查询效率上的方案。
2.1 Hadoop的MapReduce处理数据流程
（1）MapReduce框架会对指定目录的文件以用户指定的方式分割成许多inputSplits（输入分片），默认会以64M为单位将文件分割[5]。
（2）每个inputSplit将在分布式并行的环境下，使用用户指定方法分割每个inputSplit具体内容，读取成（key，value）的形式，再交给map（）函数处理。
（3）map（）函数以（key，value）的形式输出处理后的结果，经过“洗牌合并”处理，即相同的key，使它对应的value成为一组，以（key，List（value））的形式交给reduce（）函数处理。
2.2 XML的分割读取方法
根据以上介绍，文件实际上经历了两个分割，第一次分割是将海量文件分割成许多的inputSplit，每个inpuSplit对应于一次Map任务，多个Map任务之间并行处理。第二次分割是针对于每一个inputSplit的具体内容，把内容以某种形式分割成（key，value）的形式，传递给map（）函数处理[6]。 第一次分割Hadoop默认是以64M为大小将海量数据切分成许多小InputSplit；第二次分割Hadoop默认有按行分割，按制表符分割等规则分割函数。
可以看到，上面这些默认分割都无法满足XML属性多变，可扩展的格式要求。这里假设已知XML内容结构，那么可以把海量XML按照每个小部分切分，切分完整后，每个小部分仍然是独立的XML。如对于历史天气的一个XML，根结点下有年月日层次关系，日结点下有天气的属性内容。那么我们可以以日结点为单位切分，切分的每块key为日结点偏移量，value为整个日结点的XML内容。
至于具体切分方法，本文自定义了一个分割类，该类只需指定开始内容与结束内容，运行后，它能够返回开始和结束之间内容作为value和它的偏移量作为key。
2.3 XML的索引查询方法
Hadoop作为大数据处理工具，由于采用的是流式处理方案，因此是没有索引机制的，即只要给定的MapReduce开始运行，就会默认扫描处理整个输入目录或文件，使大XML文件的查询效率极低。
针对上述问题，本文设计了索引机制，主要利用了Hadoop的HDFS文件系统支持随机读写的特性，即知道文件偏移量（offset），能够快速略过前面内容，直接跳到指定偏移量位置开始操作[7]。
3 Hadoop下处理XML具体实现
对于海量XML处理，主要有如下几步：
（1）上传待处理XML文件，对待处理XML运行MapReduce框架建立索引；
（2）查询时，先用MapReduce框架查询索引，取出待查询的偏移量；
（3）根据偏移量，直接读取文件指定部分；
3.1 建立海量XML索引
上传步骤仅仅用Hadoop命令即可完成，这里就不在赘述了，建立索引时，主要通过加入XML分割函数，来把海量数据切分成指定小段XML，再交给map（）函数处理。整体步骤如下：
（1）在MapReduce程序中设置自定义的切割函数。
（2）针对待建索引的字段配置XmlInputFormat类的属性，即指定小片段XML数据的开头标记和结尾标记。
（3）map（）函数接收（key，value），对value即小段XML进行SAX解析，取出我们待建立索引的内容，将取出的数值与偏移量分别作为key和value传递给reduce（）函数。
（4）reduce（）函数把每个偏移量用逗号分隔，写在一行中，与索引内容一起作为输出。
3.2 查询索引和读取偏移量位置内容
查询索引就比较简单了，因为索引是结构化数据，按行排列，因为面对海量数据，索引文件可能依旧很大，所以可以通过Hadoop程序并行查询索引，加快查询，步骤如下：
（1）MapReduce程序中设置按行分割。
（2）TextInputFormat把key为偏移量，value为整行内容的键值对传递给map（）函数。
（3）map（）中截取value第一个逗号以前的内容，对比待查询内容，若相同，这把value值即整行内容传递给reduce（）函数。
（4）reduce（）函数中处理第一个逗号以后的内容，得到一系列待查询的偏移量，利用Hadoop的FSDataInputStream类方法，定位读取指定内容后，作为结果输出。
4 实验结果及分析
4.1 实验环境
硬件环境：3台HP电脑构成的Hadoop集群，每个节点均为双核Intel i3 CPU，频率为3.3GHZ，2GB内存，60GB硬盘，网络环境是百兆以太网。
软件环境：操作系统均为32位 Linux Fedora 14（内核版本为2.6.35），JDK版本为1.6，Hadoop版本为0.202。
3台电脑均参与运算，其中一台兼做主节点。
数据集由XMark中XML生成工具产生，其中XMark是针对XML查询检索性能测量的一套工具，实验结果均是5组后测量时间取的平均值。
4.2 实验结果
（1）上传海量文件。由图4看到相比传统的XML文件直接交给操作系统管理，Hadoop首先要上传海量数据至HDFS，由于HDFS是分布式冗余管理文件，所以上传还是比较耗时的。
图4 文件上传至HDFS耗时
（2）查询时间。从图5时间对比（不包含建立索引时间）可以看出，索引查询在小于500MB时，查询优势还不太明显，当大于500MB后，查询时间依旧能维持在20 s左右，说明，索引查询能很好的提高查询速度，这点在XML数据量较大的查询上显得尤为突出。
（3）考虑建立索引时间。若考虑建立索引时间，且只查询一次，那么索引查询的优势将不存在了，但是考虑到索引能够重复利用，且查询也不可能是一次性的。为了分析索引优势，我们列出如下等式：
非索引查询时间*n=索引查询时间*n+建立索引时间
我们解出n画出图6，这里n代表着查询n次，索引查询的优势时间弥补建立索引时间。当查询次数小于n次，非索引查询总时间较短；当查询次数大于n次，索引查询总时间会较短，且优势在后面会越来越明显。
从图6可以看出，在XML数据比较大的情况，查询两次，即可抵消建立索引的时间开销。
5 结束语
本文从实际需求出发，对比传统方案的缺点，提出了一种更适合海量XML数据处理的解决方案。经小型模拟实验，此方案能够很好的解决某些海量XML存储与查询问题，同时具备良好的性能，在大型hadoop集群上，相信会有更好的表现。当然，该解决方案现阶段只适合一些已知的，结构简单的海量XML，以后的研究目标将把XML树编码加入到索引用以支持更通用的XML结构查询。同时，在建立索引方面，目前正在研究如何在上传时建立索引，若成功，则可大大减少索引查询的总共耗时。
参考文献：
[1]Yang，M.J.XML学习指南[M].北京：机械工业出版社，2008.
[2]Tom White.Hadoop权威指南（2版）[M].周敏奇.北京：清华大学出版社，2011.
[3]Tom White. Hadoop The Definitive Guide 2nd Edition [M].Oreilly，2010.
[4]Apache. Welcome to Apache Hadoop[OL].2011.http：//hadoop.apache.org/.
[5]刘鹏.实战Hadoop—开启通向有云计算的捷径[M].北京：电子工业出版社，2011.
[6]刘鹏.云计算[M].北京：电子工业出版社，2011.
[7]董长春.基于Hadoop的倒排索引技术的研究[D].沈阳：辽宁大学，2011.
[8]付志超.基于Map/Reduce的分布式智能搜索引擎框架研究[D].北京：北京邮电大学，2008.
作者简介：危奇（1989-），男，湖北武汉人，工学硕士，研究方向：云计算；万立（1977-），男，湖北武汉人，副教授，博士，研究方向：神经网络。
作者单位：武汉纺织大学数学与计算机学院，武汉 430073
基金项目：国家自然科学基金项目号11271295，湖北省教育厅科研项目D20131602。