Stall‐Free Asynchronous State Repartitioning With a Proactive Workload Tracking Window

ABSTRACT High‐throughput stateful applications rely on dynamic data repartitioning to adapt to changing workloads, but this process presents significant challenges. This paper provides a detailed analysis of such challenges, drilling down into the tradeoffs between adaptation, computational overhead, and service availability. We identify that a primary limitation of common rebalancing methods is their need to halt request processing during the repartitioning computation, which preserves consistency but introduces disruptive downtime. To overcome this limitation, we present a fully asynchronous repartitioning strategy that eliminates service interruptions by executing the rebalancing logic in the background, decoupled from the main scheduling thread. We further enhance this with a novel workload tracking window, which allows the system to generate proactive partition maps based on upcoming requests, making the adaptation more timely and relevant. Our experimental results demonstrate the strengths of this approach. The asynchronous strategy is shown to be a robust, high‐performance alternative that remains competitive even in workloads where it is not the top performer. In synchronization‐intensive scan workloads, the combination of our techniques proved superior, reducing the makespan by up to over a multithreaded round‐robin baseline. Our analysis also reveals that the tracking window improves the robustness of traditional rebalancing schemes by making them less sensitive to parameter tuning. Our work thus presents a comprehensive framework for building highly adaptive systems without sacrificing availability.