EdgeScaler: effective elastic scaling for graph stream processing systems

Existing solutions for elastic scaling perform poorly with graph stream processing for two key reasons. First, when the system is scaled, the graph must be dynamically re-partitioned among workers. This requires a partitioning algorithm that is fast and offers good locality, a task that is far from being trivial. Second, existing modelling techniques for distributed graph processing systems only consider hash partitioning, and do not leverage the semantic knowledge used by more efficient partitioners. In this paper we propose EdgeScaler, an elastic scaler for graph stream processing systems that tackles these challenges by employing, in a synergistic way, two innovative techniques: MicroMacroSplitter and AccuLocal. MicroMacroSplitter is a new edge-based graph partitioning strategy that is as fast as simple hash partinioners, while achieving quality comparable to the best state-of-the-art solutions. AccuLocal is a novel performance model that takes the partitioner features into account while avoiding expensive off-line training phases. An extensive experimental evaluation offers insights on the effectiveness of the proposed mechanisms and shows that EdgeScaler is able to significantly outperform existing solutions designed for generic stream processing systems.