CN102467572B - Data block query methods that support deduplicators - Google Patents

Abstract

A data block query method supporting a repeating data deleting procedure improves the speed of the repeating data deleting procedure for querying data blocks. The query method comprises the following steps: storing a hash index list in a server; generating a data block and a hash value according to an input file in a client; the client sends a query request to the server, and the hash value of the corresponding data block is recorded in the query request; when the hash value is not stored in the server, the server sends a storage requirement to the client, and adds the received hash value into a hash index list; establishing a corresponding associated data index list for the hash index list, and recording information of data blocks related to the hash values in the associated data index list; and when the hash value is stored in the server, returning the hash value in the corresponding associated data index list to the client according to the hash value.

Description

Data block query methods that support deduplicators

technical field

The invention relates to a data block query method, in particular to a data block query method supporting a duplicate data deletion program.

Background technique

Data deduplication is a data reduction technique, usually used in disk-based backup systems, with the main purpose of reducing the storage capacity used in the storage system. It works by looking for variable sized blocks of duplicate data at different locations in different files over a certain period of time. Duplicated data blocks are replaced with indicators. Because the storage system is always filled with a large amount of redundant data. In order to solve this problem and save more space, the "duplication deletion" technology has naturally become the focus of people's attention. Using "deduplication" technology can reduce the stored data to 1/20 of the original, so as to make more backup space, not only can save the backup data on the storage system for a long time, but also save the time of offline storage A lot of bandwidth is required.

In order to achieve the purpose of complete data preservation, the input file will be segmented during the process of data deduplication. After the input file is split, multiple data blocks will be generated. In order to effectively manage data blocks, index files are used to record various storage information of all data blocks during the splitting process.

After the client splits the entire input file (fixed length or variable length), it immediately generates the corresponding hash value of the data block. Then the client sends a query request to the server, and uses the hash value to ask the server whether the same hash value already exists. The server will search the hash index table for each query request, and then return the query results through the network. Please refer to FIG. 1 , which is a schematic diagram of a query data block in the prior art.

When the amount of data queried by the client 110 is very large, the hash index table will also increase sharply, and it may occur that the memory of the server 120 is not enough to store the hash index table. In this case, the hash index table will involve Querying a storage device with a slow access speed will greatly slow down the running speed of the entire system.

Contents of the invention

In view of the above problems, the technical problem to be solved by the present invention is to provide a data block query method that supports the deduplication program, which is applied to multiple data blocks generated by the deduplication program, and the data blocks are Query processing, thereby improving the query speed of data blocks.

In order to achieve the above object, the data block query method that supports the deduplication program disclosed in the present invention includes the following steps: storing a hash index list in the server, recording multiple groups of hash values in the hash index list; Load the input file in the file, and generate the data block of the corresponding input file and the hash value of each data block; the client sends a query request to the server, records the hash value of the corresponding data block in the query request, and uses To query the server whether there is the same hash value; when the hash value is not stored in the hash index list of the server, the server sends a storage request to the client to store the data block corresponding to the hash value Send it to the server for storage, and the server will add the received hash values to the hash index list in sequence; create a corresponding associated data index list for the hash values in the hash index list, and create a corresponding associated data index list in the associated data index Record other hash values related to the hash value in the list; when the server stores the hash value, the server will return the hash value in the corresponding associated data index list to the client according to the hash value; the client When querying the hash value of the data block next time, the client queries whether the hash value already exists from the received associated data index list; when the hash value already exists in the associated data index list received by the client, the associated Obtain the hash value information or the description information of the data block related to the hash value in the data index list, such as the number of times the data block has been referenced, which can be increased according to the reference needs; when there is no hash value in the associated data index list received by the client Hash value, the client will query the server for the hash value.

Since the associated data index list can indicate the association (front and back association) of the data blocks, and the server can continuously adjust the associated data index list according to the statistical information during use. Therefore, the hit rate of client queries in local memory can be guaranteed to a certain extent. The server can obtain a large number of related records at the cost of accessing the slow storage device once, which greatly reduces the problem that the client repeatedly performs query requests and causes the server to continuously read and query the slow storage device. At the same time, sending the data index set through the network at one time also reduces the time consumption of network access due to back and forth request/confirmation in the network.

The present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments, but not as a limitation of the present invention.

Description of drawings

FIG. 1 is a schematic diagram of a query data block in the prior art;

Fig. 2 is a schematic diagram of the architecture of the present invention;

Fig. 3 is a schematic diagram of the operation flow of the present invention;

FIG. 4 is a schematic diagram of a record-related data index set in the present invention.

Among them, reference signs

110 clients

120 server

210 server

211 hash index list

212 Linked Data Index List

220 clients

Detailed ways

Below in conjunction with accompanying drawing, structural principle and working principle of the present invention are specifically described:

Please refer to FIG. 2 , which is a schematic diagram of the architecture of the present invention. The present invention includes a server 210 and a client 220 . The client 220 can be connected to the server 210 through the Internet (Internet) or the enterprise intranet (intranet), and the client 220 and the server 210 can also be run on the same computing device at the same time. The server 210 also includes a hash Index list 211. The hash index list 211 records multiple sets of hash values. When the client 220 sends a query request to the server 210 for the hash value of a data block in an input file, the server 210 performs the query according to the content recorded in the hash index list 211 in the following manner. Please refer to FIG. 3 , which is a schematic diagram of the operation flow of the present invention.

Step S310: store the hash index list in the server, and record multiple sets of hash values in the hash index list;

Step S320: the client loads the input file, and generates data blocks of the corresponding input file and a hash value corresponding to each data block;

Step S330: the client sends a query request to the server, and records the hash value of the corresponding data block in the query request to query the server whether there is the same hash value;

Step S340: When the hash value is not stored in the hash index list of the server, the server sends a storage request to the client to transmit the data block corresponding to the hash value to the server for storage, and the server will The received hash values are sequentially added to the hash index list;

Step S350: Establish a corresponding associated data index list for the hash value in the hash index list, and record other hash values related to the hash value in the associated data index list; and

Step S360: When the hash value is stored in the server, the server returns the hash value in the corresponding associated data index list to the client according to the hash value.

The client 220 loads the input file, and the client 220 splits the input file, and generates data blocks of the corresponding input file and hash values corresponding to each data block. The algorithm for hash value calculation can be but not limited to SHA-1 or MD5. The data blocks are based on fixed-size partition or content-defined chunking (CDC). The fixed-length segmentation algorithm uses a predefined data block size to segment the input file. The advantages of the fixed-length block algorithm are simplicity and high performance. The content-defined segmentation algorithm is a variable-length block algorithm, which uses fingerprint data (such as Rabin fingerprint) to divide files into block strategies of different lengths. Different from the fixed-length segmentation algorithm, the content-defined segmentation algorithm performs data block segmentation based on the file content, so the size of the data block can be changed.

Next, the client 220 sends a query request to the server 210, and records the hash value of the corresponding data block in the query request to query the server 210 whether there is the same hash value. When the hash value is not stored in the hash index list 211 of the server 210, the server 210 sends a storage request to the client 220 to transmit the data block corresponding to the hash value to the server 210 for storage, and The server 210 sequentially adds the received hash values into the hash index list 211 . A corresponding associated data index list 212 is established for the hash value in the hash index list 211 , and the information of the data block related to the hash value is recorded in the associated data index list 212 . For example, the associated data index list 212 may store the hash value of the data block or the serial number of the data block, or the index information of the storage location of the data block.

Assume that the processing description of the query is performed from the first data block of the input file, and the server 210 has not recorded any data block of the input file. The client 220 first converts the first data block of the input file into a first hash value hash1 (corresponding to the first hash value hash1), and sends a query request to the server 210 with the first hash value hash1. Since the server 210 does not store the hash value of any data block of the input file, the server 210 writes the received first hash value hash1 (the first data block) into the server 210 . Similarly, the second data block (corresponding to the second hash value hash2) is still written to the server 210 according to the above process. The server 210 determines whether the first hash value hash1 and the second hash value hash2 are related according to the context of the two data blocks. The server 210 puts the second hash value hash2 into the associated data index list 212 of the first hash value hash1. Please refer to FIG. 4 , which is a schematic diagram of the record-related data index set of the present invention.

The hash values of other data blocks are also written into the associated data index list 212 of the first hash value hash1 according to their order. In the present invention, the capacity of the associated data index list 212 is limited. When the number of hash values in the associated data index list 212 meets the threshold value, the server 210 will not only continue to store the hash values in the next associated data index list 212, but also store the hash values after the query. The old hash value is deleted from the associated data index list 212, and the hash value of the latest query is recorded in the associated data index list 212.

For example, if the maximum capacity of the associated data index list 212 is to record 10 sets of hash values, then the related index records of the first hash value hash1 are the second hash value hash2 to the eleventh hash value hash11 (in other words, ten consecutive data blocks after the first data block).

After the twelfth hash value hash12 is generated, the server 210 will store the twelfth hash value hash12 in the associated data index list 212 of the eleventh hash value hash11. In addition, if a certain group of hash values is associated with other hash values at the same time, the associated data index list 212 of which hash value is stored can be used according to the relevant characteristics. Or save a copy of all relevant associated data index lists 212 .

The above situation is that the server 210 does not store any queryable hash value. When the hash value is stored in the server 210, the server 210 returns the hash value in the corresponding associated data index list 212 to the client 220 according to the hash value. Take the example above. When the client 220 wants to query the fifth data block (that is, query the fifth hash value hash5), since the fifth hash value hash5 in the server 210 is classified into the corresponding associated data of the first hash value hash1 index list 212. Therefore, in addition to returning the queried fifth hash value hash5 to the client 220 , the server 210 also transmits the associated data index list 212 of the first hash value hash1 to the client 220 at the same time.

After the client 220 receives the associated data index table, the client 220 stores the associated data index table in memory. When the client 220 inquires the hash value of the data block next time, the client 220 will start to inquire whether the hash value to be queried already exists from the received associated data index list 212 . When the hash value already exists in the associated data index list 212 received by the client 220 , the hash value is obtained from the associated data index list 212 . The data blocks to be queried may be continuous, so the access time between the client 220 and the server 210 can be effectively reduced by associating the data index list 212 , thereby improving access efficiency. On the contrary, when there is no hash value in the associated data index list 212 received by the client 220 , then the client 220 re-inquires the hash value from step S330 to step S360 to the server 210 .

Since the associated data index list 212 can indicate the association of data blocks (that is, the association of the sequence), and the server 210 can continuously adjust the associated data index list 212 according to statistical information during use. Therefore, the hit rate of the client 220 querying in the local memory can be guaranteed to a certain extent. The server 210 can obtain a large number of related records at the cost of one visit to the slow storage device, which greatly reduces the problem that the client 220 repeatedly performs query requests and causes the server 210 to continuously perform read queries on the slow storage device. At the same time, sending the data index set through the network at one time also reduces the time consumption of network access due to back and forth request/confirmation in the network.

Certainly, the present invention also can have other multiple embodiments, without departing from the spirit and essence of the present invention, those skilled in the art can make various corresponding changes and deformations according to the present invention, but these corresponding Changes and deformations should belong to the scope of protection of the appended claims of the present invention.

Claims (4)

1. A data block query method that supports a deduplication program is applied to multiple data blocks generated through a deduplication program, and the processing of querying the multiple data blocks is characterized in that , the data block query method supporting the deduplication program includes the following steps: storing a hash index list in a server, and recording multiple sets of hash values in the hash index list; A client loads an input file, and generates data blocks corresponding to the input file and hash values corresponding to each of the data blocks; The client sends a query request to the server, records the hash value of the corresponding data block in the query request, and queries the server whether there is the same hash value; When the hash value is not stored in the hash index list of the server, the server sends a storage request to the client to transmit the data block corresponding to the hash value to the stored in the server, and the server sequentially adds the received hash values into the hash index list; Establishing a corresponding associated data index list for the hash value added to the hash index list, and recording other hash values related to the hash value in the associated data index list; When the server stores the hash value, the server returns the corresponding hash value in the associated data index list to the client according to the hash value; When the client queries the hash value of the data block next time, the client queries whether the hash value already exists from the received associated data index list; When the hash value already exists in the associated data index list received by the client, obtain the hash value from the associated data index list; and When the hash value does not exist in the associated data index list received by the client, the client queries the server for the hash value. 2 . The data block query method supporting deduplication program according to claim 1 , wherein the data block is generated according to a fixed-length method or a content-based variable-length segmentation method. 3 . 3. The data block query method supporting de-duplication program according to claim 1, characterized in that, when the number of hash values in the associated data index list meets a threshold value, the longest time after the query The hash value of time is deleted from the associated data index list, and the hash value of the latest query is recorded in the associated data index list. 4. The data block query method supporting de-duplication program according to claim 1, characterized in that, when the number of hash values in the associated data index list meets a threshold value, the server will down - continue to store the hash value in the associated data index list.

Images