Method and apparatus for decomposing I/O tasks in a raid system

• US 7,539,991 B2
• Filed: 03/21/2002
• Issued: 05/26/2009
• Est. Priority Date: 03/21/2002
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Schoenthal, Scott, Sundaram, Rajesh, Leong, James, Doucette, Douglas P., Viswanathan, Srinivasan, Strange, Stephen H.
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): WU, QING YUAN
• Application Number:
  US10/105,078
• Publication Number:
  US 20030182349A1
• Time in Patent Office: 2,623 Days
• Field of Search: 395/441, 714/42, 714/6, 711/114, 711/100, 719/325, 710/1, 717/6, 718102-104
• 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

The present invention implements an I/O task architecture in which an I/O task requested by the storage manager, for example a stripe write, is decomposed into a number of lower-level asynchronous I/O tasks that can be scheduled independently. Resources needed by these lower-level I/O tasks are dynamically assigned, on an as-needed basis, to balance the load and use resources efficiently, achieving higher scalability. A hierarchical order is assigned to the I/O tasks to ensure that there is a forward progression of the higher-level I/O task and to ensure that resources do not become deadlocked.

Claims

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

representing logical combination and configuration of physical storage components of said RAID 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;

dynamically allocating a resource for a child I/O task;

generating said 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, said child I/O task using the resources;

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

scheduling for execution said child I/O task by an I/O thread;

suspending the child I/O task by the I/O thread if the resource is not available;

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

deallocating said resources allocated to said child I/O task when the child I/O task is completed;

resuming the parent I/O task upon an event indicating the completion of said child I/O task, said event indicating the completion occurred when a function vector is invoked by said child I/O task.

2. The method of claim 1 wherein the scheduling further comprises:

scheduling for execution said child I/O task in response to an occurrence of said event such that no synchronization points are required between said parent I/O task and said child I/O task.

3. The method of claim 1 further comprising:

queuing said parent I/O task and said child I/O task on separate I/O threads.

4. The method of claim 1 further comprising:

queuing said parent I/O task and said child I/O task on separate computing devices.

5. The method of claim 1 further comprising:

queuing said parent I/O task and said child I/O task to separate processes.

6. The method of claim 1, further comprises:

scheduling said parent I/O task for execution in response to a second event; and

generating said child I/O task in response to execution of said parent I/O task.

7. The method of claim 1 further comprising:

queuing said parent and said child I/O tasks to an I/O thread, wherein said parent and child I/O tasks are independently schedulable entities.

8. The method of claim 1 wherein the step of suspending the child I/O task further comprises:

moving said child I/O task from an I/O thread to a wait queue.

9. The method of claim 8 wherein the step of suspending further comprises:

moving said child I/O task from an I/O thread to a wait queue.

10. The method of claim 1 wherein said child I/O task has no dependency on said first object, said first object being at a higher level in said hierarchical set than said second object.

11. The method of claim 1 further comprising:

generating, by said parent I/O task, an error-handling I/O task when said child I/O task encounters an error.

12. The method of claim 1 further comprising:

defining said parent and child I/O tasks having a standard interface.

13. The method of claim 1 further comprising:

defining said child I/O task including a start operation and a finish operation.

14. The method of claim 1 further comprising:

defining said parent I/O task including a start operation, a finish operation and a child-I/O-task-finished operation.

15. The method of claim 1 wherein said child I/O task is a bypass I/O task.

16. The method of claim 1 wherein said child I/O task is a first child I/O task, the method further comprising:

generating a second child I/O task to implement at least a portion of said parent I/O task; and

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

17. The method of claim 16 further comprising:

completing said parent I/O task upon completion of said first child I/O task and said second I/O task.

18. The method of claim 1 wherein said event is one of a disk I/O completion, a RAID group I/O completion, mirror I/O completion, plex I/O completion volume I/O completion or a request from a RAID client.

19. 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 completion of execution of said grandchild I/O task.

20. The method of claim 1 wherein each I/O task is one of a disk read, a disk write, a volume write, a volume read, a mirror write, a mirror read, a plex write, a plex read, a group read, an array write, a parity reconstruction of a RAID group, a stripe parity reconstruction or a mirror verification.

21. The method of claim 1, further comprising:

defining a plurality of states for each of the parent I/O task, the child I/O task, and a grandchild I/O task, and changing a state of the plurality of states from a first state to a second state, wherein said first and said second states are one of a perform I/O task state, a child I/O task pending state, an X0R task pending state, an I/O task finished state and an I/O task suspended state.

22. A storage system for decomposing a data access request into a plurality of lower-level I/O tasks in a RAID system, said storage system comprising:

a memory;

a network adapter;

an instantiator module stored in the memory configured to provide a hierarchical set of objects representing logical combination and configuration of physical storage components of said RAID system, to generate a parent I/O task from a first object in said hierarchical set of objects in response to said data access request received at the network adapter, to dynamically allocate a resource to a child I/O task, and to generate said 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, said child I/O task using the resources; and

an I/O manager stored in the memory configured to receive said parent and child I/O tasks and to schedule execution of said parent I/O tasks, to suspend the parent I/O task until said child I/O task is completed, to schedule for execution said child I/O task by an I/O thread, to suspend the child I/O task by the I/O thread if the resource is not available, to resume the parent I/O task upon an event indicating the completion of said child I/O task, said event indicating the completion occurring when a function vector is invoked by said child I/O task, to deallocate said resource allocated to said child I/O task when said child I/O task is completed, and to perform said data access request to accomplish an I/O data access to the RAID system of the storage system.

23. The storage system of claim 22 further comprising:

said I/O manager further configured to suspend processing of said child I/O task if said resource is not available.

24. The storage system of claim 22 further comprising:

said child I/O task configured to indicate its completion to said parent I/O task when said child I/O task is complete.

25. The storage system of claim 22 further comprising:

said instantiator module further configured to generate, from a call to said first object, an error-handling I/O task when said child I/O task encounters an error.

26. The storage system of claim 22 further comprising:

a first standard interface for said parent I/O task and a second standard interface for said child task.

27. The storage system of claim 22 further comprising:

a start operation and a finish operation for said child I/O task.

28. The storage system of claim 22 further comprising:

a start operation, a finish operation, and a child-I/O-task-finished operation for said parent I/O task.

29. The storage system of claim 22 further comprising:

said instantiator module further configured to instantiate a bypass I/O task.

30. The storage system of claim 22 wherein each I/O task is one of a disk read, a disk write, a volume write, a volume read, a mirror write, a minor read, a plex write, a plex read, a group read, an array write, a parity reconstruction of a RAID group, a stripe parity reconstruction and a minor verification.

31. A computer readable medium having stored thereon computer-readable instructions for execution on a processor to perform a method of decomposing a data access request into a plurality of lower-level I/O tasks in a RAID system, said method comprising the steps of:

representing logical combination and configuration of physical storage components of said RAID 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;

dynamically allocating a resource for a child I/O task;

generating said 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, said child I/O task using the resources;

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

scheduling for execution said child I/O task by an I/O thread;

suspending the child I/O task by the I/O thread if the resource is not available;

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

deallocating said resources allocated to said child I/O task when the child I/O task is completed;

resuming the parent I/O task upon an event indicating the completion of said child I/O task, said event indicating the completion occurred when a function vector is invoked by said child I/O task.