Method and apparatus for preventing permanent data loss due to single failure of a fault tolerant array

• US 7,774,643 B2
• Filed: 01/06/2006
• Issued: 08/10/2010
• Est. Priority Date: 01/06/2006
• Status: Expired due to Fees

• Current Assignee: Dot Hill Systems Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Dot Hill Systems Corporation (Seagate Technology Holdings Plc)
• Inventors: Wang, Yuanru Frank
• Primary Examiner(s): Baderman; Scott T
• Assistant Examiner(s): Ko; Chae
• Application Number:
  US11/326,799
• Publication Number:
  US 20070159897A1
• Time in Patent Office: 1,677 Days
• Field of Search: 714/6, 714/7, 714/8
• US Class Current: 714/6.13
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata

Abstract

Methods and systems for preventing permanent data loss due to a single failure in an array of storage devices are described. In particular, a defective memory block is detected and data that was on the now defective memory block is reconstructed using backup data in the array. The reconstructed data is stored in a replacement memory block, without requiring the rewriting of data in non-defective memory blocks. The information mapping the defective memory block to the replacement memory block may be stored as metadata on a storage device.

Claims

1. A method of avoiding permanent data loss due to a defect in an information storage system, comprising:

designating a first storage device to store data and not metadata, and a second storage device to store metadata;

determining if the first storage device is a new storage device;

if the first storage device is not a new storage device, determining a number of defective blocks in the first storage device and setting an index to the number of defective blocks in the first storage device; and

if the first storage device is a new storage device, foregoing determining the number of defective blocks in the first storage device and setting the index to zero;

detecting a defective block on the first storage device;

incrementing the index upon detection of the defective block, wherein the index corresponds to a number of defective blocks identified on the first storage device, wherein the first storage device is identified as critical if the index reaches a predetermined value;

in response to detecting the defective block, reconstructing data that was stored at the defective block to a different block on the first storage device, wherein reconstructing data comprises recreating the data originally stored in the defective block without using data from the defective block; and

mapping the defective block to the different block with mapping metadata and storing the mapping metadata in the second storage device, wherein the mapping metadata identifies the defective block, the different block and the logical connection between the defective block and different block, wherein the data that was stored at the defective block is associated with a stripe of data comprising a number of blocks including at least one non-defective block and wherein the at least one non-defective block is not reconstructed.

2. The method of claim 1, wherein the first storage device is further portioned into a first part that is user accessible and a second part that is only available for controller access.

3. The method of claim 2, wherein the defective block is on the first part of the first storage device and the different block is on the second part of the first storage device.

4. The method of claim 1, wherein the different block is on a third storage device.

5. The method of claim 1, wherein the defective block was initially detected in response a read command issued by a controller of the first storage device.

6. The method of claim 1, further comprising storing the mapping metadata on the second storage device about the relationship between the defective block and the different block.

7. The method of claim 6, further comprising:

in response to receiving at least one of a read, write, and verify command for the defective block, consulting the mapping metadata on the second storage device to determine the location of the reconstructed data; and

performing the at least one of a read, write and verify command utilizing the reconstructed data from the different block.

8. The method of claim 6, further comprising:

determining that the different block is defective;

in response to determining that the different block is defective, reconstructing data that was stored at the different block to a second different block; and

updating the mapping metadata to identify the defective block, the different block, the second different block, and the logical connection between the defective block, the different block, the second different block, wherein the mapping metadata comprises a nested link between the defective block, the different block, and the second different block.

9. An information storage system, comprising:

a first section of a first storage device for storing data that is user accessible, wherein the first section does not store metadata, wherein if the first storage device is not a new storage device, an index is set to a number of defective memory blocks in the first section of the first storage device, wherein if the first storage device is a new storage device, forego setting the index to the number of defective memory blocks in the first section of the first storage device and set the index to zero, wherein the first storage device is identified as critical if the index is at or above a predetermined value;

a second section of the first storage device for storing data that is not user accessible, wherein the second section does not store metadata; and

a second storage device for storing metadata, wherein metadata stored on the second storage device is a nested link which provides an indication of a relationship between a first memory block in at least one of the first and second sections, a second memory block, and a third memory block, wherein a maximum size of the metadata in the second storage device is configured such that when the second storage device is at capacity the second storage device is identified as critical, wherein the first and second memory blocks are defective memory blocks and the third memory block is a memory block where reconstructed data from the first memory block is stored, wherein reconstructed data comprises data originally stored in the defective block recreated without using data from the defective block.

10. The information storage system of claim 9,

wherein the metadata stored on the second storage device is created in response to determining that the first memory block is defective and the data from the first memory block was reconstructed and stored at the second memory block.

11. The information storage system of claim 9,

wherein the nested link provides an indication of a relationship between the first memory block and the second memory block as well as an indication of a relationship between the second memory block and the third memory block.

12. The information storage system of claim 9,

wherein the first memory block resides in the first section and the second memory block resides in the second section.

13. The information storage system of claim 9,

wherein the third memory block resides on a third storage device.

14. The information storage system of claim 9,

wherein the first memory block and the third memory block reside on the second section.

15. The information storage system of claim 9,

wherein the first memory block and the third memory block reside on the first section.

16. The information storage system of claim 9,

wherein the first and second storage devices are at least one of a disk drive, tape drive, and optical storage device.

17. An information storage system, comprising:

an array of storage means comprising at least a first and second storage means, wherein the first storage means stores data and the second storage means stores metadata, wherein the first storage means does not store metadata; and

a means for controlling the array of storage means, wherein the means for controlling the array of storage means determines if the first storage means is a new storage means, wherein if the first storage means is not a new storage means the means for controlling the array of storage means sets an index to a number of defective memory blocks in the first storage means, wherein if the first storage means is a new storage means the means for controlling the array of storage means foregoes setting the index to the number of defective memory blocks in the first storage means and sets the index to zero, wherein the first storage means is identified as critical if the index is at or above a predetermined value;

wherein the first storage means has a defective block, wherein data stored on the defective block is originally reconstructed by the means for controlling the array of storage means from backup data on storage means other than the second storage means and stored on first alternate block on storage means other than the second storage means, wherein reconstructed data comprises recreating the data originally stored in the defective block without using data from the defective block, wherein the first alternate block is later identified as defective and data originally stored on the defective block is reconstructed on a second alternate block on storage means other than the second storage means, wherein mapping information identifying a relationship between the defective block, the first alternate block, and the third alternate block is stored on the second storage means in connection with the defective block, wherein the data stored on the defective block is associated with a stripe of data comprising a number of blocks including at least one non-defective block, wherein the at least one non-defective block is not reconstructed, and wherein at least one of the first and second alternate blocks and the defective block resides on a different storage means.

18. The system of claim 17, wherein the mapping information relating to the defective block and the first alternate block is stored on the second storage means.

19. The system of claim 18, wherein the mapping information relating to the first alternate block and the second alternate block is stored on the second storage means.

20. The system of claim 18, wherein the mapping information relating to the first alternate block and the second alternate block is stored on the second storage means.

21. The system of claim 18, wherein the array of storage means is at least one of a mirrored array and a parity array.