Consistent Low Latency Scheduler for Distributed Key-Value Stores

Wanchun Jiang

doi:10.1109/TPDS.2023.3315777

Consistent Low Latency Scheduler for Distributed Key-Value Stores

2023-12-01

0

PRE

AI

DOI：10.1109/TPDS.2023.3315777

原文链接

原文求助

摘要

En 中文

Nowadays, the distributed key-value stores have be -come the basic building block for large-scale cloud applications. In large-scale distributed key-value stores, many key-value access operations, which will be processed in parallel on different servers, are usually generated for a single end-user request. Accordingly, the completion time of an end-user request is determined by the last completed key-value access operation. Scheduling the order of serving key-value access operations can effectively reduce the completion times of end requests, thereby improving the user ex-perience. However, existing scheduling algorithms hardly achieve consistent low latency due to the following challenges: the large overhead of cooperating clients and servers, the time-varying load and performance of servers, the traffic distribution can be either heavy-tailed or light-tailed and both the mean and the tail com-pletion time are expected to be low. In this paper, we formal-ize the problem of scheduling key-value access operations and show it is NP-hard. Furthermore, we heuristically design the dis-tributed adaptive scheduler (DAS), which distributively combines the largest remaining processing time last and the shortest remain-ing process time first algorithms. Theoretical analysis shows that DAS is adaptive to the time-varying traffic and server performance and can achieve consistent low mean and tail latency regardless of traffic distributions. Extensive simulations show that DAS reduces the mean request completion time by 17 similar to 50% with heavy-tailed traffic and 2 similar to 26% with light-tailed traffic, while keeping the smallest tail completion time, compared to the default first come first served algorithm. Moreover, DAS outperforms the existing Rein-SBF algorithm under various scenarios.

Keyword:

Servers

Tail

Lightly-tailed distribution

Heavily-tailed distribution

Scheduling algorithms

Low latency communication

Job shop scheduling

Adaptive

distributed key-value stores

request completion time

scheduling

Consistent Low Latency Scheduler for Distributed Key-Value Stores

摘要

期刊

机构

引用论文