基于K-距離拓撲的分布式數據存儲方法*

郎登何

(1. 重慶大學 大數據與軟件學院，重慶 401331；2. 重慶電子工程職業學院 人工智能與大數據學院，重慶 401331)

隨著移動互聯網技術和信息技術的快速發展，越來越多的終端設備和傳感器被接入互聯網，產生了海量數據，令傳統的數據存儲方式逐漸被云存儲和分布式存儲所取代[1-2].

分布式數據存儲采用廣泛分布在不同地理區域并相互連接的成本低廉、數量眾多的PC服務器來存儲海量數據[3]，這種存儲方式能大幅節省存儲成本，但節點的可用性較低.同時，數據存儲規模的不斷擴大也大幅增加了系統發生故障的概率.而云存儲技術可在云計算的基礎上，通過應用軟件和分布式文件系統、集群技術和網絡技術，將不同設備和不同類型的數據相結合協同工作[4-5]，但不同位置的存儲節點有著不同的存儲能力和鏈路帶寬，使得難以提高數據存取速度[6-8].

云存儲概念提出的同時，云計算的安全性也受到廣泛關注[9].如Google Cloud Platform和Amazon S3為用戶提供了不同安全等級的加密服務，然而云存儲通常需要加密龐大的數據，這將消耗大量的計算資源，且這種數據加密方式需要用戶自己保管秘鑰，也會導致服務質量的降低和存取時間的增加.

目前，國內外學者和專家提出了諸多方法來解決這些問題，如采用圖分割的方式從數學理論的角度考慮分布式數據存儲的拓撲結構，但該種方法并未綜合考慮鏈路和節點的性能[10]；也有文獻提出使用智能優化算法來選擇存儲節點，以降低帶寬消耗并節省數據存取時間，但這種方法存在局部最優的問題且具有較高的復雜度，不適合作為數據放置策略[11].

本文綜合考慮分布式數據存儲的安全性和高效性，提出了一種基于K-距離拓撲的低復雜度數據放置算法.該算法通過尋找K-距離拓撲子圖來實現數據的安全放置，在此基礎上，采用最小化存取時間的方式合理地放置數據.

1 系統模型

本文使用網絡拓撲圖模型G(V，E)來表示分布式存儲系統，其中，V和E分別為存儲節點集合和鏈路集合.第i個節點的存儲能力由SCi表示，鏈路的帶寬矩陣由B表示，且對于任意的bij∈B，則有

(1)

模型中用戶可以任意選擇數據存儲的節點來提交數據.本文將存儲數據D進行分塊，并用SDi表示節點i處存儲的數據塊，則有

(2)

本文從以下兩方面保證數據的安全性：

1) 根據數據存放的距離來表示數據安全級別的高低，距離更大的數據塊間具有更高的安全性；

2) 不同領域的數據具有不同的安全性.

為了實現上述安全性要求，本文提出了一種安全距離的定義：使用K表示安全距離，K=0表示數據沒有安全性需求；K=1表示任意兩個數據塊間的距離必須大于1；K=2表示任意兩個數據塊間的距離必須大于2.定義fs表示計算數據間的安全距離，即

fs=minfk(SDi，SDj) (i≠j，i，j=1，2，…，V)

(3)

(4)

式中，dis(i，j)為兩點之間歐式距離.

在確定數據存取的安全性條件后，對數據存取的時間進行建模，假設當前數據存儲策略SD的安全距離為K，數據從節點A接入，則對任意存儲節點SDi≠0，i=1，2，…，V，各節點的數據存取時間為

(5)

式中：Pi，A為節點i和節點A間的最短路徑；tls，ld為鏈路l數據存取時間；ls，ld為兩鏈路的起點和終點.存取所有數據塊D所需的時間為

(6)

基于上述對數據安全和數據存取速率的分析，本文將分布式數據存取問題表示為：在接入點A處將給定大小的數據D進行合理分配，則在滿足距離大于K且所需存取時間最小條件時，可將該問題表示為

(7)

2 數據存儲算法

2.1 數據存取模型定義

本文使用K-距離拓撲子圖來表示數據存儲節點，以保證數據塊的放置能滿足安全距離的要求.

K-距離拓撲子圖的定義為：假設G(V，E)為無向連通圖，如果其節點集合V′?V滿足

dis(v1，v2)≥K(?v1，v2∈V′，v1≠v2)

(8)

則稱該子圖為K-距離拓撲子圖.

基于上述定義可以得到K-距離拓撲子圖的生成算法如下：

1) 假設需要得到的圖模型為G(V，E)，安全距離為K；

2) 隨機選擇一個節點v；

3) 將節點v與所有到節點v的距離小于K的節點相連；

4) 執行循環比較，循環停止后得到的結果即為生成的K-距離拓撲子圖.

根據該算法描述可知，對于給定的圖模型G(V，E)，存在多個K-距離拓撲子圖.圖1為一個包含10個頂點的拓撲圖，圖2、3為選擇不同的初始和中間節點得到的兩種不同拓撲子圖.其中，圖2為包含節點2，4，7，9的2-距離拓撲子圖，即K=2；圖3為包含節點1，3，5，6，8，10的2-距離拓撲子圖.從圖2和圖3可以看出初始節點和中間節點的選擇對于構造拓撲子圖異常重要.

圖1 10頂點網絡拓撲圖Fig.1 Network topology with 10 vertexes

圖2 2-距離拓撲子圖1Fig.2 Sub-graph 1 of 2-distance topology

圖3 2-距離拓撲子圖2Fig.3 Sub-graph 2 of 2-distance topology

2.2 節點選擇算法

基于上文定義的K-距離拓撲子圖，本文將存儲節點選擇過程轉化為在給定安全距離K的條件下，尋找使數據存取時間最小的K-距離拓撲子集問題.本文提出一種基于節點優先級選擇的算法來求解該問題，即根據各節點的數據存取速度優先選擇存取速度更快的節點和自身保護能力強的節點.

單位數據存取速度定義為

(9)

式中：Pv，A為節點v和A間的最短距離；D為數據總量.

數據存儲節點選擇算法具體流程如下：

1) 對每一個節點，根據式(9)計算Uv.

2) 對所有Uv按照從大到小的順序排序，得到排序后的集合PV.

3) 計算節點A與集合PV中每一個節點間的最短距離d.

4) 當d≥K時，將該點放入最優數據存儲集合；當d

本文存儲節點選擇算法主要分為兩部分：1)按照單位存取時間排列數據存儲節點；2)使用最短距離算法選擇最優的數據存儲序列.其中，第1部分的時間復雜度為O(V)；第2部分的時間復雜度為O(VO(E+VlgV))或O(VO(kE))，其中，E為圖G的邊數量，k為SPFA算法中節點進入Queue的次數.因此，本文存儲節點選擇算法的時間復雜度包括兩種情況：最優情況下為O(kVE)，最壞情況下為O(VE+V2lgV).

3 仿真分析

本文使用Matlab和Omnet++仿真平臺驗證所提出的基于K-距離拓撲的高效、安全的分布式數據存儲算法的有效性，并使用Internet 2拓撲圖與隨機拓撲圖衡量該算法在不同應用場景下的性能.兩種網絡的具體仿真環境參數如表1所示.

表1 仿真參數設置Tab.1 Settings of simulation parameters

圖4為本文使用的Internet 2拓撲圖.該拓撲圖由帶寬為1 Gbit·s-1的節點組成，每個節點表示一個美國的城市.

本文通過與FNF算法、GA算法和kDDS算法進行比較來驗證所提出算法的有效性.其中，FNF算法直接根據節點間的距離來選擇存儲節點以提高數據的安全性；GA算法則使用遺傳算法來選擇最優的存儲節點來減少數據的存取時間，這種方法計算量較大；kDDS算法采用圖分割理論來減少帶寬和數據存取時延.

圖4 Internet 2拓撲圖Fig.4 Internet 2 topology graph

本文首先比較了不同數據量和網絡節點情況下，各種算法在隨機拓撲網絡中的數據存取時間結果如圖5、6所示.從圖5中可以看出，相比于其他算法，本文算法所需的數據存取時間最小，且隨著數據的增加，本文算法所需的存取時間增加量最小、最緩慢.這是因為所提出的算法能通過選擇鏈路狀況最優的節點來減小數據的存取時間.從圖6可以看出，即使網絡節點數量不斷提高，所提出算法的數據存取時間仍穩定且較小.相對于其他算法，本文算法能減少60%～70%的存取時間.在隨機拓撲網絡中的測試結果表明，所提出的算法在滿足安全距離的情況下，能通過選擇性能最優的節點來存儲數據，以減小數據的存取時間.

圖5 隨機拓撲下不同數據量的數據存取時間Fig.5 Data access time of different data volumes under random topology

圖6 隨機拓撲下不同網絡規模的數據存取時間Fig.6 Data access time of different network sizes under random topology

圖7、8為在不同數據量與網絡節點情況下，各種算法在Internet 2拓撲圖中的數據存取時間.

圖7 Internet 2拓撲圖下不同數據量的數據存取時間Fig.7 Data access time of different data volumes under Internet 2 topology

圖8 Internet 2拓撲圖下不同網絡規模的數據存取時間Fig.8 Data access time of different network sizes under Internet 2 topology

從圖7、8中可以看出，隨著Internet 2拓撲圖中數據量的不斷增加，所有算法的數據存取時間均在增長.而本文算法的增長速度最慢，且相較于其他算法需要更少的存取時間，且隨著Internet 2拓撲圖數據規模的不斷增加，本文算法所需的數據存取時間也是最低的.

從仿真結果可以看出，在Internet 2拓撲圖和隨機拓撲圖情況下，本文算法均具有最低的數據存取時間.這是因為相較于其他算法，本文算法能在滿足安全距離約束的條件下選擇到最優的數據存儲節點并使用最少的數據存取時間.

4 結 論

本文提出了一種基于K-距離拓撲的分布式數據存儲方法.該算法使用K-距離拓撲子圖來表示數據存儲節點，來保證數據塊的放置能滿足安全距離的要求.同時提出了一種基于節點優先級選擇的算法，將存儲節點選擇過程轉化為在給定安全距離K條件下的拓撲選擇過程.使用Matlab和Omnet++仿真平臺在Internet 2拓撲圖與隨機拓撲圖下的仿真測試結果表明，所提出的算法能在滿足安全距離約束的條件下選擇到最優的數據存儲節點，從而減小數據存取時間.