De-duplication indexing
View Patent ↗Example apparatus, methods, and computers support data de-duplication indexing. One example apparatus includes a processor, a memory, and an interface to connect the processor, memory, and a set of logics. The set of logics includes an establishment logic to instantiate one-to-many de-duplication data structures, a manipulation logic to update the de-dupe data structure(s), a key logic to generate a key from a block of data to be de-duplicated, and a similarity logic to make a similarity determination for the block. The similarity determination identifies the block as a unique block, a duplicate block, or a block that meets a similarity threshold with respect to a stored de-duplicated block accessible through the dedupe data structure. The similarity determination involves comparing the block to be de-duplicated to a stored block available to the apparatus using a byte-by-byte approach, a hash approach, a delta hash approach and/or a sampling sequence approach.
1. An apparatus, comprising:
a processor;
a memory; and
an interface to connect the processor, the memory, and a set of logics, the set of logics comprising:
an establishment logic configured to instantiate a first one-to-many de-duplication data structure that is configured to receive a key value and to return one or more items that facilitate making one or more of, a decision concerning whether a similarity determination is to be made, and a similarity determination for a block of data to be de-duplicated,
where the key value is one of, a sample taken from the block of data, the sample being less than the entire block of data, a weak hash computed from the block of data, the weak hash being susceptible to hash collisions, the weak hash being unsuitable for a duplicate determination, and an aggregation of two or more samples taken from blocks of data to be de-duplicated,
where the similarity determination classifies the block of data to be de-duplicated as being one of at least three items: a unique block, a duplicate block, or a block that meets a similarity threshold with respect to a stored de-duplicated block accessible to the apparatus through the one-to-man de-duplication data structure,
where the one or more items that facilitate making the similarity determination are a de-duplication data structure identifier, a de-duplication data structure ent identifier a de-duplication process identifier or a de-duplication process entry point; and
a manipulation logic configured to selectively update the one-to-many de-duplication data structure by performing one or more of, adding an item that facilitates making the similarity determination, and deleting an item that facilitates making the similarity determination.
2. The apparatus of claim 1 , where the de-duplication data structure is one of, an index, a tree, a list, and a graph.
3. The apparatus of claim 1 , where the one-to-many de-duplication data structure is configured to fit in the memory.
4. The apparatus of claim 1 , where the establishment logic is configured to instantiate a second one-to-many de-duplication data structure and to arrange the second one-to-many de-duplication data structure to be reachable via the first one-to-many de-duplication data structure.
5. The apparatus of claim 1 , where the manipulation logic selectively updates the first one-to-many de-duplication data structure as a function of a similarity determination associated with a block of data.
6. An apparatus, comprising:
a processor;
a memory; and
an interface to connect the processor, the memory, and a set of logics, the set of logics comprising:
a key logic configured to generate a key value from a block of data to be de-duplicated, where the key value is configured to access a one-to-many de-duplication data structure that is configured to receive a key value and to return an item that facilitates determining making a similarity determination for a block of data to be de-duplicated,
where the key value is one of, a sample taken from the block of data, the sample being less than the entire block of data, a weak hash computed from the block of data, and an aggregation of two or more samples taken from blocks of data to be de-duplicated,
where the key logic selects the one-to-many de-duplication data structure from two or more available one-to-man de-duplication data structures based on an entropy associated with the block, a data type associated with the block, the size of the block, or the probability that the block is a duplicate; and
a similarity logic configured to make the similarity determination for the block of data to be de-duplicated, where the similarity determination is made as a function of the item, where the similarity determination identifies the block as being one of at least three items: a unique block, a duplicate block, or a block that meets a similarity threshold with respect to a stored de-duplicated block accessible to the apparatus through the one-to-many de-duplication data structure.
7. The apparatus of claim 6 , where the one-to-many de-duplication data structure is one of, an index, a tree, a list, and a graph.
8. The apparatus of claim 6 , where the item that facilitates making a similarity determination is one of, a block of data, a de-duplication data structure identifier, a de-duplication data structure entry identifier, a de-duplication process identifier, and a de-duplication process entry point.
9. The apparatus of claim 6 , where the similarity logic is configured to make the similarity determination by comparing the block to be de-duplicated to a stored block available to the apparatus through the one-to-many de-duplication data structure, where the comparing comprises one or more of:
a byte-by-byte comparison between at least a portion of the block to be de-duplicated and at least a portion of the stored block;
comparing a hash of at least a portion of the block to be de-duplicated to a hash of at least a portion of the stored block;
comparing a delta hash associated with at least a portion of the block to be de-duplicated to a delta hash associated with at least a portion of the stored block; and
comparing one or more additional sampling sequences associated with the block to be de-duplicated to one or more additional sampling sequences associated with the stored block.
10. The apparatus of claim 9 , where the similarity logic is configured to make the similarity determination by performing two or more comparisons in parallel.
11. The apparatus of claim 9 , where the key logic is configured to selectively repetitively generate key values and where the similarity logic is configured to selectively repetitively make similarity determinations until a threshold similarity is determined.
12. The apparatus of claim 9 , where the similarity logic is configured to make the similarity determination without updating the one-to-many de-duplication data structure.
13. An apparatus, comprising:
a processor;
a memory; and
an interface to connect the processor, memory, and a set of logics, the set of logics comprising:
an establishment logic configured to instantiate a first one-to-many de-duplication data structure that is configured to receive a value and to return one or more items that facilitate making a similarity determination for a block of data to be de-duplicated, where the one-to-many de-duplication data structure is configured to fit in the memory;
a manipulation logic configured to selectively update the one-to-many de-duplication data structure by adding or deleting an item that facilitates making a similarity determination for a block of data to be de-duplicated;
a key logic configured to generate a key value from a block of data to be de-duplicated, where the key value is configured to access the one-to-many de duplication data structure; and
a similarity logic configured to make a similarity determination for the block of data as a function of the item, where the similarity determination identifies a block being de-duplicated as one of, a unique block, a duplicate block, and a block that meets a similarity threshold with respect to a stored de-duplicated block accessible to the apparatus through the one-to-many de-duplication data structure, where the similarity logic is configured to make the similarity determination by comparing the block to be de-duplicated to a stored block available to the apparatus through the one-to-many de-duplication data structure, where the comparing comprises one or more of:
a byte-by-byte comparison between at least a portion of the block to be de-duplicated and at least a portion of the stored block;
comparing a hash of at least a portion of the block to be de-duplicated to a hash of at least a portion of the stored block;
comparing a delta hash associated with at least a portion of the block to be de-duplicated to a delta hash associated with at least a portion of the stored block; and
comparing one or more additional sampling sequences associated with the block to be de-duplicated to one or more additional sampling sequences associated with the stored block.
14. A method, comprising:
receiving a key value associated with a block to be de-duplicated;
selecting a one-to-many data de-duplication data structure to access using the key value;
acquiring an item from a location in the data de-duplication data structure, where the location is a function of the key value, and where the item identifies a set of items upon which a similarity determination for the block to be de-duplicated can be made; and
performing one or more of, making the similarity determination based, at least in part, on the set of items, and deciding not to make the similarity determination.
15. The method of claim 14 , comprising:
upon determining that the set of items are insufficient to make a data de-duplication similarity determination for the block to be de-duplicated, repetitively:
generating additional keys associated with one or more of, the block to be de-duplicated, and one or more of the set of items;
selecting second one-to-many data de-duplication data structures to access using the additional keys;
acquiring additional items from locations in the second data de-duplication data structures, where the locations are a function of the additional keys, and where the additional items identify additional sets of items upon which a similarity determination for the block to be de-duplicated can be made; and
making the similarity determination based, at least in part, on the additional sets of items.
16. The method of claim 14 , comprising:
instantiating the one-to-many de-duplication data structure; and
selectively updating the one-to-many de-duplication data structure by performing one or more of, adding an item that facilitates making the similarity determination, and deleting an item that facilitates making the similarity determination.