趙鑫宇 郭銀章

（太原科技大學計算機科學與技術學院 太原 030024）

1 引言

云存儲服務給用戶提供虛擬化的存儲資源池，數(shù)據(jù)實際存放在各個CSP 的服務器集群上［1］，不受用戶直接監(jiān)管。據(jù)調(diào)研機構RedLock 公司數(shù)據(jù)顯示，僅2017 年至2018 年就有超半數(shù)組織的云存儲服務發(fā)生數(shù)據(jù)泄露。針對云存儲中數(shù)據(jù)的安全性問題，大量研究從數(shù)據(jù)本身安全出發(fā)［2］，研究數(shù)據(jù)加密存儲技術、完整性審計技術、加密訪問控制技術等安全存儲策略［3～4］。而從云計算數(shù)據(jù)存儲的過程來看，如何有效地將數(shù)據(jù)資源劃分成合理的數(shù)據(jù)片，部署在恰當?shù)奈锢砑何恢?，以防止個別結(jié)點被入侵后，按照存儲路徑使相鄰節(jié)點乃至整個云存儲系統(tǒng)遭到破壞，已成為云數(shù)據(jù)存儲安全性研究的另一個重要問題。云環(huán)境中用戶數(shù)據(jù)存儲過程如圖1 所示，因此，需要基于安全性考慮，進一步研究云環(huán)境下數(shù)據(jù)存儲物理空間布局和存儲路徑優(yōu)化策略，以避免數(shù)據(jù)的泄露和破壞。

圖1 云中數(shù)據(jù)存儲過程

2 相關工作

數(shù)據(jù)資源初始分布包括數(shù)據(jù)片段的劃分和分配。在數(shù)據(jù)劃分階段，傳統(tǒng)數(shù)據(jù)庫（Oracle、DB2等）［5］采用簡單分片技術（hash、Range等）。各大云平臺則構建各自的數(shù)據(jù)存儲管理系統(tǒng)，谷歌的GFS和Big Table 均采用默認大小數(shù)據(jù)分片［6］；亞馬遜的Dynamo 采用一致性hash 算法［7］隨機分片。21 世紀前后，大量復雜分片技術被提出［8～9］，文獻［10］根據(jù)數(shù)據(jù)屬性間相關度垂直分片，添加泄露概率門限、偽造數(shù)據(jù)等安全措施。

在數(shù)據(jù)分配階段，聶世強等［11］結(jié)合矩陣表示和聚類算法，提升一致性hash算法的性能。為解決個多應用目標，Wu Q 等［12］提出了一種多目標進化算法。Sharma N K 等［13］結(jié)合粒子群和遺傳算法，對云環(huán)境資源利用率和節(jié)能等目標進行優(yōu)化。

基于安全需求，Ali M 等［14］將數(shù)據(jù)片段分布問題定義為圖著色問題，結(jié)合T-color［15］思想提出DROPS策略，通過保持“距離T”降低數(shù)據(jù)被完整獲取的可能，并保證較高數(shù)據(jù)檢索效率。Kang S等［16］開發(fā)了SEDuLOUS系統(tǒng)，定義線性規(guī)劃模型并設定安全等級機制，優(yōu)化數(shù)據(jù)檢索效率。吳超等［17］借鑒文獻［15］，按權重合成安全評估、訪問效率評估函數(shù)為最終適應度函數(shù)，用遺傳算法求解數(shù)據(jù)片段分布方案。這些文獻中雖然都將安全性作為優(yōu)化目標之一，但缺少具體數(shù)據(jù)分片、多備份存儲策略，也沒有考慮結(jié)點發(fā)生數(shù)據(jù)遷移時的負載均衡等問題。

3 云數(shù)據(jù)資源初始分片策略

將網(wǎng)絡中不同地理位置，具備存儲功能的數(shù)據(jù)中心（設備）定義為結(jié)點，假定總數(shù)為N，用戶所須安全標準為L。云數(shù)據(jù)資源初始分布流程：將用戶上傳的某份數(shù)據(jù)data，劃分為n個片段，合理分配到N 個結(jié)點上，以達到安全等級L。其中需解決的問題有安全等級L 的標準的建立、劃分n 個片段的原則、片段劃分和分配的策略。

3.1 數(shù)據(jù)分片標準建立

定義1 最終的安全需求定級L：

其中，Q代表上述環(huán)境中，2n個結(jié)點被入侵時，數(shù)據(jù)片段均被非法獲取的概率范圍。H 即結(jié)點間通信需經(jīng)歷的跳數(shù)hop，數(shù)據(jù)存儲在單個結(jié)點或相鄰結(jié)點時，hop 均定義為0。如圖2 所示的G（V，E）圖，在包含8 個存儲結(jié)點的網(wǎng)絡中，深色結(jié)點表示滿足hop=1 安全標準的一種存儲方案，其中所有數(shù)據(jù)片段所在結(jié)點互訪時需經(jīng)歷至少一個不存放分片的結(jié)點。

圖2 hop=1，著色結(jié)果

3.2 數(shù)據(jù)分割依據(jù)確立

定義2 根據(jù)3.1 節(jié)所述情形，由組合數(shù)學可求得數(shù)據(jù)泄露概率P。

對分片數(shù)量n 按升序遍歷，求解P 符合安全量級Q的要求，即可獲得的詳細符合安全標準的分片數(shù)量范圍。表1 給出低規(guī)模結(jié)點集群中，Q 對應的最低分片數(shù)量標準n。

表1 分片數(shù)量標準

3.3 數(shù)據(jù)分片的實施

如圖3，該算法對完成range分組且確立了數(shù)據(jù)劃分數(shù)量的數(shù)據(jù)，進行隨機大小分片，將劃分后的碎片按照大小降序排列，有助于后續(xù)數(shù)據(jù)分配策略的實施。

圖3 數(shù)據(jù)分片算法

4 云數(shù)據(jù)資源初始分配策略

4.1 數(shù)據(jù)初始分配策略

數(shù)據(jù)初始分配由SA-Greedy 算法完成，借鑒了貪心算法和T-color 思想。根據(jù)前文中的問題描述，核心問題為在結(jié)點分布的G（V，E）圖中，保證hop 要求（L 指標之一）的前提下，貪心選擇數(shù)據(jù)片段的存放位置，優(yōu)化數(shù)據(jù)檢索效率、系統(tǒng)負載均衡等指標。

定義3 為針對目標進行有效優(yōu)化，本文對數(shù)據(jù)的檢索代價CT做如下定義：

上式主要考慮數(shù)據(jù)傳輸代價，由數(shù)據(jù)的發(fā)送時延和傳播時延兩部分組成，前者為數(shù)據(jù)大小data_size 與網(wǎng)絡傳輸帶寬B 的比值，后者為由信號的傳輸距離shortest_path 和在傳輸介質(zhì)中速度speed_trans的比值。

定義4 為在多個滿足限制的結(jié)點中選擇合適的存儲結(jié)點，需同時考慮結(jié)點負載和傳輸代價問題，結(jié)點的利用率和傳輸代價均與存儲目標負相關，因此本文定義了各個結(jié)點的優(yōu)先程度數(shù)組priority［N］，作為貪心選擇的主要指標。

其中use_rage［i］代表i 結(jié)點的使用率，用傳輸代價和結(jié)點利用率乘積的倒數(shù)作為評判指標，分配某一片段時選擇優(yōu)先度最高的結(jié)點，分配完成后即更新相關屬性。

定義5 當前數(shù)據(jù)存儲方案優(yōu)越性sp：

其中n代表當前數(shù)據(jù)分片數(shù)，priority［i］代表第i 個碎片存儲位置的優(yōu)先級，Si代表當前碎片大小。采用貪心算法進行數(shù)據(jù)片段的位置選擇，可使sp在L需求下取到最大值。

數(shù)據(jù)分配算法如圖4，代碼1～3 行代表輸入所需參數(shù)，5～31行對數(shù)據(jù)的每個片段進行位置選擇。

圖4 數(shù)據(jù)分配算法

其中7～11 行，求解當前分配片段符合安全要求的結(jié)點標號存放在satisfy［］中；求解每個結(jié)點的優(yōu)越性存放在priority［］中。12～26 行，為當前數(shù)據(jù)的片段i 選擇優(yōu)越性最高、符合安全要求且存儲剩余容量滿足的結(jié)點并更新集群結(jié)點狀態(tài)。26～29行，在當前數(shù)據(jù)對象完成分配后，判斷當前待存儲片段是否存儲成功。32～33 行重置集群中結(jié)點的著色允許狀態(tài)，以備下一個數(shù)據(jù)存儲。

4.2 算法正確性分析

貪心算法的解的最優(yōu)性，需證明貪心選擇性和最優(yōu)子結(jié)構性質(zhì)。

1）貪心選擇性質(zhì)

本文策略在為每個數(shù)據(jù)片段i選擇存儲位置的時候，總是在所有當前符合L 標準的結(jié)點中選擇priority值最大的結(jié)點，該選擇方法符合貪心選擇性質(zhì)。

2）最優(yōu)子結(jié)構性質(zhì)

對n 個數(shù)據(jù)片段先按片段大小進行降序排列，假設完成排序后每個片段的大小為Si（S0最大）；然后對可選結(jié)點根據(jù)priority值降序排列，每個結(jié)點的的優(yōu)先級表示為priority［i］。求解前i 個片段的最大sp 值表示為f（i）。正常情況下，集群結(jié)點容量充足，對于單次片段的分配過程，可選的n 個最大pri-ority值的結(jié)點是固定的。

證明1：

當i=1時，易得f（1）=priority［1］·S1；

當i=2時，Si與priority［i］的組合方式有兩種，

假設：S2+x=S1；

priority［2］+y=priority［1］（x＞0，y＞0）；

計算可得：

（priority［1］·S1+priority［2·S2）-（priority［1］·S2+priority［2］·S1）=x·y＞0；

故：

f（2）=priority［1］·S1+priority［2］·S2；

同理可遞推證得，當i=3…n時：

上述性質(zhì)同時成立證明本問題使用貪心策略能夠獲取sp的最優(yōu)值。因此，本文所提算法能在保障安全性的前提下，很大程度提升系統(tǒng)在負載均衡和檢索效率方面的表現(xiàn)。

5 實驗仿真

本文通過數(shù)值模擬方法，求解使用SA-Greedy方法進行數(shù)據(jù)資源初始分配的結(jié)果。對比該策略與DROPS、一致性hash 策略、最遠優(yōu)先存儲策略、GA在執(zhí)行耗時以及各自所得布局方案在系統(tǒng)負載均衡、數(shù)據(jù)檢索效率、安全性能上的表現(xiàn)。

5.1 對比實驗組一

基礎參數(shù)：N=50，M=100，Q=1，hop=1；結(jié)點容量取值范圍50GB～100GB 的隨機值，單個數(shù)據(jù)大小取1GB～5GB 的隨機值，T=300km，結(jié)點實際位置：橫縱坐標0～1000，面積為1000km*1000km 區(qū)域內(nèi)隨機分布。策略實施時n值固定。獨立重復完成20次源數(shù)據(jù)分布后，各項指標的中位數(shù)結(jié)果如表2。

表2 實驗組1中位數(shù)結(jié)果

可看出實驗中SA-Greedy 在檢索效率上表現(xiàn)僅次于單目標遺傳算法，比DROPS 高出15%左右；算法耗時長于普通隨機策略，顯著短于復雜的進化算法；而由于選擇的低安全標準和集群規(guī)模，在安全性和負載均衡性的表現(xiàn)上無明顯優(yōu)勢。

為進一步研究云計算環(huán)境下，結(jié)點規(guī)模、數(shù)據(jù)量對幾種分布策略的性能表現(xiàn)，本文擴展初始環(huán)境，調(diào)整存儲數(shù)據(jù)量，進一步對比各項指標。

5.2 對比實驗組二

基礎參數(shù)調(diào)整：N=100，M=100，200，500、1000、2000；Q=3，hop=2；結(jié)點容量取范圍500GB～1000GB的隨機值，單個數(shù)據(jù)大小取2GB～10GB 的隨機值，T=500km。對于每個M 值進行20 次獨立重復實驗，實驗結(jié)果如圖5～7。

圖5 負載均衡對比

在當前環(huán)境下，L=6 時，SA-Greedy策略的Safty指標均達到109，達到最優(yōu)，且能有效避免臨近結(jié)點變節(jié)帶來的安全風險。圖5 顯示SA-Greedy 與DROPS 的負載均衡性均優(yōu)于最遠優(yōu)先存儲策略，略遜于一致性hash策略，但無顯著差異。在算法的執(zhí)行耗時上，圖6 說明一致性hash 策略和最遠優(yōu)先存儲策略有明顯優(yōu)勢，SA-Greedy與DROPS耗時相仿，但由于本次實驗耗時僅針對源數(shù)據(jù)，而DROPS的二輪存儲策略的實施極為耗時，故本文所提策略的耗時優(yōu)于DROPS方法。數(shù)據(jù)檢索效率上，由圖7可知，隨著數(shù)據(jù)存儲量的增加，SA-Greedy 策略能夠更好的保障用戶體驗。

圖6 算法執(zhí)行耗時對比

圖7 數(shù)據(jù)檢索效率對比

通過上述對比實驗可知，SA-Greedy 算法與傳統(tǒng)算法相比，在數(shù)據(jù)的安全性和檢索效率上有顯著改善。

6 結(jié)語

本文所述的SA-Greedy 方法，綜合數(shù)據(jù)分布的分片、分配階段提出了清晰的安全分級標準L 供客戶選擇；求解出云中符合標準L 的數(shù)據(jù)分布方案。實驗對比證明SA-Greedy 方法在保障了數(shù)據(jù)存儲安全性的同時，有負載均衡，執(zhí)行耗時短、檢索效率高等優(yōu)越性。下一步研究：1）針對不同類型數(shù)據(jù)，提出詳細的數(shù)據(jù)劃分依據(jù)；2）發(fā)生批量數(shù)據(jù)“刪”、“改”操作時，動態(tài)調(diào)整數(shù)據(jù)位置來保障系統(tǒng)性能。