一种适合移动云节点的可靠存储模型

姜春茂，王启明，申 倩，许美玉(. 哈尔滨师范大学计算机科学技术与信息工程学院 哈尔滨 5005；. 平顶山学院计算机科学与技术学院 河南 平顶山 467000)



一种适合移动云节点的可靠存储模型

姜春茂1，王启明2，申 倩1，许美玉1
(1. 哈尔滨师范大学计算机科学技术与信息工程学院 哈尔滨 150025；2. 平顶山学院计算机科学与技术学院 河南 平顶山 467000)

【摘要】多维异构的情况下，完全副本的存储方式网络传输负担重，单个节点的能耗消耗大，可用性低。针对于此，该文提出了两种适合移动节点的存储模型：1) 交叉存储策略；2) 比例存储策略。模型中移动节点不再存储数据的完全副本，同时根据移动节点的带宽差异性的特点，将存储和并行传输统筹考虑，降低速度缓慢节点对于整体性能的影响。实验表明，该文并行传输模型相比传统的传输算法，既聚集了较大的带宽，也节省了存储空间。

关 键 词云计算; 交叉存储; 移动节点; 并行传输

A Reliable Storage Model and Transmission Mechanism for the Mobile Cloud Node

JIANG Chun-mao1, WANG Qi-ming2, SHEN Qian1, and XU Mei-yu1
(1. School of Computer Science Technology and Information Engineering, Harbin Normal University Harbin 150025; 2. School of Computer Science and Technology, Pingdingshan University Pingdingshan Henan 467000)

Abstract In the case of multi-dimensional heterogeneous networks, the full copy of storage data caused a heavy burden on the network and a single node's huge energy consumption, thus, the availability of system is very low. In view of this, the paper proposes two storage models for mobile nodes: the cross storage strategy and the storage strategy according to the proportion. In this model, the mobile node no longer stores the full copy of the data, and at the same time, according to the characteristics of the bandwidth of mobile nodes, the storage and parallel transmission are considered together to reduce the impact of the slow speed of nodes on the performance of the whole. Experiments show that the proposed parallel transmission model is more efficient than the traditional transmission algorithm in both bandwidth utility and storage space saving.

Key words cloud computing; cross storage; mobile node; parallel transmission

云存储[1-3]是利用云平台实现分布式存储的一种方式，通过将网络中大量的异构存储设备协同工作，对外提供数据存储和服务业务访问功能。现如今云存储得到了充分的发展，如google推出的google drive、dropbox、百度云盘等。

实施安全可靠的数据存储是云存储所面临的挑战。提高数据的冗余度可以提高数据存储的可靠性，同时进一步提高用户的服务体验。然而，数据的大量冗余无形中加大了云服务提供商的服务成本，同时也造成了网络的负载压力。基于此，分块存储模型被提出。其中，作为典型的分块存储范例，hadoop 和google的GFS[4-5]无疑是最成功的典型实例。

GFS的副本容错方式是至少采用3个副本存储。在副本的分布上考虑拓扑结构、机架分布、磁盘使用等因素。如果出现副本丢失情况，master服务器自动复制副本给其他服务器，使得副本个数得以保持。该方法可靠、有效，缺点在于磁盘利用率不高。

利用移动节点构造云存储方式，不仅要考虑节点的异构性和存储空间的大小、带宽、功耗等，还要考虑物理连接方式。就移动节点而言，如何以低代价的方式来实现高可靠的存储方式(提供足够多的冗余)进而构建分布式的移动云服务节点是一个挑战性的课题。文献[6-7]提出了一种基于无线环境下的移动设备合作存储方式，给出了数据重要性的概念，重要的数据要最大化可用率。系统采用分块存储模式。但是并没有考虑移动节点的传输速度缓慢问题。

公平性是移动节点另一个要考虑的问题[8-9]，结构化的数据存储方式以相同的概率存储数据，有利于节点的负载平衡，但并没有考虑节点的异构性，由于移动节点的存储空间有限，完全多副本的方法很难被直接使用。完整副本的存储方式一旦出现节点不在线或能耗耗尽等情况，则只从一个完整副本的节点进行数据传输恢复。考虑网络线路故障、带宽的有限，恢复速度极慢，若数据量增加，恢复过程的失效情况也会时常发生。因而，降低数据的整体失效概率是移动节点中需要解决的重要问题[10]。

1 数据划分模型

1.1 数据划分方法

定义 1 数据划分 假定M表示数据总体存储量，分布到k个节点，每个节点上存储的数据份数为x(x∈I)，等量分割数据为kx份。则数据量表示为:

定义 2 本地化数据，将定义1中的kx份数据平均分发到1−k号节点上，则每个节点上存储有x份数据，这些数据成为节点的本地化数据。存储在节点i的本地数据用Li表示，1≤i≤k。

定义 3 CS(cross storage)存储模型 按照定义1的规则分割数据，节点i存储了x份数据，同时节点(i+1) mod k上存储同样的x份数据。有：

式中，Oj表示交叉存储在其他节点的数据。

定理 1 CS数据存储模型的数据存储量为2M。

证明：据CS模型的定义可得：

证毕。

定义 4 空间利用率U由定义1可得：

文件名称为f，S表示其大小，f存储的k个节点分别用N1～Nk表示。

1) 文件分块

K等分f为fi(1≤i≤k)，其大小为Si，Si=S/k。x等分表示每份子文件，其大小表示为分块示意图如图1所示。

数据块存储示意图如图2所示，下层为步骤①分配的数据，称为LND数据；上层为步骤②分配的数据，称为OND数据。

明显可得，LNDsize=ONDsize，其中LNDsize表示LND的数据量，ONDsize表示OND的数据量，总量为2S。当任一节点不可用，可以从其余节点的数据集求并来获得整个数据。其中，k等分的每块原始数据用Bi表示，i∈(1, k )。

图2　数据块存储示意图

1.2 比例存储模型

文中比例分割如图3所示，首先将完整的数据文件file按照δ和1−δ(0<δ<1)的比例分成两个部分。

图3　文件比例分割

1) 对于文件的δ部分直接等分为i份，存储于对应的节点i；

2) 1−δ部分采用CS模型存储进行存储。

文件的整体存储策略如图4所示，图中Ni表示节点号。

图4　文件的比例模型存储策略示例

从数据占用的空间比较，CS存储模型使用k个节点存储数据，与完全的副本存储之比为U=2/k。而RS存储模型，空间占用比表示为：

式中，a表示δ部分存储的数比例，且0

定义 5 本地数据剩余量Si令节点Ni的平均带宽为Vi，在并行数据获取中，从移动节点Ni下载的理想数据量与本地数据LNDi的差值定义为本地数据剩余量Si，即：

分析：Si表明节点的负载程度。Si=0基本表明负载均衡；Si>0表明节点i传输速度快，可以承担Si<0的节点的传输任务。

2 基于CS存储方案的负载均衡算法

对于CS模型中的k个节点按照从大到小的次序排序，然后依次处理。从Ni节点传输LNDi+Si，考察LNDi中未被标记的数据量LNDWi，如果大于等于LNDi+Si，则直接从LNDWi中取出LNDi+Si块，反之取出所有LNDWi，并从节点的ONDi中取出LNDi+Si−L份。

优化过程：令实际下载块数为B，理想下载块数为A。从B−A最大的节点开始，如果B−A节点和其前后两个节点不能直接优化，检测是否存在优化环路(OPC)，即Ni节点的LND数据如果没有被后一节点的OND完全下载，或Ni节点的OND数据如果没有被前一节点的LND完全下载，则存在优化环路。每优化一次重新计算B−A值。

目标：节点均衡负载，优化调度，使Si=0。输入：K、x、Vi以及符合存储模型的数据。输出：给出从各节点下载数据的调度方案。算法描述：

Compute(Si)

Sort(Si)

For(i∈sort(Si))

If LNDi+Si≤LNDWiGet (LNDi+Si) blocks

Else

Get (LNDWi) blocks

Get (LNDi+Si−LNDWi) blocks from

ONDiand mark them

OPT：

While OPC exists

Sort(compute(B−A))

BNx=MAX(B−A),BNx.pre=BNy,BNx.next=BNz.

在(BNy、BNz)中查询B−A，取最小的先优化满足：优化后BNx和BNy或BNx和BNz的下载时间不会延长(判断B−A/V)

将BNx的LND数据已经标记下载的减少m块，增加BNz的OND数据为下载的m块。

3 实验结果和性能分析

3.1 实验说明

实验目的主要包括: 1) 验证CS存储模型与其他传输模型的速度比较；2) δ变化对传输的影响；3) 数据块大小对于传输的影响。

实验使用的原型系统主要包括6个功能模块，分别是数据的上传单元，云计算中心单元，数据分发单元、G-Peer组存储单元、数据下载单元、数据恢复单元，如图5所示。

命名PTIM(parallel transmission based oninterleave model)表示基于CS模型的并行传输算法，PTRM(parallel transmission based on ratio model)表示比例模型传输算法，CLBS(conservative load balancing strategy)表示保守调度算法，DAS(dynamic adjustment strategy)为文献[11]提出的算法。

在教育网、移动网络、联通宽带的3种网络中选取一些节点作为实验数据的部署节点。具体如下：

使用联通3G作为移动模拟节点，为数据需求方。数据部署节点使用教育网内电脑两台，移动网内计算机一台。数据的大小为960 M。为了保证保证物理条件的一致性，对于PTRM、CLBA和DAS使用相同的网络接入与服务节点。根据最短下载时间的定义，各种并行传输算法所能达到的最小下载时间不能超过MDT。

图5　实验使用的系统组成

3.2 PTIM性能比较

令数据块大小Bi=40，通过开源文件分割工具将数据文件分割处理后成为480块数据，每块2 M。两种存储模型的分割方法相同。 为了保证数据的精确性，进行了多次、多时间点、重复性的实验，如图6所示。

实验结果分析：多项式曲线拟合的结果显示，MLTT曲线位于最下方，PTRM和CLBS两条曲线基本吻合，走势相同，中间存在交线，表明二者性能相仿，而DAS拟合曲线处于二者下方，略微具有一定优势。3种曲线都以MLTT曲线为下限。

图6　传输时间多项式曲线拟合

3.3 PTIM中Bi影响分析

测试时间为北京时间上午8:00～11:00，数据如表1所示。

表1　Bi与metadata列表

表中，metadata表示Bi取不数值时相应的最小文件块大小，Bi=10时，性能最差，基本等同于基于历史的调度策略。随着Bi的增加，传输的时间也随之逐步下降并且在Bi∈[40,50,60,70]的时候逐步趋稳，表明Bi的大小在一定程度上对算法的影响逐步趋于稳定。

而在实验A中，发现在Bi取40时，算法性能与以往的保守调度算法是大致相同的。

3.4 PTRM性能比较

考察比例系数δ对不同算法的影响程度。主要包括：1) 在特定的网络情况下，确定的δ对PTRM、CLBS和DAS在传输性能上影响的差异；2) 改变δ时，网络状态改变时PTRM性能与CLBS和DAS的差异。

首先，取δ=0.3，分别取8:00～10:00，14:00～15:00，17:00～19:00这3个时间段。分别在3天固定观测3种策略，在不同时段进行测试，为了避免网络动态性影响，每种策略独立观测3次。

观测到的PTRM数值如表2所示，CLBS与DAS结果采用之前实验中的数据。

表2　PTRM观测结果

数据显示，DAS算法略有一定优势，其他的3种算法性能近似。

其次，令δ={0.1, 0.2, 0.3, 0.4, 0.5}，进行5天实验。为确保实验结果的准确，固定20:00～21:00观测PTRM在δ取不同数值时的性能，如图7所示。

在δ={0.1,0.2,0.3}时算法性能比较接近，从上述实验中可知，在δ=0.3时PTRM与其他两种算法的性能都比较接近，效果较好；而在δ={0.4,0.5}时PTRM性能明显降低。

通过最大带宽和最小带宽比的计算发现，在δ为别为0.4和0.5的时候，其比值分别为4.6和4.5，均比理论值3和4大。因此，从实际的情形看，对于带宽比较大的情况，应该取较小的δ。

图7　δ变化时的传输时间

3.5 实验总结

实验1)表明本文提出的PTIM算法与CLBS和DAS在存储空间大大节约的情况下达到了相似的性能。

实验2)表明，PTIM算法性能受Bi的影响明显，但是在metadata的大小达到2 M以内时，继续增大Bi基本不会对算法产生影响。

实验3)表明本文提出的PTRM算法，在给定的网络环境中当δ<0.3时算法的性能与CLBS和DAS相近。在带宽差异较大，取δ<0.3时PTRM可以适应较差的网络环境，而且可以节省大量的存储空间。

4 结 束 语

为了节省存储空间，同时保证数据量只增加两倍的情况下，本文提出了CS存储策略，与此同时，在数据需求节点在一定程度上增多的时候依然可以满足下载速度的需求。

考虑到以往的分块存储策略割裂传输和存储之间的关系导致较低的带宽节点的瓶颈效应的问题，本文提出的并行传输策略PTIM和PTRM，将存储和传输统筹考虑，提出了负载均衡的调度算法。在有效解决了移动节点存储开销过大的同时依旧获得了较好的性能。

参 考 文 献

[1] ZENG Wen-ying, ZHAO Yue-long, OU Kai-ri, et al. Research on cloud storage architecture and key technologies[C]//Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human. New York: ACM, 2009.

[2] PAMIES-JUAREZ L, GARCIA L P, ARTIGAS S M. Availability and redundancy in harmony: Measuring retrieval times in p2p storage systems[C]//IEEE Tenth International Conference on Peer-to-Peer Computing(P2P). Delft Netherlands: IEEE, 2010.

[3] LIU Shuo, REN Shao-lei, QUAN Gang, et al. Profit aware load balancing for distributed cloud data centers[C]//27th International Symposium on Parallel & Distributed Processing (IPDPS). Boston: IEEE, 2013: 126-135.

[4] 陈康, 郑纬民. 云计算: 系统实例与研究现状[J]. 软件学报, 2009, 20(5): 1337-1348. CHEN Kang, ZHENG Wei-ming. Cloud computing: System instances and current research[J]. Journal of Software, 2009, 20(5): 1337-1348.

[5] 冯国富, 李文中, 张金城, 等. 无结构覆盖网络中面向搜索范围最小化的副本分布[J]. 计算机学报, 2011, 34(4): 628-635. FENG Guo-fu, LI Wen-zhong, ZHANG Jin-cheng, et al. Replica distribution for search size minimization in unstructured overlay[J]. Chinese Journal Of Computers, 2011, 34(4): 628-635.

[6] PRABAVATHY B, PRIYA K, BABU C. A load balancing algorithm for private cloud storage[C]//Fourth International Conference on Computing, Communications and Networking Technologies. Tiruchengode: IEEE, 2013:1-6.

[7] PARVEZ N, WILLIAMSON C, MAHANTI A, et al. Analysis of bittorrent-like protocols for on-demand stored media streaming[C]//Proceedings of ACM Sigmetrics. Annapolis: ACM, 2008: 301-312.

[8] XIE T, QIN X. Security-aware resource allocation for real-time parallel jobs on homogeneous and heterogeneous clusters[J]. IEEE Trans on Parallel and Distributed Systems, 2008, 19(5): 692-697.

[9] CHRISTIAN C, KEIDAR I, SHRAER A. Trusting the cloud[J]. Newsletter ACM Sigact News, 2009, 40(2): 81-86.

[10] ZHANG Hong, LI Bo, JIANG Hong-bo, et al. A framework for truthful online auctions in cloud computing with heterogeneous user demands[C]//2013 Proceedings IEEE Conference on Infocom. Turin: IEEE, 2013: 190-201.

[11] JUN Feng, MARTY H. Eliminating replica selection-using multiple replicas to accelerate data transfer on grids[C]// Proceedings of the Tenth International Conference on Parallel and Distributed Systems. Washinton: IEEE, 2004.

[12] PATEL K, ANNAVARAM M, PEDRAM M. Generalized network flow-based resource allocation for hosting centers[J]. IEEE Transactions on Computers, 2013, 62(9): 1772-1785.

编 辑 叶 芳

作者简介：姜春茂(1972 − )，男，博士，教授，主要从事移动P2P、云计算、嵌入式计算方面的研究.

基金项目：国家自然科学基金(61073042); 黑龙江省教育厅项目(12531189); 中国博士后基金面上项目(2014M561330)

收稿日期：2013 − 07 − 21；修回日期：2015 − 11 − 10

中图分类号

文献标志码A

doi:10.3969/j.issn.1001-0548.2016.01.019