mClock paper, OSDI 2010

dmclock

前面一篇文章我详细解释了mClock算法的调度目标和设计原理，这篇文章我会详细介绍mClock的分布式版本dmclock的设计思想和原理。

在mClock的论文中，针对dmclock的设计原理只有两段内容，而且只有文字和公式，很难让人真正理解。dmclock算法相比mclock只改了一个地方，那就是标签的计算公式：

可以发现在Reservation标签的计算公式中由变为，、分别变为、。论文中对于这两个参数、这样解释：表示该用户在除所要发送请求的服务器外，距上次发送请求这个时间内在其他服务器完成的请求个数，而表示reservation阶段的结果，基本含义和相同。看到这个解释，你会觉得不仅非常拗口，而且难以理解。下面给你两个栗子，让你理解这两个参数的含义。

图片来自网络

现在看懂这两个栗子了吗？

两个栗子

不好意思，开个玩笑。下面进入正题，下图是一个分布式的简单模型，一个客户端向多个服务器发送请求，其中请求上的字母代表所要发送的服务器的标志（A、B、C）。假设仍然按照mClock的公式打标签，那么结果是用户参数的3倍：或者，也就是有几个服务器就翻几倍，这个应该很好理解，因为分布式版本中，每个服务器都会有一个mClock调度器同时调度。

这里采用添加虚拟请求的方法，客户端会向所有服务器发送自己的所有请求，除目标服务器外的请求作为虚拟请求，仍然按照mClock的计算公式计算标签值，但是不会被实际处理，相当于虚拟请求只是占了一个坑（标签值），但是没有处理时间。这样的话就不会出现“翻倍”的问题。下面我们对这个方案进行优化，请看下面这个图：

图中不再使用虚拟请求，而是统计当前请求前发送到其他服务器的请求个数作为当前请求的delay，对比前面的方案，你会发现这个方案十分巧妙。dmclock正是运用了这个方案，将delay值分别乘以、、。我们所需要计算的就是当前请求之前发送到其他服务器的请求个数即可，这个含义和或者类似。

讲到这里，你应该对dmclock的设计原理有了一定的了解。也许你会问，具体怎么实现呢？其实很简单，只要用一个map（C++、Java都有这个数据结构），为每个服务器存放完成请求个数，初始值为0。服务器每次完成请求时通过一个计数器记录全局完成的请求个数，每次客户端发送请求时，用全局请求个数减去要发送的服务器对应的map记录的值（初始值为0），然后用此时的全局请求个数更新该服务器对应的map中的值。具体实现细节，可以参考dmclock官方代码库：https://github.com/ceph/dmclock。

实现方法会有很多，上面只是介绍的其中一种。好了，关于dmclock就介绍到这里，详细细节请阅读原始论文或者在评论区给我留言，欢迎大家的讨论！

参考资料

• mClock论文原文：mClock: Handling Throughput Variability for Hypervisor IO Scheduling
• dmclock代码仓库：https://github.com/ceph/dmclock
• 分布式dmclock的灵感来源：Proportional-Share Scheduling for Distributed Storage Systems