摘 要： 地震數(shù)據(jù)處理中的數(shù)據(jù)讀取具有塊小量大的特點(diǎn)，常規(guī)磁盤所用的數(shù)據(jù)讀取方式，其處理速度緩慢。設(shè)計(jì)了一種基于FastDFS的分布式地震數(shù)據(jù)存取系統(tǒng)。該系統(tǒng)將數(shù)據(jù)分塊存儲(chǔ)在硬盤上，在FastDFS中建立基于炮號(hào)和道號(hào)的兩級(jí)索引結(jié)構(gòu)，并選取Trie樹作為一級(jí)索引，AVL樹或紅黑樹作為二級(jí)索引，提高了系統(tǒng)讀取速度。實(shí)驗(yàn)結(jié)果表明，該地震數(shù)據(jù)存取系統(tǒng)減少了相應(yīng)的查詢響應(yīng)時(shí)間，提高了系統(tǒng)存取性能。
關(guān)鍵詞： 地震數(shù)據(jù)；兩級(jí)索引；Trie樹；紅黑樹；AVL樹
0 引言
隨著地震勘探技術(shù)快速發(fā)展，地震數(shù)據(jù)規(guī)模不斷增加。數(shù)據(jù)顯示，地震道集數(shù)按每三年翻一番的速度增長(zhǎng)，2014年單文件已經(jīng)突破16 000道[1-2]，這些數(shù)據(jù)量一般在TB甚至PB級(jí)別。當(dāng)今PC集群的計(jì)算性能有了很大提高，但相應(yīng)的集群存儲(chǔ)相對(duì)滯后，地震數(shù)據(jù)存取效率越來(lái)越成為地震資料處理的瓶頸。采用共享網(wǎng)絡(luò)文件系統(tǒng)NFS存取地震數(shù)據(jù)，制約了海量地震數(shù)據(jù)存取的效率[3]。并行文件系統(tǒng)Lustre[4]在存取地震數(shù)據(jù)I/O性能上優(yōu)于NFS[3]，它采用RAID存儲(chǔ)數(shù)據(jù)，擁有高性能的順序讀取效率，但每次需要讀取整個(gè)條帶的數(shù)據(jù)，隨機(jī)讀取效率低。
地震數(shù)據(jù)處理程序請(qǐng)求的數(shù)據(jù)不一定連續(xù)存儲(chǔ)在文件中。處理程序在隨機(jī)請(qǐng)求數(shù)據(jù)時(shí)只需要文件中的若干道數(shù)據(jù)，卻要讀取整個(gè)文件，讀取效率就會(huì)很低。為此，本文提出一種快速存取地震數(shù)據(jù)的方法，該方法將地震文件的數(shù)據(jù)分塊存儲(chǔ)，并建立以炮號(hào)和道號(hào)為關(guān)鍵字的兩級(jí)索引結(jié)構(gòu)。通過(guò)實(shí)驗(yàn)表明，加入索引后，在滿足存取需求的同時(shí)，減少了查詢時(shí)間和數(shù)據(jù)傳輸開銷，提高了系統(tǒng)的存取效率。
1 地震數(shù)據(jù)
1.1 地震數(shù)據(jù)格式
勘探地球物理協(xié)會(huì)（Society of Exploration Geophysicists，SEG）制定的SEGY地震數(shù)據(jù)格式是最常用的數(shù)據(jù)格式，SEGY文件結(jié)構(gòu)如圖1所示。
標(biāo)準(zhǔn)的SEGY格式包括3個(gè)部分：（1）3 200 B的EBCDIC文件頭，保存一些地震數(shù)據(jù)整體性的描述信息；（2）400 B的二進(jìn)制頭文件，用來(lái)保存描述SEGY文件的信息，如文件數(shù)據(jù)格式、采樣點(diǎn)數(shù)目、采樣時(shí)間、測(cè)量單位等；（3）實(shí)際地震勘探數(shù)據(jù)，每道數(shù)據(jù)前面會(huì)有240 B的道頭信息，保存該道數(shù)據(jù)對(duì)應(yīng)的位置坐標(biāo)、采樣點(diǎn)數(shù)、炮號(hào)、道號(hào)等信息。
1.2 數(shù)據(jù)格式的改進(jìn)
地震數(shù)據(jù)道頭主要是記錄道的信息，對(duì)用戶分析數(shù)據(jù)沒有作用，每次讀取地震數(shù)據(jù)還要把道頭數(shù)據(jù)也讀出來(lái)，效率很低。本文將道頭和數(shù)據(jù)體分開存儲(chǔ)，并在兩者之間加入關(guān)鍵字索引信息。用戶每次讀取數(shù)據(jù)，只要指定數(shù)據(jù)關(guān)鍵字，就可以通過(guò)索引查找到該數(shù)據(jù)存放的具體位置。這種方式下用戶每次讀的有效數(shù)據(jù)增多，效率有所改善。
2 兩級(jí)索引結(jié)構(gòu)
2.1 FastDFS介紹及兩級(jí)索引結(jié)構(gòu)
FastDFS充分考慮了冗余備份、負(fù)載均衡、線性擴(kuò)容等機(jī)制，解決了大容量存儲(chǔ)、高并發(fā)訪問等問題。與現(xiàn)有的類Google FS相比，F(xiàn)astDFS的架構(gòu)和設(shè)計(jì)的獨(dú)到之處體現(xiàn)在輕量級(jí)、分組方式和對(duì)等結(jié)構(gòu)[5]。跟蹤器（Tracker）作為中心節(jié)點(diǎn)，提供負(fù)載均衡和任務(wù)調(diào)度；存儲(chǔ)節(jié)點(diǎn)（Storage）則直接利用文件系統(tǒng)存儲(chǔ)文件。FastDFS不對(duì)文件進(jìn)行分塊存儲(chǔ)，上傳文件時(shí)，文件ID由存儲(chǔ)節(jié)點(diǎn)生成并返回給客戶端，文件ID中包含文件所在組名、相對(duì)路徑和文件名。存儲(chǔ)節(jié)點(diǎn)可以直接根據(jù)文件名ID來(lái)定位數(shù)據(jù)。因此FastDFS中不需要存儲(chǔ)索引信息。
本系統(tǒng)為支持順序讀取和隨機(jī)讀取地震道數(shù)據(jù)，對(duì)SEGY文件格式進(jìn)行改進(jìn)，將道頭和數(shù)據(jù)塊分開存儲(chǔ)，在兩者之間建立二級(jí)索引。考慮到跟蹤器負(fù)責(zé)管理數(shù)據(jù)，因此將數(shù)據(jù)塊的位置信息存儲(chǔ)在跟蹤器上，客戶端讀數(shù)據(jù)時(shí)，可以根據(jù)跟蹤器上存儲(chǔ)的信息直接找到存儲(chǔ)數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)，而跟蹤器上的信息就是本文提出的一級(jí)索引。綜上所述，兩級(jí)索引中一級(jí)索引記錄數(shù)據(jù)塊所在存儲(chǔ)節(jié)點(diǎn)號(hào)，二級(jí)索引記錄數(shù)據(jù)塊具體位置。系統(tǒng)框架如圖2所示。
2.2 I/O操作流程
（1）寫數(shù)據(jù)
Client寫數(shù)據(jù)的數(shù)據(jù)頭中包含炮號(hào)、起始和終止道號(hào)及數(shù)據(jù)塊大小等信息，以便跟蹤器和存儲(chǔ)節(jié)點(diǎn)構(gòu)建索引。寫數(shù)據(jù)塊過(guò)程中同一炮號(hào)不同塊的數(shù)據(jù)分布在不同的卷組內(nèi)，以實(shí)現(xiàn)負(fù)載均衡。寫數(shù)據(jù)前Client向跟蹤器詢問可存儲(chǔ)新數(shù)據(jù)塊的存儲(chǔ)節(jié)點(diǎn)，數(shù)據(jù)寫入存儲(chǔ)節(jié)點(diǎn)后，該存儲(chǔ)節(jié)點(diǎn)會(huì)根據(jù)數(shù)據(jù)塊信息（數(shù)據(jù)塊所屬的炮號(hào)、起始道號(hào)、終止道號(hào)）和位置信息構(gòu)建二級(jí)索引。跟蹤器會(huì)根據(jù)存儲(chǔ)節(jié)點(diǎn)報(bào)告的信息構(gòu)建一級(jí)索引，流程如圖3所示。
（2）讀數(shù)據(jù)
Client從存儲(chǔ)節(jié)點(diǎn)讀數(shù)據(jù)時(shí)，命令需要包含炮號(hào)、起始和終止道號(hào)。Client首先查詢跟蹤器上的一級(jí)索引，找到數(shù)據(jù)塊所在的存儲(chǔ)節(jié)點(diǎn)，然后Client向該存儲(chǔ)節(jié)點(diǎn)讀數(shù)據(jù)，存儲(chǔ)節(jié)點(diǎn)則根據(jù)二級(jí)索引查詢數(shù)據(jù)具體位置，并讀出數(shù)據(jù)返回給Client。讀數(shù)據(jù)流程如圖4所示。
3 兩級(jí)索引實(shí)現(xiàn)
3.1 一級(jí)索引
存儲(chǔ)采用共炮存儲(chǔ)，即同一炮的多道數(shù)據(jù)合并后作為一個(gè)數(shù)據(jù)塊存儲(chǔ)在存儲(chǔ)節(jié)點(diǎn)上，數(shù)據(jù)塊名格式為：炮號(hào)_起始道號(hào)_終止道號(hào)，且以此數(shù)據(jù)塊名形成的字符串作為一級(jí)索引的key值，value值是該數(shù)據(jù)塊所在存儲(chǔ)節(jié)點(diǎn)的信息。用戶要查詢第100炮的第0~99道的數(shù)據(jù)，就會(huì)首先生成100_0_99這個(gè)字符串，然后去一級(jí)索引中查找，返回存儲(chǔ)數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)。
一級(jí)索引采用Trie樹，Trie樹利用字符串的公共前綴來(lái)降低查詢時(shí)間以達(dá)到提高效率的目的。Trie樹的插入、刪除和查找都很簡(jiǎn)單，用一個(gè)循環(huán)就可以解決，第i次循環(huán)找到前i個(gè)字符。以靜態(tài)開辟個(gè)數(shù)組來(lái)實(shí)現(xiàn)這棵字符樹，本文每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)有11種情況（0~9和_），需要對(duì)每個(gè)節(jié)點(diǎn)開辟一個(gè)大小為11的數(shù)組。
3.2 二級(jí)索引
紅黑樹[6]在每個(gè)節(jié)點(diǎn)上增加一個(gè)顏色位，可以是Red或Black，通過(guò)限制從根到葉子路徑中各節(jié)點(diǎn)著色方式來(lái)維持平衡，有4種平衡方法[7]。紅黑樹正是用這種非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)旋轉(zhuǎn)次數(shù)的降低，性能比普通二叉樹高。
參考文獻(xiàn)[8]中說(shuō)明當(dāng)操作僅限于插入和檢索時(shí)AVL樹是平衡二叉搜索樹中最有效的方法，在查找和排序上有很重要的應(yīng)用。AVL樹左右子樹高度差超過(guò)1，會(huì)被認(rèn)為是不平衡的，由于AVL樹的這種平衡條件，使樹的深度不會(huì)過(guò)深。參考文獻(xiàn)[9]、[10]中闡述了可能導(dǎo)致AVL樹失去平衡的4種可能，及相應(yīng)的4種旋轉(zhuǎn)方法。
Client查到存儲(chǔ)節(jié)點(diǎn)后通過(guò)炮號(hào)、起始道號(hào)向該存儲(chǔ)節(jié)點(diǎn)查尋二級(jí)索引，找數(shù)據(jù)具體位置。
本文分別采用紅黑樹和AVL樹作為二級(jí)索引，力求尋找一個(gè)性能更佳的二級(jí)索引結(jié)構(gòu)。通過(guò)炮號(hào)及道號(hào)來(lái)唯一標(biāo)識(shí)數(shù)據(jù)塊，于是本文把炮號(hào)和起始道號(hào)組成的聯(lián)合體組合成一個(gè)唯一長(zhǎng)整形數(shù)，代碼如下。以此作為該二級(jí)索引key值，對(duì)應(yīng)的value值為該數(shù)據(jù)塊的位置信息。
二級(jí)索引關(guān)鍵字結(jié)構(gòu)代碼：
typedef union
{
struct
{
int shot_no；//炮號(hào)
int begin_receiver_no；//起始道號(hào)
}combine_no；
long long index_key；
}StorageIndexKey_t；
4 實(shí)驗(yàn)與結(jié)果
4.1 實(shí)驗(yàn)環(huán)境
本實(shí)驗(yàn)集群由5臺(tái)服務(wù)器組成，1臺(tái)client、1臺(tái)跟蹤器和3臺(tái)存儲(chǔ)節(jié)點(diǎn)。每臺(tái)服務(wù)器CPU均為2.33 GHz，內(nèi)存為4 GB，操作系統(tǒng)是CentOS6.4。
4.2 實(shí)驗(yàn)和結(jié)果
本文提出的地震數(shù)據(jù)存取系統(tǒng)是基于FastDFS修改而來(lái)的。一級(jí)索引采用Trie樹，二級(jí)索引加入AVL樹的版本命名為AVLFS，加入紅黑樹的版本命名為RBFS。每道數(shù)據(jù)32 KB，將100道數(shù)據(jù)作為一個(gè)數(shù)據(jù)塊。采用以下兩種方法進(jìn)行測(cè)試：（1）寫入相同數(shù)據(jù)塊，測(cè)試讀取速度隨著讀的有效數(shù)據(jù)大小變化的關(guān)系；（2）讀取有效數(shù)據(jù)一定，測(cè)試速度隨著寫入數(shù)據(jù)量變化的關(guān)系。
實(shí)驗(yàn)1 寫入200炮的數(shù)據(jù)，每炮100個(gè)數(shù)據(jù)塊，一共20 000個(gè)數(shù)據(jù)塊。讀取分布在不同數(shù)據(jù)塊中的道，測(cè)試結(jié)果如圖5所示。
實(shí)驗(yàn)2 讀取8 000道地震數(shù)據(jù)，這8 000道數(shù)據(jù)分布在不同數(shù)據(jù)塊，結(jié)果如圖6所示。
圖5顯示，與FastDFS相比，加入兩級(jí)索引的地震數(shù)據(jù)存取系統(tǒng)在隨機(jī)讀的速度上有了8~10倍的提升，隨著數(shù)據(jù)塊請(qǐng)求數(shù)的增加，速度也有所提升，這是由于多磁盤并發(fā)讀取使得速度有所增加。圖6中隨著寫數(shù)據(jù)塊個(gè)數(shù)的增多讀取速度幾乎沒有影響，這說(shuō)明索引性能沒有隨著寫數(shù)據(jù)塊個(gè)數(shù)增加而降低。通過(guò)圖5、圖6，還可得出二級(jí)索引采用AVL樹在讀取速度上優(yōu)于紅黑樹，主要是AVL樹比紅黑樹更加平衡，查詢效率更快。
5 結(jié)論
本文提出一種能夠快速存取地震數(shù)據(jù)的方法，該方法將數(shù)據(jù)分塊存儲(chǔ)，并建立兩級(jí)索引結(jié)構(gòu)。實(shí)驗(yàn)表明，加入兩級(jí)索引后滿足了對(duì)地震數(shù)據(jù)隨機(jī)讀取的要求，同時(shí)減少了查詢時(shí)間和數(shù)據(jù)傳輸開銷，系統(tǒng)讀取速度有很大提高。針對(duì)查詢操作，AVL樹優(yōu)于紅黑樹索引，而地震數(shù)據(jù)存取就是一次存儲(chǔ)，多次讀取，故本系統(tǒng)最終選擇AVL樹作為二級(jí)索引。本文后續(xù)工作將會(huì)對(duì)兩級(jí)索引進(jìn)行進(jìn)一步優(yōu)化。
參考文獻(xiàn)
[1] 張捷.石油勘探地震數(shù)據(jù)的處理和成像問題[R].合肥：中國(guó)科學(xué)技術(shù)大學(xué)地球物理研究所，2013.
[2] 趙改善.我們需要多大和多快的計(jì)算機(jī)[J].勘探地球物理進(jìn)展，2004，27（1）：23-28.
[3] 杜吉國(guó)，孫孝萍，陳繼紅，等.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].潘金貴，顧鐵成，李成法，等，譯.北京：機(jī)械工業(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.