基于MapReduce的地震波形数据并行解压缩算法研究1
2015-12-05刘凡鸣郭瑞强李永庆边鹏飞
刘凡鸣 郭瑞强 李永庆 边鹏飞
基于MapReduce的地震波形数据并行解压缩算法研究1
刘凡鸣1）郭瑞强1）李永庆2）边鹏飞2）
1）河北师范大学数学与信息科学学院，石家庄 050024 2）河北省地震局，石家庄 050021
近年来各省级地震台网SEED文件数据量急增。在数据处理过程中，利用原有的串行解压缩算法批量解压缩地震波形数据时存在操作繁琐、耗时较长的问题。本文引入了MapReduce并行编程模型，根据该编程模型思想结合原有串行解压缩算法，提出了一种并行解压缩地震波形数据的算法，并给出了算法的设计与实现。本文从正确性、运行效率以及可扩展性三个方面进行了对比实验，验证了使用并行算法解压缩数据的效率较高，并且能够一次实现批量地震波形数据的解压缩，且操作简单。
地震波形数据 解压缩 并行 MapReduce
引言
目前，中国数字地震监测网络的测震台站数量已达1000多个，它们为测震台网中心提供了大量的波形数据。各省级测震台网中心在完成地震速报和编目处理后，将这些波形数据归档成SEED（The Standard for the Exchange of Earthquake Data，地震数据交换标准）（中国地震局，2003）格式用于地震科研。单是省级测震台网中心就已经积累了庞大的波形数据，以河北省地震局为例，目前已经积累了10TB左右的波形数据，而且还以约0.6TB/年的速率增长。其中，“台站卷”归档了单个台站的连续波形，“事件卷”归档了多个台站对同一地震事件的记录波形。随着数字地震波形的广泛使用，对地震精定位、波形互相关分析、重复地震、波速比、地脉动噪声成像、震动图快速计算、震源机制解、震源破裂过程反演等方面的研究越加深入。在进行上述研究时，首先会将压缩格式的SEED波形还原成数字序列，因此需要处理的台站数量也越来越多。而原有的SEED解压算法属于单文件、单线程操作，极大制约了数据处理工作的效率。
Hadoop是Apache软件基金会旗下的一个开源的分布式计算平台（White，2012），其核心组件包括分布式文件系统（HDFS）和MapReduce编程模型。其中HDFS具有可靠、可扩展等优点，因此用户可以将多台廉价的硬件部署成并行处理集群（Ghemawat等，2003）。而MapReduce是一个可以在集群上处理大规模数据的并行编程模型，它借鉴了函数式编程思想，其中分布式系统底层细节对用户是透明的，因此用户只需编写函数式程序就可以进行并行程序的开发（Dean等，2008）。利用Hadoop架构提供的MapReduce编程模型，可将单文件、单线程的SEED解压缩工作转变为计算机集群上多文件、多线程的并行处理，因此可以极大地提高解压缩效率。特别是针对测震台网数据服务中心在多用户环境下提供数据服务时，这种效率的提高更加明显。
目前Hadoop技术在地震相关领域已经有了初步使用，文必龙等（2014）提出了非结构化地震数据在Hadoop分布式平台上的存取设计方案，该方案采用了混合索引查询方法进行统一访问，提高了数据的存储效率。赵长海等（2012）探讨了MapReduce对石油勘探领域应用算法的适用性，并采用MapReduce处理地震数据用以获取地下构造，从而实现石油勘探。由于地震波形数据文件属于半结构化文件，而处理半结构化文件又是MapReduce的优势之一，所以MapReduce比较适合以批处理的方式解决问题。本文引入了MapReduce的编程模型（李闯等，2010），同时根据编程模型和原有串行解压缩算法，提出了一种并行解压缩地震波形数据的算法（以下简称PDSWD算法），并给出了算法的设计与实现。笔者从正确性、运行效率以及可扩展性三个方面对算法进行了对比实验，结果表明使用该算法解压缩数据时效率较高，并且能够一次实现批量地震波形数据的解压缩，且操作简单、方便实用。
1 地震波形数据的串行解压缩算法
中华人民共和国地震行业标准《地震波形数据交换格式（DB/T 2-2003）》（中国地震局，2003）中规定了SEED的格式，因此本文不再介绍。SEED文件采用Steim2压缩算法（Mauro等，2006），这种算法既能节省存储空间，又能保证数据信息不丢失。而地震波形数据的解压缩算法是Steim2压缩算法的逆过程（王洪体等，2004），首先需要计算样本个数，然后提取样本序列的第一个值并获取编码方式，利用差值序列重建原始的32位数据样本序列。
2 基于MapReduce的地震波形数据并行解压缩算法
2.1 MapReduce模型
MapReduce是一个可以在集群上处理大规模数据的并行编程模型，其分布式系统底层细节对用户是透明的。MapReduce主要包括Map和Reduce两个阶段，用户只需根据自己的需求编写相应的Map和Reduce程序，就可以进行并行程序的开发。
输入数据可以看成是若干个
Map: (k1，v1)→List (k2，v2)
之后混洗操作将key值相同的
Reduce: (k2，List(v2))→List (k3，v3)
图1是MapReduce的数据流程。
2.2 并行解压缩算法
由于输入数据中每个通道中的各条数据记录相互独立，在解压缩过程中互不影响，因此SEED文件适合并行化处理，可以将解压缩算法移植到MapReduce上使用。并行解压缩地震波形数据的基本思路是：利用MapReduce编程模型的分治思想，Map阶段解压缩每个分片中的数据记录，然后将中间结果传递给Reduce阶段进行规约，拼接各通道数据得到最终结果。解压缩过程如图2所示。
以下是MapReduce各阶段的流程描述：
（1）输入：地震事件波形SEED文件，包括台站、位置、台网、通道、时间、样本数据、采样率以及压缩数据等。
（2）Map阶段：并行解压缩每个分片中的各条数据记录，得到原始样本数据，根据输入文件读取每条数据记录所属文件的文件名，以及台站、位置、台网、通道的信息，将这些信息作为中间结果的key，将从每条数据记录中读取的其余头部信息和解压缩后得到的数据作为中间结果的value。
（3）Reduce阶段：远程拷贝Map阶段输出的中间结果，把key相同的值对聚集到一起，并按照数据记录序号进行排序，然后将数据传递给Reduce节点，根据用户自定义的Reduce函数，将解压缩后得到的各通道数据按照时间的先后顺序进行拼接。
（4）输出：输出文件中包含每个台站的各个通道解压缩得到的原始样本，并按采样顺序排列。
2.3 Map阶段处理过程
2.3.1 自定义Inputformat
Inputformat是MapReduce的一个重要接口，其中包含输入数据切片方法以及每个从分片读取键值对的方法。通常系统默认的是按行提取键值对，即
2.3.2 Map函数
Map函数接收从分片中读取的<文件名，数据记录>对，并将其作为输入，通过用户自定义的Map函数解压缩每条数据记录，并读取数据记录中的属性信息。因为每个通道包含的数据记录不止一条，所以需要根据时间的先后，将各通道内数据记录解压缩后的结果进行拼接。同一通道内数据记录的编号可以反映出时间的先后，编号越小则记录的时间越早，因此把数据记录的编号作为排序依据。
MapReduce中Map的输出只会按照key排序，不会根据value进行排序。而本文中不仅需要按照key排序，在拼接数据时还需要按照数据记录编号进行排序，但数据记录编号在value中保存，因此就需要使用二次排序。使用二次排序时需要定义一个组合key，在本文中组合key包括需要首先排序的头部信息，即原始key，以及之后需要排序的value中的数据记录编号。
因此Map阶段输出的中间结果格式为<(头部信息，数据记录编号），其余头部信息@解压缩后数据>。Map阶段输出结构如图3所示，FN-Sid-Lid-Nid-Cid和Did形成组合key，FN-Sid-Lid-Nid-Cid作为组合key的第一个值，每个编码间用分隔符“-”隔开，Did作为第二个值。其中FN为文件名称，Sid为台站编码，Lid为位置编码，Nid为台网编码，Cid为通道编码，Did为数据记录编号。其余头部信息@解压缩后数据作为value输出，将其余头部信息和解压缩后数据之间用分隔符“@”隔开，其余头部信息各编码之间用分隔符“-”隔开。其中ST为采样开始时间，ET为采样结束时间，SN为样本数目，SR为采样率，由于剩余的头部信息与本文算法关联不大，这里就不再一一展开介绍。Data为单条数据记录解压后数据。因此Map输出结果为<(FN-Sid-Lid-Nid-Cid,Did), Did-ST-ET-SN-SR-剩余头部信息@解压缩后数据>。
以下是PDSWD Mapper算法：
输入：<文件名，数据记录>
输出：<(FN-Sid-Lid-Nid-Cid,Did),Did-ST-ET-SN-SR-剩余头部信息@解压缩后数据>
步骤：
（1）读取value值；
（2）获取分片所属文件的文件名FN；
（3）读取台站编码Sid，位置编码Lid，台网编码Nid，通道编码Cid，数据记录编号Did；
（4）计算数据记录中包含的样本个数SN，然后解压缩数据记录，得到原始数据样本data=decode(d,SN,false）；
（5）获取数据记录的开始时间ST，采样率SR，并根据这两个值计算结束时间ET；
（6）输出中间结果Context.write((FN-Sid-Lid-Nid-Cid,Did）, Did-ST-ET-SN-SR-剩余头部信息@解压缩后数据）。
2.4 Reduce阶段处理过程
Map阶段后会将具有相同key值的键值对分发到同一个Reduce节点，在Reduce节点上拼接属于同一通道的数据记录解压后得到的数据。由于地震数据在采样过程中可能会发生异常（如两条数据记录间出现时间重叠或者时间间隔的情况），因此不能直接按照数据记录编号从小到大的顺序直接拼接，需要先比较上一条数据记录的结束时间和本条数据记录的开始时间。如果两个时间相同，则按数据记录编号从小到大的顺序直接拼接两条记录中解压出的数据。如果上一条的结束时间和本条的开始时间之间存在时间间隔，则首先计算出时间间隔，并根据采样率计算在该时间间隔内能采集到的样本个数，再在两条数据记录间补充相同个数的null。如果本条的开始时间比上条的结束时间还早，应计算出两者重叠的时间段，再根据采样率计算出在该时间段内能采集到的样本个数，然后在上一条数据记录尾部去除相同个数的数据，最后再拼接本条数据记录中解压缩得到的数据。输入键值对为<(FN-Sid-Lid-Nid-Cid, Did), Did-ST-ET-SN-SR-剩余头部信息@解压缩后数据>，输出键值对为<全部头段信息，按台站通道拼接后得到的原始样本数据>。
以下是PDSWD Reducer算法：
输入：<(FN-Sid-Lid-Nid-Cid,Did),Did-ST-ET-SN-SR-剩余头部信息@解压缩后数据>
输出：<全部头段信息，按台站通道拼接后得到的原始样本数据>
步骤：
（1）读取组合键中的第一个key值以及value中除解压缩后数据以外的所有头部信息，将两者合并得到全部头段信息；
（2）读取value集合中第一个value值，获取结束时间ET以及解压后数据；
（3）读取集合中下一个value，获取开始时间ST、结束时间ET以及解压后数据，通过比较本条的开始时间与上一条的结束时间来决定数据拼接方法；
（4）重复步骤（3），直到读完所有value值，得到按通道拼接好的原始样本数据；
（5）输出最终结果Context.write(<全部头段信息，按台站通道拼接后得到的原始样本数据>）。
3 实验结果及分析
3.1 实验环境及数据
由于条件限制，实验使用由6台PC机搭建的集群环境，其中1台机器作为主NameNode节点和ResourceManager节点，1台机器作为备份NameNode节点，另外4台机器均作为DataNode节点和NodeManager节点。每台机器的配置相同，操作系统为SUSE Linux Enterprise 11SP3，CPU型号为Intel双核6600、2.40GHz，内存为4GB，硬盘容量为1T，Hadoop版本为2.2.0，开发环境eclipse+Hadoop plugin。
实验数据采用河北省地震局提供的2013年9月部分SEED 事件波形数据，共包含文件140个，文件总大小2.7G。
3.2 结果分析
3.2.1 解压正确性验证
为验证本文方法的正确性，使用PDSWD算法和原有解压缩算法分别解压缩相同的输入数据，PDSWD算法运行在Hadoop集群上。每次都将使用PDSWD算法得到的输出样本值和原有方法解压缩得到的输出样本值做比较，结果表明两组样本值均完全相同，这就验证了PDSWD算法的正确性。但由于解压缩后数据样本较多，为便于可视化显示，笔者随机选取了一个开始位置，从开始位置处连续选中30个样本数据，并将这两组数据样本分别绘图后得到了如图4所示的曲线，进一步验证了PDSWD算法的正确性。
3.2.2 运行效率对比实验
为了证明本文提出的并行解压算法的效率，笔者将PDSWD算法与原有的串行解压缩算法的运行效率进行了对比。PDSWD算法运行在由PC机搭建的分布式集群上，原有串行解压算法运行在单台机器上，分别选取19M（1个文件）、125.6M（5个文件）、454.5M（20个文件）、1126.4M（60个文件）、2764.8M（140个文件）数据作为输入，观察运行时间变化。图5是它们的运行时间对比，其中PDSWD-3表示在3节点的集群中使用PDSWD算法，PDSWD-6表示在6节点的集群中使用PDSWD算法，Original表示原有串行解压缩算法。当输入数据较小时，原有串行解压算法和PDSWD算法所用时间基本相同，因为作业的启动和交互需要消耗较多资源；但随着输入数据的增大，并行解压缩算法的工作效率逐渐高于串行解压缩算法的工作效率。
3.2.3 可扩展性实验
通过改变集群规模，可观察不同节点数量对并行解压算法效率的影响。为此笔者在伪分布式集群和3台机器搭建的Hadoop集群上进行了实验，条件是只有机器数量的不同，其余配置均保持一致。实验分别解压缩了19M（1个文件）、125.6M（5个文件）、454.5M（20个文件）、1126.4M（60个文件）的输入数据并记录解压时间。对于不同大小的数据输入，均测试10次运行时间并求出平均值，然后画出趋势图进行对比。在输入数据集的大小相同的情况下，可以利用加速比来衡量增加集群节点个数对并行解压算法效率的影响（陆秋等，2012），即：
式中，1表示加速比；a指的是伪分布式集群运行解压缩程序的执行时间；T指的是多台机器搭建的Hadoop集群运行解压程序的执行时间，本文中T指的是3节点集群的运行时间。
图6展示了运行结果。当输入数据较小时，增加节点数量后并没有明显的变化；随着输入数据的不断增大，加速比的变化愈加明显。因此当输入数据量较大时，增加集群节点个数可以得到更好的效率。
4 结语
本文尝试将MapReduce编程模型引入到地震波形数据处理，提出了基于MapReduce的并行解压缩地震波形数据的算法PDSWD，并给出了较详细的算法实现。与传统的串行解压缩算法相比，利用MapReduce并行解压缩处理数据具有更高的加速比，而且可以一次性解压缩批量文件。下一阶段笔者将尝试使用更大的集群规模和更大的测试数据集，并对MapReduce并行解压缩算法进行优化，扩展其功能，获得更好的工作效率。
李闯，赵长海，晏海华，2010．基于MapReduce的菲涅耳带地震层析成像并行算法．见：2010年全国高性能计算学术年会（HPC China）论文集，90—96．
陆秋，程小辉，2012．基于MapReduce的决策树算法并行化．计算机应用，32（9）：2463—2465，2469．
王洪体，陈阳，庄灿涛，2004．SEED格式STEIM2数据压缩算法在实时地震数据传输中的应用．地震地磁观测与研究，25（4）：14—19．
文必龙，冯翔，左春雪等，2014．地震资料分布式存取的效率优化设计．计算机与数字工程，42（8）：1386—1389．
赵长海，晏海华，刘晓朋，熊登，史晓华，2012．以实际算法为例评估MapReduce在石油勘探中的应用．通信学报，（Z2）：81—89．
中国地震局，2003．地震波形数据交换格式（DB/T 2-2003）．北京：地震出版社．
Dean J., Ghemawat S., 2008. MapReduce: Simplified data processing on large clusters. Comunications of the ACM, 51 (1): 107—113.
Ghemawat S., Gobioff H., Leung S.T., 2003. The Google file system. ACM SIGOPS Operating Systems Review, 37 (5): 29—43.
Mauro M., Terje U., 2006. Mini SEED for LISS and data compression using Steim1 and Steim2. Norweigian National Seismic Network Technical Report.
White T., 2012. Hadoop: The definitive guide. CA Sebastopol: O’Reilly Media, Inc, 2012.
Research on Parallel Decompressing Algorithm for Seismic Waveform Data Based on MapReduce
Liu Fanming1), Guo Ruiqiang1), Li Yongqing2)and Bian Pengfei2)
1) College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China 2) Earthquake Administration of Hebei Province, Shijiazhuang 050021, China
In recent years, the number of SEED files was growing rapidly. In data processing, original algorithm of decompression batch seismic waveform data operated complicatedly and cost much time. In this paper, MapReduce programming model was introduced and a new parallel algorithm based on the thoughts of programming model and original decompression algorithm was presented. Also the design and implementation of this algorithm were given. Comparative experiments were carried out in terms of correctness, efficiency and extensibility. The results showed that the original algorithm spent more time compared to parallel algorithm which implementing decompression rapidly for a large number of seismic waveform data files. Using this method can decompress bulk of seismic waveform data and operate easily.
Seismic waveform data; Decompress; Parallel; MapReduce
河北省重点地区壳幔结构及地震监测预报关键技术研究（13275407D）、河北省教育厅自然科学研究项目（QN20131141）和河北师范大学应用开发基金项目（L2012K01）联合资助
2014-11-03
刘凡鸣，女，生于1990年。河北师范大学数学与信息科学学院硕士研究生。主要研究方向：数据挖掘、分布式计算。E-mail：mingl.0219@163.com
郭瑞强，男，生于1974年。河北师范大学数学与信息科学学院副教授，博士，硕士生导师，中国计算机学会（CCF）会员（E200017546M）。主要研究方向：数据挖掘、WEB智能系统。E-mail：rqguo@126.com
