Efficient parallel processing and fault tolerance in a streaming join system

Abstract

Stream joins are an important component of stream processing, as they provide an online mechanism to efficiently combine multiple streams of data. In this thesis, we consider the RiverJoin system, which presents a general method for performing stream joins without relying on the ordering and timing of records in a stream. RiverJoin implements a useful set of primitives, called operands, that provide persistence and caching, allowing full-history stream joins. RiverJoin implements critical performance optimizations like batching and automatic parallelization, having performance comparable to lossy windowed joins while maintaining its strong correctness semantics. The individual contributions of the thesis come from further extending RiverJoin by adding functionality required for an end-to-end distributed system, specifically sharding and fault tolerance. In particular, we are able to leverage RiverJoin's automatic parallelization mechanism to provide a data stream sharding interface that allows for close-to linear speedup in stream joins, allowing arbitrarily fast joins. Stream processing systems require high throughput and low latency in order to provide real-time guarantees. Traditional methods of periodic global snapshots provide fault recovery at the cost of pausing the entire system during the snapshot process and persisting records in transit, leading to large snapshot sizes. In this thesis, we present a low-latency mechanism to snapshot a RiverJoin topology asynchronously, providing consistent system recovery and exactly-once delivery semantics between its operands. The method builds upon the idea of Asynchronous Barrier Snapshotting (ABS) and a novel asynchronous backup strategy, called fork-backup, that can snapshot an operand with gigabytes of state in milliseconds. Our results show that we can take snapshots without affecting system latency and throughput even with frequent snapshotting. We are also able to issue and complete a global snapshot for a complex RiverJoin topology in around 50ms, faster than a Java GC pause, and can recover from failure in less than a second.