mClock 调度算法与 QoS

作者：楚

2024-03-06
湖南
本文字数：2758 字
阅读完需：约 9 分钟

调度与 QoS

在日常生活中，我们经常会对任务按照优先顺序进行排序，然后先处理优先级高的任务；这种根据单一维度来调度的场景比较简单，有时候需要的决策信息往往是多维度的。

例如，如果一个客服人员要同时服务投诉、业务、咨询三个窗口，业务和投诉窗口优先级较高，但是也不能完全不管咨询窗口的客户，确保每小时服务至少 10 个投诉和业务窗口的客户，每小时服务至少 3 个咨询窗口客户，如果还有精力，则按照 2:2:1 的优先级来服务，这样能保证较高的服务质量 QoS（Quality of Service），那么，我们该如何进行调度(服务客户先后顺序的决策)呢？

在生活中，我们可能会碰到这种决策问题，在软件系统中，亦是如此。

如果按照单一维度的优先级来进行调度（如 SFQ、WFQ 等），则会有一些服务的请求迟迟得不到调度，导致其“饿死”。

例如，对于病毒扫描服务，其需要的 IO 吞吐较大，但对时延要求较低，而 GUI 等交互服务，IO 吞吐较低，但对时延要求较高，所以我们需要优先保证 GUI 等服务的最低要求，同时额外的吞吐又可以按照比例进行分配。

对于此类调度，我们来看一篇论文《mClock: Handling Throughput Variability for Hypervisor IO Scheduling》是如何解决此类问题的。

mClock

mClock 是 vmware 为其虚拟机的 IO 调度所设计的，意为多维度时钟。

Tag

为每个服务(mClock 中称为虚拟机，本文称服务，方便理解)定义不同的 QoS，每个 QoS 有三个指标，按照指标为每个服务的请求打上三个 tag(标签)，调度器根据 tag 值来调度，以满足每个服务的 QoS。

QoS 指标

Reservation: 最小服务次数，OLTP 等对时延要求较高的服务，确保其最小的服务质量，使用 R 作为 tag
Limitation : 最大服务次数，吞吐较大而时延不敏感的服务，如备份服务，限制其服务次数，使用 L 作为 tag
Weight : 服务优先级比重，论文中使用 P 作为 tag

论文中 RD, OLTP, DM 分别表示远程桌面服务， OLTP 服务，数据迁移服务，如下图所示，其 QoS 不一样，RD 和 OLTP 对 Reservation 有要求，而 DM 没有 Reservation 要求，但是 Weight 值最大，而且限制了 DM 的最大服务次数，避免 DM 占满带宽。

下图为 mclock 算法对三种不同服务的 QPS 调度比对。

如果总吞吐 T 小于 500，则无法满足 RD 和 OLTP 最小额度要求，所以平均分配给他们
如果总吞吐 T 大于 500 小于 1500：则 RD 和 OLTP 都是 250，其他额度分配给 DM
如果 T 大于 1500 小于 2000：则按照 weight 进行分配，即 250:500:750
如果 T 大于等于 2000：DM 被限制在 1000 的 QPS，剩余额度按照 1:2 分配给 RD 和 OLTP

大致思想是：如果系统吞吐不满足所有服务的 QoS 的 reservation 总和，则按照 QoS 的 reservation 比例进行分配。否则尝试按照 weight 进行分配带宽，如果按 weight 分配的带宽不满足 reservation，则以 reservation 进行分配，满足则按照 weight 分配；

调度器

mclock 有两个维度的调度器，分别是基于绝对值(基于 R tag 调度)和基于相对值(基于 P tag 调度)的调度器。

优先使用绝对值调度器，选择所有服务的请求队列中，R tag 最小的那个请求，如果其 R tag 小于当前时间，则进行调度；如果没有请求可调度，则使用相对值调度器，从 P tag 中选择 P tag 值最小的请求，无论其 P tag 值是否小于当前时间。

Tag 分配

对于每个服务，按照其请求到达的先后顺序，给每个请求打上这 3 个标签，每个服务的标签以 1/Reservation、1/Weight 等步长进行等距分布。

以 Reservation tag 为例，reservation 步长为 1/reservation，当前时钟和前一个请求 R tag 值+步长中的最大的一个作为新请求的 R tag 值。公式如下：

如图所示，新请求根据当前时钟进行分配

如果新请求只根据前一个请求的 tag+1/r，则可能造成 R tag 值远远小于当前时钟，由于调度器按照最小 tag 值进行调度，这样就会导致其他服务的请求暂短的得不到调度。如下图所示，蓝色服务有一段时间没有请求了，那么新请求如果按照上一个请求 tag+1/r，则其 tag 值非常小(如红色虚线的椭圆)，导致红色服务请求虽然先到，也会被延后调度

Tag 的调整

weight tag 是一个相对值，所以就存在一个特殊情况需要考虑，如下图所示，如果蓝色服务已经调度到请求 8 了，而蓝色和红色服务都来了新请求(虚线格子)，如果不对蓝色的 P 进行调整，则会造成蓝色 9、10、11 请求的 P 值远大于红色 3 和 4，这样就导致了 weight 调度的失效。

论文伪代码如下：

调度

mClock 分两个阶段进行调度，

R tag 调度阶段：先根据根据 R tag 进行调度，从所有服务的请求列队中，选择一个 R tag 值最小的请求，如果此请求的 R tag 值小于当前时钟，则进行调度，否则进入 P tag 调度阶段
P tag 调度阶段：找出 L tag 小于当前时钟的服务，从这些服务的请求队列中，找出 P tag 最小的请求，对其进行调度，同时调整此服务的请求队列的 R tag，以确保 R tag 调度不会被 P tag 调度影响。

下图中，当前时钟等于 4，所有 R tag 都大于 4，则进行 P tag 调度，选择了红色虚线框中两个请求，如果不对 R9:P5 进行的 R tag 进行调整，时钟前进 9 之前，R tag 调度都不会进行公平调度，也就是 R9:P5 得不到调度。

论文伪代码如下

其他因素

由于 mclock 是 vmware 研究其存储层调度算法的产物，所以需要考虑一些其他因素，如突发 IO 流量、IO 请求类型、IO size，等等，这里就不进行赘述。

最后

我们再用 Golang 来实现一个简易版本的 mclock 算法https://github.com/ikenchina/mclock。

通过一个测试代码来模拟论文中对 DM、OLTP、DM 三个 VM 的调度，

func TestMClock(t *testing.T) {    // SLO    rdSlo := Slo{Reserve: 250, Weight: 100, Limit: 500000000}    oltpSlo := Slo{Reserve: 250, Weight: 200, Limit: 500000000}    dmSlot := Slo{Reserve: 0, Weight: 300, Limit: 1000}
    cases := []struct {        throughput uint64        rd         uint64        oltp       uint64        dm         uint64    }{{250, 125, 125, 0}, {500, 250, 250, 0}, {700, 250, 250, 200},        {875, 250, 250, 375}, {1500, 250, 500, 750}, {2000, 333, 667, 1000},        {2500, 500, 1000, 1000}, {3000, 667, 1333, 1000}}
    for _, da := range cases {        clis := []uint64{0, 0, 0}        clock := NewMClock(da.throughput)        for i := uint64(0); i < da.throughput; i++ {            clock.Enqueue(1, rdSlo, 1)            clock.Enqueue(2, oltpSlo, 2)            clock.Enqueue(3, dmSlot, 3)        }
        for i := uint64(0); i < da.throughput; i++ {            req := clock.Dequeue().(int)            clis[req-1]++        }        assert.Equal(t, da.rd, clis[0])        assert.Equal(t, da.oltp, clis[1])        assert.Equal(t, da.dm, clis[2])    }}