Consistent Low Latency Scheduler for Distributed Key-Value Stores
Consistent Low Latency Scheduler for Distributed Key-Value Stores
复制标题
DOI：
10.1109/tpds.2023.3315777
复制
发表时间：
2023-12
影响因子：
5.3
通讯作者：
Wanchun Jiang;Haoyang Li;Yulong Yan;Fa Ji;Jiawei Huang;Jianxin Wang;Tong Zhang
中科院分区：
文献类型：
--
作者：
Wanchun Jiang;Haoyang Li;Yulong Yan;Fa Ji;Jiawei Huang;Jianxin Wang;Tong Zhang
如今，分布式键值存储已成为大规模云应用的基本构建块。在大规模的分布式键值存储中，对于一个最终用户请求，通常会产生多个键值访问操作，这些操作将在不同的服务器上并行处理。因此，最终用户请求的完成时间由最后完成的键值访问操作确定。调度服务键值访问操作的顺序可以有效地减少结束请求的完成时间，从而改善用户体验。然而，现有的调度算法很难实现一致的低延迟，由于以下挑战：合作的客户端和服务器的大开销，随时间变化的负载和服务器的性能，流量分布可以是重尾或轻尾，平均和尾部完成时间都期望是低的。在本文中，我们形式化的调度问题的关键值访问操作，并表明它是NP-难的。在此基础上，我们设计了分布式自适应调度器（DAS），它将最大剩余处理时间算法和最短剩余处理时间算法分布式地结合起来。理论分析表明，DAS是适应时变的流量和服务器的性能，可以实现一致的低平均和尾部延迟，而不管流量分布。广泛的模拟表明，DAS减少了平均请求完成时间$17 \！sim！50\%$17 - 50%，重尾流量和$2 \！“sim 26”！与默认的先到先服务算法相比，在保持最小尾部完成时间的情况下，轻尾流量减少了26%。此外，DAS优于现有的Rein-SBF算法在各种情况下。
Nowadays, the distributed key-value stores have become 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 experience. 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 completion time are expected to be low. In this paper, we formalize the problem of scheduling key-value access operations and show it is NP-hard. Furthermore, we heuristically design the distributed adaptive scheduler (DAS), which distributively combines the largest remaining processing time last and the shortest remaining 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 \! \sim \! 50\%$17∼50% with heavy-tailed traffic and $2 \! \sim 26 \! \%$2∼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.