随机加权调度器

包含您的 Launchpad 蓝图的 URL

https://blueprints.launchpad.net/manila/+spec/stochastic-weighing-scheduler

过滤器调度器是 Manila 的事实上的标准调度器，并且具有许多理想的特性。然而，在某些情况下，很难或不可能让它做出正确的决策。我认为一些小的调整可以帮助简化管理员的生活。

问题描述

我关注 2 个具体问题

  1. 当存在多个非完全相同的后端时，很难确保负载在所有后端之间均匀分布。考虑几个“大型”后端与一些“小型”后端混合的情况。即使它们来自同一供应商，默认情况下，新的共享也会独占地分配给大型后端，直到空闲空间降低到与小型后端相同的水平。可以通过使用除空闲空间以外的其他内容来加权主机来解决这个问题，但无论您选择什么，只要后端不相同，您都会遇到类似的问题。

  2. 即使管理员能够确保所有后端在各个方面都相同，云最终可能需要通过添加新的存储后端来扩展。当发生这种情况时，将存在一批全新的空后端和大部分已满的后端。无论您使用哪种加权函数，最初 100% 的新请求都将安排在新的后端上。根据加权函数的优劣，可能需要很长时间才能开始将新请求发送到旧后端，在此期间，系统性能可能会大幅下降。如果升级很小，这个问题尤其严重：考虑在一个具有 10 个现有后端系统的系统中添加 1 个新后端。如果 100% 的新共享都发送到新后端，那么在一段时间内，单个后端将承受 10 倍的负载。

存在一个现有的部分解决方案来解决上述问题——优良度加权器——但值得一提的是它有一些局限性。考虑一个理想的优良度函数——一个始终返回正确值的预言机，以便将最佳后端用于新的共享排序到顶部。由于优良度函数的输入（除可用空间外）仅每 60 秒评估一次，创建请求的爆发几乎总是会在 60 秒窗口内发送到相同的后端。虽然我们可以通过发送更频繁的更新来缩小此问题的时间窗口，但这本身也有成本，并且收益递减。在优良度函数不理想的更现实情况下，优良度函数输出反映基于最近创建请求的变化可能需要超过 60 秒。

用例

现有的调度器最擅长处理同构后端，并且依赖于与整个系统容量相比相对较低的创建请求速率，以便它可以及时获取做出最佳决策所需的信息。它也最擅长处理不随时间添加容量的情况。

我对使调度器在各种部署场景中表现良好感兴趣

  1. 混合供应商场景

  2. 来自单个供应商的硬件代际混合

  3. 硬件容量的混合（小型与大型配置）

  4. 向正在运行的云添加容量以应对增长

这些都是部署者/管理员关注的问题。拟议的解决方案的一部分是启用当今不可能实现的事情，但主要目标是使平均情况“正常工作”，以便管理员不必照看系统才能获得合理行为。

提议的变更

当前，过滤器调度器执行 3 项操作

  1. 获取所有池的列表，并过滤掉不适合给定创建请求的池。

  2. 基于可用的加权器之一为每个池生成权重。

  3. 对池进行排序并选择权重最高的池。

我将上述系统称为“胜者全得”，因为无论前两个权重是 100 和 0 还是 49 和 51，获胜者都会 100% 的时间获得请求。

我建议将现有的 HostWeightHandler 重命名为 OrderedHostWeightHandler，并向过滤器调度器添加一个新的权重处理程序，称为 StochasticHostWeightHandler。OrderedHostWeightHandler 将继续作为默认值，并且不会更改行为。新的权重处理程序将实现不同的行为，如下所示

在上述步骤 3 中，而不是简单地选择最高权重，权重处理程序将加总所有选择的权重，为每个池分配一个等于该主机权重的范围的子集，然后生成一个跨整个范围的随机数，并选择映射到该范围的池。

更简单地可视化上述算法的方法是想象一个抽奖。每个池都会获得与池的权重相等数量的抽奖券（假设权重归一化为 0-100）。通过抽奖选择获胜池。每个创建请求都会导致进行新的抽奖。

权重较高的池会获得更多的抽奖券，因此获胜的机会更高，但任何权重高于 0 的池都有一些获胜的机会。

上述算法的优点是它区分了权重接近（49 和 51）与权重差异很大的情况（0 和 100），因此即使一个池略好于另一个池，也不总是获胜。此外，它可以在权重输入未更新的 60 秒窗口内产生不同的结果，从而大大减少了缓慢共享统计更新带来的痛苦。

应该指出的是，该算法不仅要求权重正确归一化（当前的优良度加权器也要求这样做），而且权重在可能的整个值范围内应该是大致线性的。任何偏离线性“优良度”都可能导致做出错误的决策，因为这种方法固有的随机性。

备选方案

没有很多好的选择来处理相对于共享统计更新频率的突发请求问题。您可以更快地更新统计信息，但存在限制。限制是让调度器同步地从每个后端请求最新的共享统计信息。显然，这种方法无法扩展。

为了解决异构后端问题，我们有优良度函数，但选择一个在后端所有类型的变化中都能产生可接受结果的优良度函数具有挑战性。该提案保留了优良度函数，并在此基础上构建，以使其更强大，并且更能容忍不完美性。

数据模型影响

没有数据库更改。

REST API 影响

没有 REST API 更改。

安全影响

没有安全影响。

通知影响

没有通知影响。

其他最终用户影响

最终用户可能会间接体验到修改后的调度器所做的更好的（或可想而知地更差的）调度选择。

性能影响

没有性能影响。事实上，提出这种方法正是因为替代方案会产生性能影响，而我想避免这种情况。

其他部署者影响

我建议为调度器添加一个新类别的加权器。默认加权器将继续是现有的加权器。管理员需要有意修改加权器类配置选项才能观察到行为的变化。

开发人员影响

开发人员不会受到直接影响，但任何从事优良度函数或其他加权器工作的人都需要了解为了从这种新的调度器模式中获得良好的行为，线性度要求是什么。

为了避免意外地将非线性优良度值输入到随机加权调度器中，我们可能希望创建替代名称的各种权重或加权器，强制驱动程序作者明确选择新的方案，从而表明他们返回的权重是合适的线性权重。

实现

负责人

主要负责人

bswartz

工作项

这应该可以通过一个补丁来完成。

依赖项

  • 过滤器调度器 (manila)

  • 优良度加权器 (manila)

测试

测试此功能需要一个多后端配置（否则调度只是一个空操作）。

由于算法的正确性固有地需要随机性，因此很难编写自动功能测试用例，而不会破坏随机数生成。我建议我们依赖单元测试来确保正确性，因为在单元测试中“伪造”随机数很容易。

文档影响

需要更新开发文档，以向驱动程序作者解释对优良度函数有什么期望。

需要更新配置参考，以向部署者解释新的配置选项的作用。

参考资料

此规范是 Cinder 社区接受的任何想法的副本：https://github.com/openstack/cinder-specs/blob/master/specs/newton/stochastic-weighing-scheduler.rst