云数据中心下重复数据删除技术研究

杜 华，刘华春

(1.核工业西南物理研究院，四川 成都 610000；2.成都理工大学 工程技术学院，四川 乐山 614000)

0 引 言

重复数据删除技术是一种数据缩减技术，常用于基于磁盘的备份系统中，旨在减少存储系统中使用的存储容量。以往的重复数据删除系统往往采用单服务器结构，具有配置简单、易于管理的优点[1]。

近年来，随着云计算、大数据技术的发展，企业数据中心存储的需求量日益庞大[2]。据国际数据公司(IDC)统计[3]，全球数据总量预计2020年达到44 ZB，中国数据量将达到8 060 EB，占全球数据总量的18%。因此，重复数据删除技术需要向分布式存储结构转变[4]，以适应云数据中心环境下的按需获取、弹性增长、快速部署等多方面要求。

1 重复数据删除技术综述

重复数据删除技术是一种基于数据自身的冗余度来检测数据中是否有相同的对象，然后只传输和(或)存储唯一的数据对象副本的数据去冗余技术。根据不同的区分原则，一般可以把重复数据删除技术进行不同的分类。该技术的主要工作原理如图1所示。

图1 重复数据删除技术工作原理示意

在单一存储结构形式下[5]，平均响应时间、I/O吞吐量和重复率是评价重复删除系统效率的三个重要指标。

(1)平均响应时间：是指完成单位大小的数据块重复删除操作所需要的平均延迟时间。这个时间包括对数据块指纹进行内存查询和磁盘查询的开销，以及查询失败之后的存储开销。平均响应时间越短，重复数据删除系统效率越高。

(2)I/O吞吐率：是指单位时间内传输的数据量。由于重复删除系统要在正常的数据读写时间之外，额外增加了重复删除的操作，因此比起单纯的磁盘数据传输，吞吐率会有所降低。吞吐率越高，重复数据删除系统效率越高。

(3)冗余度：冗余度也称重复率，是指应该删除的重复数据字节数与未删除之前的全部数据字节数的比值。一般来说，冗余度越高，重复数据删除的经济效益越好。

2 云存储环境下的重删系统

在云数据中心存储环境下，数据存储有两个显著变化：

第一，云存储是由大量的廉价存储设备构成的庞大存储中心，具有离散性和低可靠性的特点，需要依赖特别的方法将这些廉价设备聚合成一个高可靠性、高扩展性的资源池。因此，对单独某个廉价设备的评价指标，并不适合直接用于评价存储结构整体的存储性能表现。

第二，云存储是直接面向用户评价的，挑剔的云用户要求云存储具备历史数据版本多、数据保存期延长、备份时间窗口缩短和实时故障恢复要求高四个特点[6]，评价指标需要考虑这些新增的评价维度。

单一存储和云存储的区别如表1所示。

表1 单一存储和云存储的区别

由此可见，云数据中心下的重复数据删除技术，必须在原有机制下进行改进，提高执行效率、缩短操作时间，并且保证数据可靠性。

2.1 指纹查询模式改进

在云数据中心下，数据量大幅度提升，单一服务器下TB规模的数据量，在云数据中心下可能达到PB级别规模，直接导致指纹库的增大。从而对数据块指纹查询提出新的要求。

以重复数据删除系统的指纹库设计为例。1 TB数据量的单一服务器下，按照每个数据块固定大小为4 MB进行切分，且每个数据块的数据指纹是64 bit(8 Byte)，那么指纹库的大小只有2 MB，这就可以将指纹库常驻内存中，从而减少平均响应时间。

但是当数据量达到1 PB规模时，同样的指纹库将达到2 GB，如果继续将指纹库常驻内存，就必须占据较大的内存资源，影响云服务的SLA(service level agreement，服务等级协议)。

所以，为了保证云用户的SLA，提高服务响应速度，在云数据中心环境下，需要兼顾数据块切分和指纹库查询的综合效率，而不能照搬单一服务器存储结构下的模式。

2.2 数据容错机制改进

在云数据中心环境下，分布式存储规模不断增大，云数据中心采用虚拟化技术，将数以万计的服务器共同构成一个资源存储池，用户按需申请。每个用户的数据，可能存放在多个不同的物理服务器上，一个物理服务器中也可能保存着多个用户的数据。因此，跨网络、跨服务器形势下的数据容错问题就变得比较复杂。

数据容错机制一般可以分为两种：基于复制的数据容错和基于纠删码的数据容错。在单一存储结构下，数据容错基本上可以简单采用基于复制的策略来完成，以更多的空间消耗来保障可靠性。在云数据中心下，本身巨大的数据量直接造成基于复制的备份技术成本倍增，更多的存储设备不但意味着更多的设备成本，还意味着更多的人力、电力、管理等运维成本，这常常是企业不得不考虑降低的资源消耗。所以，基于纠删码的数据容错逐渐为大家所重视。

2.3 资源可扩展性改进

存储设备的扩展，一般分为垂直扩展和水平扩展两种方式。垂直扩展是指对原有设备进行替换，用新的、性能更高的设备来替代原有设备。水平扩展是指在原有设备的基础上，通过更新或是添加部件的方式提升原有存储设备的性能。

在单一存储结构服务器中，水平扩展的次数是比较有限的，大多数情况下只能选择垂直扩展的方式，这降低了设备的利用率。

云数据中心模式下，可以通过增加同构(或异构)设施设备的方式近乎线性地扩充IT资源，而且扩展的过程中，不需要停止目前正在进行的服务。这种水平扩展的方式，正是云计算区别于其他计算范式的重要特点之一。

所以，为了适应新的计算范式，云数据中心环境下的重复删除技术还要具备可水平扩展的能力，且在扩展的情况下尽可能做到“数据本地化与负载均衡”的兼顾

3 云存储环境下重删系统加速技术

根据前面对云存储环境下重复删除技术的新要求，需要有针对性地设计加速技术，使得重删系统可以更加有效地迁移到云存储环境下。应该从以下几个方面开展研究。

3.1 指纹查询优化

3.1.1 算法优化

由于指纹库的增大，只能将指纹库中的一部分置入内存，显然的是，如果置入部分选择得当，那么查询命中率高，可以在一定程度上节约查询时间。理想状态下，应该选择那些最近最有可能被查询的指纹来置入内存。

凭空预测即将查询哪一个数据块的指纹是没有道理的，但是云计算的VIM(virtual instrument monitor，虚拟设备监控器)采集了大量的虚拟机运行状态数据，可以通过对CPU、内存和磁盘I/O运行状况的监控，收集虚拟机运行数据，并对此进行必要的处理，从而预测哪一个虚拟机可能有重复数据指纹比对的需要，进而提前将该虚拟机数据的相关指纹数据置入内存库中。其工作原理如图2所示。

图2 最近最有可能使用(LPU)查询算法工作原理示意

3.1.2 硬件优化

算法上的优化可以保证尽可能高地提升查询的命中率，但是一旦发生未命中情况，就必然面临额外的磁盘查询和可能的内存换入换出操作，这就不可避免地影响磁盘I/O的速度。

在云数据中心环境下，通常一个物理服务器上会承载多个虚拟机以服务多个不同用户。每个用户的数据在逻辑上虽然是隔离开的，但是实际在物理服务器层面看来，都是存在于一个存储设备中。因此，可以考虑在物理服务器的内存和磁盘设备之间引入SSD作为cache。具体结构如图3所示[7]。

SSD作为一种新型存储介质，跟传统的磁盘相比速度更快，其顺序读写速度约为机械硬盘的3～5倍,随机读写IOPS约为机械硬盘的100～1 000倍[8]。更适用于应对大规模的随机读写I/O负载。所以，如果将指纹库加载到SSD中，即使出现了未命中现象，从SSD中进行指纹查询，在速度上也比磁盘中进行查询更快。

图3 虚拟环境下SSD做cache的结构示意

3.2 基于纠删码的容错机制

在提高存储系统可靠性方面，还有一种普遍采用的技术就是纠删码技术。纠删码技术可以节约磁盘空间，但是计算耗时相对较长，并且任何数据位的变化，都必须重新计算纠删码，所以，对计算所需的时间比起其他重复删除技术而言，没有综合优势，一般只是在空间约束特别严格的环境下才得以使用。

但是云数据中心环境下，计算能力已经不能构成制约，云计算的计算范式跟以往的计算方式相比，计算能力上已经有了巨大的变化，因此，利用纠删码技术来加速重复数据删除方面，就有了新的可能。

但是在错误恢复方面，基于复制的容错和基于纠删码的容错的网络开销差异还是很大。当一个数据块发生错误，基于复制的容错只需要在网络中下载一个同样大小的数据恢复即可。而基于纠删码的方法就要删除k个数据来计算得以恢复，这就需要更多的网络开销，占用更多的内部网络带宽。

因此，还需要进一步降低基于纠删码的数据修复成本，把数据修复所耗费的CPU资源和网络资源降下来，这也是目前研究的热点方向。

3.3 数据去重的方式选择

3.3.1 数据去重的三个类型

数据去冗余的时机一般分为3种[9]：先备份再去重策略(deduplication after backup，DAB)、先去重再备份策略(deduplication before backup，DBB)和边备份边去重策略(deduplication during backup，DDB)。

去冗余的时机选择恰当与否，直接关系到用户体验。根据Aberdeen Group的调查“页面的显示速度每延迟1 s，网站访问量就会降低11%，从而导致营业额减少7%，顾客满意度下降16”；Google发现“相应时间每延迟0.5s，查询数将会减少20%”；Amazon发现“响应时间每延迟0.1 s，营业额下降1%”。下面是三种不同的去冗余方式所占用的总耗时差异对比，如表2所示。

表2 去冗余操作时机选择的耗时区别

三种不同策略的总耗时分别为：

其中：

(1)Td、Ts、Tt分别表示数据块指纹计算的耗时、数据块本地存储的耗时和数据块网络传输的耗时；

(2)n表示需要备份的所有数据的数据块数量，m表示经过指纹比对之后需要更新备份的数据块的数量。显然(n-m)/n就是数据的重复率；

(3)该计算耗时是在假设所有的数据块大小一致的情况下做出的分析结果。基于滑动窗口的耗时分析可以类比得出。

3.3.2 云用户的三种类型

根据用户从云数据中心获取资源的类型不同，通常可以将用户服务的类型分为3类：网络密集型、计算密集型和存储密集型。

网络密集型：此类用户对虚拟网络传输的带宽、延迟要求都很高，而且随着观看直播用户数量的动态变化，负载也会随之波动，一旦负载稍微高出资源承载能力，都会造成视频卡顿，影响用户体验。同时，此类视频数据信息本身冗余度很高，一般而言连续的画面帧之间只有细微的变化，所以，DDB方式是这种情况下的首选。网络直播[10]、视频监控[11]通常属于这种类型。

计算密集型：此类用户通常是批量地将数据输入到虚拟服务器上，然后虚拟服务器自主进行计算，在操作过程中几乎不再与用户产生数据交互。因此，针对这种类型的用户，数据去重的方式可以选择DAB方式，科学计算通常属于这种类型[12]。

存储密集型：此类用户通常是有大量突发性的数据读写需要完成，单次操作所耗费的时间都不是很长，但是对网络带宽要求较高[13]。针对此类用户，数据去重的时机可以根据数据量的大或小来适当地选择DAB或DBB方式，云存储、Web服务通常属于这种类型。

4 结束语

云数据中心环境下的重复数据删除技术，与单一存储结构模式在指纹查询模式、数据可靠性保证和备份方式选择等方面都提出了更多样化的要求，因此，有必要根据云服务的特点来设计具有云特征的重复数据删除技术，从而达到节约提高云数据中心存储效率、提升云用户服务感受的目的。