一种基于预测的Map/Reduce数据处理平台内存资源动态分配方法

摘要

一种基于预测的Map/Reduce数据处理平台内存资源动态分配方法，分配方法分为五个步骤，初始化、任务内存资源使用预测、任务内存资源释放、任务内存资源追加和回溯。本方法针对Map任务和Reduce任务在运行过程中内存资源使用量具有明显波动性的特征，根据Map任务和Reduce任务运行过程中的内存使用量历史记录，采用线性回归和t检验法，统计任务内存使用规律，预测任务后续运行中需要使用的内存量，并根据任务内存使用预测量，动态追加或减少正在运行的Map任务和Reduce任务的内存分配量，从而有效提高Map/Reduce平台内存资源的使用效率，提升Map/Reduce作业的执行效率。

说明书

技术领域

本发明属于分布式计算领域，具体涉及Map/Reduce型海量数据处理平 台中内存资源的使用预测与动态分配方法。

背景技术

Map/Reduce是一种新型的并行计算模型，已被广泛应用于海量数据处理 领域。内存是支撑Map/Reduce应用运行的重要计算资源。在实际运行中， 一个Map/Reduce应用是由一个或多个Map/Reduce作业组成。每个Map/Re duce作业的执行通常包含一个Map阶段和一个Reduce阶段。其中，Map阶 段和Reduce阶段可分别映射为多个Map任务进程和Reduce任务进程并行执 行。Map/Reduce应用的运行平台(以下简称“Map/Reduce平台”)以任务为 单位为Map/Reduce应用分配其运行所需的内存资源。

由于Map/Reduce应用普遍具有大数据处理的特征，是否分配充足的 内存资源，已成为制约Map/Reduce应用执行效率的关键因素。目前，Ma p/Reduce平台对内存资源的分配通常采用以用户设置为导向的方法，即用 户在Map任务和Reduce任务运行前或运行中主动发起内存资源申请请求， 给出确定的内存资源需求量，Map/Reduce平台根据用户指定的需求量为其 分配或追加内存资源；任务一旦获得内存资源将持续占用，直至任务运行 结束，或在其他运行任务需要追加内存资源时被动释放。

然而，上述方法运用于实际Map/Reduce生产性平台存在如下问题： Map任务和Reduce任务在其运行过程中对内存资源的使用量往往具有显 著的波动性，用户对任务的内存资源的实际消耗需求难以准确把握。因此， 在Map/Reduce平台中采用以用户设置为导向的内存分配方法，导致用户 过量申请内存资源是客观存在的事实。同时，在既有以用户设置为导向的 方法中，任务无法将其过量占有的内存资源主动释放出来以供待调度的M ap任务和Reduce任务使用。这使得待调度任务由于无法获得初始内存分 配而延迟启动执行，从而大大降低了平台的任务吞吐率和内存资源的利用 率。此外，以用户设置为导向的方法难以防止恶意用户过度申请内存资源， 从而导致平台资源恶意竞争的现象。

发明内容

本发明方法针对Map和Reduce任务在运行过程中内存资源使用量具有 明显波动性的特征，根据Map任务和Reduce任务运行过程中的内存使用量 历史记录，采用线性回归和t检验法，统计任务内存使用规律，预测任务后 续运行中需要使用的内存量，并根据任务内存使用预测量，动态追加或减少 正在运行的Map任务和Reduce任务的内存分配量，从而有效提高 Map/Reduce平台内存资源的使用效率，提升Map/Reduce作业的执行效率。

本发明所述的内存资源分配方法分为五个步骤：初始化、任务内存资 源使用预测、任务内存资源释放、任务内存资源追加和回溯。在本方法中， 有五个基本的参数：预测函数拟合次数阈值C_max、任务内存资源追加判断 阈值U_a、任务内存资源释放判断阈值U_r、内存追加量计算时间步长τ、任务 抢占优先级权值比例θ。C_max一般取值在3～5之间，U_a取值在0.1～0.5之间， U_r取值在0.5～1之间，τ取值在5～10秒，θ取值在0～1之间。

上述方法在计算机上按以下步骤实现：

(1)初始化：从Map/Reduce平台既有资源及作业管理组件采集运行 任务t_ij(1≤i≤m，1≤j≤n)内存动态分配所需的初始化信息，包括任务当 前内存分配量RC_ij、任务开始运行时刻c_i_ij和任务的内存资源使用量历史记 录集合RN_ij。其中，i表示任务所属Map/Reduce作业的编号，j表示任务在 作业内的任务编号。

(2)建立任务t_ij的内存资源使用量预测函数。

2.1)设置任务t_ij的内存资源使用预测量是关于时间的函数，预测函 数形如其中，a_ij与c_ij是待估算的参数；

2.2)令平台中运行任务t_ij的内存资源使用量历史记录集合RU_ij表示为 RU_ij＝{r_l|r_l＝(t_l，m_l)，t_l≥t_l-1，m_l≥0}，其中，t_l为第l个记录周期，m_l为t_l记 录周期任务t_ij的内存使用量。设置RU_ij为预测样本；

2.3)令x＝ln(t+1)，y＝q_ij(t)，将任务t_ij的内存资源 需求预测函数变换为y＝b_ijx+c_ij，待估算的参数变换为b_ij和c_ij；令C_ij为 函数拟合失败的次数，C_ij←0；

2.4)采用线性回归方法对函数y＝b_ijx+c_ij进行拟合，其中b_ij和c_ij即 为回归系数；

2.4.1)对于任务t_ij的历史内存资源使用记录集RU_ij中的每一个记录r_l， 计算一个变换后的记录r_l′：(x_l，y_l)，x_l＝ln(t_l+1)，y_l＝m_l；

2.4.2)利用公式(1)-(6)，计算回归系数b_ij和c_ij的估计值和其中， n_ij表示RU_ij中当前内存资源使用记录的个数。

$\bar{x}=\frac{1}{n_{\mathrm{ij}}}{\Sigma }_{l=1}^{n_{\mathrm{ij}}}{x}_l---\left(1\right)$

$\bar{y}=\frac{1}{n_{\mathrm{ij}}}{\Sigma }_{l=1}^{n_{\mathrm{ij}}}{y}_l---\left(2\right)$

$S_{\mathrm{xx}}={\Sigma }_{l=1}^{n_{\mathrm{ij}}}{(x_l-\bar{x})}^2={\Sigma }_{l=1}^{n_{\mathrm{ij}}}{x}_l^2-\frac{1}{n_{\mathrm{ij}}}{\left({\Sigma }_{l=1}^{n_{\mathrm{ij}}}{x}_l\right)}^2---\left(3\right)$

$S_{\mathrm{xy}}={\Sigma }_{l=1}^{n_{\mathrm{ij}}}(x_l-\bar{x})(y_l-\bar{y})={\Sigma }_{l=1}^{n_{\mathrm{ij}}}{x}_l{y}_l-\frac{1}{n_{\mathrm{ij}}}\left({\Sigma }_{l=1}^{n_{\mathrm{ij}}}{x}_l\right)\left({\Sigma }_{l=1}^{n_{\mathrm{ij}}}{y}_l\right)---\left(4\right)$

由此得出经验回归方程

2.5)利用t检验法，对回归方程进行显著性检验。令 $S_{\mathrm{yy}}={\Sigma }_{l=1}^{n_{\mathrm{ij}}}{(y_l-\bar{y})}^2,$检验是 否满足。其中，是自由度为n_ij-2的t分布函数α/2分位值，α是显 著性水平；

2.6)若检验满足，则函数拟合成功，执行步骤2.10)；否则，执行步 骤2.7)；

2.7)C_ij←C_ij+1，若C_ij＞C_max，则拟合失败，执行步骤2.9)；否则， 执行步骤2.8)；其中，C_max为预测函数拟合次数阈值；

2.8)修正预测样本；对RU_ij中所有内存资源使用记录r_l＝(t_l，m_l)，r_l∈ RU_ij，若满足r_l-1＝(t_l-1，m_l-1)，r_l-1∈RU_ij，m_l-m_l-1＜0，则设置 RU_ij←RU_ij-{r_l}，执行步骤2.4；

2.9)标记任务t_ij内存资源使用量预测函数构建失败，执行步骤(3)；

2.10)标记任务t_ij内存资源使用量预测函数构建成功，将任务t_ij的内 存资源需求预测函数中的待估计参数设置为

(3)计算任务t_ij的内存资源追加量RA_ij和释放量RD_ij。令当前时刻为 c_c_ij，任务t_ij当前内存使用量为RN_ij。

3.1)初始化RA_ij＝0，RD_ij＝0；

3.2)估算任务t_ij的完成时刻c_f_ij。令任务t_ij处理的进度为p_ij，根据公式 (7)估算任务t_ij的完成时刻c_f_ij：

c_f_ij＝c_i_ij+(c_c_ij-c_i_ij)/p_ij   (7)

3.3)判断判断任务t_ij是否需要追加内存资源；若则执 行步骤3.7)；否则，执行步骤3.4)；其中，U_a为内存资源追加判断阈值。

3.4)根据步骤(2)，判断任务t_ij的预测函数是否构建成功，若是，则 执行步骤3.5)，否则，执行步骤3.6)；

3.5)根据公式(8)计算RA_ij，执行步骤3.8)；

${\mathrm{RA}}_{\mathrm{ij}}=\left(\begin{array}{c}{q}_{\mathrm{ij}}(c\_c_{\mathrm{ij}}-{c\_i}_{\mathrm{ij}}+\tau )-{\mathrm{RN}}_{\mathrm{ij}},\tau <{c\_f}_{\mathrm{ij}}-{c\_c}_{\mathrm{ij}}\\ q_{\mathrm{ij}}({c\_f}_{\mathrm{ij}}-{c\_i}_{\mathrm{ij}})-{\mathrm{RN}}_{\mathrm{ij}},\tau \ge {c\_f}_{\mathrm{ij}}-c\_c_{\mathrm{ij}}\end{array}\right)---\left(8\right)$

其中，τ为内存追加量预测时间步长；

3.6)根据公式(9)计算RA_ij，执行步骤3.8)；

RA_ij＝(RC_ij-RN_ij)×1.5   (9)

3.7)设置RA_ij＝0；

3.8)判断判断任务t_ij是否需要释放内存资源。若则执行步 骤3.9)；否则，执行步骤3.12)；其中，U_r为内存释放判断阈值。

3.9)根据步骤(2)，判断任务t_ij的预测函数是否构建成功，若是，则 执行步骤3.10)，否则，执行步骤3.11)；

3.10)令RM_ij＝q_ij(c_f_ij-c_i_ij)，根据公式(10)计算RD_ij，执行步骤(4)；

3.11)根据公式(11)计算RD_ij，执行步骤(4)；

${\mathrm{RD}}_{\mathrm{ij}}=\frac{1}{5}{\mathrm{RN}}_{\mathrm{ij}}---\left(11\right)$

3.12)设置RD_ij＝0；

(4)任务t_ij内存资源释放。令t_ij运行所在节点服务器为N_k，执行 RC_ij←RC_ij-RD_ij，R_{k_free}←R_{k_free}+RD_ij，其中，R_{k_free}为节点N_k的空 闲内存资源量。

(5)任务t_ij内存资源追加。令任务t_ij运行所在节点服务器为N_k， R_{k_free}为节点N_k的空闲内存资源量。

5.1)根据步骤(4)，判断是否满足RA_ij≤R_{k_free}，若是，则执行 R_{k_free}←R_{k_free}-RA_ij，并转至步骤5.9)；否则，执行步骤5.2)；

5.2)令节点服务器N_k上所有正在运行的任务组成集合TR，对TR中的 每一个任务t_uv，按照公式(12)计算该任务的抢占优先级A_uv，

A_uv＝θ×p_uv+(1-θ)×f_u，0≤θ≤1   (12)

其中，p_uv是任务t_uv的运行进度，f_u是任务t_uv所属作业J_u中已完成任务 数占总任务数的比例，θ是权值比例；

5.3)选取TR中所有抢占优先级高于任务t_ij的任务组成集合TR′；

5.4)令TP为节点服务器N_k上需要抢占其内存资源的任务集合，设置 初始设置内存资源抢占总量Pr_R_k＝0；

5.5)判断是否满足RA_ij＞R_{k_free}+Pr_R_k且若是，则执行步 骤5.6)；否则，执行步骤5.7)；

5.6)按照任务抢占优先级从高到低的顺序从TR′中选取任务，不妨将 所选取任务表示为t′_uv，任务t′_uv的当前内存分配量表示为RC′_uv；对于TR′中每 个任务t′_uv，设置Pr_R_k←Pr_R_k+RC′_uv，TR′←TR′-{t′_uv}，TP←TP∪{t′_uv}。 执行步骤5.5)；

5.7)判断是否满足RA_ij≤R_{k_free}+Pr_R_k，若是，则执行R_{k_free}← R_{k_free}+Pr_R_k-RA_ij，并执行步骤5.8)；否则，执行步骤5.10)；

5.8)对任务集合TP中的每一个任务执行内存资源抢占操作，即中止该 任务的运行进程，将任务重新标记为待调度任务；

5.9)标记任务t_ij内存资源追加成功，设置任务t_ij的当前内存资源分配 量RC_ij←RC_ij+RA_ij，转至步骤(6)；

5.10)标记任务t_ij内存资源追加失败。

(6)回溯：一个内存资源动态分配周期间隔t后，判断任务t_ij是否结 束，是则转至步骤(7)，否则转到步骤(1)；其中，内存资源动态分配周 期间隔t是指相邻两次任务内存资源动态分配间，从第一次内存分配结束 到第二次内存分配开始的间隔时长。

(7)结束：中止对任务t_ij的内存资源重分配功能。

当平台中存在多个运行任务时，在本发明方法的各步骤中，依照所述 方法顺次处理每一个运行任务，以完成对所有运行任务的动态内存资源分 配。

为了实现上述方法，本发明在Map/Reduce平台每个任务运行所在的服 务器上增设一个任务内存使用及运行进度监控器，用于周期性地获取任务 内存资源使用信息、任务运行进度信息，本发明将监控器所获取的任务内 存资源使用信息构成发明步骤(2)中所需的任务内存资源使用量历史记录 集合；并将最后一次获取的任务内存使用信息作为步骤(3)中所需的当前 内存使用量为RN_ij，将最后一次获取的任务进度信息作为该任务当前的运 行进度。任务的运行进度和其内存资源使用量信息可通过复用Map/Reduce 平台中既有的周期性任务运行状态监控机制获取。为了实现该方法，本发 明在Map/Reduce平台中增设任务内存使用预测器，用于根据任务内存使用 及运行进度监控器提供的内存使用量信息拟合任务内存资源使用预测函数 并计算任务需要追加或释放的内存量(步骤(2)和步骤(3))。为了实现 该方法，本发明在Map/Reduce平台中增设任务内存资源动态分配器，用于 根据预测器提供的预测结果，完成对运行任务内存资源的追加或释放(步 骤(4)和步骤(5))。

附图说明

图1为本发明方法所依附的Map/Reduce平台的部署图。

图2为采用本发明方法的Map/Reduce平台中新增软件模块及其交互关 系图。

图3为本发明方法的总体流程图。

图4为任务内存资源使用量预测函数构建流程图。

图5为任务内存资源追加/释放量计算的流程图。

图6为任务内存资源追加过程流程图。

具体实施方式

下面结合附图和具体实施方式对本发明加以说明。

本发明所提出的内存资源动态分配方法可依附于现有Map/Reduce数 据处理平台(如Hadoop平台)，通过修改和新增相应的软件模块实现。图 1是本方法所依附的Map/Reduce平台的部署图。该平台由多个计算机服务 器(平台节点)组成，服务器间通过网络连接。平台节点分为两类：包括 一个管理节点(Master)和多个计算节点(Slave)。本发明方法所依附的 Map/Reduce平台包含四类核心软件模块：资源管理模块(ResourceManager)、 应用管理模块(ApplicationMaster)、任务执行模块(TaskContainer)和节 点管理模块(NodeManager)。其中，ResourceManager负责维护平台中所 有节点的内存资源信息、执行作业调度及根据用户提交的内存需求进行任 务内存资源的初始分配，仅在管理节点上部署；NodeManager负责启动和 结束任务的运行，并监控本节点上任务运行情况及资源使用情况，每个计 算节点上均部署一个NodeManager。ApplicationMaster负责Map/Reduce作 业生命周期管理，对作业包含的每个Map和Reduce任务记录其初始内存 资源需求量信息以及任务状态信息，并对任务的启动、运行、结束等进行 管理和监控。在Map/Reduce平台中提交和运行的每一个Map/Reduce作业 均对应一个独立的ApplicationMaster，该模块在计算节点上部署。 TaskContainer负责执行Map任务或Reduce任务。每一个Map任务或Reduce 任务均对应一个独立的TaskContainer，该模块在任务运行所在节点上部署。 上述四类软件模块中，ResourceManager模块和NodeManager模块在 Map/Reduce平台启动时即部署运行，ApplicationMaster模块和 TaskContainer模块分别在相应的Map/Reduce作业提交以及Map或Reduce 任务运行时触发部署运行。

图2是为实施本发明方法在所依附的Map/Reduce平台中需增加的软件 模块及其交互关系图。阴影模块是为实现本发明方法须在既有Map/Reduce 平台中新增的软件模块，包括任务监控模块(MemCollector)、内存使用预 测模块(MemPredictor)、内存重分配模块(MemReallocator)、任务状态更 新模块(TaskUpdator)和资源更新模块(MemUpdator)。其中，MemCollector 负责收集其所在节点的所有任务执行模块的内存使用情况及任务运行进度 信息，MemPredictor负责根据MemCollector模块提供的各任务内存使用信 息预测任务后续的内存使用量，MemReallocator负责根据内存使用预测信 息，调整(包括追加和释放)各任务的内存分配量。上述三个模块可作为 NodeManager的子模块部署于每个计算节点上。TaskUpdator作为 ApplicationMaster的子模块，部署于计算节点，负责接收任务状态调整信 息，并修改ApplicationMaster中保存的相应任务的状态信息。MemUpdator 作为ResourceManager的子模块，部署于管理节点，负责收集计算节点上 任务内存资源分配变动信息，并修改ResourceManager中维护的计算节点 可分配内存资源信息。上述新增模块中，隶属于同一软件模块的子模块间 采用共享变量和方法调用的通信方式，隶属于不同软件模子模块线程间采 用远程过程调用(RPC)的网络通信方式。

为实现本发明方法，在每个计算节点的MemCollector、MemPredictor 和MemReallocator模块之间设置一个共享变量--运行任务信息列表 RunTasklist，每一个列表单元对应一个运行任务。对于任一运行任务t_ij， 列表单元的存储信息格式如下：

其中，任务内存资源使用历史记录集合中每个记录包含记录时刻和内 存使用量信息。为实现本发明方法，每个计算节点上的MemCollector需要 周期性地收集本节点上运行任务的内存资源使用量及运行进度信息，并将 收集的信息添加至共享变量RunTasklist相应列表单元中，供内存使用预测 模块MemPredictor获取使用。具体实施方法包括：

1)任务注册任务t_ij对应的TaskContainer启动后，以RPC调用的方 式，向所在节点的MemCollector进行任务注册。MemCollector根据 TaskContainer发送的任务注册信息，包括任务号、作业号、任务进程号、 任务对应的TaskUpdator的IP地址，在共享变量RunTasklist中创建一个新 的列表单元，并填写相应信息。

2)任务内存使用量及运行进度信息收集在完成任务注册后， MemCollector通过在NodeManager模块中嵌入的回调接口，根据任务号j和 作业号i，周期性(每隔5秒)地从NodeManager获取任务进程的内存使用 量信息，然后将获取的任务内存使用量信息及相应的记录时刻，按记录时 刻顺序追加至RunTasklist相应列表单元的任务内存资源使用量历史记录集 合RU_ij项中，并用获取的任务当前内存分配量信息更新RunTasklist相应列 表单元的任务当前内存分配量RC_ij项值。同时，MemCollector周期性地以 RPC调用的方式，从TaskContainer获取任务运行进度信息，并将获取的量 值赋给RunTasklist中相应列表单元的任务当前运行进度p_ij项。

3)任务注销在任务运行结束后，TaskContainer以RPC调用的方式， 向所在节点的MemCollector发送任务注销消息，任务注销消息包含作业号、 任务号信息。MemCollector根据作业号和任务号信息，停止对该任务周期 性内存使用量和运行进度信息的收集操作，并删除RunTasklist中该任务相 应的列表单元。

下面结合图3发明内容总流程说明本发明方法的具体实施方法。在本 实施方法中，五个基本的参数的设置如下：预测函数拟合次数阈值C_max＝5、 任务内存资源追加判断阈值U_a＝0.1、任务内存资源释放判断阈值U_r＝0.5、 内存追加量计算时间步长τ为10秒、任务抢占优先级权值比例θ＝0.8。本 实施方法可分为以下步骤：

(1)初始化任务t_ij运行所在计算节点上的MemCollector读取共享 变量RunTasklist中任务t_ij的信息，根据任务号j和作业号i，通过在 NodeManager模块中嵌入的回调接口，从NodeManager获取任务的当前内存 分配量信息，并根据任务信息中的任务对应的TaskUpdator IP地址，以RPC 调用的方式，从相应TaskUpdator获取任务t_ij开始运行时刻，将上述量值 分别赋给RunTasklist中任务t_ij对应列表单元中任务当前内存分配量RC_ij项 和任务开始运行时刻c_i_ij项。任务内存资源使用量历史记录集合RU_ij和任 务当前运行进度p_ij，则如前所述，通过MemCollector周期性收集运行任务 的内存资源使用量及运行进度信息获得。

(2)建立任务t_ij的内存资源使用量预测函数。

2.1)设置任务t_ij的内存资源使用预测量是关于时间的函数，预测函数 形如其中，a_ij与c_ij是待估算的参数；

2.2)任务t_ij运行所在计算节点上的MemPredictor读取共享变量 RunTasklist中任务t_ij的内存资源使用量历史记录集合RU_ij，RU_ij＝ {r_l|r_l：(t_l，m_l)，t_o＝0，t_l≥t_l-1，0≤l≤n_ij}，其中，t_l为第1个记录时刻，m_l为 t_l记录时刻任务t_ij的内存使用量。设置RU_ij为预测样本；

2.3)令x＝ln(t+1)，y＝q_ij(t)，将任务t_ij的内存资源需 求预测函数变换为y＝b_ijx+c_ij，待估算的参数变换为b_ij和c_ij； MemPredictor设置函数拟合失败的次数C_ij＝0；

2.4)MemPredictor根据发明内容2.4)中的方法，采用线性回归方法 进行变换预测函数的拟合；

2.5)MemPredictor根据发明内容2.5)所述的方法，采用t检验法对拟 合函数进行显著性检验；

2.6)MemPredictor判断检验是否满足，若是，则函数拟合成功，执行 步骤2.10)；否则，执行步骤2.7)；

2.7)MemPredictor将C_ij加1，判断拟合总次数是否大于总次数阈值C_max， 则拟合失败，执行步骤2.9)；否则，执行步骤2.10)。其中，C_max为预测函 数拟合次数阈值；

2.8)修正预测样本。MemPredictor读取共享变量RunTasklist中任务t_ij的内存资源使用量历史信息集合RU_ij，从RU_ij中去除所有满足条件 r_l-1：(t_l-1，m_l-1)，r_l-1∈RU_ij，m_l-m_l-1＜0的内存资源使用量记录 r_l：(t_l，m_l)，并执行步骤2.4)；

2.9)MemPredictor标记任务t_ij内存资源使用量预测函数构建失败，执 行步骤(3)；

2.10)MemPredictor标记任务t_ij内存资源使用量预测函数构建成功， 将任务t_ij的内存资源需求预测函数中的待估计参 数设置为

(3)计算任务t_ij的内存资源追加量RA_ij和释放量RD_ij。令当前时刻为 c_c_ij，任务t_ij当前内存使用量为RN_ij。

3.1)MemPredictor设置RA_ij＝0，RD_ij＝0；

3.2)MemPredictor从共享变量RunTasklist中读取任务t_ij的任务起始运 行时刻c_i_ij和任务t_ij的当前运行进度p_ij，并根据发明内容3.2)所述方法估 算任务t_jj的完成时刻c_f_ij；

3.3)MemPredictor从共享变量RunTasklist中读取任务t_ij当前内存资源 分配量RC_ij，并按照记录时刻的先后获取t_ij最近一次的内存资源使用记录， 作为任务t_ij的当前内存使用量RN_ij。MemPredictor判断是否满 足，若是，则执行步骤3.7)；否则，执行步骤3.4)。

3.4)MemPredictor根据步骤(2)，判断任务t_ij的预测函数是否构建成 功，若是，则执行步骤3.5)，否则，执行步骤3.6)；

3.5)MemPredictor根据公式(8)计算RA_ij，执行步骤3.8)；

${\mathrm{RA}}_{\mathrm{ij}}=\left(\begin{array}{c}{q}_{\mathrm{ij}}(c\_c_{\mathrm{ij}}-{c\_i}_{\mathrm{ij}}+\tau )-{\mathrm{RN}}_{\mathrm{ij}},\tau <{c\_f}_{\mathrm{ij}}-{c\_c}_{\mathrm{ij}}\\ q_{\mathrm{ij}}({c\_f}_{\mathrm{ij}}-{c\_i}_{\mathrm{ij}})-{\mathrm{RN}}_{\mathrm{ij}},\tau \ge {c\_f}_{\mathrm{ij}}-c\_c_{\mathrm{ij}}\end{array}\right)---\left(8\right)$

3.6)根据公式(9)计算RA_ij，执行步骤3.8)；

RA_ij＝(RC_ij-RN_ij)×1.5   (9)

3.7)MemPredictor设置RA_ij＝0；

3.8)MemPredictor判断是否满足，若是，则执行步骤3.9)； 否则，执行步骤3.12)。

3.9)MemPredictor根据步骤(2)，判断任务t_jj的预测函数是否构建成 功，若是，则执行步骤3.10)，否则，执行步骤3.11)；

3.10)令RM_ij＝q_ij(c_f_ij-c_i_ij)，MemPredictor根据公式(10)计算RD_ij， 执行步骤(4)；

3.11)MemPredictor根据公式(11)计算RD_ij，执行步骤(4)；

${\mathrm{RD}}_{\mathrm{ij}}=\frac{1}{5}{\mathrm{RN}}_{\mathrm{ij}}---\left(11\right)$

3.12)MemPredictor设置RD_ij＝0；

(4)任务t_ij内存资源释放，令t_ij运行所在节点服务器为N_k，根据步骤 (3)执行结果，对任务t_ij执行如下操作：

4.1)MemPredictor调用处于同一计算节点的MemReallocator提供的任 务内存释放本地方法，将该任务的任务号、作业号和内存释放量RD_ij传递 给MemReallocator；

4.2)MemReallocator根据任务的内存释放量信息，以RPC调用的方式， 将所在计算节点号N_k和释放内存量RD_ij发送给MemUpdator；

4.3)MemUpdator根据节点号和内存释放量信息，修改ResourceManager 主模块中维护的节点N_k可用内存资源量R_{k_free}，R_{k_free}←R_{k_free}+RD_ij， 然后向MemReallocator返回内存释放成功/失败信息；

4.4)MemReallocator根据返回信息，若成功，则修改共享变量 RunTasklist中任务t_ij当前内存资源分配量RC_ij，执行RC_ij←RC_ij-RD_ij。

(5)任务内存资源追加。根据步骤(2)执行结果，对任务t_ij执行如下 操作：

5.1)MemPredictor调用处于同一计算节点的MemReallocator提供的任 务内存追加本地方法，将该任务的任务号、作业号和内存追加量RA_ij传递 给MemReallocator；

5.2)MemReallocator根据任务的内存追加量信息，以RPC调用的方式， 将所在计算节点号N_k和追加内存量RA_ij发送给MemUpdator；

5.3)MemUpdator根据内存追加信息，读取ResourceManager主模块中 维护的节点N_k可用内存资源量R_{k_free}，如果R_{k_free}≥RA_ij，则MemUpdator 执行R_{k_free}←R_{k_free}-RA_ij，并向MemReallocator返回内存追加成功消息， 并执行步骤5.9)；否则，向MemReallocator返回失败消息，并执行步骤5.4)；

5.4)MemReallocator根据返回消息，若追加失败，MemReallocator读 取共享变量RunTasklist中每一个运行任务t_uv的任务当前运行进度p_uv，并 以RPC调用的方式，从该任务对应的TaskUpdator获取任务所属作业已完 成任务数占总任务数的比例f_u，MemReallocator根据本发明内容5.2)-5.6) 中所述方法，计算运行任务的抢占优先级，选取需要抢占其内存资源的任 务集合TP；

5.5)MemReallocator从共享变量RunTasklist中获取TP中所有任务当 前内存资源分配量，并求和作为节点N_k可抢占的内存资源量Pr_R_k； MemReallocator以RPC调用的方式，将任务t_ij所在计算节点号N_k、追加内 存量RA_ij及节点N_k可抢占的内存资源量Pr_R_k信息发送给MemUpdator；

5.6)MemUpdator根据内存抢占追加信息，读取ResourceManager主模 块中维护的节点N_k可用内存资源量R_{k_free}，判断R_{k_free}+Pr_R_k≥RA_ij是 否满足，若是，则执行步骤5.7)，否则，向MemReallocator返回内存抢占 追加失败消息，并执行步骤5.10)；

5.7)MemUpdator执行R_{k_free}←R_{k_free}+Pr_R_k-RA_ij，并向 MemReallocator返回内存抢占追加成功消息；

5.8)MemReallocator根据内存抢占追加返回消息，若追加成功，则调 用其所在NodeManager的方法，终止TP中所有任务对应的TaskContainer 运行进程，在共享变量RunTasklist中删除运行任务对应的记录，并调用任 务相应的TaskUpdator提供的任务状态改变RPC方法，通知TaskUpdator 将任务状态重新设置为待调度；

5.9)MemReallocator标记任务t_ij内存资源追加成功，修改共享变量 RunTasklist中任务t_ij当前内存资源分配量RC_ij，执行RC_ij←RC_ij+RA_ij， 转至步骤(6)；

5.10)MemReallocator根据内存抢占追加返回消息，若追加失败， emReallocator标记任务t_ij内存资源追加失败。

(6)回溯。一个内存资源动态分配周期(本方案中设置为10秒)结束 后，任务t_ij运行所在计算节点上的MemColloector查找共享变量RunTasklist 中是否存在任务t_ij对应的列表单元，若存在，则执行步骤(1)，若不存在， 则执行步骤(7)。

(7)结束：中止对任务t_ij的内存资源重分配功能。

当平台中存在多个运行任务时，可在上述实施方法的各步骤中，依照 所述方法顺次处理每一个运行任务，以完成对所有运行任务的动态内存资 源分配。

根据本发明所提出的Map/Reduce平台内存资源优化分配方法，发明人 做了相关的性能测试。测试结果表明，本发明方法可适用于典型 Map/Reduce应用负载。采用本发明方法的Map/Reduce型海量数据处理平 台较既有主流Map/Reduce型海量数据处理平台，如Hadoop，可较好地提升 作业执行效率及平台内存资源的利用率。

性能测试将依据本发明具体实施方案实现的Map/Reduce型海量数据 处理平台Predra与目前使用最为广泛的Map/Reduce型海量数据处理平台 Hadoop进行性能比较。测试选取作业吞吐率，作业平均周转时间以及任务 平均内存资源利用率作为性能指标，以体现本发明提出的方法在提升 Map/Reduce作业执行效率以及优化Map/Reduce平台内存资源利用率上的 优势。其中，吞吐率是指单位时间内完成作业的数量，以作业数/小时为单 位；作业平均周转时间是指作业从提交到运行完成所需的平均时间，以秒 为单位；作业平均等待时间是指作业从提交到开始运行所需的平均时间， 以秒为单位；任务平均内存资源利用率是指平台中单任务所实际使用的内 存量占其获得的内存分配总量的比例平均值。性能测试运行于由24个计算 节点构成的集群系统，计算节点的硬件配置包括：4个Intel(R)Xeon(R)CPU  E5-2660 0@2.20GHz的CPU、16GB DDR3RAM、1TB SATA硬盘，节点 间采用千兆以太网互连，操作系统为Centos6.5。测试选用模拟实际生产环 境的人工合成混合测试负载。混合负载在四个方面模拟实际生产环境中的 情形：输入数据类型及规模、作业类型及混合数量、作业包含的map任务 数量及reduce任务数量、作业到达分布。混合负载中包含6种作业类型， 作业到达间隔符合泊松分布，到达强度为平均每10秒提交一个作业。混合 负载的具体配置如表1：

表1测试混合负载配置

针对不同任务内存资源需求量的测试

测试首先为Map任务和Reduce任务设置不同的内存需求量，分析不 同的任务内存需求下Pradra的性能。在该组测试中，不同类型的作业所包 含的平均Reduce任务数量设置如表2。

表2作业包含的平均Reduce任务数设置

在该组测试中，map和reduce任务的内存资源初始需求量设置如表2。

表3任务内存资源初始需求量设置

表4不同任务内存初始需求量下作业吞吐率测试结果

表5不同任务内存初始需求量下作业平均周转时间测试结果

表6不同任务内存初始需求量下任务平均内存利用率测试结果

表4、表5和表6分别给出在不同的任务内存资源需求量设置下，Predra 和Hadoop平台中作业吞吐率、作业平均周转时间和任务平均内存利用率的 测试结果。由测试结果可知，采用本发明方法的Predrap平台较Hadoop平台 作业吞吐率最大提升了47.5％，平均提升了29％；作业平均周转时间最大缩 短了57.1％，平均缩短了37.4％；任务平均内存利用率最大提升了170.9％， 平均提升了141.2％。由于Map/Reduce平台是根据用户提出的任务内存资 源需求量进行任务内存资源的初始分配，故任务的初始内存分配量即为内 存需求量。在Hadoop平台中，任务一旦获得初始内存分配，就占有所分 配的内存直至任务运行结束。与Hadoop平台比较，Predra平台的优势在于 可针对任务运行过程中内存资源实际使用量波动的特征，通过预测的手段 实时评估任务运行过程中内存的实际需求量，并进行内存资源的动态分配， 从而将任务占有但未使用的内存资源释放出来并分配给其他待调度任务， 缩短了待调度任务等待内存资源初始分配的时间，因此在作业平均周转时 间和作业吞吐率这两个表征作业执行效率的指标上可获得更好的性能。同 时，Predra平台通过采用基于预测的内存资源动态分配方法可减少任务占 用但无实际使用的内存量，故提升了内存资源的利用率。

针对不同的作业包含Reduce任务数量的测试

该部分测试为Map/Reduce作业设置不同的Reduce任务数，分析在作 业包含的任务规模不同的场景下Pradra的性能。在该组测试中，map和 reduce任务的内存资源初始需求量分别为1024MB和2048MB，作业所包 含的Reduce任务数设置如表7。

表7Map/Reduce作业包含的Reduce任务数设置

表8不同的单作业包含Reduce任务数设置下作业吞吐率测试结果

表9不同的单作业包含Reduce任务数设置下作业平均周转时间测试结果

表10不同的单作业包含Reduce任务数设置下任务平均内存利用率测试结果

表8、表9和表10分别给出在不同的单作业包含Reduce任务数设置下， Predra和Hadoop平台中作业吞吐率、作业平均周转时间和任务平均内存利 用率的测试结果。由测试结果可知，采用本发明方法的Predrap平台较 Hadoop平台作业吞吐率最大提升了48.4％，平均提升了35.9％；作业平均 周转时间最大缩短了最大缩短了66.9％，平均缩短了42.9％。，平均缩短了 37.4％；任务平均内存利用率最大提升了196.8％，平均提升了165.7％。在 Map/Reduce平台中，单作业所包含的map任务数量通常由作业所处理的文 件规模确定，无需用户设定。因此，变动作业所包含的Reduce任务数量可 以模拟由于作业包含的任务规模不同，导致平台内存资源竞争强度不同的 场景。实验结果表明，在不同的作业包含Reduce任务数的设置下，Pradra 均获得了优于Hadoop的性能，其原因仍然是由于Pradra支持任务在运行 中根据实际需求动态获得内存资源，并可将未实际使用的内存份额释放出 来，以供其他任务更快地获得初始内存分配并启动运行。

最后应说明的是：以上示例仅用以说明本发明而并非限制本发明所描述 的技术，而一切不脱离发明的精神和范围的技术方案及其改进，其均应涵 盖在本发明的权利要求范围当中。