基于八叉樹的地震數(shù)據(jù)分布式存儲與計算

彭 成

（中國石油化工股份有限公司 石油勘探開發(fā)研究院，北京 100083）

0 引言

隨著地震采集及電子掃描技術(shù)的發(fā)展，產(chǎn)生了海量的地震數(shù)據(jù)。地震數(shù)據(jù)的特點是單一文件數(shù)據(jù)量大，經(jīng)常達(dá)到TB級別，因此需要采用合適的存儲技術(shù)來提升訪問效率。常用的技術(shù)、如分布式存儲減少了本地的空間占用，通過將地震數(shù)據(jù)分塊，一方面對局部區(qū)域的獲取提升了效率，另一方面分塊小數(shù)據(jù)更加靈活，可以在不同存儲節(jié)點間進(jìn)行遷移和備份等，相比于單一文件存儲更加可靠。

在地震數(shù)據(jù)的獲取和使用上，由于地震數(shù)據(jù)的文件數(shù)據(jù)量大，緩沖技術(shù)的使用必不可少。地震數(shù)據(jù)常用的訪問方式為按照線道方式的剖面獲取，遍歷整體地震數(shù)據(jù)體的屬性計算和反演計算，以及任意方向三維切片顯示等。對于不同的數(shù)據(jù)獲取需求，最適合的緩沖策略也不同，如何設(shè)計較為均衡的緩沖策略以支持多種不同的使用場景，是提升地震數(shù)據(jù)存取效率亟需解決的研究問題。

在高效的分布式存儲和緩沖策略前提下，需要將其真正應(yīng)用到地震反演等處理中，就還要配套的分布式計算框架。目前主流的分布式并行處理框架包括谷歌分布式文件系統(tǒng)等，是比較易于擴(kuò)展、并能應(yīng)用到不同領(lǐng)域中的架構(gòu)?；诂F(xiàn)有的并行編程模型，開發(fā)出適合地震數(shù)據(jù)文件特點以及符合地震計算流程需求的計算框架，才能充分利用分布式子塊形式存儲的地震數(shù)據(jù)。不同編程模型的取舍及實現(xiàn)的復(fù)雜度主要體現(xiàn)在—合適的并行粒度需要根據(jù)計算量、通信量、計算速度、通信速度進(jìn)行綜合平衡，同時設(shè)法加大計算時間相對于通信時間的比重，減少通信次數(shù)、甚至以計算換通信等。不管選用何種并行編程模型，均會涉及到任務(wù)劃分、通信分析、任務(wù)組合及處理器映射等關(guān)鍵環(huán)節(jié)。

本文在參考谷歌文件系統(tǒng)基礎(chǔ)上，利用三維空間下八叉樹結(jié)構(gòu)與編碼的快速空間定位機(jī)制，實現(xiàn)對三維大數(shù)據(jù)體的結(jié)構(gòu)分塊存儲，同時設(shè)計了基于地震道的一級緩存和基于子塊的二級緩存結(jié)構(gòu)，提升了數(shù)據(jù)訪問效率。進(jìn)一步，設(shè)計實現(xiàn)了地震屬性的分布式映射歸并計算方法，為大數(shù)據(jù)背景下三維數(shù)據(jù)體的高效存儲與處理分析提供了技術(shù)支持。

1 八叉樹編碼與分塊存儲

八叉樹結(jié)構(gòu)適用于對三維數(shù)據(jù)的分塊，廣泛應(yīng)用于三維圖像領(lǐng)域，即把三維數(shù)據(jù)立方體分割為8個子塊，每個子塊進(jìn)一步切分為8個，直至達(dá)到合適的粒度。通過讀取子塊代替讀取整個文件，可以提升圖像的查詢顯示效率。

1.1 地震分塊配置

對地震數(shù)據(jù)按照設(shè)定的分塊大小進(jìn)行八叉樹切分，子塊采用線性莫頓（Morton）編碼。莫頓碼按照大小排序得到子塊自然數(shù)編碼（Tile ID）。在利用八叉樹子塊來讀取地震數(shù)據(jù)時，通過輸入的主測線號，聯(lián)絡(luò)線號和深度范圍得到其在源地震數(shù)據(jù)立方體中相應(yīng)的空間范圍，進(jìn)而轉(zhuǎn)換成一組對應(yīng)的Morton編碼，再轉(zhuǎn)換為Tile ID，定位到在文件中的存儲位置。

地震子塊文件命名采用隨機(jī)64位哈希編碼（uuid），每個子塊文件命名為”XXX（uuid）.afs”。子塊有Morton、Tile ID、uuid三種碼，與子塊一一對應(yīng)，從莫頓碼和子塊大小可以推導(dǎo)出對應(yīng)的空間位置，從而實現(xiàn)編碼和位置信息的關(guān)聯(lián)。在分配存儲節(jié)點時確定一個子塊需要傳輸?shù)侥男┐鎯?jié)點中，采用的是一致性哈希算法。

分布式存儲的結(jié)構(gòu)包括本地（local）、存儲管理服務(wù)（master）、子塊存儲服務(wù)（chunk）三個類型的對象，其中l(wèi)ocal存放了待切分的源地震數(shù)據(jù)，master中存放切分和chunk節(jié)點的參數(shù)配置，chunk節(jié)點中存放子塊及地震測網(wǎng)信息。master及chunk節(jié)點基于遠(yuǎn)程調(diào)用框架（Remote Call Framework，RCF），運行數(shù)據(jù)存取服務(wù)程序。子塊平均分配傳輸?shù)礁鱾€chunk節(jié)點中，實現(xiàn)分布式存儲。

1.2 子塊切分與傳輸

為提升切分生成子塊的速度，減少讀寫文件對象切換及盡量順序讀寫文件，本文中子塊的傳輸通過中間文件進(jìn)行周轉(zhuǎn)。將源地震數(shù)據(jù)按照存儲節(jié)點中逐個節(jié)點切割一份中間文件。中間文件數(shù)據(jù)全部屬于對應(yīng)的存儲節(jié)點，存儲節(jié)點的數(shù)據(jù)也全部來自于此中間文件。此后將中間文件傳輸?shù)綄?yīng)的存儲節(jié)點中。如圖1左半側(cè)可以看到，本地工作包括源文件的順序讀取與中間文件的順序?qū)懭搿?/p>

圖1 地震數(shù)據(jù)切塊流程Fig.1 Seismic data segmentation process

每次讀取源數(shù)據(jù)若干個地震道，默認(rèn)讀取數(shù)據(jù)量為100 MB，并順序遍歷各個存儲節(jié)點，將這批地震道數(shù)據(jù)中屬于當(dāng)前存儲節(jié)點的數(shù)據(jù)寫入其對應(yīng)的中間文件。數(shù)據(jù)與存儲節(jié)點的對應(yīng)關(guān)系通過八叉樹的切分方法來計算得到。在存儲節(jié)點中，對接收到的中間文件，每次順序讀取100 MB左右的數(shù)據(jù)，將數(shù)據(jù)寫入到各個子塊中。如圖1右半部分所示，遍歷這100 MB左右的數(shù)據(jù)，每次讀取最小單元的子塊號和在子塊中的位置，再將最小單元數(shù)據(jù)寫入到對應(yīng)的子塊文件中。通過中間文件實現(xiàn)了源文件的順序讀、中間文件的順序?qū)?，且減少了寫對象切換的頻率。讀取地震數(shù)據(jù)與切分相反，也通過中間文件進(jìn)行，實現(xiàn)源文件的順序?qū)?、中間文件的順序讀。

2 多級緩存建立及利用

構(gòu)成地震數(shù)據(jù)文件的基本單元是地震道，一級緩存就是在內(nèi)存中存放一組地震道，每次查詢請求傳過來時，查找對應(yīng)的地震道。通過命中次數(shù)計數(shù)，優(yōu)先刪除使用次數(shù)少的結(jié)果。

二級緩存是對子塊的緩存，當(dāng)一級緩存無法命中，就會繼續(xù)從二級緩存去尋找。每個二級緩存相當(dāng)于將一個子塊文件加載到內(nèi)存中，數(shù)據(jù)結(jié)構(gòu)包括Morton碼、Tile ID、命中次數(shù)等。

2.1 一級緩存的生成及利用

以地震道為單元的一級內(nèi)存緩沖，緩存的是不同時窗范圍、多次讀取子塊地震道數(shù)據(jù)合并后的地震道數(shù)據(jù)。一次具體的生成和利用如圖2中左半部分所示：

圖2 分級緩存讀取地震道邏輯圖Fig.2 Hierarchical cache reading seismis channel logic diagram

（1）對于輸入的主測線號、聯(lián)絡(luò)線號、時間范圍，在地震道緩存中尋找相同主測線號、聯(lián)絡(luò)線號的緩存，如果找到，則判斷緩存的時間范圍是否能覆蓋輸入的時間范圍；如果無法命中，繼續(xù)查找二級緩存。

（2）當(dāng)緩存道時間起止范圍無法覆蓋查詢道的時間起止范圍時，缺少的部分從二級子塊緩存中查找，而后將得到的數(shù)據(jù)與當(dāng)前緩存中的地震道拼接；如果緩存時間范圍可以覆蓋用戶查詢請求，則直接使用此緩存地震道并增加緩存命中次數(shù)。

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

（4）當(dāng)緩存道數(shù)量超過上限時，根據(jù)各個緩存道命中次數(shù)的多少，刪除命中較少的緩存道，剩余所有緩存道的命中次數(shù)統(tǒng)一減去一個數(shù)值，數(shù)值大小為所刪除的所有緩存道中命中次數(shù)最多的值。

2.2 二級緩存的生成及利用

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

（1）如果找到二級緩存子塊，命中計數(shù)加一；如果沒有找到，則讀取分布式子塊數(shù)據(jù)并建立子塊緩存。

（2）如果前期找到一級地震道緩存，可將子塊數(shù)據(jù)拼接到地震道緩存中，如果沒有找到則新建一個地震道緩存，時間范圍為用戶查詢請求的范圍，將子塊數(shù)據(jù)填充到地震道緩存中。子塊數(shù)據(jù)拼接和填充的流程方法為：根據(jù)子塊數(shù)據(jù)所代表的時間范圍，與地震道緩存的時間范圍比較得到子塊數(shù)據(jù)相對地震道緩存數(shù)據(jù)的具體位置，并替換已有位置上的數(shù)據(jù)或者填充到已有位置。子塊緩存拼接、填充或替換地震道緩存如圖3所示。由圖3可知，對于緩存地震道時間起止范圍內(nèi)的情況，采用填充或者替換的方法；對于時間起止范圍外的數(shù)據(jù)，采用拼接的方法。

圖3 子塊緩存拼接、填充或替換地震道緩存Fig.3 Subblock cache splicing，filling，or replacing the seismic channel cache

（3）當(dāng)子塊緩存數(shù)量超過上限時，刪去較早且使用次數(shù)較少的子塊緩存，同時其他所有子塊緩存的命中次數(shù)統(tǒng)一減去此批刪去子塊緩存的命中次數(shù)。

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

3 分布式映射歸并計算

對批處理編程模型而言，任務(wù)劃分與高效執(zhí)行是建立在合理的數(shù)據(jù)粒度切分基礎(chǔ)上。本文中的Map-Reduce是面向地震數(shù)據(jù)分析的服務(wù)，可執(zhí)行常見的切片、地震屬性分析及反演等算法，每一個映射服務(wù)（）或歸并服務(wù)（）本身又是一個多線程執(zhí)行框架。

3.1 部署映射歸并服務(wù)

映射歸并服務(wù)的結(jié)構(gòu)包括任務(wù)管理服務(wù)（）、映 射 服 務(wù)（）、 歸 并 服 務(wù)（），配置包括和端口、工作目錄，服務(wù)之間的數(shù)據(jù)傳輸基于的開源代碼實現(xiàn)，實現(xiàn)心跳、消息傳遞、廣播、事件服務(wù)等多種異步調(diào)用機(jī)制調(diào)度宕機(jī)的任務(wù)服務(wù)及發(fā)現(xiàn)新加入的任務(wù)服務(wù)，并合理安排計算過程。

地震數(shù)據(jù)屬性計算模塊參數(shù)配置包括計算的測網(wǎng)及深度范圍，不同的地震屬性計算有各自特有的計算參數(shù)，輸出包括若干地震數(shù)據(jù)體或若干地震數(shù)據(jù)切片。在進(jìn)行映射歸并計算時，運行流程如圖4所示。由圖4可知，首先將用戶配置好的屬性計算參數(shù)傳給、，并從分布式文件數(shù)據(jù)塊按照約定的計算數(shù)據(jù)體大小獲取所有計算單元（），通過遍歷分布式地震數(shù)據(jù)子塊（），提取數(shù)據(jù)。然后遍歷每個子塊中的數(shù)據(jù)，以鍵值對（）為單位進(jìn)行計算。鍵值對是地震數(shù)據(jù)與對應(yīng)空間范圍對應(yīng)關(guān)系的結(jié)構(gòu)數(shù)據(jù)，對其進(jìn)行屬性計算后將結(jié)果寫入、并傳給。

圖4 Map-Reduce計算框架時序圖Fig.4 Map-Reduce computing framework sequence diagram

所有算得中間分析結(jié)果后，通知進(jìn)行歸并，遵循鍵值對提取同一類別中間計算結(jié)果（），遍歷并根據(jù)約定的算法歸并最終數(shù)據(jù)塊文件（），形成及建立分布式結(jié)果存儲文件結(jié)果（），得到最終的計算結(jié)果，再上傳到節(jié)點中，完成分布式計算。所有和內(nèi)部計算基于多線程執(zhí)行。

Map-Reduce計算的關(guān)鍵步驟如圖5所示。由圖5可知，從不同的獲取待處理的粗粒度數(shù)據(jù)文件并讀取鍵值對，執(zhí)行匹配的地震屬性計算函數(shù)，中間產(chǎn)生的結(jié)果存儲到圓形內(nèi)存緩沖區(qū)（先進(jìn)先出類型），達(dá)到閾值后寫入本地硬盤、且初步歸并（）形成面向不同的子塊文件。通知所屬的子塊文件都在哪些里并進(jìn)行下載。獲取到所有中間鍵值對后，就按照鍵值對的鍵進(jìn)行歸并排序形成中間臨時文件。對于相同鍵的一批鍵值對，將其數(shù)據(jù)全部傳給Reduce算法函數(shù)執(zhí)行，將結(jié)果寫入最終的輸出文件。

圖5 Map-Reduce關(guān)鍵環(huán)節(jié)示意圖Fig.5 Map-Reduce key link diagram

3.2 分布式映射計算

分布式計算流程如圖6所示。由圖6可知，首先通過獲取到和的地址并初始化與其連接的接口服務(wù)，接下來會為其分配各自負(fù)責(zé)的子塊文件。和分配時，在平均分配子塊的基礎(chǔ)上，另需考慮避免超過剩余存儲空間。各個和所負(fù)責(zé)的子塊配置好后，本地將給其傳送地震屬性計算參數(shù)，開始進(jìn)行計算，計算完成后再將計算結(jié)果發(fā)送過去。歸并生成最終計算結(jié)果，此后傳回本地及節(jié)點，實現(xiàn)結(jié)果的分布式存儲。

圖6 Map-Reduce計算流程Fig.6 Map-Reduce calculation process

Map的具體流程如圖7所示，主要分為以下幾個步驟：

圖7 Map計算流程Fig.7 Map calculation process

（1）首先從節(jié)點下載源地震數(shù)據(jù)的索引文件獲取測網(wǎng)參數(shù)，然后結(jié)合傳送的地震屬性計算參數(shù)，得到輸出的測網(wǎng)范圍，寫成一個參數(shù)文件發(fā)送到節(jié)點中，發(fā)送過去的路徑即用戶配置的分布式結(jié)果存放路徑。

（2）通過向?qū)?yīng)節(jié)點下載負(fù)責(zé)的子塊文件，同時生成子塊所屬的鍵值對。遍歷子塊鍵值對進(jìn)行屬性計算，將輸出寫回鍵值對。

（3）將鍵值對寫入輸出文件，當(dāng)一個子塊計算完畢后，提交當(dāng)前內(nèi)存中的所有鍵值對到對應(yīng)的結(jié)果文件中。

（4）發(fā) 送 結(jié) 果 文 件 到節(jié) 點，并 向獲取各個所負(fù)責(zé)的子塊編號，再將這個子塊傳到上層督管負(fù)責(zé)的中。

3.3 分布式歸并計算

Reduce的具體流程如圖8所示，主要包括以下幾個步驟：

圖8 Reduce計算流程Fig.8 Reduce calculation process

（1）初始化輸出文件，分為2部分。一部分為單一的一個文件“reduceresult.afs”，存儲所有計算結(jié)果；另一部分為按子塊結(jié)構(gòu)組織的一批文件，存放各個子塊的計算結(jié)果，而后會上傳到節(jié)點，實現(xiàn)結(jié)果的分布式存儲。

（2）遍歷由其負(fù)責(zé)的所有子塊，對每個子塊遍歷這些鍵值對，進(jìn)行Reduce計算，形成八叉樹子塊。對涉及到面元計算的，需要跨鍵值對周圍數(shù)據(jù)進(jìn)行共同處理得到計算結(jié)果。

（3）將鍵值對寫入輸出文件，當(dāng)一個子塊計算完畢后，提交當(dāng)前內(nèi)存中的所有鍵值對到相應(yīng)的結(jié)果文件中。

（4）將這些結(jié)果文件發(fā)送到節(jié)點中，并向查獲各個存儲的子塊編號，同時將子塊傳輸?shù)缴蠈佣焦茇?fù)責(zé)的中；本地下載“reduceresult.afs”讀取其中的鍵值對，按照鍵值對的位置信息寫入到新建的輸出數(shù)據(jù)體或切片中，完成分布式結(jié)果的下載。

4 結(jié)束語

本文實現(xiàn)了一種基于八叉樹的地震數(shù)據(jù)多級緩存方法，采用基于地震道的一級緩存和基于子塊的二級緩存，分別提升了查詢請求響應(yīng)速度和子塊讀取響應(yīng)速度。

采用緩存訪問頻次記錄，避免數(shù)據(jù)塊在內(nèi)存中的頻繁遷移，并且可以優(yōu)先剔除出利用次數(shù)少的緩存對象。

基于分布式八叉樹實現(xiàn)了地震數(shù)據(jù)分布式屬性計算及結(jié)果分布式存儲，減少單機(jī)計算工作量，提升了計算效率。