任 睿 馬久躍 隋秀峰 包云崗

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)2 (中國(guó)科學(xué)院大學(xué) 北京 100049)

?

一種減少長(zhǎng)尾延遲的分布式實(shí)時(shí)約束傳播方法

任 睿1,2馬久躍1,2隋秀峰1包云崗1

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100049)

(renrui@ict.ac.cn)

提出了一種在數(shù)據(jù)中心環(huán)境下用于減少長(zhǎng)尾延遲的分布式實(shí)時(shí)約束傳播方法，該方法能夠使當(dāng)前節(jié)點(diǎn)感知請(qǐng)求的全局響應(yīng)時(shí)間約束信息，并能夠?qū)⒄?qǐng)求的實(shí)時(shí)約束信息傳播到整個(gè)處理路徑；節(jié)點(diǎn)可以利用請(qǐng)求的實(shí)時(shí)約束信息進(jìn)行請(qǐng)求調(diào)度或加速請(qǐng)求執(zhí)行時(shí)間，以此來(lái)減少長(zhǎng)尾延遲現(xiàn)象.同時(shí)，針對(duì)劃分聚合模式和串行依賴模式2種數(shù)據(jù)中心應(yīng)用，提出了階段服務(wù)模型和并行單元模型，并基于這2種模型實(shí)現(xiàn)了分布式實(shí)時(shí)約束傳播框架.最后，在分布式實(shí)時(shí)約束傳播框架上實(shí)現(xiàn)了實(shí)時(shí)約束感知調(diào)度算法，通過(guò)實(shí)驗(yàn)進(jìn)行了簡(jiǎn)單的驗(yàn)證，初步的實(shí)驗(yàn)結(jié)果顯示了分布式實(shí)時(shí)約束傳播方法能夠在一定程度上減少長(zhǎng)尾延遲.

實(shí)時(shí)約束傳播;長(zhǎng)尾延遲;數(shù)據(jù)中心;劃分聚合模式;串行依賴模式

隨著互聯(lián)網(wǎng)應(yīng)用的普及，電子郵件、搜索、電子商務(wù)、社交網(wǎng)絡(luò)、在線視頻等互聯(lián)網(wǎng)服務(wù)已經(jīng)成為人們生活的一部分.對(duì)互聯(lián)網(wǎng)應(yīng)用來(lái)說(shuō)，服務(wù)質(zhì)量是互聯(lián)網(wǎng)應(yīng)用的關(guān)鍵指標(biāo)，快速的響應(yīng)時(shí)間不僅預(yù)示了好的用戶體驗(yàn)，成為互聯(lián)網(wǎng)企業(yè)讓用戶滿意、留住用戶的關(guān)鍵之一，同時(shí)也是互聯(lián)網(wǎng)企業(yè)收入的關(guān)鍵因素[1].有研究表明，如果服務(wù)響應(yīng)時(shí)間增加，公司收入就會(huì)減少.例如亞馬遜發(fā)現(xiàn)Amazon.com的加載時(shí)間每增加100 ms就會(huì)導(dǎo)致銷售額降低1%[2]；當(dāng)服務(wù)的響應(yīng)時(shí)間從0.4 s增加到0.9 s，谷歌的廣告收入會(huì)降低20%[3]；微軟搜索引擎Bing的服務(wù)響應(yīng)時(shí)間從50 ms增加到2 000 ms時(shí)，用戶滿意度下降了3.8%，而每個(gè)用戶帶給企業(yè)的收益下降了4.3%[4].

為了保障互聯(lián)網(wǎng)應(yīng)用的服務(wù)質(zhì)量，數(shù)據(jù)中心運(yùn)營(yíng)商通常會(huì)通過(guò)預(yù)留資源的方式來(lái)解決，但這樣做會(huì)降低數(shù)據(jù)中心的資源利用率.例如谷歌報(bào)告了某在線應(yīng)用數(shù)據(jù)中心5 000臺(tái)服務(wù)器在6個(gè)月期間的CPU利用率統(tǒng)計(jì)，該報(bào)告顯示，整個(gè)數(shù)據(jù)中心的平均CPU利用率僅為30%左右，資源利用率并不高；而同一時(shí)期，批處理負(fù)載的數(shù)據(jù)中心資源利用率為75%[5].

當(dāng)然，一些企業(yè)為了提高資源利用率，會(huì)將多個(gè)應(yīng)用部署到同一個(gè)節(jié)點(diǎn)上共享資源，但是資源共享又會(huì)帶來(lái)干擾，干擾則會(huì)進(jìn)一步影響在線應(yīng)用或延遲敏感應(yīng)用的服務(wù)質(zhì)量，導(dǎo)致不可避免的性能波動(dòng)，產(chǎn)生長(zhǎng)尾延遲現(xiàn)象[6]；而且長(zhǎng)尾延遲現(xiàn)象在數(shù)據(jù)中心環(huán)境下會(huì)被進(jìn)一步放大[6-7].因此，對(duì)很多互聯(lián)網(wǎng)企業(yè)來(lái)說(shuō)，他們不得不在資源利用率與服務(wù)質(zhì)量之間二選一.

面對(duì)數(shù)據(jù)中心資源利用率和應(yīng)用服務(wù)質(zhì)量的矛盾，本文針對(duì)如何降低性能波動(dòng)和減少長(zhǎng)尾延遲的問(wèn)題，提出了在數(shù)據(jù)中心環(huán)境下的一種分布式實(shí)時(shí)約束傳播方法，該方法能夠?qū)⒄?qǐng)求的全局響應(yīng)時(shí)間約束信息傳播到整個(gè)處理路徑[8].該設(shè)計(jì)方法受啟發(fā)于紐約曼哈頓的交通信號(hào)燈，紐約市交管中心會(huì)及時(shí)跟蹤曼哈頓島上所有交通信號(hào)燈的動(dòng)態(tài)變化，各個(gè)路口的信號(hào)燈被分割成多個(gè)有機(jī)的整體，即十幾個(gè)路口的信號(hào)燈會(huì)同時(shí)或依次變燈，例如一個(gè)紅燈之后的多個(gè)路口都變成綠燈，從而大大提高了車輛的通行速度.此外，我們分別針對(duì)串行依賴模式和劃分聚合模式的數(shù)據(jù)中心應(yīng)用，提出了階段服務(wù)模型和并行單元模型，將分布式實(shí)時(shí)約束傳播方法應(yīng)用到這2種模型上，實(shí)現(xiàn)了一個(gè)分布式實(shí)時(shí)約束傳播框架.最后，在分布式實(shí)時(shí)約束傳播框架上，我們利用在請(qǐng)求全生命周期過(guò)程中所傳播的實(shí)時(shí)約束信息來(lái)對(duì)請(qǐng)求進(jìn)行優(yōu)先級(jí)調(diào)度，用以減少長(zhǎng)尾延遲現(xiàn)象，并通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證.

1 國(guó)內(nèi)外相關(guān)工作

近年來(lái)，為了保障數(shù)據(jù)中心應(yīng)用的服務(wù)質(zhì)量，學(xué)術(shù)界、工業(yè)界在各個(gè)層次上進(jìn)行了探索.

谷歌的Dean與Barroso[6]闡述了數(shù)據(jù)中心的長(zhǎng)尾延遲問(wèn)題.他們分析了導(dǎo)致長(zhǎng)尾延遲的首要原因是資源共享，包括體系結(jié)構(gòu)層次的CPU核、Cache、訪存帶寬、網(wǎng)絡(luò)帶寬等，而干擾不僅來(lái)自應(yīng)用，還來(lái)自于系統(tǒng)軟件層次的后臺(tái)守護(hù)作業(yè)以及監(jiān)控作業(yè)等[1].此外，還有部分學(xué)者研究了不同資源對(duì)長(zhǎng)尾延遲和性能的影響各不相同，例如Ousterhout等人[9]分析了大規(guī)模數(shù)據(jù)分析框架的性能瓶頸，發(fā)現(xiàn)一些特定負(fù)載的性能主要受限于CPU，而網(wǎng)絡(luò)IO對(duì)性能的影響較小.

為了緩解干擾所引起的長(zhǎng)尾延遲現(xiàn)象，Dean等人[6]還介紹了谷歌所采用相關(guān)技術(shù)，例如操作系統(tǒng)容器隔離技術(shù)、應(yīng)用優(yōu)先級(jí)管理、請(qǐng)求備份、同步后臺(tái)管理進(jìn)程等[7].但是，谷歌采用的超時(shí)發(fā)送備份請(qǐng)求和同步后臺(tái)管理進(jìn)程等技術(shù)雖然對(duì)改善劃分聚合模式應(yīng)用的長(zhǎng)尾延遲有幫助，卻并不能顯著改善串行依賴模式應(yīng)用的響應(yīng)時(shí)間.此外，微軟對(duì)Bing搜索引擎則采用并行查詢的方式來(lái)減少響應(yīng)時(shí)間延遲，例如自適應(yīng)并行查詢方法[10]、可預(yù)測(cè)的并行查詢方法[11]、Few-to-Many增量并行方法[12]等，主要思路是通過(guò)增加搜索索引服務(wù)請(qǐng)求的執(zhí)行并行度，加快請(qǐng)求的響應(yīng)時(shí)間，而這種方法主要適用于改善劃分聚合模式應(yīng)用的長(zhǎng)尾延遲.

另一部分工作則是通過(guò)減少網(wǎng)絡(luò)延遲來(lái)減少長(zhǎng)尾延遲現(xiàn)象[13-16].例如Kapoor等人[13]提出了Chronos架構(gòu)，以降低數(shù)據(jù)中心應(yīng)用的長(zhǎng)尾延遲，該架構(gòu)基于NIC上應(yīng)用層數(shù)據(jù)包頭字段的請(qǐng)求劃分、應(yīng)用實(shí)例負(fù)載均衡和NIC負(fù)載均衡模塊的加載來(lái)消除關(guān)鍵通信路徑上的共享資源，如內(nèi)核和網(wǎng)絡(luò)協(xié)議棧，以減少應(yīng)用延遲以及相關(guān)干擾[1]；此外，DeTail[14]用于減少數(shù)據(jù)中心網(wǎng)絡(luò)中的網(wǎng)絡(luò)流完成時(shí)間延遲；DCTCP[15]是一個(gè)類似于TCP的網(wǎng)絡(luò)協(xié)議，可以容忍流高峰和減少短小流的延遲.D2TCP[16]是一種新的傳輸協(xié)議，可用于進(jìn)行帶寬分配和避免擁塞.

一部分學(xué)者則通過(guò)資源隔離或軟硬件調(diào)度技術(shù)來(lái)減少資源共享帶來(lái)的干擾，從而達(dá)到減少長(zhǎng)尾延遲的目的.目前，操作系統(tǒng)虛擬化技術(shù)[17-18]、共享緩存劃分技術(shù)[19-20]、共享DRAM顆粒劃分技術(shù)[21-22]等可以實(shí)現(xiàn)特定資源的隔離，從而保障多個(gè)應(yīng)用之間的性能隔離，減少性能干擾.軟硬件調(diào)度技術(shù)則可以盡量為高優(yōu)先級(jí)應(yīng)用分配更多的資源，例如Tang等人[23]提出了一種動(dòng)靜結(jié)合的編譯方法ReQoS，在確保高優(yōu)先級(jí)應(yīng)用的服務(wù)質(zhì)量的同時(shí)，讓低優(yōu)先級(jí)應(yīng)用也可以自適應(yīng)地執(zhí)行，可以減少高優(yōu)先級(jí)應(yīng)用的長(zhǎng)尾延遲.Bobtail[24]則是通過(guò)聯(lián)合調(diào)度的方法來(lái)減少數(shù)據(jù)中心應(yīng)用的長(zhǎng)尾延遲.

此外，還可以通過(guò)對(duì)請(qǐng)求響應(yīng)時(shí)間進(jìn)行建模和屬性分析來(lái)理解請(qǐng)求響應(yīng)延遲的波動(dòng)情況，例如Cipar等人[25]提出了一種同步SSP模型，該模型對(duì)BSP模型進(jìn)行了改進(jìn)，可用于避免落后者問(wèn)題.

除了數(shù)據(jù)中心應(yīng)用，由于移動(dòng)應(yīng)用越來(lái)越普及，而且移動(dòng)應(yīng)用的服務(wù)端一般會(huì)部署在數(shù)據(jù)中心，所以如何減少移動(dòng)應(yīng)用的端對(duì)端延遲也顯得越來(lái)越重要.例如微軟提出了AppInsight[26]和Timecard[27]，用于監(jiān)控移動(dòng)應(yīng)用請(qǐng)求在各個(gè)執(zhí)行階段的性能情況和控制移動(dòng)應(yīng)用的端對(duì)端延遲.

Fig. 1 The examples of request response variability range圖1 請(qǐng)求響應(yīng)時(shí)間波動(dòng)范圍舉例

2 數(shù)據(jù)中心應(yīng)用和長(zhǎng)尾延遲

2.1 數(shù)據(jù)中心應(yīng)用

在數(shù)據(jù)中心中，互聯(lián)網(wǎng)應(yīng)用大多會(huì)被分解為許多服務(wù)，然后將這些服務(wù)部署到數(shù)據(jù)中心的服務(wù)器上[1].一般而言，服務(wù)之間的耦合方式有2種[13]，而且這2種模式都會(huì)放大長(zhǎng)尾延遲現(xiàn)象.

2.2 長(zhǎng)尾延遲現(xiàn)象

無(wú)論是在單臺(tái)機(jī)器還是數(shù)據(jù)中心，由于資源共享、后臺(tái)守護(hù)作業(yè)、共享文件系統(tǒng)等因素，性能波動(dòng)和響應(yīng)延遲波動(dòng)是不可避免的[2,28].

在數(shù)據(jù)中心環(huán)境下，由于應(yīng)用的可擴(kuò)展性和分布式屬性，一般情況下，請(qǐng)求響應(yīng)的延遲波動(dòng)會(huì)被放大[6-7].例如圖1(a)顯示了在一臺(tái)機(jī)器上執(zhí)行Equake程序的執(zhí)行時(shí)間分布圖[29]，圖1(b)則顯示了谷歌某后端服務(wù)在某數(shù)據(jù)中心的響應(yīng)時(shí)間波動(dòng)情況[2].我們定義請(qǐng)求的響應(yīng)延遲波動(dòng)范圍為variabilityrange，請(qǐng)求的響應(yīng)延遲波動(dòng)范圍可通過(guò)式(1)計(jì)算得到，其中，Tmax為最大的請(qǐng)求響應(yīng)時(shí)間，Tmin為最小的請(qǐng)求響應(yīng)時(shí)間，Tavg為請(qǐng)求平均響應(yīng)時(shí)間.

variabilityrange=(Tmax-Tmin)Tavg×100%.

(1)

基于圖1中的數(shù)據(jù)，并根據(jù)上述定義分別計(jì)算單臺(tái)機(jī)器上Equake程序和數(shù)據(jù)中心某后端服務(wù)的響應(yīng)時(shí)間波動(dòng)范圍，發(fā)現(xiàn)單臺(tái)機(jī)器上Equake程序的響應(yīng)延遲波動(dòng)為5.42%，但是數(shù)據(jù)中心環(huán)境下后端服務(wù)的響應(yīng)延遲波動(dòng)為5980%，顯而易見，數(shù)據(jù)中心環(huán)境下的響應(yīng)延遲波動(dòng)遠(yuǎn)遠(yuǎn)大于單臺(tái)機(jī)器上的響應(yīng)延遲波動(dòng).

而數(shù)據(jù)中心環(huán)境下響應(yīng)延遲波動(dòng)范圍變大的原因在于：用戶請(qǐng)求可能會(huì)被劃分為多個(gè)子請(qǐng)求并扇出到成百上千臺(tái)機(jī)器上.假設(shè)一臺(tái)機(jī)器處理請(qǐng)求的平均響應(yīng)時(shí)間為1 ms，有1%的請(qǐng)求響應(yīng)時(shí)間會(huì)大于1 s；如果一個(gè)請(qǐng)求需要由100個(gè)這樣的節(jié)點(diǎn)一起處理，那么就會(huì)出現(xiàn)63%的請(qǐng)求響應(yīng)時(shí)間大于1 s；或者，請(qǐng)求的服務(wù)處于關(guān)鍵路徑上，每個(gè)服務(wù)的處理延遲會(huì)隨著請(qǐng)求在關(guān)鍵路徑上的傳遞而累加.如圖2所示，我們模擬了一個(gè)具有5個(gè)服務(wù)階段的串行依賴應(yīng)用，從服務(wù)階段S1到服務(wù)階段S5，90%的響應(yīng)延遲增大了2.6倍，95%的響應(yīng)延遲增大了2.4倍.

Fig. 2 Latency variability is amplified when service stage increases圖2 響應(yīng)時(shí)間延遲波動(dòng)隨服務(wù)階段的增加而放大

綜上所述，數(shù)據(jù)中心的2種應(yīng)用模式都會(huì)導(dǎo)致處理一個(gè)請(qǐng)求需要訪問(wèn)多臺(tái)服務(wù)器，因而只要有一臺(tái)服務(wù)器的處理速度受到干擾，就會(huì)導(dǎo)致整個(gè)請(qǐng)求的處理時(shí)間增加.由此，便產(chǎn)生了長(zhǎng)尾延遲現(xiàn)象.

3 分布式實(shí)時(shí)約束傳播方法

為了解決數(shù)據(jù)中心應(yīng)用的長(zhǎng)尾延遲問(wèn)題，我們提出了一個(gè)分布式實(shí)時(shí)約束傳播方法(distributed deadline propagation, D2P)，該方法綜合考慮期望響應(yīng)時(shí)間、請(qǐng)求執(zhí)行時(shí)間及網(wǎng)絡(luò)傳輸延遲來(lái)定義實(shí)時(shí)約束信息，能夠在請(qǐng)求的全生命周期上動(dòng)態(tài)更新并傳播請(qǐng)求的全局實(shí)時(shí)約束信息.本節(jié)將介紹分布式實(shí)時(shí)約束傳播方法如何運(yùn)用在串行依賴模式應(yīng)用和劃分聚合模式應(yīng)用上.

3.1.1 階段服務(wù)模型

我們定義了階段服務(wù)模型(stage-service model, SSM)來(lái)描述串行依賴模式應(yīng)用.在階段服務(wù)模型中，應(yīng)用由多個(gè)服務(wù)組成，各個(gè)服務(wù)之間的請(qǐng)求串行執(zhí)行，并且相鄰的2級(jí)服務(wù)請(qǐng)求具有一定的依賴關(guān)系.

階段服務(wù)模型如圖3所示，其中，階段服務(wù)模型中的相關(guān)參數(shù)為

N: 應(yīng)用所包含的服務(wù)階段的個(gè)數(shù)；

Si: 應(yīng)用的第i個(gè)服務(wù)階段,1≤i≤N；

LSi: 應(yīng)用請(qǐng)求在第i個(gè)服務(wù)階段的執(zhí)行時(shí)間；

CSi: 應(yīng)用請(qǐng)求在第i個(gè)服務(wù)階段處理完畢后，將請(qǐng)求發(fā)送到下一個(gè)服務(wù)階段所花費(fèi)的網(wǎng)絡(luò)延遲；

elapsed_timeSi: 服務(wù)階段Si的處理延遲，表示從生成請(qǐng)求開始，到第i個(gè)服務(wù)階段處理完畢所經(jīng)歷的總延遲；其中,綜合考慮了請(qǐng)求在傳輸過(guò)程中的網(wǎng)絡(luò)延遲和在服務(wù)階段上的請(qǐng)求處理延遲：

elapsed_timeSi=elapsed_timeSi-1+CSi-1+LSi.

(2)

Fig. 3 Stage-service model圖3 階段服務(wù)模型

3.1.2 基于SSM的分布式實(shí)時(shí)約束傳播方法

在階段服務(wù)模型下，由于服務(wù)都在關(guān)鍵路徑上，因此每個(gè)階段的服務(wù)請(qǐng)求處理延遲會(huì)累加.例如，在圖3中，如果一個(gè)請(qǐng)求在服務(wù)階段S2和服務(wù)階段S3中的處理延遲位于“長(zhǎng)尾”區(qū)域，那么，該請(qǐng)求的響應(yīng)時(shí)間將會(huì)被放大.本文介紹的分布式實(shí)時(shí)約束傳播方法會(huì)在請(qǐng)求的全生命周期中，實(shí)時(shí)記錄請(qǐng)求在每一個(gè)服務(wù)階段的處理延遲，并根據(jù)用戶期望的響應(yīng)時(shí)間實(shí)時(shí)調(diào)整下一個(gè)服務(wù)階段的請(qǐng)求處理時(shí)間，以達(dá)到減少長(zhǎng)尾延遲的目的.

Fig. 4 Parallel-unit model圖4 并行單元模型

在分布式實(shí)時(shí)約束傳播方法中，實(shí)時(shí)約束信息定義如下:

expected_deadline: 實(shí)時(shí)約束信息的初始值，表示用戶期望的請(qǐng)求響應(yīng)時(shí)間閾值.

deadlineSi:服務(wù)階段Si的實(shí)時(shí)約束信息，用elapsed_timeSi和expected_deadline之間的差值表示.當(dāng)請(qǐng)求傳遞時(shí)，請(qǐng)求在服務(wù)階段的實(shí)時(shí)約束信息可計(jì)算并更新為

deadlineSi=expected_deadline-elapsed_timeSi.

(3)

根據(jù)式(3),在請(qǐng)求的傳遞過(guò)程中，通過(guò)使用分布式實(shí)時(shí)約束傳播方法，可以在每一個(gè)服務(wù)階段更新實(shí)時(shí)約束信息deadlineSi，并將更新后的實(shí)時(shí)約束信息傳播給下一個(gè)服務(wù)階段.如果某個(gè)請(qǐng)求的deadlineSi值為0或負(fù)數(shù)，表明該請(qǐng)求已經(jīng)超時(shí)，即該請(qǐng)求已經(jīng)不滿足用戶期望的響應(yīng)時(shí)間閾值.這時(shí)，用戶可以對(duì)超時(shí)請(qǐng)求采取一些特殊的措施進(jìn)行處理.

當(dāng)請(qǐng)求在不同的服務(wù)階段進(jìn)行傳遞時(shí)，可以將請(qǐng)求的實(shí)時(shí)約束信息同時(shí)進(jìn)行傳播，那么，對(duì)每一個(gè)服務(wù)階段而言，系統(tǒng)可以利用實(shí)時(shí)約束信息進(jìn)行優(yōu)先級(jí)調(diào)度、資源分配或增加并行度，以此來(lái)加速緊急請(qǐng)求的處理速度.

3.2.1 并行單元模型

并行單元(parallel-unit,PU)包含一個(gè)聚合節(jié)點(diǎn)(aggregator)和多個(gè)工作節(jié)點(diǎn)(worker)，其中，聚合節(jié)點(diǎn)用于劃分請(qǐng)求和聚合工作節(jié)點(diǎn)的執(zhí)行結(jié)果，工作節(jié)點(diǎn)用于并行執(zhí)行請(qǐng)求.

此外，在1個(gè)并行單元中，還包含3個(gè)階段：劃分階段PP(partition-phase)、聚合階段AP(aggregate-phase)、計(jì)算階段CP(computation-phase)；其中，劃分階段和聚合階段在聚合節(jié)點(diǎn)上執(zhí)行，計(jì)算階段在工作節(jié)點(diǎn)上執(zhí)行.

并行單元模型如圖4所示，并行單元模型中的相關(guān)參數(shù)為

m: 并行單元中的工作節(jié)點(diǎn)個(gè)數(shù)；

Ai: 第i個(gè)聚合節(jié)點(diǎn)；

Wj: 第j個(gè)工作節(jié)點(diǎn),1≤j≤m；

PP: 聚合節(jié)點(diǎn)上的劃分階段；

AP: 聚合節(jié)點(diǎn)上的聚合階段；

CP: 工作節(jié)點(diǎn)上的計(jì)算階段；

p: 請(qǐng)求在并行單元中所處于的階段,p∈{PP,AP,CP}；

l: 請(qǐng)求在并行單元中所處的節(jié)點(diǎn),l∈{Ai,Wj}；

Ll_p：請(qǐng)求在節(jié)點(diǎn)l、階段p時(shí)的處理時(shí)間；

elapsed_timel_p: 請(qǐng)求經(jīng)過(guò)節(jié)點(diǎn)l、階段p后所花費(fèi)的總處理時(shí)間；

CWj: 請(qǐng)求從工作節(jié)點(diǎn)Wj返回結(jié)果到聚合節(jié)點(diǎn)時(shí)所花費(fèi)的網(wǎng)絡(luò)延遲.

3.2.2 基于PUM的分布式實(shí)時(shí)約束傳播方法

基于并行單元模型，我們也可以將分布式實(shí)時(shí)約束傳播方法運(yùn)用在劃分聚合模式的應(yīng)用上.

基于并行單元模型的分布式實(shí)時(shí)約束傳播方法如圖4所示，當(dāng)請(qǐng)求到達(dá)并行單元并且處于聚合節(jié)點(diǎn)的劃分階段，或者請(qǐng)求剛到達(dá)工作節(jié)點(diǎn)的計(jì)算階段，聚合節(jié)點(diǎn)和工作節(jié)點(diǎn)按照階段服務(wù)模型的實(shí)時(shí)約束信息計(jì)算方法(式(3))來(lái)更新劃分階段和計(jì)算階段的實(shí)時(shí)約束信息.當(dāng)工作節(jié)點(diǎn)返回請(qǐng)求計(jì)算結(jié)果并且在聚合節(jié)點(diǎn)進(jìn)行請(qǐng)求結(jié)果的聚合處理時(shí)，即聚合節(jié)點(diǎn)處于聚合階段，由于elapsed_timeAi_AP將受限于最慢的工作節(jié)點(diǎn)，并且還受到請(qǐng)求傳輸過(guò)程中網(wǎng)絡(luò)延遲的影響，所以其計(jì)算為

elapsed_timeAi_AP=

max(elapsed_timeWj_CP+CWj+LAi_AP).

(4)

那么，在并行單元的每一個(gè)階段上，實(shí)時(shí)約束信息計(jì)算并動(dòng)態(tài)更新為

deadlinel_p=expected_deadline-elapsed_timel_p,

l_p∈(Ai_PP,Wj_CP,Ai_AP).

(5)

4 分布式實(shí)時(shí)約束傳播框架

4.1 分布式實(shí)時(shí)約束傳播框架的工作流程

分布式實(shí)時(shí)約束傳播方法作為一種設(shè)計(jì)方法，可以實(shí)現(xiàn)在不同的分布式系統(tǒng)中.本文設(shè)計(jì)的分布式實(shí)時(shí)約束傳播框架包含2個(gè)模塊：1)實(shí)時(shí)約束傳播模塊(D2P module)，用于收集請(qǐng)求在各個(gè)階段節(jié)點(diǎn)上的處理延遲，為每個(gè)請(qǐng)求附加一個(gè)用于保存實(shí)時(shí)約束信息的實(shí)時(shí)約束信息域(deadline field)并初始化，在請(qǐng)求傳遞過(guò)程中計(jì)算并更新實(shí)時(shí)約束信息域，并在請(qǐng)求的整個(gè)生命周期上進(jìn)行傳播,并提供給請(qǐng)求加速模塊使用；2)請(qǐng)求加速模塊(request accelerating module)，利用實(shí)時(shí)約束傳播模塊提供的實(shí)時(shí)約束信息，進(jìn)行請(qǐng)求優(yōu)先級(jí)調(diào)度，用于加速緊急請(qǐng)求的執(zhí)行；或者增加請(qǐng)求的并發(fā)度，加快請(qǐng)求的執(zhí)行速度.

分布式實(shí)時(shí)約束傳播框架的工作流程主要包括3個(gè)步驟，如圖5所示：

Fig. 5 The workflow of D2P-enabled framework圖5 分布式實(shí)時(shí)約束傳播框架的工作流程

步驟1. 當(dāng)客戶端發(fā)出一個(gè)新請(qǐng)求，實(shí)時(shí)約束傳播模塊會(huì)為該請(qǐng)求附加一個(gè)實(shí)時(shí)約束信息域(deadline,PU_flag).然后，實(shí)時(shí)約束傳播模塊會(huì)用預(yù)先定義的請(qǐng)求期望響應(yīng)時(shí)間閾值expected_deadline來(lái)初始化deadline.如果該請(qǐng)求被劃分為多個(gè)子請(qǐng)求，那么就認(rèn)為該請(qǐng)求位于并行單元上，并設(shè)置PU_flag=1.當(dāng)PU_flag=1時(shí)，實(shí)時(shí)約束傳播模塊會(huì)使用基于并行單元模型的分布式實(shí)時(shí)約束傳播方法來(lái)計(jì)算和更新deadline；否則，實(shí)時(shí)約束傳播模塊使用基于階段服務(wù)模型的分布式實(shí)時(shí)約束傳播方法來(lái)計(jì)算和更新deadline.

步驟3. 當(dāng)請(qǐng)求在某一個(gè)服務(wù)階段或者并行單元上執(zhí)行完畢，實(shí)時(shí)約束傳播模塊會(huì)記錄這時(shí)候請(qǐng)求的elapsed_time，并使用式(3)(5)計(jì)算一個(gè)更新的deadline，并將更新后的deadline填入到請(qǐng)求的實(shí)時(shí)約束信息域.此后，更新的實(shí)時(shí)約束信息域會(huì)隨著請(qǐng)求傳播到下一個(gè)服務(wù)階段或并行單元，直到請(qǐng)求返回最終的結(jié)果.

4.2 利用分布式實(shí)時(shí)約束傳播框架減少長(zhǎng)尾延遲

一般來(lái)說(shuō)，目前主要有4種方法可用于保障服務(wù)質(zhì)量要求和減少長(zhǎng)尾延遲：

1) 調(diào)度方法.應(yīng)用級(jí)調(diào)度算法[28,30]、分布式實(shí)時(shí)調(diào)度算法[31]都可以用于提高緊急請(qǐng)求的優(yōu)先級(jí)，幫助緊急請(qǐng)求盡快完成.

2) 資源調(diào)整.通過(guò)增加緊急請(qǐng)求所需的某些資源，例如為緊急請(qǐng)求增加IO帶寬、共享緩存等[19,32]，以幫助緊急請(qǐng)求盡快完成，提升請(qǐng)求的執(zhí)行效率；或通過(guò)增加網(wǎng)絡(luò)帶寬、減少網(wǎng)絡(luò)擁塞等，以減少網(wǎng)絡(luò)傳輸上的長(zhǎng)尾延遲.

3) 增加并行度.隨著多核服務(wù)器的發(fā)展，單個(gè)請(qǐng)求可以利用多核資源并行執(zhí)行，這也是一種減少請(qǐng)求執(zhí)行時(shí)間的可行方法，尤其會(huì)對(duì)長(zhǎng)請(qǐng)求有效[10-12].

4) 調(diào)整精度[27].對(duì)一些互聯(lián)網(wǎng)在線應(yīng)用來(lái)說(shuō)，適當(dāng)?shù)亟档途葘?duì)用戶的體驗(yàn)影響不大，那么就可以通過(guò)適當(dāng)?shù)亟档途葋?lái)降低請(qǐng)求的響應(yīng)時(shí)間，以此減少長(zhǎng)尾延遲.

本節(jié)針對(duì)階段服務(wù)模型和并行單元模型，基于分布式實(shí)時(shí)約束傳播框架，介紹一種分布式實(shí)時(shí)約束感知的請(qǐng)求調(diào)度算法，用于減少請(qǐng)求處理延遲，以達(dá)到減少長(zhǎng)尾延遲的目的.在分布式實(shí)時(shí)約束感知的請(qǐng)求調(diào)度算法中，為了方便理解，我們直接使用deadline作為調(diào)度優(yōu)先級(jí)，當(dāng)某個(gè)請(qǐng)求的deadline的值越小，表明該請(qǐng)求越緊急，那么該請(qǐng)求的優(yōu)先級(jí)越高.此外，編程人員也可以根據(jù)自己的需求，將deadline和其他一些參數(shù)進(jìn)行綜合，再作為調(diào)度的優(yōu)先級(jí).

4.2.1 基于SSM的分布式實(shí)時(shí)約束感知調(diào)度算法

針對(duì)階段服務(wù)模型，在請(qǐng)求的每一個(gè)服務(wù)階段上，會(huì)根據(jù)實(shí)時(shí)約束信息實(shí)時(shí)調(diào)整下一個(gè)服務(wù)階段的請(qǐng)求優(yōu)先級(jí)，具體地，基于階段服務(wù)模型的分布式實(shí)時(shí)約束感知調(diào)度算法的工作流程如下:

步驟1. 請(qǐng)求在服務(wù)階段Si-1執(zhí)行完成后，實(shí)時(shí)約束傳播模塊會(huì)根據(jù)請(qǐng)求的elapsed_timeSi-1和expected_deadline計(jì)算出該請(qǐng)求在服務(wù)階段Si-1的deadlineSi-1的值，并將該deadlineSi-1附加到實(shí)時(shí)約束信息域(deadline,PU_flag)中，再由實(shí)時(shí)約束傳播模塊將deadlineSi-1值傳遞給服務(wù)階段Si上的請(qǐng)求加速模塊.

步驟2. 在服務(wù)階段Si上，請(qǐng)求加速模塊會(huì)根據(jù)當(dāng)前所有請(qǐng)求的deadlineSi-1判斷請(qǐng)求的優(yōu)先級(jí)：如果請(qǐng)求的deadlineSi-1的值越小，表明該請(qǐng)求的優(yōu)先級(jí)越高，該請(qǐng)求屬于緊急請(qǐng)求，需要在服務(wù)階段Si上優(yōu)先執(zhí)行.那么，請(qǐng)求加速模塊會(huì)優(yōu)先調(diào)度緊急請(qǐng)求.當(dāng)請(qǐng)求在服務(wù)階段Si執(zhí)行完畢，實(shí)時(shí)約束傳播模塊會(huì)再次根據(jù)elapsed_timeSi和expected_deadline更新deadlineSi，并且傳遞到下一個(gè)服務(wù)階段上的請(qǐng)求加速模塊.

該算法的算法描述如算法1所示.

算法1. 基于階段服務(wù)模型的分布式實(shí)時(shí)約束感知調(diào)度算法.

輸入:elapsed_timeSi,expected_deadline；

輸出:deadlineSi.

begin

初始化(deadlineS0,PU_flag)：

deadlineS0=0,PU_flag=0；

for (i=1;i

記錄請(qǐng)求處理時(shí)間elapsed_timeSi；

計(jì)算deadlineSi：

deadlineSi=expected_deadline-elapsed_timeSi；

發(fā)送deadlineSi到Si的請(qǐng)求加速模塊；

end for

end

4.2.2 基于PUM的分布式實(shí)時(shí)約束感知調(diào)度算法

針對(duì)并行單元模型，由于請(qǐng)求在并行單元上所花費(fèi)的時(shí)間主要在工作節(jié)點(diǎn)的計(jì)算階段，所以請(qǐng)求加速模塊主要對(duì)工作節(jié)點(diǎn)上的請(qǐng)求進(jìn)行加速處理.那么，基于并行單元模型的分布式實(shí)時(shí)約束感知調(diào)度算法的工作流程如下：

步驟1. 進(jìn)入并行單元的請(qǐng)求，當(dāng)經(jīng)過(guò)聚合節(jié)點(diǎn)劃分的各個(gè)子請(qǐng)求進(jìn)入到工作節(jié)點(diǎn)時(shí)，由實(shí)時(shí)約束傳播模塊計(jì)算各個(gè)請(qǐng)求剛到達(dá)工作節(jié)點(diǎn)的deadlineWj_CP_in.

步驟2. 實(shí)時(shí)約束傳播模塊將deadlineWj_CP_in值傳遞給該工作節(jié)點(diǎn)上的請(qǐng)求加速模塊，由請(qǐng)求加速模塊根據(jù)deadlineWj_CP_in決定請(qǐng)求的調(diào)度優(yōu)先級(jí)，然后根據(jù)優(yōu)先級(jí)進(jìn)行調(diào)度，優(yōu)先調(diào)度緊急請(qǐng)求.

該算法的算法描述如算法2所示.

算法2. 基于并行單元模型的分布式實(shí)時(shí)約束感知調(diào)度算法.

輸入:elapsed_timeWj_CP_in,expected_deadline；

輸出:deadlineWj_CP_in.

begin

設(shè)置PU_flag=1；

for (j=1;j

當(dāng)請(qǐng)求到達(dá)worker時(shí)由D2P模塊記錄elapsed_timeWj_CP_in

計(jì)算deadlineWj_CP_in：

deadlineWj_CP_in=expected_deadline-elapsed_timeWj_CP_in；

發(fā)送deadlineWj_CP_in到Wj的請(qǐng)求加速模塊；

end for

end

5 性能評(píng)估

5.1 實(shí)驗(yàn)設(shè)置

Fig. 6 The D2P-enabled framework based on SSM圖6 基于SSM的分布式實(shí)時(shí)約束傳播框架

在具體的部署方案中，我們總共部署了21臺(tái)虛擬機(jī)，其中，1臺(tái)虛擬機(jī)是數(shù)據(jù)源spout節(jié)點(diǎn)，用于發(fā)射查詢請(qǐng)求，請(qǐng)求生成速率為100請(qǐng)求數(shù)s；1臺(tái)虛擬機(jī)是寫數(shù)據(jù)庫(kù)Redis的節(jié)點(diǎn)；1臺(tái)虛擬機(jī)是合并計(jì)算結(jié)果的節(jié)點(diǎn)，即聚合節(jié)點(diǎn)；其他18臺(tái)虛擬機(jī)是中間計(jì)算的bolt節(jié)點(diǎn)，即工作節(jié)點(diǎn)，在每個(gè)工作節(jié)點(diǎn)上都有一個(gè)執(zhí)行索引查詢的任務(wù)，用于執(zhí)行索引查詢請(qǐng)求.我們?cè)贘Storm拓?fù)涞腷olt組件中，對(duì)查詢請(qǐng)求附加了實(shí)時(shí)約束信息域，并修改了執(zhí)行查詢?nèi)蝿?wù)的bolt組件，使其可以根據(jù)請(qǐng)求的實(shí)時(shí)約束信息對(duì)請(qǐng)求進(jìn)行調(diào)度.

5.2 實(shí)驗(yàn)結(jié)果

為了評(píng)估實(shí)驗(yàn)，我們采用的評(píng)價(jià)指標(biāo)有請(qǐng)求平均處理延遲(mean processing latency)和95%請(qǐng)求處理延遲(95th-percentile processing latency).一般來(lái)說(shuō)，可以使用95%請(qǐng)求處理延遲來(lái)表示請(qǐng)求的長(zhǎng)尾延遲現(xiàn)象.

Table 1 The Compare of FIFO and D2P -enabled Deadline - aware Scheduling in SSM表1 SSM中FIFO調(diào)度和實(shí)時(shí)約束感知調(diào)度算法的比較

圖7和圖8展示了分別使用先進(jìn)先出調(diào)度算法和分布式實(shí)時(shí)約束感知調(diào)度算法的請(qǐng)求處理延遲的概率密度函數(shù)(PDF).通過(guò)圖7和圖8的對(duì)比，我們可以看到圖8中的概率密度函數(shù)分布比圖7的概率密度函數(shù)分布更集中，分布式實(shí)時(shí)約束感知調(diào)度算法可以使請(qǐng)求處理延遲波動(dòng)降低約25%.

Fig. 7 The PDF of request processing latency when using FIFO scheduling algorithm圖7 請(qǐng)求處理延遲的概率密度分布(FIFO調(diào)度)

Fig. 8 The PDF of request processing latency when using D2P-enabled deadline-aware scheduling algorithm圖8 請(qǐng)求處理延遲的概率密度分布(實(shí)時(shí)約束感知調(diào)度)

圖9則展示了服務(wù)階段S1到S3上請(qǐng)求處理延遲的累積分布函數(shù)圖，從圖9中可以看出，分布式實(shí)時(shí)約束傳播框架是通過(guò)優(yōu)先調(diào)度落后請(qǐng)求和延遲調(diào)度非緊急請(qǐng)求來(lái)達(dá)到減少長(zhǎng)尾延遲的目的；但是，從服務(wù)階段S1到S3，隨著請(qǐng)求處理延遲越來(lái)越接近用戶期望的請(qǐng)求響應(yīng)時(shí)間，分布式實(shí)時(shí)約束感知調(diào)度算法的作用則會(huì)有所削弱.

Fig. 9 The CDF of request processing latency圖9 請(qǐng)求處理延遲的累積分布函數(shù)

針對(duì)實(shí)驗(yàn)搭建的索引查詢服務(wù)，我們也比較了使用先進(jìn)先出(FIFO)調(diào)度算法和分布式實(shí)時(shí)約束感知(D2P-enabled deadline-aware)調(diào)度算法的請(qǐng)求平均處理延遲和95%請(qǐng)求處理延遲.如表2所示，相對(duì)于先進(jìn)先出調(diào)度算法，分布式實(shí)時(shí)約束感知調(diào)度算法可以將工作節(jié)點(diǎn)上的95%請(qǐng)求處理延遲降低約10%.

我們以工作節(jié)點(diǎn)W1上的請(qǐng)求處理延遲情況為例，從圖10和圖11的請(qǐng)求處理延遲概率密度分布圖及累計(jì)分布函數(shù)圖可知，分布式實(shí)時(shí)約束感知調(diào)度算法相比先進(jìn)先出調(diào)度算法，能夠在一定程度上減少工作節(jié)點(diǎn)上的長(zhǎng)尾延遲.

此外，我們?cè)趯?shí)驗(yàn)中觀察到，針對(duì)同一個(gè)查詢?cè)~，在不同的工作節(jié)點(diǎn)上的查詢處理時(shí)間可能有較大差異.例如對(duì)同一個(gè)查詢?cè)~“國(guó)際廣播電臺(tái)”，在工作節(jié)點(diǎn)W1和W2上的查詢處理時(shí)間分別為5 457 ms和51 ms；而對(duì)查詢?cè)~“善哉”，在工作節(jié)點(diǎn)W6和W7上的查詢處理時(shí)間分別為107 ms和34 ms.雖然每一次查詢都會(huì)受到一些隨機(jī)因素的影響，但也可以看出索引數(shù)據(jù)的存儲(chǔ)位置對(duì)請(qǐng)求的查詢處理時(shí)間有較大的影響.而工作節(jié)點(diǎn)上的查詢處理結(jié)束后，又會(huì)

Table 2 The Compare of FIFO and D2P-enabled Deadline - aware Scheduling in PUM表2 PUM中FIFO調(diào)度算法和實(shí)時(shí)約束感知調(diào)度算法比較

Fig. 10 The PDF of request processing latency at W1圖10 在工作節(jié)點(diǎn)W1上請(qǐng)求處理延遲的概率密度分布

Fig. 11 The CDF of request processing latency at W1圖11 在工作節(jié)點(diǎn)W1上請(qǐng)求處理延遲的累積分布

將查詢結(jié)果返回給聚合節(jié)點(diǎn)進(jìn)行匯總，聚合節(jié)點(diǎn)的處理延遲則會(huì)受限于最慢的工作節(jié)點(diǎn)；若最慢工作節(jié)點(diǎn)上的請(qǐng)求處理延遲未得到較多改善，則對(duì)聚合節(jié)點(diǎn)的請(qǐng)求處理延遲影響不大.所以，針對(duì)并行單元的請(qǐng)求處理延遲優(yōu)化，還需要思考如何在工作節(jié)點(diǎn)上進(jìn)行數(shù)據(jù)的存儲(chǔ)優(yōu)化，以及對(duì)請(qǐng)求增加并行度，以此來(lái)減少并行單元的長(zhǎng)尾延遲.

6 結(jié)束語(yǔ)

本文提出了在數(shù)據(jù)中心的一種分布式實(shí)時(shí)約束傳播方法，根據(jù)期望響應(yīng)時(shí)間、請(qǐng)求執(zhí)行時(shí)間及網(wǎng)絡(luò)傳輸延遲來(lái)定義實(shí)時(shí)約束信息，并且能夠?qū)⒄?qǐng)求的全局實(shí)時(shí)約束信息傳播到整個(gè)處理路徑.此外，我們分別針對(duì)串行依賴模式和劃分聚合模式的數(shù)據(jù)中心應(yīng)用，提出了階段服務(wù)模型和并行單元模型，將分布式實(shí)時(shí)約束傳播方法應(yīng)用到這2種模型上，實(shí)現(xiàn)了一個(gè)分布式實(shí)時(shí)約束傳播框架.最后，在分布式實(shí)時(shí)約束傳播框架上，我們利用請(qǐng)求全生命周期過(guò)程中所傳播的實(shí)時(shí)約束信息來(lái)對(duì)請(qǐng)求進(jìn)行優(yōu)先級(jí)調(diào)度，用以減少長(zhǎng)尾延遲現(xiàn)象，并通過(guò)實(shí)行了驗(yàn)證.

由于在數(shù)據(jù)中心環(huán)境下，影響數(shù)據(jù)中心應(yīng)用服務(wù)質(zhì)量和響應(yīng)延遲的因素較多，如何保障請(qǐng)求全生命周期的服務(wù)質(zhì)量作為一個(gè)開放性問(wèn)題，也還需要進(jìn)行更深入的探討，我們也將在真實(shí)應(yīng)用中驗(yàn)證分布式實(shí)時(shí)約束傳播方法，并利用增加請(qǐng)求并行度的方法來(lái)減少長(zhǎng)尾延遲現(xiàn)象.

[1]Bao Yungang. The challenges and opportunities of guaranteeing quality of services in data center[J]. Journal of Integration Technology, 2013, 2(6): 71-81 (in Chinese)(包云崗. 數(shù)據(jù)中心保障應(yīng)用服務(wù)質(zhì)量面臨的挑戰(zhàn)與機(jī)遇[J]. 集成技術(shù), 2013, 2(6): 71-81)

[2]Krushevskaja D, Sandler M. Understanding latency variations of black box services[C]Proc of the 22nd Int Conf on World Wide Web. New York: ACM, 2013: 703-714

[3]Google. Google’s marissa mayer: Speed wins[EBOL]. (2006-11-09) [2013-04-21]. http:www.zdnet.comblogbtlgoogles-marissa-mayer-speed-wins3925

[4]Schurman E, Brutlag J. The user and business impact of server delays, additional bytes, and HTTP chunking in Web search[C]Proc of Velocity Web Performance and Operations Conf. San Jose, CA: O’Reilly, 2009

[5]Barroso L A, Clidaras J, Hoelzle U. The Datacenter as a Computer: An Introduction to the Design of Warehouse-scale Machines[M]. San Rafael, CA: Morgan & Claypool Publishers, 2009

[6]Dean J, Barroso L A. The tail at scale[J]. Communications of the ACM, 2013, 56(2): 74-80

[7]Dean J. Achieving rapid response times in large online services[C]Proc of Berkeley AMPLab Cloud Seminar. Berkeley: AMPLab, 2012

[8]Ren Rui, Ma Jiuyue, Sui Xiufeng, et al. D2P: A distributed deadline propagation approach to tolerate long-tail latency in datacenters[C]Proc of the 5th Asia-Pacific Workshop on Systems. New York: ACM, 2014: Article No.2

[9]Ousterhout K, Rasti R, Ratnasamy S, et al. Making sense of performance in data analytics frameworks[C]Proc of the 12th Symp on Networked Systems Design and Implementa-tion. Berkeley, CA: USENIX Association, 2015: 293-307

[10]Jeon M, He Y, Elnikety S, et al. Adaptive parallelism for Web search[C]Proc of the 8th ACM European Conf on Computer Systems. New York: ACM, 2013: 155-168

[11]Jeon M, Kim S, Hwang S W, et al. Predictive parallelization: Taming tail latencies in Web search[C]Proc of the 37th Int ACM SIGIR Conf on Research & Development in Information Retrieva. New York: ACM, 2014: 253-262

[12]Haque M E, Eom Y, He Y, et al. Few-to-Many: Incremental parallelism to reduce tail latency in interactive services[C]Proc of the 20th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2015: 161-175

[13]Kapoor R, Porter G, Tewari M, et al. Chronos: Predictable low latency for data center applications[C]Proc of the 3rd ACM Symp on Cloud Computing. New York: ACM, 2012: Article No.9

[14]Zats D, Das T, Mohan P, et al. DeTail: Reducing the flow completion time tail in datacenter network[J]. ACM SIGCOMM Computer Communication Review -Special October Issue SIGCOMM’12, 2012, 42(4): 139-150

[15]Alizadeh M, Greenberg A, Maltz D A, et al. Data center TCP (DCTCP)[C]Proc of ACM SIGCOMM 2010. New York: ACM, 2010: 63-74

[16]Vamanan B, Hasan J, Vijaykumar TN. Deadline-aware datacenter TCP (D2TCP)[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 115-126

[17]Canonical. Linux container[EBOL]. [2015-03-21]. https:linuxcontainers.org

[18]Barham P, Dragovic B, Fraser K. Xen and the art of virtualization[C]Proc of the 19th ACM Symp on Operating Systems Principles. New York: ACM, 2003: 164-177

[19]Liu Lei, Cui Zehan, Xing Mingjie, et al. A software memory partition approach for eliminating bank-level interference in multicore systems[C]Proc of the 21st Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2012: 367-376

[20]Cho S, Jin L. Managing distributed, shared L2 caches through OS-level page allocation[C]Proc of the 39th Annual IEEEACM Int Symp on Microarchitecture. Los Alamitos, CA: IEEE Computer Society, 2006: 455-468

[21]Jeong M K, Yoon D H, Sunwoo D. Balancing DRAM locality and parallelism in shared memory CMP systems[C]Proc of IEEE Int Symp on High-Performance Computer Architecture. Piscataway, NJ: IEEE, 2012: 1-12

[22]Mi Wei, Feng Xiaobing, Xue Jingling, et al. Software-hardware cooperative DRAM bank partitioning for chip multiprocessors[G]LNCS 6289: Proc of Network and Parallel Computing. Berlin: Springer, 2010: 329-343

[23]Tang Lingjan, Mars J, Wang Wei, et al. ReQoS: Reactive staticdynamic compilation for QoS in warehouse scale computers[C]Proc of the 18th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2013: 89-100

[24]Xu Yunjing, Musgrave Z, Noble B, et al. Bobtail: avoiding long tails in the cloud[C]Proc of the 10th Symp on Networked Systems Design and Implementation. New York: ACM, 2013: 329-341

[25]Cipar J, Ho Q, Kim J K, et al. Solving the straggler problem with bounded staleness[C]Proc of the 14th Workshop on Hot Topics in Operating Systems. Berkeley, CA: USENIX Association, 2013

[26]Ravindranath L, Padhye J, Agarwal S, et al. AppInsight: Mobile app performance monitoring in the wild[C]Proc of the 10th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 107-120

[27]Ravindranath L, Padhye J, Mahajan R, et al. Timecard: Controlling user-perceived delays in server-based mobile applications[C]Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 85-100

[28]Zhuravlev S, Blagodurov S, Fedorova A. Addressing shared resource contention in multicore processors via scheduling[C]Proc of the 15th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2010: 129-142

[29]Chen T S, Guo Q, Temam O, et al. Statistical performance comparisons of computers[J]. IEEE Trans on Computers, 2015, 64(5): 1442-1455

[30]Delimitrou C, Kozyrakis C. Paragon: QoS-aware scheduling for heterogeneous datacenters[C]Proc of the 18th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2013: 77-88

[31]Wikipedia. Least laxity first[EBOL]. [2013-07-18]. http:en.wikipedia.orgwikiLeast_slack_time_scheduling

[32]Lin Jiang, Lu Qingda, Ding Xiaoning, et al. Gaining insights into multicore cache partitioning: Bridging the gap between simulation and real systems[C]Proc of the 14th Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2008: 367-378

[33]Alibaba. Dubbo: Distributed service framework[EBOL]. [2013-07-09]. http:dubbo.io

[34]Chinese Academy of Sciences, Institute of Computing Technology. BigdataBench-Jstorm[EBOL]. [2016-04-02]. http:prof.ict.ac.cnbdb_uploadsbdb_streamingSearch-Engine-JStorm.tar.gz

Ren Rui, born in 1987. PhD candidate in the Institute of Computing Technology, Chinese Academy of Sciences. Her main research interests include big data system and performance analysis.

Ma Jiuyue, born in 1988. PhD. His main research interests include computer archi-tecture and operating system (majiuyue@ncic.ac.cn).

Sui Xiufeng, born in 1982. Associate professor. His main research interests include high performance computer architecture, system performance modeling and evaluation, and cloud computing (suixiufeng@ict.ac.cn).

Bao Yungang, born in 1980. Professor and PhD supervisor. Member of CCF. His main research interests include computer architecture, operating system and system performance modeling and evaluation (baoyg@ict.ac.cn).

A Distributed Deadline Propagation Approach to Reduce Long-Tail in Datacenters

Ren Rui1,2, Ma Jiuyue1,2, Sui Xiufeng1, and Bao Yungang1

1(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

Long-tail latency is inevitable and may be amplified for highly modular datacenter applications such as Bing, Facebook, and Amazon’s retail platform, due to resource sharing, queuing, background maintenance activities, etc. Thus how to tolerate the latency variability in shared environments is crucial in datacenters. This paper proposes a distributed deadline propagation (D2P) approach for datacenter applications to reduce long-tail latency. The key idea of D2P is inspired by the traffic light system in Manhattan, New York City, where one can enjoy a chain of green lights after one stop at a red light, and it allows local nodes to perceive global deadline information and to propagate the information among distributed nodes. Local nodes can leverage the information to do scheduling and adjust processing speed to reduce long-tail latency. Then, we propose stage-service model and parallel-unit model to describe sequentialdependent pattern and partitionaggregate pattern, and implement a distributed deadline propagation framework. At last, based on distributed deadline propagation framework, we use D2P-enabled deadline-aware scheduling algorithm to reduce long-tail latency in our experiments, and the preliminary experimental results show that D2P has the potential of reducing the long-tail latency in datacenters by local nodes leveraging the propagated deadline information.

deadline propagation; long-tail latency; datacenter; partitionaggregates pattern; sequentialdependent pattern

2016-03-31；

2016-08-08

國(guó)家自然科學(xué)基金國(guó)際合作項(xiàng)目(61420106013)；國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1000201) This work was supported by the International Cooperation Project of National Natural Science Foundation of China (61420106013) and the National Key Research and Development Program of China (2016YFB1000201).

包云崗(baoyg@ict.ac.cn)

TP302