The SODA Optimizing Scheduler for System S

This paper describes SODA, a scheduler for System S. System S is a highly scalable distributed computer system designed to handle complex applications processing enormous quantities of streaming data. Unlike traditional batch applications, streaming applications are open-ended. The system cannot typically delay the processing of the data. The scheduler must be able admit or reject jobs. It must be able to assign and reassign resource allocations dynamically in response to changes in resource availability, incoming data rates, the relative importance of the work, as well as job arrivals and departures, and so on. The design assumptions of System S, in particular, pose additional scheduling challenges. SODA must deal with a highly complex optimization problem involving numerous real-world constraints, which must be solved in real-time while maintaining scalability. SODA relies on a careful problem decomposition, and intelligent use of both heuristic and exact algorithms. This paper is intended to be as complete a description of SODA as is reasonably practical. We describe the design and functionality of SODA, give overviews and extensive details of the four major mathematical components, as well as three key input data infrastructure components. We present experiments to show the performance of the scheduler.