鄧見光　潘曉衡　趙鐵柱

(東莞理工學院　計算機學院，廣東東莞　523808)

?

云存儲環(huán)境中的數(shù)據(jù)布局策略研究

對云存儲系統(tǒng)環(huán)境中的數(shù)據(jù)布局策略進行了論述與總結。首先討論了云存儲技術的起源以及云存儲系統(tǒng)不同于傳統(tǒng)集中式存儲方法和現(xiàn)有網(wǎng)絡存儲技術的獨特特征，然后討論了面向云存儲系統(tǒng)的數(shù)據(jù)文件布局策略；考慮到云存儲系統(tǒng)對于系統(tǒng)可靠性、可用性以及可擴展性等性能指標具有更高要求，接下來對面向云存儲系統(tǒng)的數(shù)據(jù)副本布局策略進行了論述。數(shù)據(jù)布局策略對于云存儲系統(tǒng)的性能指標具有重要決定作用，全文工作將為未來研究高能效的商用云存儲系統(tǒng)奠定基礎。

云存儲；數(shù)據(jù)布局；數(shù)據(jù)副本；可用性

近年來，隨著信息技術的快速發(fā)展以及社會信息化程度的不斷提高，數(shù)據(jù)逐漸取代硬件設施成為企業(yè)最為寶貴的資源。在數(shù)據(jù)規(guī)?？焖倥蛎浀耐瑫r，數(shù)據(jù)對于現(xiàn)代企業(yè)的重要性也日益提升，這意味著用戶在需要更大容量存儲空間的同時，對存儲性能也提出了更高的要求，他們希望存儲系統(tǒng)具有更高的訪問速率和響應效率、更好的可用性、可擴展性以及更高的安全性。

傳統(tǒng)存儲系統(tǒng)一般采用集中式的數(shù)據(jù)部署方案，當對同一數(shù)據(jù)文件發(fā)出密集的訪問請求時，訪問節(jié)點與存儲系統(tǒng)之間將不可避免地出現(xiàn)數(shù)據(jù)傳輸瓶頸。本世紀初出現(xiàn)的各種網(wǎng)絡存儲技術，如DAS、NAS、SAN以及面向對象的存儲技術等在一定程度上緩解了傳統(tǒng)集中式存儲方法所存在的問題，然而由于在可擴展性、并發(fā)性、網(wǎng)絡負載等方面的不足，它們并不能很好地滿足用戶對于更大容量存儲系統(tǒng)的數(shù)據(jù)存儲需求。

近幾年隨著云計算的發(fā)展，云存儲技術應運而生。與傳統(tǒng)集中式存儲方法以及現(xiàn)有的網(wǎng)絡存儲技術相比，云存儲技術具有高可擴展性，它能夠很好地滿足不斷膨脹的數(shù)據(jù)規(guī)模所帶來的存儲難題；同時云存儲系統(tǒng)還具有高可用性，它可以根據(jù)不同的用戶需求進行量身定制，在方便用戶管理數(shù)據(jù)的同時為用戶節(jié)約存儲開支。盡管如此，云存儲系統(tǒng)的廣泛應用仍然面臨著不少挑戰(zhàn)。由于目前現(xiàn)有的大多數(shù)云存儲系統(tǒng)均是基于企業(yè)已有的廉價存儲設備改造部署的，云存儲節(jié)點容易發(fā)生故障，使得系統(tǒng)的可靠性受損；此外，由于云存儲系統(tǒng)需要存儲和管理海量的數(shù)據(jù)資源，不合理的數(shù)據(jù)布局不僅會導致存儲空間的浪費，而且還會影響到系統(tǒng)的整體響應效率和訪問速率。為了滿足云存儲系統(tǒng)對于更多數(shù)據(jù)存儲性能指標的要求，研究人員在面向云存儲系統(tǒng)的數(shù)據(jù)布局策略方面進行了大量研究。

1　數(shù)據(jù)文件布局策略研究

數(shù)據(jù)布局策略是指為了達到一定的存儲目標，通過某種映射機制將數(shù)據(jù)指派到合適的存儲設備或存儲節(jié)點中去，因此，存儲系統(tǒng)的數(shù)據(jù)存儲目標決定了其所應采用的數(shù)據(jù)布局策略。與傳統(tǒng)集中式的數(shù)據(jù)存儲方法以及現(xiàn)有的網(wǎng)絡存儲技術相比，云存儲系統(tǒng)對于響應效率、訪問速率、可擴展性、容錯性、可用性、負載均衡以及系統(tǒng)的能耗水平等性能指標均有著更高要求，為了更好地滿足云存儲系統(tǒng)對于上述指標的要求，研究人員在數(shù)據(jù)文件布局策略方面進行了大量研究。

數(shù)據(jù)文件布局策略可分為靜態(tài)策略和動態(tài)策略兩大類，其中靜態(tài)策略要求系統(tǒng)擁有關于數(shù)據(jù)存儲請求特征的先驗知識，以便提前進行部署決策；動態(tài)策略不需要上述先驗知識的支持，其只需在數(shù)據(jù)的存儲請求到達時，將它們動態(tài)地分配到相應的存儲節(jié)點。Round-Robin是一種經(jīng)典的靜態(tài)數(shù)據(jù)文件布局策略[1]，其首先將數(shù)據(jù)文件條塊化，然后再在多個存儲節(jié)點上依次輪轉放置條塊。由于計算復雜度較低，Round-Robin策略已被應用到多個并行系統(tǒng)中；盡管如此，由于基于該策略所劃分的數(shù)據(jù)條塊尺寸大小固定不變，且沒有任何的容錯機制，這使得它的可用性受到了較大的限制。針對Round-Robin策略可用性不足且不能夠動態(tài)擴展的問題，SLAS策略[2]對其進行了改進，該策略確保系統(tǒng)在增刪存儲節(jié)點之后仍能按照Round-Robin策略對數(shù)據(jù)進行布局。為了對數(shù)據(jù)進行重新布局，在實現(xiàn)SLAS策略時需要尋找一個合適的重排序窗口。

一致性Hash策略[3]具有較好的自適應性和公平性，其基于不同的Hash函數(shù)將存儲空間和數(shù)據(jù)文件分別映射到單位環(huán)上，每個存儲空間的映射節(jié)點代表一個虛擬的存儲設備，數(shù)據(jù)最終被指派至單位環(huán)中與其自身的Hash結果最臨近的節(jié)點所代表的存儲設備上。文獻[4]在一致性Hash的基礎上提出了一種新的數(shù)據(jù)布局策略，該策略首先對存儲設備進行聚類，然后根據(jù)類權重系數(shù)將每個存儲設備類分別指派到相應的單位環(huán)子區(qū)間，落入相應子區(qū)間的數(shù)據(jù)即被分配到對應類的存儲設備中，在每個存儲設備類的內(nèi)部則仍采用一致性Hash策略進行數(shù)據(jù)布局。該策略在保留了一致性Hash策略良好的公平性和自適應性的同時，提高了數(shù)據(jù)請求的定位效率，然而該方法的實現(xiàn)過程過于復雜，且空間開銷較大。針對于此，文獻[5]中提出了一種基于單位區(qū)間劃分的數(shù)據(jù)布局方法，該方法具有較低的空間復雜度，但其數(shù)據(jù)定位效率和自適應性均劣于一致性Hash策略，不太適合于對于訪問實時性要求較高的數(shù)據(jù)存儲應用場景。

隨著云存儲系統(tǒng)的廣泛應用，系統(tǒng)的響應性能和訪問效率逐漸為用戶所重視，同時出現(xiàn)了一系列以提高系統(tǒng)響應效率和訪問速率為目標的啟發(fā)式數(shù)據(jù)文件布局策略。SP策略[6]首先基于預期服務時間對數(shù)據(jù)文件進行降序排列，然后根據(jù)系統(tǒng)中各個磁盤的負載情況依次對各個文件分別進行存儲，這種做法可以實現(xiàn)不同規(guī)模數(shù)據(jù)文件的分離存儲，避免在數(shù)據(jù)訪問請求過程中可能出現(xiàn)的不同大小文件之間的長時間等待現(xiàn)象；盡管如此，這一做法同時也帶來了小文件的集中存儲問題，容易導致部分磁盤訪問過熱。針對該問題，SOR策略[7]首先根據(jù)預期服務時間對數(shù)據(jù)文件進行升序排列，然后根據(jù)磁盤負載情況以輪轉的方式依次存儲數(shù)據(jù)文件，這一做法可以有效解決部分磁盤訪問過熱的問題。

2　數(shù)據(jù)副本布局策略研究

數(shù)據(jù)文件布局策略一般只考慮了數(shù)據(jù)只有單一副本的情況，由于目前的云存儲系統(tǒng)大多基于企業(yè)已有的存儲設施改造而成，容易發(fā)生故障，單點失效嚴重。在這種情況下，為了提高云存儲系統(tǒng)的可靠性和可用性，可考慮在系統(tǒng)中為數(shù)據(jù)文件部署多個副本。

文獻[8]基于Hash機制將數(shù)據(jù)副本分別部署在多個不同的存儲設備中，進而實現(xiàn)了一種動態(tài)冗余的數(shù)據(jù)布局策略，該策略在數(shù)據(jù)存儲規(guī)模發(fā)生變化時需要遷移的數(shù)據(jù)量較大，自適應性較差。針對該問題，文獻[9]根據(jù)存儲設備的權重系數(shù)將各個存儲節(jié)點分別映射至各個單位子區(qū)間，進而構建了一種基于動態(tài)區(qū)間映射的數(shù)據(jù)布局策略，當數(shù)據(jù)的存儲請求達到時，根據(jù)數(shù)據(jù)所落入的單位子區(qū)間來決定將當前數(shù)據(jù)指派至哪個存儲節(jié)點，然后再將該數(shù)據(jù)的副本文件依次存入其他節(jié)點。在進行系統(tǒng)擴展時，該策略將拆分當前單位子區(qū)間為更小的子區(qū)間，并根據(jù)設備權重將新增的更小區(qū)間分配給新增設備，然后進行相應更小區(qū)間的數(shù)據(jù)遷移操作；當有存儲節(jié)點退出系統(tǒng)時，則執(zhí)行上述動作的反向操作?；趧討B(tài)區(qū)間映射的數(shù)據(jù)布局策略具有很好的自適應性，但當系統(tǒng)規(guī)模較大時，其數(shù)據(jù)遷移操作的時空開銷較大，可擴展性受限。

副本管理策略要綜合考慮初始創(chuàng)建的副本數(shù)量、副本的動態(tài)增刪管理、副本置換策略等多個因素[10]。目前面向云存儲系統(tǒng)的副本管理策略大都比較簡單，如HDFS默認副本數(shù)量為3，它們分別存儲在當前節(jié)點、當前機架的另外一個節(jié)點以及其他機架的一個任意節(jié)點上，并基于Round-Robin策略在節(jié)點內(nèi)部進行副本的存儲操作[11]。HDFS所采用的副本管理策略忽略了系統(tǒng)負載狀況以及不同磁盤之間的性能差異，不利于從整體上來提升和優(yōu)化系統(tǒng)性能。為了盡可能地提高數(shù)據(jù)文件的可靠可用性，在Google文件系統(tǒng)中，其宿主節(jié)點總是傾向于選擇使用率較低、最近一段時間內(nèi)未創(chuàng)建任何副本，以及分散在多個機架的塊服務器進行數(shù)據(jù)副本的放置操作[12]。爬山算法[13]則希望通過優(yōu)化數(shù)據(jù)副本布局來提高系統(tǒng)的可用性，該算法首先對數(shù)據(jù)副本進行隨機存儲，然后根據(jù)文件的可用性情況不斷地動態(tài)調(diào)整數(shù)據(jù)副本的存儲位置，該算法公平性較差，且開銷較大。

文獻[14]首先根據(jù)所期望的系統(tǒng)可靠性計算需要創(chuàng)建的副本數(shù)量，然后再分別計算在每個候選存儲節(jié)點上創(chuàng)建數(shù)據(jù)文件副本所可能帶來的預期收益以及所可能增加的系統(tǒng)開銷，最終選擇凈收益最高的候選節(jié)點來創(chuàng)建和放置數(shù)據(jù)副本，這種動態(tài)的副本策略總是傾向于創(chuàng)建過多的數(shù)據(jù)副本，造成系統(tǒng)資源的浪費。文獻[15]根據(jù)訪問熱度來決定是否需要為當前文件創(chuàng)建副本以及創(chuàng)建多少副本，為了提高系統(tǒng)的響應效率和訪問性能，它總是選擇性能最高的超級節(jié)點來存放數(shù)據(jù)副本，該算法在副本數(shù)量的確定和副本放置位置的選擇上靈活性較差。

由于云存儲系統(tǒng)的本質是一種大規(guī)模的分布式系統(tǒng)，因此應用于其他分布式文件系統(tǒng)中的副本管理策略也可以為云存儲系統(tǒng)所借鑒。文獻[16]基于歐洲數(shù)據(jù)網(wǎng)格系統(tǒng)層次化的特點，將原始數(shù)據(jù)置于網(wǎng)格系統(tǒng)的頂層設備中，實現(xiàn)了六種不同的副本創(chuàng)建策略。文獻[17]綜合考慮數(shù)據(jù)文件的網(wǎng)絡傳輸時間及其訪問頻率，將二者的乘積看作一個整體，進而實現(xiàn)了三種不同的副本放置策略。文獻[18]將經(jīng)濟學中的一些研究成果用于熱點文件的預測，并應用不同的策略分別進行副本的放置、置換及刪除操作，最終實現(xiàn)了一種動態(tài)的基于對未來趨勢進行預測的副本管理策略。文獻[19]應用動態(tài)的方法進行副本的調(diào)整操作，在確保系統(tǒng)達到一定可用性的前提下盡可能地降低副本的管理開銷，它忽略了系統(tǒng)可用性與數(shù)據(jù)一致性之間的平衡。針對于此，文獻[20]周期性地掃描每個存儲節(jié)點中的所有副本文件，當某個副本文件的讀寫操作達到一定比例時，即對相應的副本執(zhí)行增刪操作。文獻[21]為每個數(shù)據(jù)節(jié)點分別維護一個存儲記錄，根據(jù)文件的讀寫情況動態(tài)修改其存儲記錄值，并在存儲記錄值達到特定閾值時對相應的副本文件執(zhí)行增刪操作，該策略需要為所有存儲節(jié)點分別維護存儲記錄，系統(tǒng)開銷較大；此外由于系統(tǒng)規(guī)模不斷變化，其很難找個一個合適的存儲記錄閾值。

3　結語

目前在分布式系統(tǒng)的數(shù)據(jù)布局策略領域已經(jīng)開展了大量的研究工作，并有不少成果發(fā)表，與一般的分布式系統(tǒng)相比，云存儲系統(tǒng)規(guī)模龐大且動態(tài)變化，現(xiàn)有的數(shù)據(jù)布局策略大多是針對傳統(tǒng)分布式系統(tǒng)環(huán)境而設計的，它們過于關注系統(tǒng)的負載均衡情況，而很少考慮系統(tǒng)的成本開銷以及用戶體驗等指標，很難滿足云存儲系統(tǒng)的一些新的數(shù)據(jù)存儲要求。作為一種商業(yè)服務模式，云存儲系統(tǒng)在滿足用戶存儲需求及各類服務質量要求的前提下，還應盡可能地降低其運營開銷成本和能量消耗水平。本文對當前現(xiàn)有的面向云存儲系統(tǒng)的數(shù)據(jù)文件及數(shù)據(jù)副本布局策略進行了詳細的探討，這將為我們未來研究更好的面向云存儲系統(tǒng)的高能效數(shù)據(jù)布局策略奠定基礎。

[1]Yuan X，Duan Z H. Fair round-robin: a low-complexity packetscheduler with proportional and worst-case fairness. IEEE Transactions on Computers[J]. 2009，58(3)：365-379.

[2]Zhang G Y，Shu J W，Xue W，et al. SLAS : an efficient approach to scaling round-robin striped volumes[J]. ACM Transactions on Storage，2007，3(1)：1227838.

[3]Karger D，Lehman E，Leighton T，et al. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. Proceedings of the 29th Annual ACM Symposium on Theory of Computin[C]. New York：ACM Press. 1997：654-663.

[4]陳濤，肖儂，劉芳，等. 基于聚類和一致Hash的數(shù)據(jù)布局算法[J]. 軟件學報，2010，21(12)：3175-3185.

[5]Brinkmann A，Salzwedel K，Scheideler C. Efficient，distributed data placement strategies for storage area networks. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures[C]. New York：ACM. 2000：119-128.

[6]Lee L W，Scheuermann P，Vingralek R. File assignment in parallel I/O systems with minimal variance of service time[J]. IEEE Transactions on Computers，2000，49(2)：127-140.

[7]Xie T，Sun Y. A file assignment strategy independent of workload characteristic assumptions[J]. ACM Transactions on Storage，2009，5(3)：1-24.

[8]Brinkmann A，Effert S，Meyer F，et al. Dynamic and redundant data placement. Proceedings of the 27th International Conference on Distributed Computing Systems[C]. Piscataway，USA：Institute of Electrical and Electronics Engineers Inc. 2007：4268184.

[9]Liu Z. Efficient，balanced data placement algorithm in scalable storage clusters[J]. Journal of Communication and Computer，2007，4(7)：8-17.

[10]徐婧. 云存儲環(huán)境下副本策略研究[D]. 合肥：中國科學技術大學，2011：2-11.

[11]黃翀民. 搜索引擎中分布式文件系統(tǒng)的研究與優(yōu)化[D]. 廣州：華南理工大學，2010：4-9.

[12]Yang Jade. From google file system to omega：a decade of advancement in big data management at google. Proceedings of the IEEE First International Conference on Big Data Computing Service and Applications，Big Data Service[C]. Piscataway，USA：Institute of Electrical and Electronics Engineers Inc., 2015：249-255.

[13]Douceur J R，Wattenhofer R P. Competitive hill-climbing strategies for replica placement in a distributed file system. Proceedings of the 15th International Conference on Distributed Computin[C]. Lisbon，Portugal：Springer Verlag. 2001：48-62.

[14]Ranganathan K，Iamnitchi A，F(xiàn)oster I. Improving data availability through dynamic model-driven replication in large peer-to-peer communities. Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid[C]. Washington：IEEE Computer Society. 2002：376-381.

[15]侯孟書，王曉斌，盧顯良，等. 一種新的動態(tài)副本管理機制[J]. 計算機科學，2006，33(9)：50-52.

[16]Ranganathan K，F(xiàn)oster I. Design and evaluation of dynamic replication strategies for a high performance data grid. Proceedings of Computing in High Energy and Nuclear Physics Conference[C]. Washington：IEEE Computer Society, 2001：712-715.

[17]Rahman R M，Barker K，Alhajj R. Replica placement in data grid：considering utility and risk. Proceedings of the International Conference on Information Technology：Coding and Computing[C]. Las Vegas：IEEE Computer Society, 2005：354-359.

[18]陳宇，董健全. 非結構化P2P網(wǎng)絡中的副本管理策略[J]. 計算機工程，2008，34(18)：108-110.

[19]Yu H F，Amin V. The costs and limits of availability for replicated services[J]. ACM Transactions on Computer Systems，2006，24(1)：70-113.

[20]Maurer M，Emeakaroha V C，Brandic I，et al. Cost-benefit analysis of an SLA mapping approach for defining standardized cloud computing goods[J]. Future Generation Computer Systems，2012，28(1)：39-47.

[21]Lund C，Reingold N，Westbrook J，et al. Competitive on-line algorithms for distributed data management[J]. SIAM Journal on Computing，1998，28(3)：1086-1111.

The Data Layout Strategy in Cloud Storage Environment

DENG JianguangPAN XiaohengZHAO Tiezhu

(Computer College, Dongguan University of Technology, Dongguan 523808, China)

The paper discusses and summarizes the data layout strategies in cloud storage system environment, introducing the origin of the cloud storage technology and its unique characteristics which differed greatly from the traditional centralized storage method and the current network storage technology, as well as the data file layout strategies in cloud storage system. It also expounds the data replica layout strategy in cloud storage system, in view of higher requirements in the cloud storage system for system reliability, availability and scalability performance. It is obvious that the data layout strategy plays an importance role in the performance of cloud storage system, so the work of this paper will be a guideline of our future study on the highly energy-efficient, commercial cloud storage system.

cloud storage; data layout; data replica; availability

2016-03-30

國家自然科學基金(61402106)；廣東省自然科學基金(2014A030313632)。

鄧見光(1981—)，男，河南商水人，副研究員，博士，主要從事云計算、計算機網(wǎng)絡研究。

鄧見光潘曉衡趙鐵柱

(東莞理工學院計算機學院，廣東東莞523808)

TP302

A

1009-0312(2016)03-0045-04