论文导读：本文对网格空间数据库的几个副本优化算法进行了研究;其描述为网格空间数据库的建设奠定良好的基础,并为网格技术在空间数据库的应用提供了可靠的依据.
关键词：网格，空间数据库，副本优化算法
1. 引言
在网格空间数据库中,副本优化算法能够根据数据文件的请求历史,预测未来数据文件的利用情况,把文件及时地摆放到最需要的地方,从而使网格在性能与资源利用率上有较大的提高.针对这种情况,作者对几个副本优化算法进行了研究.
2. 网格空间数据库的几个副本优化算法
利用排队长度调度算法作为网格空间数据库的调度算法,在空间数据处理站点接受用户作业之后,按照以下定义的副本优化算法.各算法都以空间作业所需要的空间数据文件名列表F为输入,以各文件的副本列表R为输出,作为空间数据处理站点读取空间数据的依据.
2.1直接从中心站点读取空间数据文件的算法
站点N接到作业任务之后,首先提取作业所需的空间数据文件表F;其次从中心站点逐个读取文件到N,以便计算单元开始处理.在这种情况下,仅考虑各站点在读取空间数据时的带宽变化,在处理作业的时候,每个计算单元仅考虑传输文件的路由情况,选择传输时间最小的站点作为数据传输的源站点,算法结束后,返回副本文件列表R到计算单元,算法描述如下：
N1:初始化当前作业的空间数据文件副本列表R,单个空间数据文件的副本列表:SpatialReplicaList,网络传输代价transferCost,最小传输代价mintransferCost=+∞,令i=0；
N2:获取网格中空间数据文件F[i]的副本列表SpatialReplicaList,令j=0；
N3:为SpatialReplicaList[j]加锁（防止文件被删）,获取该副本所在的空间数据站点SpatialDataSite；
N4：IF SpatialDataSite=N,如果R[i]!=null, R[i]解锁；R[i]=SpatialReplicaList[j],转到N9；
N5:transferCost=  .其中R[i].size为文件R[i]的大小, 为N到SpatialDataSite最大可用带宽；
N6:如果j=0或mintransferCost 〉transferCost,mintransferCost=transferCost如果R[i]!=null,R[i]解锁,R[i]= SpatialReplicaList[j]；否则SpatialReplicaList[j]解锁；
N7：如果j<SpatialReplicaList.size,j=j+1,转到N3（SpatialReplicaList.size为一个文件在各网格站点中存在的副本的个数）；
N8：如果R[i]=null,转到N2 （直到找到这个副本才能够开始计算工作）；
N9：如果i<F.size,i=i+1,转到N2.（F.size为文件列表的元素个数）；
N10：把R交给作业处理单元进行作业处理.
2.2有删除的算法
算法2.1是为了仿真现有空间数据库作业情况而建立的,它只在文件传输上考虑了传输时间最小的站点,网格中的数据文件固定不变,也就是作出了第一步优化,得出了一个副本文件列表R.但是,为了体现网格技术实施到空间数据库后的优越性,需要让各站点在处理作业的同时具备一定的存储能力,以便根据算法的需要创建空间数据文件副本和删除这些副本.如果处理作业的站点没有所需要的文件,优化算法就复制文件到作业站点的存储单元.如果在存储单元上有足够的空间,复制就一直进行.如果没有足够的空间,就要根据不同的删除算法对文件进行删除来创建复制文件所需要的空间,从而不断优化系统空间数据副本分布,使系统在作业吞吐率和性能达到优化.在算法2.1的结果R的基础上,我们进行了有删除的算法描述,该算法返回RD作为作业处理单元的数据访问的依据.
N1:用算法2.1的结果初始化RD=R,获取站点N的空间数据存储单元SpatialDataStorage；
N2:ifSpatialDataStorage!=null,令i=0；
N3:getRD[i]的存储单元SE；
N4:ifSE的所在站点为作业处理站点,转到N11（文件传输代价为0）；
N5: if SpatialDataStorage的存储空间没有添加新文件副本的可能,则不能存放文件RD[i],goto N11；
N6: if RD[i]复制到SpatialDataStorage成功,replicatedSpatialFile 指向该文件,RD[i]解锁, RD[i]= replicatedSpatialFile（变为本地数据）,goto N11；
N7:SetupSE上的总空间比RD[i]大的可删除文件列表expendableSpatialData ；
N8:ifexpendableSpatialData=null,转N11（那么这个文件仍要从远地读写）；
N9:deleteSE上expendableSpatialData中的全部文件；
N10:ifreplicatedSpatialFile=null,goto N6（一定要在本地创建副本）；
N11:ifi<RD.length,i=i+1,goto N3；
N12:把RD交给作业处理单元进行作业处理.
2.3预测文件价值的算法
以上选择的文件删除算法虽然在一定程度上解决了文件副本问题,但是由于选择的方式过于粗糙,有较多主观成分.如果能够利用经济预测的手段预测最要删除的文件价值,在可删与创建之间作出一个衡量,避免盲目行事.为此本算法根据在一段历史时间的统计结果,利用经济预测函数逐个预测要删除文件和要创建文件在未来一段时间的价值,通过比较来决定删除与否.
当本地站点的存储空间不足时,根据分布函数预测未来文件的代价,在存储单元查找文件列表信息,根据预测的价值,选择将来一段时间内价值最低的数据文件进行删除,直到有足够的空间存放新文件.根据经验,对于文件的访问一般是服从一定概率分布的,在大多数情况下,对文件的总体访问情况服从二项分布.因此,需要利用文件的索引值,对同一类的文件在作业处理中根据不同的索引值进行分类,同类空间数据文件索引值的编号相近,这样在文件的筛选中很容易地区分出哪些文件在将来有用.
利用对文件的访问服从二项分布的情况,利用指数平滑预测法,对索引文件的价值进行预测,具体预测顺序如下：
N:估计文件价值（由Na,Nb两步实现）
Na:获取最近一段时间空间数据文件访问的历史记录H=recentAccessedSpatialFile,L=H.size,
I(j)= recentAccessedSpatialFile(j).index；
Nb:根据文件编号的索引值,为文件进行价值评估,计算评估参数,F为文件索引平均值,
I（j）为H中文件的索引值,L为历史文件列表长度.因此平均索引值为 ,评估按照公式FV进行.我们选择最小的历史数据个数为5.
 ,其中 Id为要预测函数的索引.
 , ,
 (lm(x)系数值利用查找二项分布的分子自由度表得来) (单个文件的预测)
算法描述如下：
N1:初始化SpatialFilesToDelete,deleteableSpatialFileSize;
N2:令SpacialFile=null,i=0;
N3:获取AllSpatialFileList的第一个记录file;
N4:如果file非空,文件file可删除并且SpatialFilesToDelete不包含文件file,如果SpacialFile=null, 或者SpecialFile(Id)为SpecialFile的索引,file(Id)为file的索引,SpacialFile=file.如果file为空,转N6;
N5:file=AllSpatialFileLis.next,转N4;
N6:用N为SpatialFiel预测价值,结果为value;
N7:把SpacialFile加入SpatialFilesToDelete ,deleteableSpatialFileSize,= deleteableSpatialFileSize+SpacialFile.size（SpacialFile.size 是SpatialFile的大小）;
N8:如果deleteableSpatialFileSize< newSpatialFile.size,转N2;
N9:用Na计算 newSpatialFile的价值;
N10:如果newSpatialFile.Value〉deleteableSpatialFile.Value,(newSpatialFile.Value为newSpatialFile的价值,deleteableSpatialFile.Value为deleteableSpatialFile文件列表的价值之和),返回文件列表deleteableSpatialFile.
3.结束语
利用建立好的网格空间数据库模型和通过对不同的副本优化算法的研究,选择合理的网格空间数据库副本优化算法,能够为网格空间数据库的建设奠定良好的基础,并为网格技术在空间数据库领域的应用提供可靠依据.
参考文献:
[1]钟杨俊,吴为波.网格空间数据库副本优化算法比较与仿真试验[J]. 江西理工大学学报,2010,31(3):56-59.
[2]徐志伟,冯百名,李伟.网格计算技术[M]. 北京: 电子工业出版社, 2005. 279-292 .
[3]胡运权,郭耀煌.运筹学教程（第二版）[M]. 北京: 清华大学出版社, 2003.
[4]张伟哲,方滨兴.基于信任QoS增强的网格服务调度算法[J]. 计算机学报,2006,29(7) :1157-1166.
[5]郁志辉,陈渝,刘鹏.网格计算[M]北京:清华大学出版社2002.
[6]Li MA,Santen PV,Walker DW.Grid:”a service-oriented model for theSemantic Grid”.Future Generation Computer Systems,2004,20:7-18.
|
