Problem overview

How to define the quality-aware scheduling problem in key-value stores is the foundation of studying the scheduling strategies. In this chapter (Part of this chapter are reprinted from Xu et al., Distrib Parallel Databases 32(4):535–581, 2014 [1], with kind permission from Springer Science+Business Media.), with a comprehensive analysis on data organization, data replication, and consistency, user queries as well as system updates, we first model the asynchronous update in distributed key-value stores and highlight the difference between state-transfer and operation-transfer updates. Then, we employ a series of parameters to specify users’ expectation on QoS and QoD, and propose tardiness on query and staleness of data to measure the satisfaction of users’ requirement on QoS and QoD. Hence, motivated by the idea that penalties are incurred if the system cannot meet user prespecified expectation, we formally define our quality-aware scheduling problem in key-value stores since optimizing QoS and QoD is equivalent to minimizing penalties incurred. In the following, Sect. 3.1 introduces preliminaries about key-value stores and models the data access processing; Sect. 3.2 defines the metrics to qualify QoS and QoD, so as to formally illustrate quality-aware scheduling in key-value stores; Sect. 3.3 summarizes this chapter.