趙鑫宇 郭銀章

（太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 太原 030024）

1 引言

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

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

2 相關(guān)工作

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

在數(shù)據(jù)分配階段，聶世強(qiáng)等［11］結(jié)合矩陣表示和聚類算法，提升一致性hash算法的性能。為解決個(gè)多應(yīng)用目標(biāo)，Wu Q 等［12］提出了一種多目標(biāo)進(jìn)化算法。Sharma N K 等［13］結(jié)合粒子群和遺傳算法，對(duì)云環(huán)境資源利用率和節(jié)能等目標(biāo)進(jìn)行優(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ī)劃模型并設(shè)定安全等級(jí)機(jī)制，優(yōu)化數(shù)據(jù)檢索效率。吳超等［17］借鑒文獻(xiàn)［15］，按權(quán)重合成安全評(píng)估、訪問效率評(píng)估函數(shù)為最終適應(yīng)度函數(shù)，用遺傳算法求解數(shù)據(jù)片段分布方案。這些文獻(xiàn)中雖然都將安全性作為優(yōu)化目標(biāo)之一，但缺少具體數(shù)據(jù)分片、多備份存儲(chǔ)策略，也沒有考慮結(jié)點(diǎn)發(fā)生數(shù)據(jù)遷移時(shí)的負(fù)載均衡等問題。

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

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

3.1 數(shù)據(jù)分片標(biāo)準(zhǔn)建立

定義1 最終的安全需求定級(jí)L：

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

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

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

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

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

表1 分片數(shù)量標(biāo)準(zhǔn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 算法正確性分析

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

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

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

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

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

證明1：

當(dāng)i=1時(shí)，易得f（1）=priority［1］·S1；

當(dāng)i=2時(shí)，Si與priority［i］的組合方式有兩種，

假設(shè)：S2+x=S1；

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

計(jì)算可得：

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

故：

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

同理可遞推證得，當(dāng)i=3…n時(shí)：

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

5 實(shí)驗(yàn)仿真

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

5.1 對(duì)比實(shí)驗(yàn)組一

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

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

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

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

5.2 對(duì)比實(shí)驗(yàn)組二

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

圖5 負(fù)載均衡對(duì)比

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

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

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

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

6 結(jié)語(yǔ)

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