Decima(Learning Scheduling Algorithms for Data Processing Clusters):用强化学习解决调度问题
解决的问题
解决了在云上的多个以DAG图表示的任务在多个Executor上运行时的调度问题。该问题为NP-Hard难度的问题，在该论文中，作者使用RL和GNN来解决它。
- 任务描述
每一个节点表示一个计算的阶段(computation stage)， 每个阶段都包含可以并行计算的任务；
每一条边表示数据依赖(Data dependencies)，父节点完成之后子节点才可以开始运行。
- 交互过程
- 调度器接受任务，并且将挂起的计算阶段映射到可用服务器上运行。
- 与此同时不断有新的、随机的任务请求出现，即待分配的任务和可用的服务器都处于动态变化的环境中。
- 智能体的观测(Observation)：所有可用作业的信息和服务器在每个调度事件上的状态。(the information of all available jobs and the status of the servers at every scheduling event.)
- 目标：最小化任务的平均完成时间。
- 论文贡献：
- 针对具有依赖关系的任务，使用RL训练workload-specific调度算法：Decima
- 使用可伸缩的GNN来表示调度策略，可以处理任意形状和大小的DAG表示的任务
- 任务随机到达，可以进行在线学习
强化学习模型
- Action组成：(node, 服务器数量)
- 当服务器池中有空闲服务器的时候，选择一个node，为其分配相应的节点数量，重复该过程直至所有服务器都处于忙碌状态。这样的优点是减少动作空间大小和动作序列的长度，降低强化学习的难度，作者称这是唯一work的设计。
- State：DAG信息（包括任务数量、平均任务时间、可用服务器数量、待决策的任务数量等
GNN（DAG信息聚合）
$e_v = g[\sum_{w\in\xi(v)}f(e_w)]+x_v$
其中x表示节点的特征，w表示所有的子节点，因此节点的打分因子是由子节点分数之和以及节点特征决定的。
使用两个非线性函数是因为它能让Decima表达更加广泛多变的聚合函数，例如$f\sim log(\cdot/n),g\sim exp(n \times \cdot)$时，Decima能表示下图的关键路径：
$e_t^i = g[\sum_{w\in \xi(v)}f(e_w^i)]+x_v^i$
上式为Per-node embeddings表达式，体现了子节点的信息向当前节点汇聚的过程。与Per-node embedding类似，作者为每个Job和所有的任务都分别设计了Per-job embeddings
${(x_v^i,e_v^i), v\in G_i} \rightarrow y^i$
以及global embeddings
${y^1, y^2, …} \rightarrow z$
GNN(节点信息聚合)的全过程在论文中由下图表示：
因此，每个层级的信息聚合由两个非线性变换(f and g)表示；整个GNN由6个非线性变换构成。
决策网络设计
- 调度过程：当某个job完成或者有新job到达时，系统开始调度。
- 动作(action)$<v,l_i>$有两个维度，决策网络的输出包括两部分，v是选择哪个任务节点($P_{node}$)，$l_i$是为这个任务分配多少计算资源(Parallelism limit on job)。调度包括以下三个阶段：
- 当任务i使用的服务器比$l_i$少时，Decima为节点$v$分配executors直到executors的数量到达$l_i$.
- 上一步完成后，如果有多余的executors，Deciam将继续运行agent得到stage($v$)和parallelism($l_i$).
- 上述步骤一直运行，直至没有空闲的executors和未处理的stage($v$).
网络结构如下图所示，包括了GNN部分以及决策网络部分，GNN负责聚合DAG的信息，决策网络负责输出stage($v$)以及并行度上限(parallelism limit)($l_i$):
决策网络运行过程
- 得到stage(v)
- 用非线形网络$q(\cdot)$，得到$q_v^i\triangleq q(e_v^i, y^i, z)$
- 使用softmax层，选择调度的stage(v)
$P(node = v) = \frac{exp(q_v^i)}{\sum_{u\in A_t}exp(q_u^{j(u)})}$
- 为任务节点分配服务器数量parallelism limit($l_i$)
计算过程与得到stage(v)类似
训练模型与实验
系统的整体结构图如下：
模型训练采用的是策略梯度法(PG):
作者在训练时采用以下公式更新策略梯度：
$\theta \leftarrow \theta + \alpha \sum_{k=1}^{T} \nabla_\theta log \pi_\theta (s_k, a_k)(\sum_{k’ = k}^{T}r_{k’} - b_k)$
其中$\alpha$为学习率， $b_k$为baseline，添加baseline是参见此链接
在训练初期使用较短的任务序列，逐渐加长序列。
- 因为在训练初期，agent比较笨，它无法对长序列进行很好的处理，反而会导致任务堆积，学习效率也很低。因此作者的构想为先处理简单的，再逐渐增加难度，效率会高一些。
- 这是一种课程学习(curriculum learning)的模式
与(朴素的)传统方法比较
- 朴素的先进任务先执行、最短任务优先会导致资源闲置等待。朴素的公平分配虽然会使服务器没有闲置，但是会导致大量IO开销从而拖慢速度。
而Decima
- 有选择的将服务器集中在某些小任务上，同时仍然不留下任何资源空闲。
- 为每个作业分配适当数量的服务器，这样就不会产生不必要的IO工作。
实验
- 在任务batched arrivals、按泊松分布continuous arrivals两个实验里，Decima完爆传统方法。
- ppt里暂时没看到对任务信息的更进一步描述，比如复杂度分布之类的。不过讲到了Decima完成小任务特别快，并且倾向于对小任务分配更多（但不会过多）的服务器。
- 其他实验：解决其他资源调度问题、评估算法各个部分的影响、大规模集群泛化、训练及推理速度、离线优化等，ppt里没讲，等我看了论文再补充
实验
我们已经将 Decima 实现为一种可插入的调度服务，并行数据处理平台可以通过 RPC 接口与之通信。在 §6.1 中，我们描述了 Decima 与 Spark 的集成。接下来，我们将描述我们基于 Python 的训练基础设施，其中包括一个准确的 Spark 集群模拟器（§6.2）。
Spark集成
Spark集群的结构图如图所示：
为了在 Spark 中集成 Decima，我们做了两个主要更改：
- 每个应用程序的 DAG 调度程序在启动时和调度事件发生时联系 Decima。 Decima 响应下一阶段的工作和并行度限制（§5.2）。
- 当新作业到达时，Spark master 会联系 Decima 以确定为其启动多少执行程序，并通过在完成一个阶段后将执行程序从作业中撤走来帮助 Decima。
State observations.
(i) 阶段中剩余的任务数量，(ii) 平均任务持续时间，(iii) 当前在该节点上工作的执行者数量，(iv) 可用执行者数量，以及 (v) 可用执行者是否可用当地的工作。我们通过尝试包含捕获集群状态所需的信息来选择这些功能（例如，当前分配给每个阶段的执行者数量），以及可能有助于调度决策（例如，一个阶段的平均任务持续时间）。这些统计数据取决于可用信息（例如，同一作业过去执行的配置文件或运行时指标）和所使用的系统（此处为 Spark）。 Decima 可以很容易地合并额外的信号。
Neural network architecture.
图神经网络的六个转换函数 f (·) 和g(·) (§5.1)（节点级、作业级和全局嵌入各两个）和策略网络的两个评分函数 q(·) 和 w( ·) (§5.2) 是使用双隐藏层神经网络实现的，每层有 32 和 16 个隐藏单元。由于这些神经网络可重复用于所有作业和所有并行限制，因此 Decima 的模型是轻量级的——它总共包含 12,736 个参数 (50KB)。将集群状态映射到调度决策所需的时间不到 15 毫秒（图 15b）。
Spark模拟
为了忠实地模拟 Decima 的决策如何与集群交互，我们的模拟器捕获了几个真实世界的效果：
(1) 来自特定阶段的第一波任务通常比后续任务运行得慢。这是由于 Spark 的流水线任务执行 [63]、任务代码的 JIT 编译 [47] 和预热成本（例如，与其他执行程序建立 TCP 连接）。因此，Decima 的模拟环境从不同的分布中选择第一波任务的实际运行时间，而不是后来的波。
(2) 为Spark作业添加执行器需要启动JVM进程，耗时2-3秒。 Executors 与工作相关联以进行隔离，因为 Spark 假定它们是长期存在的。因此，每次 Decima 跨作业移动执行程序时，Decima 的环境都会施加空闲时间以反映启动延迟。
(3) 高度并行会减慢单个 Spark 任务，因为更广泛的混洗需要额外的 TCP 连接，并在合并来自许多分片的数据时创建更多工作。 Decima 的环境通过从不同并行级别收集的分布中抽样任务持续时间来捕获这些影响（如果此数据可用）
我们通过将其与真实的 Spark 执行进行比较来验证我们的模拟器的保真度。（结果是模拟器的保真度很高）
评估
我们在真实的 Spark 集群测试台上和阿里巴巴的生产工作负载模拟中评估了 Decima。
我们的实验解决了以下问题：
(1) 与真实 Spark 集群中精心调整的启发式算法相比，Decima 的性能如何 (§7.2)？
(2) Decima 的学习能否推广到具有不同机器配置的多资源设置（§7.3）？
(3) 我们的每一个关键想法如何为 Decima 的业绩做出贡献；当调度环境发生变化时，Decima 如何适应；以及 Decima 训练和训练后做出调度决策的速度有多快？
现有的baseline算法
(1) Spark 的默认 FIFO 调度，它按照作业到达的相同顺序运行作业，并根据用户请求为每个作业授予尽可能多的执行程序。
(2) 最短作业优先的关键路径启发式 (SJF-CP)，它根据作业的总工作量确定作业的优先级，并在每个作业中运行其关键路径上下一阶段的任务。
(3) 简单的公平调度，它为每个作业提供平等公平的执行者份额，并轮询来自可运行阶段的任务，以同时耗尽所有分支。
(4) 朴素加权公平调度，将执行者分配给与其总工作成比例的工作。
(5) 一个精心调整的加权公平调度，给每个作业 Tα i /Í iTα i 的总执行者数，其中 Ti 是每个作业 i 的总工作量，α 是一个调整因子。请注意，α = 0 简化为简单公平方案，而 α = 1 简化为朴素加权公平方案。我们遍历 α ∈ {−2,−1.9,…,2} 以获得最佳因子。
(6) 来自俄罗斯方块 [34] 的标准多资源打包算法，它贪婪地调度最大化请求资源向量和可用资源向量的点积的阶段。
(7) Graphene，Graphene [36] 对 Decima 的离散执行器类的改编。 Graphene 使用 Graphene 的算法 [36, §4.1] 检测和分组“有问题的”节点，并将它们与（5）中优化调整的并行性一起调度，实现 Graphene 规划策略的本质。我们执行网格搜索以优化超参数（附录 F 中的详细信息）。
Spark cluster
我们使用运行 Spark v2.2 的 OpenStack 集群，在 Chameleon Cloud 测试平台中按照 §6.1 中的描述进行了修改。该集群包括25 个工作虚拟机，每个虚拟机在 m1.xlarge 实例（8 个 CPU，16 GB RAM）上运行两个执行器，在 m1.xxxlarge 实例（16 个 CPU，32 GB RAM）上运行一个主虚拟机。我们的实验考虑 (i) 批量到达，其中多个作业同时开始并运行直到完成，以及 (ii) 连续到达，其中作业以随机到达间隔分布到达或遵循跟踪。
批量到达
最后，Decima 优于所有基线算法，并且比最接近的启发式算法（“优化加权公平”）将平均 JCT 提高了 21%。这是因为 Decima 更好地确定工作的优先级，将高效的执行者份额分配给不同的工作，并利用工作 DAG 结构（§7.4 分解了每个因素的好处）。 Decima 通过端到端 RL 训练自主学习此策略，而性能最佳的基线算法需要仔细调整。
连续到达
Decima 的性能提升来自于更快地完成小作业，Decima 通过为小型作业分配更多执行程序来实现这一点（图 10d）。每个作业的正确执行程序数量取决于工作负载：不加选择地为小型作业提供更多执行程序会低效地使用集群资源（§2.2）。Decima 的执行者分配产生的总工作量与手动调整启发式相似。图 10e 显示了这一点：在对角线以下的作业使用 Decima 的总工作量小于启发式，而在对角线以上的工作在 Decima 中的总工作量更大。大多数小型作业都在对角线上，这表明 Decima 仅在额外的执行程序仍然有效时才增加并行度限制。因此，Decima 成功地在为小型作业提供额外资源以更快完成它们和有效利用资源之间取得平衡。
多维资源打包
我们之前实验中使用的独立 Spark 调度程序只为作业提供对预定义执行程序槽的访问权限。更高级的集群调度器，例如 YARN [75] 或 Mesos [41]，允许作业指定其任务的资源需求并创建适当大小的执行器。将具有多维资源需求（例如，⟨CPU、内存⟩）的任务打包到固定容量的服务器上，进一步增加了调度问题的复杂性 [34、36]。我们使用来自阿里巴巴的生产跟踪来调查 Decima 是否可以使用相同的核心方法学习良好的多维调度策略。
Industrial trace.
跟踪包含来自生产集群的大约 20,000 个作业。我们使用轨迹的前半部分进行训练，然后将 Decima 的性能与其余部分的其他方案进行比较。
Multi-resource environment
我们修改 Decima 的环境以提供几个具有不同内存大小的离散执行器类。我们的实验使用了四种类型的执行器，每一种都有 1 个 CPU 内核和 (0.25,0.5,0.75,1) 单位的标准化内存；每个执行器类别占集群执行器总数的 25%。
Results
Decima 的平均 JCT 比最佳竞争算法 (Graphene*) 低 32%，表明它在多资源环境中学习了良好的策略。
Decima深挖
最后，我们展示了 Decima 可以学习的各种调度策略，并分解了我们的关键思想和技术对 Decima 性能的影响。
在附录中，我们通过详尽搜索工作顺序（附录 H）、学习策略对不断变化的环境的稳健性（附录 I）以及 Decima 对不完整信息的敏感性（附录 J）进一步评估 Decima 的最优性。
学习策略：Decima 优于其他算法，因为它可以根据高级目标、工作负载和环境条件学习不同的策略。
学习架构的影响：图 14 显示，从 Decima 中删除任何一个组件会导致平均 JCT 比在高集群负载下调整的加权公平启发式更差。这个结果有四个要点。
- 首先，并行度控制对 Decima 的性能影响最大。在没有并行控制的情况下，Decima 在每个调度事件中将所有可用的执行程序分配到一个阶段。即使在中等集群负载（例如 55%）下，这也会导致无法跟上传入作业到达率的不稳定策略。
- 其次，省略图形嵌入（即，直接将每个节点上的原始特征作为 §5.2 中评分函数的输入）使得 Decima 无法估计作业中的剩余工作并考虑集群中的其他作业。因此，Decima 没有小作业或集群负载的概念，并且随着负载的增加，其学习的策略很快变得不稳定。
- 第三，在训练集中使用不固定的工作序列会增加奖励信号的方差（§5.3）。
- 第四，仅针对批量工作到达的培训不能推广到连续工作到达。在对分批到达进行训练时，Decima 学会了系统地推迟大型作业，因为这会导致 JCT 总和最低（惩罚总和最低）。
推广到不同的工作负载：我们通过改变 TPC-H 实验（§7.2）中的训练工作量来测试 Decima 的泛化能力。最终结果显著表明，多样化的训练工作负载集有助于使 Decima 的学习策略对工作负载变化具有鲁棒性；我们在§8 中讨论了可能的在线学习。
训练和推理性能：
- 图 15a 显示了 Decima 在连续 TPC-H 作业到达 (§7.2) 上的学习曲线（蓝色），每 100 次迭代（看不见的）作业到达序列测试模型的快照。每次训练迭代大约需要 5 秒。 Decima 的设计（§5.3）对于训练效率至关重要：省略输入中的并行度限制值（黄色曲线）迫使 Decima 对不同的限制使用单独的评分函数，显着增加要优化的参数数量；对节点（绿色曲线）进行细粒度并行控制会减慢训练速度，因为它增加了 Decima 必须探索的算法空间。
- 图 15b 显示了 Decima 在我们的 Spark 测试平台 (§7.2) 中决定调度操作（红色）和调度事件之间的时间间隔（蓝色）所花费的时间的累积分布。 Decima 的平均调度延迟小于 15 毫秒，而调度事件之间的间隔通常在秒级。在不到 5% 的情况下，调度间隔比调度延迟短（例如，当集群在单个调度事件中请求多个调度操作时）。因此，Decima 的调度延迟不会对任务运行时造成可测量的开销。
Decima的讨论
在本节中，我们将讨论 Decima 技术的未来研究方向和其他潜在应用。
- 稳健性和泛化性。
- 其他学习目标
- 抢占式调度
- 潜在的网络和系统应用程序。
结论
Decima 证明了使用强化学习自动学习复杂的集群调度策略是可行的，并且学习到的策略灵活高效。 Decima 的学习创新，例如其图形嵌入技术和流式处理训练框架，可能适用于处理 DAG 的其他系统（例如，查询优化器）。我们将在 https://web.mit.edu/decima 上开源 Decima、我们的模型和我们的实验基础设施。这项工作不会引发任何伦理问题。
数据集
Chameleon Cloud 测试平台.
阿里巴巴的生产工作负载（感谢来自阿里云智能的 Haiyang Ding 和 Yihui Feng 分享生产集群数据集。）
我们使用了阿里巴巴早期版本的public cluster-trace-v2018 trace[6,52]
[6]Cluster data collected from production clusters in Alibaba for cluster management research(https://github.com/alibaba/clusterdata.)
[52]Imbalance in the cloud: An analysis on alibaba cluster trace.