High Availability for VM Placement and a Stochastic Model for Multiple Knapsack

k-HA (high-Availability) is an important faulttolerance property of VM placement in clouds and clusters - it is the ability to tolerate up to k host failures by relocating VMs from failed hosts without disrupting other VMs. It has long been assumed [1] that deciding the existence of a k-HA placement is ΣP 3 -hard. In a surprising yet simple result we show that k-HA reduces to multiple knapsack and hence is in NP= ΣP 1 . We propose a stochastic model for multiple knapsack that not only captures real-world workloads but also provides a uniform basis for comparing the efficiencies of different polynomial-time heuristics. We prove, using the central limit theorem and linear programming, that, there exists a best polynomial-time heuristic, albeit impractical from the standpoint of implementation. We turn to industry practice and discuss the drawbacks of commonly used heuristics-First- fit,Best-fit,Worst-fit,MTHM and CSP. Load-balancing is a fundamental customer requirement in industry. Based on a large real-world dataset of cluster workloads (from industry leader Nutanix) we show that the natural load-balancing heuristic - Water- filling - has several excellent properties. We compare and contrast Water-filling with MTHM using our stochastic model and find that Water-filling is a heuristic of choice.