物聯(lián)網(wǎng)環(huán)境下負載均衡的低代價云存儲數(shù)據(jù)副本分布

何典 ，吳敏，胡春華

(1. 中南大學 信息科學與工程學院，湖南 長沙，410083；2. 湖南商學院 計算機與電子工程學院，湖南 長沙，410205)

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

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

1 云存儲副本分布及訪問代價

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

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

1.1.1 副本數(shù)目

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

1.1.2 副本類型

副本分為臨時副本、永久副本和長期副本[16]：臨時副本用來提高訪問性能(位于存儲服務器上)，永久副本用來備份數(shù)據(jù)，長期副本用來對副本歸檔。假設副本總數(shù)為3，本文為同一數(shù)據(jù)定義2個臨時副本和1個永久副本，這樣既可以提高數(shù)據(jù)訪問效率，又能夠對數(shù)據(jù)進行備份。本文中，訪問代價是指對臨時副本的訪問代價，副本位置是指存儲2個臨時副本的云存儲服務器的位置。

1.2 訪問代價描述

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

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

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

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

2 低訪問代價副本分布

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

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

2.1 低代價副本分布方法

找到最低訪問代價的2個存儲服務器來布置數(shù)據(jù)r的副本，相當于在矩陣C中找出m個元素，這m個元素僅屬于矩陣的某2列，并且元素之和最小。應用程序沒有訪問的服務提供點不參與計算。使用集合 V記錄應用程序對服務提供點訪問的情況：

其中：若vi=0，則表示應用程序未在服務提供點i訪問過數(shù)據(jù)r；若vi=1，則表示應用程序在服務提供點i訪問過數(shù)據(jù) r。未訪問過的結點不需要參與總代價計算。由于僅考慮整個拓撲結構的一部分，減少了計算的復雜度，計算結果與訪問情況相符合。數(shù)據(jù)r最低代價計算公式為：

由式(3)計算得到最小訪問代價fmin-cost，與之對應的i和j表示2個副本應分別存放在存儲服務器Si和Sj上。

2.2 結合訪問頻率

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

使用集合P記錄應用程序對某數(shù)據(jù)r的訪問頻率，如式(4)所示：

其中：pi表示應用程序在服務提供點i對數(shù)據(jù)r訪問的頻率，即在該服務提供點訪問該數(shù)據(jù)的次數(shù)占所有服務提供點對該數(shù)據(jù)訪問總次數(shù)的比例。pi=0表示在服務提供點i未訪問過該數(shù)據(jù)r。

將應用程序在服務提供點i訪問某數(shù)據(jù)的次數(shù)記為ti，則pi計算方法為：

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

2.3 考慮訪問頻率的合理性

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

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

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

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

根據(jù)代價矩陣 C和式(6)計算得出有最小的總代價的2列為S4和S5，各數(shù)據(jù)訪問服務提供點對應的存儲服務器如表中有下劃線的數(shù)字顯示。其訪問總代價為990。如果不考慮訪問頻率，采用式(3)將選擇S2和S5為存儲服務器，產生代價1 410?？梢钥闯觯Y合訪問頻率的總代價計算方法能夠更準確反映實際的訪問情況。

3 基于動態(tài)代價矩陣的負載均衡機制

僅考慮訪問代價，每次均選取總代價最低的存儲服務器來布置副本，使低代價存儲服務器被選擇的可能性大大增加，將造成各存儲服務器負載不均衡。

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

3.1 訪問代價矩陣的動態(tài)修正方法

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

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

3.2 基于負載均衡機制的副本分布算法

引入負載均衡機制的副本分布算法(RDLBLC)，每一個副本的分布位置可以由該算法來確定。作為補充，若某存儲服務器的負載超過了目前平均負載的 β倍，即便其訪問代價最小，也不選擇該服務器作為當前副本分布的結點，這樣可以保證當代價矩陣增加太慢時，負載的相對均衡。β根據(jù)存儲服務器最大負載與平均負載的比例設定。

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

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

For i=1 to n

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

For j=i+1 to n

使用式(6)計算最小代價fmin-cost

設相應的Si和Sj為應選擇的存儲服務器

End For

End If

End For

輸出Si，Sj//確定副本所在存儲服務器Si和Sj

For k=1 to m //負載均衡機制

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

End For

End RDLBLC

3.3 副本位置重新分布問題

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

4 實驗

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

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

從圖2可見，負載均衡方法產生的數(shù)據(jù)訪問總代價略高于結合訪問頻率的選擇方法，但相對于隨機選擇方法，減少了一半以上的數(shù)據(jù)訪問開銷。

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

結合訪問頻率選擇存儲服務器雖然有最小的應用程序訪問總代價，但負載不均衡。圖3所示為按照結合訪問頻率的最小代價選擇存儲服務器后各個服務器的訪問代價與其負載的對照圖。

從圖3可以看出，總代價較小的存儲服務器其承擔的副本存儲任務較重。雖有一定的合理性，但負載分布過于不均衡。

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

將采用負載均衡機制時各個存儲服務器的訪問總代價與其負載的比值如圖5所示。其中，縱坐標為各比值與這些比值的平均值比較后的分布結果。

從圖4和5見：負載均衡方法使副本的分布比較平均，而且使副本的分布與存儲服務器的訪問代價結合較好。

圖3 結合訪問頻率的最小代價方法各服務器總代價與負載Fig.3 Total access cost and load of selection method with minimum cost integrating access frequency

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

5 結論

(1) 將訪問位置、訪問頻率、訪問代價結合在一起考慮，通過選取訪問代價較小的存儲服務器，減少云存儲系統(tǒng)中應用程序進行數(shù)據(jù)訪問的總代價，降低系統(tǒng)數(shù)據(jù)訪問總開銷。

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

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

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

[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] 游新冬, 陳學耀, 朱川, 等. 數(shù)據(jù)網(wǎng)格中基于效益函數(shù)的副本管理策略[J]. 東北大學學報: 自然科學版, 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] 易侃, 王汝傳. 分布式任務調度與副本復制集成策略研究[J].通信學報, 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] 付偉, 肖儂, 盧錫城. 個體 QoS 受限的數(shù)據(jù)網(wǎng)格副本管理與更新方法[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.