Spatiotemporal Load Balancing for Near-Memory Accelerated Databases by Partial Resharding

Abstract

Near-memory acceleration, where a large number of compute nodes with limited memory process data in parallel, is a promising approach for in-memory databases. Therein, partitioning is required to balance data and queries for skewed workloads. However, existing load balancing methods lack efficient support for dynamic workload changes. As an instance, query density-driven partitioning statically refers to the reference workload to find hot ranges of data and distributes them over less busy nodes. In this paper, we propose an extension of query density-driven partitioning to support dynamically changing workloads. We distribute hot ranges to a limited number of nodes as long as theoretical worst-case load balance is maintained, reserving less busy nodes for hot ranges to appear in future. This approach enables us to restore load balancing with small amortized overhead for dynamic workloads. Our experiments have confirmed that our approach can handle more frequent changes in the workload than query density-driven partitioning. We have also achieved significantly higher throughput with our approach than PIM-tree, a skew-resistant state-of-the-art data structure, during periods without workload changes.