C114齐乐娱乐网: 门户(微博 微信) 论坛(微博) 人才(微博) 百科 | C114客户端 | English | IDC联盟 与风网
新闻 - 设备商新闻 - 中兴 - 正文 运营商投稿当日通信资讯

装箱算法在虚机部署中的应用实践

http://www.c114.com.cn ( 2017/9/13 09:22 )
随着云计算概念的深入人心,虚拟化技术应用越来越广泛。虚机要运行在服务器上,如何部署才能节约资源、降低成本、提高物理硬件的利用率,成为贯穿整个虚拟化过程的重要话题。虚机拥有大大小小各种规格,涉及到网络带宽、硬盘、处理器、内存、驱动、互斥属性等物理信息,其部署过程的复杂度可归类为典型的多维度装箱问题。 装箱算法介绍 装箱问题也叫背包问题,为简便,以一维经典装箱问题为例,其数学模型可描述如下: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块刀片: 虚机部署涉及多个维度,如虚机的物理核数、内存大小、硬盘大小、带宽等,按哪个维度进行排序,就需要针对具体的场景进行分析比较。如按物理核数来排序,占用11块刀片;按内存排序,占用13块;按带宽排序,占用10块;按虚机数量排序,占用11块。 可见,对于多维装箱,要找到最优的排序算法还是有一定难度的,各种维度相互交织,应该针对具体的场景进行分析比较。通过多次尝试可以看到,影响结果的关键就是虚机排序,第一优先级是应保证大虚机规格优先部署,其次应考虑到备份方式,因为N+1的负荷分担备份方式,需要虚机部署时考虑互斥,互斥的虚机每个刀片只能部署一个,所以如果刀片被先装入的非互斥虚机占满,会导致互斥的虚机在后来放入时无法装入,造成刀片服务器数量增加。 虚机部署工具 因此本部署工具基于上述对比考虑,对虚机排序做了优化,优先部署规格较大、数量较多的互斥虚机,如上面的部署实例,先按备份方式进行降序排序,再按虚机核数量排序,就能保证在相同虚机核数的情况下,要求互斥的虚机优先部署。排序结果如下: 虚机部署结果如下,可见只占用了8块刀片,占用资源最少!相对之前的13块刀片,采用降序最佳适应算法节约了38%! 虚机优化部署的关键就是要找到影响虚机部署的最关键的瓶颈维度。按照瓶颈维度进行排序,一般就能获得较好的效果。由于服务器的规格限制,针对不同的场景,瓶颈维度可能会改变,一般需要进行多次尝试才能发现。本装配工具采用降序最佳适应算法,不仅提高了资源的利用率,在部署过程中还考虑了NUMA、互斥、带宽等约束条件,确保了虚机均衡分配,保证了设备可靠性。而且为了方便调整也支持手工部署,工具具有普适性。虚机在服务器中的部署情况,包括CPU核的占用序号,内存大小,硬盘大小等,都可以直观的显示出来。 中兴通讯利用虚机部署工具这一利器,解决了多维度装箱问题,已广泛应用于售前配置、售后设备开通、自动编排以及运营维护节能减排等,使得云化产品落到实地,用最少的资源池为用户带来最大的收益。可以预见,随着云化产品的不断扩张,自动部署工具将发挥更大的作用。
作者:司远潮   来源:C114齐乐娱乐网 版权说明:凡注明来源为“C114齐乐娱乐网”的文章皆属C114版权所有,除与C114签署内容授权协议的单位外,其他单位未经允许禁止转载、摘编,违者必究。如需使用,请联系021-54451141。其中编译类仅出于传递更多信息之目的,系C114对海外相关站点最新信息的翻译稿,仅供参考,不代表证实其描述或赞同其观点,投资者据此操作,风险自担;翻译质量问题请指正
支持作者观点 轻松参与 VS 表达立场 反对作者观点
合作伙伴: 一诺 华工
Copyright©1999-2017 c114 All Rights Reserved
上海荧通网络信息技术有限公司版权所有
南方广告业务部: 021-54451141,54451142 E-mail:c114@c114.net
北方广告业务部: 010-63533177,63533977 E-mail:shixinqi@c114.net.cn
编辑部联系: 021-54451141,54451142 E-mail:editor@c114.net.cn
服务热线: 021-54451141,54451142
沪ICP备12002291号
齐乐国际娱乐老虎机