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

任 睿 馬久躍 隋秀峰 包云崗

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

?

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

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

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

(renrui@ict.ac.cn)

提出了一種在數據中心環境下用于減少長尾延遲的分布式實時約束傳播方法，該方法能夠使當前節點感知請求的全局響應時間約束信息，并能夠將請求的實時約束信息傳播到整個處理路徑；節點可以利用請求的實時約束信息進行請求調度或加速請求執行時間，以此來減少長尾延遲現象.同時，針對劃分聚合模式和串行依賴模式2種數據中心應用，提出了階段服務模型和并行單元模型，并基于這2種模型實現了分布式實時約束傳播框架.最后，在分布式實時約束傳播框架上實現了實時約束感知調度算法，通過實驗進行了簡單的驗證，初步的實驗結果顯示了分布式實時約束傳播方法能夠在一定程度上減少長尾延遲.

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

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

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

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

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

1 國內外相關工作

近年來，為了保障數據中心應用的服務質量，學術界、工業界在各個層次上進行了探索.

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

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

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

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

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

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

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

2 數據中心應用和長尾延遲

2.1 數據中心應用

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

2.2 長尾延遲現象

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

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

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

(1)

基于圖1中的數據，并根據上述定義分別計算單臺機器上Equake程序和數據中心某后端服務的響應時間波動范圍，發現單臺機器上Equake程序的響應延遲波動為5.42%，但是數據中心環境下后端服務的響應延遲波動為5980%，顯而易見，數據中心環境下的響應延遲波動遠遠大于單臺機器上的響應延遲波動.

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

Fig. 2 Latency variability is amplified when service stage increases圖2 響應時間延遲波動隨服務階段的增加而放大

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

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

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

3.1.1 階段服務模型

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

階段服務模型如圖3所示，其中，階段服務模型中的相關參數為

N: 應用所包含的服務階段的個數；

Si: 應用的第i個服務階段,1≤i≤N；

LSi: 應用請求在第i個服務階段的執行時間；

CSi: 應用請求在第i個服務階段處理完畢后，將請求發送到下一個服務階段所花費的網絡延遲；

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

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

(2)

Fig. 3 Stage-service model圖3 階段服務模型

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

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

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

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

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

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

deadlineSi=expected_deadline-elapsed_timeSi.

(3)

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

當請求在不同的服務階段進行傳遞時，可以將請求的實時約束信息同時進行傳播，那么，對每一個服務階段而言，系統可以利用實時約束信息進行優先級調度、資源分配或增加并行度，以此來加速緊急請求的處理速度.

3.2.1 并行單元模型

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

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

并行單元模型如圖4所示，并行單元模型中的相關參數為

m: 并行單元中的工作節點個數；

Ai: 第i個聚合節點；

Wj: 第j個工作節點,1≤j≤m；

PP: 聚合節點上的劃分階段；

AP: 聚合節點上的聚合階段；

CP: 工作節點上的計算階段；

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

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

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

elapsed_timel_p: 請求經過節點l、階段p后所花費的總處理時間；

CWj: 請求從工作節點Wj返回結果到聚合節點時所花費的網絡延遲.

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

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

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

elapsed_timeAi_AP=

max(elapsed_timeWj_CP+CWj+LAi_AP).

(4)

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

deadlinel_p=expected_deadline-elapsed_timel_p,

l_p∈(Ai_PP,Wj_CP,Ai_AP).

(5)

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

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

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

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

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

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

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

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

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

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

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

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

4) 調整精度[27].對一些互聯網在線應用來說，適當地降低精度對用戶的體驗影響不大，那么就可以通過適當地降低精度來降低請求的響應時間，以此減少長尾延遲.

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

4.2.1 基于SSM的分布式實時約束感知調度算法

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

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

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

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

算法1. 基于階段服務模型的分布式實時約束感知調度算法.

輸入: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；

發送deadlineSi到Si的請求加速模塊；

end for

end

4.2.2 基于PUM的分布式實時約束感知調度算法

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

步驟1. 進入并行單元的請求，當經過聚合節點劃分的各個子請求進入到工作節點時，由實時約束傳播模塊計算各個請求剛到達工作節點的deadlineWj_CP_in.

步驟2. 實時約束傳播模塊將deadlineWj_CP_in值傳遞給該工作節點上的請求加速模塊，由請求加速模塊根據deadlineWj_CP_in決定請求的調度優先級，然后根據優先級進行調度，優先調度緊急請求.

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

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

輸入:elapsed_timeWj_CP_in,expected_deadline；

輸出:deadlineWj_CP_in.

begin

設置PU_flag=1；

for (j=1;j

當請求到達worker時由D2P模塊記錄elapsed_timeWj_CP_in

計算deadlineWj_CP_in：

deadlineWj_CP_in=expected_deadline-elapsed_timeWj_CP_in；

發送deadlineWj_CP_in到Wj的請求加速模塊；

end for

end

5 性能評估

5.1 實驗設置

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

在具體的部署方案中，我們總共部署了21臺虛擬機，其中，1臺虛擬機是數據源spout節點，用于發射查詢請求，請求生成速率為100請求數s；1臺虛擬機是寫數據庫Redis的節點；1臺虛擬機是合并計算結果的節點，即聚合節點；其他18臺虛擬機是中間計算的bolt節點，即工作節點，在每個工作節點上都有一個執行索引查詢的任務，用于執行索引查詢請求.我們在JStorm拓撲的bolt組件中，對查詢請求附加了實時約束信息域，并修改了執行查詢任務的bolt組件，使其可以根據請求的實時約束信息對請求進行調度.

5.2 實驗結果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結束語

本文提出了在數據中心的一種分布式實時約束傳播方法，根據期望響應時間、請求執行時間及網絡傳輸延遲來定義實時約束信息，并且能夠將請求的全局實時約束信息傳播到整個處理路徑.此外，我們分別針對串行依賴模式和劃分聚合模式的數據中心應用，提出了階段服務模型和并行單元模型，將分布式實時約束傳播方法應用到這2種模型上，實現了一個分布式實時約束傳播框架.最后，在分布式實時約束傳播框架上，我們利用請求全生命周期過程中所傳播的實時約束信息來對請求進行優先級調度，用以減少長尾延遲現象，并通過實行了驗證.

由于在數據中心環境下，影響數據中心應用服務質量和響應延遲的因素較多，如何保障請求全生命周期的服務質量作為一個開放性問題，也還需要進行更深入的探討，我們也將在真實應用中驗證分布式實時約束傳播方法，并利用增加請求并行度的方法來減少長尾延遲現象.

[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)(包云崗. 數據中心保障應用服務質量面臨的挑戰與機遇[J]. 集成技術, 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

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