随着云计算概念的深入人心，虚拟化技术应用越来越广泛。虚机要运行在服务器上，如何部署才能节约资源、降低成本、提高物理硬件的利用率，成为贯穿整个虚拟化过程的重要话题。虚机拥有大大小小各种规格，涉及到网络带宽、硬盘、处理器、内存、驱动、互斥属性等物理信息，其部署过程的复杂度可归类为典型的多维度装箱问题。
装箱算法介绍
装箱问题也叫背包问题，为简便，以一维经典装箱问题为例，其数学模型可描述如下：S=（S1,S2,..Sn）,其中0< Si ≤ 1, 称之为第i个物体的体积（或重量），1≤i≤n,现有n个容积（或载重量）为1 的箱子，要求如何设法将S1,S2,..Sn放入尽可能少的箱中。简单来说，就是把小货物往大箱子里装，要如何才能装得多。
装箱问题是典型的NP(Non-Deterministic Polynomial, 非确定多项式)问题,即在多项式时间内无法精确求解,一般采用近似算法，即启发式算法，这样可以迅速得到满意解，但不一定是最优解。常见的算法包括NF(Next Fit)近似算法，FF(First Fit)近似算法，FFD（First Fit Decreasing）近似算法，BF(best Fit),BFD(Best Fit Deceasing)等。
其中下次适应算法(NF)是始终维持一个当前打开的箱子，对于每一个要装入的物品，检查该物品是否可以放入当前打开的箱子，如果无法装入，则打开一个空箱子，装入该物品，以该箱子作为当前的箱子，由于每个物品在装入时，只有当前打开的箱子和空箱可以选择，这必然造成装箱的效率低下。
首次适应算法(FF)：针对下次适应算法的缺陷，首次适应算法FF处理当前物品的时候，检查所有非空箱子，找到第一个能够放下当前物品的箱子并将该物品放入，否则则开启新的箱子。
最佳适应算法(BF)：与首次适应算法类似，唯一的区别是当物品装箱时，不是直接装在第一个可装入的箱子中，而是装入在最适合该物体的箱子中，如果没有该箱子，则开启空箱。
首次适应算法和最佳适应算法有一个缺陷，即由于物品没有实现排序，则可能由于先装入小的物品，使大的物品在后来放入时无法装入，只得开启新的箱子，造成了空间的浪费,因此才有了这两种算法的改进算法。
降序首次适应算法(FFD)：先对物品按降序排序，再按照首次适应算法进行装箱。
降序最佳适应算法(BFD)：先对物品按降序排序，再按照最佳适应算法进行装箱。
虚机部署应用装箱算法的对比分析
类比虚机部署，由于涉及到多种因素，是更为复杂的多维装箱问题。如果简单的采用NF、FF或FFD算法，会导致某类虚机集中在个别刀片的情况，对可靠性造成不利影响。同时由于没有排序，先装入小的虚机，使大的虚机在后来放入时无法装入，只得占用新的服务器，造成了资源浪费。
经过分析比较，本虚机装配工具采用的优化算法是降序最佳适应算法(BFD)，即先对虚机按照类别分别进行带宽、物理核、数量降序排序，再检查所有非空的服务器，通过多维度的资源比较，找到第一个能够放下当前虚机类型的服务器，并部署该虚机类型的第一个虚机，否则就部署在新的服务器上。接着检查下一个服务器是否能部署该虚机规格的第二个虚机，依次类推，直至此类虚机全部部署完成，再依次部署下一个虚机类型的虚机。直至全部虚机部署完成。经过这种优化算法后，虚机的装载率可以由通常的85%达到90~95%左右。
下面来看看实战例子，比如，有如下虚机需要部署在刀片服务器上，刀片服务器规格为：双路14核处理器、192G内存、2*600G系统盘、10G网口。
在没有考虑排序的情况下，下图是可能出现的虚机部署结果，由于先部署的小的虚机（SMP），使大的虚机在后来放入时无法装入，只得新增刀片服务器，虚机部署总共占用了13块刀片：
(79).jpg)
虚机部署涉及多个维度，如虚机的物理核数、内存大小、硬盘大小、带宽等，按哪个维度进行排序，就需要针对具体的场景进行分析比较。如按物理核数来排序，占用11块刀片；按内存排序，占用13块；按带宽排序，占用10块；按虚机数量排序，占用11块。
可见，对于多维装箱，要找到最优的排序算法还是有一定难度的，各种维度相互交织，应该针对具体的场景进行分析比较。通过多次尝试可以看到，影响结果的关键就是虚机排序，第一优先级是应保证大虚机规格优先部署，其次应考虑到备份方式，因为N+1的负荷分担备份方式，需要虚机部署时考虑互斥，互斥的虚机每个刀片只能部署一个，所以如果刀片被先装入的非互斥虚机占满，会导致互斥的虚机在后来放入时无法装入，造成刀片服务器数量增加。
虚机部署工具
因此本部署工具基于上述对比考虑，对虚机排序做了优化，优先部署规格较大、数量较多的互斥虚机，如上面的部署实例，先按备份方式进行降序排序，再按虚机核数量排序，就能保证在相同虚机核数的情况下，要求互斥的虚机优先部署。排序结果如下：
虚机部署结果如下，可见只占用了8块刀片，占用资源最少！相对之前的13块刀片，采用降序最佳适应算法节约了38%！
(70).jpg)
虚机优化部署的关键就是要找到影响虚机部署的最关键的瓶颈维度。按照瓶颈维度进行排序，一般就能获得较好的效果。由于服务器的规格限制，针对不同的场景，瓶颈维度可能会改变，一般需要进行多次尝试才能发现。本装配工具采用降序最佳适应算法，不仅提高了资源的利用率，在部署过程中还考虑了NUMA、互斥、带宽等约束条件，确保了虚机均衡分配，保证了设备可靠性。而且为了方便调整也支持手工部署，工具具有普适性。虚机在服务器中的部署情况，包括CPU核的占用序号，内存大小，硬盘大小等，都可以直观的显示出来。
中兴通讯利用虚机部署工具这一利器，解决了多维度装箱问题，已广泛应用于售前配置、售后设备开通、自动编排以及运营维护节能减排等，使得云化产品落到实地，用最少的资源池为用户带来最大的收益。可以预见，随着云化产品的不断扩张，自动部署工具将发挥更大的作用。 
