張 皓，李敬偉，海本齋

（1.河南工學(xué)院計算機科學(xué)與技術(shù)系，河南 新鄉(xiāng) 453000；2.河南師范大學(xué)計算機與信息工程學(xué)院，河南 新鄉(xiāng) 453007）

0 引言

云計算是一種利用互連網(wǎng)和中央遠程服務(wù)器來為用戶提供適應(yīng)性服務(wù)的技術(shù)。在云中，服務(wù)通過具有“XaaS”的高速互聯(lián)網(wǎng)按需求發(fā)送給外部用戶，其中的“X”作為服務(wù)是一種計算結(jié)構(gòu)，被分解為3 部分：“基礎(chǔ)設(shè)施”、“平臺”和“應(yīng)用”。它以最便宜的價格、最強大的處理器給客戶提供最適合的服務(wù)，以滿足其業(yè)務(wù)功能，并提供良好的服務(wù)質(zhì)量如可用性、可擴展性和性能。如果能夠滿足全部業(yè)務(wù)需求但卻不能滿足性能質(zhì)量，則將導(dǎo)致軟件應(yīng)用終端用戶的更大不滿。在引入云之后，客戶選擇基于云的基礎(chǔ)設(shè)施，以提供高性能軟件應(yīng)用的基礎(chǔ)設(shè)施需求。

數(shù)據(jù)復(fù)制是在地理分布的站點上創(chuàng)建數(shù)據(jù)（文件、數(shù)據(jù)庫等）的相同復(fù)制品的一種技術(shù)，每一份復(fù)制品稱為一個副本［1］。數(shù)據(jù)復(fù)制已廣泛應(yīng)用于許多領(lǐng)域，如互聯(lián)網(wǎng)、對等系統(tǒng)和分布式數(shù)據(jù)庫等［2-4］。關(guān)于復(fù)制策略，副本優(yōu)化是軟件系統(tǒng)的性能增強技術(shù)之一。為了設(shè)計高效的動態(tài)數(shù)據(jù)復(fù)制方案，關(guān)鍵步驟是對數(shù)據(jù)訪問模式的分析［5-6］。在云計算中，復(fù)制是通過在不同節(jié)點上提供給用戶一個特定服務(wù)的多個副本，用于減少用戶等待時間、增加數(shù)據(jù)可用性和最小化云帶寬消耗；在復(fù)制環(huán)境中，文件或片段的副本被托管在多個系統(tǒng)或站點中。當(dāng)副本數(shù)量增加時，它通過改進局部性來提高系統(tǒng)性能；然而，它還包括額外的數(shù)據(jù)傳輸，以保持副本更新來獲得數(shù)據(jù)的一致性。文獻［7］討論了P2P 復(fù)制系統(tǒng)，提出了動態(tài)副本分布方法，給出了副本目錄的設(shè)計和副本信息的獲取方法，能夠獲得某一邏輯資源的所有副本信息，然后根據(jù)邏輯資源的全局副本信息，對訪問頻率高且平均響應(yīng)時間長的數(shù)據(jù)資源進行復(fù)制，并給出副本數(shù)量的計算方法；文獻［8］提出了稱為最新訪問最大權(quán)值的動態(tài)數(shù)據(jù)復(fù)制策略，以減少作業(yè)執(zhí)行時間，找到受歡迎的文件并復(fù)制到合適的站點，以實現(xiàn)系統(tǒng)負載平衡；在文獻［9］中，作者提出了動態(tài)片段分配的新框架。通過采用這種技術(shù)，在框架內(nèi)找到最優(yōu)分配方案，為碎片分配問題提供了有效的解決方案；文獻［10］提出了一種改進的最新訪問最大權(quán)值算法，與現(xiàn)有的8 種算法進行了比較，并改進了平均作業(yè)時間和在全部訪問模式下有效的網(wǎng)絡(luò)，特別是在不同隨機文件訪問模式下；文獻［11-12］提出了2 種動態(tài)集中數(shù)據(jù)復(fù)制算法。算法通過創(chuàng)建和擴展超級數(shù)據(jù)中心到主要數(shù)據(jù)中心的副本，使得數(shù)據(jù)訪問時間和網(wǎng)絡(luò)負載最小化；文獻［13］研究了云計算數(shù)據(jù)中心的數(shù)據(jù)復(fù)制技術(shù)，以使能量消耗、網(wǎng)絡(luò)帶寬和通信延遲最小化，該技術(shù)可以應(yīng)用于地理上分布的數(shù)據(jù)中心，以及每個單獨的數(shù)據(jù)中心內(nèi)部。

為了提高云存儲計算環(huán)境中軟件系統(tǒng)的性能，本文提出了一種動態(tài)數(shù)據(jù)復(fù)制和放置算法。動態(tài)數(shù)據(jù)復(fù)制采用受歡迎程度（Popularity Degree，PD）來找到需要復(fù)制的文件，采用復(fù)制因子（Replica Factor，RF）來創(chuàng)建副本，最后采用一種基于可用性的放置算法將副本放置在合適的位置，即算法包括3 個階段：1）采用PD 選擇需要創(chuàng)建副本的文件；2）采用RF 創(chuàng)建副本；3）放置副本。

1 系統(tǒng)模型

在云計算中，云存儲被認為是一個非常重要的因素，它是一種數(shù)據(jù)遠程維護、管理和備份的服務(wù)，允許用戶在線存儲文件，將上傳的文件保存在外部服務(wù)器上，以便用戶可以通過互聯(lián)網(wǎng)從任何位置訪問文件?？捎眯跃褪强刹僮餍曰蚩商峤坏倪\行狀態(tài)。為了提高系統(tǒng)性能，應(yīng)當(dāng)增加可用性。一個系統(tǒng)的可用性定義為A=MTTF/（MTTF+MTTR）， 其中MTTF 是業(yè)務(wù)系統(tǒng)的平均無故障時間（Mean Time Too Failure，MTTF），MTTR 是平均修復(fù)時間（Mean Time To Repair，MTTR）。對于云數(shù)據(jù)服務(wù)中心來說，它的架構(gòu)如圖1 所示，包括：1）副本管理器；2）副本選擇；3）副本目錄；4）調(diào)度和副本代理。

圖1 云數(shù)據(jù)中心體系結(jié)構(gòu)

1.1 副本管理器

副本管理器控制復(fù)制管理系統(tǒng)的整個操作。它有助于根據(jù)用戶需求創(chuàng)建和管理副本，增加存儲空間和目錄，以跟蹤全部副本及其位置；副本管理器保存了區(qū)域內(nèi)關(guān)于數(shù)據(jù)中心和副本位置的一般信息，提供副本服務(wù)，并管理副本訪問、一致性、核心副本創(chuàng)建、刪除和身份驗證；副本管理器支持云之間的數(shù)據(jù)管理和數(shù)據(jù)傳輸，還跟蹤用戶訪問模式，監(jiān)測數(shù)據(jù)的受歡迎程度，并根據(jù)其可用性確定是否需要本地創(chuàng)建；副本管理器和目錄彼此同步通信，以維持成功的復(fù)制過程。

1.2 副本選擇

副本選擇需要關(guān)于存儲系統(tǒng)的容量和性能特征信息，副本選擇是采用副本選擇器來完成，它基于用戶需求和在訪問時間內(nèi)出現(xiàn)的故障。通過選擇合理的副本，可以改善服務(wù)響應(yīng)時間，并降低服務(wù)成本；副本選擇器中的緩存功能用于創(chuàng)建相應(yīng)的服務(wù)終結(jié)點和請求副本的復(fù)制。

1.3 副本目錄

每個新創(chuàng)建的副本都登記在副本目錄表中。副本目錄還負責(zé)查找請求的數(shù)據(jù)，并維護區(qū)域中的用戶基數(shù)、數(shù)據(jù)中心、副本的數(shù)量，以及在某時刻的請求數(shù)量和可用性。當(dāng)站點每次存儲一個新副本時，它就發(fā)送一個文件注冊請求給副本目錄，副本目錄將該站點添加到站點列表并保存副本。然后由應(yīng)用查詢目錄，以找到每個數(shù)據(jù)中心中一個特定副本位置的可用副本的位置；副本目錄包含關(guān)于副本和相關(guān)副本的位置以及與這些復(fù)制的數(shù)據(jù)相關(guān)聯(lián)的元數(shù)據(jù)信息。

1.4 調(diào)度和副本代理

調(diào)度代理是中央管理代理。調(diào)度器讀取服務(wù)列表，并采用服務(wù)描述文件作為輸入來部署每個新服務(wù)；副本代理用于管理副本文件的活動，控件將首先從用戶移動到調(diào)度代理，在那里調(diào)度用戶請求并將控制權(quán)傳遞給副本代理，指示要創(chuàng)建的副本文件，并將其發(fā)送給副本管理器，決定將這些副本放置在何處。

2 基于3 階段的云存儲計算系統(tǒng)

在本文提出的算法中，采用動態(tài)數(shù)據(jù)復(fù)制和放置算法來實現(xiàn)云存儲軟件系統(tǒng)。為了實現(xiàn)動態(tài)數(shù)據(jù)復(fù)制，需要解決3 個重要問題。1）哪些數(shù)據(jù)應(yīng)當(dāng)復(fù)制、何時復(fù)制，以減少等待時間或加快數(shù)據(jù)訪問速度；2）應(yīng)當(dāng)創(chuàng)建多少合適的新副本。隨著新副本數(shù)量的增加，系統(tǒng)維護成本將顯著增加；3）新副本應(yīng)當(dāng)放在哪里，以滿足系統(tǒng)任務(wù)的成功執(zhí)行率和帶寬消耗要求。為此，分3 個階段實現(xiàn)：

1）根據(jù)PD 選擇需要創(chuàng)建副本的文件；

2）根據(jù)RF 創(chuàng)建副本；

3）放置副本。

2.1 根據(jù)PD 選擇需要創(chuàng)建副本的文件

為了選擇需要創(chuàng)建副本的文件即選擇副本，通過分析訪問歷史確定一個受歡迎的數(shù)據(jù)文件，并對不同的訪問數(shù)據(jù)設(shè)置不同的權(quán)值?；旧希绞亲罱辉L問得多的數(shù)據(jù)，就越適合于分析，因此，就要通過給予高權(quán)值設(shè)置一個最高優(yōu)先級，這可以通過計算PD 來找到它。PD 計算如下：

式中，Q1表示第1 因子，Q2表示第2 因子。Q1的計算公式如下：

式中，F(xiàn)A 表示在時間ti和ti+1之間的訪問頻率，nu表示在ti和ti+1之間唯一用戶的數(shù)量，nr表示在ti和ti+1之間重復(fù)的用戶數(shù)量，ts表示開始時間，tp表示當(dāng)前時間。第1 個因子是通過采用訪問頻率和反向訪問頻率乘積來計算的。第2 個因子的計算公式如下：

式中，Wt是一個文件中表的總權(quán)值。第2 個因子是通過采用一個時間間隔中的訪問頻率和一個文件中每個表的總權(quán)值的乘積來計算的，然后求出每個間隔上得到的值的和來計算第2 個因子的值。在每個文件中有許多表，而且每個表都有權(quán)值。總的權(quán)值是一個文件中每個表的權(quán)值相加。

2.2 根據(jù)RF 創(chuàng)建副本

RF 的計算用于查找數(shù)據(jù)文件是否應(yīng)當(dāng)復(fù)制或創(chuàng)建副本。通過計算正因子（Positive Factor，PF）和負因子（Negative Factor，NF）來計算復(fù)制因子。正因子就是確定復(fù)制一個文件的重要性，計算公式如下：

式中，PDcurrent表示當(dāng)前文件的受歡迎程度，PDmin表示最小受歡迎程度，PDmax表示最大受歡迎程度。計算正因子以找到復(fù)制文件的重要性，此后，必須計算每個文件的負度（Negative Degree，ND）。負度的計算是用來得到負因子（Negative Factor，NF）。一個文件的NF 表明是否一個文件不應(yīng)當(dāng)被復(fù)制。每個文件的ND 計算如下：

式中，M 表示一個文件的存儲大小，R 表示副本的存在數(shù)量，QRT 表示查詢響應(yīng)時間。ND 用于計算一個文件的負因子NF。負因子的計算公式如下：

式中，NDcurrent表示當(dāng)前文件的負度值，NDmin表示最小負度值，NDmax表示最大負度值。

然后就可以用下面的公式計算復(fù)制因子：

式中，γ 和α 是常數(shù)值，它們是通過檢查不同值的性能而指定為1。

隨后通過下列條件生成副本數(shù)量Nr：式中，RFt表示在一個時間間隔t 的復(fù)制因子，RFt-1表示在前一個時間間隔t-1 的復(fù)制因子。它把復(fù)制因子和閾值進行比較來決定是否為特定文件創(chuàng)建副本。如果副本大于閾值，則將創(chuàng)建副本，在分配節(jié)點時將考慮這些副本。

2.3 放置副本

放置策略要考慮所需的可用性、系統(tǒng)中節(jié)點的穩(wěn)定性和故障，需要一個位置來放置從前面步驟得到的副本。對此，首先必須考慮數(shù)據(jù)中心中的節(jié)點列表，然后采用下面所述的分類標(biāo)準(zhǔn)把這些節(jié)點按降序安排。實踐表明，在同一節(jié)點放置同一數(shù)據(jù)的多個副本并不能提高可用性或容錯性?？紤]一些節(jié)點列表并計算這些節(jié)點的可用性因子（AF），計算可用性因子以找到特定節(jié)點是否可以放置數(shù)據(jù)。節(jié)點Ni的可用性因子計算如下：

如果一個節(jié)點Ni具有好的AF，則它就具有好的穩(wěn)定性STAB（Ni）和低故障率FR（Ni），穩(wěn)定性的范圍為在0≤STAB（Ni）≤1，節(jié)點Ni的故障率計算如下：

式中，k 是在節(jié)點Ni中數(shù)據(jù)的數(shù)量，Dij是存儲在節(jié)點Ni中的數(shù)據(jù)j。為了加大相同副本之間的距離，即非相似性函數(shù)，定義為：

式中，n 是一個節(jié)點，LDn是節(jié)點n 中本地數(shù)據(jù)的列表，DNn是數(shù)據(jù)中心中節(jié)點n 的全部鄰居的數(shù)據(jù)列表。這里（n）就是節(jié)點n 的數(shù)據(jù)列表和它的鄰居數(shù)據(jù)列表之間的數(shù)據(jù)差的大小。例如，如果（n）=0，則節(jié)點n 中的全部數(shù)據(jù)存在于鄰域中。為了避免（n）=0 這種不確定的情況，根據(jù)下列標(biāo)準(zhǔn)對節(jié)點進行分類。

算法1 副本放置算法偽代碼

創(chuàng)建一個節(jié)點的列表N_List

對列表采用式（12）按降序排列

存儲數(shù)據(jù)副本在節(jié)點n 中

存儲副本到列表N_List 中的第1 個節(jié)點n 中

3 算法實驗結(jié)果

3.1 實驗設(shè)置

為了對本文提出的云存儲計算系統(tǒng)性能進行驗證，采用Java（jdk1.6）來實現(xiàn)，安裝的系統(tǒng)配置為：酷睿i5 處理器，3.2 GHz 時鐘速率，4GB RAM。采用下頁表1 所示的某醫(yī)院部分病人的樣本數(shù)據(jù)集，數(shù)據(jù)集包括身份識別號（ID）、性別（SEX）、生日（Birthday）、描述（Description）、第1 次時間（First Date）、入院（Admission）和診斷結(jié)論（Diagnosis）。

表1 樣本數(shù)據(jù)庫

3.2 實驗結(jié)果

為了對本文提出的算法性能進行評價，將本文提出的算法和目前比較先進的技術(shù)［11-12］在系統(tǒng)字節(jié)有效率（SBER）和執(zhí)行時間兩方面性能進行比較。

首先執(zhí)行本文提出的算法，生成的查詢流程如圖2 所示。生成的查詢在數(shù)據(jù)庫中進行搜索，并把查詢相關(guān)結(jié)果在短時間內(nèi)提供給用戶。圖3 和圖4分別為可用性與查詢數(shù)量、副本數(shù)量和可用性因子之間的關(guān)系?？梢姡?dāng)查詢數(shù)量增加時，可用性增加，而且可用性增加時，可以增加副本數(shù)量的創(chuàng)建。因此，相關(guān)數(shù)據(jù)可以放在云中，而且訪問查詢相關(guān)數(shù)據(jù)所需的時間可以快速而有效地完成。

圖2 查詢生成流程

圖3 可用性與查詢數(shù)量的關(guān)系

圖4 副本數(shù)量與可用性的關(guān)系

圖5 SBER 性能比較

圖6 執(zhí)行時間性能比較

圖5 所示為本文提出的算法與現(xiàn)有技術(shù)［11-12］在SBER 性能方面得到的比較結(jié)果。從圖5 可見，在每個時間間隔，本文提出策略得到的SBER 值要高于現(xiàn)有技術(shù)［11-12］，而且基本不隨時間間隔的增加而改變，有很好的穩(wěn)定性。這主要是由于本文的算法是采用可用性因子和分類標(biāo)準(zhǔn)計算并找到被創(chuàng)建的副本數(shù)量，然后把副本放置在相應(yīng)的節(jié)點，節(jié)點基于又節(jié)點的可用性來安排，從而減少了網(wǎng)絡(luò)中的過載，提高了帶寬利用率。

圖6 所示為本文提出的算法與現(xiàn)有技術(shù)［11-12］在查詢性能方面得到的比較結(jié)果。從圖6 可見，當(dāng)查詢數(shù)量增加時，不同技術(shù)的執(zhí)行時間都會增加，但相比于現(xiàn)有技術(shù)［11-12］來說，本文算法的執(zhí)行時間隨查詢數(shù)量增加要低得多，執(zhí)行每個查詢量所需的時間更少，分別比文獻［11］和文獻［12］平均低43%和49%，提高了系統(tǒng)性能。這主要是由于在本文提出的算法中，找到需要復(fù)制的數(shù)據(jù)，然后采用受歡迎程度和復(fù)制因子來創(chuàng)建副本，這有助于減少等待時間，加快進程，減少由查詢執(zhí)行過程所花費的時間。

4 結(jié)論

為了提高云計算存儲系統(tǒng)的性能，本文提出了一種基于3 階段的動態(tài)數(shù)據(jù)復(fù)制策略和放置算法。在該技術(shù)中，使用受歡迎程度和復(fù)制因子來識別要復(fù)制的文件和復(fù)制文件的數(shù)量，并通過向用戶提供相同服務(wù)的不同副本來增加數(shù)據(jù)可用性；然后采用一種放置算法，將副本放置在相應(yīng)的節(jié)點或標(biāo)識的系統(tǒng)中，提高了系統(tǒng)的性能而沒有系統(tǒng)過載節(jié)點的副本放置，從而改善云系統(tǒng)任務(wù)的成功執(zhí)行率，并最大限度地減少云系統(tǒng)帶寬消耗。