Granted Patent B2

US 10,255,217 · App. 14/945,309 · Granted Apr 9, 2019

Abstract

Claims (46)

1. A processor-based method for two level quality of service scheduling for latency and queue depth control in a storage system having a plurality of storage subsystems in which each storage subsystem has an associated queue and a level one scheduler provides a first level of scheduling input/output interactions with storage clients based on overall storage system capacity and a level two scheduler manages input/output flows with individual storage subsystems, comprising:

determining, by the level two scheduler, a queue depth as input/output operations per unit time that a storage subsystem can sustain, for each of a plurality of queues corresponding to each storage subsystems in the storage system;

determining, by the level one scheduler, a system capacity as total input and output operations per unit time that the storage system can sustain, based on the queue depth of each of the plurality of queues;

determining, by the level one scheduler, whether to accept or deny an input/output request for placement onto an input/output stack, based on a comparison of credits of the input/output request to the system capacity as determined on an ongoing basis;

placing, by the level two scheduler, the input/output request from the input/output stack onto one of the plurality of queues based on whether doing so maintains or exceeds the queue depth of the one of the plurality of queues;

wherein the queue depth is controlled by, the level two scheduler, by the determining the queue depth and the placing; and

wherein latency of input/output request servicing is controlled on the ongoing basis, by the determining for placement onto the input/output stack and the placing from the input/output stack with the level one scheduler regulating congestion of the input/output stack beyond the capacity of the storage system and the level two scheduler regulating oscillations in throughput.

2. The method of claim 1 , further comprising:

distributing input/output requests from the input/output stack to the plurality of queues according to latency or throughput requirements of the input/output requests.

3. The method of claim 1 , wherein the queue depth is associated with an underlying device or a storage tier of the storage system.

4. The method of claim 1 , wherein the credits of the input/output request are based on at least one of: a service level agreement of an application associated with the input/output request, a deadline of the input/output request, or a throughput requirement of the input/output request.

5. The method of claim 1 , wherein the queue depth is maintained by allowing, on the one of the plurality of queues, a total number of input/output requests less than or equal to the determined queue depth.

6. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method for two level quality of service scheduling for latency and queue depth control in a storage system having a plurality of storage subsystems in which each storage subsystem has an associated queue and a level one scheduler provides a first level of scheduling input/output interactions with storage clients based on overall storage system capacity and a level two scheduler manages input/output flows with individual storage subsystems, the method comprising:

determining by the level two scheduler, for each storage subsystem of a plurality of storage subsystems of a storage system how many input/output operations per unit time the storage subsystem can sustain, as a queue depth of the storage subsystem, wherein the queue depth is associated with a queue coupled to the storage subsystem, there being a plurality of such queues corresponding to the plurality of storage subsystems;

determining, by the level one scheduler, based on the queue depths of the plurality of storage subsystems, total input/output operations per unit time that the storage system can sustain, as system capacity of the storage system;

accepting or refusing, by the level two scheduler, to place input/output requests onto an input/output stack based on credits of each of the input/output requests in comparison to system capacity determined on an ongoing basis;

moving, by the level two scheduler, the input/output requests from the input/output stack to the plurality of queues corresponding to the plurality of storage subsystems so as to maintain the queue depth of each such queue;

controlling latency of input/output request servicing on the ongoing basis, by the accepting or refusing to place the input/output requests onto the input/output stack; and

controlling the queue depth of each of the plurality of queues, by the determining the queue depth and each decision about when, and to which queue, to perform the moving of each of the input/output requests from the input/output stack to one of the plurality of queues;

wherein the level one schedler regulates congestion of the input/output stack beyond the capacity of the storage system and the level two scheduler regulates oscillations in throughput.

7. The computer-readable media of claim 6 , wherein the method further comprises:

determining to which of the plurality of queues to move each input/output request of the input/output requests from the input/output stack based on latency or throughput requirement of the input/output request.

8. The computer-readable media of claim 6 , wherein the method further comprises:

communicating with storage stack clients via an application programming interface; and

communicating with device drivers of the plurality of storage subsystems via a further application programming interface.

9. The computer-readable media of claim 6 , wherein the method further comprises:

placing, on each queue of the plurality of queues, from the input/output stack, a total number of input/output requests less than or equal to the queue depth of the queue.

10. A storage system scheduler, comprising:

an input/output stack;

a plurality of queues, each configured to couple to one of a plurality of storage subsystems of a storage system;

one or more processors, configured to implement a level one scheduler and a level two scheduler in which the level one scheduler provides a first level of scheduling input/output interactions with storage clients based on overall storage system capacity and the level two scheduler manages input/output flows with individual storage subsystems;

the level two scheduler configured to determine, on a continuous or interval basis, queue depth for each queue of the plurality of queues, wherein the queue depth is input/output operations per unit time the one of the plurality of storage subsystems to which the queue is coupled can sustain;

the level one scheduler configured to determine, on the continuous or interval basis, system capacity of the storage system, wherein the system capacity is the total input/output operations per unit time that the storage system can sustain, based on the queue depth of each of the plurality of queues;

the level one scheduler configured to compare credits of input/output requests to the system capacity as determined on the continuous or interval basis and accept or reject input/output requests onto the input/output stack based on such comparison;

the level two scheduler configured to move the input/output requests from the input/output stack onto the plurality of queues based on maintaining the queue depth of each of the plurality of queues;

the level two scheduler configured to control the queue depth of each of the plurality of queues on a continuous or interval basis;

wherein the level one scheduler regulates congestion of the input/output stack beyond the capacity of the storage system and the level two scheduler regulates oscillations in throughput.

11. The storage system scheduler of claim 10 , further comprising:

the level two scheduler configured to distribute the input/output requests from the input/output stack to the plurality of queues based on latency or throughput requirements of the input/output requests.

12. The storage system scheduler of claim 10 , further comprising:

the level one scheduler configured to provide an application programming interface by which storage stack clients communicate to the storage system scheduler; and

the level two scheduler configured to provide an application programming interface by which device drivers managing the plurality of storage subsystems communicate to the storage system scheduler.

13. The storage system scheduler of claim 10 , further comprising:

the one or more processors further configured to implement a storage discovery application programming interface by which storage characteristics of each storage subsystem discovered are communicated to the storage system scheduler.

14. The storage system scheduler of claim 10 , further comprising:

the level two scheduler configured to determine whether placing one of the input/output requests from the input/output stack onto one of the plurality of queues exceeds the determined queue depth of the one of the plurality of queues and place the one of the input/output requests from the input/output stack onto the one of the plurality of queues responsive to a determination that this does not exceed the determined queue depth of the one of the plurality of queues.

Assignments (16)

Cited By (1)

US 12,254,346