CN103838645B - 一种基于哈希的远程差异合成备份实现方法 - Google Patents

Abstract

本发明涉及一种基于哈希的远程差异合成备份实现方法，包括以下步骤：1)备份客户端获取需要备份的源文件，设定备份类型，生成文件列表，所述的备份类型包括全备份或差异备份；2)判断是否存在与文件列表相关的编录信息文件，若是，则直接执行步骤3)，若否，则生成一个空的编录信息文件后，执行步骤3)；3)根据文件列表和编录信息文件计算差异数据，并保存至备份服务器中；4)获取此次备份的备份类型，若备份类型为全备份，则备份服务器对每个文件执行差异合成备份，执行步骤5)，若备份类型为差异备份，则直接执行步骤5)；5)备份结束。与现有技术相比，本发明具有数据量少、网络的利用率高、数据存储空间少、处理速度快等优点。

Description

一种基于哈希的远程差异合成备份实现方法

技术领域

本发明涉及一种远程备份实现方法，尤其是涉及一种基于哈希的远程差异合成备份实现方法。

背景技术

随着计算机在人们生活及生产中所起的作用越来越重要，用计算机来存储相关的数据也越来越多。数据是人们在使用计算过程当中产生的用来记录重要信息的载体，因此保证数据完整性与安全就是保证人们生活与生产活动的顺利进行。然而由于计算机本身的物理特性，保存在其上的数据会因为各种外部原因的冲击而不可用，比如物理损坏、被盗、电力中断等等都可能导致存储在计算机上的数据丢失。为了保证数据持续可用，最好的方式就是保证数据的冗余存储，即将数据存储在两个或者多个位置。

为了应用各种破坏数据的场景，不同的技术被开发出来用于数据的冗余存储，像RAID(Redundant Array ofIndependent Disks，独立磁盘冗余阵列)系统可以用来保证在物理介质损坏时的数据冗余，而远程备份方法则可以保证在计算机受到自然灾害、被盗或者物理介质损坏的情况下数据的冗余存储。

远程备份方法通常有定时的备份方法，即在设定的时间点启动备份任务。在这种备份方式下，备份程序通过读取文件的时间标签以确定文件是否被更改过，如果文件被更改就备份该文件，否则就不备份。这种方式一个明显的缺陷就是，就算是文件一个字节都未更改，只是变更了时间标签，这个文件都需要备份。特别是当文件的尺寸很大时，备份所带来的时间以及网络消耗是非常大的。

为了解决上面的备份方式所带来的问题，则使用另一种实时的备份方式，即利用监控文件的方式来读取文件的变化数据，只备份向文件中写入的数据。当文件有变化时，就将变化的数据写入到备份目的地去。这种方式虽然解决了上面备份大文件的问题，但是也有相应的缺陷。如果当频繁写文件的相同位置时，这种备份方式会将这些变化的数据存储多份，即使其实只需要最后一次变化的数据。其次，要实时监控文件的写操作，需要在系统上安装相应的监控程序，每增加一个监控的文件，就要占用一定的系统资源，因此，当需要监控的文件非常多时，对于系统资源有限的系统来说就不一定能够实施了。特别是监控与备份跟正常业务是同时进行的，因此会对正常的业务造成影响。

如果有另一种备份方法能够只备份变化的文件差异的部份，同时又不会造成对业务的影响的话，那么这种备份方式则可以解决上面所述的备份方法所具有的缺陷。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种备份数据量少、网络利用率高、数据存储空间少、处理速度快的基于哈希的远程差异合成备份实现方法。

本发明的目的可以通过以下技术方案来实现：

一种基于哈希的远程差异合成备份实现方法，包括以下步骤：

1)备份客户端获取需要备份的源文件，设定备份类型，并根据源文件生成文件列表，所述的备份类型包括“全备份”或“差异备份”；

2)判断是否存在与文件列表相关的编录信息文件，若是，则直接执行步骤3)，若否，则生成一个空的编录信息文件后，执行步骤3)；

3)根据文件列表和编录信息文件计算差异数据，并保存至备份服务器中；

4)获取此次备份的备份类型，若备份类型为“全备份”，则备份服务器对每个文件执行差异合成备份，执行步骤5)，若备份类型为“差异备份”，则直接执行步骤5)；

5)备份结束。

所述的编录信息文件包括哈希表、文件备份时使用的哈希块长度和文件记录信息，所述的记录信息包括文件名称、文件大小和文件最后修改时间。

所述的步骤3)具体为：

3.1)从文件列表中取得下一个需备份的文件作为当前文件，判断当前文件是否为空，若是，则执行步骤4)，若否，则执行步骤3.2)；

3.2)根据文件名称判断编录信息文件中是否存在当前文件的编录信息，若是，则当前文件为第一次备份，执行步骤3.6)，若否，则执行步骤3.3)；

3.3)获取当前文件的大小SIZE，利用如下公式求得当前文件所对应的哈希块长度L：

L=L1+[(L1％SIZE)／(SIZE／L1)]

其中，L1％SIZE表示的是L1对SIZE求余数；

3.4)从当前文件开头起，以步骤3.3)计算的哈希块长度L为单位，计算每一块数据的“快哈希”与“慢哈希”，形成当前文件的哈希表，将哈希表、哈希块长度和文件记录信息保存至编录信息文件中；

3.5)将当前文件的完整数据保存至备份服务器，即当前文件的备份类型为“全备份”，返回步骤3.1)；

3.6)获取当前文件的修改时间，并与记录在编录信息文件中的文件最后修改时间进行比较，若相同，则返回步骤3.1)，若不同，则执行步骤3.7)；

3.7)获取当前文件对应的哈希表和哈希块长度L，并设置当前文件的当前位置为0；

3.8)判断当前位置到文件末尾的数据块的长度是否小于L，若是，则输出自上一个相同数据块以来窗口滑过的数据块以及该数据块为差异数据，执行步骤3.11)，若否，则从当前位置以L为窗口长度计算窗口中数据块的“快哈希”，并判断哈希表中是否存在相同值的“快哈希”，若是，则执行步骤3.9)，若否，则执行步骤3.10)；

3.9)计算当前数据块的“慢哈希”，判断在具有相同的“快哈希”的哈希对中是否存在相同的“慢哈希”，若是，则说明当前数据块与该哈希对所对应的数据块相同，则输出窗口自上一个相同块以来滑过的数据块为差异数据块，并输出查找到的相同数据块在对应文件中的位置信息，将当前位置向后移动一个窗口长度，返回步骤3.8)，若否，则执行步骤3.10)；

3.10)将当前位置向后移动一个字节，返回步骤3.8)；

3.11)将输出的所有差异数据块以及相同数据块信息作为差异数据保存至备份服务器中，即当前文件的备份类型为“差异备份”。

所述的“快哈希”为快速哈希算法计算的哈希值，所述的“慢哈希”为高强度哈希算法计算的哈希值；

所述的快速哈希算法计算包括Rabin-Karp算法或Adler32算法，所述的高强度哈希算法包括MD5、MD4、SHA-1、SHA-2或SHA-3。

所述的哈希块长度L的下限为400K字节，上限为512K字节。

所述的步骤4)中的差异合成备份具体为：

4.1)判断文件列表中的所有文件是否均为第一次备份，若是，则执行步骤5)，若否，则执行步骤4.2)；

4.2)从当前时间点到第一次备份的时间点之间的所有文件执行如下步骤：

4.2.1)判断当前文件的备份类型是否为“全备份”，若是，则执行下一个文件的合成，若否，则执行步骤4.2.2)；

4.2.2)查找当前文件所对应的“全备份”，从“差异备份”中读取所有数据块记录信息，并对每个数据块执行如下判断：

如果是相同的数据块，则从“全备份”中读取相应位置所描述的数据，并写入新的“全备份”中；如果是差异数据，则从当前的“差异备份”中读取数据写入到新的“全备份”中，直到处理完所有的数据块，然后执行步骤4.2.3)；

4.2.3)完成“全备份”的合成后，删除本次“全备份”之前的所有“全备份”以及“差异备份”数据，并更新编录信息文件。

需要恢复备份数据时，根据指定的恢复文件时间点及文件名称执行如下步骤：

从指定的时间点向前查找文件的第一个“差异备份”以及其对应的“全备份”，从“差异备份”中读取所有数据块记录信息，并对每个数据块执行如下判断：如果是相同的数据块，则从“全备份”中读取数据中所描述的数据，并返回给客户端，如果是差异数据，则从“差异备份”中读取数据返回给客户端，直到处理完所有的数据块。

与现有技术相比，本发明具有以下优点：

1、备份的数据量少：在实施文件备份时，只备份差异数据。因此需要备份数据大小跟文件大小无关，只跟变化数据量有关，因此可以减少备份的数据量。

2、网络的利用率高：由于跟需要备份差异数据，因此在通过网络备份到远端服务器时，所需要传输的数据量远小于备份完全的文件时的数据量，因此可以加快数据的传输，减少对网络的占用，降低了网络的要求。

3、数据存储空间少：由于在存储时，只需要存储文件的差异部分，因此可以极大地减少存储的数据量，减少对于存储的投资成本。

4、处理速度快：文件的完全数据通过对差异数据进行合并而取得，因此在恢复合成“全备份”，及传输时都只需要处理差异数据，因此生成“全备份”以及恢复时不会占用大量的网络资源，加快了合并与恢复过程。

附图说明

图1为本发明的流程图；

图2为本发明中模块结构示意图；

图3为本发明中滑动哈希计算示意图；

图4为本发明中差异备份数据格式示意图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

一种基于哈希的远程差异合成备份实现方法，该方法通过比较文件当前内容与初始内容之间相同长度的数据块的哈希值是否相同来确定数据块是否相同来提取差异数据。哈希值是计算机中数据通过某种数据摘要(哈希)算法计算出来的数据特征值，也称为数据摘要，或者数据特征码。哈希值一般具有这样的特性：相同数据是相同哈希值的充分条件，即相同的数据一定有相同的哈希值，不同的数据有不同的哈希值，但反之则不然。采用强度高的哈希算法，可以在大时间与大空间范围内保证不同的数据一定有不同的哈希值。在本发明中，为了快速找到差异数据，还运用到一种快速哈希算法，最终数据是否相同，通过强度高的哈希算法进行确认。在本发明中，上述的快速哈希算法计算出来的哈希值，称为“快哈希”，更高强度哈希算法计算出来的哈希值，称为“慢哈希”。所述的快速哈希算法(RollingHasher)为满足如下特征的算法：哈希的计算可以通过滑动窗口的方式进行，即新的哈希值，可以仅通过滑出窗口与滑入窗口的两个字节即可以取得。类似的算法包括Rabin-Karp算法、改进的Adler32算法等。所述的强度高的哈希算法包括MD5、MD4、SHA-1、SHA-2或SHA-3等。

在本实施例中，实现本发明方法的系统包括备份服务器和备份客户端。备份服务器由“合成／恢复模块”以及“存储模块”组成，客户端由“备份/恢复模块”以及“差异数据计算模块”组成，其结构图如图2所示。

1.首先启动备份服务器。

2.启动备份客户端，并向客户端指定备份服务器的地址，然后向备份客户端指定需要备份的源文件，并指定备份类型。客户端将需要备份的源文件生成文件列表K，并查询是否存在与本次备份相关的编录信息文件C，如果不存在，则生成一个空的编录信息文件。然后将列表K，以及编录信息文件C提交给“差异数据计算模块”。所述的编录信息文件包括哈希表、文件备份时使用的哈希块长度和文件记录信息，所述的记录信息包括文件名称、文件大小和文件最后修改时间。

备份类型包括全备份或差异备份，备份了所有文件的完整数据的备份类型为“全备份”，只备份了差异数据的备份类型为“差异备份”。当第一次执行备份时，备份的都是所有文件的完整数据，因此第一次备份都是“全备份”。

3.如图1所示，差异数据计算模块在接收到列表K以及编录信息文件C后，对于K中的每一个当前文件file，首先在C中查询是否存在当前文件的编录信息。如果存在，则执行3.1，否则执行3.2。当执行完所有文件的备份后，则进入步骤4。

3.1即文件已经备份过了，此时先取得文件的修改时间，并与记录在编录C中的文件最终修改时间进行比较，如果文件时间相同，表示上次备份以来，文件没有变化，因此返回列表K，处理下一个文件。否则执行3.1.1。

3.1.1如果文件的修改时间不同，则说明文件有变化，需要计算差异数据，计算过程如下步骤所述：

A、先取得file在编录信息文件中的哈希表H，以及哈希数据块长度L，并设置file的当前位置为0。如图3所示，以L为窗口长度滑动计算相应的数据哈希值来提取差异数据，图3中方框表示差异数据，箭头表示窗口移动方向。

B、如果文件的当前位置到文件尾的长度小于L字节，则输出一个数据块，类型为DIFF，其中包括滑动窗口自上一个相同数据块以来滑过的差异以及本块数据，并输出给“备份／恢复模块”，然后进入步骤E。否则从file的当前位置利用RollingHasher计算L长度的数据“快哈希”值，并进入步骤C。

C、在H中查找是否有相应的“快哈希”值。如果存在，则再计算该块数据的MD5哈希值，如果在有相同的“快哈希”值的哈希对中找到相同的MD5哈希值，则说明找到了一块相同的数据，因此，输出滑动窗口自上一个相同数据块以来滑过的差异以及本块数据已经滑过的数据为差异数据块到“备份／恢复模块”，并指定其类型DIFF，并输出相同哈希对对应的数据块的信息(即该块数据在文件中的位置及长度)到“备份／恢复模块”，并指定其类型为SAME，然后将文件的当前位置向前移动L字节，并返回步骤B。如果未找到相应的“快哈希”值，或者虽然“快哈希”值相同，但是MD5哈希值不相同，则执行步骤D。

D、将文件file的当前位置向前移动一个字节，然后返回步骤B。由于我们采用了快哈希算法——RollingHasher哈希计算方法，该方法的特征就是，只需要使用将移出与移入窗口的字节就可以计算“快哈希”，因此在返回B步骤时，B计算哈希的速度就会非常快，通过这种方式，就能够非常快速地定位差异数据。

E、向“备份／恢复模块”输出一个类型为END特殊块，以表示文件的处理已经结束，最终每一个差异文件在备份时都产生如图4所示的格式，并被“备份／恢复模块”备份到备份服务器的存储模块中。

3.2即编录信息文件中无法查询到file文件的信息，说明这个文件是第一次备份。首先取得文件file的大小，并利用以下公式计算出一个哈希数据块大小L：

$L1=\left({\mathrm{Log}}_2\mathrm{SIZE}\right)\left(\sqrt[3]{\mathrm{SIZE}}\right)$

L=L1+[(L1％SIZE)／(SIZE／L1)]

其中，L1％SIZE表示的是L1对SIZE求余数，SIZE为文件file的大小。

从文件的开始处，每L字节的数据块利用滑动哈希算法RollingHasher计算一个“快哈希”，并且利用MD5对相同的数据块计算一个“慢哈希”，形成一个哈希对，然后将哈希对以及这个哈希对所对应的数据块的位置、长度，以及文件的备份时间、大小、文件名写入到编录信息文件C中，然后将文件内容备份到备份服务器中，并返回列表K处理下一个文件。

4.当所有文件备份执行完成时，需要确定备份的类型。如果是第一次备份，则将备份类型指定为COMPLETE_BACKUP类型。如果用户指定的是COMPLETE_BACKUP类型，则“备份／恢复模块”通知备份服务器的“合成／恢复模块”进行数据合成。合成完成后，设置备份的类型为COMPLETE_BACKUP，否则备份的类型就是DIFFERENTIAL_BACKUP。

当“合成／恢复模块”接受到客户端的合成备份指令时执行下面的步骤：

5.首先从当前时间点到第一次类型为COMPLETE_BACKUP备份的时间点之间的所有备份过的文件执行如下步骤：

A、如果当前文件是“全备份”，则结束当前文件的处理，执行下一个文件的合成。如果文件是“差异备份”，则执行步骤B。

B、从当前时间点向更早的备份时间点查找当前文件的“全备份”，找到“全备份”后，从差异备份中读取“差异备份”的所有块记录信息，并对每个块执行如下判断：如果是类型为SAME的数据块，则从“全备份”的文件中读取数据中所描述的数据，并写入文件的新的“全备份”文件中。如果是类型为DIFF的差异数据，则从当前的“差异备份”文件中读取数据写入到新的“全备份”文件中，如果是类型为END的数据块，则表明文件已经处理完成，然后执行C步骤。

C、完成“全备份”的全成后，则删除本次全备份之前的所有“全备份”以及“差异备份”数据。并更新编录信息，以反映合成备份的变化。并通知客户端的“备份／恢复模块”合成备份完成。

当恢复时，其执行过程类似于合成备份数据的过程。当要恢复某个文件时，备份客户端向备份服务器指定需要恢复的时间点以及文件名称。当备份服务器接收到对应的时间及文件时，执行如下步骤：

从指定的时间点向前查找文件的第一个“差异备份”，以及其对应的“全备份”，然后执行下一步；

从差异备份中读取“差异备份”的所有块记录信息，并对每个块执行如下判断：如果是相同的数据块，则从“全备份”的文件中读取数据中所描述的数据，并返回给客户端。如果是差异数据，则从“差异备份”文件中读取数据返回给客户端，直到处理完所有的数据块；

当所有的块记录都已经处理完成了，则恢复结束。

Claims (5)

1.一种基于哈希的远程差异合成备份实现方法，其特征在于，包括以下步骤：

1)备份客户端获取需要备份的源文件，设定备份类型，并根据源文件生成文件列表，所述的备份类型包括“全备份”或“差异备份”；

2)判断是否存在与文件列表相关的编录信息文件，若是，则直接执行步骤3)，若否，则生成一个空的编录信息文件后，执行步骤3)；

3)根据文件列表和编录信息文件计算差异数据，并保存至备份服务器中；

4)获取此次备份的备份类型，若备份类型为“全备份”，则备份服务器对每个文件执行差异合成备份，执行步骤5)，若备份类型为“差异备份”，则直接执行步骤5)；

5)备份结束；

所述的编录信息文件包括哈希表、文件备份时使用的哈希块长度和文件记录信息，所述的记录信息包括文件名称、文件大小和文件最后修改时间；

所述的步骤3)具体为：

3.1)从文件列表中取得下一个需备份的文件作为当前文件，判断当前文件是否为空，若是，则执行步骤4)，若否，则执行步骤3.2)；

3.2)根据文件名称判断编录信息文件中是否存在当前文件的编录信息，若是，则当前文件为第一次备份，执行步骤3.6)，若否，则执行步骤3.3)；

3.3)获取当前文件的大小SIZE，利用如下公式求得当前文件所对应的哈希块长度L：

L＝L1+[(L1％SIZE)/(SIZE/L1)]

其中，L1％SIZE表示的是L1对SIZE求余数；

3.4)从当前文件开头起，以步骤3.3)计算的哈希块长度L为单位，计算每一块数据的“快哈希”与“慢哈希”，形成当前文件的哈希表，将哈希表、哈希块长度和文件记录信息保存至编录信息文件中；

3.5)将当前文件的完整数据保存至备份服务器，即当前文件的备份类型为“全备份”，返回步骤3.1)；

3.6)获取当前文件的修改时间，并与记录在编录信息文件中的文件最后修改时间进行比较，若相同，则返回步骤3.1)，若不同，则执行步骤3.7)；

3.7)获取当前文件对应的哈希表和哈希块长度L，并设置当前文件的当前位置为0；

3.8)判断当前位置到文件末尾的数据块的长度是否小于L，若是，则输出窗口自上一个相同块以来滑过的数据块以及该数据块为差异数据块，执行步骤3.11)，若否，则从当前位置以L为窗口长度计算窗口中数据块的“快哈希”，并判断哈希表中是否存在相同值的“快哈希”，若是，则执行步骤3.9)，若否，则执行步骤3.10)；

3.9)计算当前数据块的“慢哈希”，判断在具有相同的“快哈希”的哈希对中是否存在相同的“慢哈希”，若是，则说明当前数据块与该哈希对所对应的数据块相同，则输出窗口自上一个相同块以来滑过的数据块为差异数据块，并输出查找到的相同数据块在对应文件中的位置信息，将当前位置向后移动一个窗口长度，返回步骤3.8)，若否，则执行步骤3.10)；

3.10)将当前位置向后移动一个字节，即滑动一个字节，返回步骤3.8)；

3.11)将输出的所有差异数据块以及相同数据块信息作为差异数据保存至备份服务器中，即当前文件的备份类型为“差异备份”。

2.根据权利要求1所述的一种基于哈希的远程差异合成备份实现方法，其特征在于，所述的“快哈希”为快速哈希算法计算的哈希值，所述的“慢哈希”为高强度哈希算法计算的哈希值；

所述的快速哈希算法计算包括Rabin-Karp算法或Adler32算法，所述的高强度哈希算法包括MD5、MD4、SHA-1、SHA-2或SHA-3。

3.根据权利要求1所述的一种基于哈希的远程差异合成备份实现方法，其特征在于，所述的哈希块长度L的下限为400K字节，上限为512K字节。

4.根据权利要求1所述的一种基于哈希的远程差异合成备份实现方法，其特征在于，所述的步骤4)中的差异合成备份具体为：

4.1)判断文件列表中的所有文件是否均为第一次备份，若是，则执行步骤5)，若否，则执行步骤4.2)；

4.2)从当前时间点到第一次备份的时间点之间的所有文件执行如下步骤：

4.2.1)判断当前文件的备份类型是否为“全备份”，若是，则执行下一个文件的合成，若否，则执行步骤4.2.2)；

4.2.2)查找当前文件所对应的“全备份”，从“差异备份”中读取所有数据块记录信息，并对每个数据块执行如下判断：

如果是相同的数据块，则从“全备份”中读取相应位置所描述的数据，并写入新的“全备份”中；如果是差异数据，则从当前的“差异备份”中读取数据写入到新的“全备份”中，直到处理完所有的数据块，然后执行步骤4.2.3)；

4.2.3)完成“全备份”的合成后，删除本次“全备份”之前的所有“全备份”以及“差异备份”数据，并更新编录信息文件。

5.根据权利要求4所述的一种基于哈希的远程差异合成备份实现方法，其特征在于，需要恢复备份数据时，根据指定的恢复文件时间点及文件名称执行如下步骤：

从指定的时间点向前查找文件的第一个“差异备份”以及其对应的“全备份”，从“差异备份”中读取所有数据块记录信息，并对每个数据块执行如下判断：如果是相同的数据块，则从“全备份”中读取数据中所描述的数据，并返回给客户端，如果是差异数据，则从“差异备份”中读取数据返回给客户端，直到处理完所有的数据块。