一种基于聚类分组的虚拟机镜像去冗余方法-徐继伟.pdf

《一种基于聚类分组的虚拟机镜像去冗余方法-徐继伟.pdf》由会员分享，可在线阅读，更多相关《一种基于聚类分组的虚拟机镜像去冗余方法-徐继伟.pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、软件学报ISSN 10009825，CODEN RUXUEWJournal ofSoftware，2016，27(2)：466-480【doi：1013328jcnkijos004878】中国科学院软件研究所版权所有一种基于聚类分组的虚拟机镜像去冗余方法幸徐继伟1,2,3，张文博1，魏峻1,2,3钟华1,3，黄涛1231(中国科学院软件研究所软件工程技术中心，北京 100190)2(计算机科学国家重点实验室(中国科学院软件研究所)，北京 100190)3(中国科学院大学，北京 100190)通讯作者：徐继伟，E-mail：xujiweiotcaixiscasaccnE-mail：josisca

2、saccnhttp：wwwjosorgcnTel：+861062562563摘要： 随着云计算的兴起，虚拟化技术使用也越来越广泛，虚拟机正逐步取代物理机，成为应用服务的部署环境出于灵活性、可靠性等方面的需求，虚拟机镜像急剧增长，如何高效地、经济地管理这些镜像文件已成为一个很有挑战性的研究热点由于虚拟机镜像之间存在大量重复性的数据块，高效的去冗余方法对于虚拟机镜像管理至关重要然而，传统的去冗余方法由于需要巨大的资源开销，会对平台中托管的虚拟机性能造成干扰，因而并不适用于云环境提出了一种局部去冗余的方法，旨在优化镜像去冗余过程其核心思想是：将全局去冗余变成局部去冗余，从而降低去冗余算法的空间复杂度

3、，以达到减少操作时间的目的该方法利用虚拟机镜像相似性作为启发式规则对虚拟机镜像进行分组，当一个新的镜像到来时，通过统计抽样的方法为镜像选取最为相似的分组进行去冗余实验结果表明：该方法可以通过牺牲1左右的存储空间。缩短50以上的去冗余操作时间关键词： 云计算；虚拟化；虚拟机镜像；存储；去冗余中图法分类号：TP316中文引用格式：徐继伟，张文博，魏竣，钟华，黄涛一种基于聚类分组的虚拟机镜像去冗余方法软件学报，2016,27(2)：466-480http：wwwjusorgcn100098254878htm英文引用格式：Xu JW，Zhang WB，Wei J，Zhong H，Huang TVirt

4、ual machine image deduplication me也od based on clusteringRusn Jian Xue BaoJournal ofSoftware，2016,27(2)：466-480(in Chinese)http：wwwjosorgcn1000-98254878htmVirtual Machine Image Deduplication Method Based on Clusteringxu JiWeil2，一，ZHANG Wen-B01，WEI Junl，2，一，ZHONG Hual一，HUANG Ta01，2，31(TechnologyCente

5、rofSoftwareEngineering，Institute ofSoRware，TheChineseAcademy ofSciences，Beijing 100190，China)2(State Key Laboratory ofComputer Science(Institute ofSoftware，The Chinese Academy ofSciences)，Beijing 100190，China)3(University ofChinese Academy ofSciences，Beijing 100190，China)Abstract：Virtualization tech

6、nology is becoming more and more prevalence with the rise of cloud computingThe physical machines forservice hosting are gradually being replaced by virtual onesDriven by reliability and flexibility considerations，virtual machine imagesincrease sharply,and how to manage them efficiently and economic

7、ally has become a big challengeSince large amount ofduplicated datablocks exist in different virtual machine images，an efficient deduplication method is vital to the virtual machine image managementTheexisting deduplication works are not very suitable for cloud environments as they employ time-consu

8、ming algorithms which Can cause基金项目：国家自然科学基金(61402450)；国家科技支撑计划(2013BAH45F01)；国家高技术研究发展计划(863)(2013AA041301)；北京市自然科学基金(4154088)Foundation item：National Natural Science Foundation of China(61402450)；National Key Technology Research and DevelopmentProgram of China(2013BAH45F01)；National High-Tech R&D

9、Program of China(863)(2013AA041301)；Beijing Natural ScienceFoundation ofChina(4154088)收稿时间：20140423；修改时间：20141231；采用时间：2015081l；jOS在线出版时间：20151115CNKI网络优先出版：2015-1116 09：22：17http：wwwcnkinetkcmsdetail112560TE201511160922001html万方数据徐继伟等：一种基于聚类分组的虚拟机镜像去冗余方法 467serious performance interference to the n

10、eighboring virtual machinesThis paper proposes a local deduplication method which call greatlyoptimize the deduplication process of virtual machineThe main idea of the method is tO convert the global deduplication tO a local one，thus considerably reducing the space and time complexityIn this method，

11、the images ale classified into different groups through allimproved k-means clustering algorithm according to image similaritiesWhen a new image is entered，a sampling method is used tochoose aft appropriate group tO perform the deduplication operationExperiments show that this approach is robust and

12、 effectiveIt cansignificantly reduce(more than 50)the performance interference to hosting virtual machine with an acceptable increase(about 1)indisk space usageKey words：cloud computing；virmalization；virtual machine image；storage；deduplication云计算作为一种新兴的计算模式，具有弹性供给资源和按使用付费等特点云计算通过网络提供对后台共享资源池(服务器、网络、

13、存储、应用软件、服务等)的访问和使用，并对不同租户的资源访问进行隔离，以保证不同租户的数据安全和性能隔离虚拟化技术【l】已经成为构建云计算环境的关键技术，国内外主流的公有云平台(如亚马逊AWS、微软Azure、阿里云等)都采用虚拟化技术搭建，开源社区私有云建设方案(如OpenNebula，OpenStack，Eucalyptus等)也都采用虚拟化技术作为支撑虚拟化技术能够使虚拟机像物理机一样运行，虚拟机的磁盘信息(如操作系统、应用软件、用户配置、用户数据等)都封装在虚拟机镜像中因为虚拟机镜像具有封装性，所以镜像在存储过程中以一个整体的形式存在，这就不可避免地存在相当程度的数据冗余以亚马逊AWS

14、为例，虚拟机机器镜像的持久化存储是以对象的形式保存在亚马逊简单存储服务(Amazon S31中隶属于不同用户的镜像可能继承自相同的模板，这使得不同镜像之间存在相同的数据块；即使镜像是各自创建而不是继承自相同的模板，镜像之间也可能存在相同的操作系统、应用软件等内容研究发现【2】，在虚拟机镜像之间存在80以上的数据冗余IBM Pulse 2012的报告指出，企业环境中存在大量镜像且不断增长在大型企业中，虚拟机的数量高达5 00020 000个，每天产生的镜像数量多达数千个，且以每两年增长3倍的速度增加假设每个镜像大小为IOGB一20GB，平均每天产生的数据增量超过10TB，这种数据存储需求严重超出

15、了存储设备能力的增长，并且使企业管理数据的成本越来越高，数据中心的能耗越来越大重复数据删除技术是一种有效的消除冗余数据的技术，广泛应用于数据归档和备份中【3】传统环境中的数据去冗余技术面向的是封闭的归档或备份系统，在去冗余操作过程中具有资源独占的特性，因而更加关注数据压缩率；而云计算环境是一种开放的、资源共享的环境，虚拟机镜像去冗余操作会不可避免地对平台中托管的其他应用产生性能干扰与此同时，我们还发现，虚拟机镜像去冗余过程中存在“相似相容”的特点，即，对拥有相同或相似操作系统、文件系统和应用软件的镜像进行去冗余之后得到的数据总量要远远小于两个镜像总大小，而对拥有不同操作系统或文件系统的镜像进行

16、去冗余之后所得到的数据总量与两个镜像总大小基本一致因此，在特定镜像的去冗余过程中，不相似的镜像数据将成为无效数据我们把利用所有已有镜像数据对特定镜像进行去冗余的过程称为全局去冗余过程在全局去冗余过程中，无效数据将占用大量的内存空间，降低有效数据查找的命中率，延长去冗余操作的时间，加重镜像去冗余操作对平台托管应用性能的干扰我们利用虚拟机镜像之间的相似性作为启发式规则，采用聚类分组的方法过滤镜像去冗余过程中的无效数据。解决镜像去冗余时间长、对平台中托管虚拟机干扰严重的问题该方法可以将全局去冗余问题转化为局部去冗余问题，降低去冗余操作的空间复杂度论文的贡献主要体现在以下几个方面：(1)利用镜像相似性

17、作为启发式规则对虚拟机镜像进行聚类分组，过滤去冗余过程中的干扰数据，从而降低虚拟机镜像去冗余过程中指纹查找的空间复杂度；(2)探索了两种统计抽样方法，用于为镜像选择合适的去冗余分组，并给出了一种用于计算样本容量的可行性方法本文第1节简单介绍虚拟机镜像和分级存储的一些相关背景第2节将全面阐述我们的基于聚类分组的镜像局部去冗余方法和相关的镜像抽样分组选择方法第3节通过实验验证方法的有效性和稳定性第4节分析介绍已有块级别去冗余工作和虚拟机镜像去冗余工作第5节对本文工作进行简单的总结万方数据1研究背景与动机Journal of Software软件学报V0127，No2，February 201611

18、镜像相关概念虚拟机镜像是封装了操作系统和应用软件的一种特殊格式的文件，可以被相应的虚拟机监控器实例化为虚拟机虚拟机镜像格式分为两大类：全镜像模式(flat mode)和稀疏模式(sparse mode)我们常见的虚拟机镜像的格式有RAW,QCOW,VMDK，VHD等，其中，RAW格式即为全镜像模式，其他格式均为稀疏模式虚拟机实例化是指为虚拟机镜像分配相应的计算和IO资源，使其变成一台可以运行的虚拟机的过程而虚拟机在运行过程中，会实时地从相应的镜像文件中读取和写入信息由于存在备份、调试、错误修复等需求。系统需要周期性地(或按用户指定要求)保存虚拟机磁盘内容在特定时刻的状态，即，对虚拟机镜像文件做

19、快照(snapshot)从文件系统语义讲，镜像文件快照是指针重定向或写时复制技术的产物，是附属于某个镜像文件存在的，但是从应用语义讲，镜像文件快照是包含虚拟机完整硬盘信息的文件镜像快照在备份保存(跨文件系统保存)过程中会按照应用语义进行还原，这也是造成镜像冗余的重要因素12镜像分级存储分级存储是根据数据大小、重要程度、访问频率等指标，将数据存储在不同性能的存储设备上，并能按照特定需求实现数据客体在不同存储设备之间的自由迁移一般情况下，存储设备的容量越大，则其存取速度与带宽越低，每bit价格越低权衡容量、速度、成本三者的关系，迫使存储系统不得不从经济角度考虑分级结构在云环境中，虚拟机镜像存储通常

20、也会采用类似的结构虚拟机镜像往往以对象的形式存储在容量较大、价格较低的存储服务中，而且存储服务往往具有更高的可靠性虚拟机实例化时，需要将虚拟机镜像从存储服务中加载到本地存储设备中当虚拟机镜像需要备份或持久化保存时，需要将虚拟机镜像保存到存储服务中本文的去冗余工作主要是针对这种场景为了便于理解，本文中将复杂的存储服务抽象成简单的存储设备(如磁盘阵列)，在本文后面的论述和实验部分均以存储设备替代存储服务该方法适用的部署架构如图l所示，终端用户通过网络访问虚拟机提供的服务，镜像文件存储在本地存储介质中，虚拟机通过NFSCIFSiSISC等协议进行镜像文件读写图中的备份存储表示远程存储服务，虚拟机镜像

21、需要通过网络持久化到备份存储中这种架构体现了当前主流的云环境搭建场景，如AWS，CloudStack等均采用类型架构，在AWS中镜像存储类似于EBS，备份存储类似于S3，而在CloudStaek中镜像存储则类似于主存储，备份存储类似于二级存储vktual machinehostFig1 Typical image backup system deployment architecture图1 典型的镜像文件备份系统部署架构13虚拟机镜像去冗余对平台托管Web应用性能影响为了说明研究虚拟机镜像去冗余方法的必要性，我们按照图l的架构搭建了一个基于虚拟化的计算平台在平台中的一台虚拟机上运行一个RUB

22、iS应用，并通过监控软件监测其性能在应用运行过程中，我们采用传统方法对平台中的虚拟机镜像进行去冗余备份，方法步骤如下：(1)对镜像进行分块并采用MD5算法计算每个分万方数据徐继伟等：一种基于聚类分组的虚拟机镜像去冗余方法块的哈希指纹；(2)查找指纹库确定指纹是否已经存在，判断该数据块是否重复；(3)存储数据块我们对比去冗余过程执行之前和执行时的Web应用性能，其结果如图2所示我们观察了RUBiS应用的两个性能指标每秒点击数和响应时间从图中我们可以看出，虚拟机镜像去冗余会使应用每秒点击量下降，并使应用响应时间提高，整体性能损失在15以上这说明虚拟机镜像去冗余操作会对平台托管的虚拟机应用造成干扰因

23、此，本文关注一种可以降低性能干扰的虚拟机镜像去冗余方法Before dedupDuring dedup0 50 100 150 200 250 300Time(S)l-6， Beforededup15 During dedupl飞，。_l_3一+-，t- -一。1 2j一 一【10 50 100 150 200 250 300Time(s)Fig2 Comparison of Web application performance before and during backup operations图2备份操作执行之前和执行时的Web应用性能对比2基于聚类分组的镜像局部去冗余方法本文工作的目

24、标是消除虚拟机镜像中的冗余数据镜像去冗余存在“相似相容”的特点，拥有相同操作系统、应用和数据集的镜像有很大几率(高于80)拥有相同数据块；反之，操作系统不同的镜像拥有相同数据块的几率则很小(可能低于l)这就意味着，如果两个镜像不相似，它们之间存在相似数据块的概率就很小，对它们进行去冗余只能取得非常微小的存储收益这是本文方法的可以有效工作的基本前提在这样一种启发式规则下，我们通过过滤去冗余过程中的无效数据来降低查找算法的空间复杂度，以牺牲少量的存储空间为代价换取快速的去冗余时间假设所有已存在的虚拟机镜像形成集合臼，我们的方法首先利用一种聚类算法F将力中的镜像分成若干小集合，只力)=刃l，刃2，力

25、。)，其中，U：q=口，n!q=a针对每一个分组口中的镜像，采用固定长度分块去冗余的方法执行去冗余操作，即，将力域的全局问题转化为皿子域的局部问题对于新到来的镜像采用特定的取样方法S提取17l的指纹样本，计算样本双与每个分组力，的相似度Sim(S(，f21)，选择相似度值最大的分组臼。对口执行去冗余操作，其中，Q=曰=max篙Sim(S(a)，日)分组刀个数的大小需满足条件npm，其中护表示力的全部指纹数据大小，m表示可用内存大小图3为局部去冗余方法示意图接下来我们将具体介绍方法细节A11thec2Fig3 Local deduplication diagram图3局部去冗余示意图OO0OOO

26、0OO如踮鲫加舒铂蔼一霜一苗日口透f一一万方数据470 Journal of Software软件学报V0127，No2，February 201621镜像备份及去冗余时机去冗余操作将分别消耗大量的服务器端资源和存储端资源考虑到备份和去冗这两个操作的时机，将会有3种不同的策略：备份前去冗余、备份后去冗余和备份中去冗余若执行备份前去冗余，网络传输的数据量将会是压缩后的数据大小，备份所需要的时间窗口将会缩短，然而指纹计算和指纹查找的过程就只能在主机端完成，这将会对主机上托管的虚拟机或应用性能造成严重干扰；相反地，若执行备份后去冗余，则数据传输量的大小将与镜像大小一致，备份所需要的时间窗口将会大为增

27、加我们的目标是平衡主机端和存储端的资源开销，避免造成负载集中的情况出现，同时要尽量降低备份所需时间窗口因此在我们的工作中，我们采用备份中去冗余的策略这样，数据传输量会尽可能地小，而指纹计算和指纹查找也将分别在主机端和存储端执行在我们的备份去冗余系统中，我们把主机端作为备份的客户端，把存储端作为备份的服务器端如图4所示，我们把数据切分的模块和指纹计算模块放到主机端，而把指纹查找和数据块存储模块放到存储设备端这样做的目的是为了减小网络传输的数据量，只需要从主机端到服务器端传输未曾保存的数据块然而，数据切分和指纹计算是CPU密集型操作，由于在云环境中主机端托管了大量的虚拟机，这就不可避免地会造成资源

28、竞争，从而对托管虚拟机的性能产生影响对此，我们能做到的就是加快去冗余备份的速度，以缩短影响时间因此，与之前的工作不同的是，我们在去冗余系统中加入了一个预处理模块(图4中灰色框)，用于加速指纹查找过程，从而加快去冗余的速度在这个模块中，我们采用简单的聚类分组算法将镜像分为若干组，使得指纹查找由一个空间复杂度高的全局问题变成一个空间复杂度相对较小的局部问题同时，为了权衡压缩比例和指纹查找性能，我们采用分组优化方法来控制分组大小对于数据块的存储，我们把固定数目的数据块以追加的方式存储到存储设备端的文件中，由于数据块大小是固定的。因此只需知道数据块的编号就可以计算出该数据块起始位置在文件中的偏移指纹到

29、数据块的映射由指纹索引表来维护Fig4 System deployment architecture图4系统部署架构22镜像聚类分组算法图5展示了镜像备份、指纹和数据块之间存在的对应关系，镜像的备份是一个逻辑的实体，可以由元数据文件和相应的数据块复合而成元数据文件包含一组顺序的指纹，可以看做是一组指纹的集合，指纹则可对应相应的数据块数据块指纹集合是一维的数据集合，我们采用“均值聚类算法对指纹数据集合进行处理我们根据镜像的特点和组织结构对“均值聚类算法【4】进行改进，并将改进的算法用于镜像元数据文件的分组操作运行如均值万方数据徐继伟等：一种基于聚类分组的虚拟机镜像去冗余方法 471聚类算法之前，

30、首先要确定k的大小我们根据kpm的原则来决定k的大小，并通过调整k的大小保证每组镜像的指纹能全部加载到内存中k聚类算法的基本原理如下：给定一组元素的集合G12，而)，其中，每个元素是一个d维的数组k聚类算法的目标就是将这行个元素划分为k个子集合s-(sl，岛，SD，并使所有集合中元素到集合中心点距离的平方和最小karg中屿一圳2 (1)。i=l xEs，其中，似表示集合S的中心点rB-。-。-。i习r一1Backup 2户Chunk”Chunk，件1Chunk n+2Chunk，r3Chunk n+4Chunk n+5ChunkmChunk m+1Chunk m+2Chunk m+3Chunk

31、 m+4Chunk朋+5Fig5 Relationship among backup，fingerprint and chunks图5备份、指纹、数据块之间的关联关系虚拟机镜像包含虚拟机的硬盘信息，因此，我们可以大致根据镜像的启动扇区信息判断镜像的操作系统和文件系统类型，我们把这些信息作为缸均值聚类算法的一种先验知识在“均值聚类中，初始中心点的选取对聚类的结果具有一定的影响我们在选择初始中心点时，根据前面提到的先验知识，尽量选择具有不同操作系统和文件系统的镜像作为中心点在改进的聚类算法中，我们采用镜像相似度来表示两个镜像之间的距离由于镜像内部存在大量冗余的数据块。于是在镜像的元数据文件中也会有

32、大量相同的指纹，如0字节填充的数据块指纹我们把这些冗余数据块称为内部冗余(inner duplication)这些内部冗余数据块可能因为数量过多而影响两个镜像之间相似度的计算要计算镜像相似度，首先要消除镜像内部冗余数据块，这个过程被称为内部去冗余(inner deduplition)；与之相对的是消除镜像之间的冗余数据块，称为外部去冗余(inter deduplication)因为元数据文件包含了整个镜像的所有数据块指纹，所以要计算两个镜像的相似度可以等价为计算其相应的元数据文件的相似度正如前文中提到那样，一个元数据文件可以被视为一组指纹向量，即M=-qi压，五)我们用M=(llf2fm)(m

33、-n)来表示元数据文件去冗余后的指纹集合我们把，称为镜像的特征集合于是，我们可以通过公式(2)计算两个镜像A皿之间的相似度Sim(A，曰)：型丝Q丝! (2)I肘：I+I朋；I根据公式(2)可知，两个镜像之间的相似度取值范围为【0，l】于是，我们给出虚拟机镜像聚类算法一一黼一万方数据472 Journal of Software软件学报V0127，No2，February 2016算法1虚拟机镜像聚类算法输入：初始分组数七；c；代表i个分组的选出初始中心点算法：l：Set蜀=cl，=c2，S：ck2：repeat3： 研卜S，最卜是，研-足4： forallA口do5： minindex，mi

34、nvalue卜1，loop,-O6： for eachj1，明do7： 曰卜q8： valuel-Sim(A声)计算镜像A,B的相似度9： if valueminLengh Then10： minvaluP七一v口lue1 1： minindex-j12： endif13： endfor14： 品访i。缸卜品j月涮“u M)15： endfor16： for each fE1，明do17： c,+-RepickCentroid(Si)重新选择分组墨的中心点18： endfor1 9：loop-loop+l20：until(爿一墨and是一是andand一最)or(100pt)众所周知，肛均值聚

35、类算法的时间复杂度为O(tknm)，其中，t为迭代次数，k为分组的数目，行为镜像总数，m为数据维度而在我们的算法中，数据维度为l，于是，算法的时间复杂度为O(tkn)而在一般情况下，职拧并且f捍，即，算法可在多项式时间内完成为了避免不同的分组数量对局部去冗余的效果以及内存的使用的影响，我们从触发时机和分组合并两个方面对算法进行优化1)触发时机由于聚类算法需要的时间复杂度较高，如果运行过于频繁则会导致大量的资源浪费，影响系统性能；反之，如果运行次数过少则可能导致其失去原有的作用，造成镜像去冗余备份存储中的内存溢出因此，我们需要设定合适的触发时机假设镜像分为k组，可用内存大小为M，对于每一个分组f

36、(Of七)，如果分组f总的特征值大小超过可用内存坛，则对j分组使用分组聚类算法这样既可以做到在去冗余过程中不会造成内存溢出，又可以做到聚类算法的时间复杂度始终控制在一个合理的范围内2)分组优化通过实验我们发现，尽管算法可以成功地将镜像分为若干组，然而每组镜像的特征值总量大小相差较大，有的分组只有少数几个镜像存在为了不致影响取样比较阶段的性能以及提高去冗余率。我们需要在不超过内存限制的前提下，将一些小的分组进行合并从某种角度来讲，基于镜像相似的聚类可能存在逻辑上的冲突，例如，镜像A和镜像口的相似度大于50，镜像B和镜像C的相似度大于50，然而镜像A和镜像C的相似度可能为O然而，我们聚类的目标并不

37、仅仅是为了使分组中所有的镜像具有极高的相似度也尽可能地将每个分组的指纹大小控制在可使用的内存范围之内在这种目标前提下，不同的分组之间也可能存在相似度极高的镜像同样，由于存在分组优化，同一个分组中万方数据徐继伟等：一种基于聚类分组的虚拟机镜像去冗余方法 473的镜像也可能完全不具有相似性，而这也是为了最大限度地利用内存资源，加速去冗余过程23取样比较选择去冗余分组完全的内存去冗余是本文方法最主要的特征，我们已经通过聚类算法实现镜像的分组当一个新的镜像到来时，系统将根据特定的规则R选取一组指纹样本然后计算该组样本在每一个去冗余分组中的命中率，并选择命中率最高的分组来执行去冗余操作在我们的工作中，我

38、们对比了简单随机取样和系统取样两种方法1) 简单随机取样(SRS)：首先，按照固定大d,(4KB)将镜像分为份(即样本空间为)，并分别用1朋为每一份进行编号；然后，随机地从【l朋中选择一个数字(即样本容量为疗)，计算对应的这刀个块的指纹，形成一个样本&2) 系统取样(SS)：和简单随机取样一样，首先将镜像分为大小相等的份；然后，将从l到按顺序等分成rB组，每组有Nm个块，分别用1,Nm进行编号；从每组中随机选择nm个块，计算这些块对应的指纹，形成一个样本叠为了提高样本在每个分组中命中率的辨识度，我们需要计算样本S的容量拧假设样本在分组的命中率为P，则其未命中的概率为l叩令变量Z代表样本在分组中

39、的命中数，则X服从参数为0，p)的二项分布，记作。Y瑚(疗炉)当拧足够大时，二项分布BCn护)可以被近似为均值为肌方差为盯2的正态分布，记为(从盯2)，其中， g=np，盯=赢而于是，令y=(x-a),r,i0 Y服从标准正态分布，记为YN(O，1)，其概率密度函数为，1 一西(y)=卜=e 2 dy (3)一21t假设样本在分组中至少命中z个的概率为p,eP Px)=仍那么，西(y)=P限x)=l-p (4)于是，可以得到炉伊痧-1(1-力+综合公式(3)、公式(4)，可以得到有效样本的计算公式(5)J2印一睁1(1一户)r朋+饥p1(1一p)】。朋一2剜 闻，l=-二-一 I)l2p由于镜

40、像中存在冗余数据，因此在实际取样过程中可能存在冗余样本我们假设镜像的内部冗余率为r，那么实际样本容量可以根据公式(6)计算。一2印_【西-1(1一p)】2Pq+【睁_1(1一p)2pg一2印】 闻，I=-；-一 -U-2pr上述公式用于计算取样样本的大小，用于给出一种可供参考的选择由于事先并不知道哪一个分组是最合适的分组，在参数选择的过程中，需要根据历史经验进行判断如要求样本有99的概率在分组中至少命中100条，假定分组数据冗余率为40，样本命中的概率为30，贝IJp=O99,p=04,x=100，r=O3通过统计取样的方法，我们可以为新来的镜像选择合适的去冗余分组执行去冗余操作，从而过滤掉干

41、扰分组，提高查找命中率24方法的时间收益与空间开销基于聚类分组的镜像局部去冗余方法根据镜像相似度将镜像分为若干组，使得每组镜像的指纹可以被完全地载人内存中，从而避免了传统去冗余方法频繁的内存磁盘数据交换导致的性能瓶颈，可以大大加速去冗余过程该方法取得的收益是时间维度的收益然而，由于我们只进行分组内去冗余，这必然会导致一定量的冗余数据块的产生，这意味着方法造成的开销是空间维度的开销在时间维度上，去冗余时间随着数据量的不断增大而不断增长变为常数时间接下来，我们将分析在空间维度上方法造成额外开销的上界就全局而言，我们假设共有拧个不同的数据块，每个数据块的冗余份数为c，则去冗余之前的数据块为：，q，即

42、石刀，则全局去冗余率可表示为万方数据474 Journal of Software软件学报V0127，No2，February 201 6，：1一 C我们将所有数据块分为m组，并假设每个数据块平均在而(1历m)个分组中出现，那么去冗余之后的数据块总数为r：1一竺C即，=m的比值越小，方法造成的额外开销就越小3实验验证我们通过一系列的实验来验证我们的方法的有效性和性能我们从OnceCloudt5】云环境中选择了584个不同的虚拟机镜像，每个大小在15GB-20GB之间其中包括raw格式镜像416个，vhd格式镜像168个，镜像总大小为668TB，在实验中可用于去冗余的内存大小为500MB我们采用

43、128位的MD5值作为数据块指纹，使用64位地址作为块索引，那么一个块记录需要192位(24B)如果块大小为4KB，则需要402GB的空间来存储所有的指纹数据即便是所有的冗余数据块被去除之后，指纹数据总量仍大于可用内存大小，因此无法全部放置到内存中为了与已有工作做对比，我们首先实现了一个基于硬盘的哈希表，用来执行全局去冗余操作(global dedup)，在去冗余过程中，需要不断地进行硬盘读写，实现内存数据交换然后，我们用基于镜像聚类分组的方法执行局部去冗余操作，并对两种方法的实验结果进行比较实验中，采用5台刀片服务器作为实验设备，每台服务器拥有两颗Intel Xeno E5645 CPU，6

44、00GB硬盘和32GB内存备份存储端采用10TB空间的存储集群所有设备通过千兆网络设备进行连接31去冗余率和操作时间在虚拟机镜像去冗余中，去冗余率和操作时间是我们最为关心的两个要素，前者关系到数据最终占用的存储空间大小，后者则直接影响到去冗余备份时间窗121大小在本节中，我们将对这两个要素进行对比为了验证本文方法的先进性，我们先不对镜像数据进行分组，直接采用基于硬盘哈希表的方式进行全局去冗余，然后再采用基于镜像聚类分组的方法进行局部去冗余去冗余率的实验结果如图6所示，我们把所有镜像数据集的总大小(before dedup)记为100，当内部去冗余(inner dedup)完成后，数据集大小变为

45、242从图中我们可以看出：全局去冗余方案(global dedup)可以达到92的数据压缩率，而基于缸均值聚类分组的局部去冗余方法(10caldedup)可以达到102的数据压缩率，与全局去冗余仅有1的差距相对于压缩掉的90的数据，1的差距完全在可接受范围之内在接下来的实验数据中我们可以看到，1的空间消耗将会节省成倍的时间开销lBefore dedupIInnerdedup75 8lGlobal dedup。1 r-q Local dedup6：296 24：蔓ojl4蕊西译【 2) 0 JFig6 Comparison of data size and deduplication rate

46、under different approach图6不同方案下数据大小及数据压缩率对比在完成584个镜像的去冗余之后，我们分别对两种不同格式(raw和vhd)的新镜像进行去冗余操作对于每种镜像，我们分别采用全局去冗余方法和基于“均值聚类分组的局部去冗余方法备份20次，备份时间如图7所0加如们如加m万方数据徐继伟等：一种基于聚类分组的虚拟机镜像去冗余方法 475示对于raw格式和vhd格式镜像，我们的局部去冗余方法都将节省超过50的时间由于我们的方法是一种完全的内存索引查找，在去冗余过程中无需与外存进行进行交换，与全局去冗余方法相比，可以节省大量磁盘查找的时间vhdlocalrawglobalr

47、aw&localvhd&globalFig7 Different format image deduplication time图7不同格式镜像去冗余时间从上面的实验结果可以看出，我们的基于如均值聚类分组的局部去冗余方法可以在以付出微小的空间开销(1左右)为代价的基础上大幅度降低时间开销(超过50)32聚类分组算法的有效性和稳定性由于聚类算法的结果具有一定的不确定性，这就意味着我们采用聚类分组的方法去冗余可能导致最终结果具有一定的随机性为了保证算法的可用性，我们需要对算法的有效性和稳定性进行检验在这部分的实验中，我们使用聚类分组算法将镜像分为k组，并进行去冗余操作重复运行该操作10次，对于每一次实验，我们计算数据压缩率和每个分组的统计学特性图8展示了每次实验的数据压缩率，结果显示，最终数据压缩率稳定在895899之间这表明我们的基于“均值聚类分组的局部去冗余算法在实验给定的数据集上具有很好的稳定性实验的平均压缩率为897，仅比全局去冗余低11，所有实验去冗余结果与全局去冗余相比低不超过15个百分点，这表明我们的算法具有很好的有效性9084Global rate8974Avarage lo