Data deduplication
AssigneeHewlett-Packard Development Company, L.P.
InventorsKave Eshghi, Mark D. Lillibridge, David M. Falkinder
Life of this patent
Estimating the term…
Abstract
A method for data deduplication includes receiving a set of hashes derived from a data chunk of a set of input data chunks 310. The method includes sampling the set of hashes 320, using an index indentifying data chunk containers that hold data chunks having a hash in the set of sampled hashes 330, and loading indexes for at least one of the identified data chunk containers 340. The method includes determining which of the hashes correspond to data chunks stored in data chunk containers corresponding to the loaded indexes 350 and deciding which of the set of input data chunks should be stored based at least in part on the determination.
Claims15
A method for data deduplication, comprising:
- receiving a set of hashes, wherein each hash of the set of hashes is derived from a data chunk of a set of input data chunks;
- sampling the set of hashes based on a set value for each of a predetermined number of bits in a string of hash bits, to form a sampled set of hashes;
- using an index, identifying data chunk containers that hold data chunks having a hash in the sampled set of hashes;
- loading indexes having the sampled set of hashes for at least one of the identified data chunk containers into a memory;
- determining which of the hashes in the set of the input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes;
- deciding which of the set of input data chunks should be stored based at least in part on determining which of the hashes of the set of input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes;
- and
- storing the chunks of the set of input data chunks that have been decided to be stored in one or more data chunk containers.
A system for performing data deduplication, comprising:
- a sampling module that samples a set of hashes based on a set value for each of a predetermined number of bits in a string of hash bits to form a sampled set of hashes corresponding to hashes sampled from data chunks of a data stream;
- one or more chunk container indexes that identify data chunk containers that hold data chunks having a hash in the sampled set of hashes;
- logic for loading indexes having the sampled set of hashes for at least one of the identified data chunk containers into a memory;
- logic for determining which of the hashes of the set of the input data chunks correspond to data chunks stored in data chunk containers corresponding to the loaded indexes;
- and
- logic for deciding which of the set of input data chunks should be stored based at least in part on determining which of the hashes of the set of input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes.
A non-transitory computer-readable medium having computer executable instructions store thereon that are executed by a processor to:
- sample a set of hashes based on a set value for each of a predetermined number of bits in a string of hash bits, wherein each hash of the set of hashes is derived from a data chunk of a set of input data chunks, to form a sampled set of hashes;
- use an index to identify data chunk containers that hold data chunks having a hash in the sampled set of hashes;
- load indexes having the sampled set of hashes for at least one of the identified data chunk containers into a memory;
- determining which of the hashes of the set of the input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes;
- and
- decide which of the set of input data chunks should be stored based at least in part on determining which of the hashes of the set of input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes.
Dependencies are inferred from the claim text.