Mitigating Dual Load Imbalance via Dynamic Cooperative Scheduling in Distributed Key-Value Stores

Distributed key-value (KV) stores are essential components of modern computing infrastructure, enabling efficient storage and management of large-scale datasets. Existing distributed KV stores often shard data by key ranges into multiple regions and distribute the regions across multiple nodes. However, such range-based sharding leads to load imbalance in two dimensions: CPU utilization and disk I/O bandwidth. Our analysis reveals that the two dimensions exhibit misaligned and dynamic behaviors. Moreover, their tight coupling, where scheduling one dimension affects the other, makes it more challenging to simultaneously achieve balance in both. To address this challenge, which we term dual load imbalance, we propose Libra, a cooperative scheduling framework that monitors the interactions of CPU and disk I/O loads and carefully migrates regions across nodes based on the critical dimension. We implement Libra atop TiKV, a production distributed KV store, and show that Libra increases throughput by up to 72.1% and reduces tail latency by up to 56.7% compared to state-of-the-art approaches. ①query region containing KV Client ` N 1 N 2 N 3 N n KV ••• KV KV KV KV ••• • • • • • • • • • • • • KV ••• KV Raft Group •••