【论文】略读笔记75-经典-大规模调度冲突检测

📖《An extended fine-grained conflict detection method for shared-state scheduling in large scale cluster》

2016 年 云南大学团队 发表于会议 ICIIP。

🎯需求

• 作为共享状态调度架构的重要组成部分，乐观并发控制算法（OCC）在数据库领域的研究由来已久。
  • 如今，许多企业都需要集群管理系统来管理集群上运行的数据并行应用程序。 因此，近年来提出了许多集群管理系统。由于集群规模的不断扩大和更复杂的应用需求，单片式调度器遇到了可扩展性瓶颈。于是，分布式调度架构被用来解决这一问题。Mesos、Sparrow和Omega是分布式调度架构的三种典型实现。
  • 作为第一个在调度架构中引入乐观并发控制（OCC）的架构，Omega 是一种可扩展且灵活的调度架构，它基于将整个集群状态共享给分布式调度器的理念。一些成功者也使用了与 Omega 相同的概念，如 Apollo 和 Tarcil。这些架构被称为共享状态调度。

🚧现状

• 作为共享状态调度架构的重要组成部分，乐观并发控制算法（OCC）已被数据库界研究了很长时间，但很少有研究旨在使其更适合共享状态调度环境。
  • 迄今为止，研究人员主要关注于提出新的调度架构和调度算法。
  • 此外，很少有人关注对共享状态调度中采用的 OCC 进行扩展。然而，在这些架构中，OCC 是影响调度器吞吐量的主要因素。对于共享状态调度来说，为了实现更好的效率和鲁棒性，在这一领域进行一些研究是非常必要的。
    • 作为共享状态调度的典型实现，Omega 给出了集群调度系统中事务的定义。然后采用粗粒度冲突检测和细粒度冲突检测两种OCC方法来控制调度事务的并发提交。
• 在具体应用中，如图1所示，当集群的闲置资源足以满足到达作业时，与粗粒度冲突检测相比，细粒度冲突检测表现良好，冲突率降低了2-3倍，但当集群的闲置资源有限且竞争激烈时，两种OCC都会忽略检测大量有害冲突。
  • 在本文中，我们将有害冲突定义为任务的资源需求未被验证为冲突，但可能让其请求的机器超额承载。
    • 调度器通过使用这些 OCC 无法意识到这些冲突，并将这些任务分派到没有足够资源的处理机上。
    • 在谷歌的集群管理系统 Borg 中，当任务请求的机器没有足够的可用资源来处理新任务时，它会抢占（杀死）优先级较低的任务，或拒绝该任务并将其排入待处理队列。然后可能会出现抢占级联。
  • 然而，提高几个百分点的利用率就能节省数百万美元。在研究人员和开发人员的努力下，集群的利用率与日俱增。
  • 因此，大量有害冲突将是一个不容忽视的问题。
• 另一方面，虽然有一些处理有害冲突的机制，但与在验证阶段检测和处理有害冲突的成本相比，在任务派发后处理冲突的成本更高。
  

🛩创新

• 本文提出了一种适用于共享状态调度架构的扩展细粒度冲突检测方法。该方法扩展了原有细粒度冲突检测方法的验证标准，使其能够在高并发调度事务下检测复杂的并发冲突。
  • 我们的解决方案倾向于在任务派发前通过 OCC 减少有害冲突。因此，我们提出了一种扩展的细粒度冲突检测方法来实现这一目标。
    • 首先，这种检测方法扩展了细粒度冲突检测方法的验证条件。
    • 其次，为了实现扩展的验证条件，除了单元状态外，我们还使用了另一个全局对象（称为活动索赔数组）来帮助检测有害冲突。
  • 最后，我们重写了欧米茄的公共模拟器，并在该模拟器中实现了我们的 OCC。

📊效果

• 我们使用 Google 的跟踪数据进行了一系列实验。实验结果表明，在高负载情况下，与原来的细粒度冲突检测方法相比，我们的方法减少了 60% 的有害冲突数量，而且只导致调度器性能下降到可以忽略不计的程度。

⛳️未来机会

• 🧠疑问

1. 本文的假设是基于Omega而非Fuxi2.0，因此假设状态同步是实时的，不存在影子资源等问题。要解决的问题为：多个调度器同时拿着完整的资源状态，同时做出决策，此时可能出现的冲突需要被消解。
2. 冲突检测是调度器层面还是状态管理器层面？
   1. 状态管理器层面。
3. 场景是什么？请求申请了多少资源量就会用多少资源量？还是会超用？
   1. 请求申请了多少资源量就会用多少资源量。
4. 细粒度和粗粒度冲突检测的区别是什么？
   1. 粗粒度冲突检测：当验证一个请求时，如果其请求的机器序列号已被其他并发调度事务占用，则该请求为冲突请求。
      1. 该条件可形式化为${C}{i}.ms!={M}{share}.msC_{i}C_{i}.msC_iC_{i}.ms{M}_{share}.ms$是当前共享状态信息中同一台机器的序列号。
      2. 仅判断是否有多个请求被调度到同一台机器，即使这台机器上资源量充足、足以服务多个请求，也被视为冲突并触发重调度。
   2. 细粒度冲突检测：不受机器序列号是否发生变化的影响，它检索共享单元的状态，只在验证时刻判断可用资源是否能容纳任务。
      1. 其验证条件可形式化为。变量是请求请求的资源，变量是机器中当前可用的资源。
      2. 如果可用资源小于该请求要求所请求的资源，则该请求被检测为冲突。
5. 细粒度冲突检测有什么问题？
   1. 意识不到有害冲突。原因是：我们发现粗粒度冲突检测和细粒度冲突检测方法都无法检测到一些有害的冲突。
      1. 以细粒度冲突检测为例，如果 调度程序X 想把需要0.5个CPU内核的 任务T1 放在 E机器 上，而 调度程序Y 想把需要1.0个CPU内核的 任务T2 放在 E机器 上。机器E 有 1.2 个备用 CPU 内核。如果在 调度程序X 和调度程序Y 的验证阶段没有更改全局机器信息（？意思是同时发生？），那么这两个请求都被验证为 “非”。那么这两个请求都会被验证为无冲突，并进入提交阶段。但只有一个任务能成功部署到 E机器上，但两个调度器都会进入提交阶段。然后两个任务都被分派到机器E。延迟提交的要求可能会冲突，但尚未被这些 OCC 验证为冲突。
      2. 这种行为会影响一个调度程序为其任务寻找另一个更合适的机器（即重调度）。更严重的是，这种过度承诺行为可能会导致机器故障和单元状态信息错误。因此，稳健的 OCC 应尽可能减少这些被忽视的冲突。
6. 更细粒度的冲突理论上会花费更大的开销、或会过于保守导致资源浪费，这两方面的代价是否被刻画？如果已被刻画且能够豁免代价，方法是什么？
   1. 方法：为了扩展细粒度冲突检测方法的验证条件，我们引入了一个类似于单元状态的持久对象来记录活动请求，并用它来帮助检测冲突。它是一个机器编号长度的数组，记录了每台机器的活动并发请求。我们会在事务提交验证时添加新的活动请求，并在验证操作完成后删除过时的请求。有了活动索赔信息，我们方法的验证条件就会发生变化。
   2. 我的评价：本质上就是加了个锁，使得不会存在并发检测冲突。
7. “有害冲突”的比例大概在多少？优化的必要性有多大？
   1. 所定位的“有害冲突”问题听起来并不严重，因此仅设计了很简单的方法就能解决问题。
8. 核心逻辑：单体式调度有性能瓶颈，分布式调度能提高效率->分布式调度中状态共享是一种被广泛使用的架构->状态共享中OOC是影响吞吐量的主要因素，现有研究很少关注OOC优化->现有OOC方式无法意识到“有害冲突”，即使细粒度冲突比粗粒度冲突冲突率低很多，但还是有很多“有害冲突”->粗粒度冲突检测导致频繁重调度，细粒度冲突检测导致冲突不被发现，进而导致任务失败、甚至导致级联抢占问题，影响集群利用率。
9. 冲突是怎么影响利用率的？是重调度浪费时间？还是已运行任务会被杀死？
10. 什么情况下会出现级联抢占？导致的代价有多大？在什么场景下特别需要优化？
11. 现实场景中优化目标会是什么？什么情况下会出现多个优化目标相互冲突并且导致严重后果？是否有可能作为一个新研究方向？

---

---

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

🗺参考文献

[1] Libo He, Shaowen Yao, and Wei Zhou. 2016. An extended fine-grained conflict detection method for shared-state scheduling in large scale cluster. In Proceedings of the 1st International Conference on Intelligent Information Processing (ICIIP ‘16). Association for Computing Machinery, New York, NY, USA, Article 29, 1–7. https://doi.org/10.1145/3028842.3028871