一种结合指纹抽样和减少数据碎片的数据块路由方法

摘要

本发明提出一种结合指纹抽样和减少数据碎片的用于分布式重复数据删除系统的数据块路由方法。该方法提出对数据块指纹进行抽样，对抽样后的数据块指纹采用布隆过滤器快速地查找重复数据，估算数据重复率，其采用的路由算法结合了数据的重删率、数据节点服务器的碎片量以及存储空间使用率来确定路由节点。与已有的路由方法相比，该方法能提高整个系统的重删率，系统的吞吐率以及数据恢复速度。

说明书

技术领域

本发明属于计算机信息存储技术领域，具体涉及一种分布式的重复数据删除系统内的，结合指纹抽样和减少数据碎片的数据块路由方法。

背景技术

随着大数据时代的来临，数据量的爆炸性增长对数据备份性能的要求越来越高。现有的单服务器重复数据删除备份系统在应对海量数据时，能存储的数据量有限，可扩展性差，系统的吞吐量低，系统整体性能比较差。采用分布式的重复数据删除备份系统，可以有效解决单服务器备份系统存在的问题。

分布式重复数据删除系统中，数据路由是实现全局去重的关键。数据路由主要解决数据块如何路由到各个数据节点服务器的问题。目前分布式重复数据删除系统的数据块路由算法分为无状态数据块路由算法和有状态数据块路由算法。无状态数据块路由算法的本质是以分布式哈希表的方式，将数据块路由到各个数据节点服务器上。此算法不考虑每个数据节点已存储的数据块，即不考虑待路由的数据块与数据节点服务器上已存储的数据块是否重复，以及每个数据块节点服务器的有效剩余存储空间，因此该路由方法能获得的重删率比较低；同时数据分布不均匀，数据负载不均衡。为了克服无状态数据块路由的缺点，有状态数据块路由算法，则根据各个数据节点服务器已存储的数据块以及对应的存储空间使用率来进行数据路由，能获得较高的重删率以及数据的均衡存储。但是目前的有状态数据路由算法获得的系统吞吐量较低，当面对TB级的备份数据时，利用布隆过滤器(Bloom Filter)查找重复数据块的时间需要以小时为单位来计算，同时这两种路由算法均没有考虑各个数据节点服务器上的数据碎片情况，导致系统的数据恢复性能较差。

针对目前分布式重复数据删除系统中数据块路由算法已存在的问题，本发明提出一种结合指纹抽样和减少数据碎片的数据块路由方法，该方法对数据块指纹进行抽样，在每个数据块节点服务器上对抽样后的数据块指纹采用布隆过滤器快速查找重复数据，得到数据重复率，同时结合每个数据块节点服务器的存储空间使用率和数据碎片来确定路由节点。与已有的路由算法相比，该算法 能提高整个系统的重删率，系统吞吐率以及数据恢复速度。

发明内容

本发明提出一种结合指纹抽样和减少数据碎片的用于分布式重复数据删除系统的数据块路由方法。该方法提出对数据块指纹进行抽样，对抽样后的数据块指纹采用布隆过滤器快速地查找重复数据，估算数据重复率，其采用的路由算法结合了数据的重删率、数据节点服务器的碎片量以及存储空间使用率来确定路由节点。与已有的路由方法相比，该方法能提高整个系统的重删率，系统的吞吐率以及数据恢复速度。

本发明涉及到客户端和数据节点服务器。客户端包含指纹处理模块；数据节点服务器包含布隆过滤器查找模块、碎片查找模块、去重模块。数据节点服务器维护了布隆过滤器、数据指纹索引表。

指纹处理模块：使用数据块变长算法对备份数据流进行分块，得到一定平均长度(如平均长度4KB)的数据块，使用哈希算法(如SHA-1哈希算法)对每个数据块计算指纹，按照备份数据流中数据块出现的顺序，指纹处理模块将连续数据块依次合并为较大的块，生成一定平均长度(如平均长度为1MB)的合并块，将合并块对应的指纹按固定的采样率(如1/2^B)进行等距采样，将采样后的指纹发送给数据节点服务器。

布隆过滤器查找模块：布隆过滤器是由一个很长的二进制向量和一系列随机映射函数组成，是一种空间效率很高的随机数据结构，它利用位数组简洁地表示一个集合，并能判断一个元素是否属于这个集合，在每个数据节点服务器上，已存储的数据块的指纹全部映射到布隆过滤器结构中。对于客户端发送的数据块指纹，布隆过滤器查找模块在布隆过滤器中查找是否存在相同的数据块指纹，得到相同数据块指纹的数量，即重复数据块指纹的数量。并计算指纹重复率D_N(即指纹序列中重复的指纹数量与指纹序列所有的指纹数量的比值)和数据节点服务器的存储空间使用率U_N(即数据节点服务器已使用的存储空间和节点最大可使用的存储空间的比值)的比值R_N，R_N＝D_N/U_N，将得到的R_N值发送给客户端。

碎片查找模块：数据在备份时，删除重复数据块后使逻辑上连续的数据块在物理地址上不连续，导致数据恢复时，需要多次的磁盘随机读取操作和磁盘寻道操作，数据恢复性能很低。这些逻辑上连续但是物理地址上不连续的数据块被称为碎片。碎片查找模块即在数据节点服务器上查找对应的碎片数量，并将查找结果返回给客户端。

去重模块：去重模块对接收的指纹在数据指纹索引表(数据指纹索引表维护数据节点服务器的全部指纹、对应的数据块存储地址和数据块引数)中查找是否存在重复的数据块指纹，若存在，则删除指纹对应的数据块，更新数据指纹索引表的块引用数；若不存在，则向客户端索取对应的数据块，将对应的数据块存放在数据节点服务器的数据区域，并将该数据块的指纹，存储地址，以及块引用数添加至数据指纹索引表中。

分布式重复数据删除系统备份的主要流程为：

(1)客户端接收用户需要备份的数据流。

(2)客户端的指纹处理模块对接收到的数据流进行预处理，具体步骤为：

(2.1)指纹处理模块使用数据块变长算法(如Rabin Fingerprint)对备份数据流进行分块，得到一定平均长度(如平均长度4KB)的数据块；指纹处理模块使用哈希算法(SHA-1)计算每个数据块的指纹。

(2.2)按照备份数据流中数据块出现的顺序，指纹处理模块将连续的数据块依次合并为较大的块，生成一定平均长度(如平均长度1MB)的合并块。

(2.3)将合并块对应的指纹序列，按固定的采样率(如1/2^B)进行等距抽样，生成新的指纹序列，将新的指纹序列发送给各个数据节点服务器。

(3)数据节点服务器接收指纹序列，数据节点服务器的布隆过滤器查找模块和碎片查找模块对接收到的指纹序列进行处理并确定最终路由的数据节点服务器，具体步骤为：

(3.1)数据节点服务器的布隆过滤器查找模块对接收到的指纹序列进行布隆过滤器查询，得到重复数据块指纹的数量，并计算指纹重复率D_N(即指纹序列中重复的指纹数量与指纹序列所有的指纹数量的比值)，存储空间使用率U_N>N和存储空间使用率U_N的比值R_N，R_N＝D_N/U_N,数据节点服务器将得到的R_N值发送给客户端。

(3.2)客户端接收每个数据节点服务器的R_N值，将步骤(2.2)中得到的合并块的所有指纹发送给R_N值最高的K个数据节点服务器。

(3.3)数据节点服务器接收到客户端发送的所有数据块指纹之后，采用碎片查找模块进行数据碎片的查找，并将对应的数据碎片量返回给客户端。

(3.4)客户端接收到步骤(3.3)所述的K个数据节点服务器的碎片量之后，选择碎片量最少的一个数据节点服务器，作为最终路由的数据节点服务器。

(4)客户端将步骤(2.2)中得到的合并块的所有数据块指纹序列，发送给步骤(3.4)得出的数据节点服务器，去重模块对接收的指纹在数据指纹索引表中查找是否存在重复的数据块指纹，若存在，则仅更新数据指纹索引表的块引用数；若不存在，则向客户端索取对应的数据块，将对应的数据块存放在数据节点服务器的数据区域，并将该数据块的指纹，存储地址，以及块引用数添加至数据指纹索引表中。

本发明具有如下的特点：

(1)客户端的指纹处理模块对用户数据处理时，进行了数据块的合并和指纹的抽样处理。由于数据节点服务器只对从客户端发来的部分指纹采用布隆过滤器进行查询，因此提升了系统的吞吐量，避免指纹查询所需的计算和内存瓶颈。

(2)在确定数据块路由节点时，本发明优先考虑重删率，但同时也考虑到了各个节点的存储空间利用率和磁盘碎片情况，使系统在获得较高的重删率的同时，能进行负载均衡以及获得较好的数据恢复性能。

附图说明

图1为本分布式重复数据删除系统的模块结构示意图；

图2为本分布式重复数据删除系统备份的流程示意图；

具体实施方式

本发明涉及的主体有客户端，数据节点服务器。客户端为备份数据流的接收方，数据节点服务器用来存储备份数据流的所有数据块。

图1为本分布式重复数据删除系统的结构示意图。分布式重复数据删除系统包括客户端100、数据节点服务器200；客户端100的模块为指纹处理模块110，数据节点服务器200的模块为布隆过滤器查找模块210、碎片查找模块220、去重模块230。数据节点服务器200维护了布隆过滤器、数据指纹索引表。指纹处理模块110：使用数据块变长算法对备份数据流进行分块，得到一定平均长度(如平均长度4KB)的数据块，使用哈希算法(如SHA-1哈希算法)对每个数据块计算指纹，按照备份数据流中数据块出现的顺序，指纹处理模块110将连续数据块依次合并为较大的块，生成一定平均长度(如平均长度为1MB)的合并块，将合并块对应的指纹按固定的采样率(如1/2^B)进行等距采样，生成新的指纹序列，将新的指纹序列发送给数据节点服务器200。布隆过滤器查找模块210：布隆过滤器是由一个很长的二进制向量和一系列随机映射函数组成，是一种空间效率很高的随机数据结构，它利用位数组简洁地表示一个集合，并能判断一个元素是否属于这个集合，在每个数据节点服务器上，已存储的数据块的指纹全部映射到布隆过滤器结构中。对于客户端发送的数据块指纹，布隆过滤器查找模块210在布隆过滤器中查找是否存在相同的数据块指纹，得到相同数据块指纹的数量，即重复数据块指纹的数量。并计算指纹重复率D_N(即指纹序列中重复的指纹数量与指纹序列所有的指纹数量的比值)和数据节点服务器200的存储空间使用率U_N(即数据节点服务器已使用的存储空间和节点最大可使用的存储空间的比值)的比值R_N，R_N＝D_N/U_N,数据节点服务器200将得到的R_N值发送给客户端100。碎片查找模块220：数据在备份时，删除重复数据块后使逻辑上连续的数据块在物理地址上不连续，导致数据恢复时，需要多次的磁盘随机读取操作和磁盘寻道操作，数据恢复性能很低。这些逻辑上连续但是物理地址上不连续的数据块被称为碎片。碎片查找模块220即在数据节点服务器上查找对应的碎片数量，并将查找结果返回给客户端。去重模块230：去重模块230对接收的指纹在数据指纹索引表(数据指纹索引表维护数据节点服务器200的>

图2为本发明中数据备份的流程示意图，具体为

(1)客户端100接收用户需要备份的数据流。

(2)客户端100的指纹处理模块110对接收到的数据流进行预处理，具体步骤为：

(2.1)指纹处理模块110使用数据块变长算法(如Rabin Fingerprint)对备份数据流进行分块，得到一定平均长度(如平均长度4KB)的数据块；指纹处理模块110使用哈希算法(SHA-1)计算每个数据块的指纹。

(2.2)按照备份数据流中数据块出现的顺序，指纹处理模块110将连续的数据块依次合并为较大的块，生成一定平均长度(如平均长度1MB)的合并块。

(2.3)将合并块对应的指纹序列，按固定的采样率(如1/2^B)进行等距抽样，生成新的指纹序列，将新的指纹序列发送给各个数据节点服务器。

(3)数据节点服务器200接收指纹序列，数据节点服务器200的布隆过滤器查找模块210和碎片查找模块220对接收到的指纹序列进行处理并确定最终路由的数据节点服务器，具体步骤为：

(3.1)数据节点服务器200的布隆过滤器查找模块210对接收到的指纹序列进行布隆过滤器查询，得到重复数据块指纹的数量，并计算指纹重复率D_N(即指纹序列中重复的指纹数量与指纹序列所有的指纹数量的比值)，存储空间使用率U_N(即数据节点服务器200已使用的存储大小和节点最大存储空间大小的比值)，以及重复率D_N和存储空间使用率U_N的比值R_N，R_N＝D_N/U_N，数据节点服务器200将得到的R_N值发送给客户端。

(3.2)客户端100接收每个数据节点服务器200的R_N值，将步骤(2.2)>N值最高的K个数据节点服务器200。

(3.3)数据节点服务器200接收到客户端100发送的所有数据块指纹之后，采用碎片查找模块220进行数据碎片的查找，并将对应的数据碎片量返回给客户端100。

(3.4)客户端100接收到步骤(3.3)所述的K个数据节点服务器200的碎片量之后，选择碎片量最少的一个数据节点服务器200，作为最终路由的数据节点服务器200。

(4)客户端将步骤(2.2)中得到的合并块的所有数据块指纹序列，发送给步骤(3.4)得出的数据节点服务器，去重模块230对接收的指纹在数据指纹索引表中查找是否存在重复的数据块指纹，若存在，则仅更新数据指纹索引表的块引用数；若不存在，则将向客户端索取对应的数据块，将对应的数据块存放在数据节点服务器的数据区域，并将该数据块的指纹，存储地址，以及块引用数添加至数据指纹索引表中。