High performance architectures for processing distributed data
streams, such as Flink, Spark Streaming, and Storm, are increasingly deployed in
emerging data-driven computing systems. Exploiting the parallelism
afforded by such platforms, while preserving the semantics of the
desired computation, is prone to errors, and motivates the development
of tools for specification, testing, and verification. We focus on the
problem of differential output testing for distributed stream processing
systems, that is, checking whether two implementations produce
equivalent output streams in response to a given input stream. The
notion of equivalence allows reordering of logically independent data
items, and the main technical contribution of the paper is an optimal
online algorithm for checking this equivalence. Our testing framework
is implemented as a library called DiffStream in Flink.
We present four case studies to illustrate how our framework can be
used to (1) correctly identify bugs in a set of benchmark MapReduce programs,
(2) facilitate the development of
difficult-to-parallelize high performance applications, and (3)
monitor an application for a long period of time with minimal performance overhead.