Efficient data storage system

• US 7,065,619 B1
• Filed: 12/20/2002
• Issued: 06/20/2006
• 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:
  US10/325,479
• Time in Patent Office: 1,278 Days
• Field of Search: 711/118, 711/161, 711/162, 711/165, 707/201, 707/204, 709/231
• 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; and

determining 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; and

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.

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

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

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.

3. 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;

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

generate segment information for each of the plurality of data segments;

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

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

4. 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;

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

generate segment information for each of the plurality of data segments;

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

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