Method and an apparatus to store data patterns

• US 7,853,750 B2
• Filed: 01/30/2007
• Issued: 12/14/2010
• Est. Priority Date: 01/30/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Stager, Roger
• Primary Examiner(s): Bragdon; Reginald G
• Assistant Examiner(s): Faal; Baboucarr
• Application Number:
  US11/700,701
• Publication Number:
  US 20080184001A1
• Time in Patent Office: 1,414 Days
• Field of Search: None
• US Class Current: 711/112
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0686 Libraries, e.g. tape libraries, jukebox

Abstract

A method and an apparatus to store data patterns are presented. In one embodiment, the method includes searching a pattern repository to find prior copies of a pattern and to reference one of the prior copies, or insert a new copy, based on the access time of the prior copy and the effect on the sequential stream performance.

Claims

1. A method, comprising:

receiving a first data stream from one or more clients, wherein the first data stream comprises one or more data patterns referenced by one or more pointers stored in one or more storage devices;

receiving a second data stream from the one or more clients;

checking if a copy of a particular data pattern of the second data stream is already stored in a pattern repository;

in response to the copy of the particular data pattern already stored in the pattern repository, storing a new pointer in the one or more storage devices to reference the copy of the particular data pattern already stored in the pattern repository based on an access time of the copy of the particular data pattern in the pattern repository being less than a predetermined access time;

in response to the copy of the particular data pattern already stored in the pattern repository, storing a new copy of the particular data pattern in the pattern repository and storing the new pointer in the one or more storage devices to reference the new copy of the particular data pattern based on the access time of the copy of the particular data pattern in the pattern repository being greater than the predetermined access time; and

in response to the copy of the particular data pattern not already stored in the pattern repository, storing the new copy of the particular data pattern in the pattern repository and storing the new pointer in the one or more storage devices to reference the new copy of the particular data pattern.

2. The method of claim 1, wherein the access time is evaluated in terms of a locality of the particular data pattern.

3. The method of claim 1, wherein the pattern repository is a single instance store.

4. The method of claim 1, wherein the access time is based on weighing a storage efficiency benefit of accessing the particular data pattern against a compression ratio.

5. The method of claim 1, further comprising:

dividing the pattern repository into multiple segments;

reading one or more of the multiple segments into a cache buffer; and

accessing one or more of the multiple segments from the cache buffer.

6. The method of claim 4, wherein the compression ratio is a compression efficiency.

7. The method of claim 1, further comprising:

designating a number of segments of the pattern repository as redundant segments; and

replacing a failed media segment with a redundant segment.

8. The method of claim 1, further comprising:

resetting one or more pointers stored in the storage device to reference a different data pattern copy stored in the pattern repository.

9. A system, comprising:

one or more storage devices;

a pattern repository;

a processing logic configured to receive a first data stream from one or more clients, wherein the first data stream comprises one or more data patterns referenced by one or more pointers stored in one or more storage devices;

the processing logic further configured to receive a second data stream from one or more clients;

the processing logic further configured to check if a copy of the particular data pattern of the second data stream is already stored in a pattern repository;

the processing logic further configured to store, in response to the copy of the particular data pattern already stored in the pattern repository, a new pointer in the one or more storage devices to reference the copy of the particular data pattern already stored in the pattern repository based on an access time of the copy of the particular data pattern in the pattern repository being less than a predetermined access time;

the processing logic further configured to store, in response to the copy of the particular data pattern already stored in the pattern repository, a new copy of the particular data pattern in the pattern repository and store the new pointer in the one or more storage devices to reference the new copy of the particular data pattern based on the access time of the copy of the particular data pattern in the pattern repository being greater than the predetermined access time; and

the processing logic further configured to store, in response to the copy of the particular data pattern not already stored in the pattern repository, the new copy of the particular data pattern in the pattern repository and store the new pointer in the one or more storage devices to reference the new copy of the particular data pattern.

10. The system of claim 9, wherein the access time is evaluated in terms of a locality of the particular data pattern.

11. The system of claim 9, wherein the pattern repository is a single instance store.

12. The system of claim 9, wherein the access time is based on weighing a storage efficiency benefit of accessing the particular data pattern against a compression ratio.

13. The system of claim 9, further comprising:

multiple segments divided into the pattern repository; and

a module configured to read one or more of the multiple segments into a cache buffer and further configured to access one or more of the multiple segments from the cache buffer.

14. The system of claim 12, wherein the compression ratio is based on a compression efficiency.

15. The system of claim 9, further comprising:

a raid module configured to designate a number of segments of the pattern repository as redundant segments and further configured to replace a failed media segment with a redundant segment.

16. The system of claim 9, wherein the system is configured to reset one or more pointers stored in the one or more storage devices to reference a different data pattern copy stored in the pattern repository.

17. A computer readable storage medium storage containing executable program instructions executed by a processor, comprising:

program instructions that receive a first data stream from one or more clients, wherein the first data stream comprises one or more data patterns referenced by one or more pointers stored in one or more storage devices;

program instructions that receive a second data stream from the one or more clients;

program instructions that check if a copy of a particular data pattern of the second data stream is already stored in a pattern repository;

program instructions that store, in response to the copy of the particular data pattern already stored in the pattern repository, a new pointer in the one or more storage devices to reference the copy of the particular data pattern already stored in the pattern repository based on an access time of the copy of the particular data pattern in the pattern repository being less than a predetermined access time;

program instructions that store, in response to the copy of the particular data pattern already stored in the pattern repository, a new copy of the particular data pattern in the pattern repository and store the new pointer in the one or more storage devices to reference the new copy of the particular data pattern based on the access time of the copy of the particular data pattern in the pattern repository being greater than a predetermined access time; and

program instructions that store the new copy of the particular data pattern in the pattern repository and store the new pointer in the one or more storage devices to reference the new copy of the particular data pattern, in response to the copy of the particular data pattern not already stored in the pattern repository.