本发明公开了一种基于文件存储动态聚合的优化方法，该优化方法通过将文件动态组合，获取节点经常访问的文件的副本并打包存储于本地节点，减少节点远程读取文件的次数，降低用户数据访问延迟，具体步骤为：基于数据主本判定是否数据交叠，基于副本放置的最优化算法，基于存储空间的优化算法，存储请求文件。本发明选择被复制的副本不仅在当前耗费代价最小,在以后的时间内耗费代价也为最小。
1.一种基于文件存储动态聚合的优化方法，其特征在于该优化方法通过将文件动态组合，获取节点经常访问的文件的副本并打包存储于本地节点，减少节点远程读取文件的次数，降低用户数据访问延迟，具体步骤如下：
1）基于数据主本判定是否数据交叠，检查用户发出的请求文件是否在本地节点，有数据交叠，则该请求文件存在本地节点；无数据交叠时，则进入步骤2）；基于数据主本判定是否数据交叠算法如下：设系统中共有n个节点S＝{S1,S2,…Sn}，每个节点含有m个文件，用户在访问时，对某一节点发出文件请求，假设请求包含多个文件，该请求可以表示为一个文件集合D＝{d1,…dk…dp}；
定于节点Si有数据主本Ri，那么由Ri生成的集合R即为需要复制的对象R＝{Ri;1≤i≤n}；设请求文件的数据主本为Rj，当用户访问时，对任意的Ri和Rj,可有两种情况： 或者 即Ri与Rj可能有交叠数据也可能没有交叠数据；
当 即有数据交叠时，该请求文件存在本地节点；当 即
无数据交叠时，进入步骤2）；将交迭数据内容用集合Rij表示：Rij＝Ri∩Rj，则：即使当Ri和Rj在同一个站点都存在时不进行交叠数据重复传播；
2）基于副本放置的最优化算法，检查本地是否用足够的存储空间容纳请求文件，有存储空间，则选择一个耗费代价最低的远程节点获取该请求文件副本，代价包含文件传输时间和在远程节点上的排队时间；无存储空间，则转步骤3）；基于副本放置的最优化算法如下：对于某个文件i，假设其副本使用代价为Zi，其中，创建副本的成本为Z1，访问副本的费用为Z2，正常数αi和βi表示创建和访问副本在总代价中所占的权重,则Zi＝αiZ1+βiZ2；
副本放置策略就是在满足规定的约束条件下，使得副本创建与访问的代价总和Z＝∑Zi最小；
假设创建副本的站点i的存储空间为Si,则所有站点平均存储空间为 而
假设：Ri表示在某段时间内对站点i的某个副本的请求次数，站点j访问副本站点i的一次费用为Cij，可用站点i与j之间的最短路径时间表示，那么Z2＝RiCij；即文件请求次数越多，函数Z2值越大；若Ri＝0，即站点未发出对副本文件的访问请求，那么它就不产生访问副本的费用；根据上述分析有因此,副本放置问题可转化为如下最优化问题：
xij-yj≤0(i＝1，…,n;j＝1，…，n)(5)
其中，目标函数(2)使得各站点的副本创建成本加上各请求站点到与它最近的副本存放站点的成本加权总和最小，αi和βi的大小是经验值，根据副本存储空间和副本请求次数对响应时间的影响程度来设置；约束条件(3)表示可以创建的副本数目为p个；约束条件(4)表示每个请求站点只对应惟一的一个副本站点为它服务；约束条件(5)表示如果副本位于站点j，那么站点i的副本请求只能指派到站点j；
计算在K时间周期内的传输代价，以决定是否重新放置副本来换取最优的平均响应时间；因此，新的目标函数由式(2)更改为与式(2)相比，新的目标函数式(6)中增加了一项调整成本ajbj的累加，实现对K时间周期内的迭代计算，每个变元符号添加了一个上脚标(k)；其中，若在K周期内站点j的副本需要重新放置，则aj＝1，否则aj＝0；bj表示在K周期内将离站点j最近的站点的副本传输到站点j的成本；
3）基于存储空间的优化算法，计算节点远程读取请求文件的次数t1；计算本地节点存储的所有文件中读取最少的文件的次数t2，若t1>t2，则删除后者并腾出空间存储请求文件；
文件fi相对于作业jk的相关度定义为作业jk访问过fi的总次数，表示为文件fi相对于一组作业本地集合J＝(J1,J2,…,Jn)的相关度定义为作业集合J中的作业访问过文件fi的总次数，即若将本地运行的作业集合表示为Jlocal，文件fi相对于本地作业集Jlocal的相关度记为则文件动态组合的副本复制策略的目标是尽可能保留具有较高Glocal的文件存储在本地，并删除具有较低Glocal的文件，为新副本的创建腾出空间。
基于文件存储动态聚合的优化方法
技术领域
[0001] 本发明属于分布式存储领域，具体地说是一种基于文件存储动态聚合的优化方法。
背景技术
[0002] 分布式存储建立了海量数据的一体化存储、处理、访问、传输与服务的架构和异构分布环境，数据的复制不仅可以提高数据访问的效率，而且能提高系统的负载均衡性和可靠性。
[0003] 传统复制方法是将一个数据主本复制给不同站点的副本，此情况存在原因是过去或现在的某些复制需求以及处理流程比较简单。随着数据复制技术的发展，情况发生了许多变化，在同一数据源对象上可划分出不同的复制源副本，这些不同复制源副本独立具有自己的多个副本，这种情况称为“多分割副本复制”(Multi-Intersected Copy Replication，简称MICR)。尽管针对多分割副本复制的研究已经出现，但仍有部分问题没有解决，主要是未修改的主本数据不进行传播和并行链路的多分割副本复制问题。
[0004] 另外，基于经济学模型的复制策略，是按照反向拍卖协议确定副本创建位置及进行副本选择，它将数据传输时间作为拍卖的价格指标。该模型在评估数据复制价值时存在这样的问题：节点往往根据自身利益进行决策，因而不一定得到全局最佳效益。
发明内容
[0005] 为了使分布式存储的整体性能达到最优，本发明的目的是提供一种基于文件存储动态聚合的优化方法，该优化方法选择被复制的副本不仅在当前耗费代价最小, 在以后的时间内耗费代价也为最小，得到全局最佳效益，减少节点远程读取文件的次数，降低用户数据访问延迟。
[0006] 本发明的目的是通过以下技术方案来实现的：
[0007] 一种基于文件存储动态聚合的优化方法，其特征在于该优化方法通过将文件动态组合，获取节点经常访问的文件的副本并打包存储于本地节点，减少节点远程读取文件的次数，降低用户数据访问延迟，具体步骤如下：
[0008] 1）基于数据主本判定是否数据交叠，检查用户发出的请求文件是否在本地节点，有数据交叠，则该请求文件存在本地节点；无数据交叠时，则进入步骤2）；
[0009] 2）基于副本放置的最优化算法，检查本地是否用足够的存储空间容纳请求文件，有存储空间，则选择一个耗费代价最低的远程节点获取该请求文件副本，代价包含文件传输时间和在远程节点上的排队时间；无存储空间，则转步骤3）。
[0010] 3）基于存储空间的优化算法，计算节点远程读取请求文件的次数t1；计算本地节点存储的所有文件中读取最少的文件的次数t2，若t1> t2，则删除后者并腾出空间存储请求文件。
[0011] 本发明中，基于数据主本判定是否数据交叠的算法如下：
[0012] 设系统中共有n个节点 ，每个节点含有m个文件，用户在访问时，对某一节点发出文件请求，假设请求包含多个文件，该请求可以表示为一个文件集合。
[0013] 定于节点 有数据主本 ，那么由 生成的集合 即为需要复制的对象。设请求文件的数据主本为 ，当用户访问时，对任意的 和 , 可有两种情况： 或者 ，即 与 可能有交叠数据也可能没有交叠数据。
[0014] 当 ，即有数据交叠时，该请求文件存在本地节点。当 ，即无数据交叠时，进入内容2。这里将交迭数据内容用集合 表示： ，由此可推出：
，这样描述的目的是使当 和 在同一个站点都存在时不进行交
叠数据重复传播。
[0015] 基于副本放置的最优化算法如下：
[0016] 对于某个文件 ，假设其副本使用代价为 ，其中，创建副本的成本为 ，访问副本的费用为 ，正常数 和 表示创建和访问副本在总代价中所占的权重,则。副本放置策略就是在满足规定的约束条件下，使得副本创建与访问的代价总和 最小。
[0017] 假设创建副本的站点 的存储空间为 ,则所有站点平均存储空间为，而 反映了平均存储空间与站点 的存储空间的比值。
[0018] 假设： 表示在某段时间内对站点 的某个副本的请求次数，站点 访问副本站点的一次费用为 (可用站点 与 之间的最短路径时间表示)，那么 。可以看出，文件请求次数越多，函数 值越大；若 ，即站点未发出对副本文件的访问请求，那么它就不产生访问副本的费用。根据上述分析有
[0019] (1)
[0020] 因此,副本放置问题可转化为如下最优化问题：
[0021] 目标函数：
[0022] (2)
[0023] 约束条件：
[0024] (3)
[0025] (4)
[0026] (5)
[0027] 其中，目标函数(2)使得各站点的副本创建成本加上各请求站点到与它最近的副本存放站点的成本加权总和最小， 和 的大小是经验值，根据副本存储空间和副本请求次数对响应时间的影响程度来设置；约束条件(3)表示可以创建的副本数目为 个；约束条件(4)表示每个请求站点只对应惟一的一个副本站点为它服务；约束条件(5)表示如果副本位于站点 ，那么站点 的副本请求只能指派到站点 。
[0028] 计算在 时间周期内的传输代价，以决定是否重新放置副本来换取最优的平均响应时间。因此，新的目标函数由式(2)更改为
[0029] (6)
[0030] 与式(2)相比，新的目标函数式(8)中增加了一项调整成本 的累加，实现对时间周期内的迭代计算，每个变元符号添加了一个上脚标 。其中，若在 周期内站点的副本需要重新放置，则 ，否则 ； 表示在 周期内将离站点 最近的站点的副本传输到站点 的成本。
[0031] 基于存储空间的优化算法如下：
[0032] 1、文件fi相对于作业jk的相关度定义为作业jk访问过fi的总次数，表示为 。
[0033] 2、文件fi相对于一组作业本地集合 的相关度定义为作业集合J中的作业访问过文件fi的总次数，即 。
[0034] 3、 若将本地运行的作业集合表示为Jlocal，文件fi相对于本地作业集Jlocal的相关度记为 。则文件动态组合的副本复制策略的目标是尽可能保留具有较高Glocal的文件存储在本地，并删除具有较低Glocal的文件，为新副本的创建腾出空间。
[0035] 云存储系统中，会出现多个文件经常被集体访问的情况，无疑这些文件间具有较强的关联度，然而这些文件可能分布在多个节点上。本发明选择被复制的副本不仅在当前耗费代价最小, 在以后的时间内耗费代价也为最小，得到全局最佳效益。
[0036] 本发明算法通过将文件动态组合，获取节点经常访问的多个文件的副本并打包存储于本地节点，减少节点远程读取文件的次数，最终达到降低用户数据访问延迟的目标。
附图说明
[0037] 图1为本发明实的结构框图。
具体实施方式
[0038] 一种本发明所述的基于文件存储动态聚合的优化方法，该优化方法通过将文件动态组合，获取节点经常访问的文件的副本并打包存储于本地节点，减少节点远程读取文件的次数，降低用户数据访问延迟，具体步骤如下：
[0039] 1）基于数据主本判定是否数据交叠，检查用户发出的请求文件是否在本地节点，有数据交叠，则该请求文件存在本地节点；无数据交叠时，则进入步骤2）；
[0040] 设系统中共有n个节点 ，每个节点含有m个文件，用户在访问时，对某一节点发出文件请求，假设请求包含多个文件，该请求可以表示为一个文件集合。
[0041] 定于节点 有数据主本 ，那么由 生成的集合 即为需要复制的对象。设请求文件的数据主本为 ，当用户访问时，对任意的 和 , 可有两种情况： 或者 ，即 与 可能有交叠数据也可能没有交叠数据。
[0042] 当 ，即有数据交叠时，该请求文件存在本地节点。当 ，即无数据交叠时，进入内容2。这里将交迭数据内容用集合 表示： ，由此可推出：
，这样描述的目的是使当 和 在同一个站点都存在时不进行交
叠数据重复传播。
[0043] 2）基于副本放置的最优化算法，检查本地是否用足够的存储空间容纳请求文件，有存储空间，则选择一个耗费代价最低的远程节点获取该请求文件副本，代价包含文件传输时间和在远程节点上的排队时间；无存储空间，则转步骤3）。
[0044] 对于某个文件 ，假设其副本使用代价为 ，其中，创建副本的成本为 ，访问副本的费用为 ，正常数 和 表示创建和访问副本在总代价中所占的权重,则。副本放置策略就是在满足规定的约束条件下，使得副本创建与访问的代价总和 最小。
[0045] 假设创建副本的站点 的存储空间为 ,则所有站点平均存储空间为，而 反映了平均存储空间与站点 的存储空间的比值。
[0046] 假设： 表示在某段时间内对站点 的某个副本的请求次数，站点 访问副本站点的一次费用为 (可用站点 与 之间的最短路径时间表示)，那么 。可以看出，文件请求次数越多，函数 值越大；若 ，即站点未发出对副本文件的访问请求，那么它就不产生访问副本的费用。根据上述分析有
[0047] (1)
[0048] 因此,副本放置问题可转化为如下最优化问题：
[0049] 目标函数：
[0050] (2)
[0051] 约束条件：
[0052] (3)
[0053] (4)
[0054] (5)
[0055] 其中，目标函数(2)使得各站点的副本创建成本加上各请求站点到与它最近的副本存放站点的成本加权总和最小， 和 的大小是经验值，根据副本存储空间和副本请求次数对响应时间的影响程度来设置；约束条件(3)表示可以创建的副本数目为 个；约束条件(4)表示每个请求站点只对应惟一的一个副本站点为它服务；约束条件(5)表示如果副本位于站点 ，那么站点 的副本请求只能指派到站点 。
[0056] 计算在 时间周期内的传输代价，以决定是否重新放置副本来换取最优的平均响应时间。因此，新的目标函数由式(2)更改为
[0057] (6)
[0058] 与式(2)相比，新的目标函数式(8)中增加了一项调整成本 的累加，实现对时间周期内的迭代计算，每个变元符号添加了一个上脚标 。其中，若在 周期内站点的副本需要重新放置，则 ，否则 ； 表示在 周期内将离站点 最近的站点的副本传输到站点 的成本。
[0059] 3）基于存储空间的优化算法，计算节点远程读取请求文件的次数t1；计算本地节点存储的所有文件中读取最少的文件的次数t2，若t1> t2，则删除后者并腾出空间存储请求文件。
[0060] 基于存储空间的优化算法如下：
[0061] 1、文件fi相对于作业jk的相关度定义为作业jk访问过fi的总次数，表示为 。
[0062] 2、文件fi相对于一组作业本地集合 的相关度定义为作业集合J中的作业访问过文件fi的总次数，即 。
[0063] 3、 若将本地运行的作业集合表示为Jlocal，文件fi相对于本地作业集Jlocal的相关度记为 。则文件动态组合的副本复制策略的目标是尽可能保留具有较高Glocal的文件存储在本地，并删除具有较低Glocal的文件，为新副本的创建腾出空间。
[0064] 本发明选择被复制的副本不仅在当前耗费代价最小, 在以后的时间内耗费代价也为最小，得到全局最佳效益。
