Rein: Taming Tail Latency in Key-Value Stores via Multiget Scheduling

Waleed Reda, Marco Canini, Lalith Suresh, Dejan Kostić, Sean Braithwaite

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Citations (SciVal)


We tackle the problem of reducing tail latencies in distributed key-value stores, such as the popular Cassandra database.We focus on workloads of multiget requests, which batch together access to several data elements and parallelize read operations across the data store machines. We first analyze a production trace of a real system and quantify the skew due to multiget sizes, key popularity, and other factors. We then proceed to identify opportunities for reduction of tail latencies by recognizing the composition of aggregate requests and by carefully scheduling bottleneck operations that can otherwise create excessive queues. We design and implement a system called Rein, which reduces latency via inter-multiget scheduling using low overhead techniques. We extensively evaluate Rein via experiments in Amazon Web Services (AWS) and simulations. Our scheduling algorithms reduce the median, 95, and 99 percentile latencies by factors of 1.5, 1.5, and 1.9, respectively.
Original languageEnglish (US)
Title of host publicationProceedings of the Twelfth European Conference on Computer Systems - EuroSys '17
PublisherAssociation for Computing Machinery (ACM)
Number of pages16
ISBN (Print)9781450349383
StatePublished - Apr 17 2017


Dive into the research topics of 'Rein: Taming Tail Latency in Key-Value Stores via Multiget Scheduling'. Together they form a unique fingerprint.

Cite this