数据网格的存储资源预留方法

曲明成，吴翔虎，张 银，廖明宏，杨孝宗，左德承

(1.哈尔滨工业大学 计算机科学与技术学院，哈尔滨150001，qumingcheng@126.com;2.厦门大学 软件学院，福建 厦门361005)

现有的针对存储空间、计算能力和网络带宽的资源能力预留其主要解决方案为:通过在资源能力二维坐标空间中将一段时间内的资源能力预留抽象为矩形区域，最为有效的方法为基于时间槽的资源能力预留法［1-4］，本文中称其为二元法(REC).数据网格资源能力预留可以表示成存储空间与时间的二元组，即＜StorageSpace，Time ＞，该资源能力同样为矩形区域，所以StorageSpace与Time 为确定的数值.如图1 所示，网格的存储资源量总数为M，有两个资源预留分别为R1(h1，t1)，R2(h2，t2)，在图1 中分别为两个矩形区域，而资源能力的大小为矩形区域的面积.

图1 REC 法资源能力预留

REC 法在数据网格的资源能力预留中性能较差.比如:欧洲原子能数据网格是为原子能实验特别设计的，其实验时以10 M/s 的速度产生数据，并对其存储，而后以1 M/s 的速度处理数据［5］.而在其他很多时候也存在同样的问题，比如目前将数据网格与计算网格相结合，在计算前从数据网格中预留一定的存储数据，将数据以一定的速度存储到预留的空间，待计算条件具备时以一定的速度进行处理，并随时删除处理过的数据，释放存储空间［6］.为提升网络的下载速度，很多副本部署方法也呈现同样的特性［7-8］.

针对应用场景和存在的问题，将资源能力的预留表示成四元组R=＜VP，VC，H，t ＞，其中，VP 为数据生产速度，VC 为数据消耗速度，H 为存储空间总需求量，t 为起始时间.这样资源能力的预留将可以表示成图2(a)，称这种预留方法为四元法(TR).从图2(b)中可以看出，如果使用REC法，这两个资源能力预留是无法被同时接纳的.显然TR 使用的资源能力较REC 小很多，如此必可以提升资源能力的使用率、资源能力预留请求的接纳率，同时可以减少资源能力碎片，从而提升数据数据网格资源能力预留的整体性能.

图2 TR 资源能力预留与REC 的比较

1 基本阶梯法(BTR)

1.1 基本定义

定义1(资源能力空间) 在二维坐标系中，以时间t 为横坐标，数据网格的可用存储空间h 为纵坐标，称h=M(存储空间总量)与h=0(横坐标轴)围成的无限空间为资源能力空间.

定义2(资源能力三角形，资源三角形) 令V0，V1分别为一次资源能力预留中数据的生产速度和消耗速度，总存储空间需求为M(总数据量)，已知t0，V0，V1，M.则资源能力预留的几何图形可以表示为图3(a)，其中V0，V1分别为三角形两条边的斜率，称这样的三角形为资源能力三角形.其中，t0为预留起始时刻，t1为达到预留量时刻，t2为空间使用完毕时刻.两个不与t 坐标轴平行的边的函数分别为h1=V0(t-t0)，h2=-V1(t-t2).

定义3(资源能力阶梯三角形，阶梯三角形) 如图3(b)所示，将资源三角形以t1为界分割成两个三角形，将区间(t0，t1)与(t1，t2)以时间单位r 进行分割，其分割的份数分别为n1和n2.对于左侧三角形每个小区间的面积Sir =rV0(t1+ir-t0)，而令，右侧三角形每个小区间的面积-rV0(t1+jr-t2)=rV0(t2-jr-t1)，令，令，称由和构成的区域为资源能力阶梯三角形.

图3 资源能力三角形与阶梯三角形

定义4(资源能力使用率) 定义一段时间内所接纳的资源能力预留的总和与该段时间时间内资源能力空间大小的比值为资源能力使用率(U).令某个阶梯三角形的大小为，REC 法资源能力大小为.其对应的为某段时间内的资源能力空间大小.

1.2 公式推导

为了能够有效地计算某个资源能力预留请求是否可以被接纳，理想的情况下是资源能力空间在资源能力预留时刻处有足够的空间可以容纳下资源能力三角形(REC 法为矩形).给出ST，SR，UT，UR的求解过程，求解时参考图3 进行几何推导.

令时间单位长度为r，将t1-t0分成n1=份，则，并假设区间(t0，t1)，(t1，t2)之间有整数个单位时间间隔.t1，t2的求解为

由式(1)可以得出SR为

为了求解ST，需先求出S1′，S1″，由式(1)推出:，由此可以推出:

由定义4 和式(2)，式(4)得出

2 阈值阶梯法(VTR)

由于网络速度的动态变化，基本阶梯法的资源能力预留存在一定的局限性(要求网络速度平稳)，因此应为生产与消耗速度引入一定的速度变化区间.

定义5(可靠阈值ε) 生产与消耗速度实际中会存在偏差，在基本阶梯法中引入速度偏差，即生产与消耗速度分别位于区间(V0-ε，V0+ε)与(V1-ε，V1+ε)中，称ε 为可靠阈值.

定义6(阈值梯形) 在基本阶梯法中引入可靠阈值后，即相当于在图3(a)的几何图形上将非平行t 轴的两条三角形边的斜率分别±ε，而后形成的图形为一个梯形，如图4 中的由t0，t2，A，B 4 个点构成的图形，称其为阈值梯形.

图4 阈值梯形图

阈值梯形的面积为资源能力预留的数量，令其为ST′，其面积可以分解为3 部分，如图5(a)，即三角形Δt0T1A(Sa)，矩形T1T1′AB(Sb)，三角形ΔT1′T2B(Sc).将3 个区域重新组合成图5(b)，并对新的大三角形按照基本阶梯法进行处理，同时根据图4 进行推导:

根据式(4)和图5(b)可以得出ST′=(Sa+Sc)+Sb，由此推出:

图5 阈值梯形分解图

定理1 由于为在基本解题法中引入可靠阈值后致使资源能力预留时间增加了Δt2=T2-t2，当V0-V1+ε ＞0 时，如果对REC 法进行t2可靠阈值扩展，其资源能力SR′增加量SR＞ST=ST′-ST.

证明:

因为V0-V1+ε ＞0，所以ΔST-ΔSR＞0，证毕.

定理1 说明，在时间增加相同的情况下针对REC 法进行可靠扩展的代价要大于阈值阶梯法.

由式(2)，式(5)推出:

由式(7)，式(8)推出:

3 仿真实验

令资源能力空间具有2 500 个时间单位，资源最大数量为4 000，在一次测试中，针对该段资源能力空间随机的产生不同数量的资源能力预留请求.判断某请求是否可以被接纳的条件为:该请求的任意一个hi都能被其所对应的时间单位内的资源能力空间所接纳.实验中将测试REC 法与BRTVTR 法的资源能力预留请求的接纳率、资源的使用率，并对其进行对比分析.同时模拟速度动态变化，以检测不同的ε 对已预留的资源能力使用失效的影响.

3.1 基本阶梯法性能测试

在一定的资源能力空间中，对REC 法与BTR法接纳率与资源能力使用率进行比较.从图6 可以看出随着请求数的增加两种方法的接纳率都成下降趋势，但是BTR 法接纳率明显较REC 法的高.而从图7 中可以看出，在接纳率相同时BTR法的资源能力使用率明显高于BTR 法.

图6 不同资源能力请求REC 与BTR 接纳率比较

3.2 阈值阶梯法性能测试

在一定的资源能力空间中，当ε =0 时，对REC 法与VTR 法接纳率与资源能力使用率进行比较.从图8 可以看出随着资源能力预留请求数的增加两种方法的接纳率都成下降趋势，但是VTR 法接纳率明显较REC 法的高.而从图9 中可以看出，在接纳率相同时VTR 法的资源能力使用率明显高于BTR 法.

图7 相同接纳率REC 与BTR 资源能力使用率比较

图8 不同资源能力请求REC 与VTR 接纳率比较

图9 相同接纳率REC 与VTR 资源能力使用率比较

3.3 综合比较与预留失效检测

令ε=0、5、10，观测请求量与接纳率的变化曲线，从图10 中可以看出较小的ε 产生较高的接纳率.令生产与消耗速度分别在(0.8 V，1.2 V)之间随机的变化.在整个资源能力空间中，如果某个时间单位的实际资源能力需求量超出网格的资源总量那么算作一次失效，搜索请求量为600 时的失效时间单位数，并将总数与总的资源能力空间时间单位数进行比值，得出失效单位数f.针对不同ε 取值分别进行10 次实验，取平均值，绘出柱形图如图11 所示，从图11 中可以看到，当ε=4 时，f 已经为0，效果较好.

图10 ε 对VTR 接纳率的影响

图11 ε 对VTR 预留失效的影响

3.4 实验小结

①采用BTR 与VTR 方法进行资源能力预留较传统的REC 法有更好的性能;②随着ε 的增加VTR 的性能逐渐降低;③在ε 达到合理的数值时预留失效可以降低为0;④采用合理的ε 值，可以大幅的提升资源能力预留请求的接纳率和资源能力的使用率，并可以降低或消除预留失效.

4 结 论

1)提出了基本阶梯法和阈值阶梯法很好的实现了四元法预留策略，而阈值阶梯法更能适应传输速度动态变化的网络特性.

2)从实验可以看出:与二元法相比四元法能够有效降低资源能力碎片，提升存储空间的使用率，进而提高资源能力预留的接纳率和网格系统的整体吞吐量.

［1］BURCHARD L O.On the performance of computer networks with advance reservation mechanisms［C］//Proceedings of the 11thIEEE Intl.Conference on Networks(ICON’03).Washington:IEEE Computer Society，2003:449-454.

［2］HU Chunming，HUAI Jinpeng，WO Tianyu.Flexible resource reservation using slack time for service grid［C］//Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS′06).Washington:IEEE Computer Society，2006:327-334.

［3］胡春明，怀进鹏，沃天宇.一种基于松弛时间的服务网格资源能力预留机制［J］.计算机研究与发展，2007，44(1):20-28.

［4］XIAO Peng，HU Zhigang，LI Xi，et al.A novel statistic-based relaxed grid resource reservation strategy［C］//Proceedings of the 9th International Conference for Young Computer Scientists.Washington:IEEE Computer Society，2008:703-707.

［5］Large Scale System Configuration Workshop.CERN and the DataGrid Project［EB/OL］.http://homepages.inf.ed.ac.uk/group/lssconf/files2001/datagrid-edinburgh.pdf.

［6］MCCLATCHEY R，ANJUM A，STOCKINGER H，et al.Data intensive and network aware (diana)grid scheduling［J］.Journal of Grid Computing，2007，5(1):43-64.

［7］SHI Ke.A replication and cache based distributed metadata management system for data grid［C］//Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing.Washington:IEEE Computer Society，2007:20-25.

［8］YUAN Yulai，WU Yongwei，YANG Guangwen，et al.Dynamic data replication based on local optimization principle in data grid［C］//The 6th International Conference on Grid and Cooperative Computing(GCC 2007).Washington:IEEE Computer Society，2007:815-822.