摘  要： 地震數(shù)據(jù)處理中的數(shù)據(jù)讀取具有塊小量大的特點，常規(guī)磁盤所用的數(shù)據(jù)讀取方式，其處理速度緩慢。設(shè)計了一種基于FastDFS的分布式地震數(shù)據(jù)存取系統(tǒng)。該系統(tǒng)將數(shù)據(jù)分塊存儲在硬盤上，在FastDFS中建立基于炮號和道號的兩級索引結(jié)構(gòu)，并選取Trie樹作為一級索引，AVL樹或紅黑樹作為二級索引，提高了系統(tǒng)讀取速度。實驗結(jié)果表明，該地震數(shù)據(jù)存取系統(tǒng)減少了相應(yīng)的查詢響應(yīng)時間，提高了系統(tǒng)存取性能。

　　關(guān)鍵詞： 地震數(shù)據(jù)；兩級索引；Trie樹；紅黑樹；AVL樹

0 引言

　　隨著地震勘探技術(shù)快速發(fā)展，地震數(shù)據(jù)規(guī)模不斷增加。數(shù)據(jù)顯示，地震道集數(shù)按每三年翻一番的速度增長，2014年單文件已經(jīng)突破16 000道[1-2]，這些數(shù)據(jù)量一般在TB甚至PB級別。當(dāng)今PC集群的計算性能有了很大提高，但相應(yīng)的集群存儲相對滯后，地震數(shù)據(jù)存取效率越來越成為地震資料處理的瓶頸。采用共享網(wǎng)絡(luò)文件系統(tǒng)NFS存取地震數(shù)據(jù)，制約了海量地震數(shù)據(jù)存取的效率[3]。并行文件系統(tǒng)Lustre[4]在存取地震數(shù)據(jù)I/O性能上優(yōu)于NFS[3]，它采用RAID存儲數(shù)據(jù)，擁有高性能的順序讀取效率，但每次需要讀取整個條帶的數(shù)據(jù)，隨機讀取效率低。

　　地震數(shù)據(jù)處理程序請求的數(shù)據(jù)不一定連續(xù)存儲在文件中。處理程序在隨機請求數(shù)據(jù)時只需要文件中的若干道數(shù)據(jù)，卻要讀取整個文件，讀取效率就會很低。為此，本文提出一種快速存取地震數(shù)據(jù)的方法，該方法將地震文件的數(shù)據(jù)分塊存儲，并建立以炮號和道號為關(guān)鍵字的兩級索引結(jié)構(gòu)。通過實驗表明，加入索引后，在滿足存取需求的同時，減少了查詢時間和數(shù)據(jù)傳輸開銷，提高了系統(tǒng)的存取效率。

1 地震數(shù)據(jù)

　　1.1 地震數(shù)據(jù)格式

　　勘探地球物理協(xié)會（Society of Exploration Geophysicists，SEG）制定的SEGY地震數(shù)據(jù)格式是最常用的數(shù)據(jù)格式，SEGY文件結(jié)構(gòu)如圖1所示。

　　標(biāo)準(zhǔn)的SEGY格式包括3個部分：（1）3 200 B的EBCDIC文件頭，保存一些地震數(shù)據(jù)整體性的描述信息；（2）400 B的二進制頭文件，用來保存描述SEGY文件的信息，如文件數(shù)據(jù)格式、采樣點數(shù)目、采樣時間、測量單位等；（3）實際地震勘探數(shù)據(jù)，每道數(shù)據(jù)前面會有240 B的道頭信息，保存該道數(shù)據(jù)對應(yīng)的位置坐標(biāo)、采樣點數(shù)、炮號、道號等信息。

　　1.2 數(shù)據(jù)格式的改進

　　地震數(shù)據(jù)道頭主要是記錄道的信息，對用戶分析數(shù)據(jù)沒有作用，每次讀取地震數(shù)據(jù)還要把道頭數(shù)據(jù)也讀出來，效率很低。本文將道頭和數(shù)據(jù)體分開存儲，并在兩者之間加入關(guān)鍵字索引信息。用戶每次讀取數(shù)據(jù)，只要指定數(shù)據(jù)關(guān)鍵字，就可以通過索引查找到該數(shù)據(jù)存放的具體位置。這種方式下用戶每次讀的有效數(shù)據(jù)增多，效率有所改善。

2 兩級索引結(jié)構(gòu)

　　2.1 FastDFS介紹及兩級索引結(jié)構(gòu)

　　FastDFS充分考慮了冗余備份、負載均衡、線性擴容等機制，解決了大容量存儲、高并發(fā)訪問等問題。與現(xiàn)有的類Google FS相比，F(xiàn)astDFS的架構(gòu)和設(shè)計的獨到之處體現(xiàn)在輕量級、分組方式和對等結(jié)構(gòu)[5]。跟蹤器（Tracker）作為中心節(jié)點，提供負載均衡和任務(wù)調(diào)度；存儲節(jié)點（Storage）則直接利用文件系統(tǒng)存儲文件。FastDFS不對文件進行分塊存儲，上傳文件時，文件ID由存儲節(jié)點生成并返回給客戶端，文件ID中包含文件所在組名、相對路徑和文件名。存儲節(jié)點可以直接根據(jù)文件名ID來定位數(shù)據(jù)。因此FastDFS中不需要存儲索引信息。

　　本系統(tǒng)為支持順序讀取和隨機讀取地震道數(shù)據(jù)，對SEGY文件格式進行改進，將道頭和數(shù)據(jù)塊分開存儲，在兩者之間建立二級索引。考慮到跟蹤器負責(zé)管理數(shù)據(jù)，因此將數(shù)據(jù)塊的位置信息存儲在跟蹤器上，客戶端讀數(shù)據(jù)時，可以根據(jù)跟蹤器上存儲的信息直接找到存儲數(shù)據(jù)的存儲節(jié)點，而跟蹤器上的信息就是本文提出的一級索引。綜上所述，兩級索引中一級索引記錄數(shù)據(jù)塊所在存儲節(jié)點號，二級索引記錄數(shù)據(jù)塊具體位置。系統(tǒng)框架如圖2所示。

　　2.2 I/O操作流程

　?。?）寫數(shù)據(jù)

　　Client寫數(shù)據(jù)的數(shù)據(jù)頭中包含炮號、起始和終止道號及數(shù)據(jù)塊大小等信息，以便跟蹤器和存儲節(jié)點構(gòu)建索引。寫數(shù)據(jù)塊過程中同一炮號不同塊的數(shù)據(jù)分布在不同的卷組內(nèi)，以實現(xiàn)負載均衡。寫數(shù)據(jù)前Client向跟蹤器詢問可存儲新數(shù)據(jù)塊的存儲節(jié)點，數(shù)據(jù)寫入存儲節(jié)點后，該存儲節(jié)點會根據(jù)數(shù)據(jù)塊信息（數(shù)據(jù)塊所屬的炮號、起始道號、終止道號）和位置信息構(gòu)建二級索引。跟蹤器會根據(jù)存儲節(jié)點報告的信息構(gòu)建一級索引，流程如圖3所示。

　　（2）讀數(shù)據(jù)

　　Client從存儲節(jié)點讀數(shù)據(jù)時，命令需要包含炮號、起始和終止道號。Client首先查詢跟蹤器上的一級索引，找到數(shù)據(jù)塊所在的存儲節(jié)點，然后Client向該存儲節(jié)點讀數(shù)據(jù)，存儲節(jié)點則根據(jù)二級索引查詢數(shù)據(jù)具體位置，并讀出數(shù)據(jù)返回給Client。讀數(shù)據(jù)流程如圖4所示。

3 兩級索引實現(xiàn)

　　3.1 一級索引

　　存儲采用共炮存儲，即同一炮的多道數(shù)據(jù)合并后作為一個數(shù)據(jù)塊存儲在存儲節(jié)點上，數(shù)據(jù)塊名格式為：炮號_起始道號_終止道號，且以此數(shù)據(jù)塊名形成的字符串作為一級索引的key值，value值是該數(shù)據(jù)塊所在存儲節(jié)點的信息。用戶要查詢第100炮的第0~99道的數(shù)據(jù)，就會首先生成100_0_99這個字符串，然后去一級索引中查找，返回存儲數(shù)據(jù)的存儲節(jié)點。

　　一級索引采用Trie樹，Trie樹利用字符串的公共前綴來降低查詢時間以達到提高效率的目的。Trie樹的插入、刪除和查找都很簡單，用一個循環(huán)就可以解決，第i次循環(huán)找到前i個字符。以靜態(tài)開辟個數(shù)組來實現(xiàn)這棵字符樹，本文每個節(jié)點的子節(jié)點有11種情況（0~9和_），需要對每個節(jié)點開辟一個大小為11的數(shù)組。

　　3.2 二級索引

　　紅黑樹[6]在每個節(jié)點上增加一個顏色位，可以是Red或Black，通過限制從根到葉子路徑中各節(jié)點著色方式來維持平衡，有4種平衡方法[7]。紅黑樹正是用這種非嚴格的平衡來換取增刪節(jié)點時旋轉(zhuǎn)次數(shù)的降低，性能比普通二叉樹高。

　　參考文獻[8]中說明當(dāng)操作僅限于插入和檢索時AVL樹是平衡二叉搜索樹中最有效的方法，在查找和排序上有很重要的應(yīng)用。AVL樹左右子樹高度差超過1，會被認為是不平衡的，由于AVL樹的這種平衡條件，使樹的深度不會過深。參考文獻[9]、[10]中闡述了可能導(dǎo)致AVL樹失去平衡的4種可能，及相應(yīng)的4種旋轉(zhuǎn)方法。

　　Client查到存儲節(jié)點后通過炮號、起始道號向該存儲節(jié)點查尋二級索引，找數(shù)據(jù)具體位置。

　　本文分別采用紅黑樹和AVL樹作為二級索引，力求尋找一個性能更佳的二級索引結(jié)構(gòu)。通過炮號及道號來唯一標(biāo)識數(shù)據(jù)塊，于是本文把炮號和起始道號組成的聯(lián)合體組合成一個唯一長整形數(shù)，代碼如下。以此作為該二級索引key值，對應(yīng)的value值為該數(shù)據(jù)塊的位置信息。

　　二級索引關(guān)鍵字結(jié)構(gòu)代碼：

　　typedef  union

　　{

　　struct

　　{

　　int shot_no；//炮號

　　int begin_receiver_no；//起始道號

　　}combine_no；

　　long long index_key；

　　}StorageIndexKey_t；

4 實驗與結(jié)果

　　4.1 實驗環(huán)境

　　本實驗集群由5臺服務(wù)器組成，1臺client、1臺跟蹤器和3臺存儲節(jié)點。每臺服務(wù)器CPU均為2.33 GHz，內(nèi)存為4 GB，操作系統(tǒng)是CentOS6.4。

　　4.2 實驗和結(jié)果

　　本文提出的地震數(shù)據(jù)存取系統(tǒng)是基于FastDFS修改而來的。一級索引采用Trie樹，二級索引加入AVL樹的版本命名為AVLFS，加入紅黑樹的版本命名為RBFS。每道數(shù)據(jù)32 KB，將100道數(shù)據(jù)作為一個數(shù)據(jù)塊。采用以下兩種方法進行測試：（1）寫入相同數(shù)據(jù)塊，測試讀取速度隨著讀的有效數(shù)據(jù)大小變化的關(guān)系；（2）讀取有效數(shù)據(jù)一定，測試速度隨著寫入數(shù)據(jù)量變化的關(guān)系。

　　實驗1 寫入200炮的數(shù)據(jù)，每炮100個數(shù)據(jù)塊，一共20 000個數(shù)據(jù)塊。讀取分布在不同數(shù)據(jù)塊中的道，測試結(jié)果如圖5所示。

　　實驗2 讀取8 000道地震數(shù)據(jù)，這8 000道數(shù)據(jù)分布在不同數(shù)據(jù)塊，結(jié)果如圖6所示。

　　圖5顯示，與FastDFS相比，加入兩級索引的地震數(shù)據(jù)存取系統(tǒng)在隨機讀的速度上有了8~10倍的提升，隨著數(shù)據(jù)塊請求數(shù)的增加，速度也有所提升，這是由于多磁盤并發(fā)讀取使得速度有所增加。圖6中隨著寫數(shù)據(jù)塊個數(shù)的增多讀取速度幾乎沒有影響，這說明索引性能沒有隨著寫數(shù)據(jù)塊個數(shù)增加而降低。通過圖5、圖6，還可得出二級索引采用AVL樹在讀取速度上優(yōu)于紅黑樹，主要是AVL樹比紅黑樹更加平衡，查詢效率更快。

5 結(jié)論

　　本文提出一種能夠快速存取地震數(shù)據(jù)的方法，該方法將數(shù)據(jù)分塊存儲，并建立兩級索引結(jié)構(gòu)。實驗表明，加入兩級索引后滿足了對地震數(shù)據(jù)隨機讀取的要求，同時減少了查詢時間和數(shù)據(jù)傳輸開銷，系統(tǒng)讀取速度有很大提高。針對查詢操作，AVL樹優(yōu)于紅黑樹索引，而地震數(shù)據(jù)存取就是一次存儲，多次讀取，故本系統(tǒng)最終選擇AVL樹作為二級索引。本文后續(xù)工作將會對兩級索引進行進一步優(yōu)化。

參考文獻

　　[1] 張捷.石油勘探地震數(shù)據(jù)的處理和成像問題[R].合肥：中國科學(xué)技術(shù)大學(xué)地球物理研究所，2013.

　　[2] 趙改善.我們需要多大和多快的計算機[J].勘探地球物理進展，2004，27（1）：23-28.

　　[3] 杜吉國，孫孝萍，陳繼紅，等.Lustre并行文件系統(tǒng)在地震數(shù)據(jù)處理中的應(yīng)用[J].物探裝備，2013，23（5）：294-299.

　　[4] Lustre[EB/OL]（2015-03-31）.http：//wiki.lustre.org/index.php/Main_page.

　　[5] 余慶.分布式文件系統(tǒng)FastDFS架構(gòu)剖析[J].程序員，2010（11）：63-65.

　　[6] Rudolf Bayer. Symmetric binary B-Trees： data structure and maintenance algorithms[J]. Acta Informatica， 1972，1（4）：290-306.

　　[7] THOMAS H C， CHARLES E L， RONALD L R， et al.算法導(dǎo)論[M].潘金貴，顧鐵成，李成法，等，譯.北京：機械工業(yè)出版社，2006.

　　[8] BAER J L， SCHWAB B. A comparison of tree-balancing algorithms[J]. Communication of the ACM， 1977，20（5）： 322-330.

　　[9] ELLIS C S. Concurrent search and insertion in AVL Trees[J]. IEEE Transactions on Computers， 1980，29（9）：811-817.

　　[10] CHAUHAN S， THAKUR S， RANA S， et al. A brief Study of balancing of AVL Tree[J]. International Journal of Research， 2014，1（11）：406-408.