Efficient data storage system

• US 20050216669A1
• Filed: 05/24/2005
• Published: 09/29/2005
• 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,373,464 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• 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 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method for storing data comprising is disclosed. The method comprises receiving a data stream comprising a plurality of data segments wherein each data segment is associated with an identifier. The method further determining using a subset of identifiers that are stored in a low latency memory whether a data segments has been previously stored and returning the identifier for the data segment in the event the data segment is determined to have been stored previously.

Claims

1. A method for storing data comprising:

receiving a data stream comprising a plurality of data segments wherein each data segment is associated with an identifier;

determining using a subset of identifiers that are stored in a low latency memory whether a data segments has been previously stored; and

returning the identifier for the data segment in the event the data segment is determined to have been stored previously.

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

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

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

5. A method for storing data as recited in claim 1 wherein the identifier is not found in the low latency memory.

6. A method for storing data as recited in claim 1 wherein the identifier is used to reconstruct the data stream.

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

in the event that the data segment is not determined to have been stored, confirming whether the data segment has been stored; and

in the event that the data segment is confirmed to have been stored, storing the data segment.

8. A method for storing data as recited in claim 1 further comprising discarding the data segment.

9. A method for storing data as recited in claim 1 wherein the determination does not require accessing high latency memory.

10. A method for storing data as recited in claim 1 wherein the determination does not require accessing disk.

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

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

wherein the segment information includes a short identifier.

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

wherein the segment information includes a digital signature;

wherein the digital signature is a result of a hash function.

15. A method for storing data as recited in claim 1 further comprising generating segment information for the data segment;

wherein the segment information includes a digital signature;

wherein the digital signature is a Rabin fingerprint.

16. A method for storing data as recited in claim 1 further including:

looking up data segment metadata in a metadata cache to positively determine if the data has been stored previously; and

using a summary to positively determine if the data has not been stored previously.

17. A method for storing data as recited in claim 1 further including:

looking up data segment metadata in a metadata cache; and

using a summary to positively determine if the data has not been stored previously;

wherein the summary is a summary vector.

18. A method for storing data as recited in claim 1 further including:

looking up data segment metadata in a metadata cache; and

using a summary to positively determine if the data has not been stored previously;

wherein the summary is a Bloom filter.

19. A data storage device comprising:

an interface adapted to receive an input data stream comprising a plurality of data segments wherein each data segment is associated with an identifier;

a segment redundancy check engine adapted to determine using a subset of identifiers that are stored in a low latency memory whether a data segments has been previously stored and to return the identifier for the data segment in the event the data segment is determined to have been stored previously.

20. A data storage device as recited in claim 19 wherein the determination can positively confirm that the data segment has been previously stored, but cannot positively confirm that the data segment has not been previously stored.

21. A data storage device as recited in claim 19 wherein the identifier is derived from the content of the data segment.

22. A data storage device as recited in claim 19 wherein the identifier is used to reconstruct the data stream.

23. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to, in the event that the data segment is not determined to have been stored, confirm whether the data segment has been stored;

and in the event that the data segment is confirmed to have been stored, store the data segment.

24. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to generate segment information for the data segments.

25. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to generate segment information for the data segments;

wherein the segment information includes a digital signature.

26. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to generate segment information for the data segments;

wherein the segment information includes a short identifier.

27. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to generate segment information for the data segments;

wherein the segment information includes a digital signature;

wherein the digital signature is a result of a hash function.

28. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to generate segment information for the data segment;

wherein the segment information includes a digital signature;

wherein the digital signature is a Rabin fingerprint.

29. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to look up data segment metadata in a metadata cache to positively determine if the data has been stored previously;

and use a summary to positively determine if the data has not been stored previously.

30. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to look up data segment metadata in a metadata cache;

and use a summary to positively determine if the data has not been stored previously;

wherein the summary is a summary vector.

31. A data storage device as recited in claim 19 wherein the segment redundancy check engine is further adapted to look up data segment metadata in a metadata cache;

and use a summary to positively determine if the data has not been stored previously;

wherein the summary is a Bloom filter.

32. 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 wherein each data segment is associated with an identifier;

determining using a subset of identifiers that are stored in a low latency memory whether a data segments has been previously stored; and

returning the identifier for the data segment in the event the data segment is determined to have been stored previously.