Adaptive query scheduling in key-value data stores

Chen Xu, Mohamed Sharaf, Minqi Zhou, Aoying Zhou, Xiaofang Zhou

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

6 Citations (Scopus)


Large-scale distributed systems such as Dynamo at Amazon, PNUTS at Yahoo!, and Cassandra at Facebook, are rapidly becoming the data management platform of choice for most web applications. Those key-value data stores rely on data partitioning and replication to achieve higher levels of availability and scalability. Such design choices typically exhibit a trade-off in which data freshness is sacrificed in favor of reduced access latencies. Hence, it is indispensable to optimize resource allocation in order to minimize: 1) query tardiness, i.e., maximize Quality of Service (QoS), and 2) data staleness, i.e., maximize Quality of Data (QoD). That trade-off between QoS and QoD is further manifested at the local-level (i.e., replica-level) and is primarily shaped by the resource allocation strategies deployed for managing the processing of foreground user queries and background system updates. To this end, we propose the AFIT scheduling strategy, which allows for selective data refreshing and integrates the benefits of SJF-based scheduling with an EDF-like policy. Our experiments demonstrate the effectiveness of our method, which does not only strike a fine trade-off between QoS and QoD but also automatically adapts to workload settings.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 18th International Conference, DASFAA 2013, Proceedings
Number of pages15
EditionPART 1
Publication statusPublished - 2013
Externally publishedYes
Event18th International Conference on Database Systems for Advanced Applications, DASFAA 2013 - Wuhan, China
Duration: Apr 22 2013Apr 25 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7825 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Database Systems for Advanced Applications, DASFAA 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Adaptive query scheduling in key-value data stores'. Together they form a unique fingerprint.

Cite this