  Resource allocation problems in many computer systems can be formulated as
mathematical optimization problems. However, finding exact solutions to these
problems using off-the-shelf solvers in an online setting is often intractable
for "hyper-scale" system sizes with tight SLAs, leading system designers to
rely on cheap, heuristic algorithms. In this work, we explore an alternative
approach that reuses the original optimization problem formulation. By
splitting the original problem into smaller, more tractable problems for
subsets of the system and then coalescing resulting sub-allocations into a
global solution, we achieve empirically quasi-optimal (within 1.5%) performance
for multiple domains with several orders-of-magnitude improvement in runtime.
Deciding how to split a large problem into smaller sub-problems, and how to
coalesce split allocations into a unified allocation, needs to be performed
carefully in a domain-aware way. We show common principles for splitting
problems effectively across a variety of tasks, including cluster scheduling,
traffic engineering, and load balancing.
