Obtaining and Managing Answer Quality for Online Data-Intensive Services
Jaimie Kelley, Christopher Stewart, Nathaniel Morris, Devesh Tiwari, Yuxiong He, Sameh Elnikety · ACM Transactions on Modeling and Performance Evaluation of Computing Systems · 2017
Online data-intensive (OLDI) services use anytime algorithms to compute over large amounts of data and respond quickly. Interactive response times are a priority, so OLDI services parallelize query execution across distributed software components and return best effort answers based on the data so far processed. Omitted data from slow components could lead to better answers, but tracing online how much better the answers could be is difficult. We propose Ubora, a design approach to measure the effect of slow-running components on the quality of answers. Ubora randomly samples online queries and executes them a second time. The first online execution omits data from slow components and provides interactive answers. The second execution uses mature results from intermediate components completed after the online execution finishes. Ubora uses memoization to speed up mature executions by replaying network messages exchanged between components. Our systems-level implementation works for a wide range of services, including Hadoop/Yarn, Apache Lucene, the EasyRec Recommendation Engine, and the OpenEphyra question-answering system. Ubora computes answer quality with more mature executions per second than competing approaches that do not use memoization. With Ubora, we show that answer quality is effective at guiding online admission control. While achieving the same answer quality on high-priority queries, our adaptive controller had 55% higher peak throughput on low-priority queries than a competing controller guided by the rate of timeouts.