2016, Vol. 45
[PDF全文]
2. 平顶山学院计算机科学与技术学院 河南 平顶山 467000
2. School of Computer Science and Technology, Pingdingshan University Pingdingshan Henan 467000
云存储[1, 2, 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份。则数据量表示为:
| $m=\frac{M}{kx}$ | (1) |
定义 2 本地化数据，将定义1中的kx份数据平均分发到1-k号节点上，则每个节点上存储有x份数据，这些数据成为节点的本地化数据。存储在节点i的本地数据用Li表示，1≤i≤k。
定义 3 CS(cross storage)存储模型 按照定义1的规则分割数据，节点i存储了x份数据，同时节点(i+1) mod k上存储同样的x份数据。有：
| $\begin{align} & {{A}_{j}}={{L}_{j}}\bigcup {{O}_{j}}={{L}_{j}}\bigcup {{L}_{i-1}} \\ & 2\le i\le k+1j=i\bmod k \\ \end{align}$ | (2) |
式中，Oj表示交叉存储在其他节点的数据。
定理 1 CS数据存储模型的数据存储量为2M。
证明：据CS模型的定义可得：
| $\sum\limits_{i=2}^{k=1}{{{A}_{i}}}=\sum\limits_{i=2}^{k+1}{({{L}_{i\bmod k}})}\bigcup \sum\limits_{i=2}^{k+1}{({{L}_{i-1}})}\text{=}M\text{+}M\text{=2}M$ |
证毕。
定义 4 空间利用率U
由定义1可得：
| $U=\frac{2M}{xM}=\frac{2}{x}$ | (3) |
文件名称为f，S表示其大小，f存储的k个节点分别用N1～Nk 表示。
1) 文件分块
K等分f为fi(1≤i≤k)，其大小为Si ，Si=S/k。x等
分fi，fij(1≤i≤k,1≤j≤x)表示每份子文件，其大小表示为Sij(1≤i≤k, 1≤j≤k-1)，分块示意图如图 1所示。
 |
| 图1 文件分块示意图 |
2) 文件存储分两个步骤：① fi→Ni; ②fij→ (i+1) mod k。
数据块存储示意图如图 2所示，下层为步骤①分配的数据，称为LND数据；上层为步骤②分配的数据，称为OND数据。
明显可得，LNDsize=ONDsize，其中LNDsize表示LND的数据量，ONDsize表示OND的数据量，总量为2S。当任一节点不可用，可以从其余节点的数据集求并来获得整个数据。其中，k等分的每块原始数据用Bi表示，$i\in (1,k)$。
 |
| 图2 数据块存储示意图 |
文中比例分割如图 3所示，首先将完整的数据文件file按照δ和1-δ(0<δ<1)的比例分成两个部分。
 |
| 图3 文件比例分割 |
1) 对于文件的δ部分直接等分为i份，存储于对应的节点i；
2) 1-δ部分采用CS模型存储进行存储。
文件的整体存储策略如图 4所示，图中Ni表示节点号。
 |
| 图4 文件的比例模型存储策略示例 |
从数据占用的空间比较，CS存储模型使用k个节点存储数据，与完全的副本存储之比为U=2/k。而RS存储模型，空间占用比表示为：
| $\text{SAV}=\frac{a+2(1-a)}{k}=\frac{2-1}{k}$ | (4) |
式中，a表示δ部分存储的数比例，且0<a<1。
定义 5 本地数据剩余量Si 令节点Ni的平均带宽为Vi，在并行数据获取中，从移动节点Ni下载的理想数据量与本地数据LNDi的差值定义为本地数据剩余量Si，即：
| ${{S}_{i}}={{{V}_{i}}}/{\left( \sum\limits_{j=0}^{k-1}{{{V}_{j}}} \right)kx-\text{LN}{{\text{D}}_{i}}}\;$ | (5) |
分析：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≤LNDWi
Get (LNDi+Si) blocks
Else
Get (LNDWi) blocks
Get (LNDi+Si-LNDWi) blocks from ONDi and mark them
ONDi and 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 on interleave model)表示基于CS模型的并行传输算法，PTRM(parallel transmission based on ratio model)表示比例模型传输算法，CLBS(conservative load balancing strategy)表示保守调度算法，DAS(dynamic adjustment strategy)为文献[11]提出的算法。
在教育网、移动网络、联通宽带的3种网络中选取一些节点作为实验数据的部署节点。具体如下：
使用联通3G作为移动模拟节点，为数据需求方。数据部署节点使用教育网内电脑两台，移动网内计算机一台。数据的大小为960M。为了保证保证物理条件的一致性，对于PTRM、CLBA和DAS使用相同的网络接入与服务节点。根据最短下载时间的定义，各种并行传输算法所能达到的最小下载时间不能超过MDT。
 |
| 图5 实验使用的系统组成 |
令数据块大小Bi=40，通过开源文件分割工具将数据文件分割处理后成为480块数据，每块2M。两种存储模型的分割方法相同。 为了保证数据的精确性，进行了多次、多时间点、重复性的实验，如图 6所示。
实验结果分析：多项式曲线拟合的结果显示， MLTT曲线位于最下方，PTRM和CLBS两条曲线基本吻合，走势相同，中间存在交线，表明二者性能相仿，而DAS拟合曲线处于二者下方，略微具有一定优势。3种曲线都以MLTT曲线为下限。
 |
| 图6 传输时间多项式曲线拟合 |
测试时间为北京时间上午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 δ变化时的传输时间 |
实验1)表明本文提出的PTIM算法与CLBS和DAS在存储空间大大节约的情况下达到了相似的性能。
实验2)表明，PTIM算法性能受Bi的影响明显，但是在metadata的大小达到2M以内时，继续增大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. |