Techniques for global single instance segment-based indexing for backup data

• US 8,214,376 B1
• Filed: 12/31/2007
• Issued: 07/03/2012
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Jordan, Kevin Elliott, Subramanyam, Annandata Bhaskar, Dasgupta, Devasis
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US11/967,630
• Time in Patent Office: 1,646 Days
• Field of Search: 707/755, 707/736
• US Class Current: 707/755
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 2201/83 the solution involving signatures

Abstract

Techniques for global single instance segment-based indexing are disclosed. In one particular exemplary embodiment, the techniques may be realized as a method for global single instance segment-based indexing for backup data. The method may comprise dividing an item being backed up into segments, generating a fingerprint for each segment, and saving an entry for each segment in an index database. Each entry may comprise the fingerprint for the segment.

Claims

1. A method for performing global single instance segment-based indexing for backup data comprising:

parsing a non-executable data item being backed up to detect one or more syntactic boundaries within the non-executable data item being backed up between adjacent sections;

dividing, using at least one computer processor, the non-executable data item being backed up into segments using the one or more detected syntactic boundaries, wherein dividing the non-executable data item being backed up into segments comprises padding at least one of the segments to make the at least one of the segments syntactically correct by completing the at least one of the segments according to a type of file to be indexed, and wherein the at least one of the segments comprises at least one of;

an XML node, a sentence, a paragraph, and a page, wherein segmentation is performed for a plurality of different types of syntactical boundaries including paragraphs and at least one of;

an XML node, a sentence, and a page and wherein padding is based at least in part on a format, received from an index engine, for a type of file to be indexed;

generating a fingerprint for each segment; and

saving an entry for each segment in an index database, wherein each entry comprises a resource list and the fingerprint for the segment, the resource list comprising a resource name and a reference count, wherein the reference count is configured to allow counting of a plurality of references to the resource name.

2. The method of claim 1, wherein the fingerprint for a segment is an identifier in a backup catalog.

3. The method of claim 1, wherein the fingerprint is a unique identifier in the indexing database.

4. The method of claim 1, wherein the fingerprint is a content hash of the segment.

5. The method of claim 1, wherein saving an entry for each segment in the index database comprises:

determining the entry for the segment already exists;

determining the resource name already exists; and

increasing the value for the reference count by one.

6. The method of claim 1, wherein saving an entry for each segment in the index database comprises:

determining the entry for the segment does not exist;

inserting the entry for the segment in the index database; and

adding the resource name to the resource list.

7. The method of claim 6, further comprising setting the value for the reference count as one.

8. The method of claim 1, wherein saving an entry for each segment in the index database comprises:

determining the entry for the segment already exists;

determining the resource name does not exist;

adding the resource name to the resource list;

and setting the value for the reference count as one.

9. At least one non-transitory computer processor readable storage medium for storing a computer program of instructions configured to be readable by at least one processor for instructing the at least one processor to execute a computer process for performing the method as recited in claim 1.

10. The method of claim 1, wherein the resource list comprises a plurality of resource names, at least one resource name associated with a reference count greater than 1.

14. The system of claim 1, wherein padding comprises fixing tags of a syntactically incorrect XML structure.

11. A system for performing global single instance segment-based indexing for backup data comprising:

a boundary detector module for parsing a non-executable data item being backed up to detect one or more syntactic boundaries within the non-executable data item being backed up between adjacent sections;

the boundary director module further configured to divide the non-executable data item being backed up into segments using the one or more detected syntactic boundaries and to generate a fingerprint for each segment, wherein dividing the non-executable data item being backed up into segments comprises padding at least one of the segments to make the at least one of the segments syntactically correct by completing the at least one of the segments according to a type of file to be indexed, and wherein the at least one of the segments comprises at least one of;

an XML node, a sentence, a paragraph, and a page, wherein segmentation is performed for a plurality of different types of syntactical boundaries including paragraphs and at least one of;

an XML node, a sentence, and a page and wherein padding is based at least in part on a format, received from an index engine, for a type of file to be indexed; and

electronic storage for saving an entry for each segment in an index database, wherein each entry, comprises a resource list and the fingerprint for the segment, the resource list comprising a resource name and a reference count, wherein the reference count is configured to allow counting of a plurality of references to the resource name.

12. The system of claim 11, wherein the resource name comprises a file name and an offset.

13. The system of claim 11, wherein the syntactic boundaries comprise at least one of:

an XML node, a sentence, a paragraph, and a page.

15. A non-transitory article of manufacture for performing global single instance segment-based indexing for backup data, the article of manufacture comprising:

at least one non-transitory processor readable medium; and

instructions stored on the at least one medium;

wherein the instructions are configured to be readable from the at least one medium by at least one processor and thereby cause the at least one processor to operate so as to;

parse a non-executable data item being backed up to detect one or more syntactic boundaries within the non-executable data item being backed up between adjacent sections;

divide the non-executable data item being backed up into segments using the one or more detected syntactic boundaries, wherein dividing the non-executable data item being backed up into segments comprises padding at least one of the segments to make the at least one of the segments syntactically correct by completing the at least one of the segments according to a type of file to be indexed, and wherein the at least one of the segments comprises at least one of;

an XML node, a sentence, a paragraph, and a page, wherein segmentation is performed for a plurality of different types of syntactical boundaries including paragraphs and at least one of;

an XML node, a sentence, and a page and wherein padding is based at least in part on a format, received from an index engine, for a type of file to be indexed;

generate a fingerprint for each segment;

and save an entry for each segment in an index database, wherein each entry comprises a resource list and the fingerprint for the segment, the resource list comprising a resource name and a reference count, wherein the reference count is configured to allow counting of a plurality of references to the resource name.

16. The article of manufacture of claim 15, wherein the fingerprint for a segment is a unique identifier for the segment.

17. The article of manufacture of claim 15, wherein the fingerprint for a segment is content hash of the segment.