Efficient data storage system

• US 7,434,015 B2
• Filed: 10/16/2007
• Issued: 10/07/2008
• Est. Priority Date: 12/20/2002
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Li, Kai, Patterson, R. Hugo, Zhu, Ming Benjamin
• Primary Examiner(s): Peugh; Brian R
• Application Number:
  US11/974,961
• Publication Number:
  US 20080133835A1
• Time in Patent Office: 357 Days
• Field of Search: 711/162, 711/118
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A system and method are disclosed for providing efficient data storage. A data stream comprising a plurality of data segments is received. The system determines whether one of the plurality of data segments has been stored previously using a summary in a low latency memory; in the event that the data segment is determined not to have been stored previously, assigning an identifier to the data segment.

Claims

1. A method for storing data comprising:

receiving a data stream comprising a plurality of data segments;

assigning an identifier to one of the plurality of data segments; and

determining whether one of the plurality of data segments has been stored previously using a summary, wherein the summary is a space efficient, probabilistic summary of segment information.

2. A method for storing data as recited in claim 1 wherein the identifier is derived from the content of the one of the plurality of data segments.

3. A method for storing data as recited in claim 1 wherein the identifier is not derived from the content of the one of the plurality of data segments.

4. A method for storing data as recited in claim 1 wherein the identifier is a digital signature.

5. A method for storing data as recited in claim 1 further comprising storing the one of the plurality of data segments.

6. A method for storing data as recited in claim 1 wherein the determination can positively determine that the one of the plurality of data segments has not been stored previously, but cannot positively determine that the one of the plurality of data segments has been stored previously.

7. A method for storing data as recited in claim 1 further comprising:

confirming whether the one of the plurality of data segments has been stored previously using a relatively high latency memory.

8. A method for storing data as recited in claim 1 further comprising:

confirming whether the one of the plurality of data segments has been stored previously by checking in a cache.

9. A method for storing data as recited in claim 1 further comprising

confirming whether the one of the plurality of data segments has been stored previously, wherein confirming whether the data segment has been stored previously includes checking a cache;

and

in the event that checking a cache results in a cache miss, confirming whether the one of the plurality of data segments has been stored previously further includes checking in a segment database.

10. A method for storing data as recited in claim 1 further comprising:

confirming whether the one of the plurality of data segments has been stored previously, wherein confirming whether the one of the plurality of data segments has been stored previously includes checking a cache; and

in the event that checking a cache results in a cache miss, confirming whether the one of the plurality of data segments has been stored previously further includes checking in a segment database, wherein the segment database is stored in relatively high latency memory.

11. A method for storing data as recited in claim 1 further comprising generating segment information for each of the one of the plurality of data segments.

12. A method for storing data as recited in claim 1 further comprising generating segment information for each of the plurality of data segments, wherein the segment information includes a digital signature.

13. A method for storing data as recited in claim 1 further comprising generating segment information for each of the plurality of data segments;

wherein the segment information includes a short identifier that is not likely to be unique.

14. A method for storing data as recited in claim 1 wherein the summary is a Bloom filter.

15. A data storage device comprising:

an input interface adapted to receive a data stream comprising a plurality of data segments; and

a segment redundancy check engine configured to receive a data stream comprising a plurality of data segments, assign an identifier to one of the plurality of data segments, and determine whether one of the plurality of data segments has been stored previously using a summary, wherein the summary is a space efficient, probabilistic summary of segment information.

16. A computer program product for storing data, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

receiving a data stream comprising a plurality of data segments;

assigning an identifier to one of the plurality of data segments; and

determining whether one of the plurality of data segments has been stored previously using a summary, wherein the summary is a space efficient, probabilistic summary of segment information.