Highly available, fault-tolerant, parallel dataflows

We present a technique that masks failures in a cluster to provide high availability and fault-tolerance for long-running, parallelized dataflows. We can use these dataflows to implement a variety of continuous query (CQ) applications that require high-throughput, 24x7 operation. Examples include network monitoring, phone call processing, click-stream processing, and online financial analysis. Our main contribution is a scheme that carefully integrates tradi-tional query processing techniques for partitioned parallelism with the process-pairs approach for high availability. This delicate inte-gration allows us to tolerate failures of portions of a parallel dataflow without sacrificing result quality. Upon failure, our technique pro-vides quick fail-over, and automatically recovers the lost pieces on the fly. This piecemeal recovery provides minimal disruption to the ongoing dataflow computation and improved reliability as compared to the straight-forward application of the process-pairs technique on a per dataflow basis. Thus, our technique provides the high availability necessary for critical CQ applications. Our techniques are encapsulated in a reusable dataflow operator called Flux, an extension of the Exchange that is used to compose par-allel dataflows. Encapsulating the fault-tolerance logic into Flux minimizes modifications to existing operator code and relieves the burden on the operator writer of repeatedly implementing and ver-ifying this critical logic. We present experiments illustrating these features with an implementation of Flux in the TelegraphCQ code base [8]. 1