Data storage using identifiers

• US 20070101074A1
• Filed: 10/20/2006
• Published: 05/03/2007
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Patterson, R.
• Granted Patent: US 7,599,932 B2
• Time in Patent Office: Days
• US Class Current: 711/156
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method are disclosed for processing a data stream. A data segment is received. It is determined whether the data segment has been previously stored. In the event that the data segment is determined not to have been previously stored, a unique identifier for specifying the data segment in a representation of the data stream is generated.

Claims

1. A method for processing a data stream comprising:

receiving a data segment;

determining whether the data segment has been previously stored; and

in the event that the data segment is determined not to have been previously stored, generating a unique identifier for specifying the data segment in a representation of the data stream.

2. A method as recited in claim 1, wherein no unique identifier for specifying the data segment in a representation of the data stream is generated in the event that the data segment is determined to have been previously stored.

3. A method as recited in claim 1, wherein determining whether the data segment has been previously stored does not require using the unique identifier.

4. A method as recited in claim 1, wherein determining whether the data segment has been previously stored includes generating a content derived summary.

5. A method as recited in claim 1, wherein determining whether the data segment has been previously stored includes generating a content derived summary, and wherein the unique identifier is not necessarily the same as the content derived summary.

6. A method as recited in claim 1, further comprising, in the event that the data segment is determined to have been previously stored, reusing a previously generated unique identifier associated with the data segment.

7. A method as recited in claim 1, further comprising, in the event that the data segment is determined to have been previously stored, looking up a previously generated unique identifier associated with the data segment.

8. A method as recited in claim 1, further comprising, in the event that the data segment is determined not to have been previously stored:

storing the data segment in a data segment storage location; and

recording the data segment storage location.

9. A method as recited in claim 8, wherein the data segment storage location includes a memory address.

10. A method as recited in claim 1, in the event that the data segment is determined not to have been previously stored, further including:

storing the data segment in a data segment storage location; and

updating a data structure for storing the content derived summary, the unique identifier, and the data segment storage location.

11. A method as recited in claim 1, wherein determining whether the data segment has been previously stored includes generating a content derived summary for the data segment;

and

in the event that the data segment is determined not to have been previously stored, further including;

storing the data segment in a data segment storage location; and

updating a data structure for storing the content derived summary, the unique identifier, and the data segment storage location;

wherein

the data segment storage location is accessed given the unique identifier or given the content derived summary in the data structure.

12. A method as recited in claim 1, wherein:

determining whether the data segment has been previously stored includes generating a content derived summary for the data segment;

in the event that the data segment is determined not to have been previously stored, further including;

storing the data segment in a data segment storage location; and

updating a data structure for storing the content derived summary, the unique identifier, and the data segment storage location;

wherein

the data segment storage location is accessed given the unique identifier or given the content derived summary, using a single access of a storage device.

13. A method for processing a data stream as recited in claim 1 wherein:

determining whether the data segment has been previously stored includes generating a content derived summary for the data segment;

in the event that the data segment is determined not to have been previously stored, further including;

storing the data segment in a data segment storage location; and

updating a data structure for storing the content derived summary, the unique identifier, and the data segment storage location;

wherein

a region of the data structure that includes the data segment storage location is accessed given the unique identifier or given the content derived summary, using a single access of a storage device.

14. A method for processing a data stream as recited in claim 1, wherein determining whether the data segment has been previously stored includes generating a content derived summary for the data segment;

and the unique identifier is derived from the content derived summary.

15. A system for processing data stream comprising:

an interface configured to receive a data segment;

a processor coupled to the interface, configured to;

determine whether the data segment has been previously stored; and

in the event that the data segment is determined not to have been previously stored, generate a unique identifier for specifying the data segment in a representation of the data stream.

16. A system as recited in claim 15, wherein no unique identifier for specifying the data segment in a representation of the data stream is generated in the event that the data segment is determined to have been previously stored.

17. A system as recited in claim 15, wherein determining whether the data segment has been previously stored does not require using the unique identifier.

18. A computer program product for processing a data stream, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

receiving a data segment;

determining whether the data segment has been previously stored; and

in the event that the data segment is determined not to have been previously stored, generating a unique identifier for specifying the data segment in a representation of the data stream.

19. A computer program product as recited in claim 18, wherein no unique identifier for specifying the data segment in a representation of the data stream is generated in the event that the data segment is determined to have been previously stored.

20. A computer program product as recited in claim 18, wherein determining whether the data segment has been previously stored does not require using the unique identifier.