Boundaries

• US 7,478,113 B1
• Filed: 04/13/2006
• Issued: 01/13/2009
• Est. Priority Date: 04/13/2006
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: D'hondt, Koen, De Spiegeleer, Kristof
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Merilyn P
• Application Number:
  US11/403,561
• Time in Patent Office: 1,006 Days
• Field of Search: 707/5, 707/6, 707/102, 707/204, 707/205, 707/200, 235/435, 709/238
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data

Abstract

A data backup system can be operable to determine whether to send a data file segment to backup storage. The data backup system can comprise a comparator operable to compare a boundary parameter of a candidate segment proposed for sending to backup storage to a boundary parameter of a previously stored segment to determine whether the candidate segment potentially corresponds to the previously stored segment. The data backup system can also comprise a comparator operable, if it is determined that the candidate segment potentially corresponds to the previously stored segment, to compare a checksum value for the candidate segment to a checksum value for the previously stored segment to determine whether the candidate segment has previously been stored to the second location. A storage engine can be provided to send to backup storage a segment determined not to have previously been stored. Thereby a single instance store can be implemented whereby a modified segment can be identified and a segment boundary adjusted to avoid re-storage of previously stored data.

Claims

1. A method, comprising:

generating a plurality of candidate segments from a selected trial segment of a selected data file, each candidate segment corresponding to a start position offset from the start of the trial segment and having data appended thereto from a next segment of the selected data file as necessary to maintain a constant candidate segment size;

comparing a boundary parameter of each candidate segment to a boundary parameter of a previously stored segment to determine a comparison result;

if the comparison result indicates that a candidate segment potentially corresponds to the previously stored segment, comparing a segment identifier value for the candidate segment to a segment identifier value for the previously stored segment to determine whether the candidate segment is the same as the previously stored segment; and

sending to a backup storage a trial segment if none of the candidate segments generated therefrom are determined to have previously been stored.

2. The method of claim 1, wherein the previously stored segment is a segment of a previously stored version of the selected data file.

3. The method of claim 1, wherein the segment identifier value is at least one of a cyclic redundancy check value and a hash function value.

4. The method of claim 1, wherein the boundary parameter of each candidate segment is calculated by performing a semantic analysis of the candidate segment.

5. The method of claim 4, further comprising performing the semantic analysis.

6. The method of claim 5, wherein the semantic analysis is performed such that a boundary parameter for a given segment of a data file is different from a boundary parameter for all other segments of that data file.

7. The method of claim 4, further comprising excluding at least one predetermined byte pattern in a segment when determining the boundary parameter therefore.

8. The method of claim 7, wherein the at least one predetermined byte pattern includes a repetitive byte sequence.

9. The method of claim 7, wherein a record of ignored bytes is included in the boundary parameter or in an object representation associated with the selected data file.

10. The method of claim 1, wherein the boundary parameter and segment identifier value for the previously stored segment are stored in a data object representation for a previously stored data object to which the previously stored segment belongs.

11. The method of claim 1, further comprising, in the event of determining that the candidate segment corresponds to the previously stored segment, outputting an indication of the start position offset at which the match was determined.

12. The method of claim 11, further comprising creating a new segment containing contiguous data from the start of the trial segment having a size equal to the start position offset;

and sending the new segment to the backup storage.

13. The method of claim 12, further comprising consolidating the new segment with one of a previous segment and a next segment;

and sending the consolidated segment to the backup storage.

14. The method of claim 13, wherein the consolidating is performed if the consolidated segment would have a size less than or equal to a predetermined maximum segment size.

15. The method of claim 1, wherein an offset value used to generate a candidate segment falls into a range of zero to the size of the candidate segment.

16. A method for identifying data object segments for inclusion in single instance storage, the method comprising:

generating a plurality of candidate segments from a selected trial segment of a selected data object, each candidate segment corresponding to a start position offset from the start of the trial segment and having data appended thereto from a next segment of the selected data object as necessary to maintain a constant candidate segment size;

comparing a boundary parameter of each candidate segment to a boundary parameter of a previously stored segment to determine whether the candidate segment potentially corresponds to the previously stored segment;

if it is determined that a candidate segment potentially corresponds to the previously stored segment, comparing a segment identifier value for the candidate segment to a segment identifier value for the previously stored segment to determine whether the candidate segment is the same as the previously stored segment.

17. The method of claim 16, further comprising creating a new segment containing contiguous data from the start of the candidate segment having a size equal to the offset value.

18. The method of claim 17, further comprising consolidating the new segment with one of a previous segment and a next segment.

19. A system, comprising:

a processor;

a memory storing program instructions executable by the processor to;

generate a plurality of candidate segments from a selected trial segment of a selected data file, each candidate segment corresponding to a start position offset from the start of the trial segment and having data appended thereto from a next segment of the selected data file as necessary to maintain a constant candidate segment size;

compare a boundary parameter of each candidate segment to a boundary parameter of a previously stored segment to determine a comparison result;

if the comparison result indicates that a candidate segment potentially corresponds to the previously stored segment, compare a segment identifier value for the candidate segment to a segment identifier value for the previously stored segment to determine whether the candidate segment is the same as the previously stored segment; and

send to backup storage a trial segment if none of the candidate segments generated therefrom are determined to have previously been stored.