  Most online service providers deploy their own data stream processing systems
in the cloud to conduct large-scale and real-time data analytics. However, such
systems, e.g., Apache Heron, often adopt naive scheduling schemes to distribute
data streams (in the units of tuples) among processing instances, which may
result in workload imbalance and system disruption. Hence, there still exists a
mismatch between the temporal variations of data streams and such inflexible
scheduling scheme designs. Besides, the fundamental benefits of predictive
scheduling to data stream processing systems also remain unexplored. In this
paper, we focus on the problem of tuple scheduling with predictive service in
Apache Heron. With a careful choice in the granularity of system modeling and
decision making, we formulate the problem as a stochastic network optimization
problem and propose POTUS, an online predictive scheduling scheme that aims to
minimize the response time of data stream processing by steering data streams
in a distributed fashion. Theoretical analysis and simulation results show that
POTUS achieves an ultra-low response time with queue stability guarantee.
Moreover, POTUS only requires mild-value of future information to effectively
reduce the response time, even with mis-prediction.
