Method and apparatus for runtime resource deadlock avoidance in a raid system

• US 7,437,727 B2
• Filed: 03/21/2002
• Issued: 10/14/2008
• Est. Priority Date: 03/21/2002
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Sundaram, Rajesh, Leong, James, Doucette, Douglas P., Viswanathan, Srinivasan, Strange, Stephen H.
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): To; Jennifer N
• Application Number:
  US10/105,039
• Publication Number:
  US 20030182348A1
• Time in Patent Office: 2,399 Days
• Field of Search: 714/7, 714/41, 714/766, 711111-150, 711/170, 713/201, 713/1, 718100-108, 709219-226, 703/27, 710 5- 6, 710/24, 707/101, 707/8, 719/310
• US Class Current: 718/104
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

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 accessing data on a storage system comprising:

defining a data access request in terms of a plurality lower level I/O tasks, the lower level I/O tasks each performing an operation used in servicing the data access request, wherein each I/O task of the plurality of lower level I/O tasks is an asynchronous I/O task that is scheduled independently from other I/O tasks of the plurality of lower level I/O tasks;

assigning resources dynamically to a first I/O task, wherein the resources are organized in a hierarchical order;

executing the first I/O task of the data access request while preventing execution of I/O tasks with resources higher in the hierarchical other than the resources assigned to the first I/O task; and

executing a second I/O task, wherein the second I/O task is assigned a resource lower in the hierarchical order than the resources assigned to the first I/O task while the first I/O task is pending.

2. The method of claim 1 wherein the resource is selected from the group consisting of a lock, a memory data structure, a data buffer and a non-volatile memory.

3. The method of claim 1 wherein each I/O task of the plurality of I/O tasks is selected from a group consisting of a volume read, a volume write, a mirror read, a mirror write, a mirror read error, a plex read, a RAID group read, an array read, an array write, a disk read, a disk write, a stripe read, a stripe write, a parity reconstruction of a RAID group, a stripe parity reconstruction and a mirror verification.

4. The method of claim 1 wherein the first I/O task is a parent I/O task that uses one or more child I/O tasks, each child I/O task performing a portion of the parent I/O task.

5. A method for accessing data on a storage system comprising:

dividing a data access request into a plurality of lower level I/O tasks, each I/O task of the plurality of lower level I/O tasks performing a portion of the data access request, each I/O task being an asynchronous I/O task that is independently scheduled from other I/O tasks, each I/O task using resources of the storage system;

establishing a hierarchical order for the resources, the order configured to avoid deadlock of the resources of the storage system;

performing the lower I/O tasks according to the hierarchical order of the resources to service the data access request, wherein the resources higher in the hierarchical order are not allocated to a second I/O task while the resources are allocated to a first I/O task; and

performing the second I/O task, wherein the second I/O task is assigned a resource lower in the hierarchical order than the resources assigned to the first I/O task while the first I/O task is pending.

6. A storage system having a processor comprising:

an instantiator module executed by the processor, the instantriator module configured to define a data access request in terms of a plurality lower level I/O tasks, the lower level I/O tasks each performing an operation used in servicing the data access request, wherein each I/O task of the plurality of lower level I/O tasks in an asynchronous I/O task that is scheduled independently from other I/O tasks of the plurality of lower level I/O tasks; and

a resource manager configured to arrange the resources in a hierarchical order, and to allocate a first resource to a first I/O task of the data access request, and prevent allocation request of I/O tasks with resources higher in the hierarchical order than the first I/O task while the first I/O task is pending, wherein the resource manager is further configured to permit allocation of a second resource to a second I/O task, wherein the second resource is lower in the hierarchical order than the first resource while the first I/O task is pending.

7. The storage system 6 wherein the resource is selected from the group consisting of a lock, a memory data structure, a data buffer and a non-volatile memory.

8. The storage system 6 wherein the resource is selected from the group consisting of a lock, a memory data structure, a data buffer and a non-volatile memory.

9. A storage system having a processor comprising:

an instantiator module executed by the processor, the instantiator module configured to divide a data access request into a plurality of lower level I/O tasks, each I/O task of the plurality of lower level I/O tasks performing a portion of the data access request, each I/O task being an asynchronous I/O task that is independently scheduled from other I/O tasks, each I/O task using resources of the storage system; and

a resource manager configured to establish a hierarchical order for the resources, the order configured to avoid deadlock of the resources of the storage system, perform the lower I/O tasks according to the hierarchical order of the resources to service the data access request, wherein the resources higher in the hierarchical order are not allocated to a second I/O task while the resources are allocated to a first I/O task, wherein the resource manager is further configured to permit allocation of a second resource to the second I/O task, wherein the second resource is lower in the hierarchical order than a first resource while the first I/O task is pending.

10. A storage system having a processor comprising:

means for defining a data access request in terms of a plurality lower level I/O tasks, the plurality of lower level I/O tasks each performing an operation used in servicing the data access request, wherein each I/O task of the plurality of lower level I/O tasks is an asynchronous I/O task that is scheduled independently from other I/O tasks of the plurality of lower level I/O tasks;

means for allocating a first I/O task of the data access request;

means for assigning resources dynamically to the first I/O task, wherein the resources are organized in a hierarchical order;

means for preventing allocation of I/O tasks with resources higher in the hierarchical order than the resources assigned to the first I/O task while the first I/O task is pending; and

means for executing a second I/O task, wherein the second I/O task is assigned a resource lower in the hierarchical order than the resources assigned to the first I/O task while the first I/O task is pending.

11. A storage system having a processor comprising:

means for dividing a data access request into a plurality of lower level I/O tasks, each I/O task of the plurality of lower level I/O tasks performing a portion of the data access request, each I/O task being an asynchronous I/O task that is independently scheduled from other I/O tasks, each I/O task using resources of the storage system;

means for establishing a hierarchical order for the resources, the order configured to avoid deadlock of the resources of the storage system; and

means for performing the lower level I/O tasks according to the hierarchical order of resources to service the data access request, wherein the resources higher in the hierarchical order are not allocated to a second I/O tasks while the resources are allocated to a first I/O task, wherein means for performing further performing the second I/O task, wherein the second I/O task is assigned a resource lower in the hierarchical order than the resources assigned to the first I/O task while the first I/O task is pending.

12. A computer readable medium containing executable program instructions for accessing data on a storage system, the executable program instruction comprising program instructions when executed by a processor to:

define a data access request in terms of a plurality of lower level I/O tasks, the lower level I/O tasks each performing an operation used in servicing the data access request, wherein each I/O task of the plurality of lower level tasks is an synchronous I/O task that is scheduled independently from other I/O tasks of the plurality of lower level I/O tasks;

allocate a first I/O tasks of the data access request;

assign resources dynamically to the first I/O task, wherein the resources are organized in a hierarchical order;

prevent allocation of I/O tasks with resources higher in the hierarchical order than the resources assigned to the first I/O task while said first I/O task is pending; and

perform a second I/O task, wherein the second I/O task is assigned a resource lower in the hierarchical order than the resources assigned to the first I/O task while the first I/O task is pending.

13. A method for accessing data on a storage system comprising:

defining a data access request in terms of a plurality lower level I/O tasks, the lower level I/O tasks each performing an operation used in servicing the data access request, wherein each I/O task of the plurality of lower level tasks is an asynchronous I/O task that is scheduled independently from other I/O tasks of the plurality of lower level I/O tasks;

assigning resources dynamically to a first I/O tasks, wherein the resources are organized in a hierarchical order;

executing the first I/O task of the data access request while preventing execution of a second I/O task of the plurality of I/O tasks, if a resource assigned to the second I/O task is higher in the hierarchical order than the resources assigned to the first I/O task; and

executing a third I/O task of the plurality of lower level I/O tasks, where a third resource assigned to the third I/O task is lower in the hierarchical order then the resources assigned to the first I/O task while suspending the first I/O task until the third I/O task is complete.

14. The storage system of claim 13, wherein the resource is selected from the group consisting of a lock, a data structure, a data buffer and a non-volatile memory.

15. The method of claim 13, wherein each I/O task of the plurality of I/O tasks is selected from a group consisting of a volume read, a volume write, a mirror read, a mirror write, a mirror read error, a plex read, a RAID group read, an array read, an array write, a disk read, a disk write, a stripe write, a parity reconstruction of a RAID group, a stripe parity reconstruction and a mirror verification.

16. The method of claim 13, wherein the resources further comprise the plurality of lower level I/O tasks and the lower level I/O tasks have a hierarchical order of that comprises, from highest level to lowest level a volume read, a volume write, a mirror read, a mirror write, a mirror read error, a plex read, a RAID group read, an array read, an array write, a disk read, a disk write, a stripe read, a stripe write, a parity reconstruction of a RAID group, a stripe parity reconstruction and a mirror verification.

17. A method for accessing data on a storage system, comprising:

dividing a data access request into a plurality of lower level I/O tasks, each I/O task of the lower level I/O tasks performing a portion of the data access request, each I/O task of the lower level I/O tasks being an asynchronous I/O task that is independently scheduled from other I/O tasks, each I/O task of the lower level I/O tasks using resources of the storage system;

establishing a hierarchical order for the resources, the order configured to avoid deadlock of the resources of the storage system;

performing a first I/O task of the plurality of lower level I/O tasks having a first resource lower in the hierarchical order than a second I/O task of the plurality of lower level I/O tasks assigned a second resource while preventing execution of the second I/O task with the second resource higher in the hierarchical order then the first resource; and

performing a third I/O task of the plurality of lower level I/O tasks, where a third resource assigned to the third I/O task is lower in the hierarchical order then the resources assigned to the first I/O task while suspending the first I/O task until the third I/O task is complete.

18. The storage system of claim 17 wherein each resource is a lock, a memory data structure, a data buffer, or a non-volatile memory.

19. The method of claim 17, wherein each I/O task of the plurality of I/o tasks is a volume read, a volume write, a mirror read, a mirror write, a mirror read error, a plex read, a RAID group read, an array read, an array write, a disk read, a disk write, a stripe read, a stripe write, a parity reconstruction of a RAID group, a stripe parity reconstruction, or a mirror verification.