Method and apparatus to recover from interrupted data streams in a deduplication system

• US 8,074,043 B1
• Filed: 01/30/2009
• Issued: 12/06/2011
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Zeis, Michael John
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US12/363,207
• Time in Patent Office: 1,040 Days
• Field of Search: None
• US Class Current: 711/171
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641

Abstract

Detection and proper deduplication of a re-started data stream in a segmentation analysis-based deduplication system are provided by retaining information about a previous data stream and using that information when performing segmentation of the re-started data stream. Information such as a segment size associated with a last data object received in the previous data stream and a record of how much data was present in the last segment associated with the previous data stream is retained. The retained segment size information is used to set a first data object segment size of the re-started data stream, and the size of last segment information is used to determine how much information should be put in the first segment associated with the re-started data stream in order to maintain proper alignment of the remainder of the segments for the first data object in the re-started data stream for deduplication.

Claims

1. A method comprising:

receiving a current data stream having an associated unique identifier;

determining whether the current data stream is a first data stream associated with the unique identifier; and

allocating a segment of memory to contain a first amount of data from the current data stream, wherein

a size of the segment is determined using an identification of a type of first data object received in the current data stream, and

the size of the segment is further determined using a size of a last segment of a previous data stream associated with the unique identifier, if the current data stream is not the first data stream associated with the unique identifier.

2. The method of claim 1 wherein said determining whether the current data stream is the first data stream associated with the unique identifier comprises:

receiving a sequence number associated with the current data stream and the unique identifier; and

comparing the unique identifier and sequence number pair associated with the current data stream against unique identifier and sequence number pairs associated with previously received data streams.

3. The method of claim 2 further comprising:

storing the unique identifier and sequence number pair associated with the current data stream for use in a comparing against a unique identifier and sequence number pair associated with a subsequent data stream.

4. The method of claim 3 further comprising:

storing the size of the segment in association with the unique identifier and sequence number pair.

5. The method of claim 1 wherein said determining the size of the segment using an identification of a type of first data object comprises:

if the current data stream is the first data stream associated with the unique identifier, then

reading the first data object type from the current data stream, and

selecting a segment size corresponding to the first data object type; and

if the current data stream is not the first data stream associated with the unique identifier, then

determining the segment size of a last data object of the previous data stream associated with the unique identifier.

6. The method of claim 5 wherein said determining the size of the segment using a size of the last segment of the previous data stream associated with the unique identifier comprises:

subtracting the size of the last segment of the previous data stream associated with the unique identifier from the segment size of the last data object of the previous data stream associated with the unique identifier.

7. The method of claim 1 further comprising:

allocating a second segment of memory to contain a second amount of data from the current data stream, wherein

the size of the second segment is determined using the identification of the type of first data object received in the current data stream; and

storing the size of the second segment as a last data object segment size in association with the unique identifier.

8. The method of claim 7 further comprising:

allocating a third segment of memory to contain a third amount of data from the current data stream, wherein

the size of the third segment is determined using an identification of the type of second data object received in the current data stream; and

storing the size of the third segment as the last data object segment size in association with the unique identifier.

9. The method of claim 8 further comprising:

if said receiving the current data stream terminates, then

closing a current segment containing data received in the current data stream,

determining an amount of data contained in the current segment, and

storing the amount of data contained in the current segment as a last segment size in association with the unique identifier.

10. A computer-readable storage medium storing instructions executable by a processor, said instructions comprising:

a first set of instructions configured to determine whether a current data stream is a first data stream associated with a unique identifier associated with the current data stream, wherein

the current data stream is received by a network interface coupled to the processor; and

a second set of instructions configured to allocate a segment of memory to contain a first amount of data from the current data stream, wherein the second set of instructions comprises instructions further configured to

determine a size of the segment using an identification of a type of first data object received in the current data stream, and

if the current data stream is not the first data stream associated with the unique identifier, further determine the size of the segment using a size of a last segment of a previous data stream associated with the unique identifier.

11. The computer-readable storage medium of claim 10 wherein said first set of instructions further comprises instructions executable by the processor, said instructions comprising:

a third set of instructions configured to receive a sequence number associated with the current data stream and the unique identifier; and

a fourth set of instructions configured to compare the unique identifier and sequence number pair associated with the current data stream against unique identifier and sequence number pairs associated with previously received data streams.

12. The computer-readable storage medium of claim 11 further comprising:

a fifth set of instructions configured to store the unique identifier and sequence number pair associated with the current data stream for use in a comparing against a unique identifier and sequence number pair associated with a subsequent data stream; and

a sixth set of instructions configured to store the size of the segment in association with the unique identifier and sequence number pair.

13. The computer readable storage medium of claim 10 wherein said instructions configured to determine the size of the segment using an identification of a type of first data object comprise:

a third set of instructions, executable if the current data stream is the first data stream associated with the unique identifier, configured to

read the first data object type from the current data stream, and

select a segment size corresponding to the first data object type; and

a fourth set of instructions, executable if the current data stream is not the first data stream associated with the unique identifier, configured to

subtract the size of the last segment of the previous data stream associated with the unique identifier from the segment size of the last data object of the previous data stream associated with the unique identifier.

14. The computer-readable medium of claim 10, said instructions further comprising:

a third set of instructions configured to allocate a second segment of memory to contain a second amount of data from the current data stream, wherein

the size of the second segment is determined using the identification of the type of first data object received in the current data stream; and

a fourth set of instructions configured to store the size of the second segment as a last data object segment size in association with the unique identifier.

15. The computer-readable medium of claim 14, said instructions further comprising:

a fifth set of instructions configured to allocate a third segment of memory to contain a third amount of data from the current data stream, wherein

the size of the third segment is determined using an identification of the type of second data object received in the current data stream; and

a sixth set of instructions configured to store the size of the third segment as the last data object segment size in association with the unique identifier.

16. The computer-readable medium of claim 15, said instructions further comprising:

a seventh set of instructions, executable when said receiving the current data stream terminates, and configured to

close a current segment containing data received in the current data stream,

determine an amount of data contained in the current segment, and

store the amount of data contained in the current segment as a last segment size in association with the unique identifier.

17. An apparatus comprising:

a network interface configured to receive from a remote node a current data stream having an associated unique identifier;

a segment buffer memory, coupled to the network interface, and comprising memory allocatable to form one or more buffers of corresponding selected sizes; and

a processor, coupled to the network interface and the segment buffer memory, and configured to

determine whether the current data stream is a first data stream associated with the unique identifier, and

allocate a segment of the segment buffer memory to contain a first amount of data from the current data stream, wherein

a size of the segment is determined using an identification of a type of first data object received in the current data stream, and

the size of the segment is further determined using a size of a last segment of a previous data stream associated with the unique identifier, if the current data stream is not the first data stream associated with the unique identifier.

18. The apparatus of claim 17 further comprising:

a stream identifier memory coupled to the processor wherein,

the memory is configured to store one or more unique identifier and sequence number pairs associated with corresponding one or more previously received data streams,

the network interface is further configured to receive a sequence number associated with the current data stream and the unique identifier, and

the processor is further configured to determine whether the current data stream is the first data stream associated with the unique identifier by comparing the unique identifier and sequence number pair associated with the current data stream against the unique identifier and sequence number pairs associated with previously received data streams.

19. The apparatus of claim 18 wherein

the processor is further configured to store the unique identifier and sequence number pair associated with the current data stream in the stream identifier memory for use in a comparing against a unique identifier and sequence number pair associated with a subsequent data stream,

the stream identifier memory is further configured to store a segment size in association with each unique identifier and sequence number pair, and

the processor is further configured to store the size of the segment in association with the unique identifier and sequence number pair in the stream identifier memory.

20. The apparatus of claim 17 wherein

the processor is further configured to determine the size of the segment using the identification of the type of the first data object by being further configured to

in response to the current data stream being the first data stream associated with the unique identifier,

read the first data object type from the current data stream, and

select a segment size corresponding to the first data object type;

and

in response to the current data stream not being the first data stream associated with the unique identifier,

determine the segment size of a last data object of the previous data stream associated with the unique identifier, and

subtract the size of the last segment of the previous data stream associated with the unique identifier from the segment size of the last data object of the previous data stream associated with the unique identifier.