CN102810107B - 重复数据的处理方法 - Google Patents

Abstract

本发明公开一种重复数据的处理方法，从客户端接收查询请求，其中查询请求包括请求指纹值。接着于内存中对应请求指纹值的哈希区块搜寻请求指纹值。当对应请求指纹值的哈希区块不存在请求指纹值时，执行以下步骤：于内存中的新增表搜寻请求指纹值；以及当新增表中存在请求指纹值时，发送无效重复信息给客户端。

Description

重复数据的处理方法

技术领域

本发明涉及一种重复数据的处理方法，特别涉及一种判断是否有重复数据的处理方法。

背景技术

重复数据删除是一种数据缩减技术，通常用于基于磁盘的备份系统，主要目的在于减少存储系统中使用的存储容量。它的工作方式是在某个时间周期内查找不同文件中不同位置的重复可变大小数据块。重复的数据块用指示符取代。由于存储系统中总是充斥着大量的冗余数据。采用重复删除的技术可以将存储的数据缩减为原来的1/20，从而让出更多的备份空间。

由于欲存储的数据都会被储存在服务器中，因此客户端需要将确认未重复的数据传送至服务器。服务器确认是未重复的新数据时，会先登记新数据的指纹值，在接收以及储存新的数据。由于不同的客户端可以对应到相同的数据，因此可节省更多的备份空间。但是多客户端的系统可能会发生当一个客户端还在新增与传输一个新的备份数据，同时有别的客户端要对相同备份数据查询其是否重复的情况。如此一来，有可能别的客户端以为已经有重复数据，却还找不到对应的重复数据的问题。尤其是当新增中的新数据发生错误而新增失败，但别的客户端却也将拥有的数据丢弃时，会造成完全新增失败且无法补救的状况。

发明内容

本发明的目的在于提供一种重复数据的处理方法。

根据一实施范例，重复数据的处理方法从一客户端接收一查询请求，其中查询请求包括一请求指纹值。接着于一内存中对应请求指纹值的一哈希区块搜寻请求指纹值。当对应请求指纹值的哈希区块不存在请求指纹值时，执行以下步骤：于内存中的一新增表搜寻请求指纹值；以及当新增表中存在请求指纹值时，发送一无效重复信息给客户端。

于另一实施范例，重复数据的处理方法从客户端接收查询请求；再利用一布隆过滤器(Bloom filter)处理请求指纹值，并得到一回传值。当回传值为命中(hit)时，于内存中对应请求指纹值的哈希区块搜寻请求指纹值。当对应请求指纹值的哈希区块不存在请求指纹值时，执行以下步骤：于内存中的新增表搜寻请求指纹值；以及当新增表中存在请求指纹值时，发送无效重复信息给客户端。

以下结合附图和具体实施例对本发明进行详细描述，但不作为对本发明的限定。

附图说明

图1为根据本发明一实施范例的服务器的示意图；

图2为根据本发明一实施范例的重复数据的处理方法的流程图；

图3为根据本发明一实施范例的步骤S200的流程图；

图4A为根据本发明一实施范例的新增程序的流程图；

图4B为根据本发明另一实施范例的新增程序的流程图；

图5为根据本发明另一实施范例的重复数据的处理方法的流程图。

其中，附图标记

10客户端

20服务器

30内存

40磁盘

52新增表

54储存完成表

56哈希冲突表

60A，60B，60C哈希区块

70数据块

具体实施方式

以下在实施方式中详细叙述本发明的详细特征以及优点，其内容足以使任何本领域技术人员了解本发明的技术内容并据以实施，且根据本说明书所揭露的内容、权利要求范围及附图，任何本领域技术人员可轻易地理解本发明相关的目的及优点。

本发明关于一种重复数据的处理方法，其适用于一服务器。实施重复数据的处理方法的服务器可判断至少一客户端欲备份的数据是否重复，以提供重复数据删除的功能。

请参照1图，其为一实施范例的服务器的示意图。

服务器20可通过因特网(Internet)或内网(internet)等各种网络(network)与多个客户端10连接，并备份由客户端10传送来的数据。服务器20可具有一内存30、一磁盘40以及处理器等硬件。磁盘40储存多个已从客户端10完整接收的数据块70，以及多个哈希区块60A、60B以及60C(hash tank，以下统称为哈希区块60)。其中数据块70可以例如是纯文本文件、各种多媒体文件或是客户端10进行系统备份时产生的快照(snapshot)，也可以是这些文件的一部分。例如服务器20可将一个文件切成多个大小统一为2兆字节(MB)数据块70储存。

服务器20可通过MD5、SHA-1、SHA-256、SHA-512或单向哈希(One-wayhash)等算法计算每一个数据块70的一储存指纹值，并且将多个储存指纹值作为哈希区块60存入磁盘40之中。而在判断是否有重复数据时，可将与欲处理的数据块70对应的哈希区块60从磁盘40加载内存30再进行处理。

服务器20的内存30之中并可维护一新增表52、一储存完成表54以及一哈希冲突表56。其中新增表52中可纪录正在新增的数据块70的储存指纹值。储存完成表54中可纪录已新增完成，但尚未将新增完成的信息写入数据块70的储存指纹值。哈希冲突表56可纪录各哈希区块60中产生哈希冲突的储存指纹值。

请参照图2，其为根据本发明一实施范例的重复数据的处理方法的流程图。

首先服务器20从任一个客户端10接收一查询请求，其中查询请求包括一请求指纹值(步骤S100)。为了尽量减少客户端10与服务器端20之间的数据传输，客户端10欲备份一请求数据块时可以只传送代表请求数据块的请求指纹值给服务器20。但依据请求数据块计算请求指纹值的算法须与依据数据块70计算储存指纹值的算法相同。

接着服务器20于内存30对应请求指纹值的哈希区块60搜寻请求指纹值(步骤S200)，以确认服务器20是否已存有与请求数据块相同的数据块70。请配合参照图3，其为根据本发明一实施范例的步骤S200的流程图。

储存指纹值可以以哈希表的方式储存，但是由于储存指纹值的数量很大，无法全部暂存于内存30之中。因此服务器20可将哈希表分割成多个哈希区块60，以快速存取储存指纹值，但只有部分的哈希区块60会被加载内存30之中。

为了判断可能存有请求指纹值的哈希区块60是否正在内存30中，可先对请求指纹值执行一哈希程序，并得到一区块索引值(步骤S210)。接着再依据区块索引值，于内存30中搜寻对应请求指纹值的哈希区块60(步骤S220)，以及判断内存30中是否存在对应请求指纹值的哈希区块60(步骤S230)。

举例而言，假设将请求指纹值执行哈希程序后获的区块索引值是哈希区块60A，便可在内存30中找到。当内存30中存在对应请求指纹值的哈希区块60A时，于对应请求指纹值的哈希区块60A搜寻请求指纹值(步骤S240)。

相反地，假设将请求指纹值执行哈希程序后获的区块索引值是哈希区块60C，便无法在内存30中找到。当内存30中不存在对应请求指纹值的哈希区块60C时，可执行以下步骤S250至步骤S290，以在所需的哈希区块60C中搜寻请求指纹值。

服务器20先从磁盘40中将对应请求指纹值的哈希区块60C加载内存30(步骤S250)，再于内存30中的储存完成表54搜寻请求指纹值(步骤S260)。

储存完成表54中可纪录完整储存于磁盘40之中，但尚未将新增完成的信息更新一写入状态值的数据块70的储存指纹值。为了减少将磁盘40中的数据加载内存30的动作(又称为磁盘输入输出，磁盘input/output，磁盘IO)，当有数据块70新增完成后，可先将新增完成的数据块70的储存指纹值暂存于储存完成表54之中。

例如若有新的数据块已新增完成，但完成时此数据块70对应的哈希区块60正好不在内存30之中，服务器20可不将对应的哈希区块60加载内存30来更改其写入状态值。相对地，服务器20将新增完成的数据块70的储存指纹值存入储存完成表54。由于磁盘IO所需花费的时间远较直接读写内存30还长，因此以储存完成表54暂时代替磁盘IO的做法可节省重复数据的处理时间。

服务器20判断储存完成表54中是否存在请求指纹值(步骤S270)。当储存完成表54中存在请求指纹值时，更新哈希区块60的写入状态值，并由储存完成表54中删除请求指纹值，再于对应请求指纹值的哈希区块60搜寻请求指纹值(步骤S280)。换句话说，服务器20在尚未更新其写入状态值的哈希区块60需被加载内存30时(也就是步骤S200)，才将写入状态值更新。如此一来，可避免仅为了更改写入状态值而将对应的哈希区块60额外加载内存30的磁盘IO。

而当储存完成表54中不存在请求指纹值时，可直接于对应请求指纹值的哈希区块60搜寻请求指纹值(步骤S290)。

读取并搜寻所需的哈希区块60后，服务器20判断对应请求指纹值的哈希区块60是否存在请求指纹值(步骤S300)。当哈希区块60中存在请求指纹值时，发送一有效重复信息给客户端10(步骤S400)。由于在内存30或磁盘40中已找到与请求指纹值相同的储存指纹值，可知在磁盘40中已完整存有客户端10欲备份的请求数据块。因此服务器20发送有效重复信息告知客户端10。

反之，当对应请求指纹值的哈希区块60不存在请求指纹值时，服务器20执行以下步骤S500至步骤S800，以判断请求数据块是否为新的数据块。

服务器20于内存30中的新增表52搜寻请求指纹值(步骤S500)，接着判断新增表52中是否存在请求指纹值(步骤S600)。新增表52中纪录正在新增的数据块70的储存指纹值，服务器20可通过新增表52确认哪些数据块70还在传输中，而尚未完整储存于磁盘40之中。

当新增表52中存在请求指纹值时，表示对应的数据块70上在新增中，而发送一无效重复信息给客户端10(步骤S700)。客户端10收到无效重复信息后，可进行轮询(polling)或等待(waiting)；并在经过一预定时间后再度发出查询请求。且客户端10收到无效重复信息后可先暂时保留自己的请求数据块，以避免新增失败。

当新增表52中不存在请求指纹值时，执行一新增程序(步骤S800)。

请参照图4A，其为根据本发明一实施范例的新增程序的流程图。

服务器20可先将请求指纹值加入新增表52(步骤S810)，再发送一新数据信息给客户端10(步骤S820)，已要求客户端10传送请求数据块。

请参照图4B，其为根据本发明一实施范例的新增程序的流程图。于本实施范例之中，新增程序在步骤S820之后另可包括步骤S830至S870。

客户端10依据新数据信息发送请求数据块，服务器20从客户端10接收并储存请求指纹值代表的请求数据块(步骤S830)。且如前述，服务器20于内存30中搜寻对应请求指纹值的哈希区块60(步骤S840)，并判断内存30中是否正好存在对应请求指纹值的哈希区块60(步骤S850)。

当内存30中存在对应请求指纹值的哈希区块60时，可直接更新哈希区块60的写入状态值，并由新增表52中删除请求指纹值(步骤S860)。而当内存30中不存在对应请求指纹值的哈希区块60时，可将请求指纹值写入内存30的储存完成表54，并由新增表52中删除请求指纹值(步骤S870)。

请参照图5，其为根据本发明另一实施范例的新增程序的流程图。

为了减少磁盘IO的次数，接收查询请求后可先利用一布隆过滤器(Bloomfilter)处理请求指纹值，并得到一回传值(步骤S120)。布隆过滤器能够先行预测请求数据块是否为新的数据块；若是，则回传值为命中(hit)，表示请求指纹值应已存在内存30或磁盘40之中。服务器20判断回传值是否为命中(hit)(步骤S130)。当回传值为命中时，执行上述步骤S200，以判断是否为重复数据；当回传值为未命中时，则执行上述步骤S800，以新增请求数据块。

此外，服务器20可在读取哈希区块60中对应请求指纹值的储存指纹值时，比较请求指纹值与储存指纹值是否相同。若不同，可能是在纪录储存指纹值时发生哈希冲突。此时可查询哈希冲突表56，以确认真正对应请求指纹值的储存指纹值是否存在，以正确判断数据的重复性。

综上所述，重复数据的处理方法维护新增表以确认是否有新增中的无效重复数据；并维护储存完成表以减少磁盘IO的次数。因此重复数据的处理方法不但可以正确地辨别重复数据的有效性，更能快速且有效率地执行。

当然，本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。

Claims (8)

1.一种重复数据的处理方法，其特征在于，包括：

从一客户端接收一查询请求以欲备份一请求数据块，其中该查询请求包括代表该请求数据块的一请求指纹值；

于一内存中对应该请求指纹值的一哈希区块搜寻该请求指纹值；以及

当对应该请求指纹值的该哈希区块不存在该请求指纹值时，执行以下步骤：

于该内存中的一新增表搜寻该请求指纹值，其中该新增表中纪录正在新增的数据块的储存指纹值，并通过该新增表确认哪些数据块还在传输中，而尚未完整储存于磁盘之中，其中依据该请求数据块计算该请求指纹值的算法与依据该数据块计算该储存指纹值的算法相同；以及

当该新增表中存在该请求指纹值时，发送一无效重复信息给该客户端，

其中，所述于该内存中对应该请求指纹值的该哈希区块搜寻该请求指纹值的步骤还包括：当有新的数据块新增完成，但该内存中不存在对应该请求指纹值的该数据块的该哈希区块时：不将对应的该哈希区块加载到该内存来更新其写入状态值，而是将新增完成的数据块的储存指纹值存入一储存完成表；于该内存中的储存完成表搜寻该请求指纹值；以及当该储存完成表中存在该请求指纹值时，更新该哈希区块的一写入状态值，并由该储存完成表中删除该请求指纹值，再于对应该请求指纹值的该哈希区块搜寻该请求指纹值，即在尚未更新其写入状态值的哈希区块需要被加载入内存时，才将写入状态值更新；当该储存完成表中不存在该请求指纹值时，直接于对应请求指纹值的哈希区块搜寻该请求指纹值；

其中，该储存完成表中纪录完整储存于磁盘之中，但尚未将新增完成的信息更新一写入状态值的数据块的储存指纹值，以及当有数据块在磁盘中新增完成之后，先将该数据块的储存指纹值暂存于该储存完成表中。

2.根据权利要求1所述的重复数据的处理方法，其特征在于，还包括：

当该哈希区块存在该请求指纹值时，发送一有效重复信息给该客户端。

3.根据权利要求1所述的重复数据的处理方法，其特征在于，所述于该内存中对应该请求指纹值的该哈希区块搜寻该请求指纹值的步骤包括：

对该请求指纹值执行一哈希程序，并得到一区块索引值；

依据该区块索引值，于该内存中搜寻对应该请求指纹值的该哈希区块；以及

当该内存中存在对应该请求指纹值的该哈希区块时，于对应该请求指纹值的该哈希区块搜寻该请求指纹值。

4.根据权利要求1所述的重复数据的处理方法，其特征在于，还包括：

当该新增表中不存在该请求指纹值时，执行一新增程序。

5.根据权利要求4所述的重复数据的处理方法，其特征在于，该新增程序包括：

将该请求指纹值加入该新增表；以及

发送一新数据信息给该客户端。

6.根据权利要求5所述的重复数据的处理方法，其特征在于，该新增程序还包括：

从该客户端接收并储存该请求指纹值代表的一数据块；

于该内存中搜寻对应该请求指纹值的该哈希区块；

当该内存中存在对应该请求指纹值的该哈希区块时，更新该哈希区块的一写入状态值，并由该新增表中删除该请求指纹值；以及

当该内存中不存在对应该请求指纹值的该哈希区块时，将该请求指纹值写入该内存的一储存完成表，并由该新增表中删除该请求指纹值。

7.一种重复数据的处理方法，其特征在于，包括：

从一客户端接收一查询请求以欲备份一请求数据块，其中该查询请求包括代表该请求数据块的一请求指纹值；

利用一布隆过滤器处理该请求指纹值，并得到一回传值；以及

当该回传值为命中时，执行以下步骤：

于一内存中对应该请求指纹值的一哈希区块搜寻该请求指纹值；以及

当对应该请求指纹值的该哈希区块不存在该请求指纹值时，执行以下步骤：

于该内存中的一新增表搜寻该请求指纹值，其中该新增表中纪录正在新增的数据块的储存指纹值，并通过该新增表确认哪些数据块还在传输中，而尚未完整储存于磁盘之中，其中依据该请求数据块计算该请求指纹值的算法与依据该数据块计算该储存指纹值的算法相同；以及

当该新增表中存在该请求指纹值时，发送一无效重复信息给该客户端，

其中，所述于该内存中对应该请求指纹值的该哈希区块搜寻该请求指纹值的步骤还包括：当有新的数据块新增完成，但该内存中不存在对应该请求指纹值的该数据块的该哈希区块时：不将对应的该哈希区块加载到该内存来更新其写入状态值，而是将新增完成的数据块的储存指纹值存入一储存完成表；于该内存中的储存完成表搜寻该请求指纹值；以及当该储存完成表中存在该请求指纹值时，更新该哈希区块的一写入状态值，并由该储存完成表中删除该请求指纹值，再于对应该请求指纹值的该哈希区块搜寻该请求指纹值，即在尚未更新其写入状态值的哈希区块需要被加载入内存时，才将写入状态值更新；当该储存完成表中不存在该请求指纹值时，直接于对应请求指纹值的哈希区块搜寻该请求指纹值；

其中，该储存完成表中纪录完整储存于磁盘之中，但尚未将新增完成的信息更新一写入状态值的数据块的储存指纹值，以及当有数据块在磁盘中新增完成之后，先将该数据块的储存指纹值暂存于该储存完成表中。

8.根据权利要求7所述的重复数据的处理方法，其特征在于，还包括：

当该回传值为未命中时，执行一新增程序。