In distributed key-value stores, multiple replica servers are always available for each key-value access operation when the eventual consistency model is employed. Accordingly, the completion times of the key-value access operations generated by an end-user request at different servers may be of great difference, especially when the replica servers are heterogeneous and have time-varying performance. Accordingly, the replica selection algorithm is crucial to cut the response time of end-user requests. The main challenge of making replica selection for each light-weighted key-value access operation is to timely know the status of replica serves. Recently, the adaptive replica selection algorithm C3 suggests guiding the replica selection with the piggybacked information of replica server in the returned “value”. Although C3 has good performance, the poor timeliness of feedback information makes a large performance gap between C3 and the ideal replica selection algorithm. To narrow this gap, the Accelerated Information Dissemination (AID) mechanism is proposed in this paper. Specifically, AID removes the bottleneck of information dissemination at the “slow” servers by letting both “client” and “replica server” store the records about the status of replica servers and both “key” and “value” piggyback multiple records. AID is implemented in Cassandra and evaluated by experiments and large scale simulations. The results show AID can significantly improve the timeliness of feedback information, especially when the number of nodes is large. Accordingly, AID helps C3 to greatly reduce the latency.

In distributed key-value stores, multiple replica servers are always available for each key-value access operation when the eventually consistency model is employed. Accordingly, the replica selection algorithm is crucial to the tail latency of the key-value access operations generated by end-user requests, especially under the environment of heterogeneous replica servers. The main challenge of making replica selection decision is to know the status of replica serves with acceptable overhead for each lightweight key-value access operation. Recently, aware of the time-varying performance and load of replica servers, the adaptive replica selection algorithm C3 suggests piggybacking the information of replica server via the returned value” to guide the replica selection. Although the good performance of C3 has been verified by experiments and simulations, the poor timeliness of feedback information makes a large performance gap between C3 and the ideal replica selection algorithm. To narrow this gap, we propose the information dissemination mechanism for C3, which lets both “client” and “server” store the records about the status of replica servers, and both key” and value” piggyback multiple records. In this way, the information dissemination bottleneck at “slow” server would be removed with the help of multiple clients and servers. As confirmed by simulation results, the information dissemination mechanism can significantly improve the timeliness of feedback information with acceptable overhead and accordingly helps C3 to greatly reduce the tail latency (by about 35% under the default scenario).

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.

In current large-scale distributed key-value stores for cloud computing, the tail latency of the hundreds of key-value accesses generated by an end-user request determines the response time of this request. Replica selection algorithms, which select the best replica server for each key-value access as much as possible, is crucial to reduce the tail latency. This paper summarizes current replica selection algorithms and classifies them into three categories: information-agnostic, client-independence and feedback, according to their demanded information. Furthermore, simulation-based performance analysis of these algorithms is conducted. Based on the insights obtained from performance analysis, we design the L2 algorithm by assembling the basic ideas of the Least OSK algorithm and the Least RPT algorithm. The L2 algorithm has similar best performance with the recently proposed C3 algorithm, but is much simpler than C3.

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 the 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. Aware of the challenges on the time-varying performance across servers and the herd behaviors, an adaptive replica selection scheme C3 is 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 mechanism is invented. Despite of C3's good performance, we reveal the timeliness issue of C3, which has large impacts on both the replica ranking and the rate control, and propose the Tars (timeliness-aware adaptive replica selection) scheme. Following the same framework as C3, Tars improves the replica ranking by taking the timeliness of the feedback information into consideration, as well as revises the rate control of C3. Simulation results confirm that Tars outperforms C3.