DRR-based two stages IO scheduling algorithm for storage system with dynamic bandwidth regulation

Patent metadata

Field	Value
Publication number	US-11403143-B2
Application number	US-202017112618-A
Country	US
Kind code	B2
Filing date	Dec 4, 2020
Priority date	Dec 4, 2020
Publication date	Aug 2, 2022
Grant date	Aug 2, 2022

Abstract

An efficient scheduling of IOs in a computing system using dynamic bandwidth regulation includes building up a shared regulator to limit the total IOPS scheduling among all IO classes at any given time. Reserved regulators may be used to place limits on the IOPS scheduled for a particular IO class at any given time. An outstanding IO window may also limit the overall number of outstanding IOs, and/or the bytes of outstanding IOs at any particular time. A first stage of IO scheduling may involve enforcing the reserved regulators to limit the IOPS scheduled for particular IO classes. A second stage of IO scheduling may involve enforcing the shared regulator to limit the total IOPS scheduled for all IO classes.

First claim

What is claimed is:

1. A method of scheduling tasks in a distributed computing system, the method comprising:
determining whether a first input/output class is active and has available tasks, wherein the first input/output class corresponds to a type of inputs/outputs received within the distributed computing system;
after determining that the first input/output class is active and has available tasks, updating a first deficit value of the first input/output class based on a deficit quantum value;
after updating the first deficit value based on the deficit quantum value, determining whether the first deficit value of the first input/output class meets a threshold to dispatch a first task in a first queue of inputs/outputs corresponding to the first input/output class;
determining whether an outstanding limit on inputs/outputs has been reached;
determining whether an amount of bandwidth remaining in a reserved regulator corresponding to the first class meets a threshold amount of bandwidth required to dispatch the first task; and
in accordance with a determination that the first deficit value meets the threshold value required to dispatch the first task in the first queue of inputs/outputs corresponding to the first input/output class, that the outstanding limit on inputs/outputs has not been reached, and that the amount of bandwidth remaining in the reserved regulator corresponding to the first class meets a threshold amount of bandwidth required to dispatch the first task, dispatching the first task.

2. The method of claim 1 , further comprising:
after dispatching the first task, determining whether a first input/output class is active and has available tasks;
after determining that the first input/output class is active and has available tasks, updating the first deficit value of the first input/output class based on a second deficit quantum value;
after updating the first deficit value based on the second deficit quantum value, determining whether the first deficit value of the first input/output class meets a threshold value required to dispatch a second task in the first queue of inputs/outputs corresponding to the first input/output class;
determining whether an outstanding limit on inputs/outputs has been reached;
determining whether an amount of bandwidth remaining in a shared regulator meets a threshold amount of bandwidth required to dispatch the second task; and
in accordance with a determination that the first deficit value meets the threshold value required to dispatch the second task in the first queue of inputs/outputs corresponding to the first input/output class, that the outstanding limit on inputs/outputs has not been reached, and that the amount of bandwidth remaining in the shared regulator meets a threshold amount of bandwidth required to dispatch the second task, dispatching the second task.

3. The method of claim 1 , further comprising:
after dispatching the first task:
decrementing the first deficit value based on the value required to dispatch the first task; and
recording a value corresponding to the resources required to dispatch the first task in a shared regulator.

4. The method of claim 3 , further comprising:
after dispatching the first task, determining that the first input/output class is active and has available tasks;
after determining that the first input/output class is active and has available tasks and recording the value corresponding to the resources required to dispatch the first task in the shared regulator:
determining whether the first deficit value meets a threshold value required to dispatch a second task in the first queue of inputs/outputs corresponding to the first input/output class;
determining whether the outstanding limit on inputs/outputs has been reached; and
determining whether the amount of bandwidth remaining in the reserved regulator corresponding to the first class meets a threshold amount of bandwidth required to dispatch the second task;
in accordance with a determination that the first deficit value meets the threshold value required to dispatch the second task in the first queue of inputs/outputs corresponding to the first input/output class, that the outstanding limit on inputs/outputs has not been reached, and that the amount of bandwidth remaining in the reserved regulator corresponding to the first class meets a threshold amount of bandwidth required to dispatch the first task, dispatching the second task.

5. The method of claim 4 , further comprising:
while the first input/output class is active and has available tasks, the outstanding limit on inputs/outputs has not been reached, the amount of bandwidth remaining in the reserved regulator corresponding to subsequent tasks meets a threshold amount of bandwidth required to dispatch subsequent tasks, and the first deficit value of the first input/output class meets a threshold value required to dispatch subsequent tasks of the first input/output class:
continuing to dispatch subsequent tasks corresponding to the first input/output class.

6. The method of claim 3 , wherein the bandwidth in the reserved regulator corresponding to the first class is proportional to a share of the first input/output class relative to a plurality of input/output classes and a total number of resources of the shared regulator.

7. The method of claim 1 , further comprising:
in accordance with a determination that there is not sufficient bandwidth remaining in the reserved regulator corresponding to the first class to dispatch the first task, marking the first input/output class as inactive; and
determining whether a second input/output class is active and has available tasks;
after determining that the second input/output class is active and has available tasks, updating a second deficit value of the second input/output class based on a second deficit quantum value;
after updating the second deficit value based on the second deficit quantum value, determining whether the second deficit value meets a threshold value required to dispatch a second task in a second queue of inputs/outputs corresponding to the second input/output class;
determining whether an outstanding limit on inputs/outputs has been reached;
determining whether an amount of bandwidth remaining in a reserved regulator corresponding to the second class meets a threshold amount of bandwidth required to dispatch the second task; and
in accordance with a determination that the second deficit value meets the threshold value required to dispatch the second task in the second queue of inputs/outputs corresponding to the second input/output class, that the outstanding limit on inputs/outputs has not been reached, and that the amount of bandwidth remaining in the reserved regulator corresponding to the second class meets a threshold amount of bandwidth required to dispatch the second task, dispatching the second task.

8. The method of claim 1 , wherein determining that the first input/output class is active and has available tasks comprises:
determining whether a plurality of input/output classes includes any active input/output classes;
in accordance with a determination that the plurality of input/output classes includes at least a first input/output class that is active, determining a queue index of the first input/output class; and
after determining the queue index of the first input/output class, determining whether the queue of inputs/outputs corresponding to the first input/output class is empty.

9. The method of claim 1 , further comprising:
in accordance with a determination that the plurality of input/output classes does not include any active input/output classes, foregoing scheduling additional tasks in the distributed computing sys

Assignees

• Vmware Inc

Inventors

• Xiang Enning
• Knauft Eric Shannon
• Renauld Pascal
• Xu Yiqi

Classifications

• G06F2209/5014

  Reservation · CPC title

• G06F9/5011

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/5038 Primary

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06F9/4856

  resumption being on a different machine, e.g. task migration, virtual machine migration (G06F9/5088 takes precedence) · CPC title