关于云计算资源调度的一些思考

在学术界和工业界，云计算资源调度问题都被认为与非确定性多项式(Non-deterministic polynomial)优化问题一样困难，即一个NP问题。因此，解决相对常规的调度问题的算法在问题的规模增大时可能会遭受维度的破坏。随着云计算的不断发展和复杂性的增加，这个问题变得更具挑战性。

什么是资源调度？

资源调度是指在特定的资源环境下，根据一定的资源使用规则，在不同的资源使用者之间进行资源调整的过程。这些资源使用者对应着不同的计算任务(例如一个虚拟解决方案)，每个计算任务存操作系统中对应于一个或者多个进程。通常有两种途径可以实现计算任务的资源调度:在计算任务所在的机器上调整分配给它的资源使用量，或者将计算任务转移到其他机器上。

下图是将计算任务迁移到其他机器上的一个例子。在这个例子中，物理资源A(如一台物理服务器)的使用率远高于物理资源B，通过将计算任务1从物理资源A迁移到物理资源B，使得资源的使用更加均衡和合理，从而达到负载均衡的目的。

对于云平台的调度研究不仅仅让每一个云计算厂家造了N多个轮子，也因此毕业了不少这个研究方向的博士硕士研究生，对于Kubernetes的调度分析网上也已经烂大街了，例如XXX基于Kubernetes的调度实践等等这样的分享演讲也到处都是，大家都在讨论用什么算法，提升了多少的性能，可并没发现有人讨论云平台的调度究竟是一个什么样的问题？

云资源调度问题

云资源调度问题主要分为三层：为应用程序调度资源，调度虚拟资源（如虚拟机）到物理资源，物理资源调度和落地。而且，在每一层可以有多个不同的目标进行优化。在应用层，可能要满足用户指定的服务水平目标（SLO） - 即调度QoS，优化提供商的效率，或者在两者之间协商一些妥协。在虚拟资源层，可以优化负载均衡，提高资源利用率例如CPU和内存的占比，此外还有成本效益或节能。

对于较小规模的云资源调度问题，即使使用穷举调度算法将问题转换为组合优化的问题也可以满足需求。然而，作为一个NP难题，我们需要随着维度的增加或要优化的变量的数量而打破穷举或枚举的方法。因此，我们需要转向启发式的方法。“在所有的启发式方法中，最强大的是基于总体的EC算法，它有效地在团队成员之间交换搜索信息。由于云资源调度的问题被认为是NP难题，所以它的难处理性最好通过EC算法来解决。“这些”EC“算法是什么？不是最终的一致性，在这种情况下，它指的是“进化计算” - 例如最常提到的是遗传算法，粒子群算法和蚁群优以及花授粉算法。

就我自己粗浅认识而言，虽然我们说有很多的解决方案，例如OpenStack Nova、kube-scheduler、oVirt等等，但我们不会见到一个通用的万能的方案或者可以完全解决调度中可能增加的影响因子和支持硬件以及不同的需求的问题。调度这个问题本身不是我们拿来别人的方案来解决我们自己的问题，而是我们的问题应该使用什么样的方案来解决，我觉得这两种说法是有很大区别的。

为什么说这是个不确定性问题？

首先我们面临三个挑战：

第一个挑战是平台状态一致性问题，相信做过云资源调度的同学一定遇到过超售的问题，这就是因为新旧数据的交叉导致在调度的过程出现了临界的数据不一致。

第二个挑战是调度需求本身可能随时间而改变，这也是最不确定性的问题，这种不确定性可能来自于用户，也可能来自对手，需要考虑特殊的调度请求又要满足软件硬件的兼容。

第三个挑战是规模，随着云计算的迅速发展，资源，用户，任务和工作流程的规模不断扩大。未来越来越多的任务将在云环境中处理，越来越多的云资源需要在互联网普及的环境中进行管理和调度。

所以，想要设计或者实现符合自己的云平台调度方案，第一点就是定义需求边界和成本。

最难的我觉得不是能不能实现这样的一个调度器或者设计一个牛逼的调度算法，而是我们应该怎么定义我们的调度需求边界，我们比较看重什么因素，哪些是我们完全不需要考虑兼容的，哪些在未来可能要解决的问题，舍弃与妥协。比如在平台一致性问题的解决中可能我们需要避免在负载高的宿主机上调度，但这样可能会降低资源的使用率。正如我们在考虑架构时需要首先考虑的架构的边界，没有边界的方案纯属扯淡。

比如，我需要四个CPU，你是不够的话是就不给还是先给你两个用着，能不能凑合下，这些都是弹性的，动态的，可商量的。还有就是你的响应性能是多少的要求呢？比如在我完成新版的调度之前的那一个版本的调度也是可用的，照样支撑了数万台机器的调度并为亿万用户正常服务，当上线新版的调度后，调度性能上升了将近两个数量级，但对于外界使用是无感知的，创建一台机器需要分钟级别的时间，而调度性能只是从秒级到毫秒级。还有就是是不是有对特殊设备的支持，例如GPU，特定的CPU等等，是不是要支持网络和磁盘的调度，支持不支持本地磁盘等等。有时候可能还需要判断是IO类型的主机还是计算类型的主机。另外还有些问题可能是我们自己臆造的，例如我们会不由自主的想，要不要体现调度的公平性，可不可以预测等等。但从我看到的而言，真正落地的有多少会去体现公平性，一般来说我们并不非要某一次调度一定是最优的，我们仅仅需要的是能命中合适机器；还有对于预测的一些理论大概在学术界比较盛行吧！

真正的生产环境的云平台调度主要在做两件事，可用性和低成本，即如何在低成本的情况下满足可用性。这一点学术界大概对花费考虑的不多，就我看来是这样，总觉得资源是足够的，这也是每年上百篇论文几乎没有落地的主要原因。另一个是算法真正的可行性，目前业界几乎所有的调度，最有效的算法还是基于规则和资源状态的调度。工业界最终的方向是盈利，所有的事情都会基于这一点，所以提高调度的性能，提高资源的使用率或者说降低成本将是主要的功能。

调度，一直在路上！

主要来源：知乎专栏 “进击的云计算”