AMS: Adaptive Multiget Scheduling Algorithm for Distributed Key-Value Stores

Wanchun Jiang

doi:10.1109/TCC.2022.3218582

Return

AMS: Adaptive Multiget Scheduling Algorithm for Distributed Key-Value Stores

2023-07-01

PRE

DOI：10.1109/TCC.2022.3218582

Original

Original request for help

Save

Abstract

En 中文

Distributed key-value stores provide the Multiget API, where many key-value operations are batched together, to meet the parallel requirement of applications. Correspondingly, reducing the latency of Multigets is crucial for the responsiveness of the distributed key-value stores. The latency of a Multiget depends on both which replica server its key-value operations are scheduled to, i.e., the replica selection for each key-value operation, and when these key-value operations are served, i.e., the scheduling of the service sequence at different replica servers. Existing solutions solely focus on either one of them and accordingly lead to suboptimal latency for Multigets. To address these issues, this article proposes an Adaptive Multiget Scheduling (AMS) algorithm in this article, and specifically, our AMS re-architectures the framework to remove the conflict between replica selection and service sequence scheduling in the existing solution Rein. Based on the new framework, a sophisticated replica selection method is designed. Furthermore, AMS guides both replica selection and service sequence scheduling by the piggybacked information of replica servers, being adaptive to the heterogeneous time-varying server performance. Consequently, AMS can respectively reduce the median, 95th, and 99th percentile latencies of Multigets by a factor of 4, 3.1, and 1.86 compared to the default FIFO algorithm and significantly outperforms Rein.

Keywords:

Key-value store

multiget

scheduling

replica selection

latency