Memory-Efficient Database Fragment Allocation for Robust Load Balancing when Nodes Fail
Stefan Halfpap, Rainer Schlößer · 2021
Load balancing queries that access the same data fragments to the same node improves caching for a memory-efficient scale-out. However, to suitably allocate fragments to multiple nodes is a highly challenging problem, particularly when nodes might fail. The problem is to find a good balance between memory efficiency and allocating enough fragments to nodes to obtain robustness through load balancing flexibility. Existing allocation approaches are either not memory-efficient or result in load imbalances, both degrading cost/performance. In this paper, we present an optimal approach and a scalable heuristic, based on three mutually supportive linear programming models, to calculate memory-efficient fragment allocations that guarantee to distribute the workload evenly - even in the case of node failures. We demonstrate the applicability and the effectiveness of our three-step approach using numerical as well as end-to-end evaluations for TPC-H and TPC-DS workloads. We find that our robust solutions clearly outperform state-of-the-art heuristics by achieving a better workload distribution with even less memory.