Data reduction indexing

• US 8,423,519 B2
• Filed: 02/28/2011
• Issued: 04/16/2013
• Est. Priority Date: 03/08/2010
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Jeffrey Vincent Tofano
• Inventors: Tofano, Jeffrey Vincent
• Primary Examiner(s): Vu, Bai D.
• Application Number:
  US13/036,091
• Publication Number:
  US 20110218972A1
• Time in Patent Office: 778 Days
• Field of Search: None
• US Class Current: 707/692
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

Example apparatus, methods, data structures, and computers control indexing to facilitate duplicate determinations. One example method includes indexing, in a global index, a unique chunk processed by a data de-duplicator. Indexing the unique chunk in the global index can include updating an expedited data structure associated with the global index. The example method can also include selectively indexing, in a temporal index, a relationship chunk processed by the data de-duplicator. The relationship chunk is a chunk that is related to another chunk processed by the data de-duplicator by sequence, storage location, and/or similarity hash value. Indexing the relationship chunk in the temporal index can also include updating one or more expedited data structures associated with the temporal index. The expedited data structures and indexes can then be consulted to resolve a duplicate determination being made by a data reducer.

Claims

1. An apparatus, comprising:

a processor;

a memory; and

an interface that connects the processor, the memory, and a set of logics, the set of logics comprising;

a global index logic configured to store a set of location contexts in a global index and to search the global index for a hash to resolve a data reduction duplicate determination, where a location context comprises at least a fingerprint hash and a chunk location information; and

an ordered optimization index logic configured to store an ordered set of optimizations in an ordered optimization index and to search the ordered optimization index for the hash to resolve the data reduction duplicate determination without accessing the global index,

where the global index is a searchable data structure, and

where the ordered optimization index is a searchable data structure.

2. The apparatus of claim 1, where the global index logic is configured to store the set of location contexts in the global index arranged as a hash tree whose primary key is a hash field.

3. The apparatus of claim 2, where the ordered optimization index logic is configured to store the ordered set of optimizations in the ordered optimization index arranged as one or more hash trees.

4. The apparatus of claim 3, where the global index logic is configured to store the set of location contexts in the global index arranged as a partitioned index whose partitions are selectable as a function of a hash value.

5. The apparatus of claim 4, where the ordered optimization index logic is configured to store the ordered set of optimizations in one or more partitioned indexes whose partitions are selectable as a function of a hash value.

6. The apparatus of claim 5, where the global index logic is configured to maintain an expedited data structure to protect the global index and to access the expedited data structure before searching the global index for the hash.

7. The apparatus of claim 6, where the ordered optimization index logic is configured to maintain one or more expedited data structures to protect the ordered optimization index and to access the one or more expedited data structures before searching the ordered optimization index for the hash.

8. The apparatus of claim 1, where the global index logic is configured to store in the global index a location context for every unique chunk processed by a configurable variable data reducer associated with the data reduction.

9. The apparatus of claim 8, where the ordered optimization index logic is configured to store in the ordered optimization-index less location contexts than are stored in the global index.

10. The apparatus of claim 1:

where the ordered optimization index logic comprises a sequence logic configured to store, in a sequence index, sequence data describing sequence relationships between chunks processed by a data reducer, where the sequence relationships concern the order in which related chunks are processed by the data reducer;

where the sequence logic is configured to selectively pre-fetch sequence based duplicate determination resolving data for potentially resolving the data reduction duplicate determination based on the sequence data; and

where the sequence logic is configured to search the sequence index for the hash.

11. The apparatus of claim 1:

where the ordered optimization index logic comprises a location logic configured to store, in a location index, location data describing location relationships between chunks processed by a data reducer, where the location relationships identify data stored in locations that can be pre-fetched together;

where the location logic is configured to selectively pre-fetch location based duplicate determination resolving data for potentially resolving the data reduction duplicate determination based on the location data; and

where the location logic is configured to search the location index for the hash.

12. The apparatus of claim 1:

where the ordered optimization index logic comprises a relationship logic configured to store, in a relation index, similarity data describing similarity relationships between chunks processed by a data reducer, where the similarity relationships identify chunks that are not identical but that satisfy a similarity threshold as determined by a comparison of similarity hash values;

where the relationship logic is configured to selectively pre-fetch similarity based duplicate determination resolving data for potentially resolving the data reduction duplicate determination based on the similarity data; and

where the relationship logic is configured to search the relation index for the hash.

13. The apparatus of claim 10, where the ordered optimization index logic comprises:

a location logic configured to store, in a location index, location data describing location relationships between chunks processed by the data reducer, where the location relationships identify data stored in locations that can be pre-fetched together;

where the location logic is configured to selectively pre-fetch location based duplicate determination resolving data for potentially resolving the data reduction duplicate determination based on the location data; and

where the location logic is configured to search the location index for the hash; and

a relationship logic configured to store, in a relation index, similarity data describing similarity relationships between chunks processed by the data reducer, where the similarity relationships identify chunks that are not identical but that satisfy a similarity threshold as determined by a comparison of similarity hash values;

where the relationship logic is configured to selectively pre-fetch similarity based duplicate determination resolving data for potentially resolving the data reduction duplicate determination based on the similarity data; and

where the relationship logic is configured to search the relation index for the hash; and

where the ordered optimization index logic is configured to control one or more of the sequence logic, the location logic, and the relationship logic to search for the hash in parallel.

14. The apparatus of claim 1, where the data reduction duplication determination is associated with one or more of, a storage decision, and a transmission decision.

15. The apparatus of claim 1, the global index logic being configured to selectively store a chunk on a storage device and to selectively store a location context in the global index upon determining that the hash is not stored in the global index and therefore is a unique chunk.

16. An article of manufacture, comprising:

a non-transitory computer readable medium storing computer executable instructions that when executed by a computer control the computer to perform a method, the method comprising;

indexing, in a global index, a unique chunk processed by a data de-duplicator; and

selectively indexing, in a ordered optimization index, a relationship chunk processed by the data de-duplicator, where the relationship chunk is a chunk that is related to another chunk processed by the data de-duplicator by one or more of, sequence, storage location, and similarity hash value;

where indexing the unique chunk comprises;

storing a location context in a selected partition in the global index, the location context comprising a hash value computed from the unique chunk and information identifying where the unique chunk is stored in a storage system accessible to the de-duplicator; and

updating an expedited data structure associated with the selected partition in the global index to include the hash value computed from the unique chunk; and

where selectively indexing the relationship chunk comprises;

storing a hash value computed from the relationship chunk in one or more of, a partitioned sequence index, a partitioned location index, and a partitioned relation index; and

updating one or more expedited data structures associated with the one or more partitions in the one or more indexes into which the hash value is stored to include the hash value computed from the relationship chunk.

17. The article of manufacture of claim 16, the method comprising:

resolving a duplicate determination for the data de-duplicator based on determining whether a candidate hash provided by the data de-duplicator is located in one or more of, the ordered optimization index, and the global index;

where determining whether the candidate hash is located in the ordered optimization index comprises first determining whether the candidate hash is not located in the ordered optimization index by accessing an expedited data structure associated with the ordered optimization index and, if the ordered optimization index expedited data structure access is equivocal, searching the ordered optimization index for the candidate hash; and

where determining whether the candidate hash is located in the global index comprises first determining whether the candidate hash is not located in the global index by accessing an expedited data structure associated with the global index and, if the global index expedited data structure access is equivocal, searching the global index for the candidate hash;

where searching the ordered optimization index for the candidate hash and searching the global index for the candidate hash proceed in parallel, where an unequivocal determination in the ordered optimization index terminates searching the global index, and where an unequivocal determination in the global index terminates searching the ordered optimization index.

18. A memory for storing data for access by an application being executed on a data processing system, comprising:

a data structure stored in the memory, the data structure storing information used by the application and including;

a global index storing a complete set of location contexts associated with chunks processed by a data de-duplicator; and

an ordered optimization index storing an incomplete set of location contexts associated with chunks processed by the data de-duplicator;

where the global index is a hash tree whose primary key is a hash field, where the global index is partitioned, and where the global index is protected by at least one expedited data filter; and

where the ordered optimization index comprises;

a partitioned sequence index arranged as a hash tree and protected by an expedited data filter;

a partitioned location index arranged as a hash tree and protected by an expedited data filter; and

a partitioned relation index arranged as a hash tree and protected by an expedited data filter, and

where the ordered optimization index stores an ordered set of optimizations configured to facilitate resolving a duplicate determination for the data de-duplicator without accessing the global index.