US 8,527,482 B2Granted

Method for reducing redundancy between two or more datasets

AssigneeChrysalis Storage, LLC

InventorsSteve Heller, Ralph Shnelvar

Life of this patent

Estimating the term…

Loading patent…

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.

Claims18

Dependent claims

A method of reducing redundancy between two or more data sets comprising:

accessing a reference file comprising at least a plurality of data blocks, wherein the plurality of data blocks are hashed to identify duplicate data;
creating an oversubscribed hash table comprising a plurality of hash entries, wherein the oversubscribed hash table is oversubscribed based on the plurality of data blocks in the reference file by at least an oversubscribed ratio of 10:1 wherein for at least every 10 data blocks in the reference file there is a single hash entry in the hash table;
computing hash codes for the plurality of data blocks in the reference file and storing a subset of the hash codes in the hash entries in the oversubscribed hash table;
accessing a current file comprising at least a plurality of data blocks;
computing hash codes for a plurality of data blocks in the current file and comparing the hash codes associated with the current file to the hash entries in the oversubscribed hash table;
identifying a first pair of matching hash codes where a first hash code of one of the data blocks in the current file matches a first hash code in one of the hash entries in the oversubscribed hash table;
identifying a second pair of matching hash codes where a second hash code of one of the data blocks in the current file matches a second hash code of one of the hash entries in the oversubscribed hash table;
and
when the matching hash codes in the first and second pairs of matching hashes have a matching order and distance, comparing the data in the associated blocks of the current file and the reference file to identify a run of matching data in the current and reference files.

6 more elements

A system of reducing redundancy between two or more data sets comprising:

computer hardware comprising one or more computer processors configured to access a reference file comprising at least a plurality of data blocks, wherein the plurality of data blocks are hashed to identify duplicate data;
an oversubscribed hash table comprising a plurality of hash entries, wherein the oversubscribed hash table is oversubscribed based on the plurality of data blocks in the reference file by at least an oversubscribed ratio of 10:1 wherein for at least every 10 data blocks in the reference file there is a single hash entry in the hash table;
one or more computer processors configured to compute hash codes for the plurality of data blocks in the reference file and storing a subset of the hash codes in the hash entries in the oversubscribed hash table;
one or more computer processors configured to access a current file comprising at least a plurality of data blocks;
one or more computer processors configured to compute hash codes for a plurality of data blocks in the current file and compare the hash codes associated with the current file to the hash entries in the oversubscribed hash table;
one or more computer processors configured to identify a first pair of matching hash codes where a first hash code of one of the data blocks in the current file matches a first hash code in one of the hash entries in the oversubscribed hash table;
one or more computer processors configured to identify a second pair of matching hash codes where a second hash code of one of the data blocks in the current file matches a second hash code of one of the hash entries in the oversubscribed hash table;
and
when the matching hash codes in the first and second pairs of matching hashes have a matching order and distance, one or more computer processors are configured to compare the data in the associated blocks of the current file and the reference file to identify a run of matching data in the current and reference files.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/455,864Filed 8 Jun 2009 · us provisional application
Priority: 6 Jun 2008
Published: US 2009/0307251 A110 Dec 2009
Granted: 3 Sep 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 16/2365
Updating: ensuring data consistency and integrity
G06F 16/174
Details of further file system functions: redundancy elimination performed by the file system
G06F 16/217
Design, administration or maintenance of databases: database tuning
G06F 16/2379
Updating: updates performed during online database operations; commit processing