基于数据依赖性和访问量的云数据分配存储的优化方法及系统

1.一种基于数据依赖性和访问量的云数据分配存储的优化方法，其特征在于：
基于数据依赖性的定义：
定义1、数据集的集合D＝{di|i＝1,2,...,|D|}，其中：di表示第i个数据集，|D|表示D中数据集的个数，|di|表示数据集的大小；di分为固定数据集和非固定数据集；固定数据集为有固定数据中心的数据集，即需要特定存储位置的数据集；非固定数据集为无固定数据中心的数据集，即不需要特定存储位置的数据集；
定义2、数据中心集合M＝{mi|i＝1,2,...,|M|}，其中：mi表示第i个数据中心，|M|表示数据中心的个数，|mi|表示第i个数据中心存储空间的大小；
定义3、count(Ti∩Tj)，其中：Ti和Tj分别表示数据集上的任务集，count(Ti∩Tj)表示任务集Ti和任务集Tj共有的任务数量；
定义4、数据依赖性用数据相关度衡量，包括数据集之间的相关度，以及数据集与数据中心的相关度，定义如下：
(1)数据集di和dj之间的相关度定义为：
其中，FD表示固定数据集，NFD表示非固定数据集；同时，每一个数据集均有一个属性depLink，depLink定义为
depLink(i)＝{＜di,dep(i,j)＞|j≠i}，根据dep(i,j)的大小形成降序链表；
(2)数据集dk与数据中心mm之间的相关度定义为：
定义5、定义调度任务Tk在数据中心mm上执行引起的传输开销为：
thansCostmk＝[size(DSk)-size(DSk∩DSm)+size(DS'gen∩DS'm)]
其中size(DS)表示DS中所有数据集大小的和，DSk是Tk需要用的数据集，DSm包含数据中心mm上的所有数据集，DS’gen是Tk执行后产生的数据集，DS'm表示DS'gen中应该放在数据中心mm上的数据集；
采用如下优化方法：
(1)初始阶段的数据分配
a：原始数据中的固定数据集分配到相应数据中心；计算非固定数据集中每一个数据集di与其他数据集之间的相关度并加入至该数据集di的属性链表中；
b：依次分配每一个非固定数据集，选择与之相关度最大的数据集；若选择出的相关度最大的数据集为固定数据集或非固定数据集已分配，且选出的相关度最大的数据集所分配到的数据中心的存储空间足够，那么就将该非固定数据集分配到该数据中心；若选择出的相关度最大的数据集为非固定数据集且还未分配，选择计算能力最强且空间足够的数据中心进行分配；若均无法分配则放置等待队列中；
c：对等待队列中的数据集进行分配，依次选择计算能力最强且存储空间足够的数据中心进行分配，直到放置完成为止；
(2)运行阶段的数据分配
a：根据传输开销将任务调度到传输开销最小的数据中心执行；
b：执行完毕后若新产生任务与中间数据集，则首先更新任务集合，然后根据中间数据集与数据中心的相关度，选择相关度最大的数据中心放置中间数据集。

基于数据依赖性和访问量的云数据分配存储的优化方法及\n系统\n技术领域\n[0001] 本发明涉及一种基于数据依赖性和访问量的云数据分配存储的优化方法，特别是涉及一种实现上述方法的系统。\n背景技术\n[0002] 随着大数据时代的来临，在许多领域计算的数据量已经从TB级到PB级，而随着云计算的发展，其高效的特点为工作流提供了一个新思路。但是大规模的数据分配也同样存在着许多挑战，不同于传统的分布式网络，云计算采用的是廉价的虚拟化集群，硬件已经不再是数据分配所应该考虑的因素。大规模数据存在着依赖性，同时数据在单位时间的访问量是固定的，但是在各个单位时间的访问量一般是变化的，如果不考虑访问量，可能存在负载不均衡，造成系统瓶颈。因此，云计算动态存储的优化主要是解决数据访问量变化带来的负载不均衡问题，同时利用大规模数据间的依赖性来提高访问效率。\n[0003] 目前数据动态分配算法虽然能考虑访问量带来的负载不均衡问题，但是对数据直接的相关性考虑较少，随着数据量的增大，访问效率大大提高，因此在一定程度上还有较大的改进空间。\n发明内容\n[0004] 有鉴于此，本发明的目的在于提供一种基于数据依赖性和访问量的云数据分配存储的优化方法，能提高访问效率。\n[0005] 本发明还提供一种基于数据依赖性和访问量的云数据分配存储的优化系统，能提高访问效率。\n[0006] 为了达成上述目的，本发明的解决方案是：\n[0007] 一种基于数据依赖性和访问量的云数据分配存储的优化方法，基于数据依赖性的定义：\n[0008] 定义1、数据集D＝{di|i＝1,2,...,|D|}，其中：di表示第i个数据集，|D|表示数据级个数，|di|表示数据集的大小；di分为固定数据集和非固定数据集；固定数据集为有固定数据中心的数据集，即需要特定方位的数据集；非固定数据集为无固定数据中心的数据集，即不需要特定方位的数据集；\n[0009] 定义2、数据中心集合M＝{mi|i＝1,2,...,|M|}，其中：mi表示第i个数据中心，|M|表示数据中心的个数，|mi|表示第i个数据中心存储空间的大小；\n[0010] 定义3、count(Ti∩Tj)，其中：Ti和Tj分别表示数据集上的任务集，count(Ti∩Tj)表示数据集Ti和数据集Tj共有的任务数量；\n[0011] 定义4、数据依赖性用数据相关度衡量，包括数据集之间的相关度，以及数据集与数据中心的相关度，定义如下：\n[0012] (1)数据集di和dj之间的相关度定义为：\n[0013]\n[0014] 同时，每一个数据集均有一个属性depLink，depLink定义为depLink(i)＝{＜di,depij＞|j≠i}，根据depij的大小形成降序链表；\n[0015] (2)数据集dk与数据中心mm之间的相关度定义为：\n[0016]\n[0017] 定义5、定义调度任务Tk在数据中心mm上执行引起的传输开销为：\n[0018] thansCostmk＝[size(DSk)-size(DSk∩DSm)+size(DS'gen∩DS'm)][0019] 其中size(DS)表示DS中所有数据集大小的和，DSk是Tk需要用的数据集，DSm包含数据中心Mm上的所有数据集，DS'gen是Tk执行后产生的数据集，DS'm表示DS'gen中应该放在Mm上的数据集；\n[0020] 采用如下优化方法：\n[0021] (1)初始阶段的数据分配\n[0022] a：原始数据中的固定数据集分配到相应数据中心；计算非固定数据集中每一个数据集与其他数据集之间的相关度并加入至其属性链表中；\n[0023] b：依次分配每一个数据集，选择与之相关度最大的数据集；若选择出的数据集固定或非固定已分配，且分配到的数据中心空间足够则进行分配；若选择出的数据集非固定且还未分配，选择计算能力最强且空间足够则进行分配；若均无法分配则放置等待队列中，等待最后阶段分配；\n[0024] c：对等待队列中的数据集进行分配，选择计算能力最强且空间足够的数据中心进行分配，否则找到下一个，直到放置完成为止；\n[0025] (2)运行阶段\n[0026] a：根据传输开销将任务调度到传输开销最小的数据中心执行；\n[0027] b：执行完毕后若新产生任务与数据集，则首先更新任务集合，然后根据数据集与数据中心的相关度，选择相关度最大的数据中心放置中间数据集。\n[0028] 所述运行阶段，对于数据中心空间不足处理如下：\n[0029] a：与所述初始阶段的数据分配相同，但在下面两种情况时如下处理：当与非固定数据集相关度最大的数据集未分配时，将后者放置在前者的物理数据中心中；在分配等待队列中数据时也做相同处理；\n[0030] b：对比每个数据集，若逻辑数据中心与物理数据中心相同，则移动数据集到指定的逻辑数据中心，否则不移动。\n[0031] 一种基于数据依赖性和访问量的云数据分配存储的优化系统，采用如前所述的方法。\n[0032] 采用上述方案后，本发明的基于数据依赖性和访问量的云数据分配存储的优化方法具有以下有益效果：本发明基于访问量和依赖性的数据分配，结合随机游走算法计算数据间的相关性，然后在其基础上，进行数据的分配存储；本发明能很好将随机游走算法和数据相关性结合起来，即将随机游走算法结合两阶段数据分配和任务调度不仅考虑了数据的访问量还考虑了数据的依赖性，大大提高了数据的访问效率。\n[0033] 本发明的基于数据依赖性和访问量的云数据分配存储的优化系统也具有上述有益效果。\n具体实施方式\n[0034] 为了进一步解释本发明的技术方案，下面通过具体实施例来对本发明进行详细阐述。\n[0035] 本发明的基于数据依赖性和访问量的云数据分配存储的优化方法分为初始阶段的数据分配和运行阶段的数据分配，为了便于说明原理，先作如下定义：\n[0036] 1、数据集D＝{di|i＝1,2,...,|D|}，其中：di表示第i个数据集，|D|表示数据集个数，|di|表示数据集的大小；di分为固定数据集FD和非固定数据集NFD；固定数据集FD：为有固定数据中心的数据集，即需要特定方位的数据集；非固定数据集NFD：为无固定数据中心的数据集，即不需要特定方位的数据集。\n[0037] 2、数据中心的集合M＝{mi|i＝1,2,...,|M|}，其中：mi表示第i个数据中心，|M|表示数据中心的个数，|mi|表示第i个数据中心存储空间的大小；\n[0038] 3、count(Ti∩Tj)表示数据集(中心)Ti和数据集(中心)Tj共有的任务数量；Ti和Tj分别表示数据集(数据中心)上的任务集；\n[0039] 4、数据依赖性用数据相关度来衡量，包括数据集之间的相关度，以及数据集与数据中心的相关度，定义如下：\n[0040] (1)数据集di和dj之间的相关度定义为：\n[0041]\n[0042] 同时，每一个数据集均有一个属性depLink，depLink定义为depLink(i)＝{＜di,depij＞|j≠i}，根据depij的大小形成一个降序链表。\n[0043] (2)数据集dk与数据中心mm之间的相关度定义为：\n[0044]\n[0045] 5、传输开销，定义调度任务Tk在数据中心mm上执行引起的传输开销为：\n[0046] thansCostmk＝[size(DSk)-size(DSk∩DSm)+size(DS'gen∩DS'm)][0047] 其中size(DS)表示DS中所有数据集大小的和，这里的DS表达普遍含义，不仅仅指size(DSk)，是泛指所有数据集大小的数据集合；DSk是Tk需要用的数据集，DSm包含数据中心Mm上的所有数据集，DS'gen是Tk执行后产生的数据集，DS'm表示DS'gen中应该放在Mm上的数据集。\n[0048] 本方法的原理分为两个阶段：\n[0049] (1)初始阶段的数据分配\n[0050] 根据数据中心的计算能力与存储能力，在考虑数据集大小的前提下分析数据集之间的相关度，完成初始化阶段的预分配。\n[0051] 在计算数据集之间的相关度时，引入马尔可夫的随机游走理论，作为相关度的补充，从全局角度更为准确地衡量数据集之间的相关度，特别是间接相关的数据集的相关度。\n[0052] (2)运行阶段\n[0053] 由于运行会产生一堆中间数据，所以运行阶段是对中间数据进行分配，在对中间数据进行放置时，若出现数据中心存储时间不足，表明出现了负载不均衡，此时需要对所有数据集进行重新调整。\n[0054] 本发明的优点在于不仅考虑了数据的访问量而且考虑了数据间的依赖性，大大提高了云计算下的访问效率。本发明将随机游走算法和两阶段数据分配结合，极大优化了存储算法。\n[0055] 实施例一\n[0056] (1)初始阶段的数据分配\n[0057] 第一步：原始数据中的固定数据集FD分配到相应数据中心；计算非固定数据集NFD中每一个数据集与其他数据集之间的相关度并加入至其属性链表中；这里的“其他数据集”包括固定数据集和非固定数据集。\n[0058] 第二步：依次分配每一个数据集，选择与之相关度最大的数据集；若选择出的数据集为固定数据集FD或非固定数据集NFD但已分配，且分配到的数据中心空间足够则进行分配；若选择出的数据集非固定且还未分配，选择计算能力最强且空间足够的数据中心则进行分配；若均无法分配则放置等待队列中，等待最后阶段分配；\n[0059] 第三步：对等待队列中的数据集进行分配，选择计算能力最强且空间足够的数据中心进行分配，否则找到下一个，直到放置完成为止；\n[0060] (2)运行阶段\n[0061] 第一步：根据传输开销将任务调度到传输开销最小的数据中心执行；\n[0062] 第二步：执行完毕后若新产生任务与数据集，则首先更新任务集或者说任务集合，然后根据数据集与数据中心的相关度，选择相关度最大的数据中心放置中间数据集；\n[0063] 对于数据中心空间不足处理如下：\n[0064] 第一步：基本与初始化阶段算法相同，只在两种情况下略有不同：当与非固定数据集相关度最大的数据集未分配时，将后者放置在前者的物理数据中心中；在分配等待队列中数据时也做相同处理；\n[0065] 第二步：对比每个数据集，若逻辑数据中心与物理数据中心相同，则移动数据集到指定的逻辑数据中心，否则不移动。\n[0066] 对于数据中心空间不足处理有上面的两步实现，先实现第一步数据中心空间充足，然后进行第二步。\n[0067] 本发明的基于数据依赖性和访问量的云数据分配存储的优化系统，能实现上述方法。\n[0068] 上述实施例并非限定本发明的产品形态和式样，任何所属技术领域的普通技术人员对其所做的适当变化或修饰，皆应视为不脱离本发明的专利范畴。