Efficient Distributed Workload (Re-)Embedding

Monika Henzinger, Stefan Neumann, Stefan Schmid

Abstract

Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter. However, dynamically changing the embedding of workloads is algorithmically challenging: communication patterns are often not known ahead of time, but must be learned. During the learning process, overheads related to unnecessary moves (i.e., re-embeddings) should be minimized. This paper studies a fundamental model which captures the tradeoff between the benefits and costs of dynamically collocating communication partners on $\ell$ servers, in an online manner. Our main contribution is a distributed online algorithm which is asymptotically almost optimal, i.e., almost matches the lower bound (also derived in this paper) on the competitive ratio of any (distributed or centralized) online algorithm. As an application, we show that our algorithm can be used to solve a distributed union find problem in which the sets are stored across multiple servers.

1. Introduction

In modern cloud environments and data centers, applications are often scaled out across hundreds or thousands of servers. These components, such as Virtual Machines or containers, generate significant network traffic when communicating across server boundaries. If frequently interacting components are collocated on the same server, this traffic remains local and "free," improving overall system performance.

Dynamic communication requests between workload sets.

However, achieving optimal collocation is difficult because communication patterns are typically unknown in advance and must be learned online. Furthermore, migrating workloads between servers incurs high costs in terms of time and bandwidth. This paper addresses the fundamental tradeoff: determining when the benefit of reducing future communication justifies the immediate cost of migration. The problem is modeled as a graph where vertices are workloads and edges represent communication requests, evaluated against an adversary that generates worst-case request sequences.

2. Algorithmic Framework

The authors propose a distributed online algorithm designed to minimize the competitive ratio—the ratio between the algorithm's cost and that of an optimal offline solution. Key components include:

  • Small-to-Large Moving: A strategy where, upon merging two components, the smaller one is moved to the server of the larger one. This ensures any single workload is moved at most $O(\log n)$ times.
  • Bipartition Tree: Servers are organized into a virtual hierarchy (a balanced binary tree), allowing migration decisions to be made recursively.
  • Majority Voting: To prevent unnecessary "jitter" or frequent moves, a component only migrates to a new branch of the server tree if a majority of its constituent parts vote for that location based on their initial positions.
Partitioning of workload sets $S_0$ and $S_1$ into virtual server groups $V_0$ and $V_1$.
  • Capacity Augmentation: A critical theoretical insight is that competitive online algorithms require a small amount of "slack" or extra space ($\epsilon$) on servers to allow for the shuffling required during the learning process.

3. Theoretical Results and Insights

The primary algorithm achieves a competitive ratio of $O(\frac{\log n \log \ell}{\epsilon})$. The authors also derive a lower bound of $\Omega(1/\epsilon + \log n)$, demonstrating that their algorithm is asymptotically almost optimal. This logic does not require a central controller; servers can make migration decisions by exchanging a relatively small number of messages, making the approach practical for massive-scale systems. Additionally, the paper provides a polynomial-time version of the algorithm with only a minor impact on the competitive ratio.

4. Conclusion and Future Work

This work elegantly links systems engineering challenges to classic computer science theory, specifically the Union-Find data structure and $k$-way partitioning. While the current model assumes fixed communication patterns and uniform component sizes, it provides a robust foundation for future research. Potential extensions include exploring slowly shifting communication patterns and incorporating specific network topologies, such as Clos networks, where communication costs vary between racks and data centers.

Summary updated

Abstract

Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter. However, dynamically changing the embedding of workloads is algorithmically challenging: communication patterns are often not known ahead of time, but must be learned. During the learning process, overheads related to unnecessary moves (i.e., re-embeddings) should be minimized. This paper studies a fundamental model which captures the tradeoff between the benefits and costs of dynamically collocating communication partners on $\ell$ servers, in an online manner. Our main contribution is a distributed online algorithm which is asymptotically almost optimal, i.e., almost matches the lower bound (also derived in this paper) on the competitive ratio of any (distributed or centralized) online algorithm. As an application, we show that our algorithm can be used to solve a distributed union find problem in which the sets are stored across multiple servers.
BibTeX
@inproceedings{henzinger2019efficient,
  author = {Monika Henzinger and Stefan Neumann and Stefan Schmid},
  title = {{Efficient Distributed Workload (Re-)Embedding}},
  booktitle = {Proc. ACM Meas. Anal. Comput. Syst},
  year = {2019},
  url = {https://openreview.net/forum?id=KHVRO2edv2},
}
Figure