Efficient data storage system

• US 20060206669A1
• Filed: 04/11/2006
• Published: 09/14/2006
• Est. Priority Date: 12/20/2002
• Status: Active Grant

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Li, Kai, Patterson, R. Hugo, Zhu, Ming Benjamin
• Granted Patent: US 7,305,532 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• 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; and

determining whether one of the plurality of data segments has been stored previously using a summary in a low latency memory, wherein the low latency memory is random access memory (RAM), dynamic random access memory (DRAM), synchronous dynamic random access memory (SDRAM), or integrated circuit non-volatile memory;

in the event that the data segment is determined not to have been stored previously, assigning an identifier to the data segment.

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

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

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 data segment.

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

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

confirming whether the data segment 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 data segment 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 data segment 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 data segment 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 data segment has been stored previously in the event the data segment is determined to have been stored;

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 data segment 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 data segments.

12. A method for storing data as recited in claim 1 further comprising generating segment information for each of the 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 data segments;

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

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

wherein the summary is a summary; and

wherein the summary is a space efficient, probabilistic summary of segment information.

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

16. 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 determine whether one of the plurality of data segments has been stored previously using a summary in a low latency memory, wherein the low latency memory is random access memory (RAM), dynamic random access memory (DRAM), synchronous dynamic random access memory (SDRAM), or integrated circuit non-volatile memory; and

in the event that the data segment is determined not to have been stored previously, to assign an identifier to the data segment. 17. A computer program product for storing data, the computer program product being embodied in a computer readable medium and comprising computer instructions for;

receiving a data stream comprising a plurality of data segments; and

determining whether one of the plurality of data segments has been stored previously using a summary in a low latency memory, wherein the low latency memory is random access memory (RAM), dynamic random access memory (DRAM), synchronous dynamic random access memory (SDRAM), or integrated circuit non-volatile memory;

in the event that the data segment is determined not to have been stored previously, assigning an identifier to the data segment.