CN103631933A - 一种面向分布式去重系统的数据路由方法 - Google Patents

Abstract

本发明提供一种面向分布式去重系统的数据路由方法，包括：服务器将构成数据的所有数据块的指纹进行分类，并且将不同类别的指纹分别发送到存储相应类别指纹的数据摘要的不同摘要存储节点。以及，在所述摘要存储节点中查询接收到的指纹，得到该指纹在每个去重节点的命中分数，将该命中分数返回所述服务器。方法还包括所述服务器根据每个指纹在每个去重节点的命中分数得到每个去重节点的汇总分数，将该汇总分数结合每个去重节点的存储状况确定目标去重节点。本发明在实现去重效果与存储利用率的平衡的同时，有效抑制了指纹查询过程中通信和计算开销，提高了分布式去重系统的数据路由的可扩展性。

Description

一种面向分布式去重系统的数据路由方法

技术领域

本发明总体涉及重复数据删除技术，具体而言，涉及一种面向分布式去重系统的数据路由方法。

背景技术

人类进入数字信息化时代以来，大量信息已被记录成数据。从衣食住行基本的生活需求到教育医疗和商业领域，从传统的互联网到由智能手机发展起来的移动互联网，越来越多的人和设备参与到数据的创造中来，每年产生的数据总量呈现爆炸式增长。与此同时，由于数据中存在潜在的商业和科研价值，因此越来越多的数据被记录和保存起来。国际数据公司（IDC）的研究报告指出2011年全球被创建和复制的数据高达1.8ZB，而且根据趋势，到2015年这个数字将接近8ZB。国际数据公司（IDC）通过研究发现在数字世界中有近75％的数据是重复的。无独有偶，企业战略集团（the Enterprise Strategy Group）指出在备份和归档存储系统中数据的冗余度超过90％。

使用重复数据删除技术来优化存储可以有效减少数据在磁盘上的占用空间。然而，面对数据的高速增长，单一的重复数据删除服务器已经难以满足扩展性的需求。因此，集群重复数据删除技术应运而生。集群重复数据删除系统，或称分布式去重系统，通过将重复数据删除的任务分布到不同的服务器节点来提高重复数据删除服务器的处理能力。在集群重复数据删除系统中，除了考虑单个节点的去重问题外，还需要考虑将数据分配到去重服务器节点的数据路由机制，这是因为数据路由机制关系到系统整体的去重效果以及存储利用率的平衡。

目前，根据是否参考已有数据（即已存储的数据）将分布式去重系统的数据路由分为两种方法。一种方法是无状态数据路由，这种数据路由只参考当前的数据指纹信息，根据固定的映射规则，将数据分发到不同的去重服务器节点（简称去重节点）进行去重。其中，指纹（FP）用于判断构成数据的数据块是否重复，一般可通过SHA1或者MD5函数来计算数据块的指纹。这种数据路由方法实现简单，时间和空间开销都比较小。但是这种方法存在两点不足：首先，由于没有参考已存储的数据，因此无法保证数据在目标去重节点的去重率；其次，由于没有考虑去重节点的已有存储利用率，并且数据在不同去重服务器节点的去重效果不一样，因此会产生数据孤岛的问题，即某个重复数据删除服务器节点存储的数据远高于其他重复数据删除服务器节点。

另一种方法是有状态数据路由，这种方法参考系统已有数据的数据摘要和去重节点的数据存储情况来进行数据路由。这里，数据摘要是通过将构成数据的数据块指纹插入Bloom Filter（BF）而得到的。简要而言，该方法先访问存储关于每个去重节点的数据摘要的摘要存储节点，查询指纹得到该指纹在每个去重节点的命中得分，接着结合去重节点的存储利用率选择目标去重节点。这种方法的优点是能保证分布式去重系统整体的去重效果，同时能平衡去重节点的存储利用率。而缺点是这种方法需要额外的摘要存储节点用于查询，而数据摘要的内存开销很大，因此这种方法难以获得很好的扩展性。

可见，在达到去重效果与存储利用率的平衡的同时，如何提高分布式去重系统数据路由的可扩展性，并且抑制指纹查询过程中通信和计算开销的增长是当前还没有解决的问题。

发明内容

为解决上述问题，本发明提供一种面向分布式去重系统的数据路由方法，其中所述分布式去重系统包括摘要存储节点、去重节点，和与系统中其他节点通信的服务器，所述方法包括：

步骤1）、服务器将构成数据的所有数据块的指纹进行分类，并且将不同类别的指纹分别发送到存储相应类别指纹的数据摘要的不同摘要存储节点；

步骤2）、在所述摘要存储节点中查询接收到的指纹，得到该指纹在每个去重节点的命中分数，将该命中分数返回所述服务器；

步骤3）、所述服务器根据每个指纹在每个去重节点的命中分数得到每个去重节点的汇总分数，根据该汇总分数确定目标去重节点。

在一个实施例中，在步骤3）中，根据汇总分数确定目标去重节点包括：所述服务器结合每个去重节点的存储状况和汇总分数来确定目标去重节点。

在一个实施例中，每个摘要存储节点存储每个去重节点已存储数据的所有数据块指纹中一类指纹的数据摘要，其中指纹类别的总数与摘要存储节点的个数相同。

在一个实施例中，所述摘要存储节点使用Bloom Filter来存储每个去重节点的数据摘要。

在一个实施例中，在步骤1）中，服务器用所述摘要存储节点的个数对构成数据的所有数据块的指纹取模，将余数相同的指纹分为一类。

在一个实施例中，步骤2）包括：

步骤21）、在所述摘要存储节点中，使用存储每个去重节点的数据摘要的Bloom Filter所采用的哈希函数来计算接收到的指纹的哈希值；

步骤22）、根据该哈希值查询关于每个去重节点的Bloom Filter的对应位；

步骤23）、根据对应位计算命中分数；

步骤24）、将该命中分数返回所述服务器。

在一个实施例中，步骤3）包括：

步骤31）、对于每个去重节点，所述服务器计算所有指纹在该去重节点的命中分数的和，得到该去重节点的汇总分数；

步骤32）、所述服务器将每个去重节点的汇总分数与存储利用率的倒数加权求和，取值最大的去重节点作为目标去重节点。

在一个实施例中，所述方法还包括：

步骤0）、服务器从客户端接收数据，将该数据进行分块，并且计算每个数据块的指纹。

在一个实施例中，所述方法还包括：

步骤4）、所述服务器将所述数据发送到所述目标去重节点进行去重。

在一个实施例中，所述方法还包括：

步骤5）、所述摘要存储节点更新所述目标去重节点的数据摘要。

本发明可以达到如下有益效果：

使用多个摘要存储节点来存储数据路由过程中要用到的数据摘要，解决了单个摘要存储节点内存不足的问题。与此同时，由于运用分布式Bloom Filter存储方法按类别存储数据摘要，在摘要存储节点不断扩展的同时，有效抑制了指纹查询过程中通信和计算开销的增长，提高了数据路由的可扩展性。

附图说明

图1是根据本发明一个实施例的面向分布式去重系统的数据路由方法的流程图；

图2是根据本发明一个实施例的分布式Bloom Fliter存储方法的示意图；

图3是根据本发明一个实施例将原始Bloom Fliter切分为较小的Bloom Fliter的示意图；

图4是根据本发明一个实施例的Bloom Fliter的数据结构示意图；以及

图5是根据本发明一个实施例的摘要存储节点功能模块的框图。

具体实施方式

下面结合附图和具体实施方式对本发明加以说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

根据本发明的一个实施例，提供一种面向分布式去重系统的数据路由方法。简要而言，该方法包括：将多个节点作为摘要存储节点，在不同的摘要存储节点上存储关于某一类指纹的数据摘要；将需要去重的数据中所有数据块的指纹按类别发送到相应的摘要存储节点，在摘要存储节点中查询指纹，得到该指纹关于每个去重节点的命中分数；接着汇总得到数据中所有指纹关于每个去重节点的汇总分数，根据去重节点汇总分数和去重节点数据存储状况来确定目标去重节点，从而进行去重操作。现参考图1进行详细描述。

一、分布式地存储数据摘要

设置多个节点作为摘要存储节点是确定目标去重节点的前提。要提高分布式去重系统的数据路由的可扩展性，就要解决现有系统中单个摘要存储节点内存不足的问题，即采用多个节点来存储数据摘要。如果仅是简单地将数据摘要分布到不同节点，可能会造成服务器在查询指纹时进行重复的广播式通信。这是因为，服务器为了得到一个查询结果，需要将指纹发送到不同的摘要存储节点中进行查询。

为了克服上述数据摘要分布式存储方法所带来的通信开销和计算开销，在一个实施例中，可以采用分布式Bloom Filter存储方法来存储数据摘要。这种存储方法是基于Bloom Filter的自身特性，即在误判率要求（例如1%）和哈希函数个数一定的情况下，Bloom Filter的大小和插入元素的个数成正比。

在一个实施例中，可在每个摘要存储节点中创建Bloom Filter。在另一个实施例中，可以对现有分布式去重系统进行修改，基于现有系统中摘要存储节点的Bloom Filter来获得本发明中每个摘要存储节点的Bloom Filter，包括：

1、将现有系统中的一个相对较大的Bloom Filter根据摘要存储节点的个数切分成若干个相对较小的Bloom Filter，并且将这些较小的BloomFilter分布存储在不同的摘要存储节点中。参考图2，现有系统的单个摘要存储节点中存储了关于N+1个去重节点的数据摘要（即图2中所有指纹的数据摘要）的Bloom Filter（以BF节点0—BF节点N表示），则对于系统有m个摘要存储节点的情况，可将现有系统中用于存储每个去重节点的数据摘要的原始Bloom Filter切分成m个较小的Bloom Filter，每个BloomFilter可存储不同类别的指纹的数据摘要，在每个摘要存储节点中分别存储这N+1个去重节点的相应较小Bloom Filter（仍是以BF节点0—BF节点N表示）。在图2所示的实施例中，摘要节点0中存储除以m余数为0的每个去重节点的指纹的数据摘要，摘要节点1中存储除以m余数为1的每个去重节点的指纹的数据摘要，以此类推。在图3所示的实施例中，摘要存储节点的个数为3个，则系统会将一个较大的Bloom Filter分成3个等大小的Bloom Filter。图4示出了Bloom Filter的数据结构，其中asize表示Bloom Filter的大小，指针a指向为Bloom Filter分配的空间。

2、在不同的摘要存储节点上存储关于某一类指纹的数据摘要。其中指纹类别数目与摘要存储节点的个数相等。在一个实施例中，可使用取模的方法进行分类。应理解，也可以采用其他现有的分类方式来进行分类。

分布式存储数据摘要的好处在于，当需要对摘要存储节点进行指纹查询时，系统根据类别将不同指纹发送到不同的摘要存储节点，避免了广播式的通信。与此同时，在指纹查询过程中，每个指纹的哈希函数只需要进行一次计算，避免了相同指纹进行多次重复的计算。

二、查询摘要存储节点

总的来说，统筹服务器（该服务器知晓系统中的节点结构，能够与任何摘要存储节点和去重节点进行交互）在接收到客户端发来的需要去重的数据后，将该数据进行分块、计算每个数据块的指纹、对指纹进行分类，并且将所有指纹按类别发送到相应的摘要存储节点。接着，在摘要存储节点中查询接收到的指纹，得到该指纹关于每个去重节点的命中分数。

根据本发明的一个实施例，在将数据分配到目标去重节点之前查询摘要存储节点可以实现更高的去重率。在使用分布式Bloom Filter存储数据摘要后，与现有技术相比，对摘要存储节点的查询过程发生了改变，具体来说包括：

1、服务器将数据进行分块，对每个数据块计算指纹。常用的方法是使用SH1或者MD5来计算指纹。

2、根据摘要存储节点的个数对指纹进行分类。例如，按摘要存储节点的个数对指纹取模，将余数相同的指纹分为一类。

3、将分类好的指纹分别发送到相应的摘要存储节点中进行查询，避免了原始存储方式的广播式发送。指纹在每个摘要存储节点完成哈希函数的计算和Bloom Filter查询，将得到的命中分数返回给服务器。在一个实施例中，查询过程包括：在摘要存储节点中，使用存储数据摘要的BloomFilter所采用的哈希函数来计算接收到的指纹的哈希值；然后，根据该哈希值查询每个去重节点的Bloom Filter的对应位，如果对应位全为1（哈希函数一般超过一个），则指纹命中，命中分数加1。

4、将命中分数返回到服务器。图5给出了摘要存储节点的功能模块，其中，请求队列用于缓存服务器向摘要存储节点发送的请求，BF管理器用于管理节点中的Bloom Filter，整个摘要存储节点对外提供Bloom Filter的查询和更新功能。

三、确定目标去重节点

服务器在接收到摘要存储节点返回的命中分数后，对所有指纹关于每个去重节点的命中分数进行相加汇总，得到每个去重节点的汇总分数。该汇总分数可帮助服务器得到去重效果预判的分数，但是对于系统整体而言，除了要考虑去重效果，还要考虑去重节点存储利用率失衡的问题。

因此，在一个实施例中，在将数据发送到目标去重节点之前，服务器还要综合考虑每个去重节点的存储利用率。在一个实施例中，服务器可以保存记录每个去重节点存储利用率的表，每经过一段时间服务器会向每个去重节点查询一遍其存储情况，然后对该存储利用率表进行更新。存储利用率表的数据结构可以如表1所示，其中deduperID是去重节点的编号，Container_num是去重节点存储对象的个数，对象的个数反映了去重节点的存储占用情况。

表1

服务器根据这个表中记录的去重节点存储情况和去重节点汇总分数得到一个综合分数，该综合分数用于确定数据发送的目标去重节点。例如，通过对去重节点的汇总分数以及存储利用率的倒数进行加权求和，来得到一个综合分数，取值最大的去重节点作为目标去重节点。又例如，服务器可以在汇总分数大于某一阈值的节点中，选择存储利用率最小的节点作为目标去重节点。

四、服务器将数据发送到目标去重节点进行去重

在本步骤中，服务器将从客户端接收的数据发送到目标去重节点，由目标去重节点执行删除重复数据的操作，可采用本领域公知的重复数据删除技术来完成本步骤。

五、摘要存储节点中Bloom Filter的更新

在一个实施例中，服务器会发送目标去重节点的编号到摘要存储节点。接着摘要存储节点函数更新该节点中关于目标去重节点的Bloom Filter，更新过程中计算指纹对应的哈希值，并根据哈希值对Bloom Filter中相应的位进行置位，数据路由的工作就已经完成。

下面给出本文提供的面向分布式去重系统的数据路由方法的一个具体实施例，包括以下步骤：

1、服务器从客户端接收到数据，通过调用dedup_get_chunked函数将数据进行分块并且计算数据块的指纹。

2、完成指纹计算后，根据摘要存储节点的个数对指纹进行分类并调用dedup_server_send函数发送该指纹。

3、摘要存储节点接收到指纹数据，调用Bloom_query查询对应的指纹信息。其中，Bloom_query调用相应的哈希函数，得到哈希值，然后调用Bloom_check查询Bloom Filter对应的位是否已经置位，从而记录指纹是否命中得分。查询完成后，得到查询结果，发送回给服务器。

4、服务器接收结果进行汇总。由于在指纹查询前是按分类发送，因此，接收到的分数是分类查询的结果，需要汇总每个节点的分数。得到汇总分数后，服务器查找存储利用率信息表，用加权算法得出最后的综合分数。从综合分数中选取最高分，其对应的去重节点就是数据路由的目标去重节点。

5、调用dedup_server_send函数将数据和指纹发送到目标去重节点进行去重。

6、在完成去重后，服务器会发送该去重节点的编号到摘要存储节点。摘要存储节点调用Bloom_update函数更新节点中的Bloom Filter，更新过程中同样计算对应的哈希值，并根据哈希值调用Bloom_set_bit对相应的位进行置位。

相关函数描述如下：

函数dedup_get_chunked(segement)

1，调用罗宾（Rabin）函数确定数据块的边界，完成变长分块。

2，调用SHA1函数计算数据块的指纹。

3，将每个数据块的信息整合在一起返回。

函数dedup_server_send(data,length)

1，将data放到发送的缓存中，并标记数据的长度length。

2，将数据发送，等待回复。

3，接收到回复，返回。

函数Bloom_query(sha)

1，调用哈希函数计算指纹的哈希值。

2，调用Bloom_check函数查询对应的bit位是否全为1，否则，函数返回0。

3，函数返回1。

函数Bloom_check(bloom,n,...)

1，调用va_start函数取得第一个可变参数地址。

2，调用va_arg获得参数，检查需要判断的位是否为0，如果是返回0。

3，回到2，直到参数取完。

4，函数返回1。

函数Bloom_update(sha_cache，bloom_id)

1，从指纹缓存sha_cache中取出指纹。

2，调用哈希函数计算指纹的哈希值。

3，调用Bloom_check对应的位是否为1，如果不为1，调用Bloom_set_bit函数对该位进行置1。

4，判断缓存是否为空，如果缓存已空，函数返回，否则跳转到第1步。

函数Bloom_set_bit(bloom,n,...)

1，调用va_start函数取得第一个可变参数地址。

2，调用va_arg获得参数，对参数指定的位进行置位。

3，回到2，直到参数取完。

4，函数返回1。

应该注意到并理解，在不脱离后附的权利要求所要求的本发明的精神和范围的情况下，能够对上述详细描述的本发明做出各种修改和改进。因此，要求保护的技术方案的范围不受所给出的任何特定示范教导的限制。

Claims (10)

1.一种面向分布式去重系统的数据路由方法，所述分布式去重系统包括摘要存储节点、去重节点，和与系统中其他节点通信的服务器，所述方法包括：

步骤1）、服务器将构成数据的所有数据块的指纹进行分类，并且将不同类别的指纹分别发送到存储相应类别指纹的数据摘要的不同摘要存储节点；

步骤2）、在所述摘要存储节点中查询接收到的指纹，得到该指纹在每个去重节点的命中分数，将该命中分数返回所述服务器；

步骤3）、所述服务器根据每个指纹在每个去重节点的命中分数得到每个去重节点的汇总分数，根据该汇总分数确定目标去重节点。

2.根据权利要求1所述的方法，步骤3）中，根据汇总分数确定目标去重节点包括：

所述服务器结合每个去重节点的存储状况和汇总分数来确定目标去重节点。

3.根据权利要求1或2所述的方法，其中，每个摘要存储节点存储每个去重节点已存储数据的所有数据块指纹中一类指纹的数据摘要，其中指纹类别的总数与摘要存储节点的个数相同。

4.根据权利要求1或2所述的方法，其中，所述摘要存储节点使用Bloom Filter来存储每个去重节点的数据摘要。

5.根据权利要求1或2所述的方法，在步骤1）中，服务器用所述摘要存储节点的个数对构成数据的所有数据块的指纹取模，将余数相同的指纹分为一类。

6.根据权利要求4所述的方法，其中，步骤2）包括：

步骤21）、在所述摘要存储节点中，使用存储每个去重节点的数据摘要的Bloom Filter所采用的哈希函数来计算接收到的指纹的哈希值；

步骤22）、根据该哈希值查询关于每个去重节点的Bloom Filter的对应位；

步骤23）、根据对应位计算命中分数；

步骤24）、将该命中分数返回所述服务器。

7.根据权利要求2所述的方法，其中，步骤3）包括：

步骤31）、对于每个去重节点，所述服务器计算所有指纹在该去重节点的命中分数的和，得到该去重节点的汇总分数；

步骤32）、所述服务器将每个去重节点的汇总分数与存储利用率的倒数加权求和，取值最大的去重节点作为目标去重节点。

8.根据权利要求1或2所述的方法，还包括：

步骤0）、服务器从客户端接收数据，将该数据进行分块，并且计算每个数据块的指纹。

9.根据权利要求1或2所述的方法，还包括：

步骤4）、所述服务器将所述数据发送到所述目标去重节点进行去重。

10.根据权利要求9所述的方法，还包括：

步骤5）、所述摘要存储节点更新所述目标去重节点的数据摘要。

Images