Method and apparatus for resource allocation in a raid system

• US 7,254,813 B2
• Filed: 03/21/2002
• Issued: 08/07/2007
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Schoenthal, Scott, Sundaram, Rajesh, Leong, James, Doucette, Douglas P., Viswanathan, Srinivasan, Strange, Stephen H.
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): To; Jennifer N.
• Application Number:
  US10/105,079
• Publication Number:
  US 20030182503A1
• Time in Patent Office: 1,965 Days
• Field of Search: 718100-108, 718104-105, 718 4- 10, 711/114, 711/154, 711/117, 711/100, 714/7, 714/42, 710 4- 10, 707/2, 707/206, 707/207, 709/229, 370/335
• US Class Current: 718/104
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• 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

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 computer-implemented method for managing allocation of resources to I/O tasks in a RAID system, the method comprising:

generating configuration information about said RAID system;

defining a plurality of I/O tasks;

defining a plurality of resource pools;

determining for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types;

associating a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

allocating to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said respective set of resources associated with said associated respective first resource pool;

associating a second I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

scheduling said second I/O task for execution based at least in part on resources in said respective first resource pool from said plurality of resource pools not currently allocated to other I/O tasks, thereby controlling execution of said second I/O task using said respective resource pool; and

scheduling a predetermined number of additional I/O tasks for execution based at least in part on a quantity of a respective set of resources in one resource pool of said plurality of resource pools.

2. The method of claim 1 further comprising suspending said first I/O task if said requested resource is not available from said respective set of resources associated with said associated respective first resource pool.

3. The method of claim 1 wherein said set of resources comprise one or more I/O tasks.

4. The method of claim 1 wherein the step of determining further comprises defining said respective set of resources by defining a quantity and a location of each resource type for said one or more resource types.

5. The method of claim 1 further comprising selecting said respective set of resources from the group consisting of stripe locks, memory data structures, data buffers and NVRAM slots.

6. The method of claim 1 wherein the step of associating comprises:

associating with said first resource pool one or more I/O tasks associated with long-running behaviors; and

associating with a second resource pool one or more I/O tasks with time-critical behaviors.

7. The method of claim 6 wherein said long-running behaviors are selected from the group consisting of a parity verification I/O task, a mirror verification I/O task, a parity reconstruction of a RAID group and a mirror resynchronization and wherein said time-critical behaviors are selected from the group consisting of a disk read for non-degraded RAID groups and a disk write for non-degraded RAID groups.

8. The method of claim 1 wherein the step of associating further comprises associating with an error resource pool included in said plurality of resource pools one or more I/O tasks associated with error handling.

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

10. The method of claim 1 further comprising returning said requested resource to said associated respective first resource pool when said first I/O task is completed.

11. The method of claim 1 further comprising modifying said set of resources associated with said first resource pool in response to an occurrence of an event.

12. The method of claim 1 further comprising reassociating said first I/O task from said plurality of I/O tasks with a second resource pool from said plurality of resource pools in response to an occurrence of an event.

13. The method of claim 1 wherein the step of defining a plurality of I/O tasks comprises defining a plurality of I/O tasks responsive to a data access request.

14. A computer-implemented method for managing allocation of resources to I/O tasks in a RAID system, the method comprising:

generating configuration information about said RAID system;

defining a plurality of I/O tasks;

defining a plurality of resource pools;

determining for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types, and determining said respective set of resources based at least in part on a hierarchical order of said plurality of I/O tasks and a predetermined proportion of resources needed at each level of said hierarchical order;

associating a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools; and

allocating to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said respective set of resources associated with said associated respective first resource pool.

15. The method of claim 14 further comprising:

modifying said predetermined proportion of resources at a first level of said hier archical order based at least in part on an error condition at said first level; and

queuing a second I/O task for resource allocation based at least in part on said modified predetermined proportion.

16. A computer-implemented method for managing allocation of resources to I/O tasks in a RAID system, the method comprising:

generating configuration information about said RAID system;

defining a plurality of I/O tasks;

defining a plurality of resource pools;

determining for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types;

associating a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

allocating to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said respective set of resources associated with said associated respective first resource pool; and

associating said plurality of I/O tasks with a hierarchical order, and wherein the step of defining a plurality of resource pools comprises defining a plurality of resource pools, each resource pool corresponding to a level in said hierarchical order, and wherein the step of determining further comprises determining said respective set of resources based at least in part on a predetermined proportion of resources needed at each level of said hierarchical order, and wherein the step of associating comprises associating one or more I/O tasks on a same hierarchical level in said hierarchical order with a resource pool corresponding to said same hierarchical level.

17. The method of claim 16 further comprising:

modifying said predetermined proportion of resources at a first level of said hier archical order based at least in part on one of an error condition at said first level and said configuration information; and

queuing a second I/O task for resource allocation based at least in part on said modified predetermined proportion.

18. A storage system for managing allocation of resources to I/O tasks in a RAID system, said storage system comprising:

an instantiator module configured to generate configuration information about said RAID system and to define a plurality of I/O tasks; and

a resource manager configured to define a plurality of resource pools, to determine for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types, to associate a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools and to allocate to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said respective set of resources associated with said associated respective first resource pool, the resource manager further configured to associate a second I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools and scheduling said second I/O task for execution based at least in part on resources in said respective first resource pool from said plurality of resource pools not currently allocated to other I/O tasks, thereby controlling execution of said second I/O task using said respective resource pool;

the resource manager further configured to schedule a predetermined number of additional I/O tasks for execution based at least in part on a quantity of a respective set of resources in one resource pool of said plurality of resource pools; and

wherein the resource manager and instantiator module are executed using a processor within the storage system.

19. The storage system of claim 18 wherein said set of resources comprise one or more I/O tasks.

20. The storage system of claim 18 wherein the resource manager is further configured to define said set of resources by defining a quantity and a location of a resource type for one or more resource types available to said RAID system.

21. The storage system of claim 18 wherein the resource manager is further configured to select said set of resources from the group consisting of stripe locks, memory data structures, data buffers and NVRAM slots.

22. The storage system of claim 18 wherein the resource manager is further configured to associate with a first resource pool one or more I/O tasks associated with long-running behavior and to associate with a second group one or more I/O tasks with time-critical behaviors.

23. The storage system of claim 22 wherein said long-running behaviors are selected from the group consisting of a parity verification I/O task, a mirror verification I/O task, a parity reconstruction of a RAID group and a mirror resynchronization and wherein said time-critical behaviors are selected from the group consisting of a disk read for non-degraded RAID groups and a disk write for non-degraded RAID groups.

24. The storage system of claim 18 wherein the resource manager is further configured to associate with an error resource pool included in said plurality of resource pools one or more I/O tasks associated with error handling.

25. The storage system of claim 18 wherein the instantiator module is further configured to define a plurality of I/O tasks, each I/O task of the plurality of I/O tasks selected from the group consisting a volume read, a mirror write, a mirror read, a plex write, a plex read, a disk read, a disk write, a group read, an array write, a parity reconstruction of a RAID group, a stripe parity reconstruction and a mirror verification.

26. The storage system of claim 18 wherein the resource manager is further configured to return said requested resource to said associated respective first resource pool when said one I/O task is completed.

27. The storage system of claim 18 wherein the resource manager is further configured to modify said set of resources associated with said first resource pool in response to an occurrence of an event.

28. The storage system of claim 18 wherein the resource manager is further configured to reassociate said one I/O task from said plurality of I/O tasks with a second resource pool from said plurality of resource pools in response to an occurrence of an event.

29. A storage system for managing allocation of resources to I/O tasks in a RAID system, said storage system comprising:

an instantiator module configured to generate configuration information about said RAID system and to define a plurality of I/O tasks; and

a resource manager configured to define a plurality of resource pools, to determine for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types, to associate a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools and to allocate to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said respective set of resources associated with said associated respective first resource pool, and is further configured to define said plurality of I/O tasks with a hierarchical order, to define a plurality of resource pools, each resource pool corresponding to a level in said hierarchical order, and to associate one or more I/O tasks on a same hierarchical level in said hierarchical order with a resource pool corresponding to said same hierarchical level, wherein the resource manager and instantiator module are executed using a processor within the storage system.

30. An article of manufacture having computer-readable program portions embodied therein for managing allocation of resources to I/O tasks in a RAID system, said article comprising:

a computer-readable program portion for defining a plurality of I/O tasks;

a computer-readable program portion for defining a plurality of resource pools;

a computer-readable program portion for determining for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types;

a computer-readable program portion for associating a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

a computer-readable program portion for allocating to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said associated respective first resource pool;

computer-readable program portion for associating a second I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

a computer-readable program portion for scheduling said second I/O task for execution based at least in part on resources in said respective first resource pool from said plurality of resource pools not currently allocated to other I/O tasks, thereby controlling execution of said second I/O task using said respective resource pool; and

a computer-readable program portion for scheduling a predetermined number of additional I/O tasks for execution based at least in part on a quantity of a respective set of resources in one resource pool of said plurality of resource pools.

31. The article of claim 30 further comprising:

a computer-readable program portion for associating with a first resource pool one or more I/O tasks associated with long-running behavior; and

a computer-readable program portion for associating with a second resource pool one or more I/O tasks with time-critical behaviors.

32. The article of claim 30 further comprising a computer-readable program portion for associating further comprises associating with an error resource pool included in said plurality of resource pools one or more I/O tasks associated with error handling.

33. An article of manufacture having computer-readable program portions embodied therein for managing allocation of resources to I/O tasks in a RAID system, said article comprising:

a computer-readable program portion for defining a plurality of I/O tasks;

a computer-readable program portion for defining a plurality of resource pools;

a computer-readable program portion for determining for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on said configuration information and said plurality of I/O tasks, each set of resources comprising one or more resource types;

a computer-readable program portion for associating a first I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

a computer-readable program portion for allocating to said first I/O task a requested resource from said associated respective first resource pool if said requested resource is available from said associated respective first resource pool;

a computer-readable program portion for defining said plurality of I/O tasks with a hierarchical order;

a computer-readable program portion for defining a plurality of resource pools, each resource pool corresponding to a level in said hierarchical order; and

a computer-readable program portion for associating one or more I/O tasks on a same hierarchical level in said hierarchical order with a resource pool corresponding to said same hierarchical level.

34. A method, comprising:

generating configuration information about a RAID system;

defining a plurality of I/O tasks;

defining a plurality of resource pools;

determining for each resource pool a respective set of resources associated with that resource pool, the set of resources based at least in part on the configuration information and the plurality of I/O tasks, each set of resources comprising more than one resource type;

associating a first I/O task from the plurality of I/O tasks with a respective first resource pool from the plurality of resource pools;

allocating to the first I/O task a requested resource from the associated respective first resource pool if the requested resource is available from the respective set of resources associated with said associated respective first resource pool;

associating a second I/O task from said plurality of I/O tasks with a respective first resource pool from said plurality of resource pools;

scheduling said second I/O task for execution based at least in part on resources in said respective first resource pool from said plurality of resource pools not currently allocated to other I/O tasks, thereby controlling execution of said second I/O task using said respective resource pool; and

scheduling a predetermined number of additional I/O tasks for execution based at least in part on a quantity of a respective set of resources in one resource pool of said plurality of resource pools.