基于八叉樹(shù)的地震數(shù)據(jù)多級(jí)緩存方法

曹晉 彭成

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

0 引言

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

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

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

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

1 八叉樹(shù)編碼與分塊存儲(chǔ)

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

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

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

2 基于地震道的一級(jí)緩存結(jié)構(gòu)

構(gòu)成地震數(shù)據(jù)文件的基本單元是地震道，相當(dāng)于地震數(shù)據(jù)立方體高方向上的一整條。地震道包括道頭和具體的地震數(shù)據(jù)，道頭中含有地震道的主測(cè)線號(hào)、聯(lián)絡(luò)線號(hào)、起止時(shí)間、地震數(shù)據(jù)點(diǎn)個(gè)數(shù)等信息。對(duì)于地震數(shù)據(jù)的查詢請(qǐng)求通常是給定主測(cè)線號(hào)、聯(lián)絡(luò)線號(hào)、起止時(shí)間、返回對(duì)應(yīng)位置范圍的地震數(shù)據(jù)。

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

3 基于八叉樹(shù)子塊的二級(jí)緩存結(jié)構(gòu)

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

4 一級(jí)緩存的生成及利用

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

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

1） 對(duì)于輸入的主測(cè)線號(hào)、聯(lián)絡(luò)線號(hào)、時(shí)間范圍，在地震道緩存中尋找相同主測(cè)線號(hào)、聯(lián)絡(luò)線號(hào)的緩存。如果沒(méi)有找到，則尋找二級(jí)緩存；如果找到，則判斷緩存的時(shí)間范圍是否能覆蓋輸入的時(shí)間范圍。

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

3） 將得到的地震道緩存按照用戶查詢請(qǐng)求的時(shí)間范圍進(jìn)行截?cái)?，生成地震?shù)據(jù)并返回。

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

5 二級(jí)緩存的生成及利用

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

1） 如果在二級(jí)緩存中找到相同子塊編號(hào)的子塊，則增加子塊緩存命中次數(shù)，并將此子塊緩存移動(dòng)到鏈表中具有同樣命中次數(shù)的所有子塊緩存的最前端；如果沒(méi)有找到，則從文件中讀取子塊數(shù)據(jù)，并建立對(duì)應(yīng)的子塊緩存。子塊緩存的建立方法為：莫頓碼和塊編碼填入對(duì)應(yīng)的碼；中心坐標(biāo)通過(guò)八叉樹(shù)計(jì)算出空間范圍，然后求取中心點(diǎn)；地震數(shù)據(jù)為子塊中的數(shù)據(jù)順序存儲(chǔ)；地震數(shù)據(jù)大小為子塊數(shù)據(jù)大??；命中次數(shù)為1；塊大小為子塊空間范圍大小；前一個(gè)塊為空，后一個(gè)塊為當(dāng)前鏈表中第一個(gè)塊；將建立完成的子塊緩存放到命中次數(shù)為1的所有子塊緩存的最前端。

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

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

4） 將得到的地震道緩存按照用戶查詢請(qǐng)求的時(shí)間范圍進(jìn)行截?cái)?，生成地震?shù)據(jù)并返回。

6 結(jié)論

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