Mirrored stateful workers

• US 9,152,458 B1
• Filed: 08/30/2012
• Issued: 10/06/2015
• Est. Priority Date: 08/30/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hellerstein, Joseph, Pirtle, Rian T., Youseff, Lamia
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Kamran, Mehran
• Application Number:
  US13/599,861
• Time in Patent Office: 1,132 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/2025 using centralised failover control functionality
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2043 where the redundant components share a common memory address space
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for determining image search results. One of the methods includes scheduling a first computation for execution on each of a first plurality of worker processes. The first computation changes a respective state of each of one or more of the first worker processes from a first state to a second state. A respective second computation is scheduled for execution on each of a second plurality of worker, where each respective second computation will use a different value for a particular variable for two or more of the second plurality of worker processes. The respective state of each of the second plurality of worker processes is updated from the second state to a third state, where the third state corresponds to execution of the second computation using a first value of the particular variable.

Claims

1. A computer-implemented method comprising:

obtaining a plurality of different parameter values for a first computation, each parameter value being a different candidate value for transitioning all worker processes in a pool of worker processes from having a first state to having a different second state, wherein the worker processes in the pool of worker processes are installed on a plurality of different respective computing devices, wherein each worker process in the pool of worker processes has a state that is the same as the state of all other worker processes in the pool of worker processes;

providing each worker process having the first state a different respective parameter value that is different from parameter values provided to all other worker processes having the first state, wherein each worker process having the first state performs the first computation including applying the respective parameter value to generate a respective first result for the first computation according to the respective parameter value, and wherein the first computation is a non-state-altering computation;

receiving respective first results of the first computation from one or more worker processes of the pool of worker processes that performed the first computation;

receiving user input from a user selecting, as a selected parameter value, a parameter value of the plurality of parameter values based on the respective first results of the first computation; and

providing each worker process in the pool of worker processes having the first state the selected parameter value, wherein each worker process receiving the selected parameter value performs a second computation including applying the selected parameter value to modify the state of the worker process from having the first state to having the second state corresponding to the selected parameter value, and wherein the second computation is a state-altering computation.

2. The method of claim 1, wherein the respective state of a worker process is defined by a set of data to be used as input for a particular computation.

3. The method of claim 2, wherein input to the second computation and output of the second computation are the same for each of the worker processes in the pool of worker processes.

4. The method of claim 1, wherein two or more worker processes of the pool of worker processes perform the first computation simultaneously.

5. The method of claim 1, further comprising:

determining that a first worker process did not successfully modify a state of the first worker process from the first state to the second state; and

in response to the determining, removing the first worker process from the pool of worker processes.

6. The method of claim 1, further comprising:

storing the respective state of a first worker process that has a respective state that is the second state;

initializing a new worker process;

updating the respective state of the new worker process to the second state, including causing the new worker process to read the stored state of the first worker process; and

adding the new worker process to the pool of worker processes.

7. The method of claim 1, further comprising:

reading the first state from storage; and

updating the respective state of each worker process in the pool of worker processes to the first state using the first state read from storage.

8. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

obtaining a plurality of different parameter values for a first computation, each parameter value being a different candidate value for transitioning all worker processes in a pool of worker processes from having a first state to having a different second state, wherein the worker processes in the in a pool of worker processes are installed on a plurality of different respective computing devices, wherein each worker process in the pool of worker processes has a state that is the same as the state of all other worker processes in the pool of worker processes;

providing each worker process having the first state a different respective parameter value that is different from parameter values provided to all other worker processes having the first state, wherein each worker process having the first state performs the first computation including applying the respective parameter value to generate a respective first result for the first computation according to the respective parameter value, and wherein the first computation is a non-state-altering computation;

receiving respective first results of the first computation from one or more worker processes of the pool of worker processes that performed the first computation;

receiving user input from a user selecting, as a selected parameter value, a parameter value of the plurality of parameter values based on the respective first results of the first computation; and

providing each worker process in the pool of worker processes having the first state the selected parameter value, wherein each worker process receiving the selected parameter value performs a second computation including applying the selected parameter value to modify the state of the worker process from having the first state to having the second state corresponding to the selected parameter value, and wherein the second computation is a state-altering computation.

9. The system of claim 8, wherein the respective state of a worker process is defined by a set of data to be used as input for a particular computation.

10. The system of claim 9, wherein input to the second computation and output of the second computation are the same for each of the worker processes in the pool of worker processes.

11. The system of claim 8, wherein two or more worker processes of the pool of worker processes perform the first computation simultaneously.

12. The system of claim 8, wherein the operations further comprise:

determining that a first worker process did not successfully modify a state of the first worker process from the first state to the second state; and

in response to the determining, removing the first worker process from the pool of worker processes.

13. The system of claim 8, wherein the operations further comprise:

storing the respective state of a first worker process that has a respective state that is the second state;

initializing a new worker process;

updating the respective state of the new worker process to the second state, including causing the new worker process to read the stored state of the first worker process; and

adding the new worker process to the pool of worker processes.

14. The system of claim 8, wherein the operations further comprise:

reading the first state from storage; and

updating the respective state of each worker process in the pool of worker processes to the first state using the first state read from storage.

15. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

obtaining a plurality of different parameter values for a first computation, each parameter value being a different candidate value for transitioning all working processes in a pool of worker processes from having a first state to having a different second state, wherein the worker processes in the pool of worker processes are installed on a plurality of different respective computing devices, wherein each worker process in the pool of worker processes has a state that is the same as the state of all other worker processes in the pool of worker processes;

providing each worker process having the first state a different respective parameter value that is different from parameter values provided to all other worker processes having the first state, wherein each worker process having the first state performs the first computation including applying the respective parameter value to generate a respective first result for the first computation according to the respective parameter value, and wherein the first computation is a non-state-altering computation;

receiving respective first results of the first computation from one or more worker processes of the pool of worker processes that performed the first computation;

receiving user input from a user selecting, as a selected parameter value, a parameter value of the plurality of parameter values based on the respective first results of the first computation; and

providing each worker process in the pool of worker processes having the first state the selected parameter value, wherein each worker process receiving the selected parameter value performs a second computation including applying the selected parameter value to modify the state of the worker process from having the first state to having the second state corresponding to the selected parameter value, and wherein the second computation is a state-altering computation.

16. The computer-readable medium of claim 15, wherein the operations further comprise:

determining that a first worker process did not successfully modify a state of the first worker process from the first state to the second state; and

in response to the determining, removing the first worker process from the pool of worker processes.

17. The computer-readable medium of claim 15, wherein the operations further comprise:

storing the respective state of a first worker process that has a respective state that is the second state;

initializing a new worker process;

updating the respective state of the new worker process to the second state, including causing the new worker process to read the stored state of the first worker process; and

adding the new worker process to the pool of worker processes.