Adjusting input/output operation arrival times to represent a token bucket that enforces maximum rate and burst size limits
View Patent ↗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.
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.