Delta compression of probabilistically clustered chunks of data
The invention pertains to a method and Information Handling System (IHS) for performing delta compression on probabilistically clustered chunks of data. From a source of chunks a corresponding sketch to represent each chunk is generated. Then, from the generated sketches a subset of similar sketches is determined using a probabilistic based algorithm. Finally, delta compression is performed on the chunks which are represented by the similar sketches in the determined subset.
1. A method of performing delta compression of multiple chunks of data, the method comprising:
from a source of chunks, generating multiple sketches to represent each chunk using a randomized process;
from the generated sketches, determining a subset of similar sketches based on a probabilistic based function; and
performing delta compression on the chunks of the source of chunks which are represented by the similar sketches in the determined subset, performing the delta compression including storing a given chunk from the source of chunks which are represented by the similar sketches in the determined subset and storing deltas for chunks, other than the given chunk, from the source of chunks which are represented by the similar sketches in the determined subset.
2. The method of claim 1 wherein the deltas are differences between the given chunk and the chunks, other than the given chunk, from the source of chunks which are represented by the similar sketches in the determined subset.
3. The method of claim 1 further comprising:
transferring the delta compressed chunks.
4. The method of claim 1 wherein each chunk is derived from files, logical block addresses, and/or a combination thereof.
5. The method of claim 1 wherein each chunk is a variable length piece of data.
6. The method of claim 1 further comprising:
generating the chunks using a hashing function on a collection of bytes.
7. The method of claim 6 wherein the hashing function is a Rabin fingerprint.
8. The method of claim 1 wherein each sketch is a vector.
9. The method of claim 1 wherein performance of the delta compression is a function of one or more of the following:
a user selected size of the sketches;
a user selected size of each element of the sketches;
an average size of each chunk;
a user selected number of sketches to generate for each chunk;
a user selected number of sketches in the subset of similar sketches;
a user selected number of subsets of similar sketches to determine;
tuning parameters of the probabilistic based function; and
a threshold for performing delta compression on the chunks which are represented by the similar sketches in the determined subset.
10. The method of claim 1 wherein each sketch is a reference hash.
11. The method of claim 1 further comprising generating the multiple sketches to represent each chunk by employing a function from the Locality Sensitive Hashing (LSH) family of functions.
12. The method of claim 1 wherein the probabilistic based function used to determine the subset of similar sketches is a function from the LSH family of functions.
13. The method of claim 1 further comprising:
performing further compression on the delta compressed chunks.
14. The method of claim 1 further comprising:
generating a corresponding first fingerprint for each chunk.
15. The method of claim 14 further comprising:
verifying the integrity of the delta compressed chunks by:
rebuilding the delta compressed chunks;
generating a corresponding fingerprint for each rebuilt chunk; and
comparing the generated fingerprint for each rebuilt chunk with the corresponding first fingerprints.
16. The method of claim 15 wherein the first fingerprint for each chunk and the fingerprint for each rebuilt chunk is generated using a SHA256 or a MD5 function.
17. The method of claim 1 further comprising:
loading a set of segments into high speed memory when a number of similar chunks in the set of segments is greater than a threshold, wherein each segment is a fixed size division of an object, the object is a collection of bits of fixed size and each chunk is a variable size subset of those bits.
18. An Information Handling System (IHS) comprising:
a processor; and
a memory with computer code instructions stored therein, the memory operatively coupled to said processor such that the computer code instructions configure the processor to implement:
a source of chunks;
a sketch generating module communicatively connected to the source of chunks and configured to generate multiple sketches for each chunk using a randomized process;
a grouping module configured to determine a subset of similar sketches from the generated sketches using a probabilistic based function; and
a compression module communicatively connected to the grouping module and configured to perform delta compression on the chunks which are represented by the similar sketches in the determined subset, performing the delta compression including storing a given chunk from the source of chunks which are represented by the similar sketches in the determined subset and storing deltas for chunks, other than the given chunk, from the source of chunks which are represented by the similar sketches in the determined subset.
19. The IHS of claim 18 wherein each chunk is derived from files, logical block addresses, and/or a combination thereof, each chunk being a variable length piece of data generated using a hashing function on a collection of bytes.
20. The IHS of claim 18 wherein the deltas are differences between the given chunk and the chunks, other than the given chunk, from the source of chunks which are represented by the similar sketches in the determined subset.