Input-output prioritization for database workload

• US 9,262,505 B2
• Filed: 05/17/2013
• Issued: 02/16/2016
• Est. Priority Date: 05/17/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Yanacek, David Craig, Swift, Bjorn Patrick, Xiao, Wei, Muniswamy-Reddy, Kiran-Kumar, Filipe, Miguel Mascarenhas, Lu, Yijun
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US13/897,232
• Publication Number:
  US 20140344312A1
• Time in Patent Office: 1,005 Days
• Field of Search: 707/790
• US Class Current: 1/1
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A database management system may be operated by a third-party provider that hosts the system in a datacenter and provides access to the system to end users on behalf of various entities. Limits on total capacity consumption may be imposed, but may result in service outages when capacity consumption exceeds those limits. Requests to perform operations on the system may be classified. The request classifications may be associated with policies for admitting or rejecting the request. One or more token buckets representative of capacity available to the request to perform the operation may be used to determine to admit the request and updated based on the cost of performing the operation.

Claims

1. A system for prioritizing capacity consumption of a database management system, the system comprising:

one or more computing nodes configured to operate the database management system; and

one or more memories having stored thereon computer readable instructions that, upon execution, cause the system at least to;

receive a request to perform an operation on the database management system, the request comprising information indicative of a request class, the operation to be performed on behalf of a customer;

select a first token bucket from one or more data structures comprising a plurality of token buckets, the selection based at least in part on the request class, the first token bucket having an associated first capacity indicator, the first token bucket associated with a second token bucket of the plurality of token buckets;

determine that the first capacity indicator is indicative of a capacity to perform the operation on behalf of the customer;

perform the operation;

update the first capacity indicator based at least in part on capacity utilized by performing the operation; and

update a second capacity indicator associated with the second token bucket, based at least in part on the capacity utilized by performing the operation.

2. The system of claim 1, further comprising one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to:

receive information indicative of an association between the request class and the first token bucket.

3. The system of claim 1, further comprising one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to:

determine that a second capacity indicator associated with the second token bucket of the plurality of token buckets is indicative of a lack of capacity to perform the operation on behalf of the customer.

4. The system of claim 1, wherein the second capacity indicator is updated when the first capacity indicator is indicative of a lack of capacity to perform the operation.

5. The system of claim 1, wherein the second capacity indicator is updated when the first capacity indicator is updated.

6. A computer-implemented method for prioritizing capacity consumption comprising:

receiving a request to perform an operation on one or more computing nodes, the request comprising information indicative of a request class, the operation to be performed on behalf of a customer;

selecting, based at least in part on the request class, a first data structure from a plurality of data structures, wherein the first data structure comprises a first capacity indicator, the first data structure associated with a second data structure comprising a second capacity indicator;

determining that the first capacity indicator is indicative of a capacity of the one or more computing nodes to perform the operation on behalf of the customer;

performing the operation; and

updating the first capacity indicator and the second capacity indicator based at least in part on capacity utilized performing the operation.

7. The method of claim 6, wherein the operation is performed on one or more of a web service, web site, and database management system.

8. The method of claim 6, wherein the information indicative of the request class comprises a parameter.

9. The method of claim 6, wherein the information indicative of the request class comprises a configuration value.

10. The method of claim 6, further comprising associating the request class with one or more of a customer identifier, security role, and application programming interface.

11. The method of claim 6, further comprising:

receiving information indicative of a mapping between the request class and the first capacity indicator.

12. The method of claim 6, further comprising:

determining that the second capacity indicator from the plurality of data structures is indicative of a lack of capacity to perform the operation on behalf of the customer.

13. The method of claim 6, wherein the first capacity indicator and one or more additional capacity indicators from the plurality of data structures share one or more memory locations in the plurality of data structures indicative of capacity to perform the operation on behalf of the customer.

14. The method of claim 6, wherein the first capacity indicator corresponds to a subset of a total capacity of the one or more computing nodes.

15. The method of claim 6, wherein the first capacity indicator comprises a count of units of capacity available for performing operations on behalf of the customer.

16. The method of claim 15, where the count is increased based at least in part on a rate of allocated capacity accumulation.

17. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by a computing device, cause the computing device to at least:

receive a request to perform an operation on one or more computing nodes, the request comprising information indicative of a request class;

select, based at least in part on the request class, a first data structure from a plurality of data structures, wherein the first data structure comprises a first capacity indicator and is associated with a second data structure comprising a second capacity indicator;

determine that the first capacity indicator is indicative of sufficient capacity to admit the operation for processing;

perform the operation; and

update the first capacity indicator and the second capacity indicator based at least in part on capacity utilized to perform the operation.

18. The computer-readable storage medium of claim 17, wherein the information indicative of the request class comprises a parameter.

19. The computer-readable storage medium of claim 17, having stored thereon further instructions that, upon execution by the computing device, cause the computing device to at least:

determine that the second capacity indicator from the plurality of data structures is indicative of a lack of capacity to perform the operation.

20. The computer-readable storage medium of claim 17, wherein the second capacity indicator is updated when the first capacity indicator is indicative of a lack of capacity to perform the operation.

21. The computer-readable storage medium of claim 17, wherein the first capacity indicator comprises a count of units of capacity available to perform the operation.

22. The computer-readable storage medium of claim 21, wherein the count is increased based at least in part on a rate of allocated capacity accumulation.

23. A system for prioritizing capacity consumption, the system comprising:

one or more computing nodes; and

one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to;

receive information indicative of one or more requests classes;

receive information indicative of a mapping between a first request class of the one or more request classes and a first capacity indicator, the first capacity indicator associated with a second capacity indicator;

allocate a subset of total capacity to perform operations on one or more computing nodes to the first capacity indicator;

perform an operation upon determining that the operation corresponds to the first request class and determining that the first capacity indicator is indicative of capacity available to perform the operation on the one or more computing nodes; and

update the first capacity indicator and the second capacity indicator based at least in part on capacity utilized to perform the operation.

24. The system of claim 23, further comprising one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to:

receive information indicative of instructions to create a database table on behalf of a customer.

25. The system of claim 24, further comprising one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to:

determine the subset of total capacity based at least in part on a number of partitions of the database table.

26. The system of claim 23, further comprising one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to:

receive information indicative of instructions to modify a database table; and

receive information indicative of instructions to modify capacity allocated to the database table.

27. The system of claim 23, further comprising one or more memories having stored thereon computer readable instructions that, upon execution by a computing device, cause the system at least to:

send user interface instructions comprising instructions for accepting customer input, the customer input comprising the information indicative of the mapping.