古埃及人根據(jù)天狼偕日升和尼羅河泛濫周期的長期觀測，準(zhǔn)確預(yù)測出洪水到來和退去的時(shí)間，并收獲大量肥沃土地來耕耘；托勒密根據(jù)喜帕恰斯留下的大量觀測數(shù)據(jù)建立模型，高精度預(yù)測了今后某個(gè)時(shí)候某個(gè)星球所在的位置；再從“朝霞不出門，晚霞行千里”的古諺語，到通過氣象衛(wèi)星、雷達(dá)收集并進(jìn)行氣象數(shù)據(jù)同化來精確預(yù)測天氣，我們發(fā)現(xiàn)“預(yù)測未來”不再僅僅打著“科幻、超能力”的標(biāo)簽，更能通過獲取、分析數(shù)據(jù)，讓未來照進(jìn)現(xiàn)實(shí)。
云計(jì)算為何需要預(yù)測？
預(yù)測源起于“動(dòng)”，正因非靜態(tài)才無法確定未來某一時(shí)刻的狀態(tài)。而“動(dòng)”的程度決定了預(yù)測的難度。
l 從云上用戶需求側(cè)看：業(yè)務(wù)負(fù)載、業(yè)務(wù)規(guī)模、設(shè)置的告警閾值都在變動(dòng)
l 從云資源供給側(cè)看：用戶數(shù)、資源使用率、碎片率也在變動(dòng)
如果能提前預(yù)測客戶需求，就能通過智能推薦、智能告警等來提升易用性，更能提前進(jìn)行硬件規(guī)劃、資源騰挪，保障流量洪峰下的擴(kuò)容訴求，助力實(shí)現(xiàn)“極優(yōu)、極簡”的云上體驗(yàn)。
圖1 “看得見的易用”與“看不見的智能”
預(yù)測的內(nèi)核：云上資源智能畫像
根據(jù)VM歷史資源利用率、VM請求時(shí)間間隔、Flavor生命周期等歷史數(shù)據(jù)，利用關(guān)聯(lián)分析模型和深度學(xué)習(xí)算法，可用來描繪資源表面、內(nèi)在以及未來。智能畫像的引入讓云平臺(tái)資源管理更加精細(xì)化、智能化。
畫像關(guān)鍵技術(shù)剖析
關(guān)鍵技術(shù)一：時(shí)序預(yù)測
在云服務(wù)中，像容量預(yù)測，主機(jī)熱點(diǎn)、動(dòng)態(tài)告警等都涉及到時(shí)序預(yù)測，即如果知道一段歷史時(shí)間（T*時(shí)刻以前）的數(shù)據(jù)變化規(guī)律，如何去預(yù)測未來一段時(shí)間的變化趨勢呢？生活中如天氣的變化、人口增長、經(jīng)濟(jì)增速、股票波動(dòng)，甚至最近大家比較關(guān)注的新冠疫情的發(fā)展都屬于時(shí)序預(yù)測范疇。
圖 2 時(shí)序預(yù)測
云上時(shí)序預(yù)測的輸入主要來源于主機(jī)或虛擬機(jī)的資源利用率，而云上業(yè)務(wù)的復(fù)雜多變，也提升了分析資源利用規(guī)律的復(fù)雜度。總體而言，有三方面的挑戰(zhàn)：
l波形的復(fù)雜性：我們初步分析歷史trace的數(shù)據(jù)并形成圖像，可以看到有少部分是平穩(wěn)的甚至是有近似周期性的，也有一部分呈現(xiàn)上升或下降的趨勢，但更多的是單個(gè)“山峰”或者偶爾突發(fā)的情況，甚至?xí)蓄l繁地上下震蕩；
l業(yè)務(wù)的疊加性：以上波形表征的多樣性，主要是由于云平臺(tái)中單臺(tái)物理主機(jī)上可能運(yùn)行著多個(gè)租戶的多個(gè)VM，同時(shí)單個(gè)VM也可能運(yùn)行著多種應(yīng)用；
l不可以預(yù)見的人為因素：比如因促銷而產(chǎn)生的批量訂單往往會(huì)導(dǎo)致某個(gè)資源池?zé)o法容納；超大規(guī)格VM的偶然創(chuàng)建也可能引發(fā)一些容量事件。
#經(jīng)典算法#
如果從波形的特性來看，可以大致把時(shí)序預(yù)測歸為周期性和非周期性兩大類。對(duì)于周期性的預(yù)測問題，谷歌在文獻(xiàn)[1]中提到可以判別歷史曲線中是否有重復(fù)出現(xiàn)的相似性模式窗口，當(dāng)然可以通過Pearson相關(guān)系數(shù)來計(jì)算任意兩個(gè)模式窗口的相似度。但由此引發(fā)一個(gè)問題：模式窗口（即周期長度）的大小又如何確定？我們首先想到的是快速傅里葉變換（FFT），即把原始數(shù)據(jù)的時(shí)域變化轉(zhuǎn)為頻域的變化，然后模式窗口的大小等于采樣率與信號(hào)功率最大的頻率分量的頻率之商。
其實(shí)還有一個(gè)更加直觀的辦法，如圖4所示，大家可以想象一個(gè)連綿起伏的山峰，如果每個(gè)山頭是類似的，那么任意相鄰兩個(gè)山頭最高點(diǎn)（峰值）之間的距離應(yīng)該是近似相等的?；谶@個(gè)語義，我們想到一個(gè)辦法：把時(shí)域數(shù)據(jù)轉(zhuǎn)為功率譜，取出功率譜中前L個(gè)（比如100個(gè)）峰值，計(jì)算相鄰兩個(gè)峰值之間的距離，如果這個(gè)距離數(shù)據(jù)的變異系數(shù)（即標(biāo)準(zhǔn)差除以期望）足夠?。ㄈ缧∮?.1），那么可以認(rèn)為這些峰值是等間距的，尤其可以判定其周期性及周期的長度。
圖3 周期性預(yù)測辦法
至于非周期性的預(yù)測，則有非常多的模型可以參考。如比較經(jīng)典的ARIMA模型（圖5），其主要分為AR（自回歸）和MA（滑動(dòng)平均）兩部分。首先把原始數(shù)據(jù)進(jìn)行差分（即依次把后一時(shí)刻的值減去前一時(shí)刻的值得到新的序列，可以多次差分，但一般不超過三次），將不平穩(wěn)的序列變平穩(wěn)。當(dāng)差分得到平穩(wěn)序列以后即可進(jìn)行模式識(shí)別：判別其符合AR、 MA或ARMA模型。AR模型（自回歸）認(rèn)為需要預(yù)測的值是歷史數(shù)據(jù)的加權(quán)；而MA模型（滑動(dòng)平均）認(rèn)為下一個(gè)值的波動(dòng)性是歷史波動(dòng)性的加權(quán)。綜合這兩方面可以得到下一個(gè)預(yù)測結(jié)果。
圖 4 ARIMA模型
此外還有馬爾科夫（Markov-Chain）模型（圖6），其核心思想是條件概率。比如到銀行很可能是辦理金融業(yè)務(wù)、最近體溫升高則有可能患上新冠肺炎等等。同樣的道理，我們可以把CPU的利用率劃分成若干個(gè)區(qū)間，通過對(duì)歷史數(shù)據(jù)的統(tǒng)計(jì)，比如當(dāng)處于區(qū)間【30%，60%）（State 2）時(shí)，未來的利用率有60%的概率還會(huì)停留在本區(qū)間范圍，而分別有20%的概率會(huì)轉(zhuǎn)移到區(qū)間【0%，30%）（State 1）或區(qū)間【60%，100%）（State 3）。通過這樣的辦法，可以得到一個(gè)完整的馬爾科夫狀態(tài)轉(zhuǎn)移（MDP）圖，由此可以對(duì)未來的時(shí)刻的資源變化進(jìn)行預(yù)測。
圖 5 馬爾科夫模型
#進(jìn)階算法#
Facebook針對(duì)其社交平臺(tái)上用戶點(diǎn)擊和轉(zhuǎn)發(fā)事件數(shù)的預(yù)測提出了Prophet模型[2]。由于其社交平臺(tái)的數(shù)據(jù)具有明顯的周期性、趨勢、節(jié)假日以及存在個(gè)別的異常點(diǎn)（噪音），所以Prophet本質(zhì)上是一個(gè)廣義疊加模型（GAM），即把前面提到的四方面分別建模再進(jìn)行累加而成。AWS則提出了DeepAR模型[3]，主要用于其店鋪銷售的預(yù)測，其基礎(chǔ)理論是LSTM[4]，即長短期記憶神經(jīng)網(wǎng)絡(luò)，通過一些門的設(shè)計(jì)來控制歷史長河中哪些信息應(yīng)該遺忘、哪些應(yīng)該保留下來。
#前沿算法#
谷歌在AGILE系統(tǒng)[5]里提出了一種分解預(yù)測再組合的思路。打個(gè)比方，在一個(gè)房間中，如果一千個(gè)人同時(shí)在說話，那么最終的音頻可能是一段看起來雜亂無章“噪音”，但是如果把每個(gè)人說的話分離開來，那么每個(gè)人說話是清晰的也是可預(yù)測的。
基于這個(gè)思想，可以設(shè)計(jì)一個(gè)分解-組合的預(yù)測模型（圖7）。首先，對(duì)原始的資源曲線使用EMD（黃鄂院士所提出的經(jīng)驗(yàn)?zāi)B(tài)分解）技術(shù)分解成若干平穩(wěn)子序列以及殘差項(xiàng)；然后對(duì)于每個(gè)平穩(wěn)子序列使用傳統(tǒng)的時(shí)序預(yù)測算法進(jìn)行預(yù)測；最后再把所有預(yù)測結(jié)果進(jìn)行累加，從而得到最終的結(jié)果。
圖 6 分解-組合預(yù)測法
關(guān)鍵技術(shù)二：業(yè)務(wù)識(shí)別
云平臺(tái)每時(shí)每刻承載著海量的業(yè)務(wù)，這些業(yè)務(wù)中有些是CPU密集型的，有些是內(nèi)存密集型，也有些是網(wǎng)絡(luò)密集型等等。假設(shè)大家都“搶”CPU資源，且這些業(yè)務(wù)都放在同一臺(tái)主機(jī)上，那么就會(huì)引發(fā)資源爭奪的“打架”行為，造成業(yè)務(wù)之間的互相干擾；但如果把相同密集型的業(yè)務(wù)分開放，比如CPU密集型與網(wǎng)絡(luò)密集型混合放置，那么也許可以“和平共處”[6]。由此，引出一個(gè)問題（圖8）：在云上如何從底層的資源監(jiān)控?cái)?shù)據(jù)能夠準(zhǔn)確地識(shí)別上層業(yè)務(wù)類型，從而盡可能減少業(yè)務(wù)間的干擾性，保證租戶QoS？
圖 7 業(yè)務(wù)識(shí)別與QoS調(diào)度
首先，我們可以通過各維度資源的利用情況進(jìn)行關(guān)聯(lián)性分析，使用Spearman系數(shù)計(jì)算任意兩個(gè)維度的關(guān)聯(lián)程度，形成一個(gè)“feature map”（圖9）。此外，我們還可以在原始的數(shù)據(jù)序列中使用多個(gè)不同大小的滑動(dòng)時(shí)間窗口，在每個(gè)時(shí)間窗后中提取數(shù)據(jù)更細(xì)粒度的特征，類似“卷積核”的辦法。綜合以上兩方面，可以對(duì)業(yè)務(wù)類別進(jìn)行初步的畫像。
圖 8 資源利用相關(guān)性
關(guān)鍵技術(shù)三：算力匹配
我們在業(yè)務(wù)識(shí)別中發(fā)現(xiàn)一個(gè)現(xiàn)象：相當(dāng)一部分用戶其實(shí)不清楚什么樣的虛擬機(jī)類型/套餐（通常稱為flavor）最適合其業(yè)務(wù)。因?yàn)閺谋O(jiān)控?cái)?shù)據(jù)可以看出，大部分用戶資源跑得很閑，即未能將資源充分利用起來；另外也有部分用戶一直處于滿負(fù)載狀態(tài)，如可能運(yùn)行大數(shù)據(jù)作業(yè)或AI應(yīng)用。那么，如何給用戶推薦既滿足其業(yè)務(wù)訴求又使得性價(jià)比最高的最佳資源配置？如圖10所示，用戶通常只知道自己需要運(yùn)行什么樣的應(yīng)用、有多大的數(shù)據(jù)量、需要什么時(shí)間點(diǎn)完成以及有多少預(yù)算等等，雖然用戶傾向于更便宜的虛擬機(jī)類型，但通常不知道哪種類型性價(jià)比最高。
圖 9 算力匹配
一般的思路是把所有用戶與歷史所使用過的虛擬機(jī)類型（flavor）構(gòu)成一個(gè)二維矩陣，如果一個(gè)用戶使用過某種虛擬機(jī)類型，那么我們就可以根據(jù)租戶的資源使用情況對(duì)item進(jìn)行綜合打分。當(dāng)然，最終的矩陣是非常稀疏的，我們需要做的是通過SVD&PQ這類的算法進(jìn)行矩陣分解并且預(yù)測那些用戶沒有使用過的虛擬機(jī)類型的分值，并根據(jù)這個(gè)分值大小進(jìn)行推薦。
但是，如果僅根據(jù)最高預(yù)測分值進(jìn)行推薦，可能會(huì)導(dǎo)致某些用戶增加的成本較高。如圖11所示，假設(shè)某個(gè)用戶原來使用1u1g的虛擬機(jī)規(guī)格，瞬間給其推薦4u8g的配置，從業(yè)務(wù)上也許已經(jīng)緩和其高負(fù)載狀況，但是用戶需要多付的錢可能是其不能接受的。因此，需要綜合考量虛擬機(jī)價(jià)格和規(guī)格大小進(jìn)行推薦距離度量，給出合理的推薦范圍。
圖 10 推薦距離度量
Case Study
容量畫像與最佳適應(yīng)調(diào)度
一方面，如果能夠?qū)Y源池余量進(jìn)行精準(zhǔn)畫像，即通過設(shè)計(jì)測算定理預(yù)測每種flavor未來還能放置多少；另一方面，可以統(tǒng)計(jì)每種flavor在過去請求trace中的分布比例。結(jié)合這兩方面的信息，可以設(shè)計(jì)一種容量調(diào)度算法Besfit Capacity用于虛擬機(jī)在線調(diào)度，以讓任意兩種flavor的剩余容量比盡可能接近于它們的歷史請求比。
這里采用首次發(fā)放失敗時(shí)，算法接收的請求數(shù)量與最大理論上界的比值作為評(píng)測指標(biāo)，從下可以看到，相比傳統(tǒng)Cosfit算法及其改進(jìn)算法，Besfit Capacity算法表現(xiàn)更優(yōu)，甚至某些場景下比傳統(tǒng)Bestfit算法更好。
圖 11 容量調(diào)度對(duì)比實(shí)驗(yàn)
利用率畫像與彈性調(diào)度
傳統(tǒng)虛擬機(jī)調(diào)度是基于分配率的，但實(shí)際上大部分虛擬機(jī)處于低利用率狀態(tài)，并且不均衡的利用率情況下，容易產(chǎn)生熱點(diǎn)主機(jī)（即主機(jī)資源利用率>60%）。這里通過利用率預(yù)測的辦法，把基于利用率調(diào)度與基于分配率調(diào)度進(jìn)行對(duì)比實(shí)驗(yàn)，同時(shí)對(duì)相同一段時(shí)間的歷史請求序列進(jìn)行回放。從表1可以看到，相比分配率調(diào)度，利用率畫像+動(dòng)態(tài)Bestfit算法可以少用5臺(tái)主機(jī)，內(nèi)存碎片率減少2.1%，同時(shí)熱點(diǎn)主機(jī)數(shù)從原來的6臺(tái)減少到0臺(tái)。
表1 - 利用率調(diào)度與分配率調(diào)度對(duì)比實(shí)驗(yàn)
資源預(yù)測與容量規(guī)劃
前面介紹的分解-組合預(yù)測法EEMD與傳統(tǒng)Holt-Winters進(jìn)行的實(shí)驗(yàn)對(duì)比分析，使用兩個(gè)trace分別預(yù)測它們未來半小時(shí)、一小時(shí)以及一個(gè)半小時(shí)的資源用量，并且預(yù)測多次。從下圖可以看出，EEMD預(yù)測法擬合效果更好、性能更加穩(wěn)定，尤其在較長時(shí)間的預(yù)測場景中，預(yù)測誤差可比Holt-Winters減少20%以上。我們使用這個(gè)方法進(jìn)行容量規(guī)劃，預(yù)測準(zhǔn)確度95%以上，上線后有效將容量引起的客戶事件數(shù)減少60%以上。
圖 13 EEMD與Holt-Winters對(duì)比實(shí)驗(yàn)
