Learning Scheduling Algorithms for Data Processing Clusters

介绍

我们介绍了decima，一种通用的调度服务器来服务未来阶段的数据处理，我们关注这些工作有两个原因：

1. 许多系统将将作业阶段和他们的依赖关系编码为有向无环图（DAGs）

2. 调度DAGs算法是很难的问题，器最优解是难以处理的，很难在好的启发式中捕获。

Decima使用神经网络来对调度决策进行编码，通过大量的模拟实验来训练神经网络，调度一个工作负载，观察结果，逐渐的提升策略，如下图。为了使RL适应于集群调度，必须解决几个挑战。

1. 标准的神经网络需要平坦得数值向量作为输入，但是调度器的输入是带有节点和边的DAGs，我们开发了一种新的嵌入技术，把任意大小和形状的作业DAGs映射到神经网络可以处理得向量，我们的方法建立在图嵌入技术上，但是为了调度定制的，例如，现有的嵌入不能捕获基于路径的优先权，例如DAGs的关键路径，因此创造了一种新的嵌入方法。
2. 集群调度必须扩展到数千台机器的数百个作业。就调度器可用信息的数量而言（状态信息空间）和必须做出选择信息的数量（动作空间）而言，导致了比典型的游戏任务大的多的RL问题。我们必须设计一个可扩展的RL规划，神经网络架构可以处理任何数量的相同底层参数的作业，我们也可以把动作导入到独立的模型来（i）挑选一个阶段进行调度（ii）配置作业的并行度，与简单的动作编码相比，大大降低了模型的复杂度。
3. 连续的随机到达的作业导致了传统的RL训练不能容忍的方差的变化。这种差异的变化，这种偏差存在是因为传统的强化学习算法不能辨别两种奖励反馈是否因不同的潜在工作到达模式不同，或者是由于所学的调度策略的质量不同。为了计算这种影响，我们建立新的强化学习技术，设置随机输入来减小偏差，通过实际的作业到达序列来调节训练反馈，我们将调度策略的贡献隔离在整体的反馈中，是的处理连续到达的作业学习策略变得可行。

设计

根据上述提出的三个挑战来处理decima：可扩展的图嵌入，将调度决策编码为动作，连续随机作业到达的RL训练
Spark调度问题：一个spark作业包含一个DAG（节点是独立的阶段），每个阶段代表一个系统可以并行运行的操作，一旦所有的父节点完成，一个阶段就可以运行，一个阶段可以并行运行多少个任务取决于所拥有的执行器数量，因此调度器必须处理两种action：
（i）决定下一步运行哪个阶段
（ii）决定每个阶段有多少个执行者

RL构想：调度事件—例如，一个阶段完成（释放执行器），或者一个作业到达（添加一个DAG）–agent将集群的当前状态作为输入，输出调度的action，奖励来自于运行时间目标。如最小化作业完成时间（JCT），每一步相应的奖励是−τ ×J，τ是继上次奖励以来的绝对时间，J是系统中作业的数量，训练使用标准的策略梯度与spark模拟器。

可扩展的图嵌入：在每次观察状态时，decima将DAG（任意的形状和大小）转换成向量（使用图嵌入graph embedding），我们的方法是基于图卷积神经网络，是为调度而定制的。在DAG节点中给定原始特征向量x_v^i，decima建立每节点嵌入(Gi, x_v^i) → e_v^{i，结果e_v}i捕获了从v到所有节点的信息。Decima在一系列信息传递步骤中将信息从子节点传递到父节点。

父节点聚集了子节点的信息计算了自己的嵌入信息：

将调度决策编码为动作：decima将调度决策分解为一系列的二位动作空间，输出
（i）下一个被指定调度的阶段
（ii）该阶段允许的最大并行度阶段
在每一次调度中，decima将来自图嵌入处理的向量作为输入传递到图神经网络中，如图所示：

输出action<v,li>,我们扩展decima的阶段选择动作空间来明确的包括并行度限制，并行度限制指定范围{1，2，，，N}，N是执行器的数量，这种扩增将会要求O（D*N）个可能的动作，D为节点的总数量，成千上万的执行器增加了很高的复杂度，我们可以利用一个基本的观点来实现相同的并行度控制，只需要O（D+N）个动作，即只要控制整个作业的并行度，单个节点的并行度可以不受控制，如下图所示：

因此，状态s下选择一个节点和限制的可能性可以被简化为：
P(node,limit|st) = P(node|st) × P(limit|node, st) = P(node|st) × P(limit|job, st).

处理连续随机任务到达：为了训练decima连续随机到达出现了两个挑战：
（i）最大化累计期望奖励的标准的R了算法并不适合，一系列作业J1, J2, . . . , JN，标准目标最小化E[PNi=1T(Ji)],T（）表达的是作业的完成时间，然而在连续的作业到达时，真正的目标是在一个大的time horizon中最小化平均作业完成时间，E[limN→∞PNi=1T(Ji)/N]。因此我们使用了另外一种R了公式，可以优化在无穷的time horizon中的累计奖励，在操作上用不同的奖励来代替标准的奖励：在每一步中，agent收到奖励r_t-r_{,r_t表示标准奖励，r}表示移动的平均奖励。
（ii）不同的工作到达模式对奖励反馈有很大的影响，这种影响是由作业到达的随机性引起的，可以给奖励值增加噪声，扭曲策略梯度估计，为了说明误差，我们提出用于“输入驱动”环境的方差减少技术，使用依赖于输入的基线