Scalable scheduling for distributed data processing

摘要

A multi-tier scheduling approach includes a first tier comprising virtual cluster allocators that receive scheduling requests from processes and aggregate those requests and provide them to a second tier, namely a single resource distributor for the entire set of computing devices. The resource distributor, based on the requests from virtual cluster allocators, and also from information received from the computing devices themselves, generates a flow graph to identify an optimal scheduling of the assignment of resources to specific ones of the virtual clusters. Each virtual cluster allocator then, based on the assignment of resources assigned to it by the resource distributor, solves its own flow graph to identify an optimal scheduling of processes on the resources assigned. The scheduling of processes is performed iteratively by initially assigning resources to those processes having a high priority, and then, in subsequent iterations, assigning opportunistic resources to those processes having a lower priority.

主权项

1. One or more computer-readable memory comprising computer-executable instructions for assigning processing resources, the computer-executable instructions performing steps comprising:
receiving requests for the processing resources from one or more jobs, each job comprising one or more processes to be executed by the processing resources; generating a flow graph comprising a source, a sink, resource nodes for each of the processing resources, job nodes for each of the one or more jobs and process nodes for each of the one or more processes; generating at least one aggregated request from at least some of the received requests; transmitting the at least one aggregated request; receiving, in response to the transmitting, an assignment of at least some of the processing resources; generating edges in the flow graph to the sink from only the resource nodes representing the assigned processing resources; solving the flow graph; and assigning the processing resources to the one or more jobs in accordance with the flow graph solution.