Distributed key-value stores provide the Multiget API, where many key-value operations are batched together, to meet the parallel requirement of applications. Correspondingly, reducing the latency of Multigets is crucial for the responsiveness of the distributed key-value stores. The latency of a Multiget depends on both which replica server its key-value operations are scheduled to, i.e., the replica selection for each key-value operation, and when these key-value operations are served, i.e., the scheduling of the service sequence at different replica servers. Existing solutions solely focus on either one of them and accordingly lead to suboptimal latency for Multigets. To address these issues, this paper proposes an Adaptive Multiget Scheduling (AMS) algorithm in this paper, and specifically, our AMS re-architectures the framework to remove the conflict between replica selection and service sequence scheduling in the existing solution Rein. Based on the new framework, a sophisticated replica selection method is designed. Furthermore, AMS guides both replica selection and service sequence scheduling by the piggybacked information of replica servers, being adaptive to the heterogeneous time-varying server performance. Consequently, AMS can respectively reduce the median,$95^{th}$, and$99^{th}$percentile latencies of Multigets by a factor of 4, 3.1, and 1.86 compared to the default FIFO algorithm and significantly outperforms Rein.

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).

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.

We prove that if N is an internally 4‐connected minor of an internally 4‐connected binary matroid M with $E(N) \geq 4$, then there exist matroids $M_0, M_1, \ldots, M_n$ such that $M_0 \cong N$, $M_n = M$, and, for each $i\in\{1,\ldots,i\}$, $M_{i-1}$ is a minor of $M_{i}$, $|E(M_{i-1})|\ge |E(M_i)|-2$, and $M_i$ is 4‐connected up to separators of size 5.