Congestion control in storage systems

Patent metadata

Field	Value
Publication number	US-9710407-B2
Application number	US-201615056894-A
Country	US
Kind code	B2
Filing date	Feb 29, 2016
Priority date	Mar 31, 2014
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

Abstract

An I/O request directed to a portion of a storage object managed at a distributed storage service is received. A congestion control parameter value to be used to schedule a storage operation corresponding to the I/O request is determined. The congestion control parameter is based at least in part on an offset within the storage object to which the I/O request is directed. The storage operation is scheduled in accordance with the congestion control parameter at a selected physical storage device to which the portion of the storage object is mapped.

First claim

What is claimed is:

1. A system, comprising:
one or more computing devices configured to:
receive an I/O (input/output) request directed to a portion of a storage object of a storage service, wherein the storage object comprises a plurality of logical blocks;
select a prioritization policy for concurrent requests directed to at least a portion of the plurality of logical blocks;
determine, in accordance with the selected prioritization policy, a congestion control parameter value to be used to schedule a particular storage operation corresponding to the I/O request; and
schedule the particular storage operation at a selected physical storage location in accordance with the determined congestion control parameter value.

2. The system as recited in claim 1 , wherein the congestion control parameter value indicates one of: (a) a delay period after which the particular storage operation is to be initiated or (b) a cost assigned to the particular storage operation, wherein the cost is to be used to determine a sequence in which the particular storage operation is to be initiated relative to other storage operations corresponding to I/O requests directed to the portion of the plurality of logical blocks.

3. The system as recited in claim 1 , wherein the one or more computing devices are further configured to:
select the prioritization policy from among a plurality of prioritization policies including a first prioritization policy for I/O requests that include reads, and a second prioritization policy for I/O requests that include writes.

4. The system as recited in claim 1 , wherein the one or more computing devices are further configured to:
select the prioritization policy from among a plurality of prioritization policies including a first prioritization policy for I/O requests identified as belonging to a sequential access pattern and a second prioritization policy for I/O requests identified as random access requests.

5. The system as recited in claim 1 wherein the storage service implements one of: (a) a file system interface, (b) a web services interface in which the storage object is associated with a universal record identifier (URI), or a block-level device interface.

6. A method, comprising:
performing, by one or more computing devices:
receiving an I/O request directed to a portion of a storage object of a storage service, wherein the storage object comprises a plurality of logical blocks;
determining that the I/O request is directed to at least a portion of a particular logical block;
selecting a prioritization policy from among a plurality of prioritization policies for concurrent requests directed to a same logical block;
computing, in accordance with the selected prioritization policy, a congestion control parameter value to be used to schedule a particular storage operation corresponding to the I/O request; and
scheduling the particular storage operation, in accordance with the computed congestion control parameter value, at a selected physical storage device to which the particular logical block is mapped.

7. The method as recited in claim 6 , wherein the I/O request is directed to a sub-unit of the particular logical block located at a particular offset within the particular logical block, wherein the congestion control parameter value comprises a particular cost assigned to the particular storage operation, relative to costs assigned to other storage operations directed to other offsets within the particular logical block, further comprising:
scheduling another storage operation, corresponding to a different I/O request directed to a different offset within the particular logical block, before the particular storage operation in response to a determination that a cost assigned to the other storage operation is lower than the particular cost.

8. The method as recited in claim 7 , wherein the different I/O request is part of a sequential read pattern of I/O operations requested by a particular client, wherein the sequential read pattern includes a subsequent I/O request received after the particular storage request, further comprising performing, by the one or more computing devices:
in response to determining that the other storage operation scheduled corresponding to the different I/O request has been issued, scheduling one or more subsequent storage operations corresponding to the subsequent I/O request prior to scheduling the particular storage operation.

9. The method as recited in claim 7 , further comprising:
selecting a function, to which the particular offset within the particular logical block is provided as input, to be used to generate the particular cost assigned to the particular storage operation, wherein, for a first offset and a second offset provided as input, wherein if the first offset is larger than the second offset, the mathematical function generates a higher cost corresponding to the first offset than a cost generated for the second offset.

10. The method as recited in claim 6 , wherein the I/O request is directed to a sub-unit of the particular logical block, the method further comprising performing, by the one or more computing devices:
sending, based on the selected prioritization policy, an error response to a client from whom another I/O request directed to a different sub-unit of the particular logical block is received; and
receiving, after said error message is sent, a retry request corresponding to the other I/O request.

11. The method as recited in claim 6 , wherein said computing the congestion control parameter value is performed in response to determining that a workload associated with the particular logical block is above a threshold level.

12. The method as recited in claim 6 , wherein contents of the particular logical block are stored at a particular storage device, the method further comprising performing, by the one or more computing devices:
changing the threshold level based at least in part on one or more of: (a) an identification of a client from which one or more I/O requests directed to the particular storage device are received, (b) a time of day, (c) a workload metric of the particular storage device derived from measurements collected over a particular time period, or (d) a name of a file store object whose contents are located at the particular storage device.

13. The method as recited in claim 6 , wherein the computed congestion control parameter value indicates a delay period after which the particular storage operation is to be initiated.

14. The method as recited in claim 13 , wherein the I/O request is directed to a sub-unit of the particular logical block, wherein the delay period is computed using a function to which an offset of the sub-unit is provided as input.

15. The method as recited in claim 13 , wherein the delay period is computed using a random number generator.

16. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
selecting the prioritization policy from among the plurality of prioritization policies including a first prioritization policy for I/O requests that include reads, and a second prioritization policy for I/O requests that include writes.

17. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
selecting the prioritization policy from among the plurality of prioritization policies including a first prioritization policy for I/O requests identified as belonging to a sequential access pattern, and a second prioritization policy for I/O requests identified as ra

Assignees

• Amazon Tech Inc

Inventors

• Oikarinen Matti Juhani
• Frigo Matteo
• Nuss Michael Anthony
• Duso Wayne William

Classifications

• G06F2206/1012

  Load balancing · CPC title

• G06F13/18 Primary

  based on priority control (G06F13/1605 takes precedence) · CPC title

• G06F3/0659

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

• G06F3/061

  Improving I/O performance · CPC title

• G06F13/1642

  with request queuing · CPC title