基于MapReduce的地震波形數據并行解壓縮算法研究1

劉凡鳴 郭瑞強 李永慶 邊鵬飛

?

基于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程序，就可以進行并行程序的開發。

輸入數據可以看成是若干個對的集合，MapReduce的工作原理體現了分治思想，將輸入數據切分成若干片，然后交由集群內的不同節點同步處理，以此實現程序的并行化，其處理流程如圖1所示。在Map階段，MapReduce可根據用戶自定義的Map函數，讓每個Map節點處理由若干個對構成的分片，而輸出的中間結果是新的對集合，處理過程可表示為：

Map: (k1，v1)→List (k2，v2)

之后混洗操作將key值相同的對聚集到一起傳遞給Reduce。各個Reduce節點再根據用戶自定義的Reduce函數，處理具有相同key值的value集合，最后生成新的對集合輸出，處理過程可表示為：

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的一個重要接口，其中包含輸入數據切片方法以及每個從分片讀取鍵值對的方法。通常系統默認的是按行提取鍵值對，即中的key代表行偏移量，value代表該行內容。但是由于SEED文件中既有ASCII格式數據，又有二進制格式數據，而二進制數據中沒有換行的概念，因此現有的按行提取鍵值對的方法不能滿足需求，需要自定義適合地震數據處理的Inputformat。因為解壓縮操作使用的是SEED文件的數據塊部分，所以在讀取鍵值對的方法中設置跳過文件的4個控制頭段，將數據塊的第一個字節處作為起始位置，每4096個字節為一條記錄，每條記錄作為value，該條記錄所在文件名作為key，將分片解析成<文件名，數據記錄>這樣的對格式作為輸入。

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