System and method for diminishing workload imbalance across multiple database systems

• US 8,504,556 B1
• Filed: 03/08/2010
• Issued: 08/06/2013
• Est. Priority Date: 03/08/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dierkes, Glenn A., Rice, Charles E., Morley, Adam D., Leonhard, Michael D.
• Primary Examiner(s): PHAM, KHANH B
• Application Number:
  US12/719,828
• Time in Patent Office: 1,247 Days
• Field of Search: 707/713, 707/719, 707/720, 707/770
• US Class Current: 707/713
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application

Abstract

Various embodiments of a system and method for diminishing workload imbalance across multiple database systems are described. Embodiments may include a resource balancer configured to, for each of a multiple database systems hosting database resources assigned to different user entities, generate a system usage score for that database system based on database usage scores of respective database resources hosted by that database system. Each usage score of a given database resource may indicate a quantity of work performed by the respective database system to process one or more requests directed to that database resource. The resource balancer may also be configured to generate one or more instructions to move a database resource from a first database system having a first system usage score to a second database system having a smaller system usage score in order to diminish an imbalance of workload across the database systems.

Claims

1. A system, comprising:

one or more computers comprising one or more memories and one or more processors, wherein the one or more memories comprise program instructions executable by the one or more computers to implement a resource balancer configured to;

for a given multi-tenant database system of a plurality of database systems hosting databases that are each assigned to a particular user entity of different user entities;

generate a database operational usage score for each individual database of multiple databases hosted by the given multi-tenant database system, wherein;

each individual database of the multiple databases comprises a particular defined data set to which the given multi-tenant database system restricts access among the different user entities to the particular user entity to which the individual database is assigned, and at least some of the multiple databases are each assigned to a different particular user entity of the different user entities; and

the database operational usage score for each individual database of the multiple databases is determined based on applying a usage scoring model to one or more requests directed to the individual database, wherein the usage scoring model estimates a quantity of work required to be performed by the given multi-tenant database system to process request types of the one or more requests directed to the individual database of the multiple databases; and

generate a first system usage score for the given multi-tenant database system based on aggregating the multiple database operational usage scores generated for the multiple databases hosted by the given multi-tenant database system; and

generate one or more instructions to move at least one of the multiple databases from the given multi-tenant database system having the first system usage score to a second multi-tenant database system having a second system usage score that is less than the first system usage score in order to diminish an imbalance of workload across the plurality of multi-tenant database systems, wherein for each individual database of the at least one of the multiple databases, the second multi-tenant database system restricts access, to the particular defined data set of the individual database, among the different user entities to the particular user entity to which the individual database is assigned.

2. The system of claim 1, wherein the resource balancer is configured to:

for each individual database of the multiple databases hosted by the given multi-tenant database system;

receive log information that indicates results of said applying the usage scoring model to the one or more requests directed to the individual database.

3. The system of claim 2, wherein the resource balancer is configured to determine the database operational usage score for each individual database of the multiple databases hosted by the given multi-tenant database system as a summation of the results of applying the usage scoring model to each of the one or more requests directed to the individual database.

4. The system of claim 1, wherein the resource balancer is configured to determine a system usage score, for each multi-tenant database system of the plurality of multi-tenant database systems, as a summation of database operational usage scores for all databases hosted by the multi-tenant database system.

5. The system of claim 1, further comprising said plurality of multi-tenant database systems, wherein each multi-tenant database system of said plurality of database systems is configured to, for each individual database hosted by the multi-tenant database system:

receive one or more requests to perform an operation on the individual database hosted by the multi-tenant database system; and

generate a database operational usage score for the individual database based on a quantity of work performed by the multi-tenant database system to process the one or more requests to perform an operation on the individual database.

6. The system of claim 5, wherein each multi-tenant database system of said plurality of database systems is configured to store the database operational usage score for each individual database hosted by the multi-tenant database system as log data accessible to the resource balancer.

7. The system of claim 5, wherein the one or more requests to perform an operation on the individual database hosted by the multi-tenant database system comprise a request to read or write one or more attributes of a database record of the individual database, wherein the multi-tenant database system hosting the individual database is configured to determine said database operational usage score for the individual database based, at least in part, on how many of the one or more attributes of the database record of the individual database are read or written.

8. The system of claim 7, wherein the multi-tenant database system hosting the individual database is configured to determine said database operational usage score for the individual database based, at least in part, on computing a polynomial expression of the usage scoring model that includes a variable quantity representing how many of the one or more attributes of the database record are read or written.

9. The system of claim 5, wherein the one or more requests to perform an operation on the individual database hosted by the multi-tenant database system include a database query, wherein the multi-tenant database system is configured to determine said database operational usage score for the individual database based, at least in part, on how many database records must be evaluated by the multi-tenant database system in order to complete the database query.

10. The system of claim 1, wherein the resource balancer is configured to select a particular database to move, from among the multiple databases hosted by the given multi-tenant database system, in response to determining that the database operational usage score of the particular database is greater than the database operational usage scores of one or more other databases hosted by the given multi-tenant database system.

11. The system of claim 1, wherein the resource balancer is configured to eliminate one or more of the multiple databases hosted by the given multi-tenant database system as candidates to be moved in response to determining that a projection of time required to move the one or more of the multiple databases exceeds a threshold.

12. The system of claim 1, wherein the resource balancer is configured to eliminate one or more of the plurality of multi-tenant database systems as candidates to receive a database in response to one or more of:

a determination that a quantity of occupied memory of the one or more of the plurality of multi-tenant database systems exceeds a threshold, or a determination that a quantity of databases currently hosted by the one or more of the plurality of multi-tenant database systems exceeds a threshold.

13. A computer-implemented method, comprising:

for a given multi-tenant database system of a plurality of database systems hosting databases that are each assigned to a particular user entity of different user entities;

generating a database operational usage score for each individual database of multiple databases hosted by the given multi-tenant database system, wherein;

each individual database of the multiple databases comprises a particular defined data set to which the given multi-tenant database system restricts access among the different user entities to the particular user entity to which the individual database is assigned, and at least some of the multiple databases are each assigned to a different particular user entity of the different user entities; and

the database operational usage score for each individual database of the multiple databases is determined based on applying a usage scoring model to one or more requests directed to the individual database, wherein the usage scoring model estimates a quantity of work required to be performed by the given multi-tenant database system to process request types of the one or more requests directed to the individual database of the multiple databases; and

generating a first system usage score for the given multi-tenant database system based on aggregating the multiple database operational usage scores generated for the multiple databases hosted by the given multi-tenant database system; and

generating one or more instructions to move at least one of the multiple databases from the given multi-tenant database system having the first system usage score to a second multi-tenant database system having a second system usage score that is less than the first system usage score in order to diminish an imbalance of workload across the plurality of multi-tenant database systems, wherein for each individual database of the at least one of the multiple databases, the second multi-tenant database system restricts access, to the particular defined data set of the individual database, among the different user entities to the particular user entity to which the individual database is assigned.

14. The computer-implemented method of claim 13, wherein the method comprises, for each individual database of the multiple databases hosted by the given multi-tenant database system:

receiving log information that indicates results of said applying the usage scoring model to the one or more requests directed to the individual database.

15. The computer-implemented method of claim 14, wherein the method comprises determining the database operational usage score for each individual database of the multiple databases hosted by the given multi-tenant database system as a summation of the results of applying the usage scoring model to each of the one or more requests directed to the individual database.

16. The computer-implemented method of claim 13, comprising determining a system usage score, for each multi-tenant database system of the plurality of database systems, as a summation of database operational usage scores for all databases hosted by the multi-tenant database system.

17. The computer-implemented method of claim 13, wherein the method comprises, for each individual database hosted by a multi-tenant database system of said plurality of database systems:

receiving one or more requests to perform an operation on the individual database hosted by the multi-tenant database system; and

generating a database operational usage score for the individual database based on a quantity of work performed by the multi-tenant database system to process the one or more requests to perform an operation on the individual database.

18. The computer-implemented method of claim 17, wherein the method comprises storing the database operational usage score generated for the individual database hosted by the multi-tenant database system as log data accessible to a resource balancer.

19. The computer-implemented method of claim 17, wherein the one or more requests to perform an operation on the individual database hosted by the multi-tenant database system comprise a request to read or write one or more attributes of a database record of the individual database, wherein the method comprises determining said database operational usage score for the individual database based, at least in part, on how many of the one or more attributes of the database record of the individual database are read or written.

20. The computer-implemented method of claim 19, wherein the method comprises determining said database operational usage score for the individual database based, at least in part, on computing a polynomial expression of the usage scoring model that includes a variable quantity representing how many of the one or more attributes of the database record are read or written.

21. The computer-implemented method of claim 17, wherein the one or more requests to perform an operation on the individual database hosted by the multi-tenant database system include a database query, wherein the method comprises determining said database operational usage score for the individual database based, at least in part, on how many database records must be evaluated by the multi-tenant database system in order to complete the database query.

22. The computer-implemented method of claim 13, wherein the method comprises selecting a particular database to move, from among the multiple databases hosted by the given multi-tenant database system, in response to determining that the database operational usage score of the particular database is greater than the database operational usage scores of one or more other databases hosted by the given multi-tenant database system.

23. The computer-implemented method of claim 13, wherein the method comprises eliminating one or more of the multiple databases hosted by the given multi-tenant database system as candidates to be moved in response to determining that a projection of time required to move the one or more of the multiple databases exceeds a threshold.

24. The computer-implemented method of claim 13, wherein the method comprises eliminating one or more of the plurality of database systems as candidates to receive a database in response to one or more of:

a determination that a quantity of occupied memory of the one or more of the plurality of multi-tenant database systems exceeds a threshold, or a determination that a quantity of databases currently hosted by the given one or more of the plurality of multi-tenant database systems exceeds a threshold.

25. A computer-readable storage medium, storing program instructions computer-executable on a computer system to implement a resource balancer configured to:

for a given multi-tenant database system of a plurality of database systems hosting databases that are each assigned to a particular user entity of different user entities;

generate a database operational usage score for each individual database of multiple databases hosted by the given multi-tenant database system, wherein;

each individual database of the multiple databases comprises a particular defined data set to which the given multi-tenant database system restricts access among the different user entities to the particular user entity to which the individual database is assigned, and at least some of the multiple databases are each assigned to a different particular user entity of the different user entities; and

the database operational usage score for each individual database of the multiple databases is determined based on applying a usage scoring model to one or more requests directed to the individual database, wherein the usage scoring model estimates a quantity of work required to be performed by the given multi-tenant database system to process request types of the one or more requests directed to the individual database of the multiple databases; and

generate a first system usage score for the given multi-tenant database system based on aggregating the multiple database operational usage scores generated for the multiple databases hosted by the given multi-tenant database system; and

generate one or more instructions to move at least one of the multiple databases from the given multi-tenant database system having the first system usage score to a second multi-tenant database system having a second system usage score that is less than the first system usage score in order to diminish an imbalance of workload across the plurality of multi-tenant database systems, wherein for each individual database of the at least one of the multiple databases, the second multi-tenant database system restricts access, to the particular defined data set of the individual database, among the different user entities to the particular user entity to which the individual database is assigned.

26. The computer-readable storage medium of claim 25, wherein the resource balancer is configured to:

for each individual database of the multiple databases hosted by the given multi-tenant database system;

receive log information that indicates results of said applying the usage scoring model to the one or more requests directed to the individual database.

27. The computer-readable storage medium of claim 26, wherein the resource balancer is configured to determine the database operational usage score for each individual database of the multiple databases hosted by the given multi-tenant database system as a summation of the results of applying the usage scoring model to each of the one or more requests directed to the individual database.

28. The computer-readable storage medium of claim 25, wherein the resource balancer is configured to determine a system usage score, for each multi-tenant database system of the plurality of database systems, as a summation of database operational usage scores for all databases hosted by the multi-tenant database system.

29. The computer-readable storage medium of claim 25, wherein the program instructions are configured to, for each individual database hosted by a multi-tenant database system of said plurality of database systems:

receive one or more requests to perform an operation on the individual database hosted by the multi-tenant database system; and

generate a database operational usage score for the individual database based on a quantity of work performed by the multi-tenant database system to process the one or more requests to perform an operation on the individual database.

30. The computer-readable storage medium of claim 29, wherein the program instructions are configured to store the database operational usage score for each individual database hosted by the multi-tenant database system as log data accessible to the resource balancer.

31. The computer-readable storage medium of claim 29, wherein the one or more requests to perform an operation on the individual database hosted by the multi-tenant database system comprise a request to read or write one or more attributes of a database record of the individual database, wherein the program instructions are configured to determine said database operational usage score for the individual database based, at least in part, on how many of the one or more attributes of the database record of the individual database are read or written.

32. The computer-readable storage medium of claim 31, wherein the program instructions are configured to determine said database operational usage score for the individual database based, at least in part, on computing a polynomial expression of the usage scoring model that includes a variable quantity representing how many of the one or more attributes of the database record are read or written.

33. The computer-readable storage medium of claim 29, wherein the one or more requests to perform an operation on the individual database hosted by the multi-tenant database system include a database query, wherein the program instructions are configured to determine said database operational usage score for the individual database based, at least in part, on how many database records must be evaluated by the multi-tenant database system in order to complete the database query.

34. The computer-readable storage medium of claim 25, wherein the resource balancer is configured to select a particular database to move, from among the multiple databases hosted by the given multi-tenant database system, in response to determining that the database operational usage score of the particular database is greater than the database operational usage scores of one or more other databases hosted by the given multi-tenant database system.

35. The computer-readable storage medium of claim 25, wherein the resource balancer is configured to eliminate one or more of the multiple databases hosted by the given multi-tenant database system as candidates to be moved in response to determining that a projection of time required to move the one or more of the multiple databases exceeds a threshold.

36. The computer-readable storage medium of claim 25, wherein the resource balancer is configured to eliminate one or more of the plurality of database systems as candidates to receive a database in response to one or more of:

a determination that a quantity of occupied memory of the one or more of the plurality of database systems exceeds a threshold, or a determination that a quantity of databases currently hosted by the one or more of the plurality of database systems exceeds a threshold.