Granted Patent B1

US 8,078,593 · App. 12/549,787 · Granted Dec 13, 2011

Abstract

Claims (42)

1. A method of de-duplicating a volume of data, the method comprising:

partitioning the volume of data into input segments;

for each of the input segments, traversing nodes of a search tree in accordance with the value of a fixed-size portion of the input segment to determine if the search tree contains a pointer to a matching fixed-sized portion of a segment within a dictionary;

if the search tree contains the pointer:

comparing the input segment with the segment within the dictionary pointed to by the pointer; and

substituting a token representative of the segment within the dictionary for at least part of the input segment determined to match the segment within the dictionary; and

constructing the search tree based on fixed-size portions of multiple segments within the dictionary, wherein the search tree comprises at least a first search tree and a second search tree, and wherein adding branch nodes and leaf nodes within the search tree comprises:

adding branch and leaf nodes within the first search tree corresponding to the fixed-size portions of data;

associating respective code values with the leaf nodes within the first search tree;

concatenating at least two of the code values to generate a synthesized value; and

adding one or more branch nodes and a leaf node within the second search tree corresponding the synthesized value.

2. The method of claim 1 wherein constructing the search tree based on fixed-size portions of multiple segments within the dictionary comprises, for at least a first segment of the multiple segments, logically subdividing the first segment into fixed-size units of data and adding branch nodes and leaf nodes within the search tree corresponding to the fixed-size units of data, wherein the fixed-size units of data are the same size as the fixed-size portion of the input segment.

3. The method of claim 1 wherein traversing the nodes of a search tree comprises traversing the nodes of a first search tree to obtain a plurality of codes that correspond respectively to a plurality of units of data within the fixed-size portion of data.

4. The method of claim 3 wherein traversing the nodes of a search tree further comprises concatenating at least two of the codes that correspond to the plurality of units of data to synthesize a first search value and traversing the nodes of a second search tree to obtain a value that indicates a storage location of the matching fixed-size portion of the segment within the dictionary.

5. The method of claim 4 wherein traversing the nodes of a second tree to obtain a value that indicates a storage location of the matching fixed-size portion of the segment within the dictionary comprises traversing the nodes of the second tree to obtain an additional plurality of codes that correspond to plurality of units of data.

6. The method of claim 5 wherein traversing the nodes of a second tree to obtain a value that indicates a storage location of the matching fixed-size portion of the segment within the dictionary further comprises concatenating at least two codes of the additional plurality of codes to synthesize a second search value and traversing the nodes of a third search tree to obtain the value that indicates the storage location of the matching fixed-size portion of the segment within the dictionary.

7. The method of claim 6 wherein traversing the nodes of a third search tree to obtain the value that indicates the storage location of the matching fixed-size portion of the segment within the dictionary comprises traversing the nodes of the third search tree to obtain a list of one or more pointers, the list of one or more pointers including a pointer that indicates the storage location of the matching fixed-size portion of the segment within the dictionary.

8. The method of claim 7 wherein each of the first, second and third search trees each comprise a root node that points to a plurality of branch nodes, and wherein the root node within each of the first, second and third trees has the same number of maximum possible pointers to branch nodes.

9. The method of claim 3 wherein the nodes of the first search tree comprise a root node that points to a plurality of branch nodes and wherein the root node and each of the plurality of branch nodes have the same number of maximum possible pointers to nodes within the first search tree.

10. A data de-duplication apparatus comprising:

segmentation logic to partition a volume of data into input segments;

a storage component to store segments of data within a dictionary; and de-duplication logic to instantiate a search tree corresponding to the segments of data stored within the dictionary, and wherein, for each of the input segments, the de-duplication logic is adapted to traverse nodes of the search tree in accordance with the value of a fixed-size portion of the input segment to determine if the search tree contains a pointer to a matching fixed-sized portion of one of the segments of data within the dictionary, and, if the search tree contains the pointer, to compare the input segment with the segment within the dictionary pointed to by the pointer and to substitute a token representative of the segment within the dictionary for at least part of the input segment determined to match the segment within the dictionary, wherein the de-duplication logic to instantiate the search tree includes logic to instantiate the search tree based on fixed-size portions of the segments of data within the dictionary, the search tree including at least a first search tree and a second search tree, and wherein the logic to instantiate the search tree based on fixed-size portions of the segments of data within the dictionary includes logic to (i) add branch nodes and leaf nodes within the search tree corresponding to the fixed-size portions of the segments of data, (ii) associate respective code values with the leaf nodes within the first search tree, (iii) concatenate at least two of the code values to generate a synthesized value, and (iv) add one or more branch nodes and a leaf node within the second search tree corresponding to the synthesized value, and wherein the de-duplication logic is implemented at least in part by at least one of a programmed processor, application-specific integrated circuit (ASIC), or programmable gate array.

11. The data de-duplication apparatus of claim 10 wherein the de-duplication dictionary logic adapted to traverse the nodes of the search tree comprises logic to traverse the nodes of the first search tree to obtain a plurality of codes that correspond respectively to a plurality of units of data within the fixed-size portion of the input segment.

12. The data de-duplication apparatus of claim 11 wherein the logic to traverse the nodes of the search tree further comprises logic to concatenate at least two of the codes that correspond to the plurality of units of data within the fixed-size portion of the input segment to synthesize a first search value and to traverse the nodes of the second search tree to obtain a value that indicates a storage location of the matching fixed-size portion of the one of the segments of data within the dictionary.

13. The data de-duplication apparatus of claim 12 wherein the logic to traverse the nodes of the second tree to obtain the value that indicates the storage location of the matching fixed-size portions of the one of the segments of data within the dictionary comprises logic to traverse the nodes of the second tree to obtain an additional plurality of codes that correspond to another plurality of units of data.

14. The data de-duplication apparatus of claim 13 wherein the logic to traverse the nodes of the second tree to obtain the value that indicates the storage location of the matching fixed-size portions of the one of the segments of data within the dictionary further comprises logic to concatenate at least two codes of the additional plurality of codes to synthesize a second search value and logic to traverse the nodes of a third search tree to obtain the value that indicates the storage location of the matching fixed-size portion of the one of the segments of data within the dictionary.

15. The data de-duplication apparatus of claim 14 wherein the logic to traverse the nodes of the third search tree to obtain the value that indicates the storage location of the matching fixed-size portion of the one of the segments of data within the dictionary comprises logic to traverse the nodes of the third search tree to obtain a list of one or more pointers, the list of one or more pointers including a pointer that indicates the storage location of the matching fixed-size portion of the one of the segments of data within the dictionary.

16. The data de-duplication apparatus of claim 15 wherein each of the first, second and third search trees each comprise a root node that points to a plurality of branch nodes, and wherein the root node within each of the first, second and third trees has the same number of maximum possible pointers to branch nodes.

17. A data de-duplication apparatus comprising:

means for partitioning the volume of data into a plurality of input segments;

means for storing segments of data within a dictionary;

means for traversing nodes of a search tree in accordance with the value of a fixed-size portion of each input segment of the plurality of input segments to determine if the search tree contains a pointer to a matching fixed-sized portion of one of the segments of data within the dictionary;

means for comparing the input segment with the one of the segments of data within the dictionary pointed to by the pointer if the search tree contains the pointer;

means for substituting a token representative of the one of the segments of data within the dictionary for at least part of the input segment determined to match the one of the segments of data within the dictionary if the search tree contains the pointer; and

means for instantiating the search tree based on fixed-size portions of the segments of data within the dictionary, the search tree including at least a first search tree and a second search tree, and wherein the means for instantiating the search tree based on fixed-size portions of the segments of data within the dictionary includes (i) means for adding branch nodes and leaf nodes within the search tree corresponding to the fixed-size portions of the segments of data, (ii) means for associating respective code values with the leaf nodes within the first search tree, (iii) means for concatenating at least two of the code values to generate a synthesized value, and (iv) means for adding one or more branch nodes and a leaf node within the second search tree corresponding to the synthesized value.

18. A computer-readable storage medium having one or more sequences of instructions embodied therein which, when executed by a processing unit, cause the processing unit to:

partition a volume of data into a plurality of input segments;

store segments of data within a dictionary

traverse nodes of a search tree in accordance with the value of a fixed-size portion of each input segment of the plurality input segments to determine if the search tree contains a pointer to a matching fixed-sized portion of one of the segments of data within the dictionary;

compare the input segment with the one of the segments of data within the dictionary pointed to by the pointer if the search tree contains the pointer;

substitute a token representative of the one of the segments of data within the dictionary for at least part of the input segment determined to match the one of the segments of data within the dictionary if the search tree contains the pointer; and

instantiate the search tree based on fixed-size portions of the segments of data within the dictionary, the search tree including at least a first search tree and a second search tree, and wherein the one or more sequences of instructions that cause the processing unit to instantiate the search tree based on fixed-size portions of the segments of data within the dictionary include one or more sequences of instructions that cause the processing unit to (i) add branch nodes and leaf nodes within the search tree corresponding to the fixed-size portions of the segments of data, (ii) associate respective code values with the leaf nodes within the first search tree, (iii) concatenate at least two of the code values to generate a synthesized value, and (iv) add one or more branch nodes and a leaf node within the second search tree corresponding to the synthesized value.

Assignments (21)