最近有人找我请教mClock算法，我给他解释完之后，他觉得我讲的不对并搬出某技术网站的博客，如下图：
我暗自一笑，说道“这篇文章完全理解错了，下面请听正解！“。
mClock的调度目标
为什么我一看看那篇博客就立刻说他理解错了呢？其实不看mClock的算法原理，光看mClock的调度目标我就能断定那篇博客理解错了。下面我们一起来看看mClock的调度目标，这里用一个简单的例子来解释。假设有三个用户分别是RD、OLTP、DM，他们的参数配置如下：
| Client | Reservation | Weight | Limit |
|---|---|---|---|
| RD | 250 | 100 | Unlimited |
| OLTP | 250 | 200 | Unlimited |
| DM | 0 | 300 | 1000 |
下图是经过mClock算法带宽分配之后的理论结果：
如果你将上面博客的思想代入上图验证的话，你会发现当总带宽为700之后，就完全解释不通了。那么怎么理解上图呢？总结两句话：用户分配的带宽要么等于所设置的Reservation值，要么等于按照Weight分配的结果，要么等于Limit值。当按照Weight分配的结果大于用户所设置的Reservation时，则用户最终分配的带宽为按照Weight分配的结果；当按照Weight分配的结果小于用户所设置的Reservation时，则带宽分配的结果等于Reservation；当按照Weight分配的结果大于用户所设置的Limit时，则带宽分配的结果等于Limit。
你可以将上面的总结代入上图进行验证，你会发现完全符合图中的结果。那么怎么理解作者的这个思想呢？其实很简单，mClock算法的思想来源于SFQ算法，这是一个按照权重分配带宽的算法，而mClock算法是这个算法的增强版：它给SFQ算法（按照权重分配）增加了两个限制，也就是不能低于设置的预留值（reservation），也不能高于设置的上限值（limit）。这样就很好理解为什么mClock算法使用这样的调度目标了。另外，我们需要知道mClock相比SFQ算法，有三个参数Reservation、Weight、Limit，这三个参数的含义应该也不用解释了。
mClock的原理
既然理解了mClock的调度目标，下面我们就进入正题。前面我们说过mClock算法来源于SFQ算法，下面我们先来看下如何实现按照权重调度，假设有三个用户A、B、C，他们的权重分别为1/2，1/3，1/6
每个用户的请求以1/w为间隔依次打标签（假设用户连续发送请求），那么A用户每个请求的标签分别为2，4，6，8，10，...，B用户的为3，6，9，12，...，C用户的请求标签为6，12，18，24，...。调度请求时按照标签大小调度，调度结果如上图所示。可以发现采用这种方法可以很容易实现按照权重分配带宽。
但是mClock的作者发现，这种方法无法为用户提供带宽保证，当用户特别多或者系统总能力不高时，用户很可能会拿到很少的带宽，那么我们就希望设置一个带宽下限来保证用户的带宽不低于这个值；相反，我也不希望用户无限制的占用带宽，那么我希望设置一个带宽上限来限制用户的带宽不超过这个值。基于这个思想，mClock算法又引入两个标签Reservation标签和Limit标签，同样是按照1/Reservation或者1/Limit的间隔依次打标签。我觉得这也是mClock算法名字的由来：multi-clock，多个时钟标签。
请求标签
下面我们来讲mClock算法如何给请求打标签。当请求到来时，需要给每个请求打标签，标签包括三种：Reservation标签、Proportional标签（也叫Weight标签）、Limit标签。下面是标签计算的公式，其中表示第
个用户的第
个请求的Reservation标签，
、
以此类推，
、
、
分别表示用户设置的Reservation、Weight、Limit参数。
对于Reservation标签，某个请求的Reservation标签值为上一请求的Reservation标签加上和当前时间
的最大值，之所以这样处理基于两个理论：一是我希望请求按照
的间隔被处理，二是当用户空闲的话则不会给你补偿（当某个客户端的请求按照大于
的间隔来，也就是说某个客户端出现了空闲的情况的话，这样标签就被赋值为当前时间）。第二点符合Reservation的一般共识，也就是如果给某用户设置的预留带宽没有被使用，则分配给其他用户，不会给该用户保留。
类似地，Weight标签、Limit标签也是同样的道理，但是有些许差异。对于Weight标签，由于它是相对值（没有单位），我们期望Weight标签始终按照的间隔，但是当某个客户端由空闲变为活跃时，他的Weight标签就不再和时间呈线性关系了；尤其是当新的客户端到达时，二者的标签不再是同一个基准点，因此需要将空闲的客户端的Weight标签和新来的客户端的基准点对齐。那怎么对齐呢？有两种方法：一是采用一个全局虚拟时间来辅助校正；二是通过最小Weight标签值与当前时间的差来校正。mClock采用了后者，具体方法是当某个空闲的客户端有新请求到达时，计算最小Weight标签与当前时间t的差，然后更新其所有请求的Weight标签，伪代码如下：
Limit标签的计算方法也一样，但Limit标签的作用是用来限制Weight阶段请求被调度的个数的，当Limit标签仍然小于当前时间，表示完成的请求个数仍然没有达到limit所设置的请求个数；相反，当Limit标签大于当前时间时，表示已经达到Limit所设置的请求个数，此时不再入队。
请求调度
了解了mClock如何打标签，可能你还无法理解mClock的设计原理，经过下面这一节你一定会理解mClock算法。
请求调度总共有两个阶段：Constraint-based阶段（可以理解为Reservation阶段）和Weight-based阶段（可以理解为Weight阶段）。你要知道，一个请求要么从Reservation阶段被调度，要么从Weight阶段被调度。你可以这样想，有两个队列，一个队列按照Reservation标签的大小对请求进行排序（我们称之为Reservation队列），另外一个队列按照Weight标签的大小进行排序（我们称之为Weight队列）。首先，mClock算法每次从Reservation阶段开始，也就是会先检查Reservation队列是否有请求，如果有则先从Reservation队列的请求先被处理，直到每个用户的Reservation标签值大于当前时间。看到这里你可能会问，为什么满足这个条件用户的Reservation阶段就结束了呢？这是因为用户的Reservation标签表示用户应当被调度的时间，当这个时间大于当前时间时，表示该请求还未到达调度时间。
当Reservation阶段结束后，此时进入Weight阶段。Weight阶段同样是按照标签的大小依次调度，直到每个用户的Limit标签值大于当前时间，这里的判断条件和Reservation阶段的类似。另外，每次在Weight阶段调度一个请求之后，需要对所有Reservation标签进行调整：
这个很好理解，因为当用户的请求从Weight阶段被调度了之后，那么Reservation标签中间就会出现空档，为了保证用户的Reservation，必须对Reservation标签向前平移，也就是每调度一个Weight标签，则Reservation标签向前移动一个，也就是减去
。
现在请求的调度过程已经讲完了。这个时候你可能还是一头雾水，别急，听我来给你解释：当用户按照权重分配的带宽小于Reservation时，按照上面的原理，那么该用户的请求会在Reservation阶段全部被调度完成，Weight阶段不会有该用户的请求，最终的结果就是用户每秒被调度了Reservation个请求；相反，当用户按照权重分配的带宽大于Reservation时，用户有一部分请求会在Reservation阶段被调度，剩余的请求在Weight阶段被调度，将二者加起来的结果是剩余带宽按照权重分配的结果。
现在你理解mClock算法了吗？如果有什么疑问，欢迎在评论区与我交流。
其他
关于该算法的具体细节，请参考mClock的原始论文。下一篇文章，我会介绍该算法的分布式版本——dmClock的实现原理。
这篇论文mClock: Handling Throughput Variability for Hypervisor IO Scheduling发表于OSDI 2010，作者分别来自VMware公司、惠普实验室以及莱斯大学（被誉为美国南方哈佛之一，同实验室的一个大佬申请到了该学校）。OSDI这个会议在我们实验室的地位是SS级别的，其他级别分别是S、AA、A、B+、B，足见其地位之高。
参考资料
- 前面提到的CSDN博客：https://blog.csdn.net/u011364612/article/details/53608278
- mClock论文原文：mClock: Handling Throughput Variability for Hypervisor IO Scheduling
- mClock论文Slide：https://www.usenix.org/legacy/events/osdi10/tech/slides/gulati.pdf
- Ceph设计原理与实现第五章：控制先行——存储服务质量QoS
