AccGecko:面向分布式存儲(chǔ)系統(tǒng)的尾延遲SLO 保證框架①

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

（中國(guó)科學(xué)院計(jì)算技術(shù)研究所先進(jìn)計(jì)算機(jī)系統(tǒng)研究中心 北京100190）

（中國(guó)科學(xué)院大學(xué) 北京100049）

0 引言

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

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

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

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

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

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

基于上述租戶負(fù)載建模方法和尾延遲預(yù)測(cè)方法,結(jié)合固定速率資源分配方法,本文提出了AccGecko,一種面向分布式存儲(chǔ)系統(tǒng)的先驗(yàn)式多租戶服務(wù)端尾延遲SLO 保證框架?；谖④浱峁┑纳a(chǎn)環(huán)境trace[17-18],本文將AccGecko 與當(dāng)前最新的尾延遲SLO 保證框架進(jìn)了對(duì)比。結(jié)果顯示,針對(duì)99和99.9 百分位尾延遲SLO,AccGecko 使存儲(chǔ)系統(tǒng)承載的租戶數(shù)量平均提升了約112%和19%。

1 相關(guān)工作

1.1 尾延遲預(yù)測(cè)方法與租戶負(fù)載建模

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

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

1.2 資源分配方法

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

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

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

2 研究動(dòng)機(jī)

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

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

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

圖1 租戶負(fù)載示意圖

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

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

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

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

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

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

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

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

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

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

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

采用了SNC 的尾延遲預(yù)測(cè)方法與MMPP 負(fù)載建模方法,對(duì)租戶負(fù)載的尾延遲預(yù)測(cè)誤差依然較大,主要原因包括以下3 點(diǎn)。

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

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

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

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

在服務(wù)速率固定的情況下,租戶實(shí)際的百分位延遲分布與使用MMPP 和SNC 方法預(yù)測(cè)的百分位延遲分布如圖4 所示。該圖給出了請(qǐng)求服務(wù)速率固定的情況下租戶實(shí)際的百分位延遲分布（Practical）與使用MMPP 和SNC 方法預(yù)測(cè)的百分位延遲分布。

圖4 MMPP+SNC 對(duì)尾延遲預(yù)測(cè)的誤差

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

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

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

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

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

3 AccGecko 框架設(shè)計(jì)

3.1 AccGecko 框架綜述

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

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

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

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

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

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

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

租戶分配的服務(wù)速率和租戶準(zhǔn)入信息將通過(guò)Admission Judger 轉(zhuǎn)發(fā)給其他的AccGecko 組件。

3.2 租戶負(fù)載建模

為了更準(zhǔn)確地預(yù)測(cè)服務(wù)端尾延遲,Workload Modeler 從突發(fā)流量的產(chǎn)生強(qiáng)度、概率和密集程度3個(gè)維度對(duì)租戶的負(fù)載進(jìn)行建模。

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

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

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

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

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

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

3.3 AccTail 尾延遲預(yù)測(cè)方法

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

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

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

4 AccGecko 評(píng)測(cè)

4.1 評(píng)測(cè)方法

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

測(cè)試平臺(tái)測(cè)試采用3 臺(tái)物理機(jī)作為存儲(chǔ)節(jié)點(diǎn),另外1 臺(tái)物理機(jī)作為客戶端。每臺(tái)物理機(jī)含有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 的內(nèi)存。操作系統(tǒng)為CentOS 7.5.1804,Ceph 的版本為10.2.0。

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

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

4.2 AccTail 尾延遲預(yù)測(cè)方法性能分析

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

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

圖8 采用馬爾科夫過(guò)程以及AccTail 各部分對(duì)服務(wù)端尾延遲預(yù)測(cè)準(zhǔn)確度的影響

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

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

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

圖9 M 參數(shù)對(duì)尾延遲預(yù)測(cè)準(zhǔn)確程度的影響

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

圖10 k 參數(shù)對(duì)尾延遲預(yù)測(cè)準(zhǔn)確程度的影響

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

圖11 尾延遲SLO 保證工作對(duì)尾延遲預(yù)測(cè)準(zhǔn)確程度的對(duì)比

4.3 AccGecko 性能分析

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

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

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

5 結(jié)論

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