Quality-aware schedulers for weak consistency key-value data stores

Chen Xu, Mohamed A. Sharaf, Xiaofang Zhou, Aoying Zhou

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


Highly distributed NoSQL key-value data stores are rapidly becoming the favorite choice for hosting modern web applications. Such platforms rely on data partitioning, replication and relaxed consistency to achieve high levels of performance and scalability. However, these design choices often exhibit a trade-off between latency (i.e., Quality of Service (QoS)) and consistency (i.e., Quality of Data (QoD)). In this work, in addition to latency-based SLAs, we also adopt the application tolerance to data staleness as another requirement determining the end-user satisfaction and our goal is to strike a fine balance between both the QoS and QoD provided to the end-user. Towards achieving that goal, we propose a suite of quality-aware schedulers for efficiently allocating the necessary computational resources between the foreground user-queries and the background system-updates at data store nodes. This suite of schedulers features our proposed Freshness/Tardiness (FIT) mechanism, which introduces a novel selective approach for scheduling the execution of queries and updates. Our experimental results show that FIT provides significant improvements in balancing the trade-off between QoS and QoD under both the state-transfer and operation-transfer update propagation models employed in current key-value data stores.

Original languageEnglish
Pages (from-to)535-581
Number of pages47
JournalDistributed and Parallel Databases
Issue number4
Publication statusPublished - Dec 2013
Externally publishedYes


  • Consistency
  • Distributed database
  • FLA
  • Key-value data stores
  • NoSQL
  • Quality of data
  • Quality of service
  • SLA
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Information Systems and Management


Dive into the research topics of 'Quality-aware schedulers for weak consistency key-value data stores'. Together they form a unique fingerprint.

Cite this