System resource utilization balancing in a storage system

• US 10,353,743 B1
• Filed: 04/30/2018
• Issued: 07/16/2019
• Est. Priority Date: 09/07/2016
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Frandzel, Yuval, Vijayasankar, Kiron
• Primary Examiner(s): Phan, Raymond N
• Application Number:
  US15/967,040
• Time in Patent Office: 442 Days
• Field of Search: 710 36- 44
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 13/1642 with request queuing
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/5038 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 Class Codes: G06F 9/505 considering the load

Abstract

Ensuring the fair utilization of system resources using workload based, time-independent scheduling, including: receiving an I/O request associated with an entity; determining whether an amount of system resources required to service the I/O request is greater than an amount of available system resources in a storage system; responsive to determining that the amount of system resources required to service the I/O request is greater than the amount of available system resources in the storage system: queueing the I/O request in an entity-specific queue for the entity; detecting that additional system resources in the storage system have become available; and responsive to detecting that additional system resources in the storage system have become available, issuing an I/O request from an entity-specific queue for an entity that has a highest priority among entities with non-empty entity-specific queues.

Claims

1. A method of system resource utilization balancing in a storage system, the method comprising:

determining whether an amount of system resources required to service the I/O request is greater than an amount of available system resources in a storage system, wherein the I/O request is associated with an entity;

responsive to determining that the amount of system resources required to service the I/O request is greater than the amount of available system resources in the storage system;

queueing the I/O request in an entity-specific queue for the entity;

detecting that additional system resources in the storage system have become available; and

responsive to detecting that additional system resources in the storage system have become available, issuing an I/O request from an entity-specific queue for an entity that has a highest priority among entities with non-empty entity-specific queues, wherein a priority for each entity that utilizes the storage system is determined based on the amount of I/O requests associated with the entity in a time-independent period.

2. The method of claim 1 wherein the time-independent period includes an amount of most recently processed I/O requests that is equal to a multiple of the amount of I/O requests that may be processed by the storage system in parallel.

3. The method of claim 1 wherein the time-independent period is determined by determining an amount of I/O requests that may be processed by the storage system in parallel while adhering to a response time requirement.

4. The method of claim 1 further comprising:

determining a priority for each entity with a non-empty entity-specific queue, including;

determining, in dependence upon the amount of I/O requests that may be processed by the storage system in parallel, a fair share of system resources for each entity;

assigning priorities to each entity with a non-empty entity-specific queue in dependence upon the amount I/O requests processed for each entity during the time-independent period in excess of the fair share of system resources for each entity.

5. The method of claim 1 further comprising:

determining, in dependence upon the amount of I/O requests that may be processed by the storage system in parallel, a fair share of system resources for each entity;

tracking, for each entity, the amount I/O requests processed for each entity during the time-independent period; and

crediting a resource utilization balance for each entity with the fair share of system resources for each entity upon the expiration of the time-independent period.

6. The method of claim 1 further comprising:

determining the amount of system resources required to service the I/O request; and

determining the amount of available system resources in the storage system.

7. The method of claim 1 further comprising, responsive to determining that the amount of system resources required to service the I/O request is not greater than the amount of available system resources in the storage system, issuing the I/O request to the storage system.

8. The method of claim 1 further comprising, responsive to issuing the I/O request, debiting a resource utilization balance for the entity associated with the I/O request.

9. An apparatus for system resource utilization balancing in a storage system, the apparatus including a computer memory and a computer processor, the computer memory including computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the steps of:

determining whether an amount of system resources required to service the I/O request is greater than an amount of available system resources in a storage system, wherein the I/O request is associated with an entity;

responsive to determining that the amount of system resources required to service the I/O request is greater than the amount of available system resources in the storage system;

queueing the I/O request in an entity-specific queue for the entity;

detecting that additional system resources in the storage system have become available; and

responsive to detecting that additional system resources in the storage system have become available, issuing an I/O request from an entity-specific queue for an entity that has a highest priority among entities with non-empty entity-specific queues, wherein a priority for each entity that utilizes the storage system is determined based on the amount of I/O requests associated with the entity in a time-independent period.

10. The apparatus of claim 9 wherein the time-independent period includes an amount of most recently processed I/O requests that is equal to a multiple of the amount of I/O requests that may be processed by the storage system in parallel.

11. The apparatus of claim 9 wherein the time-independent period is determined by determining an amount of I/O requests that may be processed by the storage system in parallel while adhering to a response time requirement.

12. The apparatus of claim 9 further comprising computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the steps of:

determining a priority for each entity with a non-empty entity-specific queue, including;

determining, in dependence upon the amount of I/O requests that may be processed by the storage system in parallel, a fair share of system resources for each entity;

assigning priorities to each entity with a non-empty entity-specific queue in dependence upon the amount I/O requests processed for each entity during the time-independent period in excess of the fair share of system resources for each entity.

13. The apparatus of claim 9 further comprising computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the steps of:

determining, in dependence upon the amount of I/O requests that may be processed by the storage system in parallel, a fair share of system resources for each entity;

tracking, for each entity, the amount I/O requests processed for each entity during the time-independent period; and

crediting a resource utilization balance for each entity with the fair share of system resources for each entity upon the expiration of the time-independent period.

14. The apparatus of claim 9 further comprising computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the steps of:

determining the amount of system resources required to service the I/O request; and

determining the amount of available system resources in the storage system.

15. The apparatus of claim 9 further comprising computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the step of, responsive to determining that the amount of system resources required to service the I/O request is not greater than the amount of available system resources in the storage system, issuing the I/O request to the storage system.

16. The apparatus of claim 9 further comprising computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the step of, responsive to issuing the I/O request, debiting a resource utilization balance for the entity associated with the I/O request.