張 皓，李敬偉，海本齋

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

0 引言

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

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

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

1 系統(tǒng)模型

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

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

1.1 副本管理器

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

1.2 副本選擇

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

1.3 副本目錄

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

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

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

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

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

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

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

3）放置副本。

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

為了選擇需要?jiǎng)?chuàng)建副本的文件即選擇副本，通過分析訪問歷史確定一個(gè)受歡迎的數(shù)據(jù)文件，并對(duì)不同的訪問數(shù)據(jù)設(shè)置不同的權(quán)值。基本上，越是最近被訪問得多的數(shù)據(jù)，就越適合于分析，因此，就要通過給予高權(quán)值設(shè)置一個(gè)最高優(yōu)先級(jí)，這可以通過計(jì)算PD 來找到它。PD 計(jì)算如下：

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

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

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

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

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

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

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

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

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

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

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

2.3 放置副本

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

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

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

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

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

創(chuàng)建一個(gè)節(jié)點(diǎn)的列表N_List

對(duì)列表采用式（12）按降序排列

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

存儲(chǔ)副本到列表N_List 中的第1 個(gè)節(jié)點(diǎn)n 中

3 算法實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

圖2 查詢生成流程

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

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

圖5 SBER 性能比較

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

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

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

4 結(jié)論

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