Data storage using identifiers

• US 7,143,251 B1
• Filed: 06/30/2003
• Issued: 11/28/2006
• Est. Priority Date: 06/30/2003
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Patterson, R. Hugo
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US10/611,309
• Time in Patent Office: 1,247 Days
• Field of Search: None
• US Class Current: 711/162
• 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;

wherein determining whether the data segment has been previously stored includes generating a candidate identifier; and

determining whether the candidate identifier has been stored previously.

2. 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.

3. 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 content derived summary is a fingerprint.

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

and the content derived summary is the data segment.

5. 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 locating the content derived summary in a content derived summary storage.

6. A method for processing a data stream as recited in claim 1 wherein determining whether the data segment has been previously stored includes locating the data segment in a data segment storage.

7. A method for processing a data stream as recited in claim 1 wherein 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.

8. 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.

9. 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

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

10. 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

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.

11. 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.

12. A method for processing a data stream as recited in claim 1, wherein the unique identifier does not depend on probability for its uniqueness, and is shorter than a signature of the data segment.

13. A method for processing a data stream as recited in claim 1, wherein the unique identifier is a serial number.

14. A method for processing a data stream as recited in claim 1, wherein the unique identifier is derived from a hash value.

15. A method for processing a data stream as recited in claim 1, wherein the unique identifier is an address of the data segment.

16. A method for processing a data stream as recited in claim 1, wherein the unique identifier is a shortest identifier for uniquely identifying the data segment.

17. 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.

18. 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 includes a value derived from the content derived summary and a serial number.

19. A method for processing a data stream as recited in claim 1, wherein the representation of the data stream is a compressed representation.

20. A method for processing a data stream as recited in claim 1, wherein the representation of the data stream is used for reconstructing the data stream.

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

generating a unique identifier for specifying the data segment includes modifying the candidate identifier.

22. A method for processing a data stream as recited in claim 21, wherein modifying the candidate identifier includes adding a value to the candidate identifier.

23. A method for processing a data stream as recited in claim 21, wherein modifying the candidate identifier includes combining an additional bit with the candidate identifier.

24. A method for processing a data stream as recited in claim 21, wherein modifying the candidate identifier includes combining a plurality of bits with the candidate identifier.

25. A method for processing a data stream as recited in claim 1, wherein the unique identifier is stored in a reconstruction list.

26. A method for processing a data stream as recited in claim 1, in the event that the data segment is determined to have been previously stored, further including locating a unique identifier previously assigned to the data segment.

27. A method for processing a data stream as recited in claim 1, in the event that the data segment is determined to have been previously stored, further including locating a unique identifier previously assigned to the data segment;

and the unique identifier is stored in a reconstruction list.

28. A method for processing a data stream 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.

29. A system for processing a 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;

wherein to determine whether the data segment has been previously stored includes to generate a candidate identifier; and

to determine whether the candidate identifier has been stored previously.

31. A system as recited in claim 29, wherein to determine whether the data segment has been previously stored includes to generate a content derived summary.

32. A system as recited in claim 29, wherein to determine whether the data segment has been previously stored includes to locate the data segment in a data segment storage.

33. A system as recited in claim 29, wherein in the event that the data segment is determined not to have been previously stored, the processor is further configured to store the data segment in a data segment storage location.

34. A system as recited in claim 29, wherein the unique identifier does not depend on probability for its uniqueness, and is shorter than a signature of the data segment.

35. A system as recited in claim 29, wherein to determine whether the data segment has been previously stored includes to generate a content derived summary for the data segment;

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

36. A system as recited in claim 29, wherein to determine whether the data segment has been previously stored includes to generate a content derived summary for the data segment;

and the unique identifier includes a value derived from the content derived summary and a serial number.

37. A system as recited in claim 29, wherein the representation of the data stream is a compressed representation.

38. A system as recited in claim 29, wherein the representation of the data stream is used for reconstructing the data stream.

39. A system as recited in claim 29, wherein the unique identifier is stored in a reconstruction list.

40. A system as recited in claim 29, in the event that the data segment is determined to have been previously stored, the processor is further configured to locate a unique identifier previously assigned to the data segment.

30. A computer program product for processing a data stream, the computer program product being embodied in a computer readable storage 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;

wherein determining whether the data segment has been previously stored includes generating a candidate identifier; and

determining whether the candidate identifier has been stored previously.

41. A computer program product as recited in claim 30, wherein determining whether the data segment has been previously stored includes generating a content derived summary.

42. A computer program product as recited in claim 30, wherein determining whether the data segment has been previously stored includes locating the data segment in a data segment storage.

43. A computer program product as recited in claim 30, wherein in the event that the data segment is determined not to have been previously stored, the computer program product further comprising computer instructions for storing the data segment in a data segment storage location.

44. A computer program product as recited in claim 30, wherein the unique identifier does not depend on probability for its uniqueness, and is shorter than a signature of the data segment.

45. A computer program product as recited in claim 30, 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.

46. A computer program product as recited in claim 30, wherein determining whether the data segment has been previously stored includes generating a content derived summary for the data segment;

and the unique identifier includes a value derived from the content derived summary and a serial number.

47. A computer program product as recited in claim 30, wherein the representation of the data stream is a compressed representation.

48. A computer program product as recited in claim 30, wherein the representation of the data stream is used for reconstructing the data stream.

49. A computer program product as recited in claim 30, wherein the unique identifier is stored in a reconstruction list.

50. A computer program product as recited in claim 30, in the event that the data segment is determined to have been previously stored, the computer program product further comprising computer instructions for locating a unique identifier previously assigned to the data segment.