TAP: Timeliness-aware predication-based replica selection algorithm for key-value stores

摘要

In current large-scale distributed key-value stores, a single end-user request may lead tokey-value access across tens or hundreds of servers. The tail latency of these key-value accessesis crucial to user experience and greatly impacts the revenue. To cut the tail latency, it is crucialfor clients to choose the best replica server as much as possible for the service of each key-valueaccess operation. Aware of the challenges on the time-varying performance across servers andthe herd behaviors, an adaptive replica selection scheme C3 has been proposed recently. InC3, feedback from individual servers is brought into replica ranking to reflect the time-varyingperformance of servers, and the distributed rate control and backpressure mechanisms areinvented. Despite C3's good performance, we reveal the timeliness issue of C3, which has largeimpacts on both the replica ranking and the rate control. To address this issue, we propose theTAP (timeliness-aware predication-based) replica selection algorithm, which predicts the queuesize of replica servers under the poor timeliness condition, instead of utilizing the exponentiallyweighted 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 replicaselection at clients. Simulation results also confirm the advantage of TAP over C3 in terms ofcutting the tail latency.