Approximating sequential workloads on resource constrained systems

Patent metadata

Field	Value
Publication number	US-10089145-B1
Application number	US-201514980687-A
Country	US
Kind code	B1
Filing date	Dec 28, 2015
Priority date	Dec 28, 2015
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

Abstract

Data storage services may provide customers with access to computing resources of data storage server and throttling methods may be used manage the computing resources of the data storage service in order to ensure that the customers do not overload the data storage servers. Tokens may represent I/O operations executed by the customer of the data storage service. When I/O request are received the data storage service may determine if the I/O request is a member of a sequence and remove a reduced number for tokens from the work token bucket as a result. The data storage server may determine the I/O request is a member of a sequence based at least in part on a logical chunk of a storage volume the I/O request maps to.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
initializing a logical volume with a total capacity of the logical volume and a maximum merge size for the logical volume, where the maximum merge size indicates a length associated with one or more input/output (I/O) operations that may be merged to determine a number of tokens associated with the one or more I/O operations, by at least generating a logical mapping of sectors of the logical volume to one or more logical chunks by at least dividing the logical volumes into the one or more logical chunks based at least in part on the maximum merge size of the logical volume;
receiving a first work request specifying a first I/O operation;
determining a first logical chunk associated with the first I/O operation based at least in part on the logical mapping and first offset information associated with the first I/O operation;
incrementing a current length of merged I/O operations by at least adding a first length associated with the first operation to the current length of merged I/O operations;
determining a number of tokens associated with the first work request to be removed from a token bucket, where the number of tokens indicates an amount of computing resources utilized to complete the first I/O operation included the work request;
receiving a second work request including a second I/O operation; and
detecting that the second I/O operation included in the second work request is sequential to the first I/O operation by at least:
determining a second logical chunk associated with the second I/O operation based at least in part on the logical mapping and a second offset information associated with the second I/O operation;
detecting that the second I/O operation included in the second work request is sequential to the first I/O operation as a result of the first logical chunk and the second logical chunk being equal; and
incrementing the current length of merged I/O operations by at least adding a second length associated with the second operation to the current length of merged I/O operations.

2. The computer-implemented method of claim 1 , wherein determining the first logical chunk associated with the first I/O operation further comprises dividing the first offset information by a chunk size, where the chunk size corresponds to a size of a logical chunk of the one or more logical chunks associated with the volume.

3. The computer-implemented method of claim 1 , wherein the method further comprises removing a reduced number of tokens based at least in part on detecting tat the second I/O operation included in the second work request is sequential to the first I/O operation and the current length is not greater than the maximum merge size.

4. The computer-implemented method of claim 1 , wherein the method further comprises:
receiving a third work request including a third I/O operation;
detecting that the third I/O operation included in the third work request is sequential to the second I/O operation by at least:
obtaining third offset information associated with the third I/O operation from the work request;
determining a third logical chunk associated with the third I/O operation based at least in part on the logical mapping and the third offset information associated with the third I/O operation;
detecting that the third I/O operation included in the third work request is sequential to the second I/O operation as a result of the second logical chunk and the third logical chunk being equal; and
incrementing the current length of merged I/O operations by at least adding a third length associated with the third I/O operation to the current length; and

removing the number of tokens from the token bucket as a result of the current length of merged I/O operations greater than or equal to the maximum merge size.

5. A system, comprising:
one or more processors; and
memory that includes instructions that, if executed by the one or more processors, cause the system to:
receive a work request;
determine that the work request is sequential to at least one other previous work request by at least:
obtaining an offset and a length of the work request;
determining a logical chunk associated with the offset matches at least one other logical chunk associated with the at least one other previous work request, where the logical chunk is associated with one or more locations of a volume; and
incrementing a current length by at least adding the length to the current length; and

remove a number of tokens from a token bucket as a result of the determination that the work request is sequential to the at least one other previous work request, where the number of tokens is less than a second number of tokens that would be removed by the system if the work request was not a sequential work request.

6. The system of claim 5 , wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to, as a result of receiving a request to create the volume, determine a chunk size based at least in part on the maximum merge size, where the chunk size is used by the system to calculate the logical chunk and the at least one other logical chunk.

7. The system of claim 6 , wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to modify the chunk size in order to improve accuracy in determining that the work request is sequential to the at least one other previous work request.

8. The system of claim 6 , wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to modify the chunk size by at least multiplying the chunk size by a queue depth associated with the system, where the queue depth indicates a number of work requests the system will maintain in a queue for processing.

9. The system of claim 6 , wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to modify the chunk size based at least in part on metrics information obtained from the system.

10. The system of claim 5 , wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to:
generate a bit mask configured to provide chunk information if applied to the offset, the bit mask generated based at least in part on a chunk size associated with the maximum merge size; and
calculate the logical chunk based at least in part on the offset and the bit mask.

11. The system of claim 5 , wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to track a set of logical chunks corresponding to the at least one other previous work request.

12. The system of claim 5 , wherein the instructions that cause the system to determine the logical chunk associated with the offset matches the at least one other logical chunk further includes instructions that, if executed by the one or more processors, cause the system to shift the offset by a number of bits corresponding to a chunk size associated with the maximum merge size.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
obtain an offset and a length of a work request;
modify a chunk size;
determine chunk information based at least in part on the offset and the chunk size, including generating a bit mask configured to determine the chunk information associated with the offset;
determine the chun

Assignees

• Amazon Tech Inc

Inventors

• Priescu Valentin
• Thompson James Michael

Classifications

• G06F3/064

  Management of blocks · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title