【论文】略读笔记72-前沿-动态概率建模指导的复杂工作流调度

📖《Taming System Dynamics on Resource Optimization for Data Processing Workflows: A Probabilistic Approach》

2022 年 深圳大学团队 发表于 CCF-A 类期刊 TPDS。

🎯需求

• 在许多数据密集型应用中，工作流通常被用作组织数据处理任务的重要模型，而资源调配则是提高工作流性能的一个重要且具有挑战性的问题。
  • 在许多数据密集型应用中，数据处理工作通常被建模为工作流，工作流是根据数据和计算依赖关系连接起来的任务集。
    • 例如，Montage 工作流是一个与天文学相关的大数据应用，它处理的天空马赛克数据规模高达数百 GB。
    • Facebook、雅虎和谷歌等大公司经常基于 MapReduce工作流，对 PB 级数据执行临时查询和定期批处理作业。
    • 这些数据密集型工作流通常在大型系统（如用于科学应用的高性能计算机和用于工业应用的公共/私有云）中执行，而资源配置决定了执行工作流任务的资源规模和类型，是工作流性能的重要优化因素。
• 最近，人们观察到云和大规模集群中的系统变化，如 I/O 和网络性能的变化以及故障事件的变化，会极大地影响工作流的性能。
  • 在许多大型系统中，变化已成为常态而非例外。造成变化的原因既有硬件方面的，也有软件方面的。例如，
    • 在超级计算机架构中，芯片的功率和温度变化可导致处理器之间的性能差异高达 16%。
    • 在云环境中，由于多个用户之间的资源共享，网络和 I/O 性能也会出现显著变化。
    • 作业故障已被证明是多种多样的，不同系统（如高性能计算、集群和云）遵循不同的概率分布。

🚧现状

• 然而，由于工作流结构复杂，资源调配一直是数据处理工作流的一个难题，现有工作已对此进行了广泛研究。
• 但传统的资源调配方法会忽略大型系统中的这些变化，导致资源调配结果不理想。
• 为什么要考虑变化？
  • 云提供商通常会提供各种类型的实例（即虚拟机），供用户选择最合适的资源来执行工作流任务。大多数现有的资源调配方法都假设每个任务在给定类型的虚拟机上的执行时间是静态的。
    • 1）然而，这一假设在云中并不成立，已有研究发现云的动态变化（如 I/O 和网络性能的变化）会导致大规模数据处理工作流的性能发生重大变化。传统的资源调配方法会忽略这些差异值，从而导致次优的资源调配结果。
    • 2）我们分析了工作流的几个常见资源调配问题，发现性能优化目标通常与 I/O 和网络性能的云动态非线性相关。因此，传统的静态优化（例如，将平均或预期性能作为优化输入）可能会导致次优甚至不可行的解决方案。例如，要利用检查点优化工作流性能，我们必须考虑系统故障动态（更多详情见第 6 节）。
  • 利用谷歌云的生产跟踪和亚马逊 EC2 的性能跟踪，我们发现在超过 60% 的时间里，动态感知方法比静态方法能获得更好的性能优化结果。
• 为什么采用概率方法？
  • 现有研究提出了各种方法，如动态调度和随机建模等，以解决考虑云动态的资源调配问题。
  • 然而，这些方法要么依赖于运行时精确的云性能估计（如动态调度），要么涉及复杂的建模和分析，因此难以推广（如随机方法）。

🤺挑战

• 我们研究了一种将云动态纳入工作流资源优化的系统而有效的方法。我们建议将云动态建模为随机变量，并将其概率分布作为优化输入来制定资源调配问题。
  • 优点：这种设计有两大优势：
    • 1）首先，它实现了许多具有系统随机性的问题所需的概率分析，例如在系统随机故障的情况下为工作流设计容错调度技术。
    • 2）其次，它可以推导出概率边界，以保证应用程序的最坏情况性能，而现有的静态方法只能保证平均性能。
  • 挑战：
    • 1）在云动态的概率表征下，传统的静态资源调配方法无法直接使用。主要的挑战在于，将概率分布作为资源调配问题的优化输入可能会导致高昂的计算开销，这是由于昂贵的分布计算和数据处理工作流的复杂结构造成的。
    • 2）其他领域也有一些提高概率方法效率的优化技术，如概率数据库中的高效查询评估和硬件设计中的高效概率分析。然而，这些技术都没有考虑工作流结构和资源配置问题的特殊性，而这些特殊性有助于更有效地降低工作流概率资源配置的开销。

🛩创新

• 本文以云计算中的工作流资源配置问题为例进行讨论，旨在提出一种将系统变化纳入工作流性能优化问题的通用解决方案。虽然讨论的重点是云，但我们猜想，这些观察结果可以为共享集群等其他系统提供启示（见第 7 节）。
• 在本文中，我们提供了一种考虑系统变化的工作流性能优化通用解决方案 Prob。
  • 具体来说，我们将系统动态建模为随时间变化的随机变量，并将其概率分布作为优化输入。尽管这种解决方案很有效，但计算开销很大。
  • 因此，我们提出了三种剪枝技术，以简化工作流结构并减少概率评估开销。这些技术是根据工作流结构和资源配置问题的特点设计的。
    • 1）首先，我们发现计算工作流的有效期是许多工作流资源配置问题中的常见操作。因此，我们提出了预处理剪枝方法，以减少这一重要计算的开销，从而降低概率优化的开销。
    • 2）其次，我们利用现有的工作流转换技术提出了针对工作流的优化方案，以减少评估一个实例配置解决方案的开销。
    • 3）第三，我们提出了一种部分解决方案评估方法，并采用现有的剪枝技术，以减少比较多个解决方案的开销。
  • 我们在运行时库中实现了我们的技术，使用户能够将高效的概率优化纳入现有的资源调配方法。
    

📊效果

• 实验表明，与最先进的静态解决方案相比，概率解决方案最多可将性能提高 65%，而我们的剪枝技术可大大降低概率方法的开销。
  • 我们开发了一个运行时库，其中包含 Prob 的所有剪枝技术。用户可以使用 Prob API 实现其现有的资源调配方法，将概率优化纳入其中，从而提高现有方法的有效性和效率。
  • 我们将预算受限调度和容错问题作为工作流资源优化问题的两个例子。我们利用两个真实云平台上的实际工作流和模拟，将 Prob 与最先进的静态算法进行了比较。实验结果证明了我们的概率方法的有效性和效率。
    • 具体来说，在预算受限的调度问题上，Prob 比静态算法提高了工作流性能的 2-65%，在容错问题上提高了 5-30%。Prob 的剪枝技术显著降低了我们的概率方法的开销（例如，与蒙特卡罗（MC）方法相比，速度提高了 567 倍）。因此，对于一个拥有 10,000 多个任务的蒙太奇工作流程来说，完成优化只需不到一秒钟的时间。
• 目标与非目标 Prob 的主要目标，也是本文的重点，是为现有的资源调配方法提出一个高效的接口，以便轻松纳入概率优化，而不是提出一种新的资源调配技术。
  • 为了展示 Prob 的通用性，我们使用工作流中两个常见的资源调配问题作为用例，并讨论 Prob 如何提高这两个用例的现有解决方案的有效性。

🧠疑问

1. 基于概率的方法具体如何实现？是否会很依赖于人工建模？
2. 如何定义“考虑变化”？预测本质上是否也是一种考虑概率变化的手段？
3. 结合工作流结构和资源配置特殊性的概率建模是什么样的？是否能够凝练出一句话insight？
4. 看起来最适应的场景是随机故障场景下的容错问题？如果不是随机概率场景，考虑概率可能反而会起到反作用？
5. 核心逻辑：大型系统中存在大量软件与硬件导致的变化 -> 现有研究无法感知动态变化，导致做出次优解 -> 采用概率的方法无需准确预测，适用随机变化场景、并能够从理论上推导出最差边界，因此具有更高的适用性，但需要解决两大挑战：1.直接在传统静态资源配置方法基础上输入概率分布，会导致高昂的计算开销；2.在其他领域提高概率优化方法的手段没有考虑工作流和资源配置问题的特点，会导致较差的适用性 -> 在传统方法的基础上，将系统动态建模为随时间变化的随机变量，并提出三大效率优化方案。

---

---

• 希望这篇博客对你有帮助！如果你有任何问题或需要进一步的帮助，请随时提问。
• 如果你喜欢这篇文章，欢迎动动小手 给我一个follow或star。

🗺参考文献

[1] A. C. Zhou, W. Xue, Y. Xiao, B. He, S. Ibrahim and R. Cheng, “Taming System Dynamics on Resource Optimization for Data Processing Workflows: A Probabilistic Approach,” in IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 1, pp. 231-248, 1 Jan. 2022, doi: 10.1109/TPDS.2021.3091400.