Use of solid state storage devices and the like in data deduplication
AssigneeFalconStor, Inc.
InventorChin L. Kuo
Life of this patent
Estimating the term…
Abstract
Systems and methods of data deduplication are disclosed comprising generating a hash value of a data block and comparing the hash value to a table in a first memory that correlates ranges of hash values with buckets of hash values in a second memory different from the first memory. A bucket is identified based on the comparison and the bucket is searched to locate the hash value. If the hash value is not found in the bucket, the hash value is stored in the bucket and the data block is stored in a third memory. The first memory may be volatile memory and the second memory may be non-volatile random access memory, such as an SSD. Rebalancing of buckets and the table, and use of additional metadata to determine where data blocks should be stored, are also disclosed.
Claims13
A method of deduplicating data, comprising:
- providing a plurality of hash buckets in memory, each hash bucket storing a respective range of hash values corresponding to deduplicated data blocks;
- grouping the plurality of hash buckets into respective groups of hash buckets having adjacent hash value ranges, wherein each group includes at least a first hash bucket and a second hash bucket having adjacent ranges of hash values, and each group has a respective range of hash values stored within the group;
- monitoring the hash values stored in the hash buckets in the respective groups;
- only changing the respective ranges of hash values in a first hash bucket and a second hash bucket within a respective group without changing the range of hash values stored within the group based, at least in part, on a degree the first hash bucket in the respective group is full;
- and
- moving hash values only from the first hash bucket to the second hash bucket within the respective group to match the changed ranges.
A deduplication system comprising:
- memory;
- and
- at least one processing device configured to:
- provide a plurality of hash buckets in the memory, each hash bucket to store a respective range of hash values corresponding to deduplicated data blocks;
- group the plurality of hash buckets into respective groups of hash buckets, wherein each group includes at least a first hash bucket and a second hash bucket having adjacent ranges of hash values, and each group has a respective range of hash values stored within the group;
- monitor the hash values stored in each hash bucket in the respective groups;
- only change the respective ranges of hash values in a first hash bucket and a second hash bucket within a respective group without changing the range of hash values stored within the respective group based, at least in part, on a degree the first hash bucket is full;
- and
- only move hash values from the first hash bucket to the second hash bucket within the respective group to match the changed ranges.
Dependencies are inferred from the claim text.