基于八叉樹的地震數據分布式存儲與計算

彭 成

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

0 引言

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

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

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

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

1 八叉樹編碼與分塊存儲

八叉樹結構適用于對三維數據的分塊，廣泛應用于三維圖像領域，即把三維數據立方體分割為8個子塊，每個子塊進一步切分為8個，直至達到合適的粒度。通過讀取子塊代替讀取整個文件，可以提升圖像的查詢顯示效率。

1.1 地震分塊配置

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

地震子塊文件命名采用隨機64位哈希編碼（uuid），每個子塊文件命名為”XXX（uuid）.afs”。子塊有Morton、Tile ID、uuid三種碼，與子塊一一對應，從莫頓碼和子塊大小可以推導出對應的空間位置，從而實現編碼和位置信息的關聯。在分配存儲節點時確定一個子塊需要傳輸到哪些存儲節點中，采用的是一致性哈希算法。

分布式存儲的結構包括本地（local）、存儲管理服務（master）、子塊存儲服務（chunk）三個類型的對象，其中local存放了待切分的源地震數據，master中存放切分和chunk節點的參數配置，chunk節點中存放子塊及地震測網信息。master及chunk節點基于遠程調用框架（Remote Call Framework，RCF），運行數據存取服務程序。子塊平均分配傳輸到各個chunk節點中，實現分布式存儲。

1.2 子塊切分與傳輸

為提升切分生成子塊的速度，減少讀寫文件對象切換及盡量順序讀寫文件，本文中子塊的傳輸通過中間文件進行周轉。將源地震數據按照存儲節點中逐個節點切割一份中間文件。中間文件數據全部屬于對應的存儲節點，存儲節點的數據也全部來自于此中間文件。此后將中間文件傳輸到對應的存儲節點中。如圖1左半側可以看到，本地工作包括源文件的順序讀取與中間文件的順序寫入。

圖1 地震數據切塊流程Fig.1 Seismic data segmentation process

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

2 多級緩存建立及利用

構成地震數據文件的基本單元是地震道，一級緩存就是在內存中存放一組地震道，每次查詢請求傳過來時，查找對應的地震道。通過命中次數計數，優先刪除使用次數少的結果。

二級緩存是對子塊的緩存，當一級緩存無法命中，就會繼續從二級緩存去尋找。每個二級緩存相當于將一個子塊文件加載到內存中，數據結構包括Morton碼、Tile ID、命中次數等。

2.1 一級緩存的生成及利用

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

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

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

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

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

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

2.2 二級緩存的生成及利用

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

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

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

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

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

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

3 分布式映射歸并計算

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

3.1 部署映射歸并服務

映射歸并服務的結構包括任務管理服務（）、映 射 服 務（）、 歸 并 服 務（），配置包括和端口、工作目錄，服務之間的數據傳輸基于的開源代碼實現，實現心跳、消息傳遞、廣播、事件服務等多種異步調用機制調度宕機的任務服務及發現新加入的任務服務，并合理安排計算過程。

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

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

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

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

圖5 Map-Reduce關鍵環節示意圖Fig.5 Map-Reduce key link diagram

3.2 分布式映射計算

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

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

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

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

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

（2）通過向對應節點下載負責的子塊文件，同時生成子塊所屬的鍵值對。遍歷子塊鍵值對進行屬性計算，將輸出寫回鍵值對。

（3）將鍵值對寫入輸出文件，當一個子塊計算完畢后，提交當前內存中的所有鍵值對到對應的結果文件中。

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

3.3 分布式歸并計算

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

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

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

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

（3）將鍵值對寫入輸出文件，當一個子塊計算完畢后，提交當前內存中的所有鍵值對到相應的結果文件中。

（4）將這些結果文件發送到節點中，并向查獲各個存儲的子塊編號，同時將子塊傳輸到上層督管負責的中；本地下載“reduceresult.afs”讀取其中的鍵值對，按照鍵值對的位置信息寫入到新建的輸出數據體或切片中，完成分布式結果的下載。

4 結束語

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

采用緩存訪問頻次記錄，避免數據塊在內存中的頻繁遷移，并且可以優先剔除出利用次數少的緩存對象。

基于分布式八叉樹實現了地震數據分布式屬性計算及結果分布式存儲，減少單機計算工作量，提升了計算效率。