Method and apparatus for storing composite data streams

• US 7,574,418 B1
• Filed: 02/13/2004
• Issued: 08/11/2009
• Est. Priority Date: 02/13/2004
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Patterson, R. Hugo, Johnsson, Richard, Bricker, Allan
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): WILSON, KIMBERLY LOVEL
• Application Number:
  US10/779,355
• Time in Patent Office: 2,006 Days
• Field of Search: 707/1, 707/202, 707/204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

A method and apparatus for storing composite data streams. According to one embodiment of the invention, a composite data stream is stored so that it may be restored. The storing of the composite data stream includes decomposing the composite data stream into a plurality of constituent data streams, segmenting at least one of the plurality of constituent data streams, and discarding those of the segments resulting from the segmenting which are determined to have been stored previously.

Claims

1. A computer implemented method for storing data comprising:

receiving a composite data stream from a server;

storing the received composite data stream that is to be restored to the server subsequently, said storing including,

decomposing the composite data stream into a plurality of constituent data streams, the plurality of constituent data streams including at least a first constituent data stream of user data and a second constituent data stream of administrative data, wherein the composite data stream is further sectioned into one or more sections, each section including data from both the first and second constituent data streams, and wherein said decomposing includes,

storing a composite data stream map that indicates how to recompose the plurality of constituent data streams into the composite data stream,

wherein the composite data stream map includes a map header and one or more map blocks, each map block corresponding to a section, wherein the map header includes a composite data stream identifier identifying the associated composite data stream, a total number of constituent data streams associated with the composite data stream, and a constituent data stream identifier identifying each of the constituent data streams, and wherein each map block includes information identifying a location of each of the identified constituent data streams;

segmenting at least one of the plurality of constituent data streams decomposed from the composite data stream;

determining which segments resulting from the segmenting match segments already stored;

in lieu of storing those of the segments resulting from the segmenting which are determined to match already stored segments, storing pointers to those already stored segments; and

storing those of the segments resulting from the segmenting determined not to match already stored segments.

2. The computer implemented method of claim 1, wherein said storing the received composite data stream further comprises:

determining the second constituent data stream is administrative data that is to be restored by regeneration rather than being stored; and

discarding said second constituent data stream.

3. The computer implemented method of claim 2, wherein a map block of the composite data stream map further comprises a composite offset and a constituent data stream offset for each constituent data stream, wherein the composite offset specifies an offset in the composite data stream from which a starting data stream block of data to be recomposed from the constituent data streams identified by corresponding constituent data stream offsets, and wherein each constituent data stream offset indicates an offset in a corresponding constituent data stream from which the starting data stream block of data is to be recomposed.

4. The computer implemented method of claim 3, wherein the map block of the composite data stream map further comprises a list of one or more composite data stream descriptors, each corresponding to a data stream block to be recomposed for the composite data stream, wherein each composite data stream descriptor includes an identifier identifying a constituent data stream corresponding to a next data stream block and a length specifying a length of the next data stream block in an order, and wherein each composite data stream descriptor indicates, in order, how much of which constituent data stream to take next to recompose the composite data stream.

5. A computer implemented method for efficiently storing data comprising:

receiving over time, at a storage server having a composite data stream decomposer and recomposer and a segment reuse storage system, a plurality of composite data streams from a server, each of said plurality of composite data streams representing snapshots of data residing at a set of one or more sources taken over said time, wherein the server receives data streams from the client applications, wherein at least one of the server and the client applications insert into the data streams administrative data that is expected upon restore and that if kept in the data streams would result in a relatively low compression efficiency of the segment reuse storage system; and

storing each of said plurality of composite data streams that is to be restored to the server subsequently, said storing including,

decomposing the composite data stream into a plurality of constituent data streams, the plurality of constituent data streams including at least a first constituent data stream of user data and a second constituent data stream of administrative data, wherein the composite data stream is further sectioned into one or more sections, each section including data from both the first and second constituent data streams, and wherein said decomposing includes,

storing a composite data stream map that indicates how to recompose the plurality of constituent data streams into the composite data stream,

wherein the composite data stream map includes a map header and one or more map blocks, each map block corresponding to a section, wherein the map header includes a composite data stream identifier identifying the associated composite data stream, a total number of constituent data streams associated with the composite data stream, and a constituent data stream identifier identifying each of the constituent data streams, and wherein each map block includes information identifying a location of each of the identified constituent data streams; and

storing using segment reuse a set of one or more of said plurality of constituent data streams, said storing using segment reuse including performing the following for each of said set of constituent data streams,

segmenting the constituent data stream,

determining which segments resulting from the segmenting match segments already stored, and

storing only those segments of the constituent data stream that cannot be restored using segments already stored.

6. The computer implemented met hod of claim 5, wherein said storing each of said plurality of composite data streams further comprises:

determining the second constituent data stream is administrative data that is to be restored by regeneration rather than being stored; and

discarding said second constituent data stream.

7. The computer implemented method of claim 6, wherein a map block of the composite data stream map further comprises a composite offset and a constituent data stream offset for each constituent data stream, wherein the composite offset specifies an offset in the composite data stream from which a starting data stream block of data to be recomposed from the constituent data streams identified by corresponding constituent data stream offsets, and wherein each constituent data stream offset indicates an offset in a corresponding constituent data stream from which the starting data stream block of data is to be recomposed.

8. A computer implemented method for storing data comprising:

receiving, at a storage server having a composite data stream decomposer and recomposer and a segment reuse storage system, a composite data stream from a backup server, wherein the backup server is part of a backup system that includes a client application on a computer coupled to the backup server, said composite data stream representing at least a snapshot of data residing at the computer coupled to said backup server, wherein at least one of the client application and backup server insert into the composite data stream administrative data that is expected upon restore and that if kept in the composite data stream would result in a relatively low compression efficiency of the segment reuse storage system;

storing the received composite data stream that is to be restored to the backup server subsequently, said storing including,

decomposing the composite data stream into a plurality of constituent data streams, the plurality of constituent data streams including at least a first constituent data stream of user data and a second constituent data stream of administrative data, wherein the composite data stream is further sectioned into one or more sections, each section including data from both the first and second constituent data streams, and wherein said decomposing includes,

storing a composite data stream map that indicates how to recompose the plurality of constituent data streams into the composite data stream,

wherein the composite data stream map includes a map header and one or more map blocks, each map block corresponding to a section, wherein the map header includes a composite data stream identifier identifying the associated composite data stream, a total number of constituent data streams associated with the composite data stream, and a constituent data stream identifier identifying each of the constituent data streams, and wherein each map block includes information identifying a location of each of the identified constituent data streams; and

backing up each of said plurality of constituent data streams separately, said backing up including, applying segment reuse to back up a set of one or more of said plurality of constituent data streams including,

segmenting at least the first constituent data stream in to current segments;

determining which of the current segments match already stored segments; and

storing only those of the current segments that do not match already stored segments.

9. The computer implemented method of claim 8, wherein said backing up includes:

discarding the second constituent data stream because it is administrative data that is to be restored using regeneration as opposed to storage.

10. An apparatus to back up data comprising:

a storage server including,

an interface agent to receive over time composite data streams from a server representing snapshots of data residing at a set of one or more sources;

a composite data stream decomposer and recomposer, coupled to said interface agent, to decompose composite data streams into their constituent data streams and composite data stream maps, the composite data stream maps indicate how to recompose their corresponding composite data streams from their constituent data streams, the constituent data streams include at least a first constituent data stream of user data and a second constituent data stream of administrative data, and to recompose composite data streams from their constituent data streams and their composite data stream maps, wherein the composite data stream is further sectioned into one or more sections, each section including data from both the first and second constituent data streams, wherein a composite data stream map includes a map header and one or more map blocks, each map block corresponding to a section, wherein the map header includes a composite data stream identifier identifying the associated composite data stream, a total number of constituent data streams associated with the composite data stream, and a constituent data stream identifier identifying each of the constituent data streams, and wherein each map block includes information identifying a location of each of the identified constituent data streams;

a map file storage, coupled to said composite data stream decomposer and recomposer, to store the composite data stream maps; and

a segment reuse storage system, coupled to said composite data stream decomposer and recomposer, to perform segment reuse to store and restore constituent data streams.

11. The apparatus of claim 10 further comprising:

an administrative data regenerator, coupled to said composite data stream decomposer and recomposer, to regenerate data from constituent data streams that was not stored because that data is to be restored by regeneration.

12. The apparatus of claim 11 wherein the administrative data is regenerated in accordance with composite data stream attribute data retrieved from a configuration file.

13. The apparatus of claim 10 wherein the composite data stream decomposer and recomposer is stored in a machine-readable storage medium having stored thereon a set of instructions, which when executed by a set of one or more processors, cause the operations of the composite data stream decomposer and recomposer to be performed.

14. The apparatus of claim 10 wherein the composite data stream decomposer and recomposer is an application specific integrated circuit.