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.

By: Joel Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu, Lisa Fleischer

Published in: RC24911 in 2009


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .