Data deduplication

1. 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.

2. The method of claim 1 , additionally comprising:

partitioning a portion of an input data stream into the set of input data chunks; and

determining a hash for each of the set of input data chunks prior to the receiving step to form the set of hashes.

3. The method of claim 1 , additionally comprising:

requesting the input data chunks that have been decided to be stored; and

receiving the input data chunks that have been decided to be stored.

4. The method of claim 1 wherein the index maps hashes of data chunks to sets of data chunk containers records information only for hashes that have been sampled.

5. The method of claim 1 wherein the set of hashes to form a sampled set of hashes further comprises choosing, on average, less than one fourth of the hashes.

6. The method of claim 1 wherein deciding which of the set of input data chunks should be stored further comprises deciding that an input data chunk should be stored if it is determined that the hash corresponding to the input data chunk is not included in the loaded indexes.

7. The method of claim 6 wherein the step of deciding which of the set of input data chunks should be stored additionally comprises deciding that an input data chunk should not be stored if it is determined that its hash is contained in the loaded indexes.

8. The method of claim 6 wherein deciding which of the set of input data chunks should be stored additionally comprises;

using container capping to determine a first set of data chunk containers in which to store the set of input data chunks; and

deciding to store input data chunks that do not have copies already stored in the first set of data chunk containers.

9. The method of claim 1 wherein storing the data chunks of the set of input data chunks comprises:

using a locality based assignment algorithm to assign the input data chunks to be stored to data chunk containers; and

storing the input data chunks to be stored in assigned data chunk containers.

10. 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.

11. The system of claim 10 , further comprising logic for storing the data chunks of the set of input data chunks that have been decided to be stored in one or more data chunk containers.

12. The system of claim 10 , further comprising logic for sampling hashes of the data chunks stored in data chunk containers arranged on the storage media.

13. The system of claim 10 , further comprising logic for deciding which of the set of input data chunks should be stored additionally based on;

container capping information to determine a first set of data chunk containers in which to store the set of input data chunks; and

that stores input data chunks based on determining that input data chunks do not have copies already stored in the first set of data chunk containers.

14. The system of claim 10 , further comprising logic for storing the data chunks of the set of input data chunks based on:

locality based assignment information that assigns the input data chunks to be stored to data chunk containers; and

that stores the input data chunks to be stored in assigned data chunk containers.

15. 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.