Granted Patent B2

US 8,442,956 · App. 13/351,192 · Granted May 14, 2013

Abstract

Claims (49)

1. A method for controlling a data de-duplication computer to selectively store or transmit a sub-block of data based on sub-block level sampling-based de-duplication, comprising:

controlling the data de-duplication computer to select a number of locations in the sub-block to be sampled and positions for the locations to be sampled, where the selecting is based on one or more of whether an entropy measure associated with the sub-block exceeds an entropy threshold, whether a sub-block size associated with the sub-block exceeds a size threshold, and whether the sub-block was chunked using fixed boundaries or data dependent boundaries;

controlling the data de-duplication computer to compute a sampling sequence for the sub-block of data, where the sampling sequence comprises data from the selected number of locations at the selected positions in the sub-block;

controlling the data de-duplication computer to use the sampling sequence to locate a stored sub-block known to the data de-duplication computer, comprising locating an entry point to a set of sampling sequence related sub-blocks, where the entry point is identified in a sampling sequence keyed index;

controlling the data de-duplication computer to determine a degree of similarity between the sub-block and the stored sub-block, where the degree of similarity is determined by one or more of:

comparing a hash of at least a portion of the sub-block to a hash of at least a portion of the stored sub-block;

comparing a delta hash associated with at least a portion of the sub-block to a delta hash associated with at least a portion of the stored sub-block; and

comparing one or more additional sampling sequences associated with the sub-block to one or more additional sampling sequences associated with the stored sub-block;

and

based on the degree of similarity, controlling:

whether the data de-duplication computer stores the sub-block and, when the sub-block is to be stored, identifying a storage format for the sub-block and controlling the data de-duplication computer to store the sub-block according to the identified storage format;

whether the data de-duplication computer transmits the sub-block and, when the sub-block is to be transmitted, identifying a transmission procedure for the sub-block and controlling the data de-duplication computer to transmit the sub-block according to the identified transmission procedure;

whether the data de-duplication computer updates a dedupe data structure and, when the dedupe structure is to be updated, identifying how the data de-duplication computer is to update the dedupe data structure and controlling the data de-duplication computer to update the dedupe data structure; and

whether the data de-duplication computer updates the sampling sequence keyed index and, when the sampling sequence keyed index is to be updated, identifying how the data de-duplication computer is to update the sampling sequence keyed index and controlling the data de-duplication computer to update the sampling sequence keyed index.

2. The method of claim 1 , where the sampling sequence comprises a weak hash computed from less than all the data in the sub-block.

3. The method of claim 1 , where the sampling sequence keyed index has a maximum size bounded by the number of the one or more locations sampled and an alphabet associated with the sub-block of data, and where the maximum size is less than the amount of physical memory in the data de-duplication computer.

4. The method of claim 1 , wherein said degree of similarity is determined performing two or more of comparing a hash, comparing a delta hash, and comparing one or more additional sampling sequences in parallel.

5. The method of claim 1 , comprising:

selectively dynamically altering one or more of the number of locations to be sampled, and the positions of locations to be sampled, based on one or more of whether an entropy measure associated with the sub-block exceeds an entropy threshold, whether a sub-block size associated with the sub-block exceeds a size threshold, and whether the sub-block was chunked using fixed boundaries or data dependant boundaries.

6. The method of claim 1 , where said controlling whether the data de-duplication computer stores the sub-block and, when the sub-block is to be stored, identifying a storage format for the sub-block and controlling the data de-duplication computer to store the sub-block according to the identified storage format comprises controlling the data de-duplication computer to perform one of:

storing the whole sub-block upon determining that the sub-block is a non-duplicate sub-block that does not satisfy a similarity threshold;

storing less than the whole sub-block upon determining that the sub-block is a non-duplicate sub-block that satisfies the similarity threshold;

storing something other than the sub-block from which the sub-block can be recreated upon determining that the sub-block is a non-duplicate sub-block that satisfies the similarity threshold;

not storing the sub-block upon determining that the sub-block is a duplicate; and

not storing the sub-block upon determining that the sub-block is a non-duplicate sub-block, that the sub-block satisfies a second similarity threshold, and that the sub-block is associated with data for which a threshold number of errors are acceptable.

7. The method of claim 1 , where said controlling whether the data de-duplication computer transmits the sub-block and, when the sub-block is to be transmitted, identifying a transmission procedure for the sub-block and controlling the data de-duplication computer to transmit the sub-block according to the identified transmission procedure comprises controlling the data de-duplication computer to perform one of:

transmitting the whole sub-block upon determining that the sub-block is a non-duplicate sub-block that does not satisfy a similarity threshold;

transmitting less than the whole sub-block upon determining that the sub-block is a non-duplicate sub-block that satisfies the similarity threshold;

transmitting something other than the sub-block from which the sub-block can be recreated upon determining that the sub-block is a non-duplicate sub-block that satisfies the similarity threshold;

not transmitting the sub-block upon determining that the sub-block is a duplicate; and

not transmitting the sub-block upon determining that the sub-block is a non-duplicate sub-block, that the sub-block satisfies a second similarity threshold, and that the sub-block is associated with data for which a threshold number of errors are acceptable.

8. The method of claim 1 , where controlling the data de-duplication computer to update the one or more data structures used for locating the stored sub-block comprises controlling the data de-duplication computer to perform one of:

updating a sampling sequence based index that stores entry points to groups of sampling sequence related stored sub-blocks;

updating a temporal index that stores information about known sub-blocks that are related by one or more of, arrival sequence, de-duplication sequence, and physical storage location;

updating a sampling sequence based tree that stores one or more of, information about known sampling sequence related stored blocks and entry points to groups of sampling sequence related stored sub-blocks;

updating a sampling sequence based list that stores one or more of, information about known sampling sequence related stored blocks and entry points to groups of sampling sequence related stored sub-blocks; and

updating a sampling sequence based graph that stores one or more of, information about known sampling sequence related stored blocks and entry points to groups of sampling sequence related stored sub-blocks.

9. The method of claim 1 , comprising:

controlling the data de-duplication computer to compute a sampling sequence for two or more sub-blocks of data and to aggregate the two or more sampling sequences into a single sampling sequence; and

controlling the data de-duplication computer to use the aggregated sampling sequence to locate a stored sub-block known to the data de-duplication computer.

10. The method of claim 1 , comprising:

controlling the data de-duplication computer to compute two or more different sampling sequences for the sub-block;

controlling the data de-duplication computer to locate two or more stored sub-blocks known to the data de-duplication computer, where the locating is based on the two or more different sampling sequences; and

controlling the data de-duplication computer to determine degrees of similarity between the sub-block and the two or more stored sub-blocks.

11. The method of claim 10 , comprising:

controlling the data de-duplication computer to compute the two or more different sampling sequences for the sub-block at least partially in parallel;

controlling the data de-duplication computer to locate the two or more stored sub-blocks at least partially in parallel; and

controlling the data de-duplication computer to determine the degrees of similarity at least partially in parallel.

12. A non-transitory computer-readable medium storing computer-executable instructions that when executed control a data de-duplication computer to perform the method of claim 1 .

Assignments (13)