Determining placement of user data to optimize resource utilization for distributed systems

• US 7,984,151 B1
• Filed: 10/09/2008
• Issued: 07/19/2011
• Est. Priority Date: 10/09/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zongker, Douglas, Rajkumar, Nareshkumar, Raz, Danny, Bent, Leeann, Whitehead, Bradley
• Primary Examiner(s): Hamza; Faruk
• Application Number:
  US12/248,863
• Time in Patent Office: 1,013 Days
• Field of Search: 709/203, 709217-219, 709/223, 709225-226
• US Class Current: 709/226
• CPC Class Codes: G06F 13/38 Information transfer, e.g. on bus G06F13/14 takes precedence
• CPC Class Codes: G06F 2209/502 Proximity
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

User information describing a group of users of a distributed computer system configured to store and retrieve individualized user data associated with individual ones of the group of users, and system resource information associated with the distributed computer system, may be obtained. A global distribution plan describing a distribution of at least a portion of the individualized user data associated with the group may be determined based on a global optimization function of the obtained user information and system resource information associated with the distributed computer system, wherein the global optimization function is based on optimizing a global distribution of the portion of the individualized user data based on a determination of a measure of performance and fault tolerance associated with a model of the distributed computer system configured in accordance with the global distribution plan. The determined global distribution plan may be provided to a device for processing.

Claims

1. A computer-implemented method comprising:

obtaining, by a processor, information describing a geographic area from which users of a distributed computer system request access to individualized user data associated with individual ones of the users;

determining a global move plan indicating a plan of movement of individualized user data associated with selected users between different locations based on;

a global optimization function of the individualized user data;

a current geographic distribution of the selected users; and

a cost associated with the movement of the user data;

wherein the global optimization function includes moving the individualized user data to data centers geographically proximate to the geographic area; and

providing the determined global move plan to a load balancer for processing of the global move plan.

2. The computer-implemented method of claim 1 wherein the providing includes sending the global move plan to a data center load balancer.

3. The computer-implemented method of claim 1, further comprising aggregating the users into a group based on the users requesting access to their respective individualized user data from the geographic area.

4. The computer-implemented method of claim 3 further comprising aggregating user profile information including a count of the users included in the group.

5. The computer-implemented method of claim 4 wherein the aggregated user profile information further includes information describing a system resource usage attribute that indicates a usage attribute value that is similar for each user of the group.

6. The computer-implemented method of claim 5 wherein the system resource usage attribute includes a measure of usage of a system resource of the distributed computer system associated with each user included in the group.

7. The computer-implemented method of claim 5 wherein the system resource usage attribute includes a measure of an amount of individualized user data stored on one or more servers of the distributed computer system, wherein the measure of the amount of stored individualized user data is associated with each user included in the group.

8. The computer-implemented method of claim 1 further comprising obtaining system resource information associated with the distributed computer system including information indicating at least one of processor capacity, processor usage, storage device capacity, storage device usage, geographic location of distributed network devices, network bandwidth, or network latency.

9. The computer-implemented method of claim 1 wherein the distributed computer system includes a distributed computer system configured to provide at least one of email operations, calendar operations, or distributed storage operations for the users.

10. The computer-implemented method of claim 1 wherein the distributed computer system includes a master copy of individualized user data stored on a first server and a backup copy of the individualized user data stored on a second server associated with each of the users.

11. The computer-implemented method of claim 1 wherein the information includes aggregated user profile information describing at least the geographic area from which the users request access, and the global move plan includes aggregated user profile information and one or more counts associated with users selected for movement of data.

12. The computer-implemented method of claim 1 wherein determining the global move plan includes executing a constraint optimization operation on the obtained information and system resource information associated with the distributed computer system, to generate the global move plan.

13. The computer-implemented method of claim 12 wherein the constraint optimization operation is based on linear programming.

14. The computer-implemented method of claim 1, further comprising aggregating the users into a group based on the users in the group requesting access to their respective individualized user data from the geographic area and based on the users in the group using similar amounts of storage space for their data.

15. A system comprising:

at least one instruction store configured to store machine-executable instructions;

at least one instruction processor configured to execute at least a portion of the machine-executable instructions stored in the at least one instruction store to implement a global load balancer,

the global load balancer including;

a global execution engine configured to obtain information describing a geographic area from which users of a distributed computer system request access to individualized user data associated with individual ones of the users; and

a global optimization engine configured to determine a global move plan indicating a plan of movement of the individualized user data associated with selected users between different locations based on;

a global optimization function of the individualized user data;

a current geographic distribution of the selected users; and

a cost associated with the movement of the user data;

wherein the global optimization function includes moving the individualized user data to data centers geographically proximate to the geographical area.

16. The system of claim 15 wherein the global optimization engine is configured to provide the determined global move plan to a device based on sending the global move plan to a data center load balancer.

17. The system of claim 15 wherein the global execution engine is further configured to aggregate the users into a group based on the users requesting access to their respective individualized user data from the geographic area.

18. The system of claim 17 wherein the information further includes a count of the users included in the group.

19. The system of claim 17 wherein the information further includes information describing a system resource usage attribute that indicates a usage attribute value that is similar for each user of the group.

20. The system of claim 15 wherein the global optimization engine is configured to determine the global move plan based on executing a constraint optimization operation on the obtained information and system resource information associated with the distributed computer system, to generate the global move plan.

21. The system of claim 20 wherein the constraint optimization operation is based on linear programming.

22. The system of claim 15, wherein the global optimization engine is further configured to aggregate the users into a group based on the users in the group requesting access to their respective individualized user data from the geographic area and based on the users in the group using similar amounts of storage space for their data.