《面向虚拟机镜像的改进相似度分组去重优化方法》由会员分享，可在线阅读，更多相关《面向虚拟机镜像的改进相似度分组去重优化方法（11页珍藏版）》请在金锄头文库上搜索。
1、面向虚拟机镜像的改进相似度分组去重优化方法 梁小宇 陈宁江 闫承鑫 刘文斌 广西大学计算机与电子信息学院 摘 要： 根据实验研究发现, 云计算环境中虚拟机镜像备份之间存在大量的冗余数据。尽管传统的去重方法有较高的去重率, 但需要花费大量时间, 这对有时效性要求的海量镜像备份场景并不适用。考虑虚拟机镜像之间存在大量相同或相似的操作系统和应用程序等相似性特性, 提出一种基于虚拟机镜像改进相似度分组去重优化方法。该方法利用镜像之间的相似性对镜像进行相似度分组, 把相似度达到阈值的镜像归为一组, 形成多个相似的镜像组。仿真实验验证了该方法减少去重过程中的索引空间范围, 缩短去重的时间, 提高了备份效率
2、, 特别适用于海量虚拟机镜像的快速备份场景中。关键词： 虚拟机镜像; 重复数据删除; 数据备份; 相似性; 作者简介：陈宁江 (1975) , 男, 广西南宁人, 广西大学教授, 博士;E-mail:。收稿日期：2017-06-21基金：国家自然科学基金资助项目 (61363003, 61063012) An improved similarity grouping deduplication optimization method for virtual machine imagesLIANG Xiao-yu CHEN Ning-jiang YAN Cheng-xin LIU Wen-bin
3、 School of Computer, Electronics and Information, Guangxi University; Abstract： According to the existed experimental results, there is a large amount of redundant data between the backups of the virtual machine image. Although the traditional deduplication method has a higher deduplication rate, it
4、 takes a lot of time. This does not apply to the massive virtual machine image backup scene with timeliness requirements. Considering the similarity feature with a large number of identical or similar operating systems and applications between virtual machine images, a deduplication method based on
5、improved similarity grouping for virtual machine images is proposed. The method uses the similarity of images to segment images into similar groups, then the imageswhose similarity reach a certain threshold are classified into different sets, finally a number of similar image groups are formed. Simu
6、lation experiments show that the proposed method reduces the index space, shortens the deduplication time, and improves the backup efficiency during the deduplication process, which is especially suitable for fast backup of virtual machine images.Keyword： virtual machine image; deduplication; data b
7、ackup; similarity; Received： 2017-06-210 引言随着诸多云数据中心的建成及其中运行的虚拟机数据规模急剧扩张, 云计算服务性能面临挑战。根据 IBM Pulse 2012 报告指出, 当今的企业环境中存在海量与日俱增的镜像文件。例如, Amazon Elastic Compute Cloud (EC2) 就有 6 521 个公共虚拟机镜像文件1。而每个大型的互联网企业都存在 5 00020 000个虚拟机2, 由此每天至少产生数千个虚拟机镜像, 在此基础上以超过每年 1倍的速度增长。假定每个虚拟机镜像的大小为 1020 GB, 则平均每天产生的数据增量超过
8、10 TB。巨大的数据存储量严重超过了现存的存储设备容量以及设备增长的能力。研究发现数据中心存储的海量镜像数据中存在大量重复数据。其原因如下:(1) 在镜像备份过程中, 对同一镜像进行多次全备份, 各个备份镜像之间大部分数据是相同的。(2) 不同的用户安装相同的操作系统, 不同之处仅在于系统内的用户数据和应用程序。针对这种情况, 文献3指出其镜像中存在 90%的冗余数据。(3) 如 RAW 等全镜像文件虽然能保存数据完整信息, 但也存在很多零填充等无效数据。文献4针对 Linux IBM AIX 操作系统的虚拟机镜像文件进行分析, 发现零填充块在镜像文件中比例高达 35%55%, 以上的无效数
9、据均属于冗余数据。(4) 即使是刚安装操作系统的单个镜像内也存在重复数据, 文献5中表明这种情况存在约 5%的冗余。(5) 镜像中安装的操作系统属于同一种类, 仅版本不同。文献6指出一系列基于 Ubuntu 8.04LTS 的镜像与多种 BSD、Linux、Open Solaris 的虚拟机镜像进行去重对比, 结果表明在具有相似操作系统的虚拟机镜像中能找出更多的重复数据, 重复数据删除率能达到 70%以上, 系统整体能够减少 71%78%的存储空间。因此, 如果镜像数据经过去重处理, 可以节省系统大量的存储空间。镜像冗余占比重最多、出现可能性最大主要集中在以下场景:同一镜像多备份;版本不同的同
10、种操作系统;应用数据和用户数据不同, 但操作系统相同。综上, 即虚拟机镜像集群中存储了大量相似或相同的操作系统, 表明了镜像文件具有高度相似性的特点。假设镜像去重过程中镜像之间的相似度很低, 则进行去重的意义不大。如果能针对镜像群进行相似度分组预处理, 相似度高的镜像组内重复数据多, 这样可以加快去重时间, 减少索引范围。利用镜像文件之间的相似性进行去重可以减少去重的索引时间, 提高去重效率。虚拟机镜像的备份过程经常伴随着去重操作。在去重备份的过程中会占用大量系统的计算资源, 为了提高系统的运转效率, 云数据中心一般会选择在低负载的时间段内进行备份去重操作。研究指出, 云数据中心每天负载较低的
11、时间很短。如果在特定的时间内不能完成备份操作, 将会给数据中心带来巨大的损失;如果放弃备份, 又会使系统存在风险。因此, 在镜像备份场景中, 备份时间是一项很重要的指标。缩短去重备份的时间, 可以使系统在有限时间内备份更多的数据, 避免因备份速度过慢导致云服务质量下降, 进而导致系统不能快速有效的运转。目前针对虚拟机镜像的去重技术的研究主要集中在节省存储镜像空间, 没有综合考虑平衡去重效率, 以及额外带来的性能开销、备份时长等问题, 特别是如何在保证高去重率的基础上尽可能减少去重的备份时长。本文研究面向虚拟机镜像改进的相似度去重性能优化方法, 首先分析虚拟机镜像块之间出现相似性的原因, 并用代
12、表指纹表示镜像块之间的相似程度;进而提出一种改进相似度分组去重优化算法, 减少不必要的去重查找, 降低虚拟机镜像去重过程中指纹查找的空间复杂度, 从而适应有时效性要求的海量镜像去重备份场景。1 相关工作传统的重复数据删除过程是将数据流 (文件、数据块) 划分成块, 每块用特定的哈希指纹 (常用 MD5 和 SHA-1) 来唯一标识, 并将新数据指纹与已存储数据的指纹进行比较, 具有相同指纹的数据块认定为重复数据, 并将重复数据删除。当数据流具有高度相似性时, 需要引入数据相似性去重算法, 这样能够减少磁盘的访问次数, 用较小的开销来加快去重的时间, 提高去重的效率。该方法也存在其局限性, 即去
13、重的效果依赖于数据的相似性程度。典型方法是 HP 实验室提出的 Extreme Binning6分布式去重方案, 根据文件之间的相似性实现相似数据的一次磁盘索引访问。这种方法依赖于数据之间的相似度, 如果数据之间缺乏相似度, 则使用该方法性能较差。在实际场景中, 虚拟机在运行的同时, 会实时地从镜像中读取相应的数据。由于存在备份的需求, 云数据中心需要周期性的保存特定时间的虚拟机磁盘内容, 即对虚拟机镜像做快照 (Snapshot) 。镜像文件的快照包含虚拟机完整硬盘的信息, 在备份保存过程中需要进行还原, 这也是造成镜像冗余的关键因素之一。针对虚拟机镜像这类文件, 镜像之间是存在很多相似数据
14、的, 因此运用虚拟机镜像的相似性算法会加强镜像的去重效果。在近年相关工作中, 文献2通过分析虚拟机镜像存在相似相容特点, 去重前用聚类算法进行分组预处理, 聚类算法的目标是将镜像块划分成多个子集合, 并使所有镜像中元素到镜像中心点距离的平方和最小。基于聚类分组的优点是能够大幅度提高重复数据删除率, 但是去重分块过程和进行指纹索引需要的运算时间过长, 难以运用在对有时效性要求的云数据中心的备份场景中。文献7把去重技术引进到虚拟机镜像中, 阐述说明对于虚拟机镜像这类文件, 变长分块和固定分块的去重效果相近。文献8针对存储区域网络镜像提出去中心化冗余存储方案。文献9针对虚拟机镜像快照的备份场景平衡去
15、重率与去重效率, 其实验发现了镜像文件存储数据的总量在没有软件配置及位置变化的情况下增长速度很慢, 同时还发现了仅通过检测零块也可以节省相当可观的存储空间。文献10提出了应用 MD5 指纹的近似镜像算法对文本文档进行消重处理的方法。文献11设计了一个用于容错的云环境下的镜像文件存储系统。综上, 目前针对虚拟机镜像的去重技术的主要研究方向集中在用传统的去重方法提高去重率, 没有针对云数据中心环境下虚拟机镜像备份去重场景特有的备份时长的制约条件, 且专门针对虚拟机镜像特征展开的, 特别是当镜像数量和种类呈指数增长时, 针对的应用背景下的去重策略目前没有专门的研究分析。因而本文提出的方法正是针对以上
16、应用场景进行分析后得到的。把传统的去重方法运用在虚拟机镜像的基本原理如图 1 所示。系统把虚拟机中的镜像集群分别输入读缓存和写缓存中, 通过缓存把数据传入重复数据删除系统。传统的重复数据删除系统主要分成数据处理模块、地址映射模块和存储模块, 其中, 数据处理模块主要是包括对镜像数据进行分块、生成指纹等;地址映射主要存放地址映射表和地址相关的分配表;存储模块主要存放数据和指纹信息等。镜像经过整个去重系统后, 最后通过网络传输, 把经过去重的镜像放入镜像备份存储系统中。本文提出的镜像性能优化方法是在传统虚拟机镜像去重的基础上, 对镜像去重前进行预处理, 以减少镜像的索引范围, 减少去重花费的时间, 提高重复数据删除效率。图 1 传统的虚拟机镜像去重过程 Fig.1 Traditional virtual machine image deduplication 下载原图2 相似度相关定义及问题描述2.1 相似性定义定义 1 用 H 表示特征的提取函数,
