Scheduling data relocation activities using configurable fairness criteria

• US 8,327,103 B1
• Filed: 06/28/2010
• Issued: 12/04/2012
• Est. Priority Date: 06/28/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Chen, Xiangping, Can, Khang, Chaudhary, Monica, Jiang, Kevin Bangyen, Tao, Qin, Ku, Mark
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US12/824,380
• Time in Patent Office: 890 Days
• Field of Search: 711/165, 710/39
• US Class Current: 711/165
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0649 Lifecycle management
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

A storage processor of a data storage system includes a data relocation task scheduler that provides system limit control on the execution of data relocation requests. The data relocation task scheduler also provides fairness and concurrency limit enforcement by scheduling relocation requests from different provisioning domains, such as storage pools, in a fair manner. For example, the data relocation task scheduler includes stackable sets of pending task queues that store incoming data relocation requests. The data relocation task scheduler applies an iteration scheme to remove data relocation requests from the pending task queues thereby providing scheduling fairness among the queues and among the different provisioning domains within the data storage system. The data relocation task scheduler is configured to receive updated policies that control both system-wide data relocation resource consumption and scheduling fairness among the queues during operation and dynamically adjust current policies with the updated policies.

Claims

1. A method for scheduling a data relocation activity in a data storage system, comprising:

retrieving, by a storage processor, a data relocation request from a selected pending task queue of a set of pending task queues, each pending task queue of the set of pending task queues having an associated, distinct grouping property and each pending task queue of the set of pending task queues having a set of assigned data relocation requests, the grouping property of each particular pending task queue corresponding to a data relocation request grouping property of each data relocation request assigned to that particular pending task queue;

applying, by the storage processor, an acceptance threshold to the data relocation request, the acceptance threshold defining a limit to the data relocation requests processed by the storage processor; and

when the data relocation request meets the acceptance threshold, forwarding, by the storage processor, the data relocation request to an ongoing task queue for execution of the data relocation request, otherwise maintaining the data relocation request in the selected pending task queue of the set of pending task queues.

2. The method of claim 1, wherein:

applying the acceptance threshold to the data relocation request comprises comparing, by the storage processor, a total number of data relocation requests in the ongoing task queue to the acceptance threshold; and

when the total number of data relocation requests falls below the acceptance threshold, forwarding, by the storage processor, the data relocation request to the ongoing task queue for execution of the data relocation request otherwise maintaining the data relocation request in the selected pending task queue of the set of pending task queues.

3. The method of claim 1, wherein:

applying the acceptance threshold to the data relocation request comprises detecting, by the storage processor, a total number of data relocation requests in the ongoing task queue having a grouping property corresponding to the grouping property of the retrieved data relocation request and comparing, by the storage processor, the total number of data relocation requests in the ongoing task queue having the grouping property corresponding to the grouping property of the retrieved data relocation request to the acceptance threshold; and

when the total number of data relocation requests in the ongoing task queue having a grouping property corresponding to the grouping property of the retrieved data relocation request falls below the acceptance threshold, forwarding, by the storage processor, the data relocation request to the ongoing task queue for execution of the data relocation request otherwise maintaining the data relocation request in the selected pending task queue of the set of pending task queues.

4. The method of claim 1, comprising:

receiving, by the storage processor, a modified acceptance threshold, the modified acceptance threshold defining a limit on data relocation requests processed by the storage processor distinct from the limit on data relocation requests processed by the storage processor defined by the acceptance threshold; and

applying, by the storage processor, the modified acceptance threshold to the data relocation request.

5. The method of claim 1, comprising:

receiving, by the storage processor, a data relocation request from a client device;

comparing, by the storage processor, a data relocation request grouping property associated with the received data relocation request with the distinct grouping property of each pending task queue of the set of pending task queues; and

when detecting a correspondence between the data relocation request grouping property associated with the received data relocation request and a distinct grouping property of a particular pending task queue of the set of pending task queues, allocating, by the storage processor, the received data relocation request to the particular pending task queue of the set of pending task queues, otherwise creating, by the storage processor, a pending task queue associated with the data relocation request grouping property associated with the received data relocation request and allocating the data relocation request to the created pending task queue of the set of task queues.

6. The method of claim 1, comprising iteratively retrieving, by the storage processor and for each pending task queue of the set of pending task queues, a data relocation request and applying the acceptance threshold to the data relocation request.

7. The method of claim 6, wherein retrieving, for each pending task queue of the set of pending task queues, the data relocation request and applying the acceptance threshold to the data relocation request comprises retrieving, by the storage processor and for each pending task queue of the set of pending task queues, the data relocation request and applying the acceptance threshold to the data relocation request according to an iteration scheme.

8. The method of claim 1, wherein forwarding the data relocation request to the ongoing task queue for execution of the data relocation request comprises:

selecting, by the storage processor, a data relocation request from the ongoing task queue; and

removing, by the storage processor, the data relocation request from the ongoing task queue in response to a completion criterion.

9. The method of claim 8, comprising, in response to removing the data relocation request from the ongoing task queue, iteratively retrieving, by the storage processor, a data relocation request from each pending task queue of the set of pending task queues, and applying the acceptance threshold to the data relocation request.

10. The method of claim 1, comprising:

receiving, by the storage processor, a modified grouping property, the modified grouping property defining a partitioning of the received data relocation request into the pending task queues, the modified grouping property being distinct from the grouping property associated with each pending task queue of the set of pending task queues; and

applying, by the storage processor, the modified grouping property to a received data relocation request.

11. The method of claim 1, comprising:

receiving, by the storage processor, a modified iteration scheme instruction, the modified iteration scheme instruction defining a retrieval scheme for the data relocation requests from the pending task queues, the modified iteration scheme instruction being distinct from an iteration scheme associated with each pending task queue of the set of pending task queues; and

iteratively retrieving, by the storage processor and for each pending task queue of the set of pending task queues, a data relocation request according to the modified iteration scheme instruction.

12. An apparatus, comprising:

at least one communications interface; and

a controller electrically coupled to the at least one communications interface wherein the controller is configured to;

retrieve a data relocation request from a selected pending task queue of a set of pending task queues, each pending task queue of the set of pending task queues having an associated, distinct grouping property and each pending task queue of the set of pending task queues having a set of assigned data relocation requests, the grouping property of each particular pending task queue corresponding to a data relocation request grouping property of each data relocation request assigned to that particular pending task queue;

apply an acceptance threshold to the data relocation request, the acceptance threshold defining a limit to the data relocation requests processed by the storage processor; and

when the data relocation request meets the acceptance threshold, forward the data relocation request to an ongoing task queue for execution of the data relocation request, otherwise maintain the data relocation request in the selected pending task queue of the set of pending task queues.

13. The apparatus of claim 12, wherein:

when applying the acceptance threshold to the data relocation request, the controller is configured to compare a total number of data relocation requests in the ongoing task queue to the acceptance threshold; and

when the total number of data relocation requests falls below the acceptance threshold, the controller is configured to forward the data relocation request to the ongoing task queue for execution of the data relocation request, otherwise maintain the data relocation request in the selected pending task queue of the set of pending task queues.

14. The apparatus of claim 12, wherein:

when applying the acceptance threshold to the data relocation request, the controller is configured to detect a total number of data relocation requests in the ongoing task queue having a grouping property corresponding to the grouping property of the retrieved data relocation request and to compare the total number of data relocation requests in the ongoing task queue having the grouping property corresponding to the grouping property of the retrieved data relocation request to the acceptance threshold; and

when the total number of data relocation requests in the ongoing task queue having a grouping property corresponding to the grouping property of the retrieved data relocation request falls below the acceptance threshold, the controller is configured to forward the data relocation request to the ongoing task queue for execution of the data relocation request, otherwise maintain the data relocation request in the selected pending task queue of the set of pending task queues.

15. The apparatus of claim 12, wherein the controller is configured to:

receive a modified acceptance threshold, the modified acceptance threshold defining a limit on of data relocation requests processed by the storage processor distinct from the limit on the data relocation requests processed by the storage processor defined by the acceptance threshold; and

apply the modified acceptance threshold to the data relocation request.

16. The apparatus of claim 12, wherein the controller is configured to:

receive a data relocation request from a client device;

compare a data relocation request grouping property associated with the received data relocation request with the distinct grouping property of each pending task queue of the set of pending task queues; and

when detecting a correspondence between the data relocation request grouping property associated with the received data relocation request and a distinct grouping property of a particular pending task queue of the set of pending task queues, the controller is configured to allocate the received data relocation request to the particular pending task queue of the set of pending task queues, otherwise create a pending task queue associated with the data relocation request grouping property associated with the received data relocation request and allocating the data relocation request to the created pending task queue of the set of task queues.

17. The apparatus of claim 12, wherein the controller is configured to iteratively retrieve, for each pending task queue of the set of pending task queues, a data relocation request and applying the acceptance threshold to the data relocation request.

18. The apparatus of claim 17, wherein when retrieving, for each pending task queue of the set of pending task queues, the data relocation request and applying the acceptance threshold to the data relocation request, the controller is configured to retrieve, for each pending task queue of the set of pending task queues, the data relocation request and applying the acceptance threshold to the data relocation request according to an iteration scheme.

19. The apparatus of claim 12, wherein when forwarding the data relocation request to the ongoing task queue for execution of the data relocation request, the controller is configured to:

select a data relocation request from the ongoing task queue; and

remove the data relocation request from the ongoing task queue in response to a completion criterion.

20. The method of claim 19, wherein in response to removing the data relocation request from the ongoing task queue the controller is configured to iteratively retrieve a data relocation request from each pending task queue of the set of pending task queues, and applying the acceptance threshold to the data relocation request.

21. A computer program product having a non-transitory computer-readable storage medium including computer program logic encoded thereon that, when performed on a controller of an apparatus, causes the apparatus to:

retrieve a data relocation request from a selected pending task queue of a set of pending task queues, each pending task queue of the set of pending task queues having an associated, distinct grouping property and each pending task queue of the set of pending task queues having a set of assigned data relocation requests, the grouping property of each particular pending task queue corresponding to a data relocation request grouping property of each data relocation request assigned to that particular pending task queue;

apply an acceptance threshold to the data relocation request, the acceptance threshold defining a limit to the data relocation requests processed by the storage processor; and

when the data relocation request meets the acceptance threshold, forward the data relocation request to an ongoing task queue for execution of the data relocation request, otherwise maintain the data relocation request in the selected pending task queue of the set of pending task queues.