SYSTEMS AND METHODS FOR DATA DEDUPLICATION BY GENERATING SIMILARITY METRICS USING SKETCH COMPUTATION
A method for data reduction may comprise computing (i) a first sketch of a first segment and (ii) a second sketch of a second segment. The first sketch and the second sketch may each comprise a set of features that are representative of or unique to the corresponding first and second segments. The method also comprise processing the first sketch and the second sketch to generate a similarity metric indicative of whether the second segment is similar to the first segment. The method may further comprise (1) performing a differencing operation on the second segment relative to the first segment when the similarity metric is greater than or equal to a similarity threshold, or (2) storing the first segment and the second segment in a database without performing the differencing operation when the similarity metric is less than the similarity threshold.
1 . (canceled)
2 . A computer-implemented method for data processing based on variable segment sizing, comprising:
(a) receiving a first input data stream and information about a target segment size;
(b) applying a hash function to the first input data stream to identify a natural break in the first input data stream, and identifying a chunk based at least in part on the natural break; and
(c) identifying a segment by i) repeating (b) and ii) summing up lengths of a first set of chunks to determine whether a sum of the lengths falls within the target segment size.
3 . The computer-implemented method of claim 2 , wherein the natural break is identified by using a sliding window and applying the hash function to the sliding window to generate a region hash.
4 . The computer-implemented method of claim 3 , wherein the sliding window has a size of 4-16 kB.
5 . The computer-implemented method of claim 3 , wherein the region hash is a rolling hash.
6 . The computer-implemented method of claim 2 , further comprising computing a first sketch of the segment comprising a set of features that are representative of or unique to the segment.
7 . The computer-implemented method of claim 6 , wherein the set of features are computed using a first subset of chunks selected from the first set of chunks.
8 . The computer-implemented method of claim 7 , wherein the set of features are computed based on a plurality of hashes of the first subset of chunks.
9 . The computer-implemented method of claim 8 , wherein the plurality of hashes are generated using one or more hashing algorithms selected from the group consisting of Secure Hash Algorithm 0 (SHA-0), Secure Hash Algorithm 1 (SHA-1), Secure Hash Algorithm 2 (SHA-2), and Secure Hash Algorithm 3 (SHA-3).
10 . The computer-implemented method of claim 6 , further comprising receiving a second sketch of a reference segment.
11 . The computer-implemented method of claim 10 , further comprising processing the first sketch and the second sketch to generate a similarity metric indicative of whether the segment is similar to the reference segment.
12 . The computer-implemented method of claim 11 , further comprising when the similarity metric is equal to or greater than a similarity threshold, performing a differencing operation on the segment and the reference segment to determine a difference between the segment and the reference segment at a chunk level.
13 . The computer-implemented method of claim 12 , wherein the differencing operation comprises: receiving a reference set of hashes of the reference segment and generating a second set of hashes based on the first set of chunks, and comparing the first set of hashes to the reference set of hashes in a sequential order.
14 . The computer-implemented method of claim 13 , wherein the first set of hashes are weak hashes.
15 . The computer-implemented method of claim 13 , wherein the reference set of hashes are generated based on a set of chunks of the reference segment and are stored in a memory table.
16 . The computer-implemented method of claim 15 , wherein the reference set of hashes are generated using a hashing algorithm selected based at least in part on the similarity metric.
17 . The computer-implemented method of claim 16 , wherein a hashing strength of the hashing algorithm is selected based at least in part on the similarity metric.
18 . The computer-implemented method of claim 12 , wherein the similarity threshold is at least 50%.
19 . The computer-implemented method of claim 11 , further comprising when the similarity metric is less than a similarity threshold, storing the segment in a database without performing a differencing operation.
20 . The computer-implemented method of claim 2 , wherein the target segment size ranges from 1 megabyte (MB) to about 16 MB.
21 . The computer-implemented method of claim 2 , wherein the first set of chunks have variable lengths depending on the natural break.