Methods and systems for improving read performance in data de-duplication storage

• US 7,962,706 B2
• Filed: 02/14/2008
• Issued: 06/14/2011
• Est. Priority Date: 02/14/2008
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Davis, Camden John
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US12/031,560
• Publication Number:
  US 20090210640A1
• Time in Patent Office: 1,216 Days
• Field of Search: None
• US Class Current: 711/158
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

The present invention is directed toward methods and systems for data de-duplication. More particularly, in various embodiments, the present invention provides systems and methods for data de-duplication that may utilize a data de-duplication system that retrieves data from a data storage device in an order based on the location of blocks on the data storage device. Some embodiments break a data stream into multiple blocks of data and store the blocks of data on a data storage device of a data de-duplication system, wherein a code representing a redundant block of data is stored in place of the block of data. A location for each block of data may be stored. Additionally, the blocks may be read in an order that is determined based on the location of the blocks.

Claims

1. A method of data storage in a data de-duplication system comprising:

receiving a first order to read blocks of data;

determining a second order to read blocks of data based on a location of the blocks stored on a data storage device in the data de-duplication system, where the second order is configured to improve read performance as compared to the first order;

reading the blocks in the second order; and

buffering and reordering the blocks to comply with the first order.

2. The method of claim 1, comprising breaking a data stream into multiple blocks of data and storing a unique block of data on the data storage device of the data de-duplication system.

3. The method of claim 1, where a code representing a redundant block of data comprises a hash.

4. The method of claim 1, where storing a location for an individual block of data comprises storing a location to a pointer to a block of data.

5. The method of claim 1, where storing a location for an individual block of data comprises storing a pointer to a block of data.

6. The method of claim 1, where the data storage device comprises at least one of a disk drive and a tape drive.

7. The method of claim 1, where the second order is determined based on the location of the blocks stored on the data storage device relative to a read device.

8. The method of claim 1, where the data storage device comprises multiple data storage devices connected together in an array of storage devices.

9. The method of claim 8, where the array of storage devices comprises an array of disk drives.

10. The method of claim 1, where the location of an individual block comprises a physical location on a storage media.

11. A data de-duplication system comprising:

a data storage device configured to store data using data de-duplication;

a memory configured to store instructions;

a processor configured to read the memory and execute the instructions, the instructions configured to cause the processor to;

receive a first order to read blocks;

determine a second order to read the blocks based on a location of blocks on the data storage device, where the second order is configured so that fewer position commands are required prior to the blocks being read when compared to the first order;

read the blocks in the second order determined; and

buffer and reorder the data blocks to comply with the first order.

12. The data storage system of claim 11, where the instructions are further configured to cause the processor to break a data stream into multiple blocks of data and store a unique block of data on the data storage device using data de-duplication.

13. The data storage system of claim 12, where a code representing a redundant block of data comprises a hash.

14. The data storage system of claim 11, where storing a location for an individual block of data comprises storing a location to a pointer to a block of data.

15. The data storage system of claim 11, where storing a location for an individual block of data comprises storing a pointer to a block of data.

16. The data storage system of claim 11, where the data storage device comprises at least one of a disk drive and a tape drive.

17. The data storage system of claim 11, where the second order is determined based on the location of the blocks stored on the data storage device relative to a read device.

18. The data storage system of claim 11, where the data storage device comprises multiple data storage devices connected together in an array of storage devices.

19. The data storage system of claim 18, where the array of storage devices comprises an array of disk drives.

20. The data storage system of claim 11, where the location of an individual block comprises a physical location on a storage media.