TD-Orch: Efficient Task-Data Orchestration for Distributed Systems with Application to Graph Processing

Abstract

We introduce a task-data orchestration abstraction that supports a range of distributed applications. Given a batch of lambda tasks each requesting a data item, where both tasks and data are distributed across multiple machines, each task must be co-located with its target data (by moving tasks and/or data) and then executed. We present TD-Orch, an efficient lambda-task-centric orchestration framework for low-overhead load balancing with a simple interface for application developers. TD-Orch employs a distributed push-pull technique, leveraging the bidirectional flow of both tasks and data to achieve load balance across machines even under highly skewed access patterns, with low communication overhead. Experimental results on key-value stores show that TD-Orch achieves up to $2.8\times$ speedup over existing distributed scheduling baselines. Building on TD-Orch, we present TDO-GP, a distributed graph processing system with $4.1\times$ average speedup over state-of-the-art open-source distributed graph systems for general graph processing.