冷鎮(zhèn)宇 蔣德鈞 熊勁

（中國科學院計算技術研究所先進計算機系統(tǒng)研究中心 北京100190）

（中國科學院大學 北京100049）

0 引言

近幾年,分布式存儲系統(tǒng)被廣泛應用于公有云場景[1-5],并以其優(yōu)越的擴展性支持成千上萬個租戶的存儲服務。保證租戶的尾延遲服務質量目標（service level objective,SLO）非常重要,否則,長尾延遲將影響用戶的體驗,減少云供應商的收益。因此,尾延遲SLO 如99 或99.9 百分位延遲得到了工業(yè)界和學術界的共同關注[6-14]。

通常情況下,租戶的請求從客戶端出發(fā),通過網(wǎng)絡發(fā)送至服務端,并由服務端向存儲設備發(fā)出IO 請求,最終將應答發(fā)送回客戶端。本文關注的是服務端的延遲SLO,IO 隊列上的排隊尾延遲在服務端尾延遲中占據(jù)了主導地位[7-9]。排隊尾延遲主要是由租戶負載的突發(fā)流量產(chǎn)生[6-9],當IO 隊列的請求服務速率低于請求抵達速率時,請求在IO 隊列上堆積。

已有工作結合了兩套機制[9-12]以保證服務端尾延遲SLO。一套為資源分配方法,其作用于存儲節(jié)點,為租戶分配足以保證服務端尾延遲SLO 的I/O資源。另一套為租戶準入控制機制,其作用于客戶端,預測租戶的服務端尾延遲,并允許延遲SLO 得到滿足的租戶接入存儲系統(tǒng)。服務端的資源分配與客戶端的準入控制相互協(xié)作,以保證每個租戶的尾延遲SLO。

將多個延遲敏感型租戶混合部署可以提高存儲系統(tǒng)資源利用率,但同時也會加劇租戶間對資源的競爭。因此保證多租戶服務端尾延遲SLO 的同時最大化系統(tǒng)的資源利用率面臨兩方面的挑戰(zhàn)。

一方面,租戶負載突發(fā)流量的強度和持續(xù)時間變化范圍很廣。通常情況下,突發(fā)流量期間的請求發(fā)送速率可達租戶負載平均發(fā)送速率的2～6 倍,且突發(fā)流量的持續(xù)時間從幾微秒到幾十毫秒不等[11]。如何對復雜的租戶負載突發(fā)流量進行建模是第1 個挑戰(zhàn)。本文發(fā)現(xiàn)租戶負載突發(fā)流量的產(chǎn)生強度、概率和密集程度3 個維度均會對服務端尾延遲產(chǎn)生影響。傳統(tǒng)的馬爾科夫調制泊松過程（Markov modulated Poisson process,MMPP）建模方法[15]僅從租戶負載突發(fā)流量的產(chǎn)生強度和概率2 個維度進行建模,并限定了突發(fā)流量產(chǎn)生的概率,因此損失了部分精度。本文基于密度聚類算法,從3 個維度對負載突發(fā)流量進行建模,更精準地刻畫了租戶負載突發(fā)流量。

另一方面,保證租戶的尾延遲SLO 要求租戶的99 百分位延遲甚至99.9 百分位延遲不超過限值,如何對小概率事件產(chǎn)生的概率進行預測是第2 個挑戰(zhàn)?，F(xiàn)有方法要么只預測了服務端延遲的最大值[9-11],要么采用隨機網(wǎng)絡演算（stochastic network calculus,SNC）方法[16]預測尾延遲[11],這些方法基于馬爾科夫不等式,通過平均延遲預測尾延遲的上界,但實際的尾延遲可能遠小于上界。本文基于租戶負載突發(fā)流量建模方法,直接預測服務端尾延遲超出SLO 的概率。

基于上述租戶負載建模方法和尾延遲預測方法,結合固定速率資源分配方法,本文提出了AccGecko,一種面向分布式存儲系統(tǒng)的先驗式多租戶服務端尾延遲SLO 保證框架。基于微軟提供的生產(chǎn)環(huán)境trace[17-18],本文將AccGecko 與當前最新的尾延遲SLO 保證框架進了對比。結果顯示,針對99和99.9 百分位尾延遲SLO,AccGecko 使存儲系統(tǒng)承載的租戶數(shù)量平均提升了約112%和19%。

1 相關工作

1.1 尾延遲預測方法與租戶負載建模

PriorityMeister[9]、QJump[10]和Silo[12]采用rb對負載進行建模。對于租戶負載,當服務速率為r時,b為排隊請求數(shù)量的最大值,rb對只對租戶負載的最大突發(fā)流量進行了建模。在rb對的基礎上,這些工作采用network calculus[19]延遲預測方法,只能預測租戶請求的最大延遲。

SNC-Meister（SNCM）采用SNC[16]預測租戶請求的百分位延遲,提升了尾延遲預測的準確程度。SNC 尾延遲預測方法基于馬爾科夫不等式對尾延遲的上限進行預測,把概率關聯(lián)到數(shù)學期望。對于隨機變量X,期望為EX,則X的值超出a倍EX的概率為,即租戶請求的百分位延遲的上限為a倍的平均延遲。為了獲得租戶請求的平均延遲,SNC-Meister 采用MMPP[15]對負載進行建模。MMPP 按照固定周期（如1 ms）對租戶負載進行切分,統(tǒng)計每個周期的請求發(fā)送數(shù)量,并基于泊松分布,將租戶負載劃分為若干個請求發(fā)送速率多寡的狀態(tài)。再基于馬爾科夫鏈,給出不同狀態(tài)之間的轉移概率。最后基于譜半徑,計算租戶負載請求的平均延遲。

1.2 資源分配方法

資源分配方法為租戶分配足以保證尾延遲SLO的資源,包括了反饋式和先驗式兩種。

反饋式方法周期性地監(jiān)測租戶請求的延遲,如果延遲的某些指標超過了警戒線,則在下一周期通過限制請求的發(fā)送速率的方式保證延遲SLO,其代表性工作有PSLO[20]和Cake[21]。由于反饋法無法預見到租戶突發(fā)流量的產(chǎn)生,可能導致反饋周期結束前延遲已經(jīng)違反SLO 的情況產(chǎn)生,因此一般用于延遲SLO 較低（如95 百分位）的場景。

先驗式方法基于租戶負載的trace 和存儲設備的服務能力來預測請求的最大延遲或百分位延遲,在此基礎上分配I/O 資源。其代表性工作包括PriorityMeister[9]、QJUMP[10]、SNC-Meister[11]和Silo[12]。這些工作采用優(yōu)先級調度或固定速率分配的方法,靜態(tài)地分配租戶的資源。

2 研究動機

2.1 租戶負載突發(fā)流量的三維特性

通常情況下,突發(fā)流量的產(chǎn)生在整個負載中為小概率事件,并且持續(xù)時間僅為毫秒甚至微秒級,不會對負載的平均發(fā)送速率產(chǎn)生較大的影響,因此租戶請求的服務端平均延遲受負載突發(fā)流量的影響較低。對于目前存儲服務商同樣關注的服務端尾延遲來說,99/99.9 百分位服務端延遲不能忽視小概率事件的影響。因此,為了保證租戶的延遲SLO,理解負載突發(fā)流量對服務端尾延遲的影響程度十分重要。

不同租戶負載突發(fā)流量的特性不同,一些負載可以有較強但產(chǎn)生概率較低并且稀疏的突發(fā)流量,而另一些負載擁有較小但更頻繁、更密集的突發(fā)流量。以微軟提供的真實負載trace 為例,定性地分析負載突發(fā)流量對服務端尾延遲的影響。將負載trace 以1 ms 的粒度進行切分,統(tǒng)計每毫秒內請求的發(fā)送數(shù)量,得到請求發(fā)送速率的變化曲線,如圖1所示。租戶負載突發(fā)流量的特性包含3 個維度。

圖1 租戶負載示意圖

（1） 強度。租戶負載的突發(fā)流量期間,租戶發(fā)送請求的速率高于整個負載平均發(fā)送速率。將突發(fā)流量強度定義為該突發(fā)流量期間請求發(fā)送速率是整個負載平均發(fā)送速率的倍數(shù)。通常情況下,租戶負載的強度為2～10。突發(fā)流量強度影響了服務端尾延遲的大小和百分比。在服務端的IO 隊列上,若請求的發(fā)送速率高于請求的服務速率,則請求將阻塞于IO 隊列中。突發(fā)流量的強度越高,則突發(fā)流量期間IO 隊列中阻塞的請求數(shù)量越多,導致更多的請求的延遲為尾延遲,服務端尾延遲的百分比增大。與此同時,阻塞的請求數(shù)量越多,則需要更多的時間來服務請求,服務端尾延遲增大。

（2） 概率。將突發(fā)流量的概率定義為單位時間內突發(fā)流量的產(chǎn)生總時長。突發(fā)流量的概率依賴于如何定義突發(fā)流量。突發(fā)流量的強度下限越低,則突發(fā)流量產(chǎn)生的概率越高。突發(fā)流量概率主要影響了服務端尾延遲的百分比。突發(fā)流量的概率越高,則將有更多的請求延遲為尾延遲。但突發(fā)流量概率并不會影響服務端尾延遲大小的上限。假設突發(fā)流量在租戶負載中是均勻分布的,則每段突發(fā)流量對服務端延遲的影響均為獨立的,因此每段突發(fā)流量所產(chǎn)生的排隊延遲并不會疊加。

（3） 密集程度。通常情況下,租戶負載中的突發(fā)流量并非均勻分布。不同的時間段內,突發(fā)流量的密集程度不相同。在一定的服務速率下,如果前一段突發(fā)流量所產(chǎn)生的請求排隊并未完全消除,而后一段突發(fā)流量已經(jīng)抵達IO 隊列,則兩段突發(fā)流量將產(chǎn)生更高的服務端延遲。這種延遲疊加效應對服務端尾延遲的大小和百分比均造成了影響。延遲疊加效應持續(xù)的時間越長,則疊加的延遲越大,且受影響的請求數(shù)量越多。因此將突發(fā)流量的密集程度定義為延遲疊加的持續(xù)時間,也稱為突發(fā)流量持續(xù)時間。突發(fā)流量密集程度受請求服務速率的影響,請求服務速率越高,則突發(fā)流量疊加延遲的概率越低。為了簡單起見,將請求服務速率設定為租戶負載的請求平均發(fā)送速率,在此基礎上統(tǒng)計突發(fā)流量的持續(xù)時間。

接下來定量地分析租戶負載突發(fā)流量的3 個維度對服務端延遲的影響。實驗采用了微軟提供的真實負載trace[17-18],這些trace 采集了來自于Livemap、MSN、TPCC 和TPCE 等負載在塊層的IO 信息。為了不失一般性,成比例調整每個trace 負載的請求發(fā)送時間間隔,使所有負載的平均發(fā)送速率相同（2000 IOPS）。在此基礎上,各截取了trace 的一部分,使每段trace 的總發(fā)送時長相同（5 min）。為了消除請求服務延遲的變化對服務端延遲的干擾,通過控制IO 線程從IO 隊列中取請求的速率,為所有trace 設定了一個固定的服務速率,為請求平均發(fā)送的1.5 倍（3000 IOPS）,并固定相鄰請求的服務間隔（333 μs）。在上述實驗環(huán)境下,運行每段trace,統(tǒng)計95、99、99.9 和99.99 百分位服務端延遲。將租戶負載突發(fā)流量的基準線設定為租戶負載請求平均發(fā)送速率的2 倍,分析租戶負載突發(fā)流量的強度、概率和密集程度對服務端延遲的影響。

針對租戶負載突發(fā)流量的3 個維度,用所有突發(fā)流量期間的平均發(fā)送速率表征租戶負載突發(fā)流量的強度;用突發(fā)流量產(chǎn)生總時長表征租戶負載突發(fā)流量的概率;用所有連續(xù)突發(fā)流量平均時長和連續(xù)突發(fā)流量最大時長表征租戶負載突發(fā)流量的密集程度。圖2 直觀地展示了99.9 百分位服務端延遲與租戶負載突發(fā)流量產(chǎn)生概率之間的關系。圖中橫軸為租戶負載突發(fā)流量的總時長,縱軸為99.9 百分位服務端延遲,每個點對應一段trace。隨著租戶負載突發(fā)流量總時長的增加,所產(chǎn)生的99.9 百分位服務端延遲的最大值總體上不斷增加。但也存在很多的trace,其突發(fā)流量的總時長較高,而99.9 百分位服務端延遲較低。這主要由于突發(fā)流量的強度較低或者密集程度較低造成的。

圖2 99.9 百分位服務端尾延遲與租戶負載突發(fā)流量概率之間的關系

采用斯皮爾曼相關性系數(shù)進一步分析租戶負載突發(fā)流量的強度、概率和密集程度對服務端百分位延遲的影響。斯皮爾曼相關性系數(shù)被用來度量兩個變量之間變化趨勢的方向以及程度,取值范圍為[-1,1]。斯皮爾曼相關性系數(shù)的絕對值越高,則兩個變量之間的相關性越強,正值表示正相關,負值代表負相關。一般認為斯皮爾曼相關性系數(shù)的絕對值為[0.8,1]表明變量之間的相關性極強,[0.6,0.8]表明變量之間的相關性較強,[0.4,0.6]表明變量之間的相關性中等,[0.2,0.4]表明變量之間的相關性較弱,[0,0.2]表明變量之間的相關性極弱或無相關。

圖3 展示了租戶負載突發(fā)流量的強度、概率和密集程度與服務端百分位延遲之間的斯皮爾曼相關系數(shù)。圖中橫軸為服務端百分位延遲,縱軸為斯皮爾曼相關性系數(shù)。從圖中可以發(fā)現(xiàn),租戶負載突發(fā)流量3 個維度的特性與尾延遲均沒有極強的相關性。對于高百分位尾延遲來說（99 百分位、99.9 百分位和99.99 百分位）,租戶負載突發(fā)流量的平均強度和總的產(chǎn)生概率并不是最主要的因素,而密集程度對服務端尾延遲的影響最強。隨著服務端延遲百分位的增加,租戶負載突發(fā)流量的平均強度、總的產(chǎn)生概率以及平均密集程度與服務端延遲的斯皮爾曼相關性系數(shù)不斷遞減。這是由于對上述3 個維度特性的統(tǒng)計主要體現(xiàn)了租戶負載突發(fā)流量的整體情況,而服務端高百分位延遲與某些特定的突發(fā)流量相關。因此對于服務端99.9 和99.99 百分位延遲來說,起到?jīng)Q定作用的是連續(xù)突發(fā)流量持續(xù)時間的最大值。

圖3 租戶負載突發(fā)流量的強度、概率和密集程度與服務端百分位延遲之間的斯皮爾曼相關性系數(shù)

綜上所述,本節(jié)定義了租戶負載突發(fā)流量3 個維度的特性:強度、概率和密集程度,定性且定量地分析了租戶負載突發(fā)流量的強度、概率和密集程度與服務端尾延遲的關系,3 個維度的特性對服務端尾延遲均產(chǎn)生了影響。要精確地預測尾延遲需要考慮突發(fā)流量的強度、概率和密集程度3 個因素。

2.2 現(xiàn)有租戶負載建模與尾延遲預測方法的不足

采用了SNC 的尾延遲預測方法與MMPP 負載建模方法,對租戶負載的尾延遲預測誤差依然較大,主要原因包括以下3 點。

其一,SNC 尾延遲預測方法對尾延遲的預測過于保守。SNC 尾延遲預測方法基于馬爾可夫不等式,給出了隨機變量的累積分布函數(shù)一個非常寬泛的上界。以99 百分位延遲與99.9 百分位延遲為例,99 百分位延遲的上界為平均延遲的100 倍,而99.9 百分位的上界為平均延遲的1000 倍。

其二,MMPP 負載建模方法比較粗糙。在2.1 節(jié)中分析了負載突發(fā)流量的密集程度對服務端高百分位延遲的影響。如果負載突發(fā)流量的密集程度較低,則服務端高百分位延遲同樣較低。然而MMPP負載建模方法只考慮到了負載突發(fā)流量的強度和產(chǎn)生概率,并不能識別出負載突發(fā)流量的密集程度。這是因為MMPP 通過馬爾科夫鏈獲得相鄰狀態(tài)的轉移概率,如果狀態(tài)之間并不相鄰,馬爾科夫鏈并不能準確地給出相近狀態(tài)間的轉移概率。因此MMPP認為負載突發(fā)流量這樣的小概率事件均勻地分布在整個負載上,并不能識別出負載突發(fā)流量相近的情況,也就無從獲知租戶負載的密集程度。當多個租戶的負載突發(fā)流量強度和產(chǎn)生概率相近時,基于MMPP 的SNC 百分位延遲預測方法預測的延遲也相近,但租戶負載突發(fā)流量對高百分位延遲的影響較大。

從微軟提供的生產(chǎn)環(huán)境trace 中選取3 個負載突發(fā)流量平均強度與產(chǎn)生概率相近但密集程度不同的trace（T1～T3）,3 個trace 的三維特性如表1 所示。三者的突發(fā)流量總時間最大差異僅為7%,突發(fā)流量平均強度最大差異僅為8%,但最大突發(fā)流量持續(xù)時間為11～27 ms,相差達1.45 倍。

表1 突發(fā)流量平均強度與產(chǎn)生概率相近的負載

在服務速率固定的情況下,租戶實際的百分位延遲分布與使用MMPP 和SNC 方法預測的百分位延遲分布如圖4 所示。該圖給出了請求服務速率固定的情況下租戶實際的百分位延遲分布（Practical）與使用MMPP 和SNC 方法預測的百分位延遲分布。

圖4 MMPP+SNC 對尾延遲預測的誤差

圖4 展示了租戶請求的互補累積分布函數(shù)用來定義延遲超過某一限值的概率,圖上的點（x,y） 表示占比為x的請求時延至少為y秒。圖中的x軸的數(shù)值為指數(shù)分布,這種方式有助于尾延遲的可視化,x軸的主標簽分別對應于第90、99、99.9和99.99 百分位延遲。圖中圓點為預測值,叉點為實際值。基于MMPP 和SNC 預測的服務端延遲分布相近,以高百分位延遲中的99.9 百分位為例,對3 個trace 預測的延遲相差僅為7%。然而由于負載突發(fā)流量的密集程度不同,實際的99.9 百分位服務端延遲相差達到了2.93 倍。這既表明了租戶負載突發(fā)流量密集程度對服務端高百分位延遲的影響程度,又說明MMPP 負載建模方法對租戶負載突發(fā)流量的不敏感。

其三,MMPP 負載建模方法比較粗糙還體現(xiàn)在MMPP 對租戶負載的階段分布進行了簡化,對低百分位延遲的預測產(chǎn)生了較大的誤差,可能將產(chǎn)生概率較高的事件看作為產(chǎn)生概率較低事件。SNC 尾延遲預測方法基于MMPP,需要獲知狀態(tài)間轉移概率矩陣以及每個狀態(tài)的矩量母函數(shù)?；谖④浱峁┑恼鎸峵race,以1 ms 的粒度對trace 進行了切分,統(tǒng)計每個時間段內的請求發(fā)送數(shù)量,將請求發(fā)送數(shù)量相同的時間段看作同一事件。由于突發(fā)流量期間的請求發(fā)送數(shù)量最大可達負載均值的10 倍,因此從請求發(fā)送速率為0 到請求發(fā)送速率為負載的最大值之間存在10 種以上的事件。鑒于狀態(tài)間轉移概率矩陣的計算量較大,為了簡化計算,MMPP 基于泊松分布,將狀態(tài)的數(shù)量降低了一個數(shù)量級。造成租戶的請求發(fā)送速率的多樣性被消除,許多發(fā)送請求數(shù)量較低的事件與發(fā)送請求數(shù)量中等的事件被劃分為同一狀態(tài)。MMPP 基于泊松分布,限定了狀態(tài)內不同請求發(fā)送速率事件產(chǎn)生的概率。每個狀態(tài)內,MMPP 認為請求發(fā)送速率居中的事件發(fā)生概率最高,而請求發(fā)送速率越低或越高的事件的發(fā)生概率越低,這往往與實際情況不符。

從微軟的真實場景trace 中隨機選擇一個trace進行說明。以1 ms 為切分粒度統(tǒng)計請求發(fā)送的數(shù)量以及在整個trace 中產(chǎn)生的概率進行統(tǒng)計,并采用MMPP 對請求發(fā)送數(shù)量相同事件的產(chǎn)生概率進行建模,結果如圖5 所示。圖中橫軸為請求發(fā)送數(shù)量,最小為1,最大為14,縱軸為每個請求發(fā)送相同事件的產(chǎn)生概率,以百分比表示。MMPP 以請求最大發(fā)送數(shù)量14 為基準值,將階段的請求發(fā)送速率中位數(shù)設定為8.25,因此請求發(fā)送速率以3～14 為一個狀態(tài),以1～2 為另一個狀態(tài),基于泊松分布限定了每個請求發(fā)送速率相同事件的概率。與實際請求發(fā)送數(shù)量相比,平均預測誤差為11 倍,最大達到了1279 倍。

圖5 MMPP 對請求發(fā)送速率相同事件概率的建模

綜上所述,SNC 的保守與MMPP 對負載粗糙的建模導致對尾延遲的預測產(chǎn)生了較大的誤差。在服務速率固定的情況下,租戶實際的百分位延遲分布與使用MMPP+SNC 方法預測的延遲分布如圖4 所示,尾延遲（95 百分位以上）誤差平均為7 倍,最高可達23 倍。

3 AccGecko 框架設計

3.1 AccGecko 框架綜述

在開源的分布式系統(tǒng)Ceph 上構建AccGecko 框架,如圖6 所示。AccGecko 在每個客戶端創(chuàng)建一個Admission Controller,負責允許或禁止租戶的負載接入存儲系統(tǒng)。AccGecko 在每個存儲節(jié)點創(chuàng)建了固定服務速率隊列,以保證已接入系統(tǒng)租戶的延遲SLO。上述組件的所有信息由一個具有全局視圖的組件AccGecko Controller 提供。

圖6 AccGecko 框架在Ceph 上的示意圖

AccGecko Controller 的數(shù)據(jù)流如圖7 所示。新來的租戶需要提供延遲SLO 和足以代表其負載特征的trace,trace 也可以于在線狀態(tài)下抓取。trace 包含了一段請求流,每個請求以大小、位移以及發(fā)送時間作為參數(shù)。

圖7 AccGecko Controller 數(shù)據(jù)流

由于租戶的負載分布在多個存儲節(jié)點,因此保證租戶的延遲SLO 意味著保證所有存儲節(jié)點上的租戶延遲SLO。AccGecko Controller 提供了Trace Replayer 在存儲系統(tǒng)上重放trace 以獲取每個請求的存儲位置,并獲取每個存儲節(jié)點上該租戶的subtrace。

對于每個subtrace,AccGecko Controller 提供了Workload Modeler 從突發(fā)流量的產(chǎn)生強度、概率和密集程度對租戶負載進行建模,并識別出連續(xù)的突發(fā)流量（3.2 節(jié)）。

AccGecko Controller 提供了Latency Predictor 預測每個存儲節(jié)點上新租戶與已接入租戶所需的資源數(shù)量,逐幀地預測租戶連續(xù)突發(fā)流量期間請求延遲超限的概率（3.3 節(jié)）。在此基礎上,預測為租戶分配多少服務速率可以保證其尾延遲SLO,如果并未超出存儲節(jié)點的服務能力,則允許新租戶接入系統(tǒng)。

租戶分配的服務速率和租戶準入信息將通過Admission Judger 轉發(fā)給其他的AccGecko 組件。

3.2 租戶負載建模

為了更準確地預測服務端尾延遲,Workload Modeler 從突發(fā)流量的產(chǎn)生強度、概率和密集程度3個維度對租戶的負載進行建模。

基于租戶負載的trace,采用馬爾科夫鏈容易對突發(fā)流量產(chǎn)生的強度和概率進行建模,然而對突發(fā)流量的密集程度建模存在挑戰(zhàn)。其一,馬爾科夫鏈的狀態(tài)轉移矩陣只能獲得相鄰的突發(fā)流量之間的轉移概率,因此它只能運用于無突發(fā)流量的負載,即流量是均勻分布的負載。當預測一段連續(xù)事件發(fā)生的概率時,馬爾科夫鏈預測的延遲過小,無法識別出突發(fā)流量相近但不相鄰的情況。如何獲得突發(fā)流量相近的連續(xù)事件概率是第1 個挑戰(zhàn)。其二,相近的突發(fā)流量之間夾雜著非突發(fā)流量事件,當非突發(fā)流量事件較多時,前一個突發(fā)流量對服務端請求排隊的影響已經(jīng)消除。只有當非突發(fā)流量事件較少時,相近的突發(fā)流量才會對服務端請求產(chǎn)生共同影響,因此如何判斷突發(fā)流量是否相近是第2 個挑戰(zhàn)。

為了準確地對突發(fā)流量的密集程度進行建模,引入了機器學習中的密度聚類方法（density-based spatial clustering of applications with noise,DBScan）識別相近的突發(fā)流量。DBScan 算法基于一組鄰域參數(shù)（ε,MinPts）來描述樣本分布的緊密程度,規(guī)定了在一定鄰域閾值ε內樣本的個數(shù)MinPts（即密度）,并根據(jù)密度進行聚類。ε參數(shù)和狀態(tài)距離的設定決定了是否能識別出相近的突發(fā)流量。

突發(fā)流量對服務端延遲的影響存在延續(xù)性。請求的服務速率低于某突發(fā)流量期間的請求發(fā)送速率,則請求開始在IO 隊列中排隊,經(jīng)歷若干個非突發(fā)流量之后,如果IO 隊列中依然存在請求,說明該突發(fā)流量對服務端請求排隊的影響仍未結束,此時第2 個突發(fā)流量將在第1 個突發(fā)流量的影響上繼續(xù)排隊。因此如果兩個突發(fā)流量對服務端請求排隊產(chǎn)生疊加影響,則將這兩個突發(fā)流量定義為相近。

為了識別出相近的突發(fā)流量,突發(fā)流量之間的距離要小于鄰域閾值ε。對trace 按照固定周期（如1 ms）進行切分,獲取每個周期內的請求發(fā)送數(shù)量,每個周期為租戶負載的一個狀態(tài)。在此基礎上,兩個狀態(tài)之間的距離設定為狀態(tài)之間所有狀態(tài)的請求發(fā)送的均值的倒數(shù)。ε參數(shù)的設定取決于預設請求的服務速率,設服務速率為租戶負載平均發(fā)送速率的M倍,在此平均發(fā)送速率下單個周期的請求發(fā)送數(shù)量為N,則將ε參數(shù)設定為1/MN。M的設定會影響連續(xù)相近突發(fā)流量的持續(xù)時間,進而影響尾延遲預測的準確程度,本文在4.2 節(jié)對M的設定進行了評測。

Workload Modeler 所采用的密度聚類算法與原始的DBScan 有兩方面的不同。一方面,鄰域是單向的。DBScan 算法提出了核心對象的概念,若x的ε鄰域至少包含MinPts個樣本,則x為一個核心對象。以平面一維樣本為例,核心對象的左側和右側均為鄰域的一部分。由于突發(fā)流量期間的請求排隊并不會對之前的排隊產(chǎn)生影響,因此本文采用的密度聚類算法為單向的,以第1 個突發(fā)流量狀態(tài)為核心對象,按狀態(tài)發(fā)生的時間順序向前查找鄰域。另一方面,鄰域的設定不僅以ε為邊界。Workload Modeler 的目的是識別出相近的突發(fā)流量,孤立的突發(fā)流量以及相近突發(fā)流量后的非突發(fā)流量不在考慮范圍之內。對鄰域進行截尾操作,如果狀態(tài)與核心對象間的距離單調遞增直至大于ε參數(shù),則將遞增的狀態(tài)從鄰域中剔除。同時為了防止識別出孤立的突發(fā)流量,將MinPts設定為2。

通過上述方法,Workload Modeler 可以識別出對服務端請求延遲產(chǎn)生共同影響的相近突發(fā)流量,每段鄰域的長度可視為突發(fā)流量的持續(xù)時間。至此,Workload Modeler 將租戶負載劃分兩部分,一部分為突發(fā)流量連續(xù)階段,另一部分為非突發(fā)流量和孤立突發(fā)流量部分。

3.3 AccTail 尾延遲預測方法

租戶服務端尾延遲主要由連續(xù)的突發(fā)流量產(chǎn)生,Workload Modeler 已經(jīng)識別出了連續(xù)突發(fā)流量,AccTail 尾延遲預測方法通過逐幀地預測連續(xù)突發(fā)流量產(chǎn)生的延遲,并統(tǒng)計占比,以獲得尾延遲。在此基礎上,預測為租戶分配多少服務速率可以保證其尾延遲SLO。尾延遲預測的偽代碼如算法1 所示。租戶負載的連續(xù)突發(fā)流量含有強度和密集程度2 個維度的特性,從而產(chǎn)生不同的組合。為了獲得更精準的服務端尾延遲,AccTail 首先根據(jù)強度對連續(xù)突發(fā)流量進行了劃分。如算法1 中的第1～4 行所示,AccTail 按照連續(xù)突發(fā)流量平均強度由低到高,等分為k個stage。k的設定決定了尾延遲預測的準確程度。k設定得太低,則無法區(qū)分不同強度的連續(xù)突發(fā)流量;k設定得太高,則失去了一般性,將突發(fā)流量的強度和密集程度耦合在一起。兩個極端均會降低尾延遲預測的準確程度,4.2 節(jié)對k值的設定進行了評測。

逐個請求計算延遲是不可取的,既失去了一般性,又會極大地增加計算的復雜度。AccTail 采用計桶的方式獲得百分位尾延遲。如算法1 中的第5 行以及第12～20 行所示,桶的下標為服務端請求延遲,桶的數(shù)值即為服務端延遲下標的請求數(shù)量,計算尾延遲時,按照服務端延遲從大到小累加請求數(shù)量,至超出百分位限制終止并返回結果。

每個延遲桶計數(shù)的方法如算法1 中第6～11 行所示,對于每個強度階梯中的連續(xù)突發(fā)流量,在強度上不作區(qū)分,統(tǒng)計請求平均發(fā)送速率bsi.avg interval。遵循突發(fā)流量持續(xù)時間越長、延遲越大的原則來遍歷每段連續(xù)突發(fā)流量,在第9 行給出了計算延遲的方法。其中sr為服務速率,j為請求在連續(xù)突發(fā)流量中的位置,j越大則延遲越高。c為常量,將其設定為請求抵達隊列后的等待服務時間與IO 線程額外處理時間的和,4.2 節(jié)對c的設定進行了評測。

4 AccGecko 評測

4.1 評測方法

對比框架將AccGecko 框架與現(xiàn)有最新的2種框架PriorityMeister[9]和SNC-Meister[11]進行了對比。原始的開源SNC-Meister 用于網(wǎng)絡,基于源碼進行了重寫以適應分布式存儲系統(tǒng)。Silo 只提供了固定速率控制的思想,但沒有陳述如何設定速率以保證租戶的服務端尾延遲,因此并未與其作比較。

測試平臺測試采用3 臺物理機作為存儲節(jié)點,另外1 臺物理機作為客戶端。每臺物理機含有1塊Intel（R） Xeon（R） E5-2650 v4 processor（2.20 GHz）CPU,1 塊Intel P3700 400 GB SSD,1 塊Intel Corporation 82599ES 10 Gigabit 網(wǎng)卡,以及64 GB 的內存。操作系統(tǒng)為CentOS 7.5.1804,Ceph 的版本為10.2.0。

測試負載測試采用了SNIA 的Microsoft Production Server Traces[17]和 Microsoft Enterprise Traces[18]。這些trace 采集于Livemap、MSN、TPC-C和TPC-E 等場景下的塊層。負載突發(fā)流量的發(fā)送速率為均值的2～10 倍。

測試方法對于開環(huán)負載trace 測試,本文基于Ceph 的librbd 設計了一個開環(huán)負載發(fā)送器以重放trace。trace 被切割為5 min 的分段,AccGecko Controller 使用其中突發(fā)流量最大的分段來預測服務端百分位延遲。測試中回放整個trace 來驗證租戶的服務端尾延遲SLO 是否能夠得到保證。

4.2 AccTail 尾延遲預測方法性能分析

將AccTail 尾延遲預測方法的各部分進行分解,并與未使用SNC 以及泊松分布的馬爾科夫過程（Markov-modulated process,MMP）作對比,觀察租戶負載突發(fā)流量的密集程度建模對服務端尾延遲預測準確性的影響。本文主要對99 百分位和99.9 百分位2 種類型的尾延遲SLO 進行評測,通過為租戶分配固定的服務速率,使租戶的尾延遲恰好滿足其尾延遲SLO。接著回放trace 并統(tǒng)計實際的尾延遲進行對比。分別對陽性誤差（error positive）和陰性誤差（error negative）2 個指標進行評測。對于尾延遲預測來說,當預測值高于實際值時,為租戶分配的資源將超出其所需的資源,造成浪費,但租戶的尾延遲SLO 并不會被違反,稱這類延遲預測誤差為陽性誤差;與之相反,當預測值低于實際值時,租戶的尾延遲SLO 將被違反,相比于陽性誤差,這類尾延遲預測誤差更為嚴重,是不被允許的,稱其為陰性誤差。

結果如圖8 所示,圖中橫軸為評測的方法,包括只采用馬爾科夫過程的方法（MMP）、密度聚類算法（DB）以及在此基礎上額外增加請求延遲的方法（DB+17 μs 和DB +25 μs）;縱軸為延遲預測誤差的百分比。圖8（a）為99 百分位延遲預測誤差,圖8（b）為99.9 百分位預測誤差。只采用馬爾科夫鏈時,99 百分位和99.9 百分位的陰性誤差分別達到了89%和174%。這是因為馬爾科夫過程只對租戶負載突發(fā)流量的產(chǎn)生強度和概率進行了建模,并未考慮產(chǎn)生密集程度,認為突發(fā)流量在整個負載上是均勻分布的,所以對服務端尾延遲的預測較低。實際上,密集的突發(fā)流量將導致較高的服務端尾延遲。

圖8 采用馬爾科夫過程以及AccTail 各部分對服務端尾延遲預測準確度的影響

基于密度聚類算法,AccTail 對突發(fā)流量的密集程度進行了建模,預測了連續(xù)突發(fā)流量的持續(xù)時間,并逐幀計算了連續(xù)突發(fā)流量期間內請求超限的概率,因此在DB 模式下,99 百分位和99.9 百分位的陰性誤差分別為20%和13%。

為了徹底消除陰性誤差,對請求延遲進行了修正。IO 線程處理的時間同樣影響了服務端尾延遲,因此在每個請求的延遲基礎上增加了IO 線程處理時間的均值17 μs,此時99 百分位延遲預測的陰性誤差為0,而99.9 百分位延遲預測的陰性誤差降低為4%;請求抵達IO 隊列上時并不會被馬上服務,而是要等待IO 線程完成上一個請求的服務,因此將請求的延遲額外增加25 μs,包括請求等待的延遲,此時99.9 百分位的陰性誤差也降低為0。最終,99百分位和99.9 百分位延遲預測的平均陽性誤差分別為67%和59%,最大陽性誤差分別為156% 和164%。上述結果中的M參數(shù)為2,k值為1。接下來,從M參數(shù)和k值的設定兩方面對陽性誤差進行優(yōu)化。

在對負載突發(fā)流量進行建模時,對突發(fā)流量速率的下限設定決定了連續(xù)突發(fā)流量的識別精度。若下限設定過高,則無法識別強度較低的突發(fā)流量,降低尾延遲預測的準確程度;若下限設定過低,則有更多的非突發(fā)流量被誤識別為突發(fā)流量,同樣降低尾延遲預測的準確程度。設下限為租戶負載平均發(fā)送速率的M倍,本文對M參數(shù)的設定進行了評測,如圖9 所示,圖9（a）為99 百分位延遲預測誤差,圖9（b）為99.9 百分位預測誤差,橫軸為M參數(shù)。當M參數(shù)從2 降低為1.5 時,對于99 和99.9 百分位延遲來說,預測誤差均最小,平均預測誤差分別從67%和59%降低為47%和40%,最大預測誤差分別從156%和164%降至143%和123%。隨著M參數(shù)繼續(xù)下降,尾延遲預測誤差將繼續(xù)升高。

圖9 M 參數(shù)對尾延遲預測準確程度的影響

租戶負載的連續(xù)突發(fā)流量含有強度和密集程度2 個維度的特性,從而產(chǎn)生不同的組合。為了獲得更精準的服務端尾延遲,AccTail 按照連續(xù)突發(fā)流量平均強度由低到高等分為k個stage。k的設定決定了尾延遲預測的準確程度。k設定得太低,則無法區(qū)分不同強度的連續(xù)突發(fā)流量;k設定得太高,則失去了一般性,將突發(fā)流量的強度和密集程度耦合在一起。兩個極端均會降低尾延遲預測的準確程度。本文對k參數(shù)的設定進行了評測,如圖10 所示,圖10（a）為99 百分位延遲預測誤差,圖10（b）為99.9 百分位預測誤差,橫軸為k參數(shù)。當k=3 時,99 百分位延遲預測誤差均最小,平均預測誤差為36%,最大預測誤差為110%。相比于99 百分位來說,99.9 百分位所需的強度和精度更高。當k=5時,尾延遲預測誤差最小,平均預測誤差為30%,最大預測誤差為95%。AccTail 對尾延遲的預測依然存在誤差,這主要是由于對租戶負載建模時,選擇trace 片段作為輸入時采用了突發(fā)流量強度與密集程度較高的部分,而在回放整個trace 時,整體的突發(fā)流量強度與密集程度較低,產(chǎn)生一定的陽性誤差。

圖10 k 參數(shù)對尾延遲預測準確程度的影響

將AccTail 尾延遲預測方法和PriorityMeister（PM）以及SNC-Meister（SNCM）尾延遲保證框架對尾延遲預測的誤差進行對比。其中,PriorityMeister采用rb對負載建模方法和NetworkCalculus 最大延遲預測方法,SNC-Meister 框架采用了MMPP 負載建模方法和SNC 尾延遲預測方法。圖11 展示了對比結果,圖11（a）為99 百分位延遲預測誤差,圖11（b）為99.9 百分位預測誤差。由于PM 只預測了最大延遲,因此預測準確程度低于SNCM。對于99 百分位尾延遲,相比于PM,AccTail 的平均預測誤差和最大預測誤差分別降低了56 倍和33 倍;相比于SNCM,AccTail 的平均預測誤差和最大預測誤差分別降低了36 倍和18 倍。對于99.9 百分位尾延遲,相比于PM,AccTail的平均預測誤差和最大預測誤差分別降低了12 倍和11 倍;相比于SNCM,AccTail的平均預測誤差和最大預測誤差分別降低了8 倍和6 倍。

圖11 尾延遲SLO 保證工作對尾延遲預測準確程度的對比

4.3 AccGecko 性能分析

基于AccTail 尾延遲預測方法,結合固定服務速率資源分配方法來保證租戶的尾延遲SLO。通過與PM 以及SNCM 尾延遲保證框架對比系統(tǒng)承載的租戶數(shù)量,可以觀察到尾延遲預測準確度提升所帶來的系統(tǒng)資源利用率提升。

如圖12 所示,對結果基于SNCM 進行了歸一化。對于99 百分位尾延遲SLO,AccGecko 比PM 和SNCM 分別多承載了194% 和112% 的租戶;對于99.9 百分位尾延遲SLO,AccGecko 比PM 和SNCM分別多承載了109%和19%的租戶。通過提升尾延遲預測的準確程度,可以有效地降低租戶獲得資源的超配程度,提升系統(tǒng)的資源利用率。

圖12 系統(tǒng)承載租戶數(shù)量對比

5 結論

本文提出了一種面向多租戶分布式存儲系統(tǒng)以保證服務端尾延遲SLO 的框架AccGecko。本文分析了租戶負載突發(fā)流量的產(chǎn)生強度、概率和密集程度對服務端尾延遲的影響,結合密度聚類算法從3個維度對租戶負載進行建模,并逐幀地預測租戶連續(xù)突發(fā)流量期間請求延遲超限的概率,提升了服務端延遲預測的準確程度。相比于已有尾延遲SLO保證框架,針對99 百分位和99.9 百分位尾延遲SLO,AccGecko 使系統(tǒng)承載的租戶數(shù)量分別平均提升了112%和19%。下一步將采用不同的聚類方式,選取優(yōu)化的模型對比分析來進一步提升資源分配的效率;同時針對設備IO 延遲波動,更精準地預測服務端尾延遲,以適應讀寫混合等場景。