Method of reducing the complexity of an I/O request to a RAID-4 or RAID-5 array

• US 5,519,849 A
• Filed: 10/25/1994
• Issued: 05/21/1996
• Est. Priority Date: 12/07/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Malan, Steven J., Thiel, David W., Snyder, Sid, Rollow, Alan
• Primary Examiner(s): Harrell, Robert B.
• Assistant Examiner(s): NAJJAR, SALEH
• Application Number:
  US08/329,046
• Time in Patent Office: 574 Days
• Field of Search: 395/500, 395/600, 395/441, 364/425, 364/575, 325/275
• US Class Current: 711/114
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Data storage systems using a RAID-4 or RAID-5 organization divide an application I/O request into a number of individual I/O requests, each of which is contained within the boundaries of a single strip. The data blocks of each chunk on a strip responsive to an I/O request can form a complex geometric pattern requiring complicated operations to perform the I/O request. To simplify the necessary operations, each individual I/O request to a strip is divided into at most three requests targeted to data blocks forming a rectangle and each of these rectangles are processed as a unit. If a data block within a rectangle is unavailable, then the request to that rectangle is further subdivided into at most two requests targeted to data blocks forming smaller, non-overlapping rectangles which collectively are the original rectangle. The recursive decomposition of rectangles into smaller rectangles isolates the data block with an error and permits the selection of fewer and less complicated operation algorithms to complete the I/O request.

Claims

1. In a data storage system having n+1 disks arranged into a RAID array, a plurality of data blocks forming a plurality of data chunks, a plurality of parity blocks forming a plurality of parity chunks, each of said parity chunks associated with n said data chunks, said parity chunks and said data chunks distributed over said n+1 disks, each one of said parity chunks and said associated said n forming a strip, a plurality of said strips forms said RAID array, a method of implementing I/O requests comprising the steps of:

receiving an I/O request from a user application and dividing said I/O request into a plurality of individual I/O requests, each individual I/O request confined to the boundaries of a strip;

determining whether each individual I/O request is targeted to data blocks forming a rectangle;

dividing an individual I/O request into at most three strip I/O requests, each strip I/O request targeted to data blocks forming a rectangle if the individual I/O request is not already targeted to data blocks forming a rectangle;

determining the state of the first one of said rectangles;

selecting an I/O algorithm for processing said first strip I/O request based on said determined state of said first one of said rectangles;

performing said selected I/O algorithm for processing said first strip I/O request;

determining the state of the next one of said rectangles;

selecting an I/O algorithm for processing said next strip I/O request based on said determined state of said next one of said rectangles;

performing said selected I/O algorithm for processing said next strip I/O request; and

repeating the preceding three steps until all strip I/O requests have been processed.

2. In a data storage system having n+1 disks arranged into a RAID array, a plurality of data blocks forming a plurality of data chunks, a plurality of parity blocks forming a plurality of parity chunks, each of said parity chunks associated with n of said data chunks, said parity chunks and said data chunks distributed over said n+1 disks, each one of said parity chunks and said associated n data chunks forming a strip, a plurality of said strips forms said RAID array, a method of implementing I/O requests comprising the steps of:

(a) receiving a read I/O request from a user application and dividing said read I/O request into a plurality of individual read I/O requests, each individual read I/O request confined to the boundaries of a strip;

(b) determining whether one of said individual read I/O request is targeted to data blocks forming a rectangle;

(c) dividing said one of said individual read I/O requests into at most three strip read I/O requests, each strip read I/O request targeted to data blocks forming a rectangle if said individual read I/O request is not already targeted to data blocks forming a rectangle;

(d) determining the state of the first one of said rectangles;

(e) processing said first strip read I/O request using a simple read algorithm;

(f) determining the state of the next one of said rectangles;

(g) processing said next strip read I/O request using a simple read algorithm; and

(h) repeating steps (f) and (g) until all strip read I/O requests for said individual read I/O request have been processed.

3. The method set forth in claim 2 further comprising the steps of:

repeating steps (b) through (h) until all individual read I/O requests have been processed.

4. The method set forth in claim 3 further comprising the steps of:

collecting all data read using said simple read algorithm; and

sending said read data and a signal indicating a successful read I/O request to said user.

5. In a data storage system having n+1 disks arranged into a RAID array, a plurality of data blocks forming a plurality of data chunks, a plurality of parity blocks forming a plurality of parity chunks, each of said parity chunks associated with n of said data chunks, said parity chunks and said data chunks distributed over said n+1 disks, each one of said parity chunks and said associated n data chunks forming a strip, a plurality of said strips forms said RAID array, a method of implementing I/O requests comprising the steps of:

(a) receiving a read I/O request from a user application and dividing said read I/O request into a plurality of individual read I/O requests, each individual read I/O request confined to the boundaries of a strip;

(b) determining whether one of said individual read I/O request is targeted to data blocks forming a rectangle;

(c) dividing said one of said individual read I/O requests into at most three strip read I/O requests, each strip read I/O request targeted to data blocks forming a rectangle if said individual read I/O request is not already targeted to data blocks forming a rectangle;

(d) determining the state of the first one of said rectangles;

(e) processing said first strip read I/O request using a regenerate read algorithm if said first rectangle has unavailable data blocks;

(f) processing said first strip read I/O request using a simple read algorithm if said first rectangle does not have unavailable data blocks;

(g) determining the state of the next one of said rectangles;

(h) processing said next strip read I/O request using a regenerate read algorithm if said next rectangle has unavailable data blocks;

(i) processing said next strip read I/O request using a simple read algorithm if said next rectangle does not have unavailable data blocks;

(j) repeating steps (g) through (i) until all strip read I/O requests for said individual read I/O request have been processed.

6. The method set forth in claim 5, further comprising the steps of:

repeating steps (b) through (i) until all individual read I/O requests have been processed.

7. In a data storage system having n+1 disks arranged into a RAID array, a plurality of data blocks forming a plurality of data chunks, a plurality of parity blocks forming a plurality of parity chunks, each of said parity chunks associated with n of said data chunks, said parity chunks and said data chunks distributed over said n+1 disks, each one of said parity chunks and said associated n data chunks forming a strip, a plurality of said strips forms said RAID array, a method of implementing I/O requests comprising the steps of:

(a) receiving a read I/O request from a user application and dividing said read I/O request into a plurality of individual read I/O requests, each individual read I/O request confined to the boundaries of a strip;

(b) determining whether one of said individual read I/O request is targeted to data blocks forming a rectangle;

(c) dividing said one of said individual read I/O requests into at most three strip read I/O requests, each strip read I/O request targeted to data blocks forming a rectangle if said individual read I/O request is not already targeted to data blocks forming a rectangle;

(d) determining the state of the first one of said rectangles;

(e) processing said first strip read I/O request using a regenerate read algorithm if said first rectangle has unavailable data blocks;

(f) processing said first strip read I/O request using a simple read algorithm if said first rectangle does not have unavailable data blocks;

(g) if said simple read process was unsuccessful, determine if any slivers read successfully;

(h) if no slivers read successfully process said strip read I/O request using a regenerate read algorithm;

(i) if at least one sliver read successfully, divide said first rectangle into first and second clone rectangles;

(j) process said strip read I/O request to said second clone rectangle using a regenerate read algorithm;

(k) determine the state of the next one of said rectangles;

(l) processing said next strip read I/O request using a regenerate read algorithm if said next rectangle has unavailable data blocks;

(m) processing said next strip read I/O request using a simple read algorithm if said next rectangle does not have unavailable data blocks;

(n) if said simple read process was unsuccessful, determine if any slivers read successfully;

(o) if no slivers read successfully process said next strip read I/O request using a regenerate read algorithm;

(p) if at least one sliver read successfully, divide said next rectangle into first and second clone rectangles;

(q) process said strip read I/O request to said second clone rectangle using a regenerate read algorithm;

(r) repeating steps (k) through (q) until all strip read I/O requests for said individual read I/O request have been processed.

8. The method set forth in claim 7, further comprising the steps of:

repeating steps (b) through (r) until all individual read I/O requests have been processed.

9. In a data storage system having n+1 disks arranged into a RAID array, a plurality of data blocks forming a plurality of data chunks, a plurality of parity blocks forming a plurality of parity chunks, each of said parity chunks associated with n of said data chunks, said parity chunks and said data chunks distributed over said n+1 disks, each one of said parity chunks and said associated n data chunks forming a strip, a plurality of said strips forms said RAID array, a method of implementing I/O requests comprising the steps of:

(a) receiving an I/O write request from a user application and dividing said I/O write request into a plurality of individual I/O write requests, each individual I/O write request confined to the boundaries of a strip;

(b) determining whether one of said individual I/O write requests is targeted to data blocks forming a rectangle;

(c) dividing said one of said individual I/O write requests into at most three strip I/O write requests, each strip I/O write request targeted to data blocks forming a rectangle if the individual I/O write request is not already targeted to data blocks forming a rectangle;

(d) determining the state of the first one of said rectangles;

(e) if the number of blocks inside said first rectangle is greater than or equal to the number of blocks outside said first rectangle process said strip I/O write request using a reconstruct write algorithm;

(f) if the number of blocks inside said first rectangle is less than the number of blocks outside said first rectangle process said strip I/O write request using a read modify write algorithm;

(g) determining the state of the next rectangle;

(h) if the number of blocks inside said next rectangle is greater than or equal to the number of blocks outside said first rectangle process said strip I/O write request using a reconstruct write algorithm;

(i) if the number of blocks inside said first rectangle is less than the number of blocks outside said first rectangle process said strip I/O write request using a read modify write algorithm;

(j) repeat step (g) through (i) until all strip I/O write requests have been processed.

10. The method set forth in claim 9, further comprising the steps of:

repeating steps (b) through (j) until all individual I/O write requests have been processed.

11. In a data storage system having n+1 disks arranged into a RAID array, a plurality of data blocks forming a plurality of data chunks, a plurality of parity blocks forming a plurality of parity chunks, each of said parity chunks associated with n of said data chunks, said parity chunks and said data chunks distributed over said n+1 disks, each one of said parity chunks and said associated n data chunks forming a strip, a plurality of said strips forms said RAID array, a method of implementing I/O write requests comprising the steps of:

(a) receiving an I/O write request from a user application and dividing said I/O write request into a plurality of individual I/O write requests, each individual I/O write request confined to the boundaries of a strip;

(b) determining whether one of said individual I/O write requests is targeted to data blocks forming a rectangle;

(c) dividing said one of said individual I/O write requests into at most three strip I/O write requests, each strip I/O write request targeted to data blocks forming a rectangle if the individual I/O write request is not already targeted to data blocks forming a rectangle;

(d) process a strip I/O write request to a rectangle;

(e) if no slivers wrote successfully, repeat said write operation;

(f) if at least one sliver wrote successfully, divide said rectangle into first and second clone rectangles;

(g) repeat said write operation to said second clone rectangle;

(h) if a second write operation to said rectangle results in no slivers being written successfully;

(i) process said strip I/O write request using a reconstruct write algorithm or a read modify write algorithm.

12. The method set forth in claim 11, further comprising the step of:

repeating steps (d) through (i) until all strip I/O write requests for said individual I/O write request have been processed.

13. The method set forth in claim 12, further comprising:

repeating step (b) through (i) until all individual I/O write requests have been processed.

14. The method set forth in claim 13, further comprising:

sending a success signal to said user application if all write operations succeed; and

identifying said successful blocks written and sending a write failure signal to said user application.