Method of reducing redundancy between two or more datasets

Abstract

A method for reducing redundancy between two or more datasets of potentially very large size. The method improves upon current technology by oversubscribing the data structure that represents a digest of data blocks and using positional information about matching data so that very large datasets can be analyzed and the redundancies removed by, having found a match on digest, expands the match in both directions in order to detect and eliminate large runs of data by replace duplicate runs with references to common data. The method is particularly useful for capturing the states of images of a hard disk. The method permits several files to have their redundancy removed and the files to later be reconstituted. The method is appropriate for use on a WORM device. The method can also make use of L2 cache to improve performance.

1 . A method of reducing redundancy between two or more data sets comprising:
 generating a plurality of first hash codes for a plurality of data blocks associated with one or more reference files, wherein the first hash codes are generated with a first hash algorithm executing in one or more computer processors;   storing one or more of the plurality of first hash codes in one or more hash entries in a hash table;   using the first hash algorithm to compute at least a first hash code for a current data block associated with a current file;   comparing the first hash code associated with the current data block with the one or more first hash codes stored in the one or more hash entries in the hash table;   when the first hash code of the current data block matches at least one of the first hash codes in the one or more hash entries in the hash table, generating a second hash code for the current data block, wherein the second hash code is generated with a second hash algorithm that is computationally more expensive than the first hash algorithm; and   when the second hash code for the current data block matches a second hash code associated with the first hash entry, comparing the data in at least one of preceding and succeeding data blocks of the current and reference files to identify a matching run of data in the current and reference files.   
     
     
         2 . The method of  claim 1  wherein the first hash algorithm is a rolling hash algorithm. 
     
     
         3 . The method of  claim 1  wherein the first hash algorithm is calculated as a function of an existing hash code and additional data items. 
     
     
         4 . The method of  claim 1  wherein the second hash algorithm is a non-rolling hash algorithm. 
     
     
         5 . The method of  claim 1  wherein the second hash algorithm is calculated based on at least one of the group consisting of: CRC64, MD5, and Secure Hash. 
     
     
         6 . The method of  claim 1  wherein the second hash code associated with the first hash entry is generated when the first hash code of the current data block matches the first hash code in the first hash entry in the hash table. 
     
     
         7 . The method of  claim 1  wherein the plurality of blocks in the current file have different boundaries than the plurality of blocks in the reference file. 
     
     
         8 . A system of reducing redundancy between two or more data sets comprising:
 computer hardware comprising one or more computer processors configured to generate a plurality of first hash codes for a plurality of data blocks associated with one or more reference files, wherein the first hash codes are generated with a first hash algorithm executing in one or more computer processors;   a hash table comprising a plurality of hash entries, wherein each hash entry comprises at least a first hash code based on a first hash algorithm;   one or more computer processors configured to use the first hash algorithm to compute at least a first hash code for a current data block associated with a current file;   one or more computer processors configured to compare the first hash code associated with the current data block with the one or more first hash codes stored in the one or more hash entries in the hash table;   when the first hash code of the current data block matches at least one of the first hash codes in the one or more hash entries in the hash table, one or more computer processors configured to generate a second hash code for the current data block with a second hash algorithm, wherein the second hash algorithm that is more computationally expensive than the first hash algorithm; and   when the second hash code for the current data block matches a second hash code associated with the first hash entry, one or more computer processors configured to compare the data in at least one of preceding and succeeding data blocks of the current and reference files to identify a matching run of data in the current and reference files.   
     
     
         9 . The system of  claim 8  wherein the first hash algorithm is a rolling hash algorithm. 
     
     
         10 . The system of  claim 8  wherein the first hash algorithm is calculated as a function of an existing hash code and additional data items. 
     
     
         11 . The system of  claim 8  wherein the second hash algorithm is a non-rolling hash algorithm. 
     
     
         12 . The system of  claim 8  wherein the second hash algorithm is calculated based on at least one of the group consisting of: CRC64, MD5, and Secure Hash. 
     
     
         13 . The system of  claim 8  wherein one or more computer processors are configured to generate the second hash code associated with the first hash entry when the first hash code of the current data block matches the first hash code in the first hash entry in the hash table. 
     
     
         14 . The system of  claim 8  wherein the plurality of blocks in the current file have different boundaries than the plurality of blocks in the reference file.