基于K-距離拓?fù)涞姆植际綌?shù)據(jù)存儲(chǔ)方法*

郎登何

(1. 重慶大學(xué) 大數(shù)據(jù)與軟件學(xué)院，重慶 401331；2. 重慶電子工程職業(yè)學(xué)院 人工智能與大數(shù)據(jù)學(xué)院，重慶 401331)

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)和信息技術(shù)的快速發(fā)展，越來越多的終端設(shè)備和傳感器被接入互聯(lián)網(wǎng)，產(chǎn)生了海量數(shù)據(jù)，令傳統(tǒng)的數(shù)據(jù)存儲(chǔ)方式逐漸被云存儲(chǔ)和分布式存儲(chǔ)所取代[1-2].

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

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

目前，國(guó)內(nèi)外學(xué)者和專家提出了諸多方法來解決這些問題，如采用圖分割的方式從數(shù)學(xué)理論的角度考慮分布式數(shù)據(jù)存儲(chǔ)的拓?fù)浣Y(jié)構(gòu)，但該種方法并未綜合考慮鏈路和節(jié)點(diǎn)的性能[10]；也有文獻(xiàn)提出使用智能優(yōu)化算法來選擇存儲(chǔ)節(jié)點(diǎn)，以降低帶寬消耗并節(jié)省數(shù)據(jù)存取時(shí)間，但這種方法存在局部最優(yōu)的問題且具有較高的復(fù)雜度，不適合作為數(shù)據(jù)放置策略[11].

本文綜合考慮分布式數(shù)據(jù)存儲(chǔ)的安全性和高效性，提出了一種基于K-距離拓?fù)涞牡蛷?fù)雜度數(shù)據(jù)放置算法.該算法通過尋找K-距離拓?fù)渥訄D來實(shí)現(xiàn)數(shù)據(jù)的安全放置，在此基礎(chǔ)上，采用最小化存取時(shí)間的方式合理地放置數(shù)據(jù).

1 系統(tǒng)模型

本文使用網(wǎng)絡(luò)拓?fù)鋱D模型G(V，E)來表示分布式存儲(chǔ)系統(tǒng)，其中，V和E分別為存儲(chǔ)節(jié)點(diǎn)集合和鏈路集合.第i個(gè)節(jié)點(diǎn)的存儲(chǔ)能力由SCi表示，鏈路的帶寬矩陣由B表示，且對(duì)于任意的bij∈B，則有

(1)

模型中用戶可以任意選擇數(shù)據(jù)存儲(chǔ)的節(jié)點(diǎn)來提交數(shù)據(jù).本文將存儲(chǔ)數(shù)據(jù)D進(jìn)行分塊，并用SDi表示節(jié)點(diǎn)i處存儲(chǔ)的數(shù)據(jù)塊，則有

(2)

本文從以下兩方面保證數(shù)據(jù)的安全性：

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

2) 不同領(lǐng)域的數(shù)據(jù)具有不同的安全性.

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

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

(3)

(4)

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

在確定數(shù)據(jù)存取的安全性條件后，對(duì)數(shù)據(jù)存取的時(shí)間進(jìn)行建模，假設(shè)當(dāng)前數(shù)據(jù)存儲(chǔ)策略SD的安全距離為K，數(shù)據(jù)從節(jié)點(diǎn)A接入，則對(duì)任意存儲(chǔ)節(jié)點(diǎn)SDi≠0，i=1，2，…，V，各節(jié)點(diǎn)的數(shù)據(jù)存取時(shí)間為

(5)

式中：Pi，A為節(jié)點(diǎn)i和節(jié)點(diǎn)A間的最短路徑；tls，ld為鏈路l數(shù)據(jù)存取時(shí)間；ls，ld為兩鏈路的起點(diǎn)和終點(diǎn).存取所有數(shù)據(jù)塊D所需的時(shí)間為

(6)

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

(7)

2 數(shù)據(jù)存儲(chǔ)算法

2.1 數(shù)據(jù)存取模型定義

本文使用K-距離拓?fù)渥訄D來表示數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，以保證數(shù)據(jù)塊的放置能滿足安全距離的要求.

K-距離拓?fù)渥訄D的定義為：假設(shè)G(V，E)為無向連通圖，如果其節(jié)點(diǎn)集合V′?V滿足

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

(8)

則稱該子圖為K-距離拓?fù)渥訄D.

基于上述定義可以得到K-距離拓?fù)渥訄D的生成算法如下：

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

2) 隨機(jī)選擇一個(gè)節(jié)點(diǎn)v；

3) 將節(jié)點(diǎn)v與所有到節(jié)點(diǎn)v的距離小于K的節(jié)點(diǎn)相連；

4) 執(zhí)行循環(huán)比較，循環(huán)停止后得到的結(jié)果即為生成的K-距離拓?fù)渥訄D.

根據(jù)該算法描述可知，對(duì)于給定的圖模型G(V，E)，存在多個(gè)K-距離拓?fù)渥訄D.圖1為一個(gè)包含10個(gè)頂點(diǎn)的拓?fù)鋱D，圖2、3為選擇不同的初始和中間節(jié)點(diǎn)得到的兩種不同拓?fù)渥訄D.其中，圖2為包含節(jié)點(diǎn)2，4，7，9的2-距離拓?fù)渥訄D，即K=2；圖3為包含節(jié)點(diǎn)1，3，5，6，8，10的2-距離拓?fù)渥訄D.從圖2和圖3可以看出初始節(jié)點(diǎn)和中間節(jié)點(diǎn)的選擇對(duì)于構(gòu)造拓?fù)渥訄D異常重要.

圖1 10頂點(diǎn)網(wǎng)絡(luò)拓?fù)鋱DFig.1 Network topology with 10 vertexes

圖2 2-距離拓?fù)渥訄D1Fig.2 Sub-graph 1 of 2-distance topology

圖3 2-距離拓?fù)渥訄D2Fig.3 Sub-graph 2 of 2-distance topology

2.2 節(jié)點(diǎn)選擇算法

基于上文定義的K-距離拓?fù)渥訄D，本文將存儲(chǔ)節(jié)點(diǎn)選擇過程轉(zhuǎn)化為在給定安全距離K的條件下，尋找使數(shù)據(jù)存取時(shí)間最小的K-距離拓?fù)渥蛹瘑栴}.本文提出一種基于節(jié)點(diǎn)優(yōu)先級(jí)選擇的算法來求解該問題，即根據(jù)各節(jié)點(diǎn)的數(shù)據(jù)存取速度優(yōu)先選擇存取速度更快的節(jié)點(diǎn)和自身保護(hù)能力強(qiáng)的節(jié)點(diǎn).

單位數(shù)據(jù)存取速度定義為

(9)

式中：Pv，A為節(jié)點(diǎn)v和A間的最短距離；D為數(shù)據(jù)總量.

數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)選擇算法具體流程如下：

1) 對(duì)每一個(gè)節(jié)點(diǎn)，根據(jù)式(9)計(jì)算Uv.

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

3) 計(jì)算節(jié)點(diǎn)A與集合PV中每一個(gè)節(jié)點(diǎn)間的最短距離d.

4) 當(dāng)d≥K時(shí)，將該點(diǎn)放入最優(yōu)數(shù)據(jù)存儲(chǔ)集合；當(dāng)d

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

3 仿真分析

本文使用Matlab和Omnet++仿真平臺(tái)驗(yàn)證所提出的基于K-距離拓?fù)涞母咝?、安全的分布式?shù)據(jù)存儲(chǔ)算法的有效性，并使用Internet 2拓?fù)鋱D與隨機(jī)拓?fù)鋱D衡量該算法在不同應(yīng)用場(chǎng)景下的性能.兩種網(wǎng)絡(luò)的具體仿真環(huán)境參數(shù)如表1所示.

表1 仿真參數(shù)設(shè)置Tab.1 Settings of simulation parameters

圖4為本文使用的Internet 2拓?fù)鋱D.該拓?fù)鋱D由帶寬為1 Gbit·s-1的節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)表示一個(gè)美國(guó)的城市.

本文通過與FNF算法、GA算法和kDDS算法進(jìn)行比較來驗(yàn)證所提出算法的有效性.其中，F(xiàn)NF算法直接根據(jù)節(jié)點(diǎn)間的距離來選擇存儲(chǔ)節(jié)點(diǎn)以提高數(shù)據(jù)的安全性；GA算法則使用遺傳算法來選擇最優(yōu)的存儲(chǔ)節(jié)點(diǎn)來減少數(shù)據(jù)的存取時(shí)間，這種方法計(jì)算量較大；kDDS算法采用圖分割理論來減少帶寬和數(shù)據(jù)存取時(shí)延.

圖4 Internet 2拓?fù)鋱DFig.4 Internet 2 topology graph

本文首先比較了不同數(shù)據(jù)量和網(wǎng)絡(luò)節(jié)點(diǎn)情況下，各種算法在隨機(jī)拓?fù)渚W(wǎng)絡(luò)中的數(shù)據(jù)存取時(shí)間結(jié)果如圖5、6所示.從圖5中可以看出，相比于其他算法，本文算法所需的數(shù)據(jù)存取時(shí)間最小，且隨著數(shù)據(jù)的增加，本文算法所需的存取時(shí)間增加量最小、最緩慢.這是因?yàn)樗岢龅乃惴芡ㄟ^選擇鏈路狀況最優(yōu)的節(jié)點(diǎn)來減小數(shù)據(jù)的存取時(shí)間.從圖6可以看出，即使網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量不斷提高，所提出算法的數(shù)據(jù)存取時(shí)間仍穩(wěn)定且較小.相對(duì)于其他算法，本文算法能減少60%～70%的存取時(shí)間.在隨機(jī)拓?fù)渚W(wǎng)絡(luò)中的測(cè)試結(jié)果表明，所提出的算法在滿足安全距離的情況下，能通過選擇性能最優(yōu)的節(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)，以減小數(shù)據(jù)的存取時(shí)間.

圖5 隨機(jī)拓?fù)湎虏煌瑪?shù)據(jù)量的數(shù)據(jù)存取時(shí)間Fig.5 Data access time of different data volumes under random topology

圖6 隨機(jī)拓?fù)湎虏煌W(wǎng)絡(luò)規(guī)模的數(shù)據(jù)存取時(shí)間Fig.6 Data access time of different network sizes under random topology

圖7、8為在不同數(shù)據(jù)量與網(wǎng)絡(luò)節(jié)點(diǎn)情況下，各種算法在Internet 2拓?fù)鋱D中的數(shù)據(jù)存取時(shí)間.

圖7 Internet 2拓?fù)鋱D下不同數(shù)據(jù)量的數(shù)據(jù)存取時(shí)間Fig.7 Data access time of different data volumes under Internet 2 topology

圖8 Internet 2拓?fù)鋱D下不同網(wǎng)絡(luò)規(guī)模的數(shù)據(jù)存取時(shí)間Fig.8 Data access time of different network sizes under Internet 2 topology

從圖7、8中可以看出，隨著Internet 2拓?fù)鋱D中數(shù)據(jù)量的不斷增加，所有算法的數(shù)據(jù)存取時(shí)間均在增長(zhǎng).而本文算法的增長(zhǎng)速度最慢，且相較于其他算法需要更少的存取時(shí)間，且隨著Internet 2拓?fù)鋱D數(shù)據(jù)規(guī)模的不斷增加，本文算法所需的數(shù)據(jù)存取時(shí)間也是最低的.

從仿真結(jié)果可以看出，在Internet 2拓?fù)鋱D和隨機(jī)拓?fù)鋱D情況下，本文算法均具有最低的數(shù)據(jù)存取時(shí)間.這是因?yàn)橄噍^于其他算法，本文算法能在滿足安全距離約束的條件下選擇到最優(yōu)的數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)并使用最少的數(shù)據(jù)存取時(shí)間.

4 結(jié) 論

本文提出了一種基于K-距離拓?fù)涞姆植际綌?shù)據(jù)存儲(chǔ)方法.該算法使用K-距離拓?fù)渥訄D來表示數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，來保證數(shù)據(jù)塊的放置能滿足安全距離的要求.同時(shí)提出了一種基于節(jié)點(diǎn)優(yōu)先級(jí)選擇的算法，將存儲(chǔ)節(jié)點(diǎn)選擇過程轉(zhuǎn)化為在給定安全距離K條件下的拓?fù)溥x擇過程.使用Matlab和Omnet++仿真平臺(tái)在Internet 2拓?fù)鋱D與隨機(jī)拓?fù)鋱D下的仿真測(cè)試結(jié)果表明，所提出的算法能在滿足安全距離約束的條件下選擇到最優(yōu)的數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，從而減小數(shù)據(jù)存取時(shí)間.