The last decade has witnessed an unprecedented growth in the demand for data-driven real-time services. These services are fueled by emerging applications that require rapidly injecting data streams and computing updated analytics results in real-time. In many of such applications, the computing resources are often shared for processing both updates from information sources and queries from end users. This requires joint scheduling of updates and queries because the service provider needs to make a critical decision upon receiving a user query: either it responds immediately with currently available but possibly stale information, or it first processes new updates and then responds with fresher information. Hence, the tradeoff between service performance and information freshness naturally arises in this context. To that end, we propose a simple single-server two-queue model that captures the coupled scheduling of updates and queries and aim to design scheduling policies that can properly address the important tradeoff between performance and freshness. Specifically, we consider the response time as a performance metric and the Age of Information (AoI) as a freshness metric. After demonstrating the limitations of the simplest FCFS policy, we propose two threshold-based policies: the Query-k policy that prioritizes queries and the Update-k policy that prioritizes updates. Then, we rigorously analyze both the response time and the Peak AoI (PAoI) of the threshold-based policies. Further, we propose the Joint-(M,N) policy, which allows flexibly prioritizing updates or queries through choosing different values of two thresholds M and N. Finally, we conduct simulations to evaluate the response time and the PAoI of the proposed policies. The results show that our proposed threshold-based policies can effectively control the balance between performance and freshness.
Despite the aforementioned studies on service performance and information freshness, the tradeoff between them has often been neglected in the literature (partially due to the nature of the considered applications), except for the following limited work. In @cite_3 , the tradeoff of performance and freshness has been considered for database-driven web servers, where the goal is to optimize performance under the freshness constraint. The work of @cite_4 proposes to combine performance and freshness into a single compound metric and addresses the tradeoff between them through optimizing the compound metric. Further, the work of @cite_4 has been extended to account for user preference for performance and freshness @cite_16 . In stark contrast to these studies that provide heuristic solutions only, in this paper we aim to systematically understand this tradeoff by providing theoretical results with rigorous analysis.
@cite_16 @cite_4 @cite_3
2145068111 2137536766 2031513076
Typical Web-database systems receive read-only queries, that generate dynamic Web pages as a response, and write-only updates, that keep information up-to-date. Users expect short response times and low staleness. However, it may be extremely hard to apply all updates on time, i.e., keep zero staleness, and also get fast response times, especially in periods of bursty traffic. In this paper, we present the concept of quality contracts (QCs) which combines the two incomparable performance metrics: response time or quality of service (QoS), and staleness or quality of data (QoD). QCs allows individual users to express their preferences for the expected QoS and QoD of their queries by assigning "profit" values. To maximize the total profit from submitted QCs, we propose an adaptive algorithm, called QUTS. QUTS addresses the problem of prioritizing the scheduling of updates over queries using a two-level scheduling scheme that dynamically allocates CPU resources to updates and queries according to user preferences. We present the results of an extensive experimental study using real data (taken from a stock information Web site), where we show that QUTS performs better than baseline algorithms under the entire spectrum of QCs; QUTS also adapts fast to changing workloads. Web-database systems are nowadays an integral part of everybodys life, with applications ranging from monitoring trading stock portfolios, to personalized blog aggregation and news services, to personalized weather tracking services. For most of these services to be successful (and their users to be kept satisfied), two criteria need to be met: user requests must be answered in a timely fashion and using fresh data. This paper presents a framework to balance both requirements from the users perspective. Toward this, we propose a user satisfaction metric to measure the overall effectiveness of the Web-database system. We also provide a set of algorithms to dynamically optimize this metric, through query admission control and update frequency modulation. Finally, we present extensive experimental results which compare our proposed algorithms to the current state of the art and show that we outperform competitors under various workloads (generated based on real traces) and user requirements. Personalization, advertising, and the sheer volume of online data generate a staggering amount of dynamic Web content. In addition to Web caching, view materialization has been shown to accelerate the generation of dynamic Web content. View materialization is an attractive solution as it decouples the serving of access requests from the handling of updates. In the context of the Web, selecting which views to materialize must be decided online and needs to consider both performance and data freshness, which we refer to as the online view selection problem. In this paper, we define data freshness metrics, provide an adaptive algorithm for the online view selection problem that is based on user-specified data freshness requirements, and present experimental results. Furthermore, we examine alternative metrics for data freshness and extend our proposed algorithm to handle multiple users and alternative definitions of data freshness.