CN103116615B - 一种基于版本矢量的数据索引方法及服务器 - Google Patents

Abstract

本发明提供了一种基于版本矢量的数据索引方法和服务器，其特征在于包括：服务器端读取当前备份过程生成的数据，建立数据块哈希值和数据块位置之间的映射关系；服务器端具有一个最新版本Ve，结合上次数据索引的版本Vi，确定本次索引的版本范围为[Vi,Ve]，并将哈希表和索引表载入内存完成初始化任务；服务器端从元数据库中读取内有索引的所有版本文件，然后将与文件相关的信息加入到哈希表中，完成文件哈希索引。通过本发明基于版本矢量的数据索引方法和服务器，对于重复数据仅需为数据块指针建立索引，此种方式效率更高，节省了建立数据索引的时间。

Description

一种基于版本矢量的数据索引方法及服务器

技术领域

本发明涉及云计算和云存储系统中数据同步、数据备份的方法，属于计算机信息存储技术领域，广泛适用于在线存储、云存储服务、数据备份、数据归档、数据复制、异地容灾、存储管理等系统。

背景技术

在当今信息化时代，随着电子商务应用的加速，数据已经成为人们最重要的财富。人们在日常生活和工作中使用计算机产生的各种数据，却时刻面临着病毒感染、硬件故障、软件错误、设备丢失等难以预测的意外，以及黑客攻击、误操作等人为因素的威胁。数据安全已经成为信息时代的一大隐患，而数据备份自然也就成为一种重要预防手段。

在数据备份领域，数据总是在变化过程中产生无数的版本，备份系统必须真实记录数据的变更历史。如果对文件系统中每个文件的每次修改都生成一个“快照”，这不仅占用了大量的存储空间，而且随着数据量的增加，备份时间越来越长，备份效率也明显降低。对异地备份、在线备份或云备份而言，由于受到带宽、

存储空间和通信链路时延等因素局限性的制约，此种数据备份方式显然行不通。

云备份或者在线备份是一种新型的云存储服务，就是将本地数据复制到远程数据中心，此种类型的数据备份方式通常按照所使用的存储空间和数据流量计费。与传统的本地备份相比，云备份是以用户为中心，更加强调用户体验。备份过程中不能影响用户的操作，应尽量缩短备份时间，优化网络传输效率。为了确保备份数据的安全可靠，防止意外和人为误操作，云备份系统必须为所有需要备份的数据存储尽可能多的版本。即，此种数据备份方式需要保留备份数据的变更历史，这将造成云存储空间的巨大浪费，无形中增加了云存储的运营成本。

现有备份系统大都采用增量备份的方式，即仅将上次备份后发生了变更的数据复制到备份数据中心。增量备份要求本地和远程节点保留各自存储数据的元数据。有些备份系统只是简单地使用文件的修改时间作为元数据，通过比较上次备份的时间和文件的修改时间，只备份那些新修改的文件。显然这样的备份系统不仅容易产生人为的差错，而且无法甄别文件内的重复数据。为了弥补上述简单备份系统的不足，有些备份系统采用较为复杂的算法分析本地和远程节点文件内容并甄别文件内的重复数据，即重复数据删除技术简称去重或删冗技术。按照重复数据粒度，重复数据删除技术可分为文件级重复数据删除和数据块级重复数据删除。在数据备份领域，通常采用后者。

现有采用重复数据删除技术的备份系统通常在每次数据备份过程中相互交换待传输数据的数据块的哈希值，如果存储端已有哈希值对应的数据块，则无需传输该数据块，以尽可能地减少待传输的数据块的数量。然而此种类型备份系统中的备份过程之间相互独立，即每次备份过程都不会从之前的备份过程中获得相关信息，因此每次备份过程都需要对相同的文件进行重复切分和哈希计算，严重耗费本地资源。

发明内容

鉴于现有技术中存在的问题，本发明的目的是提出一种基于版本矢量的数据索引方法和服务器。

本发明提供了一种基于版本矢量的数据索引方法，其特征在于包括：

服务器端读取当前备份过程生成的数据，建立数据块哈希值和数据块位置之间的映射关系；

服务器端具有一个最新版本Ve，结合上次数据索引的版本Vi，确定本次索引的版本范围为[Vi,Ve]，并将哈希表和索引表载入内存完成初始化任务；

服务器端从元数据库中读取内有索引的所有版本文件，然后将与文件相关的信息加入到哈希表中，完成文件哈希索引，其中哈希表数据结构包括文件哈希值及版本标签。

优选的，其特征在于进一步包括：

服务器端将备份过程传来的数据文件与从元数据库中读取的内有索引的所有版本文件一起进行重新分块，并为所划分的数据块计算相应的哈希值，然后将数据块哈希值、版本标签、偏移量和数据块标识加入到索引表中。

优选的，其特征在于进一步包括：

服务器端对备份过程传来的重复数据的指针，读取元数据库中相应的数据块指针记录，并将数据块指针中的哈希值、版本标签、偏移量和数据块标识加入到索引表中。

优选的，其中所述哈希表数据结构还包括有文件指针标识，用于标识数据中的指针是文件指针还是数据块指针。

本发明还提供了一种可实现基于版本矢量的数据索引的服务器，其特征在于包括：

用于读取当前备份过程生成的数据，建立数据块哈希值和数据块位置之间的映射关系的模块；

用于根据服务器端具有的最新版本Ve，结合上次数据索引的版本Vi，确定本次索引的版本范围为[Vi,Ve]，并将哈希表和索引表载入内存完成初始化任务的模块；

用于从元数据库中读取内有索引的所有版本文件，然后将与文件相关的信息加入到哈希表中，完成文件哈希索引的模块，其中哈希表数据结构包括文件哈希值及版本标签。

优选的，其特征在于进一步包括：

用于将备份过程传来的数据文件与从元数据库中读取的内有索引的所有版本文件一起进行重新分块，并为所划分的数据块计算相应的哈希值，然后将数据块哈希值、版本标签、偏移量和数据块标识加入到索引表中的模块。

优选的，其特征在于进一步包括：

用于对备份过程传来的重复数据的指针，读取元数据库中的数据块指针记录，并将数据块指针中的哈希值、版本标签、偏移量和数据块标识加入到索引表中的模块。

优选的，其中所述哈希表数据结构还包括有文件指针标识，用于标识数据中的指针是文件指针还是数据块指针。

本发明在数据备份和还原过程中采用了独创的基于版本的重复数据删除方法。该方法使用版本矢量作为元数据，本地和远程节点共享交换版本矢量，本地节点只需要上次还原数据的版本信息就能准确判断哪些发生了变更的数据需要传输。基于哈希算法的重复数据删除方法需要传输所有数据块的哈希表，与之相比，基于版本的重复数据删除方法仅需传输已还原数据块的版本矢量，此种方式效率更高，节省了网络带宽并减少了备份时间。同时，通过本发明基于版本矢量的数据索引方法和服务器，对于重复数据仅需为数据块指针建立索引，此种方式效率更高，节省了建立数据索引的时间。

附图说明

图1例示了本发明基于版本矢量的数据备份方法的示意图。

图2例示了本发明基于版本矢量的数据还原方法的示意图。

图3例示了本发明基于版本矢量的数据备份方法的流程图。

图4例示了本发明基于版本矢量的数据索引方法的流程图。

图5例示了本发明基于版本矢量的数据还原方法的流程图。

具体实施方式

为使本发明的上述目的、特征和优点更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

云同步备份系统采用C/S体系结构，运行在本地节点的进程称为客户端，运行在远程节点的进程称为服务器端。云同步备份系统需要实现如下操作，即：将客户端的数据同步复制到服务器端，将服务器端的备份数据还原到客户端。所有操作均是由客户端发起，服务器端只是被动地接受客户端的请求。由客户端向服务器端的备份过程采用“推”的方式，而由服务器端向客户端的还原过程则采用“拉”的方式。

云同步备份系统基于客户端和服务器端之间共享交换的版本矢量，实现了重复数据删除。客户端在备份过程只完成重复数据删除的少量计算任务。为了尽可能地缩短备份时间，云同步备份系统还可以优选的采用管道机制，在甄别重复数据的同时进行数据同步复制。

云同步备份系统主要实现三个功能：

（1）数据备份：这是云同步备份系统最常用的功能，将客户端数据同步备份到服务器端，服务器端仅保留唯一的数据块；

（2）数据索引：仅在服务器端完成数据索引操作，在备份过程中为存储的数据建立索引，实现数据块哈希值和存储位置之间的映射；

（3）数据还原：将服务器端存储的备份数据还原至客户端，服务器端利用数据索引检索对应的数据块，实现数据还原操作。

图1例示了本发明基于版本矢量的数据备份方法的示意图。

如图1所示，数据备份由客户端发起，将同步目录中的数据同步备份到服务器端。假设客户端同步目录中只有两个文件，文件名分别为mydoc1和mydoc2。当备份过程启动后，首先读取同步目录中的所有文件，并为每个文件生成一个版本标签。然后将每个文件划分成多个数据块，并为每个数据块生成相应的哈希值。在本次备份过程中，如果存在有数据块与上次备份过程中已传输的数据块具有相同的哈希值，则将该数据块标记为重复数据块并以哈希值替代，然后与其他数据块一起发送至服务器端。当服务器端接收到客户端发送来的数据流后，分别将数据块和哈希值保存在文件系统和元数据库中。

数据索引操作由服务器端实现，建立数据文件和元数据之间的映射关系，并生成索引表。索引表的数据结构包括哈希值、版本号、偏移量、数据块大小和指针/数据标识。图1所述的数据备份过程中对应的索引表如下表所示。

哈希值	版本号	偏移量	数据块大小	指针/数据标识
					(abcd)	1	4	4	1
(qazw)	1	8	4	1
					(efgh)	1	12	4	1
(abcd)	1	16	4	0
					(wsxe)	2	4	4	1
(qazw)	2	8	4	0
					(efgh)	2	12	4	0

数据备份过程主要由客户端发起并实现，服务器端仅少量参与，而数据索引过程中的操作主要由服务器端实现，因此数据索引过程独立于数据备份过程。如此可以减轻数据备份过程中的任务负担，缩短备份时间。另外，数据索引过程仍采用增量变化的思想，即仅需要对上次数据索引后变化的数据文件和元数据建立索引，缩短了每次索引的时间，提高了数据索引的效率。

图2例示了本发明基于版本矢量的数据还原方法的示意图。

如图2所示，数据还原过程同样由客户端发起，但数据还原流程和数据备份流程刚好相反。客户端首先向服务器端发起对备份数据进行还原的请求，服务器端响应请求，将所需版本的数据块和指针发送给客户端，由客户端完成文件组合。

图3例示了本发明基于版本矢量的数据备份方法的流程图。

如图3所示，每次客户端将数据备份到服务器端时都创建一个类似“快照”的备份数据集合，服务器端以版本数据文件和元数据方式将“快照”保存到存储设备中。服务器端可以通过保存的版本数据文件和元数据快速重组“快照”。在数据备份过程中，为了提高备份效率，缩短备份时间，备份进程没有建立重组“快照”所需的索引表，而是交给独立的数据索引进程完成。数据备份过程中所涉及到的具体操作步骤包括初始化、读数据、生成数据块和哈希值、去重、数据传输、存储数据等。

（1）初始化

服务器端进程常驻内存并一直运行，等待客户端的任何请求。客户端启动数据备份进程，监控同步目录中文件的变化。首先客户端向服务器端发送服务器端状态数据请求，服务器端返回一个起始版本Vs和最新版本琉，这两个版本代表服务器端的最新状态信息。接着客户端读取本地数据，包括哈希表、快照表和数据块表等本地状态信息，完成初始化任务。

（2）读数据

读数据操作遍历同步目录中的所有文件和子目录，并对每个文件进行处理。首先按顺序生成文件版本标签，并在快照表中加入对应的记录，包括版本和文件名，用于数据还原。接着计算每个文件的哈希值，并向哈希表中新增记录，包括哈希值和对应文件的版本。如果哈希表中存在同样的哈希值，将所有具有同样哈希值的文件版本Vi与Vs及Ve比较。如果该文件版本介于Vs和Ve之间，即Vs<Vi≤Ve，说明该文件已经在服务器端存在，因此只需要将该文件所对应的指针发送到服务器端。另外，可将文件重复数据甄别操作和文件传输操作同时进行，如此能检测到读取的当前文件是否和正在备份的文件相同，实现文件级的重复数据删除，可大大提高重复数据删除的效率。而对那些非重复的文件将交给下个步骤处理，即“生成数据块”。

（3）生成数据块

生成数据块操作按照数据内容采用滑动窗口算法将文件划分为可变长度的数据块，并计算出每个数据块的哈希值，向数据块表中新增记录，包括数据块哈希值和对应的文件版本。然后通过下一个步骤实现数据块级的重复数据删除。

（4）甄别重复数据块

重复数据块甄别器使用本地的数据块表并结合Vs和Ve版本来识别重复数据块。本地的数据块表中记录有所有已传输的数据块的相关信息。对于上一个步骤中生成的新数据块的哈希值，如果本地数据块表中已有同样的哈希值，说明该数据块已经至少备份过一次。考虑到服务器端也有可能删除对应数据块的文件，采用上述文件级的重复数据甄别办法，如果该文件仍然存在于服务器端，则将该数据块标记为重复数据块，仅需要将该数据块对应的指针发送到服务器端。

（5）传输数据

将经过重复数据删除后的数据块打包、压缩和加密后以数据流的方式传输到服务器。在上述读数据以及生成数据块的同时，数据传输操作同步进行，如此可进一步缩短备份时间。数据包由版本标记和数据块标识（数据块或数据块指针）组成。版本标记包括版本、文件哈希值和文件名，数据块标识1代表数据块，0表示数据块指针。其中，数据块包括数据块大小和数据块内容，而数据块指针仅包含数据块的哈希值。由于数据块指针所包含的数据量远远小于数据块，因此，该数据传输方式可明显提高网络带宽的使用效率。

（6）保存数据

客户端启动数据备份过程后，服务器端进行初始化，并将快照表载入内存。服务器端的快照表与客户端的快照表在结构上完全一样，包含版本和文件名。服务器端接收到数据包后进行解包、解压和解密操作，还原原始数据包的格式。然后按照数据块标识区分数据块和数据块指针，将数据块写入备份目录，且所有相同版本的数据块都写入同一个文件；将数据块指针写入内置的元数据库，元数据结构包括文件哈希值、数据块哈希值和偏移量。同时向服务器端的快照表新增版本记录，包括版本和文件名。

当服务器端通知客户端已经接收完成最后一个数据块后，客户端将保存所有数据表，包括快照表、哈希表和数据块表，然后结束备份过程。

图4例示了本发明基于版本矢量的数据索引方法的流程图。

如图4所示，数据索引采用独立于备份进程的模式，可以减少备份过程对服务器端资源的消耗，缩短备份时间，提升备份系统的整体性能。数据索引进程仍采用增量方式，首先读取当前备份过程生成的数据，建立数据块哈希值和数据块位置之间的映射关系，用于数据还原操作。数据索引过程所涉及到的操作主要包括初始化、读数据、生成数据块和内容索引、生成元数据索引和写数据等。

（1）初始化

服务器端具有一个最新版本Ve，结合按照上次数据索引的版本Vi，可确定本次索引的版本范围为[Vi,Ve]，并将哈希表和索引表载入内存完成初始化任务。（2）读数据

首先从元数据库中读取内有索引的所有版本文件，然后将与文件相关的信息加入到哈希表中，完成文件哈希索引。哈希表数据结构包括文件哈希值、版本以及文件指针标识，文件指针标识1表示是文件指针，0表示是数据块指针。完成文件哈希索引后，读取数据文件内容交给下一步生成数据块和内容索引处理。

（3）生成数据块和内容索引

为了节省存储空间，数据文件由数据块串接而成，中间没有分隔符和其他数据。数据索引必须将备份过程传来的数据文件以及从元数据库中读取的数据文件进行重新分块，并为所划分的数据块计算相应的哈希值，然后将数据块哈希值、版本、偏移量和数据块标识加入到索引表中。如果所有数据块标识均为1，则表示为数据块而非数据块指针。如此，可完成数据文件的索引任务。

（4）生成元数据索引

完成数据文件索引后，可对备份过程传来的重复数据指针进行元数据索引。读取元数据库中相应的数据块指针记录，并将数据块指针中的哈希值、版本、偏移量和数据块标识加入到索引表中，所有数据块标识均为0，则表示为数据块指针。

图5例示了本发明基于版本矢量的数据还原方法的流程图。

如图5所示，数据还原操作是由客户端发起的，用于向服务器端请求还原之前备份的数据。客户端没有保存任何数据块，而服务器端保存了数据还原所需的所有信息，包括数据文件、元数据和索引表等。数据还原过程所涉及到的操作主要包括初始化和读数据、生成数据块和去重以及数据传输和文件重组等。

数据还原操作引入了两个临时数据表：还原哈希表和还原索引表。其中还原哈希表的数据结构和服务器端哈希表的数据结构一致，还原索引表的数据结构和服务器端索引表结构一致。还原哈希表中已存在的哈希值表示相应的版本文件已经发送到客户端，而还原索引表中已存在的哈希值则表示相应的数据块已经发送到客户端。

（1）初始化和读数据

客户端首先通过本地快照表获得所需还原的数据的版本。如果是执行第一次数据还原或者本地快照表损坏，服务器端会将其保存的快照表发送到客户端。当服务器端接收到客户端还原数据版本的请求后，将哈希表、索引表载入内存，并创建还原哈希表和还原索引表。对每个待还原的数据版本，首先读取元数据库中对应版本的哈希值，并在还原哈希表中检索对应的哈希值。如果该哈希值已经存在于还原哈希表中，则表明该数据版本已经发送到客户端，本次仅需要发送数据指针到客户端即可。如果还原哈希表中没有对应的该哈希值记录，则新增一条记录，包括哈希值和版本。同时对应版本的数据文件交给下一个步骤生成数据块处理。

（2）生成数据块和去重

与数据备份过程和数据索引过程中的数据块生成操作一样，数据还原过程中的生成数据块操作也是将数据文件划分为可变长度的数据块，并计算哈希值。同时读取已还原的数据版本的元数据，将该版本文件的数据块加入到还原索引表中，记录数据块哈希值和偏移量。

在处理数据块指针时，先检索还原索引表。如果还原索引表中没有相应的数据块指针记录，表明客户端没有该数据块指针对应的数据块内容，则可以从索引表中查询该数据块指针所对应的数据块的位置信息，读取数据块的内容并交给下一个步骤数据传输发送。同时在还原索引表中加入一条新的记录，包括数据块哈希值、版本、偏移量和数据块大小。如果还原索引表中已有该数据块指针相应的记录，则表明客户端已经接收了该数据块指针所对应的数据块内容，如此仅需要将数据块指针发送到客户端。与数据备份过程中的操作原理类似，数据还原操作使用还原索引表，实现了数据还原过程中的数据去重，避免了相同数据的重复传输，优化了网络带宽的利用率。

（3）数据传输和文件重组

数据传输将服务器端的数据包发送到客户端。与数据备份过程中的操作一样，服务器端首先将经过重复数据删除后的数据块进行打包、压缩以及加密，然后以数据流的方式传输到客户端。同样，数据传输操作也可以与读数据以及生成数据块操作同步进行，缩短客户端进行文件重组的等待时间。客户端接收到数据包后进行解包、解压和解密操作，还原原始数据包的格式。然后再对接收到的数据包进行文件重组，将相同版本的数据块和以数据块指针替代的数据块内容写入同一个文件。当客户端将所有版本数据处理完成，并将数据写入客户端用户指定的还原目录后结束数据还原操作。

以上主要通过方法步骤的形式介绍了本发明的优选实施例，本领域技术人员应当理解，本发明可以硬件、软件及硬件软件结合等方式实现，基于本说明书公开的内容可显而易见地获知这些实现方式。

当全部以计算机程序的方式实现本发明时，本发明中的客户端和服务器均可通过使用功能模块执行对应步骤的方式实现，这里不再对各功能模块一一赘述。

本领域的普通技术人员应该意识到，在本发明的范围内和精神指导下，各种改进、添加和替换都是可能的，例如调整接口调用顺序、改变消息格式和内容、使用不同的编程语言（如C、C++、Java等）实现等。这些都在本发明的权利要求所限定的保护范围内。

Claims (6)

1.一种基于版本矢量的数据索引方法，其特征在于包括：

服务器端读取当前备份过程生成的数据，建立数据块哈希值和数据块位置之间的映射关系；

服务器端具有一个最新版本Ve，结合上次数据索引的版本Vi，确定本次索引的版本范围为[Vi,Ve]，并将哈希表和索引表载入内存完成初始化任务；

服务器端从元数据库中读取内有索引的所有版本文件，然后将与文件相关的信息加入到哈希表中，完成文件哈希索引，其中哈希表数据结构包括文件哈希值及版本标签；

服务器将备份过程传来的数据文件与从元数据库中读取的所有版本文件重新分块，并为所划分的数据块计算相应的哈希值，然后将数据块哈希值、版本标签、偏移量和数据块标识加入到索引表中。

2.根据权利要求1所述的基于版本矢量的数据索引方法，其特征在于进一步包括：

服务器对备份过程传来的重复数据的指针，读取元数据库中相应的数据块指针记录，并将数据块指针中的哈希值、版本标签、偏移量和数据块标识加入到索引表中。

3.根据权利要求1或2所述的基于版本矢量的数据索引方法，其中所述哈希表数据结构还包括有文件指针标识，用于标识数据中的指针是文件指针还是数据块指针。

4.一种可实现基于版本矢量的数据索引的服务器，其特征在于包括：

用于读取当前备份过程生成的数据，建立数据块哈希值和数据块位置之间的映射关系的模块；

用于根据服务器端具有的最新版本Ve，结合按照上次数据索引的版本Vi，确定本次索引的版本范围为[Vi,Ve]，并将哈希表和索引表载入内存完成初始化任务的模块；

用于从元数据库中读取内有索引的所有版本文件，然后将与文件相关的信息加入到哈希表中，完成文件哈希索引的模块，其中哈希表数据结构包括文件哈希值及版本标签；

用于将备份过程传来的数据文件与从元数据库中读取的所有版本文件进行重新分块，并为所划分的数据块计算相应的哈希值，然后将数据块哈希值、版本标签、偏移量和数据块标识加入到索引表中的模块。

5.根据权利要求4所述的可实现基于版本矢量的数据索引的服务器，其特征在于进一步包括：

用于对备份过程传来的重复数据的指针，读取元数据库中的数据块指针记录，并将数据块指针中的哈希值、版本标签、偏移量和数据块标识加入到索引表中的模块。

6.根据权利要求4或5所述的可实现基于版本矢量的数据索引的服务器，其中所述哈希表数据结构还包括有文件指针标识，用于标识数据中的指针是文件指针还是数据块指针。