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