基于频度的动态样本算法的fbdr研究

基于频度的动态样本算法的fbdr研究

1动态副本技术随着科研领域的快速发展，存储需求对新一代存储系统的性能提出了更高的要求。动态副本技术是分布式数据环境中普遍采取的一项提高数据的可靠性、容错能力和IO性能的重要技术。目前,动态副本技术已广泛应用于数据网格,P2P存储等跨越广域网的数据环境,以提高数据服务质量。但是多数本地分布式存储系统(包括分布于局域网范围的分布式文件系统和海量存储系统)仍广泛采用静态副本机制。基于本地分布式存储系统的拓扑结构和存储单元特征,提出了一种基于频度的动态副本算法FBDR(FrequencyBasedDynamicReplica),并应用于海量存储系统dCache中。2基于数据通讯的本线副本创建策略动态副本算法的研究内容一般包括热点文件的认定,副本位置选择,副本的动态增加与删除。基于数据环境的系统拓扑结构,存储单元性质和数据访问模式,各种算法差异较大。在数据网格环境中,文献提出了NoReplication、BesClient、PlainCaching、CachingplusCascading和FastSpread五种不同的动态副本策略。文献设计了一种快速瀑布(FasCascading)模型。文献提出了SBU和ABU两种不同的动态副本策略。这几种策略基本上都采取了基于文件访问总数的热点文件认定方式,即在每个存储节点维持一个计数器,统计每个文件在一段时间内被访问的次数,如果超过阈值,则为该文件增加额外的副本。在副本创建位置的选择上,着重考虑了客户端到存储节点之间的链路代价。在P2P网络环境中,文献基于非结构化的P2P网络,采用了模糊理论,根据各节点不同的物理性能和网络的当前状态(服务质量、网络带宽、磁盘空间、在线时间),动态计算节点的可靠性,作为选择副本创建位置的依据。文献引入一种可变周期的算法,通过分析文件访问的变化趋势,提出一种根据文件热度值的高低动态调整周期的检测方案,作为确定热点文件的依据。其中热度值的计算采用了经济学中的时间序列平滑算法,每一个时间段对该文件的请求数目都具有一个权重值,权重值随着请求时间距离的变远而衰减。同时采用一个收益公式作为确定副本创建位置的基础。收益公式考虑了节点的上传、下载带宽,在线时间等因素。本地分布式存储系统一般分布于局域网范围内,因此各个存储单元之间的链路代价差异可以忽略不计;其存储单元一般为磁盘服务器,具有很高的稳定性,因此IO性能、系统负载、可用磁盘空间是决定副本位置的重要因素。此外热点文件的命中率决定了有限的存储空间是否得到合理利用。基于上述因素,提出了FBDR算法。3聚合式如何确定副本位置基于频度的动态副本算法包括热点文件的认定,副本创建位置的选择,副本的动态增加与删除策略四项内容。为获得较高的热点文件命中率,FBDR提出了两种不同的频度分析算法:基于密度的单次频度分析OFMI(OnewayFrequencyMeasurebyIntensity)与基于区间长度的两次频度聚合TFMS(TwowayFrequencyMeasurebySpan),作为确定热点文件的基础。在副本位置选择上提出了一个融合了存储单元的负载、IO性能、可用空间等因素的打分公式。在副本动态增加上,考虑了兄弟副本(隶属于同一个逻辑文件的存在于另一个存储单元的副本)的副本需求、活跃指数、代表频度值与频度阈值的关系、访问聚合区间的个数和高频访问出现的次数等因素。在副本的动态删除上,考虑了文件的近期访问频度,兄弟副本的副本需求或活跃指数等因素。为方便频度计算,采用一种相对时间分钟计时法来表示文件访问的时间戳,即将文件访问的时间戳转换成为自1970年1月1日0时0分0秒起的分钟数,如时间戳1970年1月2日0时0分0秒的相对分钟数为1440。对文件的访问时间序列可依次转换为一个升序的相对时间分钟数数组Times。3.1ofmi算法OFMI算法通过计算Times上任意一个长度为SPAN的时间段内频度值,取得所有频度值中的最大值,作为该文件的代表频度值。OFMI支持fast模式,即在第一次计算出高于阈值的频度值freq,便返回该值。fast模式被用于副本删除中评价副本的活跃指数。OFMI算法返回值是一个频度值,其计算过程如下:输入:文件Rj的时间访问数组Times假设文件Rj在扫描周期内具有P次访问记录,则OFMI算法的计算复杂度为O(P2)。对于高频文件,OFMI的计算量比较大。3.2tfms算法OFMI算法注重的是近期单位时间段上的频度最高值,所需副本个数也由该峰值决定。但不同实用环境中的数据访问模式有所差别,有些文件在长时间内只出现一次峰值,利用OFMI算法很容易为这些文件创建利用率低的副本。因此在OFMI算法的基础上,提出了一种频度分析以及聚类算法TFMS,以便更精确地量化文件的被访问模式。运用TFMS算法决定增加副本数目时,不仅关心文件的近期访问高峰,还综合该文件在较长一段时间内的历史记录来考察该文件之前是否具有同样的访问高峰。在考察周期内,如果某文件只存在一次访问高峰,则只赋予一个副本;如果该文件具有多次访问高峰,则取单位时间段内频度峰值的平均数作为代表频度值,并据此计算所需副本个数。TFMS算法的返回值为分段区间的频度值freq和聚合区间信息ag_freq。其计算过程如下:输入:副本Rj的时间访问数组Times第一步:计算分段频度值第二步:将频度按区间聚类,其中INTVL是聚类区间的长度假设文件Rj在扫描周期内具有P次访问记录,则TFMS算法的计算复杂度为O(P)。3.3存储池的选取创建副本的一个重要目的是为了让各个存储池的负载、性能与资源消耗均衡。对一个具体的存储池,采取近期的文件访问量(Ni)作为系统负载的参考因素,可用存储空间(Sfi)作为资源消耗的参考因素,近期的IO吞吐率(Ratei)作为系统性能的参考因素。综合上述三个因素,提出了存储池打分公式(1)。在公式(1)中,三个因素分别被赋予不同的权重值(Wspace,Wcn,Wrate)。因为存储池得分与文件访问量成反比,所以采用公式(2)计算存储池上文件访问量的倒数Nri。假设有n个可用存储池,每个存储池的得分是相对、可比的。每个存储池的得分是位于0到10之间的一个值。如果一个存储池的得分较高,说明它相对其他存储池具有较少的文件访问量,或者较高的IO吞吐率,或者更大的可用存储空间。对于新创的副本而言,置于访问量较少的存储池,能平衡所有存储池的系统资源(CPU,内存,网络)消耗;置于IO吞吐率快的存储池,能获得更高的访问速度;置于可用存储空间较大的存储池,能平衡各个存储池的可用空间的分布。在动态副本系统中,创建新副本时总会优先选择得分最高的存储池;而删除副本时却优先选择得分最低的存储池。存储池的得分是动态变化的,因此每次在决定新增或者删除副本时,都应该重新计算所有存储池的得分。3.4增加副本数目FBDR只针对具有一次写入多次读特性的文件,因此不考虑副本的一致性维护的代价,而充分考虑本地分布式存储系统的特性。通过OFMI或TFMS算法都可以获得一个代表频度值作为新增副本数目的依据。基于两种不同的频度分析算法(OFMI和TFMS)的副本动态增加策略有所区别。基于OFMI的策略以代表频度值作为副本个数的决定因素。基于TFMS的策略以代表频度值、聚合区间的个数以及高频区间的个数等因素作为副本个数的决定因素。但两者都兼顾该热点文件的兄弟副本的活跃情况。对于一个逻辑文件F,定义其副本集合R为{R1,R2,…,Rn}。下面分别讨论基于不同频度分析算法的副本动态增加策略。3.4.1回cs-mfreq的低频度值及副本个数OFMI对一个现存副本文件的Times计算后返回该序列上的最高频度值作为代表频度值mfreq,通过mfreq与阈值的关系以及兄弟副本的活跃情况得出该副本文件所需的副本个数。具体计算过程如下:3.4.2tfms算法TFMS算法的输出为数组freq和ag_freq,freq保存了热点文件在单位时间段(SPAN)上的频度值,ag_freq保存了热点文件按照聚合区间的分类信息。利用TFMS算法确定副本个数时充分考虑了不同时间段上频度的平均值、文件访问高峰的分布模式以及兄弟副本的活跃情况。相比OFMI算法,TFMS算法更保守,以防止创建冗余、低利用率的多副本文件。在获取高频文件时,TFMS采用了一个较低的阈值FREQ_MIN计算副本的活跃指数。一个文件是否满足增加副本的条件,取决于其代表频度值跟一个较高的阈值FREQ_MAX的比较。高频文件的状态可分为两种,一种是该文件在较长的历史周期内具有多次相隔较远的访问高峰,这类文件的代表频度值等于其所有超过FREQ_MAX2倍的频度值的平均值。该类文件所需的副本个数同时与扫描周期内聚合区间段个数Ntag以及出现高峰时间段的次数Nhf成正比。用公式(5)来求取这类文件的副本个数。其中,Ninc为递增因子,Nrep是该副本文件所需的副本个数,α为最高频度阈值,即FREQ_MAX,Favg是该副本文件的代表频度值。另一类文件在其扫描周期中只存在一个聚合区间,即只出现一次较大规模的访问高峰,对这类文件不能确认其后续是否出现新的高峰,因此只赋予一个副本。3.5逻辑文件的删除当副本的利用率下降后,应该将冗余的副本从合适的存储池删除。一个副本是否满足被删除条件不仅跟该副本近期的访问频度有关,还跟其兄弟副本当前的活跃状态有关。FDBR利用OFMI的快速频度计算的结果确定是否需要删除一个逻辑文件的额外副本。对于逻辑文件F的多个副本,判断其是否满足被删除的条件的过程如下:第一步:判断副本的删除状态对于一个文件F的每个副本Rj{上述过程中一个副本具有三种状态:-1表示副本刚创建不久,不记入考察的范围;0表示副本处于活跃状态;1表示副本处于非活跃状态。第二步:确定删除副本的位置将所有副本所在的磁盘池打分排序得RPools;从RPools中依次删除del_no个副本;4tfms多副本文件的形成代价根据FBDR的思想在海量存储系统dCache上实现了一个动态副本管理器RepHot,并运行在USATLAS的AGLT2(AT-LASGreatLakesTier2)站点的生产系统上。采集了生产系统上的实际数据对OFMI与TFMS两种算法的性能进行了分析。同时,还实现了一种基于总数的热点文件识别方式TN与OF-MI、TFMS进行命中率比较。在实验中,跟OFMI相关的阈值设为(SPAN=2,FREQ=5),与TFMS相关的阈值设为(SPAN=2,FREQ_MIN=2.5,FREQ_MAX=4.5),TN的阈值设为20,时间长度为2分钟,即2分钟内访问总数超过20的文件为热点文件。在实验中,分别采用2880小时,3600小时,4320小时作为扫描周期。其中,无效、失败的访问,访问总数低于一定阈值的记录在分析前都被过滤掉了。图1比较了不同扫描周期上,TN、OFMI与TFMS三种策略的命中率。对命中率的定义如下:单副本的命中率:n为被命中的单副本个数,如果一个单副本创建后,分担了源文件的访问量,则被命中。N为扫描周期中所涉及的文件集中的理应单副本文件个数,通过分析文件集中每个文件的所有历史访问记录而得,即如果一个文件在其整个生命周期中出现过超过阈值的频度,并且其访问记录出现在距离不远(两次访问记录的时间不超过120小时)的不同的聚合区间中,则称为理应单副本文件。多副本的命中率:m为被命中的多副本个数,如果一个文件具有多个副本,且每个副本在创建后都具有超过阈值的访问频度,则称被命中。M为扫描周期中所涉及的文件集内理应多副本文件个数,通过分析文件集中每个文件的所有历史访问记录而得,即如果一个文件的访问频度超过阈值的2倍,而且这种访问频度被分布在距离不远(两次访问高峰的间隔不超过120小时)的不同的聚合区间中,则称为理应多副本文件。由图1可见,对单副本文件,在不同扫描周期中,TFMS命中率都略高于OFMI(约1%~8%),OFMI又高于TN(约8%~20%),OFMI的命中率随扫描周期的增大呈上升趋势。对于多副本文件,在不同扫描周期中,TFMS命中率远高于OFMI(约10%~46%),OFMI又高于TN(约6%~25%),随扫描周期的增大,TFMS的命中率呈下降趋势,而OFMI的命中率呈上升趋势。出现上述趋势的主要原因是:(1)TFMS只对已具有多个访问高峰的文件赋予多副本,因此对多副本文件的命中率高于TN与OFMI。OFMI采取任意一个单位时间段SPAN上的频度最高值作为频度代表值,因此比TN更能捕捉到文件访问的高峰值,识别热点文件。(2)扫描周期增大时,文件的访问时间序列Times增大,OFMI所获得的代表频度值增大的可能性变大,更容易捕捉到潜在的热点文件。(3)TFMS采取相对保守的机制严格控制多副本文件的个数。在该模式下,虽然被识别的文件大部分被命中,但是也漏掉了一些文件(首次出现访问高峰的文件)。随着扫描周期的增大,所涉及的文件集也增大,漏掉的文件的增长速度超过了命中文件的增长速度,使得TFMS的多副本命中率下降。除了命中个数,不同的策略所产生的副本总数也有很大差别。希望一个策略能在产生较少的副本总数的前提下获得同样或者更高的命中率。因此,采用了副本的生成代价来衡量各种策略的优劣。定义副本的生成代价:其中C为创建的副本总数,S为副本的平均大小,n为命中的副本数。在比较的情况下,S可以简化为一个常数1。代价值的实际意义为一个策略需要产生P个副本才能命中一个副本。因此当一种策略的副本生成代价越低,说明该策略在同样的命中数下所产生的副本总数越低,或者在生成同样的副本总数时,命中的副本个数越多。由图2可见,对于单副本的生成代价,在各个扫描周期中,TFMS的P值略微低于OFMI,而OFMI的P值又低于TN。对于多副本的生成代价,在各个扫描周期内,TFMS的P值大大低于OFMI,OFMI的P值又大大低于TN。OFMI的多副本的P值随扫描周期的增大而大幅度降低,而TFMS的多副本P值随扫描周期的增大而略微上升。出现上述趋势的原因有:(1)对单副本文件,不同扫描周期中TFMS的命中数略微高于OFMI,并且TFMS比OFMI所创建的副本总数低,