Performance Analysis and Improvement of Replica Selection Algorithms for Key-Value Stores

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.