一種面向地震數(shù)據(jù)的兩級索引

谷文彥，李 俊，潘昌森（中國科學(xué)技術(shù)大學(xué) 自動化系，安徽 合肥 230026）

一種面向地震數(shù)據(jù)的兩級索引

谷文彥，李 俊，潘昌森
（中國科學(xué)技術(shù)大學(xué) 自動化系，安徽 合肥 230026）

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

地震數(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集群的計(jì)算性能有了很大提高，但相應(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ù)，隨機(jī)讀取效率低。

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

圖1 SEGY格式

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

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

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

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

圖2 兩級索引框架

2.2 I/O操作流程

（1）寫數(shù)據(jù)

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

圖3 寫流程

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

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

圖4 讀流程

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

3.1 一級索引

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

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

3.2 二級索引

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

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 實(shí)驗(yàn)和結(jié)果

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

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

圖5 速度隨讀請求的變化關(guān)系

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

圖6 速度隨寫數(shù)據(jù)塊數(shù)量的變化關(guān)系

圖5顯示，與FastDFS相比，加入兩級索引的地震數(shù)據(jù)存取系統(tǒng)在隨機(jī)讀的速度上有了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í)驗(yàn)表明，加入兩級索引后滿足了對地震數(shù)據(jù)隨機(jī)讀取的要求，同時減少了查詢時間和數(shù)據(jù)傳輸開銷，系統(tǒng)讀取速度有很大提高。針對查詢操作，AVL樹優(yōu)于紅黑樹索引，而地震數(shù)據(jù)存取就是一次存儲，多次讀取，故本系統(tǒng)最終選擇AVL樹作為二級索引。本文后續(xù)工作將會對兩級索引進(jìn)行進(jìn)一步優(yōu)化。

參考文獻(xiàn)

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

［2］趙改善.我們需要多大和多快的計(jì)算機(jī)［J］.勘探地球物理進(jìn)展，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 LR，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.

A two level index for seismic data

Gu Wenyan，Li Jun，Pan Changsen
（Department of Automation，University of Science and Technology of China，Hefei 230026，China）

Read data in seismic data processing has a characteristics of small piece and large number，and for the conventional disk read mode，its processing speed is slow.This paper designed a distributed seismic data access system based on FastDFS.This system stored the data in hard disk based on block，and established two level index structure based on the shot number and gather number in FastDFS.It selected Trie tree as the primary index，AVL tree or red-black tree as the secondary indexes，to improve the reading speed of the system.The experimental results show that the seismic data access system created in this paper has reduced the query response time，and can improve the performance of system access.

seismic data；two level index；Trie tree；red-black tree；AVL tree

TP316.4

A

1674-7720（2015）18-0026-03

谷文彥，李俊，潘昌森.一種面向地震數(shù)據(jù)的兩級索引［J］.微型機(jī)與應(yīng)用，2015，34（18）：26-28，35.

2015-04-20）

谷文彥（1988-），男，碩士研究生，主要研究方向：網(wǎng)絡(luò)軟件開發(fā)、嵌入式軟件開發(fā)。

李?。?973-），男，博士，副教授，碩士研究生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)傳播與控制。

潘昌森（1990-），男，碩士研究生，主要研究方向：網(wǎng)絡(luò)軟件開發(fā)、大數(shù)據(jù)。