Disk array system for processing and tracking the completion of I/O requests

• US 6,098,114 A
• Filed: 03/04/1998
• Issued: 08/01/2000
• Est. Priority Date: 11/14/1997
• Status: Expired due to Term

• Current Assignee: Summit Data Systems LLC (Acacia Research Corporation)
• Original Assignee: 3WARE
• Inventors: McDonald, James Arthur, Herz, John Peter, Altman, Mitchell Allen, Smith, III, William Edward
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Kim, Harold
• Application Number:
  US09/034,812
• Time in Patent Office: 881 Days
• Field of Search: 710/3, 710/5, 710/9, 710/27, 710/57, 709/235, 711/4, 711/201, 711/114, 714/6, 714/5, 714/7, 395/500.46
• US Class Current: 710/5
• CPC Class Codes: G06F 13/124 where hardware is a sequential transfer control unit, e.g. microprocessor, peripheral processor or state-machine
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A high-performance RAID system for a PC comprises a controller card which controls an array of ATA disk drives. The controller card includes an array of automated disk drive controllers, each of which controls one respective disk drive. The disk drive controllers are connected to a microcontroller by a control bus and are connected to an automated coprocessor by a packet-switched bus. The coprocessor accesses system memory and a local buffer. In operation, the disk drive controllers respond to controller commands from the microcontroller by accessing their respective disk drives, and by sending packets to the coprocessor over the packet-switched bus. The packets carry I/O data (in both directions, with the coprocessor filling-in packet payloads on I/O writes), and carry transfer commands and target addresses that are used by the coprocessor to access the buffer and system memory. The packets also carry special completion values (generated by the microcontroller) and I/O request identifiers that are processed by a logic circuit of the coprocessor to detect the completion of processing of each I/O request. The coprocessor grants the packet-switched bus to the disk drive controllers using a round robin arbitration protocol which guarantees a minimum I/O bandwidth to each disk drive. This minimum I/O bandwidth is preferably greater than the sustained transfer rate of each disk drive, so that all drives of the array can operate at the sustained transfer rate without the formation of a bottleneck.

Claims

1. In a disk array system which comprises an array of disk drives which are controlled by an array of controllers, a method of processing an input/output (I/O) request so as to efficiently detect the completion of processing of the I/O request, the I/O request generated by a host computer and specifying a transfer of data between the host computer and the array of disk drives, the method comprising the steps of:

(a) providing a completion monitoring circuit, the completion monitoring circuit configured to apply a logic function to a variable-length sequence of completion values to monitor the completion status of an I/O request;

(b) identifying a plurality of the controllers that are invoked by the I/O request, and generating a respective command sequence for each invoked controller, each command sequence specifying a sequence of disk transfer operations to be performed by a respective controller to process the I/O request, wherein different I/O requests invoke different numbers of controllers of the array of controllers;

(c) generating a plurality of completion values, each completion value corresponding to a different command sequence generated in step (b), the completion values generated such that application of the logic function to the plurality completion values produces a preselected final completion value that is known to the completion monitoring circuit;

(d) dispatching the command sequences generated in step (b) and the corresponding completion values generated in step (c) to the respective controllers that are invoked by the I/O request, and processing the command sequences with the controllers to transfer I/O data between the disk drives and the host computer;

(e) at each controller invoked by the I/O request, when processing of the respective command sequence dispatched in step (d) is complete, transferring the corresponding completion value to the completion monitoring circuit; and

(f) at the completion monitoring circuit, applying the logic function to the completion values transferred in step (e) and comparing an output of the logic function to the final completion value to detect the completion of processing of the I/O request.

2. The method as in claim 1, wherein each controller controls the operation of a single, respective disk drive, and wherein each command sequence generated in step (b) specifies a sequence of disk transfer operations to be performed by a single disk drive.

3. The method as in claim 1, wherein the completion monitoring circuit is configured to concurrently monitor the completion status of multiple pending I/O requests, and wherein the method further comprises the steps of:

assigning an identifier to the I/O request, and transmitting the identifier to each controller that is invoked by the I/O request; and

transferring the identifier from each controller invoked by the I/O request to the completion monitoring circuit in association with the completion values transferred in step (e) to enable the completion monitoring circuit to identify the I/O request to which each completion value corresponds.

4. The method as in claim 3, wherein the step of assigning an identifier to the I/O request is performed by a device driver that is executed by the host computer, and wherein the completion monitoring circuit uses the identifier to notify the device driver of the identity of the I/O request when the I/O processing of the I/O request is completed.

5. The method as in claim 3, wherein the steps of generating and dispatching the command sequences and the completion values are performed by a microcontroller that executes a control program, and wherein the completion monitoring circuit sends the identifier of the I/O request to the microcontroller when the final completion value is reached to inform the microcontroller that processing of the I/O request is complete, the method thereby enabling the microcontroller to monitor the completion status of multiple pending I/O requests without directly monitoring transfers of I/O data.

6. The method as in claim 3, wherein the control program implements a RAID storage algorithm, and step (b) comprises applying the RAID algorithm to the I/O request to identify the disk drives that are invoked by the I/O request.

7. The method as in claim 1, wherein the command sequences and the completion values are dispatched in step (d) over a control bus that is separate from a bus that is used for transfers of I/O data, so that bus traffic resulting from the dispatching of the command sequences and the completion values does not interfere with the flow of I/O data between the disk drives and the host computer.

8. A disk array controller card configured to connect a host computer to an array of disk drives, the controller card comprising:

a completion monitoring circuit, the completion monitoring circuit configured to apply a logic function to a variable-length sequence of completion values to monitor the completion status of an input/output (I/O) request being processed by the controller card, the I/O request generated by the host computer and specifying a transfer of data between the host computer and a plurality of the disk drives of the array;

a plurality of controllers, each controller connected to and configured to control the operation of at least one respective disk drive of the array; and

a microcontroller that runs a control program, the microcontroller configured via the control program to receive an I/O request from the host computer and to generate a plurality of completion values, the plurality of completion values generated such that application of the logic function to the plurality completion values produces a final completion value that is known to the completion monitoring circuit, the microcontroller further configured to transfer each completion value to a different respective controller that is invoked by the I/O request;

wherein each invoked controller passes a respective completion value to the completion monitoring circuit upon finishing processing the I/O request, and wherein the completion monitoring circuit applies the logic function to the completion values received from the controllers and compares a result of the logic function to the final completion value to determine whether the last completion value of the plurality of completion values has been received.

9. The disk array controller card according to claim 8, wherein the completion monitoring circuit receives the plurality of completion values from the controllers serially, and applies the logic function to the completion values cumulatively as the completion values are serially received.

10. The disk array controller card according to claim 9, wherein the completion monitoring circuit cumulatively applies a logical OR operation to the completion values.

11. The disk array controller card according to claim 8, wherein the controller card processes multiple I/O requests concurrently, and the completion monitoring circuit concurrently monitors the completion status of multiple pending I/O requests.

12. The disk array controller card according to claim 11, wherein each invoked controller passes a token value to the completion monitoring circuit with the respective completion value, the token value uniquely identifying the I/O request among the multiple pending I/O requests.

13. The disk array controller card according to claim 12, wherein the token value is generated by the host computer and is passed to the controller card in association with the I/O request, and wherein the controller card uses the token value to notify the host computer of the completion of the I/O request when the final completion value is reached.

14. The disk array controller card according to claim 8, wherein the microcontroller is further configured via the control program (i) to generate a respective command sequence for each invoked controller, each command sequence specifying a constituent sequence of disk transfer operations to be performed by a respective controller to process the I/O request, and (ii) to transfer each command sequence to a different respective controller that is invoked by the I/O request.

15. The disk array controller card according to claim 8, wherein the control program implements a RAID algorithm.

16. The disk array controller card according to claim 8, wherein at least one disk drive of the array is an ATA drive.

17. The disk array controller card according to claim 8, wherein at least one disk drive of the array is a CD-ROM drive.

18. In a disk array system which comprises an array of disk drives which are controlled by an array of controllers, a method of processing an input/output (I/O) request so as to efficiently detect the completion of processing of the I/O request, the I/O request generated by a host computer and specifying a transfer of data between the host computer and a variable number of disk drives, the method comprising the steps of:

(a) providing a completion monitoring circuit, the completion monitoring circuit configured to apply a logic function to a variable-length sequence of completion values to monitor the completion status pending I/O requests;

(b) in response to receipt of the I/O request from the host computer, generating a plurality of completion values and transmitting each completion value to a different respective controller that is invoked by the I/O request, the completion values generated such that application of the logic fuction to the plurality completion values produces a preselected final completion value that is known to the completion monitoring circuit;

(c) at each controller invoked by the I/O request, when processing of the I/O request is complete, transferring the completion value transmitted to the controller in step (b) to the completion monitoring circuit; and

(d) at the completion monitoring circuit, applying the logic function to the completion values transferred in step (c), and comparing an output of the logic function to the final completion value to detect the receipt of the last completion value.

19. The method of processing an I/O request as in claim 18, wherein step (c) comprises serially transferring the plurality of completion values to the completion monitoring circuit, and step (d) comprises applying the logic function to the completion values cumulatively as the completion values are serially received.

20. The method of processing an I/O request as in claim 19, wherein step (d) comprises cumulatively applying a logical OR function to the completion values.

21. The method of processing an I/O request as in claim 18, wherein step (d) comprises concurrently applying the logic function to multiples sets of completion values, each set corresponding to a different I/O request, to concurrently monitor the completion status of multiple pending I/O requests.

22. The method of processing an I/O request as in claim 18, wherein step (c) comprises transferring each completion value to the completion monitoring circuit with a token value that uniquely identifies the I/O request among multiple pending I/O requests, and wherein step (d) comprises using the token value transferred in step (c) to distinguish the I/O request from other pending I/O requests.

23. The method of processing an I/O request as in claim 22, wherein the token value is generated by host computer and is passed to the controller card in association with the I/O request, and wherein the method further comprises the step of:

(e) in response to detecting the receipt of the last completion value in step (c), using the token value to notify the host computer of the completion of the I/O request.