Correlated volume placement in a distributed block storage service

Patent metadata

Field	Value
Publication number	US-11080092-B1
Application number	US-201916366836-A
Country	US
Kind code	B1
Filing date	Mar 27, 2019
Priority date	Mar 27, 2019
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

Systems and methods are disclosed for handling requests to create multiple volumes with an expected usage correlation on a block storage service. Rather than handling each request to create a volume independently, embodiments described herein can handle the request in bulk, quickly determining whether the request as a whole can be handled at the system. In one embodiment, the service allows for oversubscription of use on hosts, as well as parallelization of placement decisions, by rejecting placement requests when a number of possible hosts for a volume within a requested set falls below a candidate set size, which is determined based on factors such as a number of requested volumes and an expected accuracy of state information for the service at a placement engine within a distributed set of engines.

First claim

What is claimed is:

1. A system to manage requests for multiple data volumes on a block-storage service, the system comprising:
a plurality of hosts, each host corresponding to a computing device configured to host data volumes of the block-storage service, each data volume representing network-accessible block storage; and
one or more computing devices configured to implement a control plane to:
receive a request of a client computing device to create a plurality of data volumes on the service;
identify an expected correlation in a timing of input/output (I/O) operations to the plurality of data volumes;
determine a division of the request into a plurality of subrequests, each of the subrequests corresponding to a subset of data volumes from the plurality of data volumes;
determine, from at least a total number of data volumes within the plurality of data volumes, a candidate set size indicating a minimum required number of hosts among which the subset of data volumes of each subrequest are to be distributed;
determine that a total number of hosts, within the plurality of hosts, available to host a data volume of the plurality of data volumes is less than the candidate set size; and
notify the client computing device that the request cannot be fulfilled.

2. The system of claim 1 , wherein notification to the client computing device that the request cannot be fulfilled occurs prior to any instruction to a host, from the plurality of hosts, to host a data volume of the plurality of data volumes.

3. The system of claim 1 , wherein, to determine that the total number of hosts, within the plurality of hosts, available to host a data volume of the plurality of data volumes is less than the candidate set size, implementation of the control plane causes the one or more computing devices to determine the candidate set size exceeds a number of hosts in the plurality of hosts.

4. The system of claim 1 , wherein implementation of the control plane causes the one or more computing devices to:
determine, from the total number of hosts available to host a data volume of the plurality of data volumes, an alternative candidate set size; and
determine, from the alternative candidate set size, a suggested alternative number of data volumes;
wherein the notification to the client computing device indicates the suggested alternative number of data volumes.

5. A computer-implemented method comprising:
receiving a request of a client computing device to create a plurality of data volumes on a block-storage service, wherein the service includes a plurality of placement engines, each placement engine configured to obtain a subrequest corresponding to a subset of data volumes from the plurality of data volumes and to place, among hosts of the block-storage service, individual data volumes of the subset;
identifying an expected correlation of operation of the plurality of volumes;
determining, from at least a metric regarding the plurality of data volumes in aggregate, a candidate set size, the candidate set size indicating a minimum required number of hosts among which the subset of data volumes of each subrequest are to be distributed;
determining that a total number of hosts, within a plurality of hosts configured to host data volumes of the block-storage service, available to host a data volume of the plurality of data volumes is less than the candidate set size; and
notifying the client computing device that the request cannot be fulfilled.

6. The computer-implemented method of claim 5 , wherein the expected correlation of operation of the plurality of volumes is an expected correlation in timing of input/output (I/O) operations of the plurality of volumes.

7. The computer-implemented method of claim 5 , wherein identifying the expected correlation of operation to the plurality of volumes comprises identifying that the plurality of volumes are associated with a cluster of computing devices.

8. The computer-implemented method of claim 7 , wherein the cluster of computing includes virtual computing devices on a hosted computing environment.

9. The computer-implemented method of claim 5 , wherein identifying the expected correlation of operation to the plurality of volumes comprises identifying that the plurality of volumes are associated with an individual account on the block-storage service.

10. The computer-implemented method of claim 5 , wherein the candidate set size is determined as a proportion of the number of data volumes within the plurality of data volumes.

11. The computer-implemented method of claim 5 , wherein the candidate set size is further determined based at least partly on an expected accuracy of the information indicating a state of the plurality of hosts.

12. The computer-implemented method of claim 11 , wherein the expected accuracy of the information is determined at least partly on a volume of received placement requests.

13. The computer-implemented method of claim 5 , wherein determining that the total number of hosts available to host a data volume of the plurality of data volumes is less than the candidate set size comprises determining that the candidate set size exceeds a total number of hosts in the plurality of hosts with hardware capable of hosting data volumes of a type specified within the request.

14. The computer-implemented method of claim 5 further comprising:
determining, from the total number of hosts available to host a data volume of the plurality of data volumes, an alternative candidate set size;
determining, from the alternative candidate set size, a suggested alternative number of data volumes; and
notifying the client computing device of the suggested alternative number of data volumes.

15. A system comprising:
a data store including computer-executable instructions; and
one or more computing devices configured to execute the instructions to:
receive a request of a client computing device to create a plurality of data volumes on a block-storage service, wherein the service includes a plurality of placement engines, each placement engine configured to obtain a subrequest corresponding to a subset of data volumes from the plurality of data volumes and to place, among hosts of the block-storage service, individual data volumes of the subset;
identify an expected correlation of operation of the plurality of volumes;
determine, from at least a metric regarding the plurality of data volumes in aggregate, a candidate set size, the candidate set size indicating a minimum required number of hosts among which the subset of data volumes of each subrequest are to be distributed;
determine that a total number of hosts, within a plurality of hosts configured to host data volumes of the block-storage service, available to host a data volume of the plurality of data volumes is less than the candidate set size; and
notify the client computing device that the request cannot be fulfilled.

16. The system of claim 15 , wherein the expected correlation of operation of the plurality of volumes is an expected correlation in timing of input/output (I/O) operations of the plurality of volumes.

17. The system of claim 15 , wherein the candidate set size is further determined based at least in part on a requested performance of the plurality of data volumes.

18. The system of claim 15 , wherein, to determine that the total number of hosts, within the plurality of hosts, available to host a data volume of the plurality of data volumes is less than the candidate set size, the instructions cause the one or more computing devices to

Assignees

• Amazon Tech Inc

Inventors

• Guo Yilin
• Greenwood Christopher Magee
• Flaherty Mitchell
• Venugopal Sriram
• Lin Wells
• Brennan Patrick E
• Yu Linfeng
• Yee Alexander R
• Herndon Gary Michael

Classifications

• G06F2209/5021

  Priority · CPC title

• G06F9/5011

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• G06Q10/0631

  Resource planning, allocation, distributing or scheduling for enterprises or organisations · CPC title

• G06Q30/0645 Primary

  Rental transactions; Leasing transactions · CPC title

• G06F9/5016 Primary

  the resource being the memory · CPC title