Lightweight Asynchronous Repartitioning for Local State Partitioned Systems

Partitioning strategies combined with rebalancing algorithms can be used to balance the load in high-throughput systems. Keeping the load balanced constantly is desirable, but the cost of repartitioning can be high. This work presents a rebalancing strategy based on balanced graph partitioning algorithms with low impact during rebalancing operations. The new technique allows for frequent partitioning updates by decoupling the repartitioning process from the rest of the system, thereby avoiding disruptions within the system due to the calculation of new partitioning schemas. In experimental evaluation, the proposed strategy, implemented in an in-memory key-value store prototype, eliminated scheduler pauses and increased throughput by 19% in workloads predominantly composed of scanning requests.