Distributed resource allocation

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for allocating tasks to computing nodes using multiple resource allocators. One of the methods includes providing, by each resource allocator of a plurality of resource allocators, a first request to compute a first score to each computing node of a plurality of computing nodes, the first score representing a measure of availability for the computing node to take a particular task. A first score is received from each of the plurality of computing nodes and the nodes are ranked according to the first scores. A second request is provided to a highest-ranked computing node to compute a second score. If the difference between the first score and the second score satisfies a threshold, assigning the task to the highest-ranked computing node if and only if the difference between the first score and the second score satisfies the threshold.

What is claimed is: 
     
       1. A system comprising:
 one or more first physical computers and one or more storage devices storing instructions that are operable, when executed by the one or more first physical computers, to cause the one or more first physical computers to implement a plurality of computing nodes, each computing node being configured to take and perform tasks, wherein each computing node implements a respective representative configured to compute scores representing a measure of an ability of the computing node to take a particular task, the score being based on measures of utilization for one or more resources of the computing node; and 
 one or more second physical computers and one or more storage devices storing instructions that are operable, when executed by the one or more second physical computers, to cause the one or more second physical computers to implement a plurality of resource allocators that are configured to assign tasks among the plurality of computing nodes, wherein each resource allocator is configured to perform operations comprising:
 providing, to each of the plurality of computing nodes, a first request to compute a first score that represents an ability of the computing node to take a first task, 
 receiving, from each of the plurality of computing nodes in response to the first request, a respective first score that represents an ability of the computing node to take the first task, 
 generating a ranking of the plurality of computing nodes according to the first scores, 
 selecting, from the ranking of the plurality of computing nodes according to the first scores, a highest-ranked computing node of the plurality of computing nodes with a first score that is higher than the first scores for the other computing nodes in the plurality of computing nodes, 
 in response to selecting, from the ranking of the plurality of computing nodes according to the first scores, the highest-ranked computing node of the plurality of computing nodes with a first score that is higher than the scores for the other computing nodes in the plurality of computing nodes, providing, to the highest-ranked computing node of the plurality of computing nodes, a second request to make a reservation for the first task and to compute a second score that represents an ability of the highest-ranked computing node to take the first task, 
 receiving, from the highest-ranked computing node, the second score that represents an ability of the highest-ranked computing node to take the first task, 
 determining that a difference between the first score received from the highest-ranked computing node and the second score received from the highest-ranked computing node for the first task satisfies a threshold, 
 in response to determining that the difference between the first score received from the highest-ranked computing node and the second score received from the highest-ranked computing node satisfies the threshold, assigning the task to the highest-ranked computing node. 
 
 
     
     
       2. The system of  claim 1 , wherein each resource allocator is configured to perform operations comprising restarting a resource allocation process for a second task if a difference between a first score for the second task and a second score for the second task does not satisfy the threshold. 
     
     
       3. The system of  claim 2 , wherein restarting the resource allocation process comprises providing, to each of the plurality of computing nodes, a request to recompute the first score for the second task. 
     
     
       4. The system of  claim 1 , wherein each representative on each computing node is configured to perform operations comprising penalizing the first score, the second score, or both, if a second task having a same process identifier as the first task is already assigned to the computing node. 
     
     
       5. The system of  claim 4 , wherein penalizing the first score, the second score, or both, comprises adding a constant to the first score, the second score, or both, when one or more tasks having a same process identifier as the first task are already assigned to the computing node. 
     
     
       6. The system of  claim 4 , wherein penalizing the first score, the second score, or both, comprises penalizing the first score, the second score, or both, based on a number of tasks having the same process identifier as the first task that are already assigned to the computing node. 
     
     
       7. The system of  claim 1 , further comprising one or more third physical computers and one or more storage devices storing instructions that are operable, when executed by the one or more third physical computers, to cause the one or more third physical computers to implement a controller that is configured to distribute subsets of a plurality of tasks among the plurality of resource allocators. 
     
     
       8. The system of  claim 1 , wherein the threshold is a predetermined ratio of the first score. 
     
     
       9. The system of  claim 1 , wherein the first scores from the plurality of computing nodes comprise the first score from highest-ranked computing node and other first scores from the other computing nodes in the plurality of computing nodes, and
 wherein determining that a difference between the first score received from the highest-ranked computing node and the second score received from the highest-ranked computing node for the first task satisfies the threshold comprises:
 generating a second ranking of the plurality of computing nodes according to the second score and the other first scores; 
 determining, as the difference between the first score and the second score for the highest-ranked computing node, a change in location of the highest-ranked computing node from the ranking of the plurality of computing nodes to the second ranking of the plurality of computing nodes; and 
 determining whether the change in location of the highest-ranked computing node from the ranking of the plurality of computing nodes to the second ranking of the plurality of computing nodes satisfies the threshold. 
 
 
     
     
       10. A computer-implemented method comprising:
 providing, by a first resource allocator of a plurality of resource allocators in a distributed system, a first request to compute a first score to each computing node of a plurality of computing nodes, the first score representing a measure of an ability of the computing node to take a particular task; 
 receiving, by the first resource allocator from each of the plurality of computing nodes, a respective first score that represents an ability of the computing node to take the particular task; 
 generating a ranking of the plurality of computing nodes according to the first scores; 
 selecting, from the ranking of the plurality of computing nodes according to the first scores, a highest-ranked computing node of the plurality of computing nodes with a first score that is higher than the first scores for the other computing nodes in the plurality of computing nodes: 
 in response to selecting, from the ranking of the plurality of computing nodes according to the first scores, the highest-ranked computing node of the plurality of computing nodes with a first score that is higher than the first scores for the other computing nodes in the plurality of computing nodes, providing, by the first resource allocator to the highest-ranked computing node of the plurality of computing nodes, a second request to make a reservation for the particular task and to compute a second score that represents an ability of the highest-ranked computing node to take the particular task; 
 receiving, by the first resource allocator from the highest-ranked computing node, a computed second score that represents an ability of the highest-ranked computing node to take the particular task; 
 determining that a difference between the first score and received from the highest-ranked computing node the second score received from the highest-ranked computing node satisfies a threshold; and 
 assigning the particular task to the highest-ranked computing node if and only if the difference between the first score received from the highest-ranked computing node and the second score received from the highest-ranked computing node satisfies the threshold. 
 
     
     
       11. The method of  claim 10 , further comprising restarting, by a resource allocator, a resource allocation process for a second task if a difference between a first score for the second task and a second score for the second task does not satisfy the threshold. 
     
     
       12. The method of  claim 11 , wherein restarting the resource allocation process comprises providing, to each of the plurality of computing nodes, a request to recompute the first score for the second task. 
     
     
       13. The method of  claim 10 , further comprising penalizing the first score, the second score, or both, if a second task having a same process identifier as the particular task is already assigned to the computing node. 
     
     
       14. The method of  claim 13 , wherein penalizing the first score, the second score, or both, comprises adding a constant to the first score, the second score, or both, when one or more tasks having a same process identifier as the particular task are already assigned to the computing node. 
     
     
       15. The method of  claim 13 , wherein penalizing the first score, the second score, or both, comprises penalizing the first score, the second score, or both, based on a number of tasks having the same process identifier as the particular task that are already assigned to the computing node. 
     
     
       16. The method of  claim 10 , further comprising distributing subsets of a plurality of tasks among the plurality of resource allocators. 
     
     
       17. The method of  claim 10 , wherein the threshold is a predetermined ratio of the first score. 
     
     
       18. The method of  claim 10 , wherein the first scores from the plurality of computing nodes comprise the first score from highest-ranked computing node and other first scores from the other computing nodes in the plurality of computing nodes; and
 wherein determining that a difference between the first score and received from the highest-ranked computing node the second score received from the highest-ranked computing node satisfies a threshold comprises:
 generating a second ranking of the plurality of computing nodes according to the second score and the other first scores; 
 determining, as the difference between the first score and the second score for the highest-ranked computing node, a change in location of the highest-ranked computing node from the ranking of the plurality of computing nodes to the second ranking of the plurality of computing nodes; and 
 determining that the change in location of the highest-ranked computing node from the ranking of the plurality of computing nodes to the second ranking of the plurality of computing nodes satisfies the threshold. 
 
 
     
     
       19. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
 providing, by a first resource allocator of a plurality of resource allocators in a distributed system, a first request to compute a first score to each computing node of a plurality of computing nodes, the first score representing a measure of an ability of the computing node to take a particular task; 
 receiving, by the first resource allocator from each of the plurality of computing nodes, a respective first score that represents an ability of the computing node to take the particular task; 
 generating a ranking of the plurality of computing nodes according to the first scores; 
 selecting, from the ranking of the plurality of computing nodes according to the first scores, a highest-ranked computing node of the plurality of computing nodes with a first score that is higher than the first scores for the other computing nodes in the plurality of computing nodes: 
 in response to selecting, from the ranking of the plurality of computing nodes according to the first scores, the highest-ranked computing node of the plurality of computing nodes with a first score that is higher than the first scores for the other computing nodes in the plurality of computing nodes, providing, by the first resource allocator to the highest-ranked computing node of the plurality of computing nodes, a second request to make a reservation for the particular task and to compute a second score that represents an ability of the highest-ranked computing node to take the particular task; 
 receiving, by the first resource allocator from the highest-ranked computing node, a computed second score that represents an ability of the highest-ranked computing node to take the particular task; 
 determining that a difference between the first score received from the highest-ranked computing node and the second score received from the highest-ranked computing node satisfies a threshold; and 
 assigning the particular task to the highest-ranked computing node if and only if the difference between the first score received from the highest-ranked computing node and the second score received from the highest-ranked computing node satisfies the threshold. 
 
     
     
       20. The computer program product of  claim 19 , the operations further comprising restarting, by a resource allocator, a resource allocation process for a second task if a difference between a first score for the second task and a second score for the second task does not satisfy the threshold. 
     
     
       21. The computer program product of  claim 20 , wherein restarting the resource allocation process comprises providing, to each of the plurality of computing nodes, a request to recompute the first score for the second task.