何典 ，吳敏，胡春華

(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410083；2. 湖南商學(xué)院 計(jì)算機(jī)與電子工程學(xué)院，湖南 長(zhǎng)沙，410205)

物聯(lián)網(wǎng)時(shí)刻在產(chǎn)生大量的數(shù)據(jù)，需要對(duì)這些數(shù)據(jù)進(jìn)行采集、處理、存儲(chǔ)、分析和應(yīng)用等操作。物聯(lián)網(wǎng)結(jié)點(diǎn)數(shù)目多，數(shù)據(jù)規(guī)模巨大，需要有一個(gè)分布式數(shù)據(jù)管理體系來(lái)管理和整合。傳統(tǒng)的分布式數(shù)據(jù)庫(kù)系統(tǒng)，局部故障和數(shù)據(jù)同步更新帶來(lái)的開(kāi)銷影響系統(tǒng)性能，使得數(shù)據(jù)量和結(jié)點(diǎn)數(shù)目均受到限制[1]，無(wú)法滿足物聯(lián)網(wǎng)環(huán)境下數(shù)據(jù)管理的要求。云存儲(chǔ)是一種基于互聯(lián)網(wǎng)的全局分布式資源存儲(chǔ)和訪問(wèn)模型，能同時(shí)向大量的用戶提供高傳輸率和高吞吐量的數(shù)據(jù)服務(wù)。云存儲(chǔ)是云計(jì)算的重要基礎(chǔ)和主要應(yīng)用領(lǐng)域，能夠管理大數(shù)據(jù)集，高效地在海量數(shù)據(jù)中存儲(chǔ)、處理、分析和訪問(wèn)特定對(duì)象?，F(xiàn)有的云存儲(chǔ)數(shù)據(jù)管理技術(shù)包括 Google Bigtable[2]，Yahoo PNUTS[3]，Amazon Dynamo[4]，Amazon S3和 Microsoft Live Mesh等。另外，數(shù)據(jù)的可靠性、可用性和經(jīng)濟(jì)性對(duì)數(shù)據(jù)的提供者和使用者至關(guān)重要。為保證這些特性，云存儲(chǔ)系統(tǒng)為同一數(shù)據(jù)復(fù)制多個(gè)副本，副本的分布將直接影響到副本存儲(chǔ)、查詢和更新的開(kāi)銷。在一些云存儲(chǔ)系統(tǒng)中[5-6]，副本所在的存儲(chǔ)服務(wù)器通過(guò) Hash算法等隨機(jī)選擇，具有隨機(jī)的分布位置。Amazon Dynamo[4]采用靜態(tài)方法進(jìn)行副本分布。由于沒(méi)有考慮到副本備份的地理位置、開(kāi)銷和數(shù)據(jù)訪問(wèn)位置等問(wèn)題，靜態(tài)或隨機(jī)的數(shù)據(jù)分布，均可能帶來(lái)較高的訪問(wèn)代價(jià)[7]。物聯(lián)網(wǎng)中有大量的移動(dòng)設(shè)備。移動(dòng)設(shè)備數(shù)據(jù)的存儲(chǔ)和管理困難在于數(shù)據(jù)量的不斷膨脹和移動(dòng)設(shè)備本身的固有限制，例如存儲(chǔ)空間限制、計(jì)算能力限制和無(wú)線連接的間歇性等。而且，物聯(lián)網(wǎng)中各個(gè)結(jié)點(diǎn)的通信能力不同，較寬的帶寬并不能在物聯(lián)網(wǎng)的每一個(gè)部分都得到保證。因此，物聯(lián)網(wǎng)中的數(shù)據(jù)訪問(wèn)需要有較低的訪問(wèn)代價(jià)。Bonvin等[8-9]提出一種有成本效益分析的、可伸縮的云存儲(chǔ)副本復(fù)制策略。但物聯(lián)網(wǎng)中的移動(dòng)終端在不同結(jié)點(diǎn)間訪問(wèn)數(shù)據(jù)時(shí)，需要較快的響應(yīng)速度，各個(gè)訪問(wèn)點(diǎn)的數(shù)據(jù)訪問(wèn)代價(jià)并不相同，臨時(shí)根據(jù)訪問(wèn)代價(jià)進(jìn)行副本復(fù)制和遷移的決策會(huì)損失較大的實(shí)時(shí)性能，難以滿足要求。數(shù)據(jù)網(wǎng)格是有效的分布式數(shù)據(jù)存儲(chǔ)系統(tǒng)，與副本管理有關(guān)的研究成果較多[10-11]。但云存儲(chǔ)的應(yīng)用范圍和面向用戶數(shù)目均比網(wǎng)格環(huán)境大。在數(shù)據(jù)網(wǎng)格算法中，多從網(wǎng)格結(jié)點(diǎn)或者網(wǎng)格系統(tǒng)的角度出發(fā)來(lái)考慮效益，例如通過(guò)效益函數(shù)，或者計(jì)算任務(wù)完成時(shí)間等[12-14]。物聯(lián)網(wǎng)中應(yīng)用程序的數(shù)據(jù)訪問(wèn)要求較高的移動(dòng)性和實(shí)時(shí)性，無(wú)論是從應(yīng)用程序數(shù)據(jù)訪問(wèn)代價(jià)的角度，還是從系統(tǒng)總的開(kāi)銷的角度來(lái)看，物聯(lián)網(wǎng)中的用戶層對(duì)存儲(chǔ)層的訪問(wèn)代價(jià)均要著重考慮，即從用戶的角度來(lái)考慮總體的訪問(wèn)開(kāi)銷。而且由于數(shù)據(jù)量急劇膨脹，同一數(shù)據(jù)的副本數(shù)目不能太多，過(guò)多的副本冗余將降低存儲(chǔ)空間的使用效率并加重?cái)?shù)據(jù)更新的負(fù)擔(dān)，需要更高的數(shù)據(jù)一致性保證網(wǎng)絡(luò)通信能力。當(dāng)數(shù)據(jù)網(wǎng)格中提出的方法在存儲(chǔ)結(jié)點(diǎn)數(shù)為 100個(gè)時(shí)，若副本數(shù)目超過(guò) 20個(gè)[15]，則在云存儲(chǔ)系統(tǒng)中無(wú)法實(shí)現(xiàn)。云存儲(chǔ)系統(tǒng)為同一數(shù)據(jù)提供副本數(shù)目很少。例如，Google和Amazon提供的云存儲(chǔ)服務(wù)的數(shù)據(jù)副本均為3個(gè)。因此，數(shù)據(jù)網(wǎng)格中的副本分布方法不能直接應(yīng)用于云存儲(chǔ)，特別是物聯(lián)網(wǎng)環(huán)境中。

物聯(lián)網(wǎng)各個(gè)結(jié)點(diǎn)的存儲(chǔ)能力和網(wǎng)絡(luò)狀態(tài)不同，備份開(kāi)銷不同，所承擔(dān)的副本存儲(chǔ)任務(wù)也應(yīng)不同。同時(shí)，數(shù)據(jù)副本被訪問(wèn)的情況也應(yīng)作為確定副本分布方法的依據(jù)之一。如果副本能夠按照某些條件進(jìn)行分布，并適應(yīng)數(shù)據(jù)訪問(wèn)的實(shí)際情況，數(shù)據(jù)訪問(wèn)代價(jià)將會(huì)減少。僅考慮訪問(wèn)代價(jià)來(lái)選擇存儲(chǔ)服務(wù)器，會(huì)造成集中選擇低代價(jià)存儲(chǔ)服務(wù)器來(lái)存儲(chǔ)副本，出現(xiàn)各服務(wù)器負(fù)載不均衡的現(xiàn)象。本文作者提出在最少副本前提下，考慮訪問(wèn)代價(jià)和數(shù)據(jù)被訪問(wèn)情況的副本分布方法，并設(shè)計(jì)負(fù)載均衡機(jī)制，使云存儲(chǔ)系統(tǒng)中應(yīng)用程序的數(shù)據(jù)訪問(wèn)總代價(jià)較低，各云存儲(chǔ)服務(wù)器的負(fù)載整體均衡。

1 云存儲(chǔ)副本分布及訪問(wèn)代價(jià)

1.1 副本數(shù)目與類型

副本數(shù)目與類型是討論副本分布方法的前提。

1.1.1 副本數(shù)目

為了容錯(cuò)，同一數(shù)據(jù)應(yīng)至少保留3個(gè)副本。如果存在數(shù)據(jù)副本不一致，可通過(guò)投票機(jī)制，決出產(chǎn)生錯(cuò)誤的副本。當(dāng)然，副本數(shù)目也可以是任意大于2的奇數(shù)。但過(guò)多的副本會(huì)增加維持?jǐn)?shù)據(jù)一致性的復(fù)雜性和開(kāi)銷。在云存儲(chǔ)系統(tǒng)中，數(shù)據(jù)量太大，存儲(chǔ)空間消耗過(guò)快，難以為同一數(shù)據(jù)保留過(guò)多的副本，典型的云存儲(chǔ)系統(tǒng)提供3個(gè)副本。

1.1.2 副本類型

副本分為臨時(shí)副本、永久副本和長(zhǎng)期副本[16]：臨時(shí)副本用來(lái)提高訪問(wèn)性能(位于存儲(chǔ)服務(wù)器上)，永久副本用來(lái)備份數(shù)據(jù)，長(zhǎng)期副本用來(lái)對(duì)副本歸檔。假設(shè)副本總數(shù)為3，本文為同一數(shù)據(jù)定義2個(gè)臨時(shí)副本和1個(gè)永久副本，這樣既可以提高數(shù)據(jù)訪問(wèn)效率，又能夠?qū)?shù)據(jù)進(jìn)行備份。本文中，訪問(wèn)代價(jià)是指對(duì)臨時(shí)副本的訪問(wèn)代價(jià)，副本位置是指存儲(chǔ)2個(gè)臨時(shí)副本的云存儲(chǔ)服務(wù)器的位置。

1.2 訪問(wèn)代價(jià)描述

通過(guò)應(yīng)用程序接口(API)，應(yīng)用程序在數(shù)據(jù)訪問(wèn)服務(wù)提供點(diǎn)訪問(wèn)云存儲(chǔ)中的數(shù)據(jù)。云存儲(chǔ)數(shù)據(jù)管理系統(tǒng)接到訪問(wèn)請(qǐng)求之后，將數(shù)據(jù)查詢等訪問(wèn)結(jié)果返回給應(yīng)用程序。整個(gè)數(shù)據(jù)訪問(wèn)可以看作一系列虛擬化的過(guò)程，訪問(wèn)細(xì)節(jié)對(duì)應(yīng)用程序而言是透明的。整個(gè)系統(tǒng)的模型可用圖1來(lái)表示。

圖1中，云存儲(chǔ)系統(tǒng)由分布在多個(gè)地點(diǎn)的存儲(chǔ)服務(wù)器組成，服務(wù)器的集合記作 S，各存儲(chǔ)服務(wù)器Sj∈S,j = 1,2,… ,n 。應(yīng)用程序訪問(wèn)提供云存儲(chǔ)接入服務(wù)的各服務(wù)提供點(diǎn)，這些提供點(diǎn)的集合記作 A，各服務(wù)提供點(diǎn) ai∈A,i = 1,2,… ,m。將服務(wù)提供點(diǎn)對(duì)存儲(chǔ)服務(wù)器的訪問(wèn)代價(jià)記錄在矩陣C中，即：

圖1 云存儲(chǔ)數(shù)據(jù)訪問(wèn)模型Fig.1 Data access model in cloud storage

其中：Ci,j表示服務(wù)提供點(diǎn)ai對(duì)存儲(chǔ)服務(wù)器Sj訪問(wèn)的代價(jià)(i=1，2，…， m；j=1，2，…，n)。具體的訪問(wèn)代價(jià)受通信開(kāi)銷、帶寬分配、硬件配置、存儲(chǔ)容量及利用率和查詢負(fù)載等因素的影響，其計(jì)算見(jiàn)文獻(xiàn)[8-9]。

2 低訪問(wèn)代價(jià)副本分布

在物聯(lián)網(wǎng)中，考慮到帶寬和可靠性等限制，應(yīng)用程序訪問(wèn)數(shù)據(jù)應(yīng)選擇較小訪問(wèn)代價(jià)的存儲(chǔ)服務(wù)器，以提高訪問(wèn)效率。而且，物聯(lián)網(wǎng)中結(jié)點(diǎn)具有移動(dòng)性，當(dāng)應(yīng)用程序在多個(gè)服務(wù)提供點(diǎn)訪問(wèn)數(shù)據(jù)副本時(shí)，應(yīng)找出與這些服務(wù)提供點(diǎn)相對(duì)應(yīng)的低代價(jià)存儲(chǔ)服務(wù)器。

根據(jù)當(dāng)前訪問(wèn)位置臨時(shí)進(jìn)行代價(jià)計(jì)算，決定副本存放位置和是否進(jìn)行遷移的方法，難以滿足物聯(lián)網(wǎng)實(shí)時(shí)性的要求。低代價(jià)存儲(chǔ)服務(wù)器的位置可通過(guò)分析數(shù)據(jù)訪問(wèn)的歷史數(shù)據(jù)來(lái)確定，并根據(jù)情況變化適當(dāng)進(jìn)行修正，不必臨時(shí)進(jìn)行代價(jià)計(jì)算。

2.1 低代價(jià)副本分布方法

找到最低訪問(wèn)代價(jià)的2個(gè)存儲(chǔ)服務(wù)器來(lái)布置數(shù)據(jù)r的副本，相當(dāng)于在矩陣C中找出m個(gè)元素，這m個(gè)元素僅屬于矩陣的某2列，并且元素之和最小。應(yīng)用程序沒(méi)有訪問(wèn)的服務(wù)提供點(diǎn)不參與計(jì)算。使用集合 V記錄應(yīng)用程序?qū)Ψ?wù)提供點(diǎn)訪問(wèn)的情況：

其中：若vi=0，則表示應(yīng)用程序未在服務(wù)提供點(diǎn)i訪問(wèn)過(guò)數(shù)據(jù)r；若vi=1，則表示應(yīng)用程序在服務(wù)提供點(diǎn)i訪問(wèn)過(guò)數(shù)據(jù) r。未訪問(wèn)過(guò)的結(jié)點(diǎn)不需要參與總代價(jià)計(jì)算。由于僅考慮整個(gè)拓?fù)浣Y(jié)構(gòu)的一部分，減少了計(jì)算的復(fù)雜度，計(jì)算結(jié)果與訪問(wèn)情況相符合。數(shù)據(jù)r最低代價(jià)計(jì)算公式為：

由式(3)計(jì)算得到最小訪問(wèn)代價(jià)fmin-cost，與之對(duì)應(yīng)的i和j表示2個(gè)副本應(yīng)分別存放在存儲(chǔ)服務(wù)器Si和Sj上。

2.2 結(jié)合訪問(wèn)頻率

應(yīng)用程序在不同的數(shù)據(jù)訪問(wèn)服務(wù)提供點(diǎn)多次訪問(wèn)某一數(shù)據(jù)，將產(chǎn)生這段時(shí)間內(nèi)對(duì)該數(shù)據(jù)的副本訪問(wèn)總代價(jià)。由于應(yīng)用程序在不同的服務(wù)提供點(diǎn)訪問(wèn)該數(shù)據(jù)的次數(shù)并不相同，由式(3)選取的存儲(chǔ)服務(wù)器，可能存在來(lái)自較低代價(jià)服務(wù)提供點(diǎn)的數(shù)據(jù)訪問(wèn)次數(shù)少，而較高代價(jià)服務(wù)提供點(diǎn)的數(shù)據(jù)訪問(wèn)次數(shù)多的情況，使得其總代價(jià)不一定最小。因此，結(jié)合訪問(wèn)頻率來(lái)計(jì)算總的訪問(wèn)代價(jià)更為合理。

使用集合P記錄應(yīng)用程序?qū)δ硵?shù)據(jù)r的訪問(wèn)頻率，如式(4)所示：

其中：pi表示應(yīng)用程序在服務(wù)提供點(diǎn)i對(duì)數(shù)據(jù)r訪問(wèn)的頻率，即在該服務(wù)提供點(diǎn)訪問(wèn)該數(shù)據(jù)的次數(shù)占所有服務(wù)提供點(diǎn)對(duì)該數(shù)據(jù)訪問(wèn)總次數(shù)的比例。pi=0表示在服務(wù)提供點(diǎn)i未訪問(wèn)過(guò)該數(shù)據(jù)r。

將應(yīng)用程序在服務(wù)提供點(diǎn)i訪問(wèn)某數(shù)據(jù)的次數(shù)記為ti，則pi計(jì)算方法為：

可以將集合P中的元素作為計(jì)算最小代價(jià)的加權(quán)值。修改式(3)進(jìn)行數(shù)據(jù)r最低總代價(jià)計(jì)算和選擇存儲(chǔ)服務(wù)器：

2.3 考慮訪問(wèn)頻率的合理性

由下例說(shuō)明結(jié)合訪問(wèn)頻率的副本分布的合理性和正確性。例如，有10個(gè)訪問(wèn)服務(wù)提供點(diǎn)，5個(gè)存儲(chǔ)服務(wù)器，根據(jù)式(1)，其訪問(wèn)代價(jià)矩陣C如下所示：

如果某數(shù)據(jù)的訪問(wèn)情況V={ 1, 1, 0, 1, 0, 0, 0, 0, 1,0}，使用的訪問(wèn)代價(jià)矩陣相當(dāng)于：

然后，找出具有代價(jià)之和最小的2列，如下面矩陣中的有下劃線的數(shù)字所示。對(duì)于該數(shù)據(jù)，選擇S2和S5為存儲(chǔ)服務(wù)器具有最小的總訪問(wèn)代價(jià)，值為21。

若在某一段訪問(wèn)時(shí)間內(nèi)，在這4個(gè)服務(wù)提供點(diǎn)訪問(wèn)數(shù)據(jù)的次數(shù)分別為60，100，10和30，則：P={0.3, 0.5, 0.05, 0.15}使用的訪問(wèn)代價(jià)矩陣C相當(dāng)于：

根據(jù)代價(jià)矩陣 C和式(6)計(jì)算得出有最小的總代價(jià)的2列為S4和S5，各數(shù)據(jù)訪問(wèn)服務(wù)提供點(diǎn)對(duì)應(yīng)的存儲(chǔ)服務(wù)器如表中有下劃線的數(shù)字顯示。其訪問(wèn)總代價(jià)為990。如果不考慮訪問(wèn)頻率，采用式(3)將選擇S2和S5為存儲(chǔ)服務(wù)器，產(chǎn)生代價(jià)1 410。可以看出，結(jié)合訪問(wèn)頻率的總代價(jià)計(jì)算方法能夠更準(zhǔn)確反映實(shí)際的訪問(wèn)情況。

3 基于動(dòng)態(tài)代價(jià)矩陣的負(fù)載均衡機(jī)制

僅考慮訪問(wèn)代價(jià)，每次均選取總代價(jià)最低的存儲(chǔ)服務(wù)器來(lái)布置副本，使低代價(jià)存儲(chǔ)服務(wù)器被選擇的可能性大大增加，將造成各存儲(chǔ)服務(wù)器負(fù)載不均衡。

當(dāng)選中低代價(jià)存儲(chǔ)服務(wù)器布置某個(gè)副本后，其剩余容量減少，負(fù)載增加，可認(rèn)為其訪問(wèn)代價(jià)增加。若動(dòng)態(tài)更新代價(jià)矩陣，使負(fù)載增加的存儲(chǔ)服務(wù)器訪問(wèn)代價(jià)的值增加，那么，該服務(wù)器下一次被選中成為布置副本的服務(wù)器的可能性將減小，使整體的負(fù)載能夠達(dá)到均衡。

3.1 訪問(wèn)代價(jià)矩陣的動(dòng)態(tài)修正方法

由式(6)可知，根據(jù)副本被訪問(wèn)的情況，包括訪問(wèn)點(diǎn)的位置、訪問(wèn)次數(shù)、訪問(wèn)代價(jià)來(lái)決定2個(gè)副本的位置，使得副本將來(lái)被訪問(wèn)時(shí)有盡可能小的代價(jià)。當(dāng)副本存放到存儲(chǔ)服務(wù)器后，其負(fù)載增加。這時(shí)，可以適當(dāng)提高該存儲(chǔ)服務(wù)器對(duì)各訪問(wèn)點(diǎn)的訪問(wèn)代價(jià)。若副本存放在存儲(chǔ)服務(wù)器k和l上，那么代價(jià)矩陣中的相應(yīng)元素修改方法如下：

其中：i=k，l；l≤j≤m；α是一個(gè)代價(jià)增加參數(shù)。云存儲(chǔ)中數(shù)據(jù)副本數(shù)目一般都很大，當(dāng)存儲(chǔ)服務(wù)器上增加副本時(shí)，α取略大于0的小數(shù)即可。

3.2 基于負(fù)載均衡機(jī)制的副本分布算法

引入負(fù)載均衡機(jī)制的副本分布算法(RDLBLC)，每一個(gè)副本的分布位置可以由該算法來(lái)確定。作為補(bǔ)充，若某存儲(chǔ)服務(wù)器的負(fù)載超過(guò)了目前平均負(fù)載的 β倍，即便其訪問(wèn)代價(jià)最小，也不選擇該服務(wù)器作為當(dāng)前副本分布的結(jié)點(diǎn)，這樣可以保證當(dāng)代價(jià)矩陣增加太慢時(shí)，負(fù)載的相對(duì)均衡。β根據(jù)存儲(chǔ)服務(wù)器最大負(fù)載與平均負(fù)載的比例設(shè)定。

算法 1：引入負(fù)載均衡機(jī)制的副本分布算法(RDLBLC)

輸入代價(jià)矩陣Cm×n和數(shù)據(jù)訪問(wèn)頻率數(shù)組Pm

For i=1 to n

If Load(Si) ＜ β×AvgLoad(S1to Sn) //最大負(fù)載調(diào)節(jié)

For j=i+1 to n

使用式(6)計(jì)算最小代價(jià)fmin-cost

設(shè)相應(yīng)的Si和Sj為應(yīng)選擇的存儲(chǔ)服務(wù)器

End For

End If

End For

輸出Si，Sj//確定副本所在存儲(chǔ)服務(wù)器Si和Sj

For k=1 to m //負(fù)載均衡機(jī)制

使用式(7)修正和更新代價(jià)矩陣的第i列和第j列

End For

End RDLBLC

3.3 副本位置重新分布問(wèn)題

當(dāng)代價(jià)矩陣發(fā)生變化后，決定副本位置所依據(jù)的代價(jià)也發(fā)生了變化。但是，每次副本分布均選擇了低代價(jià)的存儲(chǔ)服務(wù)器，而且增加了對(duì)應(yīng)服務(wù)器的訪問(wèn)代價(jià)，更新了代價(jià)矩陣，使副本比較均勻地分布到各個(gè)服務(wù)器上。當(dāng)大批量的副本被布置到云存儲(chǔ)系統(tǒng)時(shí)，相對(duì)于初始狀態(tài)，各個(gè)存儲(chǔ)服務(wù)器訪問(wèn)代價(jià)的增長(zhǎng)也是均衡的，即整個(gè)代價(jià)矩陣各個(gè)元素的值在同比增加。因此，副本仍分布在與訪問(wèn)情況相對(duì)應(yīng)的低代價(jià)存儲(chǔ)服務(wù)器上，整個(gè)系統(tǒng)的總訪問(wèn)代價(jià)仍然較小。

4 實(shí)驗(yàn)

在 Pentium(R) Dual-Core CPU 2.60GHZ，2.0G Memory，Windows7，Java1.6環(huán)境下，對(duì)包括一系列數(shù)據(jù)存儲(chǔ)服務(wù)器和數(shù)據(jù)訪問(wèn)服務(wù)提供點(diǎn)的云存儲(chǔ)系統(tǒng)進(jìn)行了模擬。該模擬環(huán)境包括30個(gè)存儲(chǔ)服務(wù)器和100個(gè)服務(wù)提供點(diǎn)。每1對(duì)存儲(chǔ)服務(wù)器和服務(wù)提供點(diǎn)被賦予1個(gè)隨機(jī)數(shù)，該數(shù)值為數(shù)據(jù)訪問(wèn)代價(jià)，記在代價(jià)矩陣C中。為了便于討論，代價(jià)矩陣C各元素的初始值為[1, 100]之間的一個(gè)整數(shù)，表示在初始狀態(tài)，最大代價(jià)至多是最小代價(jià)的100倍。在此基礎(chǔ)上，模擬產(chǎn)生105個(gè)數(shù)據(jù)及其訪問(wèn)位置和頻率。

將隨機(jī)選擇副本位置的方法記為RS，結(jié)合訪問(wèn)頻率的最小代價(jià)選擇方法記為MFS，負(fù)載均衡的低代價(jià)選擇方法記為 LBS。經(jīng)過(guò) 50次模擬實(shí)驗(yàn)，求出各次數(shù)據(jù)訪問(wèn)總代價(jià)的平均值。上述3種方法產(chǎn)生的總代價(jià)平均值比較如圖2所示。

從圖2可見(jiàn)，負(fù)載均衡方法產(chǎn)生的數(shù)據(jù)訪問(wèn)總代價(jià)略高于結(jié)合訪問(wèn)頻率的選擇方法，但相對(duì)于隨機(jī)選擇方法，減少了一半以上的數(shù)據(jù)訪問(wèn)開(kāi)銷。

圖2 3種副本分布方法的系統(tǒng)訪問(wèn)總代價(jià)比較Fig.2 Total access costs of three replicates distribution methods

結(jié)合訪問(wèn)頻率選擇存儲(chǔ)服務(wù)器雖然有最小的應(yīng)用程序訪問(wèn)總代價(jià)，但負(fù)載不均衡。圖3所示為按照結(jié)合訪問(wèn)頻率的最小代價(jià)選擇存儲(chǔ)服務(wù)器后各個(gè)服務(wù)器的訪問(wèn)代價(jià)與其負(fù)載的對(duì)照?qǐng)D。

從圖3可以看出，總代價(jià)較小的存儲(chǔ)服務(wù)器其承擔(dān)的副本存儲(chǔ)任務(wù)較重。雖有一定的合理性，但負(fù)載分布過(guò)于不均衡。

根據(jù)上述分析和算法，令α=0.01，β=1.3，采用負(fù)載均衡機(jī)制后，各個(gè)存儲(chǔ)服務(wù)器訪問(wèn)總代價(jià)與負(fù)載對(duì)比情況如圖4所示。

將采用負(fù)載均衡機(jī)制時(shí)各個(gè)存儲(chǔ)服務(wù)器的訪問(wèn)總代價(jià)與其負(fù)載的比值如圖5所示。其中，縱坐標(biāo)為各比值與這些比值的平均值比較后的分布結(jié)果。

從圖4和5見(jiàn)：負(fù)載均衡方法使副本的分布比較平均，而且使副本的分布與存儲(chǔ)服務(wù)器的訪問(wèn)代價(jià)結(jié)合較好。

圖3 結(jié)合訪問(wèn)頻率的最小代價(jià)方法各服務(wù)器總代價(jià)與負(fù)載Fig.3 Total access cost and load of selection method with minimum cost integrating access frequency

圖5 各數(shù)據(jù)存儲(chǔ)服務(wù)器的總代價(jià)/負(fù)載的比值分布Fig.5 Values of total access cost/load of data storage servers

5 結(jié)論

(1) 將訪問(wèn)位置、訪問(wèn)頻率、訪問(wèn)代價(jià)結(jié)合在一起考慮，通過(guò)選取訪問(wèn)代價(jià)較小的存儲(chǔ)服務(wù)器，減少云存儲(chǔ)系統(tǒng)中應(yīng)用程序進(jìn)行數(shù)據(jù)訪問(wèn)的總代價(jià)，降低系統(tǒng)數(shù)據(jù)訪問(wèn)總開(kāi)銷。

(2) 充分考慮物聯(lián)網(wǎng)中應(yīng)用程序數(shù)據(jù)訪問(wèn)的移動(dòng)性和實(shí)時(shí)性，使副本分布與用戶訪問(wèn)情況相適應(yīng)，具有較低的訪問(wèn)代價(jià)，提高用戶數(shù)據(jù)訪問(wèn)效率。

(3) 采用基于動(dòng)態(tài)代價(jià)矩陣的負(fù)載均衡機(jī)制，使副本能夠均勻地分布到與訪問(wèn)情況相適應(yīng)的低代價(jià)存儲(chǔ)服務(wù)器上，避免僅考慮訪問(wèn)代價(jià)時(shí)副本分布較為集中的問(wèn)題，達(dá)到平衡各存儲(chǔ)服務(wù)器負(fù)載的效果，適應(yīng)數(shù)據(jù)量增加后訪問(wèn)代價(jià)的變化。

(4) 使用最少副本數(shù)目，最大限度地減少保持?jǐn)?shù)據(jù)一致性和更新的開(kāi)銷。

[1] Agrawal D, Abbadi A E, Antony S et al. Data management challenges in cloud computing infrastructures[C]//Proceedings of the 6th International Workshop on Databases in Networked Information Systems. Japan: Springer, 2010: 1-10.

[2] Chang F, Dean J, Ghemawat S, et al. Bigtable: a distributed storage system for structured data[J]. ACM Transactions on Computer Systems, 2006, 26(2): 205-218.

[3] Cooper B F, Ramakrishnan R, Srivastava U, et al. PNUTS:Yahoo!’s hosted data serving platform[J]. Proceedings of VLDB Endowment, 2008, 1(2): 1277-1288.

[4] DeCandia G, Hastorun D, Jampani M, et al. Dynamo: amazon’s highly available key-value store[C]// Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles.Washington, USA: ACM, 2007: 205-220.

[5] Rowstron A, Druschel P. Storage management and caching in PAST a large-scale, persistent peer-to-peer storage utility[C]//Proceedings of ACM Symposium on Operating Systems Principles. Banff, Alberta, Canada: ACM, 2001: 188-201.

[6] Kubiatowicz J, Bindel D, Chen Y. Oceanstore: an architecture for global-scale persistent storage[J]. Special Interest Group on Programming Languages Notices, 2000, 35(11): 190-201.

[7] Abadi D J. Data management in the cloud: limitations and opportunities[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2009, 32 (1): 3-12.

[8] Bonvin N, Papaioannou T G, Aberer K. Dynamic cost-efficient replication in data clouds[C]// Proceedings of the 1st Workshop on Automated Control for Datacenters and Clouds. Barcelona,Spain: ACM, 2009: 49-56.

[9] Bonvin N, Papaioannou T G, Aberer K. A self-organized,fault-tolerant and scalable replication scheme for cloud storage[C]// Proceedings of the 1st ACM Symposium on Cloud Computing. Indianapolis, Indiana, USA: ACM, 2010: 205-216.

[10] Chervenak A, Foster I, Kesselman C. The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets[J]. Journal of Network and Computer Applications, 2000, 23(3): 187-200.

[11] Ranganathan K, Foster I. Identifying dynamic replication strategies for a high performance data grid[C]//Proceedings of the International Grid Computing Workshop. Berlin: Springer Verlag, 2001: 75-86.

[12] 游新冬, 陳學(xué)耀, 朱川, 等. 數(shù)據(jù)網(wǎng)格中基于效益函數(shù)的副本管理策略[J]. 東北大學(xué)學(xué)報(bào): 自然科學(xué)版, 2007, 28(8):1122-1126.YOU Xin-dong, CHEN Xue-yao, ZHU Chuan, et al. Benefit function based replication strategies in data grids[J]. Journal of Northeastern University: Natural Science, 2007, 28(8):1122-1126.

[13] 易侃, 王汝傳. 分布式任務(wù)調(diào)度與副本復(fù)制集成策略研究[J].通信學(xué)報(bào), 2010, 31(9): 94-101.YI Kan, WANG Ru-chuan. Decentralized integration of task scheduling with replica placement strategy[J]. Journal of Communications, 2010, 31(9): 94-101.

[14] HU Zhi-gang, XIAO Peng. A novel resource co-allocation model with constraints to budget and deadline in computational grid[J].Journal of Central South University of Technology, 2009, 16(3):458-466.

[15] 付偉, 肖儂, 盧錫城. 個(gè)體 QoS 受限的數(shù)據(jù)網(wǎng)格副本管理與更新方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(8): 1408-1415.FU Wei, XIAO Nong, LU Xi-cheng. Replica placement and update mechanism for individual QoS-restricted requirement in data grids[J]. Journal of Computer Research and Development,2009, 46(8): 1408-1415.

[16] Grossman R L, Gu Y H, Sabala M, et al. Compute and storage clouds using wide area high performance networks[J]. Future Generation Computer Systems, 2009, 25(2): 179-183.