随着云计算技术的普及,基于云计算的VDI(virtual desktop infrastructure)系统得到快速发展.目前,无论是国内还是国外,众多大型企业和政府纷纷将自己的传统PC切换到VDI桌面云,这也将原来各个相互隔离的信息孤岛(PC机)有机地联系了起来.有研究发现,不同用户之间的数据高达60%是重复的^[1].因此,在数据存储或传输前快速地消除用户之间的重复数据,不仅可以减少后端存储空间,而且可以减少在网络中传输的数据量,降低能量消耗和网络成本,产生巨大的社会价值.

但是,目前的重复数据删除技术应用在VDI桌面云中还存在一定的问题.因为当前的重复数据删除算法主要是依据数据的时间局部性和空间局部性特征设计而成,而在主存场景中,I/O模型主要为随机的小颗粒IO,这就会导致当前的重复数据删除算法的性能快速下降,甚至无法工作.因此,需要研究一种全新的、适合应用在云计算主存场景下的重复数据删除算法.

重复数据删除算法的工作过程大致可以划分为4个步骤:分割数据、计算指纹、检测重复指纹和更新数据块引用关系^{[2, 3, 4, 5, 6]}.在这4个步骤中,检测重复指纹部分是最耗时的环节.如图1测试结果所示:OpenDedup重复数据删除算法^**的平均时间开销为63μs,而其中的49μs都被检测重复指纹模块所消耗,占总开销时间的77.7%.

图1(Fig.1)

图1 OpenDedup文件系统中重复数据删除模块处理时间开销测试结果 Fig.1 Testing result: Average latency of each module of OpenDedup file system

造成该问题的主要原因在于检测重复指纹时会产生大量的读磁盘操作,特别是当指纹总量超出内存的可用容量时,检索算法需要反复将磁盘中的指纹读入到内存中,从而产生大量的I/O操作^{[7, 8, 9]}.文献^[10]中,Petros等人曾计算过1PB的存储系统按4K规模划分数据块,大概会有5 500GB的指纹,这无法存储在任何一个存储阵列的内存中.所以,最早期的重复数据删除系统SIS^[2],Venti^[4]以及Store^[11]的性能都受限于磁盘的性能,其吞吐率只能达到MBps级.

为了减少常驻内存的指纹总量,2008年,Zhu等人在文献^[12]中介绍了基于Bloom Filter^[13]技术的重复数据删除算法.Bloom Filter利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合.这样,指纹检索过程就可以分为两个步骤:首先,通过Bloom Filter函数判断该指纹属于哪个指纹集合?然后,再在选定的集合中检索重复指纹.这样,就可以避免读入大量无用的指纹到内存中.正如文献^[12]中所描述的那样,DDFS系统在进行重复数据删除时可以避免99%的磁盘I/O操作,单节点性能可以达到100MBps以上.但是,采用Bloom Filter也会带来一些新的问题.例如:如何挑选k个合适的Hash函数?每个新数据块都进行K次Hash计算的时延以及CPU资源占用问题等等.

2009年,Lillibridge等人提出的基于抽样过滤技术(sampling-based filtering)^[14]的重复数据删除算法是最经典的重复数据删除算法之一.该方法主要利用了文献^[12]中所描述的数据局部性特征,从1M大小的片段(segment)中随机挑选出一个样本指纹放在内存中.在检测重复指纹时,先比对两个segment的样本是否一致:如果不一致,则直接视为新数据;如果一致,再逐个比对segment中数据片(chunk)的指纹.这样,常驻内存的指纹数量仅为原来的0.004,极大地减少了常驻内存指纹的总量.不过,该算法也同样存在无法忽视的缺陷:(1) segment不能超出1M,否则检测误报率会快速增加;(2) 主存的I/O模型不像备份存储的I/O模型是大块的、顺序的I/O,而是随机的、小颗粒的I/O,所以在主存系统中无法应用该算法^[15].

与Bloom Filter和sampling-based filtering类似的技术还有分组索引技术(grouping index),例如,在2013年,Sun等人提出的分布式相似文件元数据集合索引的构建方法^[15].该方法使用位置敏感Hash函数^[16]将具有相同数据片的相似文件元数据组成集合并建立索引,且仅将索引lshid保存在内存中.该方法与文献^[14]相比,最大的优点是可以应用到主存场景中,且分组的粒度可以超过1M的限制;缺点是无法应用在块存储设备中,因为在块存储设备中无法获取文件信息.同样,Bhagwat等人设计的Extreme Bin技术^[17]和Yang等人设计的DEBAR^[18]也属于分组技术,只不过分组的粒度限制在单个文件,且同样无法应用在块存储设备中.

Li等人提出的“有状态数据路由”和“无状态路由”重复数据删除技术^[19]的基本工作原理与Extreme Binning类似,改进的地方主要有两点:一是放弃了基于文件的采样,采用了文献^[14]中的基于super-chunk的采样技术(采样粒度小,该系统采用1M为单位),保障了重删率;二是为了避免数据存储不均衡问题的出现,他们提出了“有状态数据路由”技术.但是该算法同样也存在重删率、可扩展性和性能相互制约的问题,并最终导致集群总节点数受限.

付印金等人设计的S-Dedupe系统^[20]采用类似文献^[19]中的超块路由粒度和容器管理策略来保持数据局部性,并提出手印(handprinting)技术来提高超块相似度的检测能力,从而能够很好地消除重复指纹检测磁盘瓶颈和重复数据删除节点信息孤岛效应.

综合对比当前经典重复数据删除算法后不难看出,目前各种重复数据删除算法都存在不同程度的限制.如表1所示:Sparse Index实现简单,但只能用在备份场景中;Extreme Bin技术适合应用到主存场景,但只能应用在文件服务器上,无法应用在块存储设备中.所以综合来看,目前还不存在一种通用的重复数据删除算法可以解决所有场景下的重复数据删除需求这一问题.

表1(Table 1)

表1 经典重复数据删除算法对比分析Table 1 The comparison and analysis of classic deduplication algorithm 典型技术 常驻内存指纹数量与总指纹数量比 计算开销 实现复杂度 识别误报率 场景限制 Bloom Filter 1:500 大 高 高 不受限制 Sparse Index 1:250 小 低 低 仅适用于备份场景 Extreme Bin 1:86.56 中 中 中 受场景限制 HANDS[21] 1:100 大 高 低 不受限制

表1 经典重复数据删除算法对比分析 Table 1 The comparison and analysis of classic deduplication algorithm

众多研究发现,不同应用场景下的数据重复规律是不一样的^[22].例如:图片、音频以及视频文件服务器中,大多数情况下是整文件重复^[23];代码库服务器则几乎不存在整文件重复;邮件服务器的正文部分一般为部分重复,而附件一般为整文件重复(in-wire deduplication of geo-replicated email database systems. http://www.pdl.cmu. edu/Retreat/retreat13.shtml).那么,云计算场景下的重复数据分布规律是什么样的呢?

如图2所示,在云计算场景中,云操作系统(cloud OS)首先将存储设备虚拟化,然后为每个VM(virtual machine,虚拟机)分配一个在逻辑上完全独立的vDisk(virtual disk,虚拟磁盘).与传统数据中心式相比,云计算场景下的数据更加集中,发现重复数据的概率也越高.除此之外,还有另外两个重要特点.

图2(Fig.2)

图2 传统数据中心的存储设备使用方式与云计算数据中心的差异 Fig.2 Storage pool in VDI system

1) 每个vDisk都隶属于唯一的VM,可以实现块级的隔离(根据LUN号区分用户),而传统文件服务器却只能实现文件级的隔离(只能根据目录区分用户);

2) 支持数据动态迁移,可以按照一定的规则将不同用户的VM迁移到同一台物理服务器上,更容易支持按类聚合.

在现实中,我们经常发现相关性(包括工作相关性、业余爱好相关性、地理位置相关性等)越大的两个用户之间存在重复数据的可能性越大,而相关性越小则二者之间存在相同数据的概率越小.例如:同时使用Windows操作系统的两个用户之间存在重复数据的可能性比一个使用Linux和一个使用Windows的两个用户之间存在重复数据要高.为了验证该现象是否为普遍现象,我们特意设计了一个实验用于分析vDisk之间的重复数据量与用户的关系.实验设计如下:首先从华为的VDI(virtual desktop instrument,虚拟桌面云)系统中(华为公司的VDI系统同时为该公司的15万员工提供云桌面服务,是目前全球最大的云计算应用系统之一),按所属组织关系随机抓取100个用户的vDisk数据(总共大约2.3T的数据),然后每10人一组进行对比分析.每组的实验对象按照工作交集度进行组合,图3为第1组实验对象的关系图.

图3(Fig.3)

图3 第1组实验对象所属部门关系图 Fig.3 The user set of the first group of experiment

实验过程如下:

步骤1. 将上述用户vDisk中的文件数据按1M的粒度进行切割,用SHA-1计算每块数据的指纹,然后,每个文件1行记录保存到以该用户ID为表名的SQLite数据库中.考虑到隐私问题,在本次实验中,我们收集回来的数据都是指纹数据,如图4所示.表中的“fp”字段保存的是指纹,“fp_count”字段保存的是该文件中的总指纹个数,“file”字段保存的是对应的文件名.

图4(Fig.4)

图4 用户数据指纹库 Fig.4 Fingerprint record of user

步骤2. 按字母顺序排序,挑选出一个用户的数据作为即将保存到存储介质上的新数据.

步骤3. 按字母顺序依次选择同组中的其他用户的数据作为比对样本库,从中检索是否存在重复数据, 并记录每轮新发现的重复指纹个数.

步骤4. 重复步骤3,直至队列为空.

步骤5. 重复步骤2,直至队列为空.

步骤6. 结束.

图5为第1组的实验结果,从该图中可以清晰地看出:颜色相同的两个用户之间存在着大量的重复数据,例如ckf67256,tkf19191,wkf37536;而颜色完全不同的用户之间,除首轮对比外,其余轮次发现的重复数据几乎为0,例如tkf19191与h00215997.不过,在数据量非常大的情况下,即使两个用户之间工作交集很弱也会存在一定数量的重复数据.例如,l00125017与每个实验对象都存在一定数量的重复数据,因为l00125017的总数据量大约是其他实验对象的10倍左右.

图5(Fig.5)

图5 每轮检索新发现的重复指纹数(新发现的指纹数=Cn-Cn-1,Cn为第n轮发现的重复指纹总数) Fig.5 Testing result of the first group of experiment (new found duplicate FPs number=Cn-Cn-1,Cn is the amount of duplicate FPs which be found at nth round)

如果去掉样本总数的影响,进行归一化处理后,则会如图6所示那样:工作交集越大,则单位样本数据的重复数据率越高.

图6(Fig.6)

图6 单位样本数据的重复数据率 Fig.6 The duplicate data rate of unit sample data

为了进一步分析数据的重复规律,我们统计分析了每个vDisk上的主要数据类型并按数据量进行排序,见表2.从该表中可以清晰地看出:vDisk上的数据主要由操作系统(exe,dll)、办公软件(exe,dll,xml)、开发工具(yaml,manifest)、项目代码(rb,tc,svn-base)、项目文档(PPT,txt)和用户个人数据(我们将与工作无关的数据都定义为个人数据,包括个人文档、邮件、音乐、视频、游戏等)组成,可以用公式(1)表示.

表2(Table 2)

表2 各种类型文件的数据总量(仅摘录部分)Table 2 The amount of data (TOP 12) 按数据量排序 Ext q00104429 (M) ckf67256 (M) tkf19191 (M) h00200077 (M) 1 svn-base 20 699 1 539 226 64 376 2 tc 15 943 5 5 59 679 3 dll 18 031 482 14 366 24 121 4 rb 18 434 3 43 30 928 5 DLL 3 281 482 14 366 24 121 6 html 30 917 77 635 8 728 7 xml 8 881 663 7 691 20 880 8 manifest 11 120 4 9 308 12 162 9 XML 356 663 7 691 20 880 10 txt 8 784 946 4 288 12 097 11 exe 4 633 1 947 9 361 9 664 12 gif 3 628 2 688 6 063 12 377 13 yaml 22 780 0 2 1 274 14 GIF 381 2 688 6 063 12 377 15 EXE 349 1 947 9 361 9 664 16 PPT 10 650 6 3 202 4 100

表2 各种类型文件的数据总量(仅摘录部分) Table 2 The amount of data (TOP 12)

假设两个vDisk之间各类数据存在重复数据的概率分别为[p1,p2,p3,p4,p5,p6],且数据量如图7所示(备注:该数据来自100个vDisk的统计结果),则vDisk_i的重复数据总量D_dup可用如下公式表示:

图7(Fig.7)

图7 vDisk中各类数据平均占比图,统计范围为100 个vDisk Fig.7 The value of Pi of the first group experiment

将两个vDisk的不同类型数据进行两两对比:user1.os_data/user2.os_data,user1.office_tools/user2.office_ tools,…,则可得到如图8所示的统计结果.从图8可以清晰地看到,P_i之间的变化趋势存在一定的关联关系. (p1,p2)经常呈联动性变化,即:p1下降则p2同步下降,p1上升则p2上升,且幅度也经常保持一致;而(p3,p4,p5)之间也存在类似规律;但p6与前面所述两组之间没有明显的关联关系.

图8(Fig.8)

图8 Pi统计结果,Pi统计结果, Fig.8 Average percent of data by type (counting 100 vDisks)

影响P_i分布的原因总结于表3.

表3(Table 3)

表3 影响Pi分布的原因总结Table 3 The reasons of influence the value of Pi 子项目 可选值范围 重复概率分析 p1: 操作 系统 Windows系列: {Windows XP,Windows 7, Windows 2000,Windows Server 2003} Linux系列:{SuSe,Ubuntu,RedHat},... 操作系统由企业统一购买,一般只有有限的几个版本.目前, 华为VDI系统仅提供了Windows 7和Linux SUSE两个版本, 相同操作系统之间可能会因为补丁或版本差异而导致一定的 差异,所以p1的取值范围一般保持在0或1两个极端 p2: 办公 软件 {Office系列},{Adobebat系列}, Lotus, UltralEdit, Source insight, EA,… 办公软件由企业统一购买,可选范围大于操作系统.所以p2的值一般 要小于p1,但在总趋势上会与p1保持一致.因为操作系统与办公软件 总体上是配套的,例如Windows XP+Office 2003,Windows7+Office 2007 p3: 开发 工具 {Visual Studio系列}, {Eclipse系列}, {华为公司自研的开发平台},… 开发工具可选择的空间较小,一般与项目强相关,要么使用 C/C++的开发工具,要么使用Java开发工具,所以p3的 取值范围也非常小,要么很大,要么很小 p4: 项目 代码 变化范围大 开发工具会决定项目代码之间的重复度,如果开发工具不一样 (p3很小),则项目代码之间的重复度一定会很小(p4的值也很小); 如果开发工具一样,则p4的值由具体项目来决定 p5: 项目 文档 变化范围大 与具体项目相关,从事相同项目的 两个人之间的数据的重复概率高 p6: 个人 数据 变化范围大 一般而言,同一个部门的同事之间的重复数据概率要高于非同一个 部门的同事.因为共同的部门活动,会产生大量相同的照片和视频数据, 而工作相关性又会让他们之间产生大量的相同邮件数据

表3 影响Pi分布的原因总结 Table 3 The reasons of influence the value of Pi

综合上述实验结果和分析,我们可以得到如下结论:两个vDisk之间存在重复数据的总量由样本库的数据总量和重复概率p_i共同决定.p_i中,[p1,p2]的取值主要由企业的软件采购策略决定,相对稳定;而[p3~p6]则相对复杂,主要由这两个vDisk拥有者的工作相关度、兴趣爱好、地理位置等因素综合决定.如果我们将后者统称为用户的相关度R_relationship,并将操作系统和办公软件对应的数据统称为part1,其余数据统称为part2,将公式(2)简化,则可得到公式(3).

其中,a为异常因子,取值范围为{0,1},用于排除一些异常的情况,例如工作语言(中文/英文).因为在实验中发现:即使两个人隶属于同一个部门,工作相关度非常高,但如果使用的工作语言不一样,则其重复数据的概率会大幅度降低.

有了公式(3)之后,我们再来审视实验结果(如图6所示),就不难理解为什么没有任何工作交集的两个用户在首轮测试时还是能找到一部分重复数据.因为D_part1部分的重复数据与用户从事什么样的工作无关,但经过首轮筛选后,剩下的主要是从D_part2中检索到的重复数据,这时会受R_relationship的影响,没有任何工作交集的两个人之间的相关度有可能为0,从而检索出来的重复数据总量也会非常少.

云计算内嵌分布式重复数据删除系统部署在Hypervisor与cache之间,由一个或多个server组成一个集群(如图9所示).VM写入磁盘的数据都先缓存到写缓存中,由写缓存将数据对齐1M后,再发送给重复数据删除引擎.重复数据删除引擎从任务队列中按照同一个用户数据集中处理和FIFO(first input,first output)策略,依次对即将下盘的数据进行删冗计算,然后,将新数据写入到后端主存储vVol(virtual volume,虚拟卷)中(虚拟卷)技术最早由VMware公司提出,目前已在SNIA标准化.该技术是架设在虚拟机和存储之间的一座桥梁,让每一个vDisk都可以对应到存储阵列中的一个vVol上,让虚拟磁盘成为存储管理和存储策略的基本单元).当VM需要读取数据时,如果读缓存命会失败,则该读命令会先下发给重复数据删除引擎,由重复数据删除引擎剥离引用关系后,从正确的位置读取数据并反馈给VM.

图9(Fig.9)

图9 云计算内嵌分布式重复数据删除系统架构 Fig.9 The architecture of vDedup system

首先构建如图10所示的用户特征库,该特征库的数据来自两个部分:一部分直接从VDI系统的注册信息中获取,例如用户注册时填写的工作部门、工作时间、操作系统类型等注册信息;另一部分则需要采用用户标签自动生成算法^[24]计算得到,例如用户的兴趣爱好特征.值得注意的是:特征库有一个逐步完善的过程,在数据量较少的时候,其特征信息主要来自用户的注册信息;在数据积累到一定阶段后,则可通过用户标签自动生成算法不断增加新的特征,实现更小粒度的分类聚合.R_relationship计算使用算法1.

图10(Fig.10)

图10 用户特征库 Fig.10 The user profiles library

算法1. 用户相关度计算算法(user relationship evaluation algorithm,简称UREA).

输入:User_Profiles_DB(用户特征库),user_ID1,user_ID2,mask_code(特征掩码);

输出:R_relationship值 //用户1与用户2之间的相关度.

1. 从n个特征项中,将影响数据量的多少作为挑选原则,选出影响数据量最大的前4个特征项作为比对项,

放入数组变量profiles_list中;

2. i=R_relationship=0; //初始化变量

3. WHILE profiles_list is not EMPTY DO //为每一个特征项设置权重

4. weight[i] = data_i Σdata ;; //

5. END

6. profiles1=User_Profiles_DB.find(user_ID1) && mask_code; //获取user1,user2的特征码,并与掩码做

与运算

7. profiles2=User_Profiles_DB.find(user_ID2) && mask_code; //掩码用于动态调整需要检索的范围

8. FOR i=0 IN 1,…,4 //依次比对用户的特征值,如果相同,则累加上其对应的权值

9. IF profiles1[i]==profiles2[i] THEN

10. R_relationship=R_relationship+weight[i];

11. END

12. return R_relationship

13. END

在算法1中,每个特征项对应的权重设置非常重要.例如,在企业的VDI系统中,个人数据占比一般不到40%,所以与之对应的个人兴趣爱好等特征项的权重就不能超过0.4;但在教育行业的VDI系统中,个人数据则有可能高达90%,此时,个人兴趣爱好特征项的权重则需要超过工作特征的权重.

用户感知的重复数据删除算法由两部分组成.

· 第1部分负责实现指纹数据的自动聚合存储,如图11所示,系统首先会根据用户相关度将用户进行分组,并将同一组用户对应的指纹数据都集中存储在同一个节点上.当数据到达重复数据删除引擎时,重复数据删除引擎首先根据该数据的user_ID进行路由,从而将待查重的指纹集路由到正确的处理节点上;

图11(Fig.11)

图11 检查重复指纹处理流程图 Fig.11 The proceeding of identifying duplicate data of vDedup

· 当待查重的指纹集到达处理节点后,用户感知的重复数据删除算法第2部分(核心算法)将会被执行,处理过程如算法2所述.

算法2. 用户感知的重复数据删除算法(user-aware deduplication algorithm,简称UADA).

输入:user_ID,mask_code,FP_list(待查重指纹列表),User_Profiles_DB(用户特征库),l(最小相似度阈值);

输出:Dup_list(重复数据块列表),Unique_list(非重复数据块列表).

1. BEGIN

2. i=0,R_relationship[User_Profiles_DB.size]=0,User_list=[] //初始化相关变量

3. WHILE i<User_Profiles_DB.size DO //遍历用户特征库,分别计算源用户与目标用户之间的相关度,并将大于阈值的用户添加到候选查找用户列表中

4. R_relationship[i]=UREA(User_Profiles_DB,user_ID,User_Profiles_Database[i].User_ID,mask_code);

5. IF R_relationship≥l THEN

6. User_list.push(User_Profiles_DB[i].User_ID,R_relationship[i])

7. i++;

8. END

9. User_list SORT BY 用户相关度and指纹数量; //按用户相关度进行降序排序,相关度相同的按指纹数量降序排序

10. //下面开始在选定的用户范围内进行查重

11. i=0,DupFP_temp_list=DupFP_list=[];

12. WHILE i<User_list.size and !FP_list.empty() DO

13. DupFP_list=FP_listÇUser_list[i].FP_list; //将源指纹与目标指纹做交集运算,检索出重复指纹

14. FP_list=Fp_list-DupFP_list; //过滤掉从当前用户中检索到的重复指纹,仅将为检索到的数据进入下一轮对比

15. DupFP_temp_list=DupFP_temp_list+DupFP_list; //将检索到的重复指纹添加到重复数据块列表中

16. END

17. DupFP_list=DupFP_temp_list;

18. Unique_list=FP_list-DupFP_list;

19. RETURN DupFP_list,Unique_list

20. END

在UADA算法中,仅从每个用户组中挑选出一个代表用户的指纹常驻内存,所以常驻内存的指纹数量与用户组的数量和每个vDisk的平均数据量成正比,如公式(4)所示.

如果以工作相关度作为计算用户相关性的主要特征项,则一个企业的用户组个数将与该企业的最小部门数相等.根据沃顿商学院的管理学教授J.S.Mueller的研究,一个团队的最佳人数是5~11人(建设团队的最佳人数可见http://yingyu.100xuexi.com/view/examdata/20100611/5DF7D5FF-6832-4BF5-BC32-77957C870DBD.html),则检测重复指纹时,需要从磁盘读取的数量在最好情况下为0(在常驻内存的指纹集中全部命中),最差的情况下需要读入n-2个用户的指纹集.以华为公司的VDI系统为例,每个vDisk的容量为500G,segment_size为1M,总共15万员工,每个团队的成员数通常在7人左右,采用SHA-1算法(计算出来的指纹长度为20byte),则常驻内存的指纹总量仅为200G左右,单次检索最差情况下需要读入5M指纹数据.所以,UADA算法的空间复杂度仅为S(n),n为用户组数量.这表明:在部门数量不增加的情况下,即使vDisk增加,常驻内存指纹数量也不会增加.如图12所示,UADA算法中的重复指纹检索部分的时间开销为O(log₂n),n=(最小部门人数x平均指纹数量).在用户相关度计算部分,因为需要计算两两用户的相关度,所以计算复杂度为O(n²).但在实际应用中,用户相关度不需要实时计算,仅在新增用户或定时刷新时才需要重新计算,所以该部分的时间开销可以忽略不计.

图12(Fig.12)

图12 The flowing of user-aware deduplication algorithm Fig.12 用户感知的重复数据删除算法流程图

我们的实验在由3台服务器和1台SAN存储阵列组成的OpenStack云平台上进行.3台服务器分别配备了英特尔酷睿2双核E7400 2.8GHz CPU,4GB DDR-II内存和一个32GB的SSD缓存盘.SAN存储阵列为华为的S5500T、50T存储空间、RAID5.所有的机器均采用Ubuntu 10.04.2的64位服务器版作为操作系统,OpenStack的组件部署如图13所示.

图13(Fig.13)

图13 实验部署图 Fig.13 The deployment of test-bed

此外,3台机器间均通过千兆以太网交换机连接.因此,我们假设网络传输开销对实验的性能不产生影响.

为了验证UADA算法在整个云计算系统实际应用中的效果,我们直接采用LoginVSI测试工具分别测试VDI系统在安装了UADA,OpenDedup和lessFS这3种重复数据删除算法情况下各自的性能表现.测试数据来自前面收集的100个vDisk.测试过程如下:

第1步. 执行Login VSI工具,监测VDI系统的I/O响应时间;

第2步. 按vDisk编号顺序依次将vDisk上的数据迁移到测试环境的服务器上,并激活该VM;

第3步. 统计分析测试结果.

从图14可以清晰地看出:在UADA算法测试过程中,随着VM数量的增加,VDI系统的最大响应时间基本保持稳定,都控制在最佳用户体验范围内(响应时间<4800ms);但在OpenDedup算法中,当指纹数量达到最大可用内存的临界值时,VDI系统的响应延迟时间突然增加3倍左右,达到9 000多ms;lessFS在本次测试中表现最差,当VM数量达到27个时,VDI系统的响应时延就已超出4 800ms,不仅平均响应时延最大,而且表现极不稳定(这也说明,依赖数据的空间局部性特征设计的重复数据删除算法不适合应用在主存场景下).所以从最终应用效果来看,UADA算法在性能上有非常大的改进,尤其是它的性能不随数据总量的增加而降低这一特点,是其他算法所不具备的.

图14(Fig.14)

图14 性能测试对比图 Fig.14 The performance testing result

在第1节中我们曾分析过,影响重复数据删除算法性能的主要瓶颈之一是检索重复指纹时产生的大量磁盘读I/O操作.所以在上述实验中,我们特别统计了3种算法在检索重复指纹时累计发出的读指纹操作指令数.如图15所示,UADA算法产生的读I/O操作数量基本上都保持在较低的水平上,几乎保持在一个常量范围,产生毛刺的地方都是在调整常驻内存的用户指纹的时候,因为在本系统中我们设计了一个自动校正模块,该模块每隔一段时间就会自动推荐每个用户组中拥有指纹数量最多的用户成为该用户组的新代表,并自动将该用户的指纹数据导入内存中,所以在每次更新时会产生大量读操作.与UADA算法相比,在常驻内存指纹总量未超过可用内存总量时,OpenDedup的读操作数量是随数据量的增加而缓慢增加的,其总值大约是UADA的两倍;但当vDisk数量达到69个时,两者之间的差距瞬间增大到8倍左右.

图15(Fig.15)

图15 读磁盘次数对比图 Fig.15 The migration time of each VM,under in different deduplication system

除性能上的改善以外,UADA算法在重删率上也达到了不错的效果,见表4.所以综合来看,UADA算法与现有的重复数据算法相比有较大的改进,特别是在存储海量数据时具有较为突出的优势.

表4(Table 4)

表4 重删率统计Table 4 The total reduction @ different deduplication algorithm Algorithm (chunk@64k) Source data (GB) Target data (GB) Total reduction (%) UADA 117 145.652 57 401.369 51.01 OpenDedup 117 145.652 55 175.602 53 lessFS 117 145.652 65 953.002 43.71

表4 重删率统计 Table 4 The total reduction @ different deduplication algorithm

在主存场景中,用户体验的优先级要远大于节省存储空间的优先级.所以在前面的UADA算法中,我们设计了一个特征掩码来动态调整存储系统的性能与重删率,这样就可以避免与生产系统竞争计算资源,优先保障了生产系统的响应时间.在下面的实验中,我们分别测试了l=1和特征掩码为[255.255.255.255,255.255.255.0,255.255.0.0,255.0.0.0,0.0.0.0]这5种情况下的重删率和性能.0.0.0.0是一个特殊掩码,表示仅与UserGroup常驻内存的指纹进行对比,一般在 CPU负载超过60%时被激活.测试结果见表5:当所有检索过程全部在内存中完成时,响应时间最短,仅为1 143ms;但与最佳重删率相比,在本轮实验中遗漏了6.81%的重复数据.当特征掩码为255.255.0.0和255.0.0.0时,VDI系统的平均响应时间超出了用户能够忍受的4 800ms时延范围.仅有当特征掩码为255.255.255.255,255.255.255.0和全0时,VDI系统才能正常工作.从测试结果来看,特征掩码可以很好地达到主存场景下通过动态调整特征掩码来优先保障生产系统性能的目标.

表5(Table 5)

表5 不同特征掩码情况下的重删率和响应时间测试结果汇总表Table 5 The total reduction @ different mask_code Total reduction (%) Average response time (ms) 第1轮(255.255.255.255) 51.01 2 143 第2轮(255.255.255.0) 53.30 3 178 第3轮(255.255.0.0) 55.28 4 922 第4轮(255.0.0.0) 56.11 7 564 第5轮(0.0.0.0) 49.30 1 143

表5 不同特征掩码情况下的重删率和响应时间测试结果汇总表 Table 5 The total reduction @ different mask_code

随着数据的快速增加和绿色IT进程的不断推进,重复数据删除技术将会成为网络存储领域的核心技术.从目前的研究情况来看,分组检索是提升重复指纹检测性能的有效方法之一.而基于数据用户局部性特征的指纹分组检索具有实现简单、计算量小且误报率低的特点,并支持动态调整性能,将具有很好的工业应用价值.目前,UADA算法已申请专利(公开号:CN103902686A),并正在应用到新产品中.在接下来的工作中,我们将重点投入到用户标记算法的设计以及不同云计算用户群体所对应的数据特征模型的分析中,从而帮助UADA算法实现更加精准的重复指纹检索.

致谢 感谢华为同事提供的大量实验数据和在异常数据甄别过程中所提供的帮助.