CN111538681A - Spark平台下基于最大化缓存增益的缓存替换方法 - Google Patents

Abstract

本发明公开了一种Spark平台下基于最大化缓存增益的缓存替换方法，该方法首先通过对有向无环图中各种操作的依赖性进行分析，提出了一个用于衡量缓存收益的缓存增益模型，目标是使其缓存增益最大化。然后在作业到达率已知的情况下采用取整舍入方法对该受背包约束的最大化问题求得离线最优近似解。最后在作业到达率未知的情况下，采用投影梯度上升方法获取每个缓存项应放置在缓存中的概率，从而获得满足缓存增益最大化的在线自适应缓存替换策略。此方法充分利用了系统资源，缩短了Spark应用的执行时间，提高了缓存命中率。

Description

Spark平台下基于最大化缓存增益的缓存替换方法

技术领域

本发明涉及计算机大数据技术领域，具体涉及一种Spark 平台下基于最大化缓存增益的缓存替换方法。

背景技术

随着大数据分析和云计算的兴起，基于集群的大规模数据 处理已成为许多应用程序和服务的常见范例。数据并行计算框 架如Apache Spark常常被用于大规模执行此类数据处理。在 此类数据处理过程中大量输入数据集被运行，其中执行的作业 也包括数百个相同的并行子任务。Spark计算框架处理这些大 量数据所需的时间和资源是巨大的。然而，在这样的分布式环 境中执行的作业通常具有显着的计算重叠，即处理相同数据的 不同作业可能涉及共同的中间计算，这种计算重叠在实践中是 自然产生的。最近来自行业内的数据记录显示，微软生产集群 中有40％～60％的中间结果重计算工作，而Cloudera集群中高 达78％的工作涉及数据的重新访问。

Spark最近已成为最有效率的基于内存的分布式数据处理 平台之一，其中弹性分布式数据集RDD是一种基于分布式内 存的抽象数据结构。RDD可以跨越集群中多个节点而将数据 存储在分布式内存中。Spark并行计算框架是以非自动方式在 其框架中实现缓存功能的，提交作业的开发人员决定需要缓存 的中间计算结果，即决定哪些RDD需要被存储在基于RAM 的缓存中。当RAM缓存已满后，进行缓存驱逐时使用最常见 的LRU缓存驱逐策略驱逐某些RDD。当然开发人员也可以选 择在Hadoop分布式文件系统(HDFS)上存储被驱逐的RDD， 但需要额外的开销才能在HDFS上执行写操作。众所周知，缓 存在RAM中的RDD可以被更快地检索重利用，但是由于开 发人员没有显式缓存RDD，或者已经缓存而随后被驱逐，都会发生缓存未命中现象。在其中任何一种情况下，Spark都不 得不承受大量的计算开销，即如果请求的RDD既不在RAM 中也不存储在Hadoop分布式文件系统中，Spark会从起点开 始进行重新计算。总的来说，缓存未命中现象会导致额外的延 迟，无论是从Hadoop分布式文件系统读取还是完全重新计算 丢失的RDD。如何在Spark平台下制定有效的缓存替换策略成为亟待解决的问题。目前关于Spark平台下缓存替换的研究 普遍存在以下几个问题：①在进行缓存替换时考虑因素过于单 一；②处理大规模密集型应用程序时缓存结果的不确定性；③ 缓存策略选取不当会极大降低Spark应用执行效率。

发明内容

本发明的目的就是针对现有技术的缺陷，提供一种Spark 平台下基于最大化缓存增益的缓存替换方法，考虑由于缓存而 减少的总工作量、作业到达率、缓存容量和缓存项的重计算成 本等因素，有效降低Spark应用的平均执行时间，同时提高系 统内存利用率与缓存命中率。

为实现上述目的，本发明所设计的Spark平台下基于最大 化缓存增益的缓存替换方法包括如下步骤：

1)通过对Spark作业特有的有向无环图DAG进行分析， 制定缓存增益目标函数，其中考虑了作业到达率λ_G、缓存容量 大小K和缓存项的重计算成本t_v等因素；

2)在作业到达率已知的情况下，采用取整舍入方法求得 缓存增益函数的最优近似解，通过计算结点v被缓存的边缘概 率y_v将缓存增益函数转化为函数F(Y)，从而构造出缓存增益 函数F(x)的凸松弛，由于此时目标函数的约束条件不是凹松 弛，因此将转化函数F(Y)近似定义为函数L(Y)；

3)通过找到两个分数变量y_v和y_v'对近似函数L(Y)的最优 解Y^**执行舍入过程，最终产生一个近似整数解x'，并证明该 近似整数解的缓存增益收敛于其最优解缓存增益的1-1/e近 似范围内；

4)在作业到达率未知的情况下，通过将时间划分为相等 长度T＞0的时间段，计算每个结点v∈V被缓存的概率 p_v∈[0,1]^V及结点后期重计算成本t_v，从而生成近似函数L(Y)的 一个关于状态向量p的子梯度

的无偏估计；

5)收集一段时间内每个缓存项的被访问信息，随着作业 的执行对某个缓存项应放置在缓存中的概率进行自适应调整， 根据以上的无偏估计值，在每个测量周期结束时自适应调整状 态向量p；

6)计算每个缓存项应放置在缓存中的概率在每个时间段 内的变化平均值

并采用概率舍入方法将每个变化平均值 舍入为整数解；

7)根据上述状态向量p的变化平均值

的排序结果做出 缓存决策，即通过建立结点权重替换模型驱逐低分结点和插入 新的高分结点，从而产生一个新的满足背包约束x^(k)∈{0,1}^|V|的 缓存放置策略。

优选地，所述步骤1)中Spark应用预期的总工作量具体 表现形式为：

其中，G′表示要在Spark并行计算框架上运行的所有可能 作业的集合，作业G∈G′根据随机平稳过程以λ_G＞0的速率到 达。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重 新生成结点v所花费的时间。缓存增益函数具体表现形式为：

其中，G′表示要在Spark并行计算框架上运行的所有可能作业 的集合，作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。 有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生 成结点v所花费的时间。结点u是结点v的后继结点即子结点， x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。若结点v 被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。根据Spark并行 计算框架的作业处理流程可知，若结点v被缓存，当后续处理 过程中再次利用到该结点的输出结果时，无需重新计算该结点 及该结点的任何前驱结点。在最大化此函数的求解过程中受缓 存容量大小的约束。Xu表示子节点u是否被缓存，若被缓存 Xu＝1,若不被缓存Xu＝0；succ(v)是节点v的子节点，后续节 点(子代节点)集合。在该公式中表示u是v的子节点的情况 下进行计算。

优选地，所述步骤3)中采用取整舍入方法求得缓存增益 函数的最优近似解的具体步骤包括：

3.1)计算结点v被缓存的边缘概率y_v，计算方式为：

y_v＝P_ψ[x_v＝1]＝E_ψ[x_v]

其中ψ表示相应的联合概率分布，P_ψ[·]表示结点v被缓存 或者未被缓存的概率，E_ψ[·]表示结点v被缓存或者未被缓存的 期望，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。 若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。

3.2)为了构造缓存增益函数F(x)的凸松弛，将缓存增益 函数转化为函数F(Y)，计算方式如下：

其中作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。 有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生 成结点v所花费的时间。结点u是结点v的后继结点即子结点， x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。若结点v 被缓存则x_v＝1，如果结点v不被缓存则x_v＝0，E_ψ[·]表示结点v 被缓存或者未被缓存的期望。

3.3)此时目标函数限制条件转化为Sub.to:y_v∈[0,1]，由于 此多线性松弛不是凹松弛，因此将转化函数F(Y)近似定义为 函数L(Y)：

其中作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。 有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生 成结点v所花费的时间。结点u是结点v的后继结点即子结点， 此时y_v,y_u∈[0,1]。

3.4)对近似函数L(Y)的最优解Y^**执行舍入过程，给定一 个分数解Y，则找到两个分数变量y_v和y_v'，使此解在这两个分 数变量之间变化。

3.5)将至少一个分数变量取值为0或1，并且满足自变量 取Y'时的缓存增益不能少于自变量取Y时的缓存增益。

3.6)不断重复步骤3.4)与3.5)，直到不存在分数变量， 最终产生一个近似整数解x'。

优选地，所述步骤4)中近似函数L(Y)的关于状态向量p 的子梯度的无偏估计z_v的计算方法为：

4.1)将时间划分为相等长度T＞0的时间段，在此期间收 集不同结点的访问统计信息，C_G'表示结点历史访问记录，C_G表示结点当前作业的结点访问记录。

4.2)根据不同结点的访问统计信息计算每个结点v∈V(每 一个RDD)被缓存的概率p_v∈[0,1]^|V|。

4.3)当每一个长度为T的时间段结束时，需要调整每个结 点的状态向量p＝[p_v]_v∈V∈[0,1]^|V|。

4.4)使用在一段时间内收集的结点访问信息计算结点后 期重计算成本t_v，计算方式如下：

t_v＝∑_v∈Vc_v(x_v+∑u∈_succ(v)x_u≤1)

其中函数(A)的作用是当不等式A成立时，(A)为1，否 则(A)为0。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生成结点v所花费的时间。结点u是结点v的后继结点 即子结点，x_v∈{0，1}为定义的缓存策略，表示结点v是否被缓存。 若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。

4.5)根据重计算成本t_v得出近似函数L(Y)的一个关于状 态向量p的子梯度

的无偏估计，计算方式如下：

其中Γ_v代表在一个持续时间段T内在结点v∈V处以上述 方式计算的重计算成本t_v的集合。

优选地，所述步骤5)中在第k个测量周期结束时，状态 向量p自适应调整方式的计算方法为：

p^(k+1)←Φ_Θ(p^(k)+γ^(k)*z(p^(k)))

其中γ^(k)＞0是一个增益因子，p^(k)为状态向量p在第k个测 量周期的状态，Φ_Θ是放松约束集Θ对凸多面体的投影，因此 其可以在多项式时间内被计算。p_v∈[0,1]^|V|表示每个结点v∈V 被缓存的概率，s_v表示结点v∈V的输出数据大小，以MB为单 位。

优选地，所述步骤6)具体包括以下步骤：

6.1)计算每个缓存项应放置在缓存中的概率在每个时间 段内的变化平均值

6.2)在每一个时间段T结束时，采用概率舍入方法将变化 平均值

舍入为整数解；

6.3)根据上述状态向量p的变化平均值

的排序结果做 出缓存决策，即通过建立结点权重替换模型驱逐低分结点和插 入新的高分结点，从而产生一个新的满足背包约束x^(k)∈{0,1}^|V|的缓存放置策略；

6.4)证明此整数解的缓存增益可以保证在离线缓存决策 最优解x^*缓存增益的1-1/e近似范围内。

优选地，所述步骤6)中每个缓存项应放置在缓存中的概 率在每个时间段内的变化平均值

的计算方式为：

其中k表示第k个测量周期，p^(l)表示状态向量p在第l个 测量周期的状态，γ^(l)＞0是一个增益因子。此时变化平均值满 足

并且是Θ中所有结点的凸组合。

Spark平台下传统的缓存替换策略在进行缓存替换时考虑 因素过于单一，导致这些缓存替换策略在某些特殊场景下并不 适用。另外当Spark处理大规模密集型应用程序时，会为整个 计算过程选择多个缓存策略。如果用户自行选择存储策略进行 计算，结果将充满不确定性，中间结果是否应该缓存完全取决 于用户经验。这种不确定性无法充分利用Spark的高性能优势。

本发明通过分析Spark作业有向无环图中各操作间存在依 赖性的特点提出来基于最大化缓存增益的缓存替换方法。本调 度方法首先通过对有向无环图中各种操作的依赖性进行分析， 提出了一个用于衡量缓存收益的缓存增益模型，目标是使其缓 存增益最大化。然后在作业到达率已知的情况下采用取整舍入 方法对该受背包约束的最大化问题求得离线最优近似解。最后 在作业到达率未知的情况下，采用投影梯度上升方法获取每个缓存项应放置在缓存中的概率，从而获得满足缓存增益最大化 的在线自适应缓存替换策略。此方法充分利用了系统资源，缩 短了Spark应用的执行时间，提高了缓存命中率。

附图说明

图1为本发明Spark平台下作业到达率已知时基于最大化 缓存增益的缓存替换方法的流程图。

图2为本发明Spark平台下作业到达率未知时基于最大化 缓存增益的缓存替换方法的流程图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步的详细说 明，便于清楚地了解本发明，但它们不对本发明构成限定。

如图1所示，本发明提出的Spark平台下基于最大化缓存 增益的缓存替换方法，是以当前Spark平台下的默认缓存替换 方法为基础，结合Spark任务执行的特点而提出来的。如图1 所示，本算法包括如下步骤：

1)通过对Spark作业特有的有向无环图DAG进行分析， 制定缓存增益目标函数，其中考虑了作业到达率、缓存容量大 小和缓存项的重计算成本等因素，具体步骤包括：

1.1)计算重新生成结点v所花费的时间c_v，其中包括根据 父结点重新计算和从磁盘读取两种情况，所花费的时间分别为 c_v′和c_v ^*，计算方式如下：

c_v′＝endTime-startTime

c_v ^*＝(SPM+DPM)·s_v

c_v＝min(c_v′,(SPM+DPM)·s_v)

其中时间c_v为根据父结点重新计算的时间和从磁盘读取 所花费的时间的最小值，startTime与endTime表示父结点完成 操作的开始时间与结束时间，SPM与DPM分别表示每个结点 的每MB数据进行序列化和反序列化所花费的时间，s_v表示结 点v的输出数据所占缓存空间的大小。

1.2)若所有结点都没有被缓存，计算作业G的总工作量 W(G(V,E))：

其中有向无环图中的结点v用集合V表示，即v∈V，c_v表 示重新生成结点v所花费的时间。

1.3)计算Spark应用预期的总工作量，计算方式如下：

其中G′表示要在Spark并行计算框架上运行的所有可能 作业的集合，作业G∈G′根据随机平稳过程以λ_G＞0的速率到 达。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重 新生成结点v所花费的时间。

1.4)通过对Spark作业特有的有向无环图DAG进行分析， 制定的衡量缓存增益的目标函数如下所示：

Sub.to:

其中G′表示要在Spark并行计算框架上运行的所有可能 作业的集合，作业G∈G′根据随机平稳过程以λ_G＞0的速率到 达。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重 新生成结点v所花费的时间。结点u是结点v的后继结点即子结 点，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。若 结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。s_v表示结 点v∈V的输出数据大小，以MB为单位，K为给定的缓存空间 大小。

2)在作业到达率已知的情况下，采用取整舍入方法求得 缓存增益函数的最优近似解，具体步骤包括：

2.1)计算结点v被缓存的边缘概率，计算方式为：

y_v＝P_ψ[x_v＝1]＝E_ψ[x_v]

其中ψ表示相应的联合概率分布，P_ψ[·]表示结点v被缓存 或者未被缓存的概率，E_ψ[·]表示结点v被缓存或者未被缓存的 期望，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。 若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。

2.2)为了构造缓存增益函数F(x)的凸松弛，将缓存增益 函数转化为函数F(Y)，计算方式如下：

其中作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。 有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生 成结点v所花费的时间。结点u是结点v的后继结点即子结点， x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。若结点v 被缓存则x_v＝1，如果结点v不被缓存则x_v＝0，E_ψ[·]表示结点v 被缓存或者未被缓存的期望。

2.3)此时目标函数限制条件转化为Sub.to:y_v∈[0,1]，由于 此多线性松弛不是凹松弛，因此将转化函数F(Y)近似定义为 函数L(Y)：

其中作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。 有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生 成结点v所花费的时间。结点u是结点v的后继结点即子结点， 此时y_v,y_u∈[0,1]。

2.4)对近似函数L(Y)的最优解Y^**执行舍入过程，给定一 个分数解Y，则找到两个分数变量y_v和y_v'，使此解在这两个分 数变量之间变化。

2.5)将至少一个分数变量取值为0或1，并且满足自变量 取Y'时的缓存增益不能少于自变量取Y时的缓存增益。

2.6)不断重复步骤2.4)与2.5)，直到不存在分数变量， 最终产生一个近似整数解x'。

3)证明步骤2)中所得缓存增益函数的近似整数解的缓 存增益收敛于其最优解缓存增益的1-1/e近似范围内，如下述 不等式所示：

其中x^*为函数F(x)的最优解，Y^*为函数F(Y)的最优解， Y^**为函数L(Y)的最优解。x'为步骤2)得出的近似整数解。

4)在作业到达率未知的情况下，需要生成近似函数L(Y) 的子梯度无偏估计，具体步骤如下：

4.1)将时间划分为相等长度T＞0的时间段，在此期间收 集不同结点的访问统计信息，C_G'表示结点历史访问记录，C_G表示结点当前作业的结点访问记录。

4.2)根据不同结点的访问统计信息计算每个结点v∈V(每 一个RDD)被缓存的概率p_v∈[0,1]^|V|。

4.3)当每一个长度为T的时间段结束时，需要调整每个结 点的状态向量p＝[p_v]_v∈V∈[0,1]^|V|。

4.4)使用在一段时间内收集的结点访问信息计算结点后 期重计算成本t_v，计算方式如下：

t_v＝∑_v∈Vc_v(x_v+∑_u∈succ(v)x_u≤1)

其中函数(A)的作用是当不等式A成立时，(A)为1，否 则(A)为0。有向无环图中的结点v用集合V表示，即v∈V，c_v表 示重新生成结点v所花费的时间。结点u是结点v的后继结点即 子结点，x_v∈{0，1}为定义的缓存策略，表示结点v是否被缓存。 若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。

4.5)根据重计算成本t_v得出近似函数L(Y)的一个关于状 态向量p的子梯度

的无偏估计，计算方式如下：

其中Γ_v代表在一个持续时间段T内在结点v∈V处以上述 方式计算的重计算成本t_v的集合。

5)收集一段时间内每个缓存项的被访问信息，随着作业 的执行对某个缓存项应放置在缓存中的概率进行自适应调整， 根据以上的无偏估计值，在第k个测量周期结束时，状态向量 p自适应调整方式如下：

p^(k+1)←Φ_Θ(p^(k)+γ^(k)*z(p^(k)))

其中γ^(k)＞0是一个增益因子，p^(k)为状态向量p在第k个测 量周期的状态，Φ_Θ是放松约束集Θ对凸多面体的投影，因此 其可以在多项式时间内被计算。p_v∈[0,1]^|V|表示每个结点v∈V 被缓存的概率，s_v表示结点v∈V的输出数据大小，以MB为单 位。

6)计算每个缓存项应放置在缓存中的概率在每个时间段 内的变化平均值，并采用概率舍入方法将每个变化平均值舍入 为整数解，具体步骤如下：

6.1)每个缓存项应放置在缓存中的概率在每个时间段内 的变化平均值

计算方式如下：

其中k表示第k个测量周期，p^(l)表示状态向量p在第l个 测量周期的状态，γ^(l)＞0是一个增益因子。此时变化平均值满 足

并且是Θ中所有结点的凸组合。

6.2)在每一个时间段T结束时，本发明采用概率舍入方法 将变化平均值

舍入为整数解。

6.3)根据上述状态向量p的变化平均值

的排序结果做 出缓存决策，即通过建立结点权重替换模型驱逐低分结点和插 入新的高分结点，从而产生一个新的满足背包约束x^(k)∈{0,1}^|V|的缓存放置策略。

6.4)证明此整数解的缓存增益可以保证在离线缓存决策 最优解x^*缓存增益的1-1/e近似范围内。

7)通过步骤6)所得到的每个整数解都代表一个新的缓 存策略，基于上述不断调整的概率值不断构造出此时此刻满足 缓存增益最大化的缓存策略。下面详述本发明的研究过程：

Spark并行计算框架是以非自动方式在其框架中实现缓存 功能的，提交作业的开发人员决定需要缓存的中间计算结果， 即决定哪些RDD需要被存储在基于RAM的缓存中。但是在 处理由具有复杂依赖性的操作组成的作业时，确定要缓存哪些 中间结果是一个亟待解决的难题。虽然目前有很多学者对 Spark平台下的缓存替换策略进行研究，但是由于考虑因素单 一及处理大规模密集型应用程序时缓存结果选择的不确定性 使得这些缓存替换策略在某些特殊场景下并不适用。因此在 Spark平台下进行缓存替换操作之前，通过对Spark作业的有 向无环图DAG中各种操作的依赖性进行分析，提出一个衡量 缓存增益的函数模型是必要的。此外通过最大化该缓存增益函 数使得在多种场景下的Spark应用的平均执行时间、系统内存 利用率和缓存命中率都得到有效保证。

缓存替换方法中的相关参数定义

(1)重新生成结点v所花费的时间c_v：时间c_v为根据父结 点重新计算的时间和从磁盘读取所花费的时间的最小值，两种 情况所花费的时间分别为c_v′和c_v ^*，其中startTime与endTime表 示父结点完成操作的开始时间与结束时间，SPM与DPM分别 表示每个结点的每MB数据进行序列化和反序列化所花费的 时间，s_v表示结点v的输出数据所占缓存空间的大小。时间c_v计 算方式如下：

c_v′＝endTime-startTime (1)

c_v ^*＝(SPM+DPM)·s_v (2)

c_v＝min(c_v′,(SPM+DPM)·s_v) (3)

(2)缓存策略x_v∈{0,1}：表示结点v是否被缓存。若结点 v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。

(3)变化平均值

在每个时间段内每个缓存项应放置 在缓存中的概率的变化平均值，计算方式如下：

其中k表示第k个测量周期，p^(l)表示状态向量p在第l个 测量周期的状态，γ^(l)＞0是一个增益因子。此时变化平均值满 足

并且是Θ中所有结点的凸组合。

(4)近似函数L(Y)的关于状态向量p的子梯度

的 无偏估计z_v：

t_v＝∑_v∈Vc_v(x_v+∑_u∈succ(v)x_u≤1) (5)

其中函数(A)的作用是当不等式A成立时，(A)为1，否则(A) 为0。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重 新生成结点v所花费的时间。结点u是结点v的后继结点即子结 点，x_v∈{0，1}为定义的缓存策略，表示结点v是否被缓存。若结 点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。

代表在一个 持续时间段T内在结点v∈V处以上述方式计算的t_v的集合。

(5)各个结点v替换权值Q_v：本发明所提缓存替换方法 主要思想是优先考虑具有高请求率(高梯度分量

)和低 尺寸s_v的结点v，且缓存该节点是否会减少大量的总工作量， 即如果结点v具有较高的替换权值，则该结点应该进入缓存。

其中R_ratve表示结点v∈V的请求率，即近似函数L(Y)对x_v的 偏导数，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。 若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0。s_v表示 结点v∈V的输出数据大小，以MB为单位。G′表示要在Spark 并行计算框架上运行的所有可能作业的集合，作业G∈G′根据 随机平稳过程以λ_G＞0的速率到达。Δ(ω)表示当结点v没有被 缓存时，其执行所有作业过程中总工作量的差异。

本专利提出的Spark环境下基于最大化缓存增益的缓存替 换方法，是以衡量缓存增益为基础结合取整舍入方法和概率舍 入方法而提出来的。本方法首先通过对Spark作业的有向无环 图DAG中各种操作的依赖性进行分析，提出了一个基于缓存 增益概念的数学模型，旨在准确表明由于某种缓存策略而减少 的总工作量，其中每个结点进行操作所花费的时间按照公式 (1)-(3)计算。然后在作业到达率已知的情况下采用取整 舍入方法对该具有背包约束的子模块最大化问题求得离线最 优近似解。在作业到达率未知的情况下，根据公式(4)中的 投影梯度上升方法获取每个RDD应放置在缓存中的概率的变 化平均值。最后对各结点的变化平均值进行排序，并根据公式 (7)-(8)给出的各结点的替换权值确定出满足缓存增益最 大化的在线自适应缓存替换策略，并证明此策略的缓存增益收 敛于离线缓存替换策略最优解缓存增益的1-1/e近似范围内。

调度方法的伪代码描述

由算法的伪代码描述可以看出，第3行在执行每个作业之 后根据第4行的updateCache函数进行缓存内容的更新。由第 34-42行的updateCache函数可以看出该函数综合考虑了结点 历史成本分数和当前成本分数，其首先更新所有被访问的结点 的成本，从而确定以使用衰减率β收集的上述状态向量p的变 化平均值

实现加权移动平均值的计算。由于实验中每个 作业平均有6个阶段(stage)，因此将衰减率β取值为0.6。第 6-22行当以递归方式在每个作业中迭代结点时，调用第23-33 行的辅助函数estimateCost来计算和记录该作业中每个结点的 时间成本，这将被用来确定updateCache函数中的缓存内容。 然后第14-18行遍历每个结点的子结点，一旦其所有子结点准 备就绪，第20行开始访问并计算该结点。最后第41行 updateCache函数通过对状态向量p的变化平均值

进行排 序，设定结点权值替换模型来驱逐低分结点并插入新的高分结 点，从而刷新整个缓存空间。本说明书未作详细描述的内容属 于本领域专业技术人员公知的现有技术。

Claims (7)

1.一种Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于包括以下步骤：

1)通过对Spark作业特有的有向无环图DAG进行分析，制定缓存增益目标函数，其中考虑了作业到达率、缓存容量大小和缓存项的重计算成本因素；

2)在作业到达率已知的情况下，采用取整舍入方法求得缓存增益函数的最优近似解，通过计算结点被缓存的边缘概率将缓存增益函数转化为函数，将转化后的函数定义为近似函数；

3)通过找到两个分数变量和对近似函数的最优解执行舍入过程，最终产生一个近似整数解，并证明该近似整数解的缓存增益收敛于其最优解缓存增益的近似范围内；

4)在作业到达率未知的情况下，通过将时间划分为相等长度的时间段，计算每个结点被缓存的概率及结点后期重计算成本，从而生成近似函数的一个关于状态向量的子梯度的无偏估计；

5)收集一段时间内每个缓存项的被访问信息，随着作业的执行对某个缓存项应放置在缓存中的概率进行自适应调整，根据以上的无偏估计值，在每个测量周期结束时自适应调整状态向量；

6)计算每个缓存项应放置在缓存中的概率在每个时间段内的变化平均值，并采用概率舍入方法将每个变化平均值舍入为整数解；

7)根据上述状态向量的变化平均值的排序结果做出缓存决策，通过建立结点权重替换模型驱逐低分结点和插入新的高分结点，从而产生一个新的满足背包约束的缓存放置策略。

2.根据权利要求1所述的Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于所述步骤1)中Spark应用预期的总工作量具体表现形式为：

其中，G表示Spark作业，G′表示要在Spark并行计算框架上运行的所有可能作业的集合，作业G∈G′根据随机平稳过程以λ_G＞0的速率到达；λ_G是指作业到达率有；向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生成结点v所花费的时间；

缓存增益函数具体表现形式为：

其中，G′表示要在Spark并行计算框架上运行的所有可能作业的集合，作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生成结点v所花费的时间；结点u是结点v的后继结点即子结点，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存；若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0；根据Spark并行计算框架的作业处理流程可知，若结点v被缓存，当后续处理过程中再次利用到该结点的输出结果时，无需重新计算该结点及该结点的任何前驱结点；在最大化此函数的求解过程中受缓存容量大小的约束；

Xu表示子节点u是否被缓存，若被缓存Xu＝1,若不被缓存Xu＝0；

succ(v)是节点v的子节点，后续节点(子代节点)集合。在该公式中表示u是v的子节点的情况下进行计算。

3.根据权利要求2所述的Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于所述步骤3)中采用取整舍入方法求得缓存增益函数的最优近似解的具体步骤包括：

3.1)计算结点v被缓存的边缘概率y_v，计算方式为：

y_v＝P_ψ[x_v＝1]＝E_ψ[x_v]

其中ψ表示相应的联合概率分布，P_ψ[·]表示结点v被缓存或者未被缓存的概率，E_ψ[·]表示结点v被缓存或者未被缓存的期望，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存。若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0；

3.2)为了构造缓存增益函数F(x)的凸松弛，将缓存增益函数转化为函数F(Y)，计算方式如下：

其中作业G∈G′根据随机平稳过程以λ_G＞0的速率到达。有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生成结点v所花费的时间；结点u是结点v的后继结点即子结点，x_v∈{0,1}为定义的缓存策略，表示结点v是否被缓存；若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0，E_ψ[·]表示结点v被缓存或者未被缓存的期望；

3.3)此时目标函数限制条件转化为Sub.to:y_v∈[0,1]，将转化函数F(Y)近似定义为函数L(Y)：

其中作业G∈G′根据随机平稳过程以λ_G＞0的速率到达；有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生成结点v所花费的时间；结点u是结点v的后继结点即子结点，此时y_v,y_u∈[0,1]；

3.4)对近似函数L(Y)的最优解Y^**执行舍入过程，给定一个分数解Y，找到两个分数变量y_v和y_v'，使此解在这两个分数变量之间变化。；

3.5)将至少一个分数变量取值为0或1，并且满足自变量取Y'时的缓存增益不能少于自变量取Y时的缓存增益；

3.6)不断重复步骤3.4)与3.5)，直到不存在分数变量，x′。

4.根据权利要求3所述的Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于所述步骤4)中近似函数L(Y)的关于状态向量p的子梯度

的无偏估计z_v的计算方法包括以下步骤：

4.1)将时间划分为相等长度T＞0的时间段，在此期间收集不同结点的访问统计信息，C_G′表示结点历史访问记录，C_G表示结点当前作业的结点访问记录；

4.2)根据不同结点的访问统计信息计算每个结点v∈V(每一个RDD)被缓存的概率p_v∈[0，1]^|V|；

4.3)当每一个长度为T的时间段结束时，需要调整每个结点的状态向量p＝[p_v]_v∈V∈[0，1]^|V|；

4.4)使用在一段时间内收集的结点访问信息计算结点后期重计算成本t_v，计算方式如下：

其中函数(A)的作用是当不等式A成立时，(A)为1，否则(A)为0；有向无环图中的结点v用集合V表示，即v∈V，c_v表示重新生成结点v所花费的时间；结点u是结点v的后继结点即子结点，x_v∈{0，1}为定义的缓存策略，表示结点v是否被缓存；若结点v被缓存则x_v＝1，如果结点v不被缓存则x_v＝0；

4.5)根据重计算成本t_v得出近似函数L(Y)的一个关于状态向量p的子梯度

的无偏估计，计算方式如下：

其中Tv代表在一个持续时间段T内在结点v∈V处以上述方式计算的重计算成本t_v的集合。

5.根据权利要求4所述的Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于所述步骤5)中在第k个测量周期结束时，状态向量p自适应调整方式的计算方法为：p^(k+1)←Φ_Θ(p^(k)+γ^(k)*z(p^(k)))

其中γ^(k)＞0是一个增益因子，p^(k)为状态向量p在第k个测量周期的状态，Φ_Θ是放松约束集Θ对凸多面体的投影，因此其可以在多项式时间内被计算。p_v∈[0,1]^|V|表示每个结点v∈V被缓存的概率，s_v表示结点v∈V的输出数据大小，以MB为单位。

6.根据权利要求5所述的Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于所述步骤6)具体包括以下步骤：

6.1)计算每个缓存项应放置在缓存中的概率在每个时间段内的变化平均值

6.2)在每一个时间段T结束时，采用概率舍入方法将变化平均值

舍入为整数解；

6.3)根据上述状态向量p的变化平均值

的排序结果做出缓存决策，即通过建立结点权重替换模型驱逐低分结点和插入新的高分结点，从而产生一个新的满足背包约束x^(k)∈{0,1}^|V|的缓存放置策略；

6.4)证明此整数解的缓存增益可以保证在离线缓存决策最优解x^*缓存增益的1-1/e近似范围内。

7.根据权利要求6所述的Spark平台下基于最大化缓存增益的缓存替换方法，其特征在于所述步骤6)中每个缓存项应放置在缓存中的概率在每个时间段内的变化平均值

的计算方式为：

其中k表示第k个测量周期，p^(l)表示状态向量p在第l个测量周期的状态，γ^(l)＞0是一个增益因子；此时变化平均值满足

并且是Θ中所有结点的凸组合。

Images