HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Taming Tail Latency in Key-Value Stores: a Scheduling Perspective (extended version)

Abstract : Distributed key-value stores employ replication for high availability. Yet, they do not always efficiently take advantage of the availability of multiple replicas for each value, and read operations often exhibit high tail latencies. Various replica selection strategies have been proposed to address this problem, together with local request scheduling policies. It is difficult, however, to determine what is the absolute performance gain each of these strategies can achieve. We present a formal framework allowing the systematic study of request scheduling strategies in key-value stores. We contribute a definition of the optimization problem related to reducing tail latency in a replicated key-value store as a minimization problem with respect to the maximum weighted flow criterion. By using scheduling theory, we show the difficulty of this problem, and therefore the need to develop performance guarantees. We also study the behavior of heuristic methods using simulations, which highlight which properties are useful for limiting tail latency: for instance, the EFT strategy-which uses the earliest available time of servers-exhibits a tail latency that is less than half that of state-of-the-art strategies, often matching the lower bound. Our study also emphasizes the importance of metrics such as the stretch to properly evaluate replica selection and local execution policies.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.inria.fr/hal-03144818
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Friday, March 12, 2021 - 11:47:45 AM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM

File

report.pdf
Files produced by the author(s)

Identifiers

Citation

Sonia Ben Mokhtar, Louis-Claude Canon, Anthony Dugois, Loris Marchal, Etienne Rivière. Taming Tail Latency in Key-Value Stores: a Scheduling Perspective (extended version). 2021. ⟨hal-03144818v2⟩

Share

Metrics

Record views

182

Files downloads

404