云存储环境中的数据布局策略研究

邓见光　潘晓衡　赵铁柱

(东莞理工学院　计算机学院，广东东莞　523808)



云存储环境中的数据布局策略研究

对云存储系统环境中的数据布局策略进行了论述与总结。首先讨论了云存储技术的起源以及云存储系统不同于传统集中式存储方法和现有网络存储技术的独特特征，然后讨论了面向云存储系统的数据文件布局策略；考虑到云存储系统对于系统可靠性、可用性以及可扩展性等性能指标具有更高要求，接下来对面向云存储系统的数据副本布局策略进行了论述。数据布局策略对于云存储系统的性能指标具有重要决定作用，全文工作将为未来研究高能效的商用云存储系统奠定基础。

云存储；数据布局；数据副本；可用性

近年来，随着信息技术的快速发展以及社会信息化程度的不断提高，数据逐渐取代硬件设施成为企业最为宝贵的资源。在数据规模快速膨胀的同时，数据对于现代企业的重要性也日益提升，这意味着用户在需要更大容量存储空间的同时，对存储性能也提出了更高的要求，他们希望存储系统具有更高的访问速率和响应效率、更好的可用性、可扩展性以及更高的安全性。

传统存储系统一般采用集中式的数据部署方案，当对同一数据文件发出密集的访问请求时，访问节点与存储系统之间将不可避免地出现数据传输瓶颈。本世纪初出现的各种网络存储技术，如DAS、NAS、SAN以及面向对象的存储技术等在一定程度上缓解了传统集中式存储方法所存在的问题，然而由于在可扩展性、并发性、网络负载等方面的不足，它们并不能很好地满足用户对于更大容量存储系统的数据存储需求。

近几年随着云计算的发展，云存储技术应运而生。与传统集中式存储方法以及现有的网络存储技术相比，云存储技术具有高可扩展性，它能够很好地满足不断膨胀的数据规模所带来的存储难题；同时云存储系统还具有高可用性，它可以根据不同的用户需求进行量身定制，在方便用户管理数据的同时为用户节约存储开支。尽管如此，云存储系统的广泛应用仍然面临着不少挑战。由于目前现有的大多数云存储系统均是基于企业已有的廉价存储设备改造部署的，云存储节点容易发生故障，使得系统的可靠性受损；此外，由于云存储系统需要存储和管理海量的数据资源，不合理的数据布局不仅会导致存储空间的浪费，而且还会影响到系统的整体响应效率和访问速率。为了满足云存储系统对于更多数据存储性能指标的要求，研究人员在面向云存储系统的数据布局策略方面进行了大量研究。

1　数据文件布局策略研究

数据布局策略是指为了达到一定的存储目标，通过某种映射机制将数据指派到合适的存储设备或存储节点中去，因此，存储系统的数据存储目标决定了其所应采用的数据布局策略。与传统集中式的数据存储方法以及现有的网络存储技术相比，云存储系统对于响应效率、访问速率、可扩展性、容错性、可用性、负载均衡以及系统的能耗水平等性能指标均有着更高要求，为了更好地满足云存储系统对于上述指标的要求，研究人员在数据文件布局策略方面进行了大量研究。

数据文件布局策略可分为静态策略和动态策略两大类，其中静态策略要求系统拥有关于数据存储请求特征的先验知识，以便提前进行部署决策；动态策略不需要上述先验知识的支持，其只需在数据的存储请求到达时，将它们动态地分配到相应的存储节点。Round-Robin是一种经典的静态数据文件布局策略[1]，其首先将数据文件条块化，然后再在多个存储节点上依次轮转放置条块。由于计算复杂度较低，Round-Robin策略已被应用到多个并行系统中；尽管如此，由于基于该策略所划分的数据条块尺寸大小固定不变，且没有任何的容错机制，这使得它的可用性受到了较大的限制。针对Round-Robin策略可用性不足且不能够动态扩展的问题，SLAS策略[2]对其进行了改进，该策略确保系统在增删存储节点之后仍能按照Round-Robin策略对数据进行布局。为了对数据进行重新布局，在实现SLAS策略时需要寻找一个合适的重排序窗口。

一致性Hash策略[3]具有较好的自适应性和公平性，其基于不同的Hash函数将存储空间和数据文件分别映射到单位环上，每个存储空间的映射节点代表一个虚拟的存储设备，数据最终被指派至单位环中与其自身的Hash结果最临近的节点所代表的存储设备上。文献[4]在一致性Hash的基础上提出了一种新的数据布局策略，该策略首先对存储设备进行聚类，然后根据类权重系数将每个存储设备类分别指派到相应的单位环子区间，落入相应子区间的数据即被分配到对应类的存储设备中，在每个存储设备类的内部则仍采用一致性Hash策略进行数据布局。该策略在保留了一致性Hash策略良好的公平性和自适应性的同时，提高了数据请求的定位效率，然而该方法的实现过程过于复杂，且空间开销较大。针对于此，文献[5]中提出了一种基于单位区间划分的数据布局方法，该方法具有较低的空间复杂度，但其数据定位效率和自适应性均劣于一致性Hash策略，不太适合于对于访问实时性要求较高的数据存储应用场景。

随着云存储系统的广泛应用，系统的响应性能和访问效率逐渐为用户所重视，同时出现了一系列以提高系统响应效率和访问速率为目标的启发式数据文件布局策略。SP策略[6]首先基于预期服务时间对数据文件进行降序排列，然后根据系统中各个磁盘的负载情况依次对各个文件分别进行存储，这种做法可以实现不同规模数据文件的分离存储，避免在数据访问请求过程中可能出现的不同大小文件之间的长时间等待现象；尽管如此，这一做法同时也带来了小文件的集中存储问题，容易导致部分磁盘访问过热。针对该问题，SOR策略[7]首先根据预期服务时间对数据文件进行升序排列，然后根据磁盘负载情况以轮转的方式依次存储数据文件，这一做法可以有效解决部分磁盘访问过热的问题。

2　数据副本布局策略研究

数据文件布局策略一般只考虑了数据只有单一副本的情况，由于目前的云存储系统大多基于企业已有的存储设施改造而成，容易发生故障，单点失效严重。在这种情况下，为了提高云存储系统的可靠性和可用性，可考虑在系统中为数据文件部署多个副本。

文献[8]基于Hash机制将数据副本分别部署在多个不同的存储设备中，进而实现了一种动态冗余的数据布局策略，该策略在数据存储规模发生变化时需要迁移的数据量较大，自适应性较差。针对该问题，文献[9]根据存储设备的权重系数将各个存储节点分别映射至各个单位子区间，进而构建了一种基于动态区间映射的数据布局策略，当数据的存储请求达到时，根据数据所落入的单位子区间来决定将当前数据指派至哪个存储节点，然后再将该数据的副本文件依次存入其他节点。在进行系统扩展时，该策略将拆分当前单位子区间为更小的子区间，并根据设备权重将新增的更小区间分配给新增设备，然后进行相应更小区间的数据迁移操作；当有存储节点退出系统时，则执行上述动作的反向操作。基于动态区间映射的数据布局策略具有很好的自适应性，但当系统规模较大时，其数据迁移操作的时空开销较大，可扩展性受限。

副本管理策略要综合考虑初始创建的副本数量、副本的动态增删管理、副本置换策略等多个因素[10]。目前面向云存储系统的副本管理策略大都比较简单，如HDFS默认副本数量为3，它们分别存储在当前节点、当前机架的另外一个节点以及其他机架的一个任意节点上，并基于Round-Robin策略在节点内部进行副本的存储操作[11]。HDFS所采用的副本管理策略忽略了系统负载状况以及不同磁盘之间的性能差异，不利于从整体上来提升和优化系统性能。为了尽可能地提高数据文件的可靠可用性，在Google文件系统中，其宿主节点总是倾向于选择使用率较低、最近一段时间内未创建任何副本，以及分散在多个机架的块服务器进行数据副本的放置操作[12]。爬山算法[13]则希望通过优化数据副本布局来提高系统的可用性，该算法首先对数据副本进行随机存储，然后根据文件的可用性情况不断地动态调整数据副本的存储位置，该算法公平性较差，且开销较大。

文献[14]首先根据所期望的系统可靠性计算需要创建的副本数量，然后再分别计算在每个候选存储节点上创建数据文件副本所可能带来的预期收益以及所可能增加的系统开销，最终选择净收益最高的候选节点来创建和放置数据副本，这种动态的副本策略总是倾向于创建过多的数据副本，造成系统资源的浪费。文献[15]根据访问热度来决定是否需要为当前文件创建副本以及创建多少副本，为了提高系统的响应效率和访问性能，它总是选择性能最高的超级节点来存放数据副本，该算法在副本数量的确定和副本放置位置的选择上灵活性较差。

由于云存储系统的本质是一种大规模的分布式系统，因此应用于其他分布式文件系统中的副本管理策略也可以为云存储系统所借鉴。文献[16]基于欧洲数据网格系统层次化的特点，将原始数据置于网格系统的顶层设备中，实现了六种不同的副本创建策略。文献[17]综合考虑数据文件的网络传输时间及其访问频率，将二者的乘积看作一个整体，进而实现了三种不同的副本放置策略。文献[18]将经济学中的一些研究成果用于热点文件的预测，并应用不同的策略分别进行副本的放置、置换及删除操作，最终实现了一种动态的基于对未来趋势进行预测的副本管理策略。文献[19]应用动态的方法进行副本的调整操作，在确保系统达到一定可用性的前提下尽可能地降低副本的管理开销，它忽略了系统可用性与数据一致性之间的平衡。针对于此，文献[20]周期性地扫描每个存储节点中的所有副本文件，当某个副本文件的读写操作达到一定比例时，即对相应的副本执行增删操作。文献[21]为每个数据节点分别维护一个存储记录，根据文件的读写情况动态修改其存储记录值，并在存储记录值达到特定阈值时对相应的副本文件执行增删操作，该策略需要为所有存储节点分别维护存储记录，系统开销较大；此外由于系统规模不断变化，其很难找个一个合适的存储记录阈值。

3　结语

目前在分布式系统的数据布局策略领域已经开展了大量的研究工作，并有不少成果发表，与一般的分布式系统相比，云存储系统规模庞大且动态变化，现有的数据布局策略大多是针对传统分布式系统环境而设计的，它们过于关注系统的负载均衡情况，而很少考虑系统的成本开销以及用户体验等指标，很难满足云存储系统的一些新的数据存储要求。作为一种商业服务模式，云存储系统在满足用户存储需求及各类服务质量要求的前提下，还应尽可能地降低其运营开销成本和能量消耗水平。本文对当前现有的面向云存储系统的数据文件及数据副本布局策略进行了详细的探讨，这将为我们未来研究更好的面向云存储系统的高能效数据布局策略奠定基础。

[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的数据布局算法[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]徐婧. 云存储环境下副本策略研究[D]. 合肥：中国科学技术大学，2011：2-11.

[11]黄翀民. 搜索引擎中分布式文件系统的研究与优化[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，Foster 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]侯孟书，王晓斌，卢显良，等. 一种新的动态副本管理机制[J]. 计算机科学，2006，33(9)：50-52.

[16]Ranganathan K，Foster 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网络中的副本管理策略[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—)，男，河南商水人，副研究员，博士，主要从事云计算、计算机网络研究。

邓见光潘晓衡赵铁柱

(东莞理工学院计算机学院，广东东莞523808)

TP302

A

1009-0312(2016)03-0045-04