METHOD AND APPARATUS FOR DECOMPOSING I/O TASKS IN A RAID SYSTEM

• US 20090222829A1
• Filed: 05/13/2009
• Published: 09/03/2009
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: Douglas P. Doucette, James Leong, Rajesh Sundaram, Scott Schoenthal, Srinivasan Viswanathan, Stephen H. Strange
• Original Assignee: Douglas P. Doucette, James Leong, Rajesh Sundaram, Scott Schoenthal, Srinivasan Viswanathan, Stephen H. Strange
• Inventors: Schoenthal, Scott, Sundaram, Rajesh, Leong, James, Doucette, Douglas P., Viswanathan, Srinivasan, Strange, Stephen H.
• Granted Patent: US 7,926,059 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 11/2087 with a common controller
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• 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
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A data access request to a file system is decomposed into a plurality of lower-level I/O tasks. A logical combination of physical storage components is represented as a hierarchical set of objects. A parent I/O task is generated from a first object in response to the data access request. A child I/O task is generated from a second object to implement a portion of the parent I/O task. The parent I/O task is suspended until the child I/O task completes. The child I/O task is executed in response to an occurrence of an event that a resource required by the child I/O task is available. The parent I/O task is resumed upon an event indicating completion of the child I/O task. Scheduling of any child I/O task is not conditional on execution of the parent I/O task, and a state diagram regulates the child I/O tasks.

Claims

1. A method for decomposing a data access request from a file system into a plurality of lower-level I/O tasks, comprising:

representing a logical combination and configuration of one or more physical storage components of said file system as a hierarchical set of objects;

generating a parent I/O task from a first object in said hierarchical set of objects in response to said data access request from the file system;

generating a child I/O task from a second object in said hierarchical set of objects to implement at least a portion of said parent I/O task;

suspending the parent I/O task until said child I/O task is completed;

executing said child I/O task in response to an occurrence of an event that a resource required by the child I/O task is available, such that scheduling of said child I/O task is not conditional on execution of said parent I/O task; and

resuming the parent I/O task upon an event indicating the completion of said child I/O task, said event indicating to the parent I/O task that the child I/O task has completed.

2. The method of claim 1, further comprising:

using a storage disk as the physical storage component.

3. The method of claim 1, further comprising:

using a plurality of storage disks as the physical storage component.

4. The method of claim 1, further comprising:

using a RAID (redundant array of independent disks) as the physical storage component.

5. The method of claim 1, further comprising:

using non volatile RAM (NVRAM) as the physical storage component.

6. The method of claim 1, further comprising:

using a memory as the physical storage component.

7. The method of claim 1, further comprising:

using a writeable persistent storage device as the physical storage component.

8. The method of claim 1, further comprising:

using a tape as the physical storage component.

9. The method of claim 1 further comprising:

scheduling for execution a grandchild I/O task in response to an occurrence of a second event such that execution of said grandchild I/O task is not conditional on execution of said parent I/O task or said child I/O task; and

indicating to said child I/O task from said grandchild I/O task that said grandchild I/O task completed its execution.

10. A file system apparatus, comprising:

a network adapter to receive a data access request;

a logical combination of one or more physical storage components of said file system represented as a hierarchical set of objects;

a processor to generate a parent I/O task from a first object in said hierarchical set of objects in response to said data access request;

the processor to generate a child I/O task from a second object in said hierarchical set of objects to implement at least a portion of said parent I/O task;

the processor to suspend the parent I/O task until said child I/O task is completed;

the processor to execute said child I/O task in response to an occurrence of an event that a resource required by the child I/O task is available, such that scheduling of said child I/O task is not conditional on execution of said parent I/O task; and

the processor to resume the parent I/O task upon an event indicating the completion of said child I/O task, said event indicating to the parent I/O task that the child I/O task has completed.

11. The apparatus of claim 10, further comprising:

a storage disk used as the physical storage component.

12. The apparatus of claim 10, further comprising:

a plurality of storage disks used as the physical storage component.

13. The apparatus of claim 10, further comprising:

a RAID (redundant array of independent disks) used as the physical storage component.

14. The apparatus of claim 10, further comprising:

non volatile RAM (NVRAM) used as the physical storage component.

15. The apparatus of claim 10, further comprising:

a memory used as the physical storage component.

16. The apparatus of claim 10, further comprising:

a writeable persistent storage device used as the physical storage component.

17. The apparatus of claim 10, further comprising:

a tape used as the physical storage component.

18. The apparatus of claim 10, further comprising:

the processor to schedule for execution a grandchild I/O task in response to an occurrence of a second event such that execution of said grandchild I/O task is not conditional on execution of said parent I/O task or said child I/O task; and

the processor to indicate to said child I/O task that said grandchild I/O task completed execution of said grandchild I/O task.

19. A computer readable storage media, comprising:

said computer readable storage media containing instructions for execution on a processor for a method of decomposing a data access request from a file system into a plurality of lower-level I/O tasks, having,

representing a logical combination and configuration of one or more physical storage components of said file system as a hierarchical set of objects;

generating a parent I/O task from a first object in said hierarchical set of objects in response to said data access request from the file system;

generating a child I/O task from a second object in said hierarchical set of objects to implement at least a portion of said parent I/O task;

suspending the parent I/O task until said child I/O task is completed;

executing said child I/O task in response to an occurrence of an event that a resource required by the child I/O task is available, such that scheduling of said child I/O task is not conditional on execution of said parent I/O task; and

resuming the parent I/O task upon an event indicating the completion of said child I/O task, said event indicating to the parent I/O task that the child I/O task has completed.

20. A method for operating a computer data storage system, comprising:

decomposing a task directed to persistent storage of the data storage system into a plurality of tasks using a state diagram having a plurality of states, the states having,

a first state of the plurality of states indicating that a data access request has been received;

in the event that resources needed to perform the data access request are not available, a second state suspending the data access request;

in the event that resources are available to perform the data access request, entering a third state of the plurality of states to perform the data access request;

decomposing a data access request received by the data storage system to the state diagram to execute the first state, the second state, the third state;

decomposing the first child I/O task to the state diagram to execute the first state, the second state, and the third state, in order to complete the first child I/O task;

in the event that the first child I/O task launches a second child I/O task at the third state as the child I/O task executes, decomposing the second child I/O task to the state diagram to execute the first state, the second state, and the third state, in order to complete the second child I/O task; and

performing the data access request to accomplish an I/O data access to persistent storage of the computer data storage system.

21. The method as in claim 20, further comprising:

in the event that a portion of the data access request requires a XOR task, the third state launching a fourth state to perform the XOR task and suspending the portion until the XOR task completes;

upon completion of any required XOR task, the third state launching a first child I/O task to perform the task, and suspending the I/O task until the first child I/O task is finished;

22. A computer data storage system, comprising:

a state diagram to decompose a task directed to persistent storage of the data storage system into a plurality of tasks using a state diagram having a plurality of states, the states having,

a first state of the plurality of states indicating that a data access request has been received;

in the event that resources needed to perform the data access request are not available, a second state suspending the data access request;

in the event that resources are available to perform the data access request, entering a third state of the plurality of states to perform the data access request;

an operating system to decompose a data access request received by the data storage system to the state diagram to execute the first state, the second state, and the third state;

the first child I/O task decomposed to the state diagram to execute the first state, the second state, and the third state, in order to complete the first child I/O task;

in the event that the first child I/O task launches a second child I/O task at the third state as the child I/O task executes, the second child I/O task decomposed to the state diagram to execute the first state, the second state, and the third state, in order to complete the second child I/O task; and

the data access request performed to accomplish an I/O data access to persistent storage of the computer data storage system.

23. The computer data storage system of claim 22, further comprising:

in the event that a portion of the data access request requires a XOR task, the third state launching a fourth state to perform the XOR task and suspending the portion until the XOR task completes;

upon completion of any required XOR task, the third state launching a first child I/O task to perform the task, and suspending the I/O task until the first child I/O task is finished.

24. A method for operating a computer data storage system, comprising:

decomposing a task directed to persistent storage of the data storage system into a plurality of tasks using a state diagram having a plurality of states, the states having,

a first state of the plurality of states indicating that a data access request has been received;

a second state suspending the data access request in the event that resources needed to perform the data access request are not available;

a third state of the plurality of states to perform the data access request in the event that resources are available to perform the data access request;

a fourth state to perform an XOR task in the event that a portion of the data access request requires an XOR task, and suspending the portion until the XOR task completes;

upon completion of any required XOR task, the third state launching a first child I/O task to perform the task, and suspending the I/O task until the first child I/O task is finished;

decomposing a data access request received by the data storage system to the state diagram to execute the first state, the second state, the third state, and the fourth state to form a decomposed data access request, the data access request directed to persistent storage of the computer data storage system;

decomposing a task from the decomposed data access request to the state diagram to form a second decomposed data access request, and placing the data access request in suspension until the second decomposed data access request completes; and

upon completion of the second decomposed data access request, taking the data access request out of suspension and restarting the first data access request in order to accomplish the data access request directed to persistent storage of the computer data storage system.

25. The method as in claim 24, further comprising:

decomposing a task from the second decomposed data access request to the state diagram to form a third decomposed data access request, and placing the task in suspension until the third decomposed data access request completes.

26. A computer data storage system, comprising:

a processor to decompose a task directed to persistent storage of the data storage system into a plurality of child I/O tasks using a state diagram having a plurality of states, the states having,

a first state of the plurality of states indicating that a data access request has been received;

a second state suspending the data access request in the event that resources needed to perform the data access request are not available for a first child I/O task of the plurality of child I/O tasks;

a third state of the plurality of states to perform the data access request in the event that resources are available for the first child I/O task to perform the data access request;

a fourth state to perform an XOR task by a XOR child I/O task of the plurality of child I/O tasks in the event that a portion of the data access request requires an XOR task, and to suspend the portion until the XOR child I/O task completes;

upon completion of any required XOR child I/O task, the third state launching a further child I/O task of the plurality of child I/O tasks to perform the task, and suspending the I/O task until the further child I/O task is finished;

a process to decompose a data access request received by the data storage system to the state diagram to execute the first state, the second state, the third state, and the fourth state to form a decomposed data access request executed by the plurality of child I/O tasks;

the process to decompose a task from the decomposed data access request to the state diagram to form a second decomposed data access request, and placing the data access request in suspension until the second decomposed data access request completes; and

upon completion of the second decomposed data access request, the process to take the data access request out of suspension and restarting the first data access request in order to accomplish the data access request directed to persistent storage of the computer data storage system by the plurality of child I/O tasks.

27. The computer data storage system as in claim 26, further comprising:

the process to decompose a task from the second decomposed data access request to the state diagram to form a third decomposed data access request, and to place the task in suspension until the third decomposed data access request completes.

28. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for a method of operating a computer data storage system, the method having,

decomposing a task directed to persistent storage of the data storage system into a plurality of tasks using a state diagram having a plurality of states, the states having,

a first state of the plurality of states indicating that a data access request has been received;

a second state suspending the data access request in the event that resources needed to perform the data access request are not available;

a third state of the plurality of states to perform the data access request in the event that resources are available to perform the data access request;

decomposing a data access request received by the data storage system to the state diagram to execute the first state, the second state, and the third state, to form a decomposed data access request, the data access request directed to persistent storage of the computer data storage system;

decomposing a task from the decomposed data access request to the state diagram to form a second decomposed data access request, and placing the data access request in suspension until the second decomposed data access request completes; and

upon completion of the second decomposed data access request, taking the data access request out of suspension and restarting the first data access request in order to accomplish the data access request directed to persistent storage of the computer data storage system.