隨著云計(jì)算概念的深入人心，虛擬化技術(shù)應(yīng)用越來(lái)越廣泛。虛機(jī)要運(yùn)行在服務(wù)器上，如何部署才能節(jié)約資源、降低成本、提高物理硬件的利用率，成為貫穿整個(gè)虛擬化過(guò)程的重要話題。虛機(jī)擁有大大小小各種規(guī)格，涉及到網(wǎng)絡(luò)帶寬、硬盤(pán)、處理器、內(nèi)存、驅(qū)動(dòng)、互斥屬性等物理信息，其部署過(guò)程的復(fù)雜度可歸類(lèi)為典型的多維度裝箱問(wèn)題。

裝箱算法介紹

裝箱問(wèn)題也叫背包問(wèn)題，為簡(jiǎn)便，以一維經(jīng)典裝箱問(wèn)題為例，其數(shù)學(xué)模型可描述如下：S=（S1,S2,..Sn）,其中0< Si ≤ 1, 稱(chēng)之為第i個(gè)物體的體積（或重量），1≤i≤n,現(xiàn)有n個(gè)容積（或載重量）為1 的箱子，要求如何設(shè)法將S1,S2,..Sn放入盡可能少的箱中。簡(jiǎn)單來(lái)說(shuō)，就是把小貨物往大箱子里裝，要如何才能裝得多。

裝箱問(wèn)題是典型的NP(Non-Deterministic Polynomial, 非確定多項(xiàng)式)問(wèn)題,即在多項(xiàng)式時(shí)間內(nèi)無(wú)法精確求解,一般采用近似算法，即啟發(fā)式算法，這樣可以迅速得到滿意解，但不一定是最優(yōu)解。常見(jiàn)的算法包括NF(Next Fit)近似算法，F(xiàn)F(First Fit)近似算法，F(xiàn)FD（First Fit Decreasing）近似算法，BF(best Fit),BFD(Best Fit Deceasing)等。

其中下次適應(yīng)算法(NF)是始終維持一個(gè)當(dāng)前打開(kāi)的箱子，對(duì)于每一個(gè)要裝入的物品，檢查該物品是否可以放入當(dāng)前打開(kāi)的箱子，如果無(wú)法裝入，則打開(kāi)一個(gè)空箱子，裝入該物品，以該箱子作為當(dāng)前的箱子，由于每個(gè)物品在裝入時(shí)，只有當(dāng)前打開(kāi)的箱子和空箱可以選擇，這必然造成裝箱的效率低下。

首次適應(yīng)算法(FF)：針對(duì)下次適應(yīng)算法的缺陷，首次適應(yīng)算法FF處理當(dāng)前物品的時(shí)候，檢查所有非空箱子，找到第一個(gè)能夠放下當(dāng)前物品的箱子并將該物品放入，否則則開(kāi)啟新的箱子。

最佳適應(yīng)算法(BF)：與首次適應(yīng)算法類(lèi)似，唯一的區(qū)別是當(dāng)物品裝箱時(shí)，不是直接裝在第一個(gè)可裝入的箱子中，而是裝入在最適合該物體的箱子中，如果沒(méi)有該箱子，則開(kāi)啟空箱。

首次適應(yīng)算法和最佳適應(yīng)算法有一個(gè)缺陷，即由于物品沒(méi)有實(shí)現(xiàn)排序，則可能由于先裝入小的物品，使大的物品在后來(lái)放入時(shí)無(wú)法裝入，只得開(kāi)啟新的箱子，造成了空間的浪費(fèi),因此才有了這兩種算法的改進(jìn)算法。

降序首次適應(yīng)算法(FFD)：先對(duì)物品按降序排序，再按照首次適應(yīng)算法進(jìn)行裝箱。

降序最佳適應(yīng)算法(BFD)：先對(duì)物品按降序排序，再按照最佳適應(yīng)算法進(jìn)行裝箱。

虛機(jī)部署應(yīng)用裝箱算法的對(duì)比分析

類(lèi)比虛機(jī)部署，由于涉及到多種因素，是更為復(fù)雜的多維裝箱問(wèn)題。如果簡(jiǎn)單的采用NF、FF或FFD算法，會(huì)導(dǎo)致某類(lèi)虛機(jī)集中在個(gè)別刀片的情況，對(duì)可靠性造成不利影響。同時(shí)由于沒(méi)有排序，先裝入小的虛機(jī)，使大的虛機(jī)在后來(lái)放入時(shí)無(wú)法裝入，只得占用新的服務(wù)器，造成了資源浪費(fèi)。

經(jīng)過(guò)分析比較，本虛機(jī)裝配工具采用的優(yōu)化算法是降序最佳適應(yīng)算法(BFD)，即先對(duì)虛機(jī)按照類(lèi)別分別進(jìn)行帶寬、物理核、數(shù)量降序排序，再檢查所有非空的服務(wù)器，通過(guò)多維度的資源比較，找到第一個(gè)能夠放下當(dāng)前虛機(jī)類(lèi)型的服務(wù)器，并部署該虛機(jī)類(lèi)型的第一個(gè)虛機(jī)，否則就部署在新的服務(wù)器上。接著檢查下一個(gè)服務(wù)器是否能部署該虛機(jī)規(guī)格的第二個(gè)虛機(jī)，依次類(lèi)推，直至此類(lèi)虛機(jī)全部部署完成，再依次部署下一個(gè)虛機(jī)類(lèi)型的虛機(jī)。直至全部虛機(jī)部署完成。經(jīng)過(guò)這種優(yōu)化算法后，虛機(jī)的裝載率可以由通常的85%達(dá)到90~95%左右。

下面來(lái)看看實(shí)戰(zhàn)例子，比如，有如下虛機(jī)需要部署在刀片服務(wù)器上，刀片服務(wù)器規(guī)格為：雙路14核處理器、192G內(nèi)存、2*600G系統(tǒng)盤(pán)、10G網(wǎng)口。

在沒(méi)有考慮排序的情況下，下圖是可能出現(xiàn)的虛機(jī)部署結(jié)果，由于先部署的小的虛機(jī)（SMP），使大的虛機(jī)在后來(lái)放入時(shí)無(wú)法裝入，只得新增刀片服務(wù)器，虛機(jī)部署總共占用了13塊刀片：

虛機(jī)部署涉及多個(gè)維度，如虛機(jī)的物理核數(shù)、內(nèi)存大小、硬盤(pán)大小、帶寬等，按哪個(gè)維度進(jìn)行排序，就需要針對(duì)具體的場(chǎng)景進(jìn)行分析比較。如按物理核數(shù)來(lái)排序，占用11塊刀片；按內(nèi)存排序，占用13塊；按帶寬排序，占用10塊；按虛機(jī)數(shù)量排序，占用11塊。

可見(jiàn)，對(duì)于多維裝箱，要找到最優(yōu)的排序算法還是有一定難度的，各種維度相互交織，應(yīng)該針對(duì)具體的場(chǎng)景進(jìn)行分析比較。通過(guò)多次嘗試可以看到，影響結(jié)果的關(guān)鍵就是虛機(jī)排序，第一優(yōu)先級(jí)是應(yīng)保證大虛機(jī)規(guī)格優(yōu)先部署，其次應(yīng)考慮到備份方式，因?yàn)镹+1的負(fù)荷分擔(dān)備份方式，需要虛機(jī)部署時(shí)考慮互斥，互斥的虛機(jī)每個(gè)刀片只能部署一個(gè)，所以如果刀片被先裝入的非互斥虛機(jī)占滿，會(huì)導(dǎo)致互斥的虛機(jī)在后來(lái)放入時(shí)無(wú)法裝入，造成刀片服務(wù)器數(shù)量增加。

虛機(jī)部署工具

因此本部署工具基于上述對(duì)比考慮，對(duì)虛機(jī)排序做了優(yōu)化，優(yōu)先部署規(guī)格較大、數(shù)量較多的互斥虛機(jī)，如上面的部署實(shí)例，先按備份方式進(jìn)行降序排序，再按虛機(jī)核數(shù)量排序，就能保證在相同虛機(jī)核數(shù)的情況下，要求互斥的虛機(jī)優(yōu)先部署。排序結(jié)果如下：

虛機(jī)部署結(jié)果如下，可見(jiàn)只占用了8塊刀片，占用資源最少！相對(duì)之前的13塊刀片，采用降序最佳適應(yīng)算法節(jié)約了38%！

虛機(jī)優(yōu)化部署的關(guān)鍵就是要找到影響虛機(jī)部署的最關(guān)鍵的瓶頸維度。按照瓶頸維度進(jìn)行排序，一般就能獲得較好的效果。由于服務(wù)器的規(guī)格限制，針對(duì)不同的場(chǎng)景，瓶頸維度可能會(huì)改變，一般需要進(jìn)行多次嘗試才能發(fā)現(xiàn)。本裝配工具采用降序最佳適應(yīng)算法，不僅提高了資源的利用率，在部署過(guò)程中還考慮了NUMA、互斥、帶寬等約束條件，確保了虛機(jī)均衡分配，保證了設(shè)備可靠性。而且為了方便調(diào)整也支持手工部署，工具具有普適性。虛機(jī)在服務(wù)器中的部署情況，包括CPU核的占用序號(hào)，內(nèi)存大小，硬盤(pán)大小等，都可以直觀的顯示出來(lái)。

中興通訊利用虛機(jī)部署工具這一利器，解決了多維度裝箱問(wèn)題，已廣泛應(yīng)用于售前配置、售后設(shè)備開(kāi)通、自動(dòng)編排以及運(yùn)營(yíng)維護(hù)節(jié)能減排等，使得云化產(chǎn)品落到實(shí)地，用最少的資源池為用戶帶來(lái)最大的收益�？梢灶A(yù)見(jiàn)，隨著云化產(chǎn)品的不斷擴(kuò)張，自動(dòng)部署工具將發(fā)揮更大的作用。