曹晉 彭成

關鍵詞：分布式；八叉樹；地震數(shù)據(jù)；多級緩存；雙向鏈表

0 引言

隨著石油勘探工作的不斷深入及勘探范圍的不斷擴大，油氣分布由早期的構造性油氣藏分布向隱蔽性油氣藏分布逐步過渡[1]。面對越來越復雜的地質(zhì)構造，單位數(shù)據(jù)采集量不斷增加，采集的地震數(shù)據(jù)日益龐大[2]。然而，相關地震數(shù)據(jù)處理技術、可視化手段仍停留在早期的簡單數(shù)據(jù)處理階段，遠遠滯后于地震數(shù)據(jù)采集技術的發(fā)展，已無法滿足當前勘探處理對象的精度和深度要求[3-4]。如何提高和改進地震資料處理技術已成為當前物探工作中亟待解決的首要問題[5]。

隨著計算機技術的飛速發(fā)展，在地理勘探領域中，深部探測會產(chǎn)生超大規(guī)模地震數(shù)據(jù)SEGY文件，其文件規(guī)模能達到TB量級[6]。傳統(tǒng)的地學應用在數(shù)據(jù)處理過程中采用一次加載、反復使用的模式。但是，當數(shù)據(jù)規(guī)模遠超內(nèi)存時，將不能使用傳統(tǒng)加載模式對數(shù)據(jù)進行處理[7-8]。為此，地震數(shù)據(jù)需要采用文件格式與內(nèi)存管理兩種手段支持超大規(guī)模數(shù)據(jù)。這種超大規(guī)模地震數(shù)據(jù)的處理手段目前被國外技術壟斷[9]。

如何利用現(xiàn)代計算機的高速處理能力，提高地震數(shù)據(jù)處理精度及地震數(shù)據(jù)顯示速度，是目前迫切需要解決的重要問題[9]。迄今為止，國內(nèi)外眾多石油地球物理勘探公司、相關高校研究院所投入了大量的資金和技術力量，致力于地震數(shù)據(jù)處理相關技術的研究[10]。

傳統(tǒng)的地震資料處理系統(tǒng)以地震道為數(shù)據(jù)輸入輸出單元，難以集成基于道集的復雜處理算法，并且數(shù)據(jù)I/O效率低。為了更快地響應地震數(shù)據(jù)查詢請求，需要設計合適的存儲結構及內(nèi)存緩沖機制。本方法利用三維空間下八叉樹結構與編碼的快速空間定位機制，實現(xiàn)對三維大數(shù)據(jù)體的結構分塊存儲，同時設計了二級緩存結構，提升了數(shù)據(jù)訪問效率。

1 八叉樹編碼與分塊存儲

對地震數(shù)據(jù)按照設定的小立方體大小進行切分，生成若干子塊文件，實現(xiàn)八叉樹結構的地震分塊存儲。八叉樹編碼使用的是線性莫頓（Morton） 編碼。莫頓碼本質(zhì)上是一種八進制碼，如圖1所示，每一位八進制數(shù)位可以看成3位二進制數(shù)，由所在節(jié)點的空間位置編碼而來（其中，n 表示子體數(shù)據(jù)塊所處的空間結構位置）：Morton = [（x0，y0，z0），（x1，y1，z1），...，（xn-1，yn-1，zn-1）]。切分時的每個子塊都會有其對應的莫頓碼，從莫頓碼也可以反推出子塊對應的空間范圍。莫頓碼的位數(shù)等于切分的層級數(shù)，層級越小，莫頓碼越短，切分的粒度越粗，層級越大，莫頓碼越長，切分的粒度越細，本方法中只切分生成最終一級的子塊，其他層級的子塊并不進行切分生成。

八叉樹節(jié)點體現(xiàn)了空間坐標信息，同時易于實現(xiàn)自然數(shù)的映射，即某一體數(shù)據(jù)塊的具體文件存儲位置。莫頓碼按照大小排序得到子塊的自然數(shù)編碼（Tile ID） ，進而映射到不同體數(shù)據(jù)塊文件存儲位置。

在利用八叉樹子塊來讀取地震數(shù)據(jù)時，通過輸入的主測線號、聯(lián)絡線號和深度范圍得到其在源地震數(shù)據(jù)立方體中相應的空間范圍，進而轉(zhuǎn)換成一組對應的線性莫頓（Morton） 編碼，然后以子塊自然數(shù)編碼（TileID） 為索引定位數(shù)據(jù)在文件中的存儲位置；同樣，給出數(shù)據(jù)存儲位置，也可以計算子塊自然數(shù)編碼（Tile ID） ，得到它在體數(shù)據(jù)或八叉樹中的空間位置。自然數(shù)編碼（Tile ID） 從零開始，對應最終層級中莫頓碼最小的子塊，依次類推。數(shù)據(jù)在子塊中的具體位置由空間范圍與子塊三個方向的長度除余得到起始偏移量，然后從起始位置讀取地震數(shù)據(jù)。

2 基于地震道的一級緩存結構

構成地震數(shù)據(jù)文件的基本單元是地震道，相當于地震數(shù)據(jù)立方體高方向上的一整條。地震道包括道頭和具體的地震數(shù)據(jù)，道頭中含有地震道的主測線號、聯(lián)絡線號、起止時間、地震數(shù)據(jù)點個數(shù)等信息。對于地震數(shù)據(jù)的查詢請求通常是給定主測線號、聯(lián)絡線號、起止時間、返回對應位置范圍的地震數(shù)據(jù)。

一級緩存就是在內(nèi)存中存放一組地震道，每次查詢請求傳過來時，如果存在滿足要求的緩存地震道，則直接返回結果。地震道緩存結構如圖2所示，測網(wǎng)中偏移指地震道在主測線和聯(lián)絡線構成的測網(wǎng)平面上的位置；地震數(shù)據(jù)中存放了此道在起始時間和終止時間范圍內(nèi)的地震數(shù)據(jù)；采樣間隔是相鄰兩個地震數(shù)據(jù)樣本點的采樣時間間隔，通過間隔和時間，建立起采樣點與采樣時間的對應關系；道集大小對于疊后數(shù)據(jù)為1，對于疊前數(shù)據(jù)，同樣的主測線和聯(lián)絡線下，對應的是一組地震道而不是一條地震道，此時道集大小為這組地震道的個數(shù)，地震數(shù)據(jù)中順序存放各個地震道；最大最小振幅表示此道地震數(shù)據(jù)的絕對值的最大最小值；命中次數(shù)表示此緩存被使用了多少次，后面在內(nèi)存不夠需要刪除部分緩存道時，會根據(jù)此值大小，優(yōu)先刪除使 用次數(shù)少的地震道緩存。

3 基于八叉樹子塊的二級緩存結構

二級緩存是對子塊的緩存，當一級緩存中不存在對應結果時，就會繼續(xù)從二級緩存去尋找。每個二級緩存相當于將一個子塊文件加載到內(nèi)存中，其數(shù)據(jù)結構如圖3所示，莫頓碼表示此子塊的線性莫頓（Mor?ton） 編碼；塊編碼是塊的自然數(shù)編碼（Tile ID） ；中心坐標是此子塊的空間位置范圍的中心點；地震數(shù)據(jù)存放了子塊中所有的地震數(shù)據(jù)；地震數(shù)據(jù)大小表示這些地震數(shù)據(jù)的個數(shù)；命中次數(shù)表示此緩存被用到的次數(shù)；塊大小表示這個子塊在三個方向上長度的乘積，即子塊立方體體積；前一個塊和后一個塊表示前面和后面的子塊緩存，二級緩存采用的是雙向鏈表緩沖技術，如圖4所示，這種結構可以避免數(shù)據(jù)塊在內(nèi)存中的頻繁遷移。同時，根據(jù)訪問頻度等信息組織子體數(shù)據(jù)塊索引，確保在鏈表末端的數(shù)據(jù)是最少被訪問的數(shù)據(jù)，可以優(yōu)先剔除出內(nèi)存，而那些最近被使用的數(shù)據(jù)將放在最前端。

4 一級緩存的生成及利用

分級緩沖讀取地震道整體流程如圖5所示。首先從地震道緩存中獲取數(shù)據(jù)，如果有則返回，并將緩存命中數(shù)加1；如果沒有，則繼續(xù)從子塊緩存中獲取數(shù)據(jù)。如果子塊緩存中有數(shù)據(jù)，則將獲取到的數(shù)據(jù)填到地震道相應的位置上，并將子塊緩存命中數(shù)加1，同時將獲取的地震道作為緩存存放下來。如果子塊緩存中沒有數(shù)據(jù)，則從子塊文件中提取數(shù)據(jù)，填到地震道相應的位置上，并生成地震道緩存和子塊緩存。當緩存數(shù)量達到設定的限制時，刪除使用數(shù)量最少的地震道緩存和使用較早的子塊緩存。

用戶對于地震數(shù)據(jù)的查詢請求有多種形式，最終都轉(zhuǎn)換成主測線號、聯(lián)絡線號、時間范圍三個參數(shù)來獲取地震數(shù)據(jù)的，一級緩存采用的是普通LRU（LeastRecently Uesd，最少使用次數(shù)）策略，以地震道為單元的一級內(nèi)存緩沖，緩存的是不同時窗范圍、多次讀取子塊地震道數(shù)據(jù)合并后的地震道數(shù)據(jù)。一次具體的生成和利用如圖6中左半部分所示。

1） 對于輸入的主測線號、聯(lián)絡線號、時間范圍，在地震道緩存中尋找相同主測線號、聯(lián)絡線號的緩存。如果沒有找到，則尋找二級緩存；如果找到，則判斷緩存的時間范圍是否能覆蓋輸入的時間范圍。

2） 當緩存時間范圍不能覆蓋用戶查詢請求時，缺少的范圍從二級緩存中繼續(xù)查找，最后將得到的數(shù)據(jù)與當前緩存中的地震道拼接；如果緩存時間范圍可以覆蓋用戶查詢請求，則直接使用此緩存地震道并增加緩存命中次數(shù)。

3） 將得到的地震道緩存按照用戶查詢請求的時間范圍進行截斷，生成地震數(shù)據(jù)并返回。

4） 當緩存道數(shù)量達到用戶設定的數(shù)量限制時，根據(jù)各個緩存道命中次數(shù)的多少，刪除命中較少的緩存道。剩余所有緩存道的命中次數(shù)統(tǒng)一減去一個數(shù)值，數(shù)值大小為所刪除的所有緩存道中命中次數(shù)最多的值。

5 二級緩存的生成及利用

一級內(nèi)存緩沖未能覆蓋被請求的地震道數(shù)據(jù)時，根據(jù)主測線、聯(lián)絡線及時窗范圍，轉(zhuǎn)換為八叉樹的莫頓碼及對應的子塊文件存儲位置，詢問以八叉樹子塊為存儲單元的二級緩存。具體的流程如圖6右半部分所示。

1） 如果在二級緩存中找到相同子塊編號的子塊，則增加子塊緩存命中次數(shù)，并將此子塊緩存移動到鏈表中具有同樣命中次數(shù)的所有子塊緩存的最前端；如果沒有找到，則從文件中讀取子塊數(shù)據(jù)，并建立對應的子塊緩存。子塊緩存的建立方法為：莫頓碼和塊編碼填入對應的碼；中心坐標通過八叉樹計算出空間范圍，然后求取中心點；地震數(shù)據(jù)為子塊中的數(shù)據(jù)順序存儲；地震數(shù)據(jù)大小為子塊數(shù)據(jù)大?。幻写螖?shù)為1；塊大小為子塊空間范圍大?。磺耙粋€塊為空，后一個塊為當前鏈表中第一個塊；將建立完成的子塊緩存放到命中次數(shù)為1的所有子塊緩存的最前端。

2） 如果之前找到一級地震道緩存，則將子塊數(shù)據(jù)拼接到地震道緩存中；如果沒有找到則新建一個地震道緩存，時間范圍為用戶查詢請求的范圍，將子塊數(shù)據(jù)填充到地震道緩存中。子塊數(shù)據(jù)拼接和填充的具體方法為：根據(jù)子塊數(shù)據(jù)所代表的時間范圍，與地震道緩存的時間范圍比較，得到子塊數(shù)據(jù)相對地震道緩存數(shù)據(jù)的具體位置，并替換已有位置上的數(shù)據(jù)或者填充到已有位置。對于疊前地震數(shù)據(jù)體，地震道緩存和子塊緩存都是深度上一整條地震數(shù)據(jù)存儲完再存儲下一條，在拼接或填充時需要一條一條拼接或填充。如圖7所示，在地震道緩存深度范圍內(nèi)的數(shù)據(jù)，采用填充或替換方法；在地震道緩存深度范圍外的數(shù)據(jù)，采用拼接的方法。

3） 當子塊緩存達到用戶設定的數(shù)量限制時，刪去鏈表末尾的一批子塊緩存，即較早且使用次數(shù)較少的子塊緩存，刪除的數(shù)量為末尾一批具有相同命中次數(shù)的緩存。同時，其他所有子塊緩存的命中次數(shù)統(tǒng)一減去此批刪去子塊緩存的命中次數(shù)。

4） 將得到的地震道緩存按照用戶查詢請求的時間范圍進行截斷，生成地震數(shù)據(jù)并返回。

6 結論

本文設計了一種基于八叉樹的地震數(shù)據(jù)多級緩存方法。利用三維空間下八叉樹結構與編碼的快速空間定位機制，實現(xiàn)對三維大數(shù)據(jù)體的結構分塊存儲。同時設計了二級緩存結構，提升了數(shù)據(jù)訪問效率。實現(xiàn)了基于地震道的緩存和基于子塊的緩存，分別提升了查詢請求響應速度和子塊讀取響應速度。還實現(xiàn)了緩存訪問頻次記錄及雙向鏈表結構，避免數(shù)據(jù)塊在內(nèi)存中的頻繁遷移，并且可以優(yōu)先剔除利用次數(shù)少的緩存對象。