System and method for scalable data distribution

• US 8,959,144 B2
• Filed: 12/27/2012
• Issued: 02/17/2015
• Est. Priority Date: 12/10/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jain, Arvind
• Primary Examiner(s): MIRZA, ADNAN M
• Application Number:
  US13/728,984
• Publication Number:
  US 20130117348A1
• Time in Patent Office: 782 Days
• Field of Search: 709/201, 709/202, 709/203
• US Class Current: 709/203
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

A system having a resource manager, a plurality of masters, and a plurality of slaves, interconnected by a communications network. To distribute data, a master determined that a destination slave of the plurality slaves requires data. The master then generates a list of slaves from which to transfer the data to the destination slave. The master transmits the list to the resource manager. The resource manager is configured to select a source slave from the list based on available system resources. Once a source is selected by the resource manager, the master receives an instruction from the resource manager to initiate a transfer of the data from the source slave to the destination slave. The master then transmits an instruction to commence the transfer.

Claims

1. A method for distributing data over a network, the method performed by a master having one or more processors and memory storing one or more programs for execution by the one or more processors, the method comprising:

determining at said master that a destination slave requires data, wherein said destination slave is one of a plurality of slaves;

generating at said master a list of those slaves of said plurality of slaves that contain said data;

transmitting from said master to a resource manager said list, where said resource manager is configured to select a source slave from said list based on available system resources;

receiving at said master from said resource manager an initiate instruction to initiate a transfer of said data from said source slave to said destination slave; and

transmitting from said master a commence instruction to commence said transfer, wherein the master, resource manager and slaves communicate with each other via the network.

2. The method of claim 1, wherein said transmitting comprises transmitting said commence instruction to said destination slave to copy said data from said source slave.

3. The method of claim 1, wherein said transmitting comprises transmitting said commence instruction to said source slave to copy said data to said destination slave.

4. The method of claim 1, further comprising after said generating, sorting said list of slaves based on predefined criteria.

5. The method of claim 4, wherein said sorting further comprises ranking each respective slave in said list based on a distance between said destination slave and said respective slave.

6. The method of claim 4, wherein said sorting further comprises ranking each respective slave in said list based on whether said destination slave recently copied data from said respective slave.

7. The method of claim 4, wherein said sorting further comprises ranking each respective slave in said list based on an activity level of said respective slave.

8. The method of claim 4, wherein said sorting said list further comprises ranking each respective slave in said list based on an amount of said data present in said respective slave.

9. A method for distributing data over a network, the method performed by a resource manager having one or more processors and memory storing one or more programs for execution by the one or more processors, the method comprising:

receiving at the resource manager, from a master, a list of slaves of a plurality of slaves that contain data to be copied to a destination slave;

ascertaining available system resources;

selecting a source slave from said list as a source of data based on available system resources; and

transmitting an initiate instruction from said resource manager to said master to initiate a data transfer from said source slave to said destination slave, wherein the master, resource manager and slaves communicate with each other via the network.

10. The method of claim 9, wherein said selecting further comprises:

identifying priority levels associated with data transfers on a link between a slave from said list and said destination slave in a past time interval; and

allocating resources for data transfers on said link in a current time interval based upon said priority levels in said past time interval.

11. The method of claim 10, further comprising:

updating an indication of priority levels associated with data transfers in said current time interval on said link between said source slave and said destination slave; and

updating an indication of resources allocated to said priority levels associated with said data transfers in said current time interval on said link between said source slave and said destination slave.

12. The method of claim 10, wherein said selecting further comprises selecting said source slave based on available system resources allocated to a priority level associated with said data.

13. The method of claim 12, wherein said selecting further comprises selecting said source slave based on available system resources allocated to a lower priority level than said priority level associated with said data, if there are no resources allocated to said priority level associated with said data.

14. A method for distributing data over a network, performed on:

a master having one or more processors and memory storing one or more programs for execution by the one or more processors; and

a resource manager having one or more processors and memory storing one or more programs for execution by the one or more processors;

said method comprising;

at the master, determining that a destination slave of a plurality of slaves requires data;

at the master, generating a list of slaves from said plurality of slaves that have said data;

at the master, transmitting said list to the resource manager;

at the resource manager, selecting a source slave from said list based on available system resources;

at the resource manager, transmitting an initiate instruction to the master to initiate a transfer of said data between said source slave to said destination slave; and

at the master, transmitting a commence instruction to said destination slave to commence said transfer, wherein the master, resource manager and slaves communicate with each other via the network.

15. The method of claim 14, further comprising:

at the resource manager, allocating system resources amongst copy operations on a link between said source slave and said destination slave based on priority levels for past copy operations on said link.

16. A non-transitory computer-readable medium carrying sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

determining at a master that a destination slave requires data, wherein said destination slave is one of a plurality slaves;

generating at said master a list of those slaves of said plurality of slaves that contain said data;

transmitting from said master to a resource manager said list, where said resource manager is configured to select a source slave from said list based on available system resources;

receiving at said master from said resource manager an initiate instruction to initiate a transfer of said data from said source slave to said destination slave; and

transmitting from said master a commence to commence said transfer, wherein the master, resource manager and slaves communicate with each other via a network.

17. The computer-readable medium of claim 16, wherein the instructions for transmitting said commence instruction comprises instructions for transmitting said commence instruction to said destination slave to copy said data from said source slave.

18. The computer-readable medium of claim 16, wherein the instructions for transmitting said commence instruction comprises instructions for transmitting said commence instruction to said source slave to copy said data to said destination slave.

19. The computer-readable medium of claim 16, wherein the instructions for generating said list further comprises instructions for, after said generating, sorting said list of slaves based on predefined criteria.

20. The computer-readable medium of claim 19, wherein the instructions for sorting said list of slaves further comprises instructions for ranking each respective slave in said list based on a distance between said destination slave and said respective slave.

21. The computer-readable medium of claim 19, wherein the instructions for sorting said list of slaves further comprises instructions for ranking each respective slave in said list based on whether said destination slave recently copied data from said respective slave.

22. The computer-readable medium of claim 19, wherein the instructions for sorting said list of slaves further comprises instructions for ranking each respective slave in said list based on an activity level of said respective slave.

23. The computer-readable medium of claim 19, wherein the instructions for sorting said list of slaves further comprises instructions for ranking each respective slave in said list based on an amount of said data present in said respective slave.

24. A non-transitory computer-readable medium carrying sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

receiving at a resource manager, from a master, a list of slaves of a plurality of slaves that contain data to be copied to a destination slave;

ascertaining available system resources;

selecting a source slave from said list as a source of data based on available system resources; and

transmitting an initiate instruction from said resource manager to said master to initiate a data transfer from said source slave to said destination slave, wherein the master, resource manager and slaves communicate with each other via a network.

25. The computer-readable medium of claim 24, wherein the instructions for selecting further comprises instructions for:

identifying priority levels associated with data transfers on a link between a slave from said list and said destination slave in a past time interval; and

allocating resources for data transfers on said link in a current time interval based upon said priority levels in said past time interval.

26. The computer-readable medium of claim 25, further comprising instructions for:

updating an indication of priority levels associated with data transfers in said current time interval on said link between said source slave and said destination slave; and

updating an indication of resources allocated to said priority levels associated with said data transfers in said current time interval on said link between said source slave and said destination slave.

27. The computer-readable medium of claim 25, wherein the instructions for selecting further comprises instructions for selecting said source slave based on available system resources allocated to a priority level associated with said data.

28. The computer-readable medium of claim 27, wherein the instructions for selecting further comprises instructions for selecting said source slave based on available system resources allocated to a lower priority level than said priority level associated with said data, if there are no resources allocated to said priority level associated with said data.

29. A system for distributing data, comprising:

a master having one or more processors and memory storing one or more programs for execution by the one or more processors of the master; and

a resource manager having one or more processors and memory storing one or more programs for execution by the one or more processors of the resource manager;

said master being configured to determine that a destination slave requires data, wherein said destination slave is one of a plurality of slaves,

to generate a list of those slaves of said plurality of slaves that contain said data,

to transmit to said resource manager said list,

to receive from said resource manager an initiate instruction to initiate a transfer of said data from a source slave to said destination slave, and

to transmit a commence instruction to one of said source slave and said destination slave to commence said transfer; and

said resource manager being configured

to receive from said master said list of slaves,

to ascertain available system resources,

to select said source slave from said list based on available system resources, and

to transmit to said master said initiate instruction, wherein the master, resource manager and slaves communicate with each other via the network.

30. The system of claim 29, wherein said list is sorted based on predefined criteria.

31. The system of claim 29, wherein said resource manager is further configured to ascertain resources on a link between said source slave and said destination slave.

32. The system of claim 29, wherein said resource manager is further configured to allocate resources along a link between said source slave and said destination slave amongst priority levels of data transfers based on priority levels of past data transfers on said link.

33. The system of claim 29, wherein said master is further configured to determine:

an indication of a state of each slave in at least a subset of said plurality of slaves; and

an indication of activity level of said each slave.

34. The system of claim 29, wherein said resource manager is further configured to determine:

an indication of maximum system resources on each link between said plurality of slaves; and

an indication of system resources remaining on each said link.