Methods and apparatus for system memory efficient disk access to a raid system using stripe control information

• US 6,021,462 A
• Filed: 08/29/1997
• Issued: 02/01/2000
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Brisbin, John W., Minow, Martin A.
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US08/921,401
• Time in Patent Office: 886 Days
• Field of Search: 711/112, 711/113, 711/114, 711/161, 711/162, 711/154, 711/111
• US Class Current: 711/114
• CPC Class Codes: G06F 3/061 Improving I/O performance
• 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 technique for accessing a series of secondary storage devices where a reduced amount of main memory is needed to implement the data transfer is disclosed. The technique operates to share control information stored in the main memory so that most of the main memory allocated to implementing a data transfer is shared by the series of the secondary storage drives.

Claims

1. A method for accessing a plurality of disk drives having data stored thereon with a stripe organization, said method comprising:

(a) receiving a data transfer request, the data transfer request identifies requested data to be retrieved from the disk drives;

(b) obtaining stripe control information, the stripe control information including at least a sequence of commands for accessing data from the disk drives;

(c) determining initial control information for each of the disk drives based on the data transfer request and the stripe control information, the initial control information including at least an initial command, a length and a next command indicator;

(d) accessing the disk drives in accordance with the initial control information for each of the disk drives to obtain a portion of the requested data; and

(e) thereafter accessing the disk drives in accordance with the stripe control information to obtain a remaining portion of the requested data, said accessing (e) comprising

(e1) for each of the disk drives, selecting one of the sequence of commands in the stripe control information based on the next command indicator;

(e2) respectively accessing each of the disk drives in accordance with the selected command for each of the disk drives; and

(e3) subsequently, respectively accessing each of the disk drives in accordance with the commands sequentially following the selected command in the stripe control information for each of the disk drives.

2. A method as recited in claim 1, wherein the initial control information includes at least an initial command, a length, and a next command indicator.

3. A method as recited in claim 1, wherein the stripe control information is shared by the disk drives.

4. A method for accessing a plurality of disk drives having data stored thereon with a stripe organization, said method comprising:

(a) receiving a data transfer request, the data transfer request identifies requested data to be retrieved from the disk drives;

(b) obtaining stripe control information, the stripe control information including at least a sequence of commands for accessing data from the disk drives;

(c) determining initial control information for each of the disk drives based on the data transfer request and the stripe control information, the initial control information including at least an initial command, a length and a next command indicator;

(d) accessing the disk drives in accordance with the initial control information for each of the disk drives to obtain a portion of the requested data; and

(e) thereafter accessing the disk drives in accordance with the stripe control information to obtain a remaining portion of the requested data said accessing (e) of the disk drives being performed in accordance with the sequence of commands, and the next command indicator pointing to one of the commands in the sequence of commands where the next command following the initial command is obtained.

5. A method as recited in claim 4, wherein subsequent next commands are obtained from the sequence of commands as those that sequentially follow the next command.

6. A method as recited in claim 5, wherein the sequence of commands is a repetitive sequence of commands.

7. A method as recited in claim 6, wherein the commands within the sequence of commands include at least a skip command and a transfer command.

8. A method as recited in claim 7, wherein the commands within the sequence of commands further includes a repeat command.

9. A method as recited in claim 4, wherein the stripe control information is shared by the disk drives.

10. A method as recited in claim 4, wherein the stripe control information is constructed into a table when the disk drives are instantiated and thereafter subsequently utilized for data access by each of the disk drives.

11. A method as recited in claim 4, wherein said obtaining (b) of the stripe control information comprises:

determining the stripe control information based on the stripe organization for the data storage on the disk drives.

12. A method as recited in claim 11, wherein said method is performed by a computer system, and

wherein the plurality of disk drives form a redundant array of inexpensive disks (RAID) organization.

13. A method as recited in claim 12, wherein said determining of the stripe control information occurs when the RAID organization is instantiated and is thereafter not modified during operation of the computer system.

14. A computer system, comprising:

a plurality of disk storage devices having data striped across said disk storage devices;

a main memory including random-access memory (RAM), the RAM including a permanent resident portion and a transitory portion;

stripe control information stored in the RAM, said stripe control information contains at least one or more commands for data access that define the striping of the data across said disk storage devices;

a virtual-to-physical address translator to translate virtual addresses to physical addresses; and

a storage device controller for controlling access to said disk storage devices, said controlling including receiving a data transfer request, forwarding the data transfer request to said virtual-to-physical address translator to produce a physical scatter-gather list for the data transfer request, determining initial control information for the physical scatter-gather list, determining subsequent control information for the physical scatter-gather list from the stripe control information, and accessing each of said disk storage devices in accordance with the initial control information and then in accordance with the subsequent control information, said accessing in accordance with the subsequent control information comprising (i) for each of the disk drives, selecting one of the commands in the subsequent control information, (ii) respectively accessing each of the disk drives in accordance with the selected command for each of the disk drives, and (iii) subsequently, respectively accessing each of the disk drives in accordance with the commands sequentially following the selected command in the subsequent control information for each of the disk drives.

15. A computer system as recited in claim 14, wherein the initial control information provides at least a disk command, and

wherein the stripe control information includes at least a sequence of commands for accessing data from the disk drives.

16. A computer system as recited in claim 15,

wherein the stripe control information is constructed into a table when the disk drives are instantiated and thereafter subsequently utilized for data access by each of the disk drives.

17. A computer system as recited in claim 14, wherein the plurality of disk drives form a redundant array of inexpensive disks (RAID).

18. A computer system as recited in claim 14, wherein said storage device controller determines the initial control information based on the stripe control information.

19. A computer system, comprising:

a plurality of disk storage devices having data striped across said disk storage devices;

a main memory including random-access memos (RAM), the RAM including a permanent resident portion and a transitory portion;

stripe control information stored in the RAM, said stripe control information contains at least one or more commands for data access that define the striping of the data across said disk storage devices;

virtual-to-physical address translator to translate virtual addresses to physical addresses; and

a storage device controller for controlling access to said disk storage devices, said controlling receives a data transfer request and includes,

means for forwarding the data transfer request to said virtual-to-physical address translator to produce a physical scatter-gather list for the data transfer request;

means for determining initial control information for the physical scatter-gather list;

means for determining subsequent control information for the physical scatter-gather list from the stripe control information; and

means for accessing each of said disk storage devices in accordance with the initial control information and then in accordance with the subsequent control information,

wherein said means for accessing operates to access the disk storage devices in accordance with the subsequent control information comprising (i) for each of the disk drives, selecting one of the commands in the subsequent control information, (ii) respectively accessing each of the disk drives in accordance with the selected command for each of the disk drives, and (iii) subsequently, respectively accessing each of the disk drives in accordance with the commands sequentially following the selected command in the subsequent control information for each of the disk drives.

20. A computer readable medium containing program instructions for accessing a plurality of disk drives having data stored thereon in a striped manner, said computer readable medium comprising:

computer readable code devices for receiving a data transfer request, the data transfer request identifies requested data to be retrieved from the disk drives;

computer readable code devices obtaining stripe control information, the stripe control information including at least a sequence of commands for accessing data from the disk drives;

computer readable code devices for determining initial control information for each of the disk drives based on the data transfer request and the stripe control information, the initial control information including at least an initial command a length and a next command indicator;

computer readable code devices for accessing the disk drives in accordance with the initial control information for each of the disk drives to obtain a portion of the requested data; and

computer readable code devices for thereafter accessing the disk drives in accordance with the stripe control information to obtain a remaining portion of the requested data, the accessing operates to (i) for each of the disk drives, selecting one of the sequence of commands in the stripe control information based on the next command indicator, (ii) respectively accessing each of the disk drives in accordance with the selected command for each of the disk drives, and (iii) subsequently, respectively accessing each of the disk drives in accordance with the commands sequentially following the selected command in the stripe control information for each of the disk drives.

21. A computer readable medium as recited in claim 20, wherein the initial control information includes at least an initial command, a length, and a next command indicator.

22. A computer readable medium as recited in claim 20, wherein the stripe control information is shared by the disk drives.

23. A computer readable medium as recited in claim 20, wherein the initial control information provides at least a disk command, and

wherein the stripe control information includes at least a sequence of commands for accessing data from the disk drives.

24. A computer readable medium as recited in claim 23, wherein the stripe control information is constructed into a table when the disk drives are instantiated and thereafter subsequently utilized for data access by each of the disk drives.

25. A computer readable medium as recited in claim 23, wherein the plurality of disk drives form a redundant array of inexpensive disks (RAID) organization, and

wherein said computer readable code devices for obtaining the stripe control information include computer readable program code to determine the stripe control information based on the stripe organization for the data storage on the disk drives.

26. A computer readable medium as recited in claim 25, wherein the RAID organization is part of a computer system, and

wherein said computer readable program code to determine the stripe control information determines the stripe control information once when the RAID organization is instantiated and is thereafter not modified during operation of the computer system.

27. A computer readable medium containing program instructions for transferring data from a plurality of disk drives having data stored thereon in a striped manner said computer readable medium comprising:

computer readable code devices for receiving a data transfer request, the data transfer request identifies requested data to by retrieved from the disk drives;

computer readable code devices obtaining stripe control information, the stripe control information including at least a sequence of commands for accessing data from the disk drives;

computer readable code devices for determining initial control information for each of the disk drives based on the data transfer request and the stripe control information, the initial control information including at least an initial command, a length and a next command indicator;

computer readable code devices for accessing the disk drives in accordance with the initial control information for each of the disk drives to obtain a portion of the requested data; and

computer readable code devices for thereafter accessing the disk drives in accordance with the stripe control information to obtain a remaining portion of the requested data, said accessing of the disk drives being performed in accordance with the sequence of commands, and the next command indicator pointing to one of the commands in the sequence of commands where the next command following the initial command is obtained.

28. A computer readable medium as recited in claim 27, wherein subsequent next commands are obtained from the sequence of commands as those that sequentially follow the next command.

29. A computer readable medium as recited in claim 28, wherein the sequence of commands is a repetitive sequence of commands.

30. A computer readable medium as recited in claim 29, wherein the command within the sequence of commands include at least a skip command and a transfer command.