Adjusting input/output operation arrival times to represent a token bucket that enforces maximum rate and burst size limits

• US 9,537,777 B1
• Filed: 03/30/2015
• Issued: 01/03/2017
• Est. Priority Date: 03/30/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Tohmaz, Abdul S., Hu, Kenneth
• Primary Examiner(s): Wu, Benjamin
• Application Number:
  US14/672,696
• Time in Patent Office: 645 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 13/4221 being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/28 in relation to timing considerations

Abstract

In-band, on the fly allocation of tokens to a token bucket that limits the rate at which input/output operations are performed on a storage resource according to a maximum rate limit, while also supporting a user-configurable burst size limit that allows for a temporary spike in the rate input/output operations are received for the storage resource. An input/output time parameter is adjusted in response to receipt of input/output operations, based on the arrival times of the input/output operations, the maximum rate limit, and the burst size limit, in order to automatically allocate and consume tokens for the token bucket without requiring a separate token allocation thread.

Claims

1. A computer-implemented method of using an input/output time parameter to represent a number of tokens in a token bucket in order to enforce a maximum rate limit for input/output operations directed to a storage resource, comprising executing, on at least one processor, the steps of:

setting a minimum permitted input/output operation inter-arrival time period to an inverse of the maximum rate limit;

processing an initially received input/output operation by setting the input/output time parameter to an arrival time of the initial input/output operation; and

processing each subsequently received input/output operation by

setting an inter-arrival time period parameter to a difference between an arrival time of the received input/output operation and the input/output time parameter,

determining whether the inter-arrival time period parameter is less than the minimum permitted input/output operation inter-arrival time, and

in response to determining that the inter-arrival time period parameter is not less than the minimum permitted input/output operation inter-arrival time, determining that there is at least one token available in the token bucket and accordingly allowing the input/output operation to be performed on the storage resource, and decrementing the number of tokens in the token bucket by adding the minimum permitted input/output operation inter-arrival time to the input/output time parameter.

2. The method of claim 1, wherein processing each subsequently received input/output operation further includes:

in response to determining that the inter-arrival time period parameter is less than the minimum permitted input/output operation inter-arrival time, determining that there is not at least one token available in the token bucket, and accordingly preventing the input/output operation from being performed on the storage resource.

3. The method of claim 1, wherein processing each subsequently received input/output operation further includes:

in response to determining that the inter-arrival time period parameter is not less than the minimum permitted input/output operation inter-arrival time, and after decrementing the number of tokens in the token bucket by adding the minimum permitted input/output operation inter-arrival time to the input/output time parameter, limiting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by

comparing the input/output time parameter to the arrival time of the received input/output operation,

comparing a difference between the arrival time of the received input/output operation and the input/output time parameter to the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time, and

in response to determining that the value of the input/output time parameter is less than the arrival time of the received input/output operation and that the difference between the arrival time of the received input/output operation and the input/output time parameter is greater than the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time, setting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by setting the value of the input/output time parameter to the arrival time of the received input/output operation minus the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time.

4. The method of claim 1, wherein processing the initially received input/output operation further includes setting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by subtracting the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time from the input/output time parameter.

5. A computerized system for using an input/output time parameter to represent a number of tokens in a token bucket in order to enforce a maximum rate limit for input/output operations directed to a storage resource, comprising:

at least one hardware processor;

a memory having program code stored thereon, wherein the program code, when executed by the processor, causes the processor to

set a minimum permitted input/output operation inter-arrival time period to an inverse of the maximum rate limit;

process an initially received input/output operation by setting the input/output time parameter to an arrival time of the initial input/output operation; and

process each subsequently received input/output operation by

setting an inter-arrival time period parameter to a difference between an arrival time of the received input/output operation and the input/output time parameter,

determining whether the inter-arrival time period parameter is less than the minimum permitted input/output operation inter-arrival time, and

in response to determining that the inter-arrival time period parameter is not less than the minimum permitted input/output operation inter-arrival time, determining that there is at least one token available in the token bucket and accordingly allowing the input/output operation to be performed on the storage resource, and decrementing the number of tokens in the token bucket by adding the minimum permitted input/output operation inter-arrival time to the input/output time parameter.

6. The system of claim 5, wherein the program code, when executed on the processor, further causes the processor to process each subsequently received input/output operation further by, in response to determining that the inter-arrival time period parameter is less than the minimum permitted input/output operation inter-arrival time, determining that there is not at least one token available in the token bucket, and accordingly preventing the input/output operation from being performed on the storage resource.

7. The system of claim 5, wherein the program code, when executed on the processor, causes the processor to further process each subsequently received input/output operation further by:

in response to determining that the inter-arrival time period parameter is not less than the minimum permitted input/output operation inter-arrival time, and after decrementing the number of tokens in the token bucket by adding the minimum permitted input/output operation inter-arrival time to the input/output time parameter, limiting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by

comparing the input/output time parameter to the arrival time of the received input/output operation,

comparing a difference between the arrival time of the received input/output operation and the input/output time parameter to the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time, and

in response to determining that the value of the input/output time parameter is less than the arrival time of the received input/output operation and that the difference between the arrival time of the received input/output operation and the input/output time parameter is greater than the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time, setting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by setting the value of the input/output time parameter to the arrival time of the received input/output operation minus the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time.

8. The system of claim 5, wherein the program code, when executed on the processor, further causes the processor to process the initially received input/output operation by setting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by subtracting the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time from the input/output time parameter.

9. A non-transitory computer readable medium for using an input/output time parameter to represent a number of tokens in a token bucket in order to enforce a maximum rate limit for input/output operations directed to a storage resource, the non-transitory medium having instructions stored thereon, that when executed on a processor of a computer, perform the steps of:

setting a minimum permitted input/output operation inter-arrival time period to an inverse of the maximum rate limit;

processing an initially received input/output operation by setting the input/output time parameter to an arrival time of the initial input/output operation; and

processing each subsequently received input/output operation by

setting an inter-arrival time period parameter to a difference between an arrival time of the received input/output operation and the input/output time parameter,

determining whether the inter-arrival time period parameter is less than the minimum permitted input/output operation inter-arrival time, and

in response to determining that the inter-arrival time period parameter is not less than the minimum permitted input/output operation inter-arrival time, determining that there is at least one token available in the token bucket and accordingly allowing the input/output operation to be performed on the storage resource and decrementing the number of tokens in the token bucket by adding the minimum permitted input/output operation inter-arrival time to the input/output time parameter.

10. The non-transitory computer-readable medium of claim 9, wherein the instructions stored thereon, when executed on a processor of a computer, further perform the step of processing each subsequently received input/output operation by:

in response to determining that the inter-arrival time period parameter is less than the minimum permitted input/output operation inter-arrival time, determining that there is not at least one token available in the token bucket, and accordingly preventing the input/output operation from being performed on the storage resource.

11. The non-transitory computer-readable medium of claim 9, wherein the instructions stored thereon, when executed on a processor of a computer, further perform the step of processing each subsequently received input/output operation by:

in response to determining that the inter-arrival time period parameter is not less than the minimum permitted input/output operation inter-arrival time, and after decrementing the number of tokens in the token bucket by adding the minimum permitted input/output operation inter-arrival time to the input/output time parameter, limiting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by

comparing the input/output time parameter to the arrival time of the received input/output operation,

comparing a difference between the arrival time of the received input/output operation and the input/output time parameter to the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time, and

in response to determining that the value of the input/output time parameter is less than the arrival time of the received input/output operation and that the difference between the arrival time of the received input/output operation and the input/output time parameter is greater than the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time, setting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by setting the value of the input/output time parameter to the arrival time of the received input/output operation minus the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time.

12. The non-transitory computer-readable medium of claim 9, wherein the instructions stored thereon, when executed on a processor of a computer, further perform the step of processing the initially received input/output operation by setting the number of tokens in the token bucket to the size of an input/output operation burst size limit for input/output operations directed to the storage resource by subtracting the result of multiplying the burst size limit and the minimum permitted input/output operation inter-arrival time from the input/output time parameter.