异构存储系统的文件迁移策略研究

异构存储系统的文件迁移策略研究

现有的文件偏移策略通常分为长期决策方法和短期决策方法。长期决策方法根据文件访问的历史数据和用户行为的历史统计获得文件访问模式，然后精确测量未来的文件访问速度，并进行文件偏移决策。在长期决策中，许多采用了mart决策模型或半mart决策模型。如果在实际系统中完全采用这些决策模型，由于巨大的状态空间，计算的复杂性将是非常复杂的。短期决策方法基于服务器现状、扇区利用率和cpu使用参数来进行文件偏移决策。这具有很强的适应性系统变化的能力。短期决策模型在动态负载平衡中起着关键作用,它对实时性要求很高,所以对设计代价小、执行快的算法尤为重要.文献提出的磁盘冷却算法是比较典型的短期决策算法.但它是针对同构单元提出的,负载平衡调整慢且调整开销大.本文介绍一种基于能量的文件迁移策略,综合考虑文件、存储单元两方面的因素来决定文件的存放位置,平衡各存储单元的负载压力,保证异构存储系统的性能能够得到充分的发挥.1能量模型1.1文件能量的衰减负载平衡中很重要的一点就是考虑由于文件访问造成的负载差异.本文提出一个对文件访问频度和大小敏感的能量模型,采用能量这一概念来描述文件访问给存储系统带来的负载压力.文件能量主要受下面这几个因素影响:1)和访问的次数成正比.访问次数越多,文件所具有的能量越高.2)和并发访问情况成正比.并发访问数相对于当时系统平均并发访问数比值越高,文件所具有的能量就越高.3)和文件大小成正比.文件越大,意味着访问文件需要消耗的带宽越大,文件具有的能量也就越高.4)随频度呈指数衰减.类似于自然界中的放射性元素,有相应的半衰期τc.对存储系统发生的每一次访问都依次编号,用e(fi,t)来表示存储系统在发生第t次访问的时候文件fi所具有的能量,α=2-1τc表示能量的衰减基数:①如果在发生第t次访问以前,文件fi从未被访问过,则e(fi,t)=0.②如果存储系统在第t次访问时访问文件fi,则e(fi,t)=e(fi,t_)+ρiˉρ⋅li其中,t_表示第t次访问之前,是个极限概念;ρi表示存储系统在发生第t次访问时,文件fi的并发访问数;ˉρ表示存储系统在发生第t次访问时的平均并发数;li表示文件fi的长度.③如果存储系统在t1和t2之间没有对文件fi的访问,那么e(fi,t2)=e(fi,t1)·αt2-t1.④如果存储系统在发生第t2次访问时访问文件fi,且上次对文件fi的访问发生在t1,那么e(fi,t2)=e(fi,t1)⋅αt2-t1+ρiˉρ⋅li(1)上式可以由式(2)和式(3)推出.1.2系统负载的描述每一存储单元根据其存储文件或者文件分块拥有不同的能量,但其能量高低并不能直接反映存储单元的负载.因为存储单元是异构的,各个存储单元拥有的存储空间和访问带宽各不相同.为了描述异构存储单元的负载,本文引入相对能量.用e(nj,t)来表示t时刻存储单元nj所拥有的相对能量:e(nj,t)=wjSj⋅ˉLLj(2)其中,wj=Σe,表示存储单元nj上文件或者文件分块拥有能量的加和;Lj为存储单元j当前可用存储空间;ˉL表示系统当前平均可用空间;Sj为存储单元j的可用带宽.2文件重复使用策略2.1迁移触发函数传统的触发函数如图1a所示,触发条件往往被设定成一个阈值,当负载超过这个阈值就触发迁移操作.但这种设置对存储系统而言有一个缺点:存储系统的访问请求一般具有较大的倾斜性,在迁移触发函数被触发的时候,后续访问请求可能迅速恶化存储单元的负载情况,进而导致存储系统性能降低.本文提出的迁移触发函数是一种适应异构存储系统、基于概率的触发函数REM(RandomEarlyMigration),式(3)为REM触发函数,函数形态如图1b所示,通过设置Lmax,Lmin(Lmin<Lmax)来衡量存储单元负载.pi={0Si′≤S⋅Lminpmax⋅Si′-S⋅LminS⋅(Lmax-Lmin)Si′∈(Lmin‚Lmax)⋅S1Si′≥S⋅Lmax(3)其中,pi为迁移概率;Si′表示i存储单元的当前可用下行带宽;S表示存储单元i的负载水平,由式(4)得到:S=min(Si⋅ˉSˉSc,ˉS)(4)其中,ˉS表示存储系统当前平均可用下行带宽;ˉSc表示存储系统拥有的平均下行带宽;Si表示i存储单元拥有的下行带宽.2.2基于迁移单元的带宽分配算法传统的文件动态迁移策略,如磁盘冷却算法,会根据负载情况选取负载最重的文件从很忙的设备读出,写入较空闲的设备.不是基于当前请求的,负载平衡时在一定程度上加重了设备的负载.本文提出的文件迁移策略兼顾以下策略:1)迁移工作以数据块为单位进行.存储系统存储的文件以固定大小分割为若干独立的数据块,以数据块为单位进行文件迁移,避免大文件、大数据分块迁移造成的迁移工作耗时长,消耗过多带宽资源,且易造成目的存储单元性能瓶颈等不足因素.2)迁移对象选择采取与当前用户请求相结合的策略.选择当前正在被访问且能量密度最高文件fi.用ρi表示文件fi的能量密度:ρi=eili(5)其中,li为文件i的长度;ei为文件i当前所具有的能量.本文定义迁出数据块的存储单元为迁移单元,接受迁出数据块的存储单元为接受单元,如图2所示.则有:1)在接受单元下行带宽允许的情况下,复合所有正在访问数据块bj的用户请求ds,将∪ds,ds⊆bj发送给接收单元;2)在接受单元下行带宽允许的情况下,充分利用迁移单元空闲带宽,从数据块bj的尾部开始读取bj-∪ds,发送给接受单元;3)在迁移过程中,如有新的访问fi请求dnew到来,或者尚未访问到数据块bj的用户请求完成了对一个数据块的访问,则该用户请求将跳转到bj,之后再依次访问其他数据块,以便迁移工作复合更多用户请求;4)在迁移任务进行过程中,对需要迁移的数据块bj,如无任何新的用户访问到来,且所有用户请求都已越过bj,迁移算法将从迁移单元的空闲带宽分配固定带宽si以保证迁移工作正常进行:si=vli(6)其中,v为系统为用户请求fi分配的带宽;li为fi以数据块为单位表示的长度.如可分配带宽小于需要分配的带宽,则将迁移单元最近完成用户请求释放的带宽补充给迁移任务,直至达到si;5)迁移任务如果拥有分配给其的固定带宽si,则该固定带宽保持到迁移任务完成,或者有新的对数据块bj用户访问到来.通过复合用户访问,既可以使重构负载与用户请求相重叠,又充分利用了存储单元的空闲带宽,从而减少了文件迁移的I/O开销.2.3基于能量接收点的适应策略文件迁移在消除源存储单元负载瓶颈的同时,会给目的存储单元带来额外的负载并可能形成新的瓶颈,成为“多米诺骨牌效应”,进而导致系统性能迅速下降.为避免这种情况,本文考虑的接受策略要求:目的存储单元i应具有较低的相对能量Ei,且在接受数据块bj后相对能量变化最小.Ei≤ˉE⋅δLi≥bjmin(Ei′-Ei)}(7)其中,ˉE表示当前系统的平均相对能量;δ为一阀值,用以衡量存储单元相对能量高低;Li为存储单元i当前可用存储空间;Ei′为存储单元接受数据块bj后的相对能量.2.4存储单元地台到tkAlgorithm:文件迁移策略Input:m:虚拟存储系统的存储单元数;n:文件数量;对存储系统D:{D1,D2,…,Dm},Dj=(Lj,Sj,Ej).其中Ej为存储单元j当前所具有的相对能量.对存储文件F:{F1,F2,…,Fn},Fi=(li,ei);tk:存储系统第k次访问时所访问的文件;Output:负载平衡所需进行的动作ACTION.Step1根据存储单元Dj的Sj,依据式(3)判断存储单元j是否触发文件迁移操作.Step2对所有触发文件迁移操作的Dj,依据式(5)选择当前正在访问文件中能量密度最高的文件分块进行迁移.Step3依据式(7),对所有触发文件迁移操作的Dj,选择合适的接受单元,安排迁移操作.3基于i/o的异构存储系统的执行时间优化本节将通过模拟试验来验证基于能量的文件迁移策略对异构存储系统I/O执行时间的优化效果.试验的访问请求采用合成负载的方式.为了比较效果,将试验结果与存储系统常用的磁盘冷却算法进行了比较.3.1盘di的生成为了验证算法的有效性,在如下环境进行验证.异构存储系统由10块虚拟磁盘构成,总计有可用存储空间120Gbyte,下行带宽100Mbyte,上行带宽50Mbyte.为了简化,规定对构成存储系统的任意虚拟磁盘Di,初始空间Ci以100Mbyte为单位随机生成,取值范围表示为[1Gbyte≤Ci≤30Gbyte];初始下行带宽Vi以1Mbyte为单位随机生成,取值范围表示为[5Mbyte≤Vi≤25Mbyte];初始上行带宽Vi′=5Mbyte,为一常数.对于异构存储系统上存储的任意文件Bj,长度Lj以100Mbyte为单位生成,取值范围表示为[0.1Gbyte≤Li≤10Gbyte];初始情况下,每一存储单元有5个文件,总计消耗80%存储空间.文件以100Mbyte为单位划分为独立的数据块.每一请求服务需要带宽取固定值Sj=500Kbyte.表1给出了本次测试中的一些参数,另外能量是无单位的数值.3.2生成i/o请求尽管实际的访问踪迹对试验的模拟非常重要,但人们收集的踪迹往往很难反映出所有的访问模式.因此试验采用按一定方式合成负载的方法产生I/O访问序列.为了充分反映请求的偏斜性,采用X/Y分布产生I/O请求,也就是说X%的请求访问Y%的文件.如果将文件编号为1～50,对于任意给定的参数X/Y,文献给出了请求访问的文件号i小于s的概率:Ρ(i≤s)=[S/Ν]lg(X/100)/lg(Y/100)(8)其中N为文件总数.可以根据这个公式求出请求访问每个文件的概率,这个概率反映每个文件的负载情况.为了使负载有一定的动态性,本文通过改变文件编号来实现.以每1000次访问为一个周期T,编号i可以写成i=(i+T)%50.3.3文件无平衡策略连续进行10组模拟试验.为每一组模拟试验按照3.1节性能测试环境一节设定的方法随机生成存储单元、文件,按3.2节负载产生一节介绍的方法生成请求任务序列.在每一组模拟实验中,比较采用本文提出的负载平衡策略、传统的磁盘冷却算法与无负载平衡情况下,完成按1s,2s,5s,10s时间间隔到来的10000次访问请求需要的平均处理时间和平均吞吐率.磁盘冷却算法采用相对负载,是根据文献中的算法改造而来的.无平衡策略指数据以初始的每存储单元存储5个文件的方式分布,无论存储单元的负载怎样变化都不进行负载平衡.请求平均处理时间为系统服务访问请求运行的总时间与总请求数的比值,越短越好,反映了系统的服务速度.平均吞吐率为为单位时间内系统处理的请求数,越大越好,反映了系统的服务规模.图3和图4分别反应了不同时间间隔下的平均处理时间、平均等待时间比值图,以无平衡策略得出的数据为1.模拟