《電子技術應用》
您所在的位置:首頁 > 測試測量 > 設計應用 > 一種面向地震數(shù)據(jù)的兩級索引
一種面向地震數(shù)據(jù)的兩級索引
2015年微型機與應用第18期
谷文彥,,李 俊,潘昌森
(中國科學技術大學 自動化系,,安徽 合肥 230026)
摘要: 地震數(shù)據(jù)處理中的數(shù)據(jù)讀取具有塊小量大的特點,,常規(guī)磁盤所用的數(shù)據(jù)讀取方式,其處理速度緩慢,。設計了一種基于FastDFS的分布式地震數(shù)據(jù)存取系統(tǒng),。該系統(tǒng)將數(shù)據(jù)分塊存儲在硬盤上,,在FastDFS中建立基于炮號和道號的兩級索引結(jié)構(gòu),并選取Trie樹作為一級索引,,AVL樹或紅黑樹作為二級索引,,提高了系統(tǒng)讀取速度。實驗結(jié)果表明,,該地震數(shù)據(jù)存取系統(tǒng)減少了相應的查詢響應時間,,提高了系統(tǒng)存取性能。
Abstract:
Key words :

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

  關鍵詞: 地震數(shù)據(jù),;兩級索引,;Trie樹;紅黑樹,;AVL樹

0 引言

  隨著地震勘探技術快速發(fā)展,,地震數(shù)據(jù)規(guī)模不斷增加。數(shù)據(jù)顯示,,地震道集數(shù)按每三年翻一番的速度增長,,2014年單文件已經(jīng)突破16 000道[1-2],這些數(shù)據(jù)量一般在TB甚至PB級別,。當今PC集群的計算性能有了很大提高,,但相應的集群存儲相對滯后,地震數(shù)據(jù)存取效率越來越成為地震資料處理的瓶頸,。采用共享網(wǎng)絡文件系統(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ù)分塊存儲,,并建立以炮號和道號為關鍵字的兩級索引結(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所示,。

001.jpg

  標準的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ù)對應的位置坐標,、采樣點數(shù),、炮號、道號等信息,。

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

  地震數(shù)據(jù)道頭主要是記錄道的信息,,對用戶分析數(shù)據(jù)沒有作用,每次讀取地震數(shù)據(jù)還要把道頭數(shù)據(jù)也讀出來,,效率很低,。本文將道頭和數(shù)據(jù)體分開存儲,并在兩者之間加入關鍵字索引信息,。用戶每次讀取數(shù)據(jù),,只要指定數(shù)據(jù)關鍵字,就可以通過索引查找到該數(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)和設計的獨到之處體現(xiàn)在輕量級,、分組方式和對等結(jié)構(gòu)[5]。跟蹤器(Tracker)作為中心節(jié)點,,提供負載均衡和任務調(diào)度,;存儲節(jié)點(Storage)則直接利用文件系統(tǒng)存儲文件。FastDFS不對文件進行分塊存儲,,上傳文件時,,文件ID由存儲節(jié)點生成并返回給客戶端,文件ID中包含文件所在組名,、相對路徑和文件名,。存儲節(jié)點可以直接根據(jù)文件名ID來定位數(shù)據(jù)。因此FastDFS中不需要存儲索引信息,。

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

002.jpg

  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所示,。

003.jpg

 ?。?)讀數(shù)據(jù)

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

004.jpg

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

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

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

  二級索引關鍵字結(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臺服務器組成,,1臺client、1臺跟蹤器和3臺存儲節(jié)點,。每臺服務器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ù)大小變化的關系,;(2)讀取有效數(shù)據(jù)一定,測試速度隨著寫入數(shù)據(jù)量變化的關系,。

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

005.jpg

  實驗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].合肥:中國科學技術大學地球物理研究所,,2013.

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

  [3] 杜吉國,,孫孝萍,陳繼紅,,等.Lustre并行文件系統(tǒng)在地震數(shù)據(jù)處理中的應用[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.算法導論[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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載。