Organize chunk store to preserve locality of hash values and reference counts for deduplication

A non-transitory computer readable medium comprising instructions to be executed in a processor of a computer system, the instructions when executed in the processor cause the computer system to carry out a method of deduplicating a first file, the first file comprising a first chunk, the method comprising:

• determining if a first hash of a first content of the first chunk is in a chunk hash data structure, wherein the chunk hash data structure comprises a first plurality of key-value mappings between a first plurality of keys and a first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk, and the first plurality of values each being a chunk ID of the corresponding chunk;
• and
• if the first hash of the first content of the first chunk is not in the chunk hash data structure:
• adding a first key-value mapping to the chunk hash data structure, the first key-value mapping comprising (a) a first key that is the first hash of the first content of the first chunk, and (b) a first value that is a first chunk ID of the first chunk;
• and
• adding a second key-value mapping to a chunk ID data structure, wherein the chunk ID data structure comprises a second plurality of key-value mappings between a second plurality of keys and a second plurality of values, the second plurality of keys being the chunk IDs of the chunk hash data structure, and the second plurality of values being sets of information about the corresponding chunk, and wherein ordering of chunk IDs within the chunk ID data structure serves to preserve locality of the sets of information with respect to the corresponding chunks.

A computer system comprising:

• a first file;
• a chunk hash data structure;
• a chunk ID data structure;
• and
• at least one processor, wherein the at least one processor is programmed to carry out a method of deduplicating the first file, the first file comprising a first chunk, the method comprising:
• determining if a first hash of a first content of the first chunk is in the chunk hash data structure, wherein the chunk hash data structure comprises a first plurality of key-value mappings between a first plurality of keys and a first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk, and the first plurality of values each being a chunk ID of the corresponding chunk;
• and
• if the first hash of the first content of the first chunk is not in the chunk hash data structure:
• adding a first key-value mapping to the chunk hash data structure, the first key-value mapping comprising (a) a first key that is the first hash of the first content of the first chunk, and (b) a first value that is a first chunk ID of the first chunk;
• and
• adding a second key-value mapping to the chunk ID data structure, wherein the chunk ID data structure comprises a second plurality of key-value mappings between a second plurality of keys and a second plurality of values, the second plurality of keys being the chunk IDs of the chunk hash data structure, and the second plurality of values being sets of information about the corresponding chunk, and wherein ordering of chunk IDs within the chunk ID data structure serves to preserve locality of the sets of information with respect to the corresponding chunks.