基于运行阶段特征的虚拟机实时迁移技术

邹庆欣，郝志宇，云晓春1,



基于运行阶段特征的虚拟机实时迁移技术

邹庆欣1,2,3，郝志宇3，云晓春1,3

(1. 中国科学院计算技术研究所，北京 100190；2. 中国科学院大学，北京100049；3. 中国科学院信息工程研究所，北京100193)

针对预拷贝算法在起始、迭代、结尾3个阶段所表现出的不同特点，提出了基于运行阶段特征的虚拟机实时迁移技术(LMCOS, live migration based on the characteristics of the operation stages)。起始阶段引入比对初始内存页的变量传输技术以避免未改变内存部分的传输；迭代阶段引入计数排序传输方法以减少内存页的重传；结尾阶段引入调减虚拟机CPU时间片的策略以缩短停机时间。与预拷贝算法相比，LMCOS使停机时间平均减少53%，总迁移时间平均减少65%。

实时迁移；预拷贝；运行阶段特征；虚拟机

1 引言

步入云计算、大数据时代，虚拟化技术得到了前所未有的应用。虚拟化技术使拥有全部硬件特征的虚拟机在彼此隔离的情况下能够同时在一台物理机器上运行，极大地增加了物理资源的利用率。虚拟机是虚拟化技术一个最直接而且集中的体现。

在虚拟机诸多技术中，实时迁移技术无疑是一项卓越而实用的服务。虚拟机实时迁移技术在保证虚拟机工作负载正常运行的情况下，使其在不同的物理主机之间可以自由地穿梭。虚拟机实时迁移有广域网迁移和局域迁移之分。在广域网迁移中不仅要迁移虚拟机内存，还要迁移虚拟机的磁盘镜像文件及网络状态等。而局域网迁移，则可以不必迁移虚拟机磁盘镜像文件等，完全可以利用NFS等服务采用共享的方式。本文主要研究局域网迁移中的内存迁移。

在虚拟机局域网内存迁移技术中，预拷贝算法是最常用，也是最实用的算法之一。对于使用预拷贝算法的虚拟机实时迁移来说，主要有2个衡量指标：总迁移时间和停机时间。顾名思义，总迁移时间是指从源主机上首次发送内存页开始到虚拟机在目标机器上重新启动运行所需的时间；而停机时间的产生则是因为目前的所有实时迁移技术并不能保证完全的实时性，在迁移的过程中都需要有一段虚拟机停顿时间。只有停机时间等于零，才是真正意义上的实时迁移。但是停机时间为零是极其困难的，通常是尽量短而使从虚拟机使用者的角度来看几乎察觉不到。

总迁移时间和停机时间的产生是从源主机到目的主机传输内存页的多少及相关内部算法等共同作用的结果。本文通过深入分析预拷贝算法的工作原理，根据其在不同运行阶段所体现的特征，有针对性地采取相应策略以改进预拷贝算法：在起始阶段引入比对初始内存页的变量传输技术以减少数据的传输量；在迭代阶段引入计数排序技术以减少高频变化内存页的多次传输；在结尾阶段引入调减虚拟机CPU时间片方法以获得更短的停机时间。通过以上基于运行阶段特征技术的运用，使虚拟机在运行不同工作负载的情况下同时减少总迁移时间和停机时间，显著提高了虚拟机实时迁移的性能。

2 相关工作

自文献[1]首次提到虚拟机实时迁移以来，研究人员对这个问题给予了极大关注。尤其是在内存迁移方面，相关研究工作不断进展，并且内存迁移的相关工作也常常对虚拟化相关的其他研究方向产生重大影响。可以说，虚拟机内存实时迁移是虚拟化技术中一个非常重要的基础技术。

在针对内存的虚拟机实时迁移过程中，除了预拷贝算法以外，文献[2]提出了后拷贝算法，与预拷贝方式相反，后拷贝技术首先从源主机端发送CPU状态和虚拟机能够恢复运行的最小工作集到目标主机，然后虚拟机在目标主机端被重启。随后，虚拟机在目标主机端启动运行过程中，其所需的但并不存在于目标主机的内存页从源主机端被请求或被推送过来。与预拷贝方式相比，后拷贝算法减少了总迁移时间，但却增加了停机时间。借鉴于各自的优缺点文献[3]实现了内存混合复制方式的虚拟机实时迁移机制。其依次执行全内存同步，内存位图同步，和脏内存同步3个过程，与预拷贝算法相比，该机制同时降低了停机时间和总迁移时间。

文献[4]基于日志采用检查点/恢复和跟踪/重放的技术提供了快速、透明的虚拟机实时迁移方法。执行轨迹在源主机端被记录，并采用同步算法实现执行轨迹记录数据从源虚拟机到目标虚拟机的传输，直到他们到达一致的状态。该机制能够大幅度地减少迁移的停机时间和网络带宽消费，而且类似于预拷贝算法，传输的不是内存而是日志，因此数据传输量较小，但实现相对比较复杂。

一种基于多线程技术的限制时间的虚拟机实时迁移机制在文献[5]中实现，类似于只采取2轮策略的预拷贝算法，先传输整个内存页，再停机拷贝所有变脏的内存页。所不同的是其采用了2个线程并行传输，第一个线程从头至尾传输所有内存页，同时另一个线程传输变脏的内存页，当第一个线程结束时，遵循时间限制，立刻进入停机阶段。

以上讨论的虚拟机实时迁移方面的工作可以说是对预拷贝机制的有力扩充。而专门针对预拷贝算法的改进工作也有相关的研究。

在文献[6]中，根据每个内存页自身的特点而采用的适应性内存压缩技术被应用在预拷贝机制的虚拟机实时迁移过程中。每一轮中发送的内存页首先在源主机端被压缩，然后再发送到目标主机。目标主机收到后进行解压缩，从而大幅减少了数据传输量。该研究工作中采用16个单词的字典，并根据字典中单词在内存页中出现的次数来区分每个内存页是高单词相似的，还是低单词相似的。对于高单词相似性的内存页采用类似WKdm机制的压缩算法，而对于低单词相似性的则采用类似LZO机制的压缩算法，同时高相似性和低相似性内存页的界限是动态变化的。文献[7]也提出了压缩的方式，所不同的是，采用的比较对象不同，它并不是每个内存页和字典里的单词做比较，而是不同内存页之间做比较，有些内存页是相同的或高相似的，这样的话，选择一个参考页做基础，同时利用游程编码，传输与参考页不同的部分，从而减少数据量的传输，而参考页的选取则采用散列指纹的方法。这2篇文章的工作虽然都采用了多线程的技术以提高算法的效率。但实验结果中总迁移时间的改进程度，大幅地低于总传输的数据量减少的程度，这说明压缩算法很耗时。文献[8]中也采用了压缩的技术，主要侧重于前后两轮同一个内存页的比较，也就是传输后一轮和前一轮不同的部分。不过这种方法，要维护一个缓存来存储上一轮的内存页。但是缓存不能覆盖全部的内存页，而且该算法对第一轮发送的内存页不起作用。文献[9]把虚拟机内存页分成已分配的和未分配的2种，对于未分配的不予传输，但需要依赖虚拟机内存分配机制设计一个代理模块执行内存探索功能。同时对于已经分配的，根据这些内存页之间的相似性，采用游程编码压缩的方式进行传输，起不到压缩作用的则传输原来的页面。总之，上述4篇文章工作过程复杂，本身计算量大。

针对预拷贝算法，文献[10]提出了有序的传输变脏的内存页的思路。但是记录每个内存页的重写率几乎是不可能的，因此把内存页分成组，使用统计的取样方法和内存组对重写率进行近似。当迭代一轮结束的时候，它统计每个内存组变脏的内存页的个数。然后用个数值除以这一轮持续的时间。所得的结果就是内存组的重写率。这种方法有效地减少了停机时间，但算法时间较长，在有些情况下会造成总迁移时间的增加。文献[11]是在文献[8]上做的改进，在原有的压缩上融合了按顺序传输的想法。文献[12]是本课题组提出的计数排序的方法，该方法根据内存页变脏的次数不大于最大迭代轮数的特点，采用时间复杂度为()的计数排序的算法，使内存页根据变脏的次数由低至高传输，同时减少了停机时间和总迁移时间。

文献[13]从调整虚拟机CPU数量的角度来进行预拷贝算法的改进，但得保证虚拟机CPU的数量大于1。文献[14]通过调整虚拟机CPU运行的时间片来改进预拷贝算法，通过降低虚拟机在被迁移过程中的运行性能来达到减少变脏内存页数量的目的。该方法通过比较相邻两轮的内存页变脏率来动态调整CPU时间片缩减的幅度。文献[15]和文献[14]类似，但缩减幅度的动态调整依据为相邻2轮需传输内存页的绝对数量差值，以每5 000个内存页对应5%的增减幅度，但该方法对于每次变化不足5 000页面的低负载场景就不适用了。采用调整虚拟机CPU方式改进预拷贝算法最直接的影响就是会对虚拟机的应用程序产生干扰，从而严重影响虚拟机使用者的用户体验。

3 预拷贝算法及其运行阶段划分

从虚拟机的角度来看，虚拟机的内存是连续的，实际上每个虚拟机内存页被监视器分散地映射到虚拟机所在的物理主机上。预拷贝算法就是保证虚拟机在运行的同时，把映射到物理主机上真实的内存页传送到目的主机。

图1描述了预拷贝算法的执行过程[12]。从图1中可以看到预拷贝算法试图最小化在最后一轮中传输的内存页，以保证停机时间尽可能短。在这个过程中位于源主机上的虚拟机物理内存镜像，通过网络被传输到目的主机，同时源主机持续运行。所以为了保持虚拟机内存状态在源和目标主机之间一致，一些发送到目标主机的内存页，在重新访问修改变脏之后应该被再次发送到目标主机。因此预拷贝算法用一个迭代的机制来不时地检查变脏的内存页并重传它们。在前一轮传送内存页期间，如果有内存页又被修改了，则该内存页会再次被标记为脏，而没有被修改的则会被标记为干净的。实际上，发送前一轮变脏的内存页时，是无法获得内存页在后一轮的状态的，只能尽可能取临近后一轮的状态。如果用1表示变脏的状态，用0表示干净的状态，则内存页的状态如表1所示。

表1 内存页状态

仅仅对10这种组合，预拷贝算法才发送内存页。因为这个内存页被修改过，在可见的将来它不会被再次修改。对于其他3种组合，预拷贝算法不发送内存页。对于11组合来说，内存页过去被修改了，现在再次被修改，没有必要立刻传送这个内存页。对于00组合来说，内存页没有被修改过，并不需要传送它。对于01组合来说，这个内存页过去没有被修改过，但现在已被修改，预拷贝算法会在下一轮做进一步的判断。预拷贝算法将重复这个过程，直到一轮中变脏的内存页数小于一个预设的阈值，或迭代过程达到最大轮数或最大数据传输量，这一轮迭代通常成为临界轮。在传输完临界轮变脏的内存页以后，虚拟机将要被暂停并进入最后一轮。

根据预拷贝算法运行过程中不同轮次所表现出来的运行特征，可以把预拷贝算法运行过程分为3个阶段。第1轮和第2轮称为起始阶段，在这一阶段会有较多的内存页被发送到目的主机包括未使用的和变脏率较低的内存页，主要是因为第1轮所有内存页都标记为脏的状态，引起第1轮传输的内存页相对较多，传输时间相对较长，间接地引起第2轮也发送较多的内存页。第2轮和临界轮之间的中间轮称为迭代阶段，这一阶段内存页重复变脏相对频繁，而且不是像第一轮那样主观上标记为脏的状态，而是客观上由于内存更改而标记为脏的。把临界轮和最后一轮称为结尾阶段，主要是两轮都和停机时间有关，临界轮的状况关系到最后一轮传送内存页的多少，而最后一轮发送内存页的多少直接影响到停机时间的长短。

4 LMCOS算法设计

预拷贝算法分成不同的阶段后，由于每一阶段运行过程中，分别具有各自阶段的鲜明运行特征，如果不去考虑不同阶段不同运行特征对算法性能产生的影响，而是始终采用同一种方法去处理，必然会影响整体算法的性能，从而导致针对某一阶段，效果非常好的技术方法，到了另一阶段性能就会严重下降，甚至产生负面的影响。而这正是目前绝大多数相关研究工作的处理方式。鉴于此，本文提出了基于运行阶段特征的虚拟机实时迁移技术LMCOS。在不同运行阶段，根据其运行特征，引入不同的处理技术，以达到不同阶段迁移性能的局部最大化效应，最终获得更优异的整体迁移性能。下面将详细介绍LMCOS所引入的技术方法。

4.1 初始阶段:引入比对初始内存页的变量传输技术

预拷贝算法的第一轮，所有内存页都被标记为脏的状态，在虚拟机创建之初，并为其分配内存之前的任何时刻，虚拟机管理器通常会把要分配给虚拟机的内存进行初始化，使每一个内存页相同。而且每一个内存页的每个字节也相同。例如通过分析虚拟化平台Xen-4.2.2的源代码，发现其利用alloc_domheap_pages函数为虚拟机分配内存页之前，就已经利用init_domheap_pages函数对内存进行了初始化工作，该函数里面使用零字节，初始化每个内存页，进而初始化要分配给虚拟机的所有内存页。本文称像Xen-4.2.2虚拟化平台这样经过初始化的内存页为初始内存页，这样的字节为初始字节。换句话说，在Xen-4.2.2虚拟化平台上，初始内存页对应全零页面。

随后在虚拟机引导操作系统并启动后，初始内存页将被改动。尽管初始内存页被改动，但其内部死角仍然有可能存在连续的初始字节。有大量初始内存页和改动很小的内存页是初始阶段最显著的特征，虚拟机内存其他方面的数据相似性因操作系统和应用程序的不同，而有一定的变化。在传送一个虚拟机内存页之前，可以先跟初始内存页进行比较，只传送与初始内存页不同的部分，而相同的部分则没有必要传输。

图2给出比对初始内存页进行变量传输的过程，一对括号表示一个字节，括号内是该字节的数值。同时一个字节最高位用1即数值128表示相同的部分，用0表示不同的部分。低7位则表示具体多长。同时做一次最基本的比较为4个字节。在Xen-4.2.2虚拟化平台具体实现过程中，针对“比对”这一环节，采用游程编码进行比较，具体如图3所示。“合成”环节则要与“比对”环节执行相反的过程。

off: 临时变量；pageoff: 偏离字节数；copy, iscopy : 标识符；uint32_t: 无符号32位整型；(uint32_t)ipage: 初始内存页；( uint32_t)cpage: 待传内存页；bytes_skipped : 省略的字节数；complen: 传送数据总长度；runptr : 待传内存页当前位置；LENMASK: 值为((char)127)；nuint: 单内存页所含uint32_t个数；RFLAG: 值为0；SFLAG: 值为(char)128；(char)runlen: 游程长)；runbytes: 游程字节数。 for (off = 0; off ≤ nuint; off++){ if(off < nuint){ if(cpage[off]!=ipage[off]){copy=1；} if(cpage[off]==ipage[off]){copy=0；} }if(off==nuint){copy =!iscopy；}if (runlen!=0){if ( (iscopy!=copy) or (runlen==LENMASK) ){ runbytes =runlen*sizeof(uint32_t)； if(iscopy==1){runlen|=RFLAG；} if(iscopy==0){runlen|=SFLAG；} dest[complen++]=runlen； if (iscopy==1) { pageoff =runptr *sizeof( uint32_t)； 从cpage的pageoff处拷贝runbyte个字节到dest的complen处，之后调整complen使其值增加runbytes字节；} else {bytes_skipped+=runbytes；} runlen=0；runptr=off；}} runlen+=1；iscopy=copy；}if (bytes_skipped== runbytes){complen=1 ；dest[0]=0；}传输complen和dest到目标端

4.2 迭代阶段：引入计数排序传输技术

进入迭代阶段以后，随着轮数增加，比对初始内存页进行变量传输从而减少数据的程度没有初始阶段高，甚至对有的内存页丝毫不起作用，反而带来额外的计算开销。根据迭代阶段有大量重复传输内存页这一特征。结合了先前在文献[12]中所做的贡献，采用时间复杂度为()的计数排序的方法以减少重复传输的内存页，同时还可以抵消“比对初始内存页进行变量传输”失效时所产生的额外计算时间。

由于总体上本文设计的算法是一种综合的算法，所以在这里有必要讨论了这2种算法结合时相互之间的影响。首先进行公式化分析并定义一些变量。

r：平均脏页增长率。

r：平均网络传输速率。

r：平均计数排序速率。

r：平均比对速率。

：非起始阶段非变量内存比例取值0到1。

p：起始阶段非变量内存比例取值0到1。

：计数排序减少的内存比例取值0到1。

：总内存。

t′: 预拷贝算法第轮时间。

t：结合2种算法后第轮所用时间。

基于上述定义，有如下推导：

1=；2=；

3=；t′=；

1=+；

2=r(1−p)+r；

3=++；

t=++

在预拷贝算法不失效的情况下，满足r<r的条件，同时在预拷贝算法的第一轮，全部内存页都被标记为脏的状态，所以有大量内存页被传输，也包括很多未使用的和初始内存页完全相同的内存页，而且第一轮传输的内存页相对后续轮传输的内存页，更改不频繁，所以p相对较大，有p>成立。要使总迁移时间(1+2+…+t)≤(1+2+…+t′)，同时使停机时间t≤t′。应满足2个条件，条件1：1<1和2<2；同时根据等比数列的性质还应该满足条件2：<。当p>时，条件1成立，同时条件2可简化为<，进一步形式转化为<(+–)，因为0<<1，所以<，且< (+–) =(+(1−))，则当≥时，不论为何值，条件2始终成立。综上所述当p>，同时≥时，无论为何值，结合2种算法始终可以改进预拷贝算法的性能。

图4直观地显现了与两者相互关系。同时r和r除了与CPU相关外还和算法的时间复杂度相关，可见采用快的算法可以使减小，有利于改进预拷贝算法。而计数排序的方法和比对初始内存页技术都是时间复杂度为()的方法，在网络速度和CPU速度一定的情况下，好的算法是至关重要的。极端情况下，也就是等于0时，比对初始内存页技术会失效，而计数排序的方法由于其自身的性质不会失效。通过公式分析，当达到一定比率时，即使不起作用，也不会对全局造成影响。

4.3 结尾阶段：引入调减虚拟机CPU时间片技术

当临界轮产生的条件被触发以后，预拷贝算法进入了结尾阶段。这一阶段的特点就是与停机时间直接相关。最后一轮发送内存页的数量直接决定停机时间，同时临界轮的状况又关系到最后一轮发送内存页的多少。减少虚拟机CPU的运行可以使变脏的内存页减少，但同时也会降低虚拟机自身应用程序的性能。基于上述考虑，只在结尾阶段引入调减虚拟机CPU时间片的技术，在减少停机时间的同时，又不至于长时间影响虚拟机自身的应用程序，从而影响用户体验。

在Xen-4.2.2虚拟化平台上，Credit调度算法为默认的虚拟机CPU周期调度算法。文献[14]中调整CPU时间片时使其不低于20%，同样把Credit调度算法的cap参数取为20，而不是更小值，用以保持一定的虚拟机性能。

还应该注意的是，对于Xen-4.2.2虚拟化平台的全虚拟化客户机而言，存在PV-on-HVM形式，即对于Linux内核的全虚拟化客户机而言存在半虚拟化驱动。在测验中发现，临界轮调减CPU时间片的方式不适用这种情况，仅仅适用没有半虚拟化的全虚拟化情形。在Xen-4.2.2虚拟化平台上，临界轮调减虚拟机时间片对于PV-on-HVM形式的虚拟机来说是不能够减小停机时间的。这也是使用本方法的局限性。

4.4 综合3种技术实现LMCOS算法

综合以上3种技术，实现了本文提出的基于运行阶段特征的虚拟机实时迁移技术。从迭代的第一轮开始，在传送每一个内存页的时候，就与初始内存页比较进行变量传输，同时从第3轮开始对要传输的内存页，根据变脏的次数进行计数排序传输，当遇到临界轮时，把虚拟机的CPU时间片降低，用以减少最后一轮变脏的内存页，使停机时间缩短。具体算法如图5所示。

p2m_size: 内存页数量；i: 临时变量；A[p2m_size]: 内存页变脏次数；D[p2m_size]: 内存页原来位置。if(是第一轮){发送采用比对初始内存页变量传输标识;}if(大于第一轮){ 记录变脏的次数到数组A中; if(大于第二轮){ 依据内存页变脏的次数进行计数排序，并把原位置信息存储在数组D中;}}if(临界轮){调整cpu时间片为20%;} for(int i=0; i

值得说明的是，进行临界轮判断时要分开判断，先进行最大迭代轮数或最大数据传输量的判断，再进行内存变脏次数小于阈值的判断，并且一旦超过阈值立即结束判断，节省计算量，减少负面效应。

通过这种设计，多种技术结合而且各种方法之间互不影响，互相协作，同时又具有针对性。相信能够很好地改进预拷贝算法。

5 实验及分析

为了验证LMCOS算法的有效性，在内核版本为3.2.0的64位操作系统Centos-6.4和Xen-4.2.2虚拟化平台上实现了LMCOS算法，并与预拷贝等算法进行了比较。每一个实验数据是取5次实验的均值并四舍五入后作为最终的结果。

5.1 实验环境

目标主机和源主机同为联想启天M4300机型，CPU同为 Intel(R) Core i3-2120 @ 3.30GZ类型，内存同为4 GB。2台主机由一台百兆五口的TH-1005T交换机连接。同时利用NFS服务把存在于目标主机上的虚拟机磁盘映像共享给源主机。客户虚拟机的磁盘文件大小为12 GB运行Ubuntu-9.04操作系统，并选2.6.28-11-generic内核，使客户虚拟机没有半虚拟化驱动的存在。同时保持每个物理主机最多只有一个虚拟机运行。

5.2 采用不同工作负载

实验中为了验证LMCOS算法的有效性，选择了5种不同类型的工作负载。

1) Idle：没有特别的应用程序在其上面运行，这个场景被用作比较和参考，代表空闲类型应用。

2) Nbench：这是一款用来对CPU、FPU和内存系统进行性能测试的工具。其本身是单进程的，实验中编写shell脚本同时循环运行了50个Nbench 基准测试程序，同时为了避免长时间集中于某一项测试，把调节某一项测试最少运行时间的MINIMUM_ SECONDS参数由5 s减为1 s。

3) Sysbench：该性能测试工具可以执行CPU、内存、数据库等方面的性能测试。实验中配置参数test=memory来执行内存测试，线程数为10个，每个块大小为768 MB，总传输数据量为5 GB。

4) Webbench：这是一款网站压力测试软件，它能够模拟多个客户并使用http请求。源主机配置Tomcat服务器和一个50 KB的静态网页，同时虚拟机并发运行10个Webbench客户请求该网页。

5) Dbench：该软件能够产生输入和输出负载给一个文件系统施加压力，实验中配置了25个客户进程来产生负载。

测试中为每个虚拟机分配1 GB内存，并配置一个VCPU，同时测试了虚拟机在源端运行时相关工作负载的参数。对于Idle场景来说，没有必要测量，而其他场景都是在Idle场景的基础上运行了特别的应用。对于CPU和内存的测试利用了虚拟机操作系统自带的top工具，而对于网络速率和磁盘的性能分别安装了iftop和iotop工具进行观测。具体参数如表2所示。

表2 各负载参数

从CPU角度来看，大部分情况下，Nbench负载单进程时就可以占用90%至100%，而其他工作负载单进程时都没能达到90%，所以Nbench可以代表CPU密集型应用；从网络流量的角度来看，只有Webbench这一工作负载有网络流量，而且网速主要集中在60~80 Mbit/s之间，其余场景基本为0，所以Webbench可以代表通信密集型应用；从磁盘角度来看，只有Dbench场景对磁盘有读写操作，而且较高的时候达到了20~30 Mbit/s的速率，其余工作负载几乎为0，所以Dbench可以代表磁盘密集型应用；从内存的角度来看，Sysbech负载的内存利用率最高，大部分情况下达到了70%到80%，而其他工作负载的利用率远低于Sysbench，所以Sysbench负载可以代表内存密集型应用。

5.3 工作负载测试

在这一部分，将进行各种工作负载的测试，并选用了Xen-4.2.2默认的30轮预拷贝算法设置。在比较预拷贝算法和本文提出的基于运行阶段特征的虚拟机实时迁移技术的同时，也进行了拆分，观察组合成LMCOS算法的计数排序的方法和临界轮调减虚拟机CPU时间片的方法(RTCR, reduce timeslice in critical round)，测试结果如图6和图7所示。

图6和图7分别给出了不同算法在不同工作负载情况下最后一轮和临界轮内存页数量情况的比较结果。从上面的数字分析中可以看到，与预拷贝算法相比，计数排序方法、临界轮和最后一轮发送的内存页数量都不大于预拷贝算法，计数排序的方法主要靠临界轮发送的内存页数量上的减少而使最后一轮发送的内存页的数量也减少。对于RTCR方法，临界轮发送的内存页的数量有时候比预拷贝算法还要多，但最后一轮发送的内存页数量却都不大于预拷贝算法，进一步验证了临界轮调减CPU时间片方法的有效性。

图8给出了不同工作负载的停机时间。从图8中可以看出，相比预拷贝算法，采用LMCOS算法以后停机时间均有所下降。同时LMCOS算法的停机时间也优于计数排序的方法和RTCR方法。说明LMCOS算法取得的成效是各种算法综合的结果。但是对于Idle负载改进不大，主要是因为Idle负载、临界轮和最后一轮发送的内存页过少所致。总之，与预拷贝算法相比，LMCOS算法使停机时间平均减少53%，最少的Idle负载减少1%，最多的Dbench负载减少98%。

图9和图10分别给出了总传输的内存页数和总迁移时间的比较结果。从图9中可以看出计数排序的方法可以减少总传输的内存页个数，而RTCR方法，则对总传输的内存页数量没有必然的影响。同时可以看到，LMCOS算法对于总迁移时间平均减少了65%，最小的减少了48%，最大的减少了89%。LMCOS方法与计数排序的方法相比，总传输的内存页数有的减少，有的增加，有的相当。但总传输时间，却明显下降。

以上不同类型的工作负载的测试结果表明，与其他方法相比，LMCOS方法能够起到一加一大于二的综合作用效果，同时减少总迁移时间和停机时间，大幅提高虚拟机实时迁移的性能。

然而在总迁移的内存页方面，采用LMCOS方法时，Sysbench场景和其他场景相比，出现了很明显的内存页增加的情形。不同的工作负载，由于其访问内存方式的不同，虽然都能产生总迁移时间减少这样同一结果，但中间的过程略有不同。对于通信密集型和磁盘密集型的应用来说，访问的内存相对集中，LMCOS保证同时减少总迁移时间和停机时间的同时，能够减少总迁移的内存页数。而对于CPU密集型应用来说，从本次实验结果来看，总迁移的内存页数变化很小。但是对于内存密集型的应用来说，总迁移的内存页却大幅度提升，尽管Sysbench工作负载更改的内存页数量较多，但每一个内存页更改的比例不是很大，LMCOS方法在总传输的内存页增多的情况下可以减少总迁移时间，说明LMCOS算法实质上减少了数据量的传输。从初始阶段就使用的比对初始内存页技术发挥了很大的作用，只传输变量部分，从而减少了数据传输量及总迁移时间。当然这和虚拟机从启动到执行实时迁移时，期间运行的时长也有一定关系。

同时把5次实验迭代的轮数绘制成图11，以便于观察。对于Idle负载，无论哪种方法，都没有达到最大迭代轮数，每次几乎都是在6轮上下。对于其他4种负载，预拷贝算法都是达到了最大迭代轮数，而采用本文所提出的LMCOS算法，虽然不能使每一次实时迁移的迭代轮数都在最大轮数以下，但在最大迭代轮数以下的现象出现次数较多。

5.4 不同内存测试

实际使用中的虚拟机，内存大小是不尽相同的。本文采用不同大小的内存进行测试，以观察LMCOS方法在不同内存中的表现。在上面的测试中，Sysbench负载是内存密集型的，而且在总发送的内存页数目和总迁移时间2个方面表现出了截然不同的趋势。所以选用此负载进行不同内存的测试。本文另外增加了1.5 GB和2 GB的内存进行测试。

图12和图13分别是Sysbench负载在不同内存下最后一轮发送的内存页和停机时间。对于不同内存进行测试时发现，停机时间和最后一轮发送的内存页数在预拷贝算法和基于运行阶段特征算法中的变化趋势基本一致。停机时间和最后一轮发送的内存页数目在随内存增加都有不同程度的减少。

图14和图15分别给出了 Sysbench负载在不同内存下的总传输的内存页和总迁移时间。可以看出，随着内存的增加，总传输的内存页数也随着增加，LMCOS增加的幅度高于预拷贝算法。也迎合了不同工作负载测试环节中Sysbench场景所表现出来的总传输的内存页数目大幅增加的情形。但是总传输时间却不同，预拷贝算法增加的幅度高于LMCOS，说明尽管内存增加，但是使用的内存有限，大部分内存页和初始内存页面还有很多的相似性，也进一步说明，采用本文所提出的基于运行阶段特征的虚拟机实时迁移技术，随着内存的增加，总迁移时间改进的程度越见效。

总之，采用本文所提出的基于运行阶段特征的方法，随着内存的不同，对停机时间的影响没有对总迁移时间的影响大。LMCOS方法中的比对初始内存页变量传输技术对虚拟机内存大小变化最为敏感，内存越大，总迁移时间改进越大，这是因为初始阶段内存页比重较大且相似于初始内存页。

6 结束语

虚拟机实时迁移技术是虚拟化领域的研究热点之一。本文对虚拟机实时迁移中最常用的预拷贝算法进行了改进，在预拷贝算法运行的不同阶段，分别引入了不同的技术手段，提出了基于运行阶段特征的虚拟机实时迁移技术。在预拷贝算法执行的过程中，通过总结各个阶段的显著特点，并分别采取有针对性的改进措施，取得了很好的收益。实验结果表明，在不同工作负载的情况下，基于运行阶段特征的虚拟机实时迁移技术可以同时减少停机时间、总迁移时间。最好的情况下可以使总迁移时间减少89%左右，同时使停机时间减少98%左右。基于运行阶段特征的虚拟机实时迁移技术适用于不同的内存，对于不同内存下的同一负载，随着内存的增加，总迁移时间的改进越有成效，但是对停机时间而言，改进的成效没有总迁移时间明显。后续工作中，将继续研究和虚拟机实时迁移相关的其他方面，包括迁移时多虚拟机之间的相互影响，以及迁移中的安全性等问题。

[1] CLARK C, FRASER K, HAND S. Live migration of virtual machines. Networked[C]//Systems Design &Implementation(NSDI). c2005: 273-286.

[2] HINES M R, DESHPANDE U, GOPALAN K. Post-copy live migration of virtual machines[C]//ACM SIGOPS Operating Systems Review. c2009: 14-26.

[3] 陈阳, 怀进鹏, 胡春明. 基于内存混合复制方式的虚拟机在线迁移机制[J]. 计算机学报, 2011, 34(12): 2278-2291.

CHEN Y, HUAI J P, HU C M. Live migration of virtual machines based on hybrid memory copy approach[J]. Chinese Journal of Computers, 2011, 34(12): 2278-2291.

[4] LIU H K, JIN H, LIAO X F. Live migration of virtual machine based on full system trace and replay[C]//Symposium on High Performance Distributed Computing (HPDC). c2009: 101-110.

[5] CHANCHIO K，THAENKAEW P. Time-bound, thread-based live migration of virtual machines[C]//Cluster, Cloud and Grid Computing (CCGrid). c2014: 364-373.

[6] JIN H, DENG L, WU S. Live Virtual machine migration with adaptive memory compression[C]//Cluster Computing and Workshops (CLUSTER). c2009: 1-10.

[7] ZHANG X, HUO Z G, MA J. Exploiting data deduplication to accelerate live virtual machine migration[C]//Cluster Computing (CLUSTER). c2009: 88-96.

[8] SVARD P, HUDZIA B, TORDSSON J. Evaluation of delta compression techniques for efficient live migration of large virtual machines[C]//Virtual execution environments(VEE). c2011: 111-120.

[9] MA Y Q, WANG H B, DONG J K. ME2:efficient live migration of virtual machine with memory exploration and encoding[C]//Cluster Computing (CLUSTER). c2012: 610-613.

[10] DU Y Y, YU H L, SHI G Y. Microwiper: efficient memory propagation in live migration of virtual machines[C]//Parallel Processing (ICPP). c2010: 141-149.

[11] SVÄRD P, TORDSSON J, HUDZIA B. High performance live migration through dynamic page transfer reordering and compression[C]//Cloud Computing Technology and Science (CloudCom). c2011: 542-548.

[12] ZOU Q X, HAO Z Y, CUI X. Counting sort for the live migration of virtual machine[C]//Cluster Computing (CLUSTER). c2013: 1-5.

[13] LIU Z B, QU W Y, LIU W J. Xen live migration with slowdown scheduling algorithm[C]//Parallel and Distributed Computing, Applications and Technologies (PDCAT). c2010: 215-221.

[14] JIN H, GAO W, WU S. Optimizing the live migration of virtual machine by CPU scheduling[J]. Journal of Network and Computer Applications. 2011, 34: 1088-1096.

[15] ADEL A, KAMRAN Z. Improving the time of live migration virtual machine by optimized algorithm scheduler credit[C]//Computer and Knowledge Engineering (ICCKE). c2014: 346-351.

Live migration based on the characteristics of operation stages for virtual machine

ZOU Qing-xin1,2,3, HAO Zhi-yu3, YUN Xiao-chun1,3

(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China; 3. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100193, China)

Being directed against the different characteristics of start, iterative and end stages of pre-copy algorithm, live migration based on the characteristics of operation stages referred to as LMCOS was proposed. In the start stage, the technique of comparing initial memory page and sending variables was brought to avoid the transferring of unmodified memory. During the iterative stage, the transmitting method of counting sort was brought to reduce retransmitting memory pages. In the end stage, the police of reducing time slices of virtual machine’s CPU was brought to shorten the down-time. Compared with pre-copy algorithm, LMCOS reduces downtime by 53% and total migration time by 65% on average.

live migration, pre-copy, characteristics of the operation stages, virtual machine

TP302

A

10.11959/j.issn.1000-436x.2016021

2015-06-03；

2015-10-30

国家科技支撑计划基金资助项目（No.2012BAH46B02）

The National Key Technology Support Program (No.2012BAH46B02)

邹庆欣（1982-），男，辽宁义县人，中国科学院计算技术研究所博士生，主要研究方向为信息安全和虚拟化技术。

郝志宇（1980-），男，山东蓬莱人，博士，中国科学院信息工程研究所副研究员，主要研究方向为信息安全和虚拟化技术。

云晓春（1971-），男，黑龙江哈尔滨人，博士，中国科学院计算技术研究所研究员、博士生导师，主要研究方向为信息安全、计算机网络等。