物聯網環境下負載均衡的低代價云存儲數據副本分布

何典 ，吳敏，胡春華

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

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

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

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

1.1 副本數目與類型

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

1.1.1 副本數目

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

1.1.2 副本類型

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

1.2 訪問代價描述

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

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

圖1 云存儲數據訪問模型Fig.1 Data access model in cloud storage

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

2 低訪問代價副本分布

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

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

2.1 低代價副本分布方法

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

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

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

2.2 結合訪問頻率

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

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

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

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

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

2.3 考慮訪問頻率的合理性

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

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

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

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

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

3 基于動態代價矩陣的負載均衡機制

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

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

3.1 訪問代價矩陣的動態修正方法

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

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

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

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

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

輸入代價矩陣Cm×n和數據訪問頻率數組Pm

For i=1 to n

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

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 副本位置重新分布問題

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

4 實驗

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

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

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

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

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

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

根據上述分析和算法，令α=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 各數據存儲服務器的總代價/負載的比值分布Fig.5 Values of total access cost/load of data storage servers

5 結論

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

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

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

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

[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] 游新冬, 陳學耀, 朱川, 等. 數據網格中基于效益函數的副本管理策略[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 受限的數據網格副本管理與更新方法[J]. 計算機研究與發展, 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.