關系化數據分塊存儲系統局部性時延優化算法

楊中杰，王立中

(內蒙古農業大學計算機技術與信息管理系，內蒙古 包頭 014109)

1 引言

存儲系統作為計算機應用領域的重要組成部分，不僅與數據采集、預處理、處理、傳輸、轉換等環節密切相關，而且系統的處理過程也比較復雜，因此在協同操作過程中可能會發生數據交叉操作。如何在保證系統穩定運行的同時，從根本上解決存儲系統的實時性問題，同時增加數據量和用戶，時延優化逐漸成為計算機領域的研究熱點之一[1]。

趙晶等[2]提出了無線傳感器網絡多路徑傳輸時延優化調度算法研究，基于傳感器網絡的多路徑傳輸形式，探索復制機制與重傳機制兩種路由容錯機制，并由此構建出兩種多路徑傳輸資源優化調度策略，實現數據成功傳輸的同時降低傳輸時延；林兵等[3]根據混合云環境的數據布局特征與科學工作流數據之間的依賴關系，制定一種混合云環境下面向時延優化的科學工作流數據布局策略，通過分析傳輸時延的影響因素，引入遺傳算法的變異算子與交叉算子，設計出自適應離散粒子群算法，經壓縮數據傳輸時延完成優化處理。吳建明等[4]分析以單點數據采集為主的光伏發電遠程監測系統，基于物聯網技術，對傳感器的原始數據進行區分量化融合處理，實時準確地采集多通道數據，對數據采集輸出信道加以均衡控制，提高了診斷數據的準確檢測和分析能力。

對此，本文構建出一種關系化數據分塊存儲系統局部性時延優化算法，在理論創新方面，建立了關系數據塊存儲系統中關系數據的鄰接關系，縮小了搜索范圍，簡化了計算過程和局部延遲優化分析過程。

2 存儲系統關系化數據分塊方法

2.1 關系化數據分塊存儲系統結構

關系數據塊存儲系統使用兩個SCSI(Small Computer System Interface)通道來完成與下一層的兩個分支的連接。統一存儲空間主要由虛擬設備驅動程序組成。作為系統的中間節點，每個單元控制器都有三個通道，一個是上行通道，另兩個是下行通道。SCSI從驅動程序和SCSI主驅動程序分別驅動上、下通道。系統的葉節點主要由磁盤結構組成。為了充分發揮關系數據組織的結構優勢，最大限度地提高底層設備在數據傳輸中的并行性，并將其分塊存儲。如圖1所示，磁盤的編號順序是8個關系數據塊的存儲順序。通過分塊存儲，可以有效降低主機數據請求的影響，充分利用塊并行傳輸的容量。

圖1 關系化數據分塊存儲系統結構示意圖

2.2 關系化數據分塊流程

2.2.1 關系化數據預處理

為了使數據滿足存儲要求，預處理可分為三個階段：關系數據鄰接關系的建立、數據法向量的預測和數據曲率的求解。在構造關系數據的鄰接關系的過程中，通過尋找與當前關系數據距離最短的K個數據來構造K鄰域。當關系數據量較大時，建立鄰接關系可以有效地減少搜索面積，簡化計算過程，降低計算量和復雜度，提高關系數據塊的存儲效率。關系化數據鄰域求解的具體過程描述如下：

1)利用數據個數總和、最小包圍盒體積以及鄰近數據個數[5-6]，計算柵格邊長，把最小包圍盒分成規格完全一樣的柵格；

2)根據非空柵格個數、柵格邊長以及數據個數總和，求解關系化數據與數據中心之間的距離均值。

3)依據解得的柵格邊長，再次劃分最小包圍盒為規格一致的柵格；

4)遍歷所有數據之后，把數據與柵格進行一一對應地歸類；

5)基于柵格的位置坐標，K鄰域搜索[7]關系化數據的附近柵格，實現關系化數據鄰域結構構建。

數據法矢預估階段的目的是提升關系化數據分塊的便捷度，利用最小二乘法，構架下列數據法矢預估表達式

(1)

基于預估的數據法矢結果，進行數據曲率求解階段。假設數據曲面B=B(υ，?)，則該曲面的第一基本形式與第二基本形式可分別用下列各式描述

Ⅰ=Ευ2+2Fυ?+Γ?2

(2)

Ⅱ=Λυ2+2Μυ?+Ν?2

(3)

由上式推導得出數據曲率的計算公式，如下所示

(4)

2.2.2 關系化數據分塊存儲流程

假設W為預處理過的關系化數據集合，曲面集合B={b1，b2，…，bn}的組成部分是關系化數據集合W，曲面集合B的子集是H={h1，h2，…，hn}，其中，n表示構成的曲面個數，當關系化數據集合符合下列各式所示的約束條件時，關系化數據的正確數據分塊結果即為數據子集H

(5)

B(hi)=TRUE，ifandonlyΔ(γ(x′)，f(x′))≤ε

(6)

式中，第i個數據子集為hi，第j個數據子集為hj，當兩子集為相鄰子集時用Nbr(hi，hj)表示，尺度函數為Δ(γ(x′)，f(x′))，表示函數γ(x′)與f(x′)之間的差值，數據曲面hi與hj的重疊部分用B(hi∩hj)表示，標準差值是ε。

利用上述方法分塊存儲關系化數據，能夠為存儲系統的網絡安全提供更有力的支撐。

3 存儲系統局部性時延優化算法

假設關系化數據分塊存儲系統的網絡結構用T表示，網絡主節點是S，分塊中的任意節點為t，則采用下列表達式界定從主節點到分塊節點的局部性時延

(7)

式中，與分塊節點t共享公共鏈路的損耗為Rkt，網絡結構T中與節點t相鄰的節點是k，該節點的荷載為Ak。

由于無法提前預知主節點S到分塊節點t的實際路徑，計算量過于繁瑣，因此，導出局部性時延del(s，t)的上界Del(s，t)，簡化關系化數據分塊存儲系統中的局部性時延優化分析過程，故得出下列表達式：

del(s，t)≤Del(s，t)=(Rd+r1L(s，t))(Am+c1W)

(8)

式中，Rd、Am分別表示存儲系統損耗與荷載，r1和c1分別表示節點之間的傳輸鏈路損耗與荷載。

在一個二維曼哈頓平面上建立關系化數據分塊存儲網絡結構，整個網絡拓撲結構圖G=〈V，E〉的頂點集合屬于一個二維陣列，用V={v1，v2，…，vm}表示，相鄰頂點間的邊集合用E={e1，e2，…，em}表示。

如果存儲結構T≤V為一個信號網引線端集合，通過在圖G上求解時延優化的樹結構，完成算法構建，該樹連接結構T的全部頂點，且存在局部性時延del(s，t)的最小值。

時延優化算法的具體流程描述如下：

1)在圖G上架構一個可以連接存儲結構T中全部頂點的樹框架，根據局部性時延del(s，t)的上界Del(s，t)，極大程度最小化del(s，t)；

2)將結構T含有的全部頂點設定成優化算法的初始節點，當前節點設定為正在分塊的節點vj∈V，當算法開始運行時，當前節點變為vi∈T；

3)假設當前節點為vj∈V，該節點的坐標是(xj，yj)，則與節點vj對應的帶權重心Cj界定過程具體如下：

設定當前節點集合R≤V，有vi∈R且i≠j

dij=(xj-xi)2+(yj-yi)2

(9)

(10)

(11)

(12)

式中，vj中帶權重心Cj的水平與垂直坐標分別是xcj與ycj，權Dij的作用是令vj與vi節點帶權重心更接近，明確當前節點方向[8]。

在構建樹狀結構的過程中，對每個步驟中的每個當前節點進行處理，使節點在一個方向上增長一個線段，得到一個邊長e。一般來說，每個主節點S包括四個增長方向：上、下、左和右。如果節點沿著加權重心或主節點的生長方向生長，則可以減少局部延遲，因此，設置不同方向的不同權值。

4)假設當前節點vj的帶權重心是Cj，節點鄰接邊是e，那么對應于帶權重心Cj的權重表達式如下所示

wCj(e)=a1L(vj，Cj)

(13)

式中，L(vj，Cj)表示節點vj與帶權重心Cj間的最短距離，a1表示鄰接邊與帶權重心的方向關系，條件式如下所示

(14)

5)當主節點S是存儲結構中的關系化源點時，節點vj的鄰接邊是e，則對應于主節點S的權值表達式如下所示

ws(e)=a2L(vj，s)

(15)

式中，L(vj，s)表示節點vj與主節點S間的最短距離，a2表示鄰接邊e與主節點S的方向關系，條件式如下所示

(16)

帶權重心與主節點的權值界定形式如圖2所示，在圖中用點O表示。

圖2 帶權重心與主節點的權值界定示意圖

根據式(11)，將上述兩個方向同時作為時延最小化指標，采用合成方向界定相應權值wcd，使時延最小化

wcd(∈)=g1wCj(e)+g2ws(e)

(17)

式中，g1與g2為權重系數[9-10]，滿足下列等式

g1+g2=1

(18)

通過調節權重系數g1與g2，能夠改變帶權重心與主節點權值在合成方向權值中的貢獻，令時延優化更加合理、有效。

4 時延優化算法模擬分析

4.1 實驗環境

為提升實驗數據的可靠性與真實度，以Kaggle( https：//www.kaggle.com/datasets )中某遠程監測系的實際應用數據為數據來源。表1為算法實現與實驗相關軟硬件配置。

表1 開發平臺配置統計表

分別采用文獻[2]、[3]、[4]方法以及本文算法展開仿真，通過各算法的節點生命周期、系統生命周期、通信距離以及局部性時延等實驗數據，驗證本文算法的有效性與可行性。

4.2 算法仿真評估

圖3為各算法的節點生命周期實驗結果曲線。

圖3 節點生命周期誤差曲線圖

根據圖3中，三種算法節點生命周期樣本方差與存儲系統所含節點個數的關系變化曲線圖中，文獻[4]方法在四種算法中擁有最大的節點生命周期樣本方差，這說明該方法令系統中所有節點之間的能耗都呈不均衡狀態；而本文算法通過尋找到與當前關系化數據距離最短的K個數據，架構了數據間的鄰接關系，縮小了節點搜索區域，故節點生命周期樣本方差最小，具有較好的能量均衡性能。

圖4為各算法的系統生命周期實驗結果曲線。

圖4 系統生命周期曲線圖

通過整個系統生命周期與節點個數之間的關系變化曲線圖即圖4可以看出，文獻[2]方法的系統生命周期最長，而本文算法主要以時延作為研究側重點，故在節點個數為0-45時的系統生命周期較短，但在節點個數為50時，系統生命周期依舊產生上升趨勢。

以實驗主機為原點，進行通信距離測試，各算法的通信距離實驗結果如圖5所示。

圖5 通信距離曲線圖

由圖5可知，由于本文算法在優化時延過程中，考慮到了存儲系統與傳輸鏈路的損耗與荷載，因此，相較于文獻[2]、[3]、[4]方法，具有更理想的通信效果。

將存儲系統分為六個存儲階段，在局部性時延方面測試四種算法，仿真結果如圖6所示。

圖6 局部性時延曲線圖

圖6表示各算法在存儲過程里需要的時隙數與節點個數之間的關系變化曲線圖，從圖中曲線趨勢可知，文獻[2]、[3]、[4]方法的時延隨著節點個數的不斷變大而呈現出線性增長走勢，而本文算法通過建立最小化局部性時延的樹結構，達成了極大程度令時延最小化的目標，取得了較好的時延優化效果。

5 結論

1)在實驗條件允許的情況下，深入探討局部性時延優化方向，以局部性時延作為優化目標，對關系化數據的分塊存儲系統展開研究，在節點個數為50時，系統生命周期依舊產生上升趨勢，

2)將節點生命周期、系統生命周期、通信距離以及局部性時延作為優化切入點，改進存儲系統性能，實驗中的最大通信距離為69米。

3)個人實驗設備具有一定的局限性，勢必會影響到實驗效果，在今后的工作中，應繼續積極探索更好、更有效的方法，通過融合多種算法，架構更大型、更仿真的實驗環境來驗證算法性能，使優化效果進一步完善