mClock paper, OSDI 2010

最近有人找我請(qǐng)教mClock算法，我給他解釋完之后矛辕，他覺得我講的不對(duì)并搬出某技術(shù)網(wǎng)站的博客笑跛，如下圖：

某網(wǎng)站博客對(duì)mClock算法的解釋

我暗自一笑，說道“這篇文章完全理解錯(cuò)了如筛，下面請(qǐng)聽正解堡牡！“抒抬。

mClock的調(diào)度目標(biāo)

為什么我一看看那篇博客就立刻說他理解錯(cuò)了呢杨刨？其實(shí)不看mClock的算法原理，光看mClock的調(diào)度目標(biāo)我就能斷定那篇博客理解錯(cuò)了擦剑。下面我們一起來看看mClock的調(diào)度目標(biāo)妖胀，這里用一個(gè)簡(jiǎn)單的例子來解釋芥颈。假設(shè)有三個(gè)用戶分別是RD、OLTP赚抡、DM爬坑，他們的參數(shù)配置如下：

下圖是經(jīng)過mClock算法帶寬分配之后的理論結(jié)果：

mClock算法的調(diào)度目標(biāo)，來自mclock論文原文

如果你將上面博客的思想代入上圖驗(yàn)證的話涂臣，你會(huì)發(fā)現(xiàn)當(dāng)總帶寬為700之后盾计，就完全解釋不通了。那么怎么理解上圖呢赁遗？總結(jié)兩句話：用戶分配的帶寬要么等于所設(shè)置的Reservation值署辉，要么等于按照Weight分配的結(jié)果，要么等于Limit值岩四。當(dāng)按照Weight分配的結(jié)果大于用戶所設(shè)置的Reservation時(shí)哭尝，則用戶最終分配的帶寬為按照Weight分配的結(jié)果；當(dāng)按照Weight分配的結(jié)果小于用戶所設(shè)置的Reservation時(shí)剖煌，則帶寬分配的結(jié)果等于Reservation材鹦；當(dāng)按照Weight分配的結(jié)果大于用戶所設(shè)置的Limit時(shí)，則帶寬分配的結(jié)果等于Limit耕姊。

你可以將上面的總結(jié)代入上圖進(jìn)行驗(yàn)證桶唐，你會(huì)發(fā)現(xiàn)完全符合圖中的結(jié)果。那么怎么理解作者的這個(gè)思想呢茉兰？其實(shí)很簡(jiǎn)單莽红，mClock算法的思想來源于SFQ算法，這是一個(gè)按照權(quán)重分配帶寬的算法邦邦，而mClock算法是這個(gè)算法的增強(qiáng)版：它給SFQ算法（按照權(quán)重分配）增加了兩個(gè)限制安吁，也就是不能低于設(shè)置的預(yù)留值（reservation），也不能高于設(shè)置的上限值（limit）燃辖。這樣就很好理解為什么mClock算法使用這樣的調(diào)度目標(biāo)了鬼店。另外，我們需要知道m(xù)Clock相比SFQ算法黔龟，有三個(gè)參數(shù)Reservation妇智、Weight、Limit氏身，這三個(gè)參數(shù)的含義應(yīng)該也不用解釋了巍棱。

mClock的原理

既然理解了mClock的調(diào)度目標(biāo)，下面我們就進(jìn)入正題蛋欣。前面我們說過mClock算法來源于SFQ算法航徙，下面我們先來看下如何實(shí)現(xiàn)按照權(quán)重調(diào)度，假設(shè)有三個(gè)用戶A陷虎、B到踏、C杠袱，他們的權(quán)重分別為1/2，1/3窝稿，1/6

按照權(quán)重調(diào)度

每個(gè)用戶的請(qǐng)求以1/w為間隔依次打標(biāo)簽（假設(shè)用戶連續(xù)發(fā)送請(qǐng)求）楣富，那么A用戶每個(gè)請(qǐng)求的標(biāo)簽分別為2，4伴榔，6纹蝴，8，10踪少，...骗灶，B用戶的為3，6秉馏，9耙旦，12，...萝究，C用戶的請(qǐng)求標(biāo)簽為6免都，12，18帆竹，24绕娘，...。調(diào)度請(qǐng)求時(shí)按照標(biāo)簽大小調(diào)度栽连，調(diào)度結(jié)果如上圖所示险领。可以發(fā)現(xiàn)采用這種方法可以很容易實(shí)現(xiàn)按照權(quán)重分配帶寬秒紧。

但是mClock的作者發(fā)現(xiàn)绢陌，這種方法無法為用戶提供帶寬保證，當(dāng)用戶特別多或者系統(tǒng)總能力不高時(shí)熔恢，用戶很可能會(huì)拿到很少的帶寬脐湾，那么我們就希望設(shè)置一個(gè)帶寬下限來保證用戶的帶寬不低于這個(gè)值；相反叙淌，我也不希望用戶無限制的占用帶寬秤掌，那么我希望設(shè)置一個(gè)帶寬上限來限制用戶的帶寬不超過這個(gè)值∮セ簦基于這個(gè)思想闻鉴，mClock算法又引入兩個(gè)標(biāo)簽Reservation標(biāo)簽和Limit標(biāo)簽，同樣是按照1/Reservation或者1/Limit的間隔依次打標(biāo)簽茂洒。我覺得這也是mClock算法名字的由來：multi-clock孟岛，多個(gè)時(shí)鐘標(biāo)簽。

請(qǐng)求標(biāo)簽

下面我們來講mClock算法如何給請(qǐng)求打標(biāo)簽。當(dāng)請(qǐng)求到來時(shí)蚀苛，需要給每個(gè)請(qǐng)求打標(biāo)簽在验，標(biāo)簽包括三種：Reservation標(biāo)簽玷氏、Proportional標(biāo)簽（也叫Weight標(biāo)簽）堵未、Limit標(biāo)簽。下面是標(biāo)簽計(jì)算的公式盏触，其中表示第個(gè)用戶的第個(gè)請(qǐng)求的Reservation標(biāo)簽渗蟹，、以此類推赞辩，雌芽、、分別表示用戶設(shè)置的Reservation辨嗽、Weight世落、Limit參數(shù)。

對(duì)于Reservation標(biāo)簽糟需，某個(gè)請(qǐng)求的Reservation標(biāo)簽值為上一請(qǐng)求的Reservation標(biāo)簽加上和當(dāng)前時(shí)間的最大值屉佳，之所以這樣處理基于兩個(gè)理論：一是我希望請(qǐng)求按照的間隔被處理，二是當(dāng)用戶空閑的話則不會(huì)給你補(bǔ)償（當(dāng)某個(gè)客戶端的請(qǐng)求按照大于的間隔來洲押，也就是說某個(gè)客戶端出現(xiàn)了空閑的情況的話武花，這樣標(biāo)簽就被賦值為當(dāng)前時(shí)間）。第二點(diǎn)符合Reservation的一般共識(shí)杈帐，也就是如果給某用戶設(shè)置的預(yù)留帶寬沒有被使用体箕，則分配給其他用戶，不會(huì)給該用戶保留挑童。

類似地累铅，Weight標(biāo)簽、Limit標(biāo)簽也是同樣的道理站叼，但是有些許差異争群。對(duì)于Weight標(biāo)簽，由于它是相對(duì)值（沒有單位）大年，我們期望Weight標(biāo)簽始終按照的間隔换薄，但是當(dāng)某個(gè)客戶端由空閑變?yōu)榛钴S時(shí)，他的Weight標(biāo)簽就不再和時(shí)間呈線性關(guān)系了翔试；尤其是當(dāng)新的客戶端到達(dá)時(shí)轻要，二者的標(biāo)簽不再是同一個(gè)基準(zhǔn)點(diǎn)，因此需要將空閑的客戶端的Weight標(biāo)簽和新來的客戶端的基準(zhǔn)點(diǎn)對(duì)齊垦缅。那怎么對(duì)齊呢冲泥？有兩種方法：一是采用一個(gè)全局虛擬時(shí)間來輔助校正；二是通過最小Weight標(biāo)簽值與當(dāng)前時(shí)間的差來校正。mClock采用了后者凡恍，具體方法是當(dāng)某個(gè)空閑的客戶端有新請(qǐng)求到達(dá)時(shí)志秃，計(jì)算最小Weight標(biāo)簽與當(dāng)前時(shí)間t的差，然后更新其所有請(qǐng)求的Weight標(biāo)簽嚼酝，偽代碼如下：

Limit標(biāo)簽的計(jì)算方法也一樣浮还，但Limit標(biāo)簽的作用是用來限制Weight階段請(qǐng)求被調(diào)度的個(gè)數(shù)的，當(dāng)Limit標(biāo)簽仍然小于當(dāng)前時(shí)間闽巩，表示完成的請(qǐng)求個(gè)數(shù)仍然沒有達(dá)到limit所設(shè)置的請(qǐng)求個(gè)數(shù)钧舌；相反，當(dāng)Limit標(biāo)簽大于當(dāng)前時(shí)間時(shí)涎跨，表示已經(jīng)達(dá)到Limit所設(shè)置的請(qǐng)求個(gè)數(shù)洼冻，此時(shí)不再入隊(duì)。

請(qǐng)求調(diào)度

了解了mClock如何打標(biāo)簽隅很，可能你還無法理解mClock的設(shè)計(jì)原理撞牢，經(jīng)過下面這一節(jié)你一定會(huì)理解mClock算法。

請(qǐng)求調(diào)度總共有兩個(gè)階段：Constraint-based階段（可以理解為Reservation階段）和Weight-based階段（可以理解為Weight階段）叔营。你要知道屋彪，一個(gè)請(qǐng)求要么從Reservation階段被調(diào)度，要么從Weight階段被調(diào)度审编。你可以這樣想撼班，有兩個(gè)隊(duì)列，一個(gè)隊(duì)列按照Reservation標(biāo)簽的大小對(duì)請(qǐng)求進(jìn)行排序（我們稱之為Reservation隊(duì)列）垒酬，另外一個(gè)隊(duì)列按照Weight標(biāo)簽的大小進(jìn)行排序（我們稱之為Weight隊(duì)列）砰嘁。首先，mClock算法每次從Reservation階段開始勘究，也就是會(huì)先檢查Reservation隊(duì)列是否有請(qǐng)求矮湘，如果有則先從Reservation隊(duì)列的請(qǐng)求先被處理，直到每個(gè)用戶的Reservation標(biāo)簽值大于當(dāng)前時(shí)間口糕∶逖簦看到這里你可能會(huì)問，為什么滿足這個(gè)條件用戶的Reservation階段就結(jié)束了呢景描？這是因?yàn)橛脩舻腞eservation標(biāo)簽表示用戶應(yīng)當(dāng)被調(diào)度的時(shí)間十办，當(dāng)這個(gè)時(shí)間大于當(dāng)前時(shí)間時(shí)，表示該請(qǐng)求還未到達(dá)調(diào)度時(shí)間超棺。

當(dāng)Reservation階段結(jié)束后向族，此時(shí)進(jìn)入Weight階段。Weight階段同樣是按照標(biāo)簽的大小依次調(diào)度棠绘，直到每個(gè)用戶的Limit標(biāo)簽值大于當(dāng)前時(shí)間件相，這里的判斷條件和Reservation階段的類似再扭。另外，每次在Weight階段調(diào)度一個(gè)請(qǐng)求之后夜矗，需要對(duì)所有Reservation標(biāo)簽進(jìn)行調(diào)整：

Reservation標(biāo)簽調(diào)整

這個(gè)很好理解泛范，因?yàn)楫?dāng)用戶的請(qǐng)求從Weight階段被調(diào)度了之后，那么Reservation標(biāo)簽中間就會(huì)出現(xiàn)空檔紊撕，為了保證用戶的Reservation罢荡，必須對(duì)Reservation標(biāo)簽向前平移，也就是每調(diào)度一個(gè)Weight標(biāo)簽逛揩，則Reservation標(biāo)簽向前移動(dòng)一個(gè)柠傍，也就是減去麸俘。

現(xiàn)在請(qǐng)求的調(diào)度過程已經(jīng)講完了辩稽。這個(gè)時(shí)候你可能還是一頭霧水，別急从媚，聽我來給你解釋：當(dāng)用戶按照權(quán)重分配的帶寬小于Reservation時(shí)逞泄，按照上面的原理，那么該用戶的請(qǐng)求會(huì)在Reservation階段全部被調(diào)度完成拜效，Weight階段不會(huì)有該用戶的請(qǐng)求喷众，最終的結(jié)果就是用戶每秒被調(diào)度了Reservation個(gè)請(qǐng)求蔓彩；相反滤蝠，當(dāng)用戶按照權(quán)重分配的帶寬大于Reservation時(shí)，用戶有一部分請(qǐng)求會(huì)在Reservation階段被調(diào)度齐邦，剩余的請(qǐng)求在Weight階段被調(diào)度赴穗，將二者加起來的結(jié)果是剩余帶寬按照權(quán)重分配的結(jié)果憔四。

現(xiàn)在你理解mClock算法了嗎？如果有什么疑問般眉，歡迎在評(píng)論區(qū)與我交流了赵。

其他

關(guān)于該算法的具體細(xì)節(jié)，請(qǐng)參考mClock的原始論文甸赃。下一篇文章柿汛，我會(huì)介紹該算法的分布式版本——dmClock的實(shí)現(xiàn)原理。

這篇論文mClock: Handling Throughput Variability for Hypervisor IO Scheduling發(fā)表于OSDI 2010埠对，作者分別來自VMware公司络断、惠普實(shí)驗(yàn)室以及萊斯大學(xué)（被譽(yù)為美國(guó)南方哈佛之一，同實(shí)驗(yàn)室的一個(gè)大佬申請(qǐng)到了該學(xué)校）项玛。OSDI這個(gè)會(huì)議在我們實(shí)驗(yàn)室的地位是SS級(jí)別的貌笨，其他級(jí)別分別是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設(shè)計(jì)原理與實(shí)現(xiàn)第五章：控制先行——存儲(chǔ)服務(wù)質(zhì)量QoS