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

　　關鍵詞： 地震數據；兩級索引；Trie樹；紅黑樹；AVL樹

0 引言

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

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

1 地震數據

　　1.1 地震數據格式

　　勘探地球物理協會（Society of Exploration Geophysicists，SEG）制定的SEGY地震數據格式是最常用的數據格式，SEGY文件結構如圖1所示。

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

　　1.2 數據格式的改進

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

2 兩級索引結構

　　2.1 FastDFS介紹及兩級索引結構

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

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

　　2.2 I/O操作流程

　?。?）寫數據

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

　?。?）讀數據

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

3 兩級索引實現

　　3.1 一級索引

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

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

　　3.2 二級索引

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

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

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

　　本文分別采用紅黑樹和AVL樹作為二級索引，力求尋找一個性能更佳的二級索引結構。通過炮號及道號來唯一標識數據塊，于是本文把炮號和起始道號組成的聯合體組合成一個唯一長整形數，代碼如下。以此作為該二級索引key值，對應的value值為該數據塊的位置信息。

　　二級索引關鍵字結構代碼：

　　typedef  union

　　{

　　struct

　　{

　　int shot_no；//炮號

　　int begin_receiver_no；//起始道號

　　}combine_no；

　　long long index_key；

　　}StorageIndexKey_t；

4 實驗與結果

　　4.1 實驗環境

　　本實驗集群由5臺服務器組成，1臺client、1臺跟蹤器和3臺存儲節點。每臺服務器CPU均為2.33 GHz，內存為4 GB，操作系統是CentOS6.4。

　　4.2 實驗和結果

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

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

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

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

5 結論

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

參考文獻

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

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

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

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

　　[5] 余慶.分布式文件系統FastDFS架構剖析[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.算法導論[M].潘金貴，顧鐵成，李成法，等，譯.北京：機械工業出版社，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.