人力成本巨大：人肉無法監控和處理所有的場景；
反應時間較長：從發現場景出問題，找出可以勻出機器的不重要場景，到加到重要場景所需要的時間相對過長，而程式天然的有反應時間短的優勢；
人力無法全局高效的排程資源， 而程式可以更敏感的發現場景的問題，更全面的搜尋可以拿出來機器的場景，并可以準确計算拿出機器的數目，有更好的全局觀。
基于如上的兩點：日常的時候提高資源使用率，大促的時候解放人力，TPP智能排程系統就産生了。TPP智能排程系統以每個叢集（一組機器，承載一個或多個場景）的CPU使用率，LOAD，降級QPS，目前場景QPS，壓測所得的單機QPS為輸入，綜合判斷每個叢集是否需要增加或者減少機器，并計算每個場景需要增減機器的确切數目，輸出到執行子產品自動增減容器。 TPP智能排程系統有如下的貢獻點：
日常運作期間，保證服務品質的情況下最大化資源使用率；
大促運作期間，能夠更快速、更準确的完成叢集之間的錯峰資源排程；
支援定時活動事件的錄入，如紅包雨、手淘首頁定時的Push，程式自動提前擴容，活動結束自動收回；
對重要場景提前預熱，完成秒級擴容。
該系統由TPP工程團隊和猜你喜歡算同學聯合搭建而成，從2017年9月開始規劃，到10月1日小批量場景上線，到10月13日三機房全量上線；經過一個月的磨合，參加了2017年雙11當天從 00:15 %到 23:59的排程，峰值QPS達到百萬級别。在日常運作中，叢集平均CPU使用率提高3.37 倍， 從原來平均8%到27%；在大促期間，完成造勢場景，導購場景和購後場景的錯峰資源排程，重要服務資源使用率保持在 30% ，非重要服務資源使用率保持在50%, 99%的重要場景降級率低于2%。同時TPP智能排程系統的"時間錄入"功能支援定時活動，如首頁紅包的提前錄入，提前擴容，活動結束收回機器，改變了以前每天需要定時手動分機器的情況。
TPP智能排程系統要解決的問題為： 如何在機器總數有限的前提下，根據每一個場景上核心服務名額KPI（異常QPS等）和場景所在叢集實體層名額KPI(CPU,IO等)，最優化每一個場景機器數目，進而使得總體資源使用率最高。
更加直白一點，就是回答如下的問題：
怎麼判斷一個叢集需要擴容？擴多少的機器
簡單的CPU超過一定的水位并不能解決問題。不同的場景的瓶頸并不完全一緻，有IO密集型的（如大量通路igraph），有CPU密集型的，一個場景可能在cpu不超過30%的情況下，就已經出現了大量的異常QPS，Load很高，需要增加機器。
如何給不同的場景自适應的判斷水位？
有的場景30% CPU運作的很好，但是有的場景10%可能就出問題了。
如何防止某些實作有問題的場景，不停的出現異常，不斷觸發擴容，進而掏空整個叢集，而實作效率較高的場景反而得不到機器，引發不公平。
如何用一套算法同時解決日常運作和大促運作的需求
當總的機器數目有限的情況下，如何配置設定不同場景之間的機器，最大化收益（有效pv）。如何用程式實作從某些場景拿機器去補充重要場景的運作。
對于運作JVM的容器，當一個新加容器在到達100%服務能力之前需要充分預熱，預熱過程會有異常QPS的産生。算法一方面要盡可能少的減少擴縮容的次數，另外一個方面，要盡可能快的發現擴容的需求，實作較高的擴容recall。如何在這兩者之間做tradeoff？
TPP智能排程涉及TPP的各方各面，其架構圖如下所示，包括資料輸入、算法決策和決策執行三個方面，但是為了更靈敏的、更及時的發現超載的場景并進行擴容，需要自動降級、秒級擴容、單機壓測qps預估功能的保證。另外還有一些功能性的開發，如業務算法配置參數分離、排程大盤監控、烽火台規則運作平台等的支援。最底層的更加離不開容器化的全量部署 ，使得加減機器，快速部署環境成為了可能。
智能排程的算法是在其他子產品都具備的情況下，才能夠穩定有效的運作。是以在介紹智能排程算法之前，先對算法依賴的每個部分進行簡要的介紹如下。
KMonitor是基于optsdb on druid架構的監控系統。支援從Hippo,amon和Log檔案收集監控資料,并可以在grafana上展示或是通過api接口擷取。 TPP排程系統對Kmonitor的使用包括兩部分:通過tpp的log檔案注冊tpp服務的狀态資訊和排程系統從Kmonitor擷取狀态資訊。 目前注冊的狀态資訊包括容器内的cpu/load等系統狀态和每個場景的pv/latency等業務資訊. 通過使用kmonitor提供的多租戶功能, tpp獨立部署了一套租戶系統, 可以支援資訊彙報延遲不超過5s。排程系統擷取這部分資訊後作為計算的資料輸入。
2017年TPP全部叢集運作在Fiber之上，Fiber是在Hippo機器排程系統的一種封裝，其優勢在于能夠将容器的加載、預熱、上線維持在秒級别，而之前直接從Hippo排程機器，加載方案到正常上線需要10分鐘級别。Fiber本身可以配置buffer，每個一定時間将重要的P1場景加載到buffer中的機器上并定時預熱，通過實踐驗證，在提前有buffer預熱的情況下，從智能擴縮容發出擴容指令開始到機器完全挂上去，能夠在10s内完成。
自動降級是2017年TPP雙11的另外一個創新，其主要的思想是判斷當天叢集總的逾時QPS的比例，如果從全局上統計超過使用者設定的門檻值（如3秒鐘區間統計值超過1%），則将出現逾時的容器集體降級。 所謂降級是指方案的一個新的配置，進階别的運作配置保證更好的展示效果，但是單容器能夠服務的QPS較少；低級别的運作配置會使得展示效果打折扣，但是單容器能夠服務的QPS會更多。舉個例子：首頁猜你喜歡L0的配置是通路RTP，利用深度模型進行item的打分，L1則會關閉RTP通路的開關，進而節省CPU，服務更多的QPS，但是可能從業務上來看，展示的item的相關度會打折扣。
自動降級主要用在如下兩個方面：1. 雙11在0點峰值附近的時候，整個叢集機器嚴重不足，可以通過集體配置降級，保證全部使用者能夠正常通路，即使服務品質稍有下滑，但是和逾時相比，是可以忍受的； 2. 是和智能擴縮容相關的。智能擴縮容的出現，使得一天中叢集的機器數目會發生更頻繁的變化，而JVM容器本身存在預熱的問題，當一個新的容器挂載到線上知道100%預熱完成之前，就會出現嚴重的逾時。有了自動降級之後，可以通過砍掉一部分二方服務的rt，使得即使預熱的QPS也不會嚴重逾時，進而消減了擴容瞬間對線上QPS的影響。當然不同的場景其預熱過程要詳細的優化，有CPU密集的、IO密集的、以及緩存型的，其預熱過程得有所不同。
場景壓測在每天夜裡定時執行，擷取場景的單機性能。對于具備降級配置的場景，會壓測每一套降級配置的性能。針對每個場景，當場景owner将場景加入日常壓測清單，自動壓測程式将會于每晚淩晨0:00調用API，獲得壓測清單，建立待壓測場景的影子場景，申請壓測發生容器，調用壓測接口逐漸增加qps，直至容器超出負載（系統load，cpu，業務異常率等）。目前CPU上限為100%，異常率的上限為5%。 該運作結果就可以作為TPP智能排程的輸入，作為每個場景在某個特定的級别（L0、L1、L2或者L3）的單機服務能力。壓測結果如下所示：
在上述子產品穩定保障下，智能排程算法形式化為資源排程優化問題：
利用每個叢集目前的運作狀态計算每個場景需要的機器數目 $N_i$, 需要加機器為正值，需要縮容為負值。
确定每個機器的擴縮容的數目，尋找最優解，優化目标為，即使得CPU盡可能的均衡并接近叢集目标負載，如OptimalCPU=40%為叢集最佳狀态：
限制條件為：
所有的Ci+Ni總和小于叢集總的機器數
有多個不同的場景，每個場景的優先級為P1到P3之一，每個場景都可能工作在L0到L3，所有工作在非L0的都可以被降級。
先滿足高優先級場景，再滿足低優先級場景。
所有P1場景的擴容需求必須要被滿足。
智能排程算法核心要解的問題是：盡可能的通過給不同的場景加減機器，改變所有場景的CPU的值，将所有叢集的CPU調節到目标CPU（人工設定優化目标）的周圍， 并且盡可能的均衡。如兩個場景，目标CPU為40%。将其調節為38%、42%，肯定要比10%、70%要好。這個均衡的程度是由優化目标來決定的。
在最開始算法考察的過程中，還考慮過别的一些算法，比如分層的背包方法，包的容量是“總的機器池子的quota”，每個叢集是要放在書包裡面的物品，放到裡面會消耗一定的機器，消耗了背包的“空間”， 但是同時加了機器，CPU降低會帶來一定的增益：優化目标變小。暴力搜尋也是可以在有限時間解這個問題的。
但是我們最後還是采用了一種樸素的做法，盡可能的模拟人進行排程的方法，對需要機器的場景排個序，用不重要場景的機器拿出機器去補充重要P1場景。可以根據人為的經驗去靈活調整擴縮容次序，因為在實際運作過程中，可解釋性永遠比最優化更重要，你給一個場景加了機器，減了機器，需要給人家解釋清楚。而不是說，給某個叢集拿掉10台機器是因為叢集總的負載均衡度上升了0.01。
更加詳細的介紹智能排程的算法如下。我們直接計算每一個叢集CPU到達最優解需要的機器數Ni, 如果Ni>0，表示需要擴充機器降低CPU到目标CPU，如果Ni < 0, 表示可以拿掉機器提高場景CPU到目标CPU。有如下的幾種情形：
1. 如果所有Ni的和 < 空閑機器, 即叢集空閑的機器數目加上可以縮出來機器大于所有要機器的數目，那所有的需要擴容的都可以到達目标CPU，所有縮容的直接拿掉機器CPU升高到目标CPU，也就是優化目标達到最小值0。
2. 如果所有Ni的和 > 空閑機器, 即擴容需求不能得到完全滿足。這時排程算法會選擇滿足限制條件，并且使得優化目标函數變化最小的梯度方向進行變動。 具體方法是：将所有的非P1場景通過降級或者提高目标CPU水位，使其需要的機器變少，甚至可以拿出機器。然後進行如下疊代：每次選擇能夠拿出機器最多的場景，将其機器加到需要機器最少、優先級最高的場景上，使其CPU達到目标CPU。然後将擴容被滿足的場景從list中移除。重複如上步驟，直到所有能夠拿出的機器被用完。“優化目标函數變化最小的梯度”是這樣展現的：盡可能少的降級非P1或者提高非P1場景的水位，盡可能多的滿足P1場景。
3. 第2步可能有兩種結果，所有P1的擴容需求被滿足，算法有解。否則算法無解，優化目标也沒有指導意義了，隻能盡可能的滿足部分P1, 不能滿足的P1隻能被降級。這種無解的情況隻有在大促次峰值附近出現過極少數時間。
上述算法的複雜度為O（m） , m 為被排程的叢集的個數，量級為1000，是以每次都能很快得出近似最優解，計算開銷很小。
除了上述的尋找最優值的算法，智能排程算法還有兩個關鍵子產品需要介紹：收斂邏輯和Ni的計算。
智能排程算法運作的控制邏輯是，設定疊代間隔，如每隔5秒進行一次疊代。每一輪疊代中，拿到場景實時的狀态資訊，場景“過載”了給擴容，場景“空載”了給縮容，不論是擴容還是縮容，在擴的過程中，要時刻監控關鍵名額是否到了目标區域，進而結束本輪疊代。這類控制邏輯，最重要的是要保證是收斂的，即不論怎麼調整，最終會較快達到穩态； 同時，不論系統何時、何種程度偏離穩态，都是可以自己重新恢複到穩态。
線上實驗表明，目前最可靠的收斂方式是為叢集設定穩态區間。如設定的區間為[20%,40%]， 如果cpu超出穩态區間，大于40%，則加機器，等到下一輪疊代，判斷cpu是否在穩定區間，如果是則停止調節；如果加機器加過頭了，cpu跌出了20%， 則減機器，讓cpu回升，經過多輪疊代，最終達到穩态。理論上，穩态區間設定越大，收斂的速度會越快，基本不會出現擴容擴過頭的情況，在比較好的計算所需機器的算法支援下，一次就可以收斂。但是過寬的穩态區間會使得資源使用率較低，有可能叢集是在下線水位運作。
另一個極端就是穩态區間設定成為一個值，指哪打哪，比如目标cpu設定成為30%，如果CPU大于30%，就會擴容，如果CPU小于30%，縮容。這樣的好處是，叢集CPU肯定在30%附近波動，平均下來，叢集CPU達到目标值30%，但是這樣的缺點就是頻繁的增減機器，增加機器并不是沒有開銷，運作JVM的容器存在預熱問題，冷機器上線會增加異常QPS的比例，是得不償失的。經過實際運作，我們標明optimalCPUDrift=2， 也就是在目标CPU的+2和-2的區間都是穩态，既能使得叢集CPU達到目标值，同時又能避免頻繁擴縮容。
Ni計算公式
Ni表示一個場景機器數目的變動，Ni>0表示需要機器，Ni<0表示可以被縮容。Ni有兩種計算方式：
第一種計算方法是根據單機壓測的QPS來計算，非常直覺，因為單機QPS是通過線下不停的增加流量，一直到該單機CPU到達100%或者異常QPS超過5%，但在真實使用的過程中發現，線下的壓測資料通常和線上真實能夠服務的qps不太一樣，主要原因有兩個：一個是線上有可能是多個場景公用一個實體機，互相影響；另外一個是線下壓測隻能是天級别的資料，但是有可能當一個場景發生了方案更改，其服務能力也會發生變化，而壓測資料還是曆史值。
第二種計算方法采用的是目前實時的結果，較為準确。唯一的缺點的是會受到噪音CPU的影響，如剛擴上去的機器，由于預熱的原因，CPU會瞬間飙高，等完全預熱了之後CPU才會降下來，這種問題的解決方法剛加上去的機器在預熱期間不輸出CPU的資料，免得影響Ni的計算。
擴容的觸發條件
有了計算Ni的方法了之後，下一步需要關注的就是何時觸發擴容，然後計算Ni。 目前智能排程算法的觸發條件有兩個：
1、當目前1分鐘的平均CPU不在穩态區間中。 此時：
2. 當一個場景降級的QPS比例大于一定門檻值，線上取5%。由于降級觸發的擴容，其：
最終的：
其他功能
負載均衡： 保證一個場景中多個容器之間的負載均衡，使得排程算法能夠工作在場景粒度，而不是容器粒度，減少需要排程的規模。
監控大盤：監控網頁、方面及時掌握智能排程的進展
規則運作保障：通過crontab功能定時排程智能擴縮容的運作。
擴容原因透出：每次擴容都有相應的原因，供場景owner檢視。
紅包雨：對于QPS增長特别快，幾乎直線拉升的增長受限于擴容的速度。如果預先能夠知道活動發生的時間區間，可以通過提前錄入預估QPS，智能排程算法提前給其擴容。
除了大盤，還進行了機器的熱點和排程可視化，能夠在雙11當天更方面的監控叢集的運作狀态。下圖中一個格子表示一個叢集，顔色表示CPU水位，大小表示擁有機器數目。當有場景被擴容或者縮容時也會可視化出來。
下圖取了10月1日（智能排程上線前）和11月6日（智能排程上線後）24小時内首頁猜你喜歡的機器數、CPU利用情況對比（其中機器數和QPS做了歸一化處理）：
從上圖中可以看出，在運作了智能排程(紅色線)之後，CPU使用率從原來持續低于15%，平均CPU使用率8%提高到平均27%。值得指出的是，為了保護場景，智能排程設定了最小機器數的保證，數目為max {3台機器，過去24小時機器平均值}，是以在淩晨1點到淩晨7點，即使QPS變為個位數， 場景機器沒有被完全拿空。如果有離線線上混部的需求，可以把淩晨的機器保護去掉，讓這些機器回歸機器池子，部署機器學習訓練模型。
同時我們可以看出來，運作了智能排程之後，日常的機器數是原來固定配置設定機器的1/3，極大的節省了機器資源。
智能排程和固定機器相比，缺點就是會在一天中，比較頻繁的發生機器數目的變動，但是通過圖(d)的統計，可以看出逾時qps能夠持續小于千分之2，處在可以接受的範圍内。
在上圖中，我們選擇了四個場景，記錄了它們在雙11當天24小時的CPU、叢集機器數、QPS（對數刻度）、逾時QPS比例的變化圖。從上面第二個子圖可以看出來四個場景明顯的錯峰資源排程，藍色線在10點需要機器，但是後面機器貢獻出來提供給綠色的場景來使用。此外，從第二張子圖可以看出來，在雙11當天有明顯的脈沖流量，自動擴縮容保證了這些脈沖流量，同時保證了逾時qps低于千分之6（如子圖4）。值得指出的是，2017年為自動擴縮容運作的第一年，為了保證11日當天的成交額，沒有将CPU水位調到很高，後來微調了叢集的CPU水位，在所有P1水位在35%時，還能保證所有P1場景降級率均低于2%。
智能排程系統作為集團雙11推薦場景的重要基礎設施保障，在2個月的時間中工程、測試團隊聯合算法同學完成了從架構設計、算法調試、功能上線測試到雙11當天百萬級的QPS的資源排程。從雙11淩晨00：15分接手機器排程開始，智能排程系統在24小時中做到了對上層應用開發同學的透明化，保證他們能夠投入最大精力沖成交，完全不用擔憂資源不夠的問題。
智能排程系統全程無需人工幹預和拆借機器，完成造勢場景，導購場景和購後場景的錯峰資源排程，P1場景資源使用率保持在 30% ，非P1資源使用率保持在50%, 所有P1場景降級率低于2%。即使大促當天各種突發和變動的流量，逾時率仍能夠控制在千分之六以内，實作了讓工程和算法同學"零點高峰瞪大眼睛認真看，雙11當天買買買" 的願望。
現在智能擴縮容在定時脈沖QPS增加（如雙11當天0點的QPS，定時的紅包雨），以及日常的QPS連續光滑變化的情況下有解 （定時脈沖QPS通過場景owner提前錄入活動預估QPS和持續時間，算法提前擴容），但是在不定時的脈沖QPS增加的情況下不能很好的解決，主要受限于機器的加載速度和預熱速度，當瞬間需要大量機器時候，提前預熱在buffer池子中的機器會被掏空，相當于發生cache miss，得從hippo拿hippo機器，擴容速度跟不上。如何能夠在有限buffer池子的情況下，盡可能的減少cache miss是未來的一個優化點。
智能擴縮容在擴較多機器的瞬間，雖然通過自動降級的解決方案，能夠消除逾時QPS，但是會有一定程度的降級QPS，如何能夠将智能擴縮容和RR層的流量排程結合起來，更穩妥的進行預熱，保證更加平滑的擴容，同時保證預熱速度是未來的一個優化的方向。
感謝桂南、天民、野蔓、永叔對項目的大力支援；
感謝TPP各場景的算法同學在智能排程運作過程中提出的寶貴的改進和指導意見；
感謝項目所有參與人員: 劍豪，玉景，巫宸，麒翔，七炎，千鹍，唯勤，林謙，劍持，成都，振之，曲竹，聿劍，畫帆，薦軒
原文釋出時間為：2017-12-19
本文作者：TPP+猜你喜歡團隊