Probabilistic algorithm to check whether a file is unique 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 file, the method comprising:

• separating the file into a plurality of chunks;
• choosing a chunk of the file;
• determining whether a hash of a content of the chunk is in a chunk hash data structure of a chunk store;
• if the hash of the content of the chunk is in the chunk hash data structure, performing a process for including all chunks of the file in the chunk store;
• and
• if the hash of the content of the chunk is not in the chunk hash data structure:
• for a number of chunks of the file, but not for all chunks of the file, determining whether a hash of a content of each of the number of chunks is in the chunk hash data structure;
• if the hash of the content of any one of the number of chunks is in the chunk hash data structure, performing the process for including all chunks of the file in the chunk store;
• and
• if none of the hashes of the contents of the number of chunks is in the chunk hash data structure, performing a process for including at least one of the chunks corresponding to the chunk and the number of chunks, but not all chunks of the file, in the chunk hash data structure.

A computer system comprising:

• a file;
• a chunk store;
• a chunk hash data structure;
• and
• at least one processor, wherein the at least one processor is programmed to carry out a method of deduplicating the file, the method comprising:
• separating the file into a plurality of chunks;
• choosing a chunk of the file;
• determining whether a hash of a content of the chunk is in the chunk hash data structure of the chunk store;
• if the hash of the content of the chunk is in the chunk hash data structure, performing a process for including all chunks of the file in the chunk store;
• and
• if the hash of the content of the chunk is not in the chunk hash data structure:
• for a number of chunks of the file, but not for all chunks of the file, determining whether a hash of a content of each of the number of chunks is in the chunk hash data structure;
• if the hash of the content of any one of the number of chunks is in the chunk hash data structure, performing the process for including all chunks of the file in the chunk store;
• and
• if none of the hashes of the contents of the number of chunks is in the chunk hash data structure, performing a process for including at least one of the chunks corresponding to the chunk and the number of chunks, but not all chunks of the file, in the chunk hash data structure.