TAP: Timeliness‐aware predication‐based replica selection algorithm for key‐value stores. (5th February 2019)

• Record Type: Journal Article
• Authors: Zhou, Xianqian; Fang, Liyuan; Xie, Haiming; Jiang, Wanchun
• Is Part Of: Concurrency and computation. Volume 31:Number 17(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-02-05
• Subjects: key‐value stores -- prediction -- tail latency -- timeliness; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5171
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: In current large‐scale distributed key‐value stores, a single end‐user request may lead to key‐value access across tens or hundreds of servers. The tail latency of these key‐value accesses is crucial to user experience and greatly impacts the revenue. To cut the tail latency, it is crucial for clients to choose the best replica server as much as possible for the service of each key‐value access operation. Aware of the challenges on the time‐varying performance across servers and the herd behaviors, an adaptive replica selection scheme C3 has been proposed recently. In C3, feedback from individual servers is brought into replica ranking to reflect the time‐varying performance of servers, and the distributed rate control and backpressure mechanisms are invented. Despite C3's good performance, we reveal the timeliness issue of C3, which has large impacts on both the replica ranking and the rate control. To address this issue, we propose the TAP (timeliness‐aware predication‐based) replica selection algorithm, which predicts the queue size of replica servers under the poor timeliness condition, instead of utilizing the exponentially weighted moving average of the piggybacked queue sizes in history as in C3. Consequently, compared with C3, TAP can obtain more accurate queue‐size estimation to guide the replica selection at clients. Simulation results also confirm the advantage of TAP over C3 in terms of cutting the tail latency.