一種減少長尾延遲的分布式實時約束傳播方法

任 睿 馬久躍 隋秀峰 包云崗

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

?

一種減少長尾延遲的分布式實時約束傳播方法

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

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

(renrui@ict.ac.cn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

3 分布式實時約束傳播方法

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

3.1.1 階段服務(wù)模型

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

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

deadlineSi=expected_deadline-elapsed_timeSi.

(3)

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

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

3.2.1 并行單元模型

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

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

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

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

Ai: 第i個聚合節(jié)點；

Wj: 第j個工作節(jié)點,1≤j≤m；

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

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

CP: 工作節(jié)點上的計算階段；

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

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

Ll_p：請求在節(jié)點l、階段p時的處理時間；

elapsed_timel_p: 請求經(jīng)過節(jié)點l、階段p后所花費的總處理時間；

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

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

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

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

elapsed_timeAi_AP=

max(elapsed_timeWj_CP+CWj+LAi_AP).

(4)

那么，在并行單元的每一個階段上，實時約束信息計算并動態(tài)更新為

deadlinel_p=expected_deadline-elapsed_timel_p,

l_p∈(Ai_PP,Wj_CP,Ai_AP).

(5)

4 分布式實時約束傳播框架

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

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

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

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

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

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

4.2 利用分布式實時約束傳播框架減少長尾延遲

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

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

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

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

4) 調(diào)整精度[27].對一些互聯(lián)網(wǎng)在線應(yīng)用來說，適當(dāng)?shù)亟档途葘τ脩舻捏w驗影響不大，那么就可以通過適當(dāng)?shù)亟档途葋斫档驼埱蟮捻憫?yīng)時間，以此減少長尾延遲.

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

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

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

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

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

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

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

輸入:elapsed_timeSi,expected_deadline；

輸出:deadlineSi.

begin

初始化(deadlineS0,PU_flag)：

deadlineS0=0,PU_flag=0；

for (i=1;i

記錄請求處理時間elapsed_timeSi；

計算deadlineSi：

deadlineSi=expected_deadline-elapsed_timeSi；

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

end for

end

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

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

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

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

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

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

輸入:elapsed_timeWj_CP_in,expected_deadline；

輸出:deadlineWj_CP_in.

begin

設(shè)置PU_flag=1；

for (j=1;j

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

計算deadlineWj_CP_in：

deadlineWj_CP_in=expected_deadline-elapsed_timeWj_CP_in；

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

end for

end

5 性能評估

5.1 實驗設(shè)置

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

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

5.2 實驗結(jié)果

為了評估實驗，我們采用的評價指標(biāo)有請求平均處理延遲(mean processing latency)和95%請求處理延遲(95th-percentile processing latency).一般來說，可以使用95%請求處理延遲來表示請求的長尾延遲現(xiàn)象.

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

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

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

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

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

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

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

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

此外，我們在實驗中觀察到，針對同一個查詢詞，在不同的工作節(jié)點上的查詢處理時間可能有較大差異.例如對同一個查詢詞“國際廣播電臺”，在工作節(jié)點W1和W2上的查詢處理時間分別為5 457 ms和51 ms；而對查詢詞“善哉”，在工作節(jié)點W6和W7上的查詢處理時間分別為107 ms和34 ms.雖然每一次查詢都會受到一些隨機(jī)因素的影響，但也可以看出索引數(shù)據(jù)的存儲位置對請求的查詢處理時間有較大的影響.而工作節(jié)點上的查詢處理結(jié)束后，又會

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

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

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

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

6 結(jié)束語

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

由于在數(shù)據(jù)中心環(huán)境下，影響數(shù)據(jù)中心應(yīng)用服務(wù)質(zhì)量和響應(yīng)延遲的因素較多，如何保障請求全生命周期的服務(wù)質(zhì)量作為一個開放性問題，也還需要進(jìn)行更深入的探討，我們也將在真實應(yī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

國家自然科學(xué)基金國際合作項目(61420106013)；國家重點研發(fā)計劃項目(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