Use of activity bins to increase the performance of disk arrays

• US 6,775,794 B1
• Filed: 05/23/2001
• Issued: 08/10/2004
• Est. Priority Date: 05/23/2001
• Status: Expired due to Fees

• Current Assignee: Summit Data Systems LLC (Acacia Research Corporation)
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Horst, Robert W., Therene, Christophe
• Primary Examiner(s): Iqbal, Nadeem
• Application Number:
  US09/863,523
• Time in Patent Office: 1,175 Days
• Field of Search: 714/42, 714/43, 714/44, 714/48, 714/6, 714/7, 711/113, 711/114, 711/133, 711/134, 711/159, 711/126, 711/162
• US Class Current: 714/42
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity

Abstract

A disk array controller reliably improves performance in RAID configurations without the need for a battery backup. Write completion interrupts are queued until a write cache flush has been performed and are then sent to a host system. States of ranges of disk addresses (activity bins) are stored in nonvolatile storage elements associated with the ranges. The states allow rebuild times to be reduced after power failures and drive failures. A range is in a Changing state if at least one of the addresses is the target of a write operation that has been initiated but not completed. The range is in a Stable state if no addresses are the target of an uncompleted write operation. Two additional states are used to identify ranges of disk addresses that have been zeroed or never been written to. The additional states allow substantial reductions in RAID volume creation times.

Claims

1. A method of reducing a rebuild time of a disk drive in a disk array, the method comprising:

maintaining activity data indicating a respective state of each of a plurality of disk address ranges in which input/output (I/O) data can be stored on the disk drive, wherein the activity data for each disk address range reflects whether that disk address range is the target of a write operation that is pending, such that the activity data for the plurality of disk address ranges may be used following a power failure to identify disk address ranges in which one or more write operations did not complete successfully; and

during a rebuild operation, skipping over at least one of the disk address ranges for which the activity data indicates that no rebuild of I/O data is required.

2. The method as in claim 1, wherein the activity data is maintained in a nonvolatile memory.

3. The method as in claim 1, wherein each of the plurality of disk address ranges is mutually exclusive.

4. The method as in claim 1, wherein each of the plurality of disk address ranges is contiguous.

5. The method as in claim 1, wherein each of the plurality of disk address ranges is substantially equal in size.

6. The method as in claim 1, wherein the nonvolatile memory is a solid state memory of a disk array controller.

7. The method as in claim 1, wherein the nonvolatile memory comprises a portion of the disk drive which is separate from the plurality of disk address ranges.

8. The method as in claim 1, further comprising clearing activity data stored in the nonvolatile memory in response to a completion of a write cache flush.

9. The method as in claim 1, further comprising clearing activity data stored in the nonvolatile memory in response to an expiration of a time interval.

26. The method of claim 1, wherein skipping over at least one of the disk address ranges comprises skipping over a disk address range for which corresponding activity data indicates that no write operations are pending.

27. The method of claim 1, further comprising, during the rebuild operation, rebuilding a disk address range for which corresponding activity data indicates that a write operation has not completed successfully.

28. The method of claim 1, wherein maintaining the activity data comprises keeping track of whether a disk address range has been written to since being zeroed, and the method further comprises using the activity data during the rebuild operation to identify and skip over a disk address range that has not been written to since being zeroed.

29. The method of claim 1, wherein maintaining the activity data comprises keeping track of whether a disk address range has been written to since creation of an array unit, and the method further comprises using the activity data during the rebuild operation to identify and skip over a disk address range that has not been written to since creation of the array unit.

30. The method of claim 1, wherein the rebuild operation is performed following a power failure event using activity data generated prior to the power failure event.

31. A disk array controller that embodies the method of claim 1.

10. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in at least one of the memory elements indicates that the associated address range does not contain written data.

11. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in at least one of the memory elements indicates that the associated address range may have been the target of a write that may not have been completed.

12. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in at least one of the memory elements indicates that the associated address range has not been the target of a write that may not have been completed.

13. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in a memory element indicates at least whether any portion of an address range corresponding to the memory element has been the target of an initiated write operation the completion of which has not been confirmed.

14. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in a memory element indicates at least whether an address range corresponding to the memory element has been zeroed.

15. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in a memory element further indicates at least whether an address range corresponding to the memory element has ever been written to.

16. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements; and

performing a rebuild of a drive in the disk array wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range, wherein the disk activity data stored in a memory element indicates at least whether any portion of an address range corresponding to the memory element has been the target of an initiated write operation.

17. A method of rebuilding a disk array, the method comprising:

for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk array, maintaining an associated memory element;

storing disk activity data in at least one of the memory elements, wherein the disk activity data for a disk address range indicates at least one of the following;

(a) whether the respective disk address range is the target of a pending write operation, (b) whether the respective disk address range has been written to since being zeroed, (c) whether the respective disk address range has been written to since creation of a corresponding array unit; and

selectively rebuilding portions of a drive in the disk array based at least upon disk activity data stored in at least one of the memory elements, whereby a rebuild time is reduced.

18. The method of claim 17, wherein the associated memory elements are maintained in nonvolatile storage.

32. The method of claim 17, wherein selectively rebuilding portions of a drive comprises rebuilding a disk address range for which corresponding activity data indicates that a write operation is pending.

33. The method of claim 17, wherein selectively rebuilding portions of a drive comprises skipping over a disk address range that, according to the corresponding disk activity data, has not been written to since being zeroed.

34. The method of claim 17, wherein selectively rebuilding portions of a drive comprises skipping over a disk address range that, according to the corresponding disk activity data, has not been written to since creation of the array unit.

35. A disk array controller that embodies the method of claim 17.

19. A method of operating a RAID volume, the method comprising:

receiving a first write operation directed to a first range of target addresses;

storing activity data in a first nonvolatile memory element associated with the first range of target addresses;

no earlier than the activity data has been stored in the first nonvolatile memory element, initiating the first write operation;

experiencing a loss of power that interrupts the completion of the first write operation;

after power is restored, rebuilding at least the first range of target addresses based at least upon the activity data stored in the first nonvolatile memory element;

receiving a second write operation directed to a second range of target addresses;

initiating the second write operation;

no earlier than the second write operation has been completed and before the loss of power, storing activity data in the nonvolatile memory element associated with the second range of target addresses; and

after power is restored, skipping the rebuilding of at least the second range of target addresses based at least upon the activity data stored in the second nonvolatile memory element.

20. A method for maintaining a history of recently occurring disk activity, the method comprising:

maintaining two sets of storage elements in a nonvolatile memory;

storing disk activity data related to a write operation within both sets of storage elements before initiating a write to disk media of write operation data for the write operation; and

periodically clearing alternating ones of the two sets of storage elements such that a most recent set of activity data is not lost when one set of storage elements is cleared.

21. The method of claim 20, further comprising performing a rebuild of a drive in a drive array, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in one of the sets of storage elements.

22. A method for identifying recently written portions of a disk drive, the method comprising:

(a) for each of a plurality of ranges of multiple disk addresses representing substantially the entire addressable storage space of the disk drive, maintaining a first associated memory element in nonvolatile storage and maintaining a second associated memory element in nonvolatile storage;

(b) setting all of the first and second memory elements to a first value;

(c) identifying a write command directed to at least one of the ranges of disk addresses;

(d) for the first and second memory elements that are associated with the at least one range of the ranges of disk addresses to which the write command is directed, setting the first and second memory elements to a second value; and

(e) subsequent to (d), initiating a write operation to execute the write command.

23. The method of claim 22, further comprising:

(f) resetting all of the first memory elements to the first value; and

(g) a predetermined amount of time after (f), resetting all of the second memory elements to the first value.

24. The method of claim 23, further comprising

(h) a predetermined amount of time after (g), repeating (f) and (g);

and

(i) repeating (h) a plurality of times.

25. The method of claim 22, further comprising performing a rebuild of the disk drive, wherein the rebuild skips the rebuilding of at least one address range based at least upon disk activity data stored in a memory element for the address range.

36. A method of reducing rebuild times in a redundant disk array system, the method comprising:

at an outset of a write operation, recording, within a non-volatile memory, an indication that a disk address range to which the write operation corresponds is in a first state;

if the write operation completes successfully and no other write operations are pending within the disk address range, updating the non-volatile memory to indicate that the disk address range is in a second state; and

during a rebuild operation, rebuilding data stored within the disk address range if the non-volatile memory indicates that the disk address range is in the first state, and skipping rebuilding of the data stored within the disk address range if the non-volatile memory indicates that the disk address range is in the second state.

37. The method of claim 36, wherein the step of updating the non-volatile memory is performed in response to a cache flush operation that causes a disk drive to commit cached write data to disk media.

38. A disk array controller that controls disk drives of a redundant disk array according to the method of claim 36.

39. The method of claim 36, wherein the non-volatile memory is a solid state memory of a disk array controller.

40. The method of claim 36, further comprising, before any write operations are performed within the disk address range, maintaining within the non-volatile memory an indication that the disk address range does not contain write data.